I am writing a code to extract information from a directed graph. This graph has cycles as well. For example,
A->B->C->D
A->E->F->A
B->F->G
From this graph, I want to create a sub graph or the list of the nodes, where the input would be any node, and output would be the graph where the input node is the root, or the list of the nodes that has all the child nodes ( till the end of the graph ) from the input nodes
For example, in the above example,
1. If the input node is C, the output would be D
2. If the input node is B, the output node would be C,D,F,G,A ( Since there is a cycle, which makes A to B bidirectional )
3. If the input is G, the output is blank or null.
Is there any functionality in python networkx, that I can use to solve this problem ?
Alternatively, is there any other tool that can help me solve this problem ?
解决方案
What you want is the function dfs_preorder_nodes(). Here is a little demo based on your data:
import networkx as nx
g = nx.DiGraph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
g.add_edge('A', 'E')
g.add_edge('E', 'F')
g.add_edge('F', 'A')
g.add_edge('B', 'F')
g.add_edge('F', 'G')
print('A:', list(nx.dfs_preorder_nodes(g, 'A')))
print('B:', list(nx.dfs_preorder_nodes(g, 'B')))
print('G:', list(nx.dfs_preorder_nodes(g, 'G')))
Output:
A: ['A', 'B', 'C', 'D', 'F', 'G', 'E']
B: ['B', 'C', 'D', 'F', 'A', 'E', 'G']
G: ['G']
The output includes the starting node. Therefore, if you don't want it, just remove the first element from the list.
Note that dfs_preorder_nodes() returns a generator object. That is why I called list() to get usable output.
