Python NetworkX从节点作为根在有向图中找到一个子图

本文介绍了Python NetworkX从节点作为根在有向图中找到一个子图的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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 ?

推荐答案

所需的功能是 dfs_preorder_nodes() .这是一个基于您的数据的演示:

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.