Let's assume I have this 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:
Currently I am using NetworkX python library, however I am open to choosing another one if it has this capability.
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)