网络X的起始节点和结束节点

Question

有人知道如何获取有向图的所有起始节点和终止节点吗？ 如果图不是一个循环并且包含多个分支，我想要获取起始节点和所有的终止节点（如果有多个分支，则可能会有多个终止节点）。

我想要获取这些节点的原因是因为我想要打印出所有的路径（networkx中有一个内置函数叫做simple path），而这需要起始节点和终止节点。

- cyntha

Answer 1

起始节点将是入度为0的节点。结束节点将具有出度为0。

这是一个有向图的示例： 请注意，节点A、B和C是起始节点，编号节点具有指向内部和外部的边缘，节点X、Y和Z是结束节点。以下是生成该图形的代码：

import matplotlib.pyplot as plt
import networkx as nx

D = nx.DiGraph()

edges = [('A', '1'), ('B', '2'), ('C', '3'), ('1', '2'),
         ('2', '3'), ('3', '4'), ('3', '5'), ('5', '6'),
         ('4', '5'), ('5', '4'), ('5', '2'), ('2', '6'),
         ('6', '4'), ('4', 'X'), ('5', 'Y'), ('6', 'Z')]
D.add_edges_from(edges)

pos = nx.spring_layout(D)
fig, ax = plt.subplots(figsize=(10, 5))

nx.draw_networkx_nodes(D, pos, ax=ax, node_size=500, node_color="#acddc5", edgecolors='g')
nx.draw_networkx_labels(D, pos, ax=ax, font_weight='bold', font_size=12)
nx.draw_networkx_edges(D, pos, ax=ax, edgelist=edges, edge_color="g")

plt.show()

现在我可以迭代所有节点，使用in_degree和out_degree函数查找入度为0且出度为0的节点。 （这两个函数都返回一个元组迭代器，其中包含图中每个节点的（节点，度数））。

start_nodes = [n for n, d in D.in_degree() if d == 0]
end_nodes = [n for n, d in D.out_degree() if d == 0]

print("Start nodes:", start_nodes)
print("End nodes:", end_nodes)

输出：

Start nodes: ['A', 'B', 'C']
End nodes: ['X', 'Y', 'Z']

- Bill the Lizard

---

嘿，谢谢你啊XD。我使用了入度和出度，它对我很有效！！！ - cyntha

Answer 2

对于一个有向无环图，NetworkX 提供了一个名为 topological_generations 的函数。这使您能够找到树形结构顶部和底部的节点，例如：

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (3, 5), (3, 6)])

for tier in nx.topological_generations(G):
    print(tier)

输出

[1]
[2]
[3]
[4, 5, 6]

假设有三层或更多层，仅抓取第一层和最后一层：

first, *middle, last = nx.topological_generations(G)
print(f'First tier:  {first}')
print(f'Lowest tier: {last}')
paths = list(nx.all_simple_paths(G, 1, 6))
print(f'Simple paths from 1 to 6: {paths}')

输出

First tier:  [1]
Lowest tier: [4, 5, 6]
Simple paths from 1 to 6: [[1, 2, 3, 6]]

- MorningSciFi

---

非常感谢您提供的所有示例，非常有帮助！另外，如果直接图中包含一个循环怎么办（对于不一致表示抱歉：）） - cyntha

topological_generations 只能在有向无环图（DAG）上工作，因此它会生成一个错误。 - MorningSciFi

哦，我明白了。如果它包含了循环，是否有办法生成图的起始节点和结束节点？我有几个图表，本以为可以跳过其中有循环的那一个，但事实证明我做不到。 - cyntha

如果您有一堆节点和边形成一个圆圈，您将如何决定“起点”和“终点”在哪里？all_simple_paths适用于循环图 - 您可以选择任何一对节点作为起点和终点（在文档中，这些被称为_source_和_target_）。 - MorningSciFi