pythonpython-3.xnetworkxgraph-theorygraph-traversal

Find all paths in a directed graph that pass a single node (NetworkX)


Let's assume I have this directed graph:

Original Directed Graph

What's the optimal (complexity and simplicity) way to get every path that passes through a given node?
Let's say I choose node = 4 I want to get this sub-graph:

Sub graph that passes a single node Currently I am using NetworkX python library, however I am open to choosing another one if it has this capability.


Solution

  • Let me propose an "ugly" solution (and I am sure there is a better way). First, find all descendants and ancestors of the node:

    desc = nx.descendants(G, 4)
    anc = nx.ancestors(G, 4)
    

    Next, find the simple paths from each ancestor to the node and from the node to each descendant:

    paths = [path for p in desc for path in nx.all_simple_paths(G, 4, p)]
    paths.extend([path for p in anc for path in nx.all_simple_paths(G, p, 4)])
    

    Finally, reconstruct the digraph from the paths:

    Q = nx.DiGraph()
    for p in paths:
        nx.add_path(Q, p)