CODEWITHSUNDEEP
pythongraphnetworkxedges
filipyoo
filipyoo

Reputation: 357

Python Networkx : find all edges for a given path in a multiDiGraph

In my multi directed graph, I would like to find all the (simple) paths possible between 2 nodes. I manage to get all the path, but cannot distinguish which edge (given that it's a multiDiGraph) the source node takes to reach the target node.

For example I have A->B->C where there are multiple edges in parallele between (A,B) and (B,C). If I have let say 5 parallele edges for A->B and 2 parallele edges for B->C, the all_simple_path(graph, source='A', target='C') will return in total 7 paths, all are of course A->B->C

When using get_edge_data(), it returns ALL the parallele edge between each node. But what I want is to be able to list all the combinations edges taken by the specified nodes in the path.

Thank you !

Upvotes: 9

Views: 3854

Answers (2)

defender
defender

Reputation: 363

Use "all_simple_edge_paths" . It will give index of the edges.

import networkx as nx

G = nx.MultiDiGraph()
G.add_edge(1, 2, **{'prop1': 'A', 'prop2': 'B'})
G.add_edge(1, 3, **{'prop1': 'A', 'prop2': 'C'})
G.add_edge(2, 3, **{'prop1': 'B', 'prop2': 'C'})
G.add_edge(2, 3, **{'prop1': 'B1', 'prop2': 'C1'})

# Our source and destination nodes
source = 1
destination = 3



paths = nx.all_simple_edge_paths(G, source, destination)

for path in paths:
   print(" Path :: ")
   for edge in path:
       src = edge[0]
       dst = edge[1]
       print(str(src)+ " - "+str(dst)+ " :: "+str(G.get_edge_data(edge[0], edge[1])[edge[2]]))

Upvotes: 3

vurmux
vurmux

Reputation: 10020

I think OP doesn't need this answer but it can be useful for others.

networkx has no built-in functions to handle it so we have to do everything manually. nx.all_simple_paths() returns node lists so for MultiDiGraph there will be many repetitions. So firstly we remove them by converting the nx.all_simple_paths() output to set and then iterate for it. For every path we extract node pairs (for example: [1,2,3,4] -> [[1,2],[2,3],[3,4]]) and for each pair we get AtlasView of all edges between them. Here is the code for this algorithm:

import networkx as nx
from pprint import pprint

# Create the graph with unique edges to check the algorithm correctness
G = nx.MultiDiGraph()
G.add_edges_from([
    [1,2],
    [1,2],
    [1,2],
    [2,3],
    [2,3],
    [2,3],
    [3,4],
    [3,4],
    [2,4]
])
G.add_edge(1,2,data='WAKA')
G.add_edge(2,3,data='WAKKA')
G.add_edge(2,4,data='WAKA-WAKA')

# Our source and destination nodes
source = 1
destination = 4

# All unique single paths, like in nx.DiGraph
unique_single_paths = set(
    tuple(path)  # Sets can't be used with lists because they are not hashable
    for path in nx.all_simple_paths(G, source, destination)
)

combined_single_paths = []
for path in unique_single_paths:
    # Get all node pairs in path:
    # [1,2,3,4] -> [[1,2],[2,3],[3,4]]
    pairs = [path[i: i + 2] for i in range(len(path)-1)]

    # Construct the combined list for path
    combined_single_paths.append([
        (pair, G[pair[0]][pair[1]])  # Pair and all node between these nodes
        for pair in pairs
    ])
pprint(combined_single_paths)

[[((1, 2), AtlasView({0: {}, 1: {}, 2: {}, 3: {'data': 'WAKA'}})),
  ((2, 3), AtlasView({0: {}, 1: {}, 2: {}, 3: {'data': 'WAKKA'}})),
  ((3, 4), AtlasView({0: {}, 1: {}}))],
 [((1, 2), AtlasView({0: {}, 1: {}, 2: {}, 3: {'data': 'WAKA'}})),
  ((2, 4), AtlasView({0: {}, 1: {'data': 'WAKA-WAKA'}}))]]

Upvotes: 0

Related Questions