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

Question

我正在编写一个从有向图中提取信息的代码。这个图也有循环结构。例如，

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，则输出为空或null。

在Python networkx中是否有功能可用于解决此问题？

或者，是否有其他工具可以帮助我解决这个问题？

- Amit Jain

---

如果输入是B，输出怎么可能是C、D、F、G、A呢？难道不应该只有C和D吗？ - ninesalt

@Swailem95，B依赖于C和D（第一行）。B依赖于F和G（第三行），F依赖于A（第二行）。实际上应该是C、D、F、G、A、E。我漏掉了这些。 - Amit Jain

Answer 1

您需要的是函数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()以获取可用的输出。

- Hai Vu

---

非常感谢！我尝试了bfs_tree()和dfs_tree()函数，但这个看起来更好！ - Amit Jain

Answer 2

nx.ego_graph()完成了你所描述的功能。使用@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 应该是一个任意大的数字，如果你想获取树中所有节点直到叶子节点。

- Alz