获取有向无环网络组件中的有序节点 x DiGraph
get ordered nodes in components of directed acyclic networkx DiGraph
我有一个带子图的有向图，其中节点的顺序很重要。
例如我的图有两个子图，都是线性的
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]]
我假设您确定这些是 "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)]
这样效率会更高。它所做的是首先生成每个组件中的节点列表。然后它对每个组件中的节点进行排序。如果你这样做，你应该看看source for topological_sort。它将 return 一个所有节点的排序列表，这些节点可以从它 nbunch 的任何节点到达。在您的情况下，这只是 nbunch，但更一般地说，它不仅必须 return nbunch.
注意：在您的代码中不需要 list(...)。没有它你会得到相同的结果。
我有一个带子图的有向图，其中节点的顺序很重要。
例如我的图有两个子图，都是线性的
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]]
我假设您确定这些是 "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)]
这样效率会更高。它所做的是首先生成每个组件中的节点列表。然后它对每个组件中的节点进行排序。如果你这样做，你应该看看source for topological_sort。它将 return 一个所有节点的排序列表，这些节点可以从它 nbunch 的任何节点到达。在您的情况下，这只是 nbunch，但更一般地说，它不仅必须 return nbunch.
注意：在您的代码中不需要 list(...)。没有它你会得到相同的结果。