我正在编写代码来从有向图中提取信息。这个图也有循环。例如,

A->B->C->D
A->E->F->A
B->F->G

从这个图中,我想创建一个子图或节点列表,其中输入是任何节点,输出将是输入节点是根的图,或包含所有节点的节点列表来自输入节点的子节点(直到图的末尾)

例如,在上面的例子中,
1.如果输入节点是C,输出就是D
2.如果输入节点是B,输出节点将是C,D,F,G,A(因为有一个循环,这使得A到B是双向的)
3. 如果输入为 G,则输出为空或空。

python networkx 中是否有任何功能可以用来解决这个问题?

或者,有没有其他工具可以帮助我解决这个问题?

最佳答案

你想要的是函数 dfs_preorder_nodes() 。这是一个基于您的数据的小演示:

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

输出包括起始节点。因此,如果您不想要它,只需从列表中删除第一个元素。

请注意 dfs_preorder_nodes() 返回一个生成器对象。这就是我调用 list() 以获得可用输出的原因。

关于Python NetworkX从作为根的节点在有向图中找到子图,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/47892944/

10-16 23:28