有向无环网络DiGraph组件中有序节点的获取

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

Answer 1

我假设你肯定这些是“有向无圈图”。

然后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)]

这样会更有效率。它所做的是首先生成每个组件中的节点列表。然后对每个组件中的节点进行排序。如果您这样做，您应该看看排序。它将返回一个排序列表，其中包含从它nbunch的任何节点可以到达的所有节点。在您的示例中，这只是nbunch，但更一般的情况下，它不只是返回nbunch。

注意:在您的代码中，不需要list(...)。没有它你就会得到同样的结果。