获取有向无环图中组件中的排序节点。

Question

我有一个有子图的有向图，其中节点的顺序很重要。

例如，我的图将有两个子图，都是线性的： 1-->2-->3 & 9-->8-->7-->6

注意：节点名称将是随机且唯一的，在图中没有循环。

NG = nx.DiGraph()
NG.add_edges_from([(1,2),(2,3)])
NG.add_edges_from([(9,8),(8,7),(7,6)])

我需要获取子图或者一个节点列表，这些节点按照它们的连接顺序排序。

我已经尝试过：

[i.nodes() for i in list(nx.weakly_connected_component_subgraphs(NG))]

导致了节点列表的结果，几乎正确，但未按照它们之间的连接排序：

[[1, 2, 3], [8, 9, 6, 7]]

我需要如何操作才能获取已排序的节点列表。例如：

[[1, 2, 3], [9, 8, 7, 6]]

- Fenrir

---

我修改了您的标题，以更贴近问题。请确认它是否可以。 - Joel

Answer 1

我假设您确定这些是“有向无环图”（Directed Acyclic Graphs）。然后，nx.topological_sort(G) 根据您希望的顺序对图中的节点进行排序：也就是说，如果 u 出现在 v 之前，那么就意味着从 v 到 u 没有路径（但可能存在从 u 到 v 的路径）。如果使用 nx.weakly_connected_component_subgraphs(G)，则可以获得感兴趣子图的生成器。因此，我建议的方法是先找到子图，然后再对节点进行排序。

[nx.topological_sort(H) for H in nx.weakly_connected_component_subgraphs(NG)]

应该得到你想要的东西。

---

一种更有效的备选方法：

以前的代码可能不是最有效的，但它很简单。创建每个子图H需要时间，可以避免。 更有效的方法是执行weakly_connected_components（NG）（它生成每个子图中节点列表而不是子图本身）。 这将创建与您已经拥有的相似的列表。 然后进行拓扑排序：

[nx.topological_sort(NG, nbunch=subgraph_nodes) for subgraph_nodes in nx.weakly_connected_components(NG)]

这样会更有效率。它首先生成每个组件中节点的列表，然后按照每个组件中的节点对其进行排序。如果您这样做，应该查看 topological_sort 的源代码。它将返回可从任何节点访问到的所有节点的已排序列表，而在您的情况下，这只是nbunch，但更一般地，它不仅限于返回nbunch。

注意：在您的代码中，没有必要使用list(...)，不使用也能得到相同的结果。

- Joel

---

谢谢，确实这就是我想要做的。我可以百分之百确定每个子图都是DAG，节点代表线性空间中物理上分离的对象。循环或分支是不可能的。 - Fenrir