Python NetworkX find a subgraph in a Directed Grap

问题:

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 ?

回答1:

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.

回答2:

nx.ego_graph() does exactly what you describe. Using the example given by @Hai Vu:

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')

a = nx.ego_graph(g, 'A', radius=100)
a.node
#out: NodeView(('A', 'B', 'C', 'D', 'E', 'F', 'G'))

list(nx.ego_graph(g, 'G', radius=100).node)
#out: ['G']

radius should be an arbitrarily large number if you would like to get all nodes in the tree until the leafs.