CODEWITHSUNDEEP
pythongraphnetworkx
mightymahesh
mightymahesh

Reputation: 303

Python: NetworkX Finding shortest path which contains given list of nodes

I have a graph

G=nx.Graph()

and its edges

G.add_edge('a', 'b')
G.add_edge('a', 'e')
G.add_edge('b', 'c')
G.add_edge('c', 'd')
G.add_edge('d', 'e')
G.add_edge('e', 'g')
G.add_edge('g', 'f')
G.add_edge('g', 'h')
G.add_edge('g', 'k')
G.add_edge('h', 'j')
G.add_edge('h', 'i')

And now suppose I want to get a shortest path which start from node 'a' and should contain nodes ['d', 'k'] so the output should be ['a', 'b', 'c', 'd', 'e', 'g', 'k'] is there a networkx function which can give me such output?

Upvotes: 1

Views: 3533

Answers (2)

user4179775
user4179775

Reputation:

You can use shortest_path to get all the shortest paths, then compare what paths contains ['d', 'k'] by verifying if it's a sublist or no.

pathList= [p for p in nx.shortest_path(G,source='a')] #Target not specified 
l=['d', 'k']
def isSubList(G,l):
    return all(True if x in G else False for x in l )

res= [x for x in pathList if  isSubList(x,l)]

Upvotes: 0

erik-e
erik-e

Reputation: 3891

I don't know of a library function which will only return shortest paths which include multiple nodes.

If it is not too computationally expensive to look at every path between the start node and end node, I would filter the list of return paths to only those which include the nodes I am looking for.

# A lambda to check if the list of paths includes certain nodes
only_containing_nodes = lambda x: 'd' in x and 'k' in x

# If you want to find the shortest path which includes those nodes this
# will get all the paths and then they can be filtered and ordered by
# their length.
all_simple_paths = nx.all_simple_paths(G, source='a', target='k')

# If you only want shortest paths which include both nodes even if a
# path includes the nodes and is not the shortest.
all_shortest_paths = nx.all_shortest_paths(G, source='a', target='k')

filter(only_containing_nodes, all_simple_paths)
# >>> [['a', 'b', 'c', 'd', 'e', 'g', 'k']]

filter(only_containing_nodes, all_shortest_paths)
# >>> []

I hope that helps.

Upvotes: 1

Related Questions