Python NetworkX从节点作为根在有向图中找到一个子图 [英] Python NetworkX find a subgraph in a Directed Graph from a node as root

问题描述

我正在编写代码以从有向图提取信息.该图也具有周期.例如，

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

例如，在上面的示例中， 1.如果输入节点为C，则输出为D 2.如果输入节点是B，则输出节点将是C，D，F，G，A(由于存在一个周期，这使得A到B是双向的) 3.如果输入为G，则输出为空白或空.

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.

python networkx中有什么功能可以用来解决此问题?

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

输出:

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.

请注意，dfs_preorder_nodes()返回一个生成器对象.这就是为什么我打电话给list()以获得可用的输出.

Note that dfs_preorder_nodes() returns a generator object. That is why I called list() to get usable output.

这篇关于Python NetworkX从节点作为根在有向图中找到一个子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！