CODEWITHSUNDEEP
pythongraphnetworkxbreadth-first-search
softProcess
softProcess

Reputation: 91

Finding a path at Networkx MultiDigraph

I have a MultiDigraph like this:

G=nx.MultiDiGraph()

G.add_edge(1,2,attr=0.5)
G.add_edge(3,2,attr=1.0)

I am trying to find a path from node 1 to node 3 which will provide result something like this:

1 to 2 (forward), 2 to 3 (reverse).

Any Networkx way to do it? Thanks,

Upvotes: 0

Views: 390

Answers (2)

busybear
busybear

Reputation: 10590

You can create an undirected version of your graph and check for a path there. Then go back to your directed graph to find if you had to go along a particular edge backward:

Gu = G.to_undirected()
path = nx.shortest_path(Gu, source=1, target=3)

# Go through each edge in the path to check if it's "forward"
for x in range(len(path)-1):
    if G.has_edge(path[x], path[x+1]):
        print(f'{path[x]} to {path[x+1]} (forward)')
    elif G.has_edge(path[x+1], path[x]):
        print(f'{path[x]} to {path[x+1]} (reverse)')
    else:
        # This shouldn't happen but always good to check
        print(f'No path from {path[x]} to {path[x+1]}')

Upvotes: 1

Mykola Zotko
Mykola Zotko

Reputation: 17911

You can find a path of undirected G and then get all edges, which build the path of undirected G and check if those edges are in the subgraph of the original graph induced by path nodes [(1, 2), (2, 3)] vs [(1, 2), (3, 2)]:

import networkx as nx

G=nx.MultiDiGraph()

G.add_edge(1,2,attr=0.5)
G.add_edge(3,2,attr=1.0)

path = nx.shortest_path(G.to_undirected(), source=1, target=3)
path_edges = zip(path, path[1:])
path_subgraph = G.subgraph(path)

for i in path_edges:
    if i in path_subgraph.edges():
        print(f'{i[0]} to {i[1]} (forward)')
    else:
        print(f'{i[0]} to {i[1]} (reverse)')

# 1 to 2 (forward)
# 2 to 3 (reverse)

Upvotes: 0

Related Questions