獲得有向非循環網絡組件中的有序節點x 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))] 

導致的NodeLists的名單，幾乎右，而是根據自己的連接沒有下令：

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

我怎麼會需要繼續取得列表訂購節點列表。即：

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

Answer 1

我假設你確定這些是「定向非循環圖」。

然後nx.topological_sort(G)排序按想要的順序在圖中的節點：即，如果出現v前u，這意味着存在從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。它將返回一個可從任何節點到達的所有節點的排序列表。在你的情況下，這只是nbunch，但更一般地說，它不只是必須返回nbunch。

---

注意：在您的代碼中不需要list(...)。沒有它你會得到同樣的結果。