在網絡x（Python）中獲取DiGraph的根（頭部）

我試圖使用networkx在項目中做一些圖形表示，我不確定如何做一些應該很簡單的事情。我用一堆節點和邊創建了一個有向圖，這樣在這個圖中只有一個根元素。現在，我想要做的是從根開始，然後遍歷每個元素的子元素並從中提取一些信息。我如何獲得這個DiGraph的根元素？在網絡x（Python）中獲取DiGraph的根（頭部）

因此，這將是這樣的：

#This is NOT real code, just pseudopython to convey the general intent of what I'd like to do 

    root = myDiGraph.root() 
    for child in root.children(): 
     iterateThroughChildren(child) 

def iterateThroughChildren(parent): 
    if parent.hasNoChildren(): return 
    for child in parent.children(): 
     //do something 
     // 
     iterateThroughChildren(child)

我沒有看到，建議一個簡單的方法來檢索有向圖的根文檔中任何東西 - 我應該手動推斷呢？：O 我試圖得到iter(myDiGraph)與希望它會迭代開始在根，但順序似乎是隨機的...：\

幫助將不勝感激，謝謝！

來源

2010-11-08 mindthief

在我不明白的觀點中，圖形不一定有根，因此沒有找到它的函數。 – fmark 2010-11-08 09:11:17

這是有道理的。 – mindthief 2010-11-08 18:03:32

如果通過「一個根元素」表示您的有向圖是rooted tree，那麼根將是唯一具有零度入度的節點。

你可以找到線性時間與該節點（在節點數目）：

In [1]: import networkx as nx 

In [2]: G=nx.balanced_tree(2,3,create_using=nx.DiGraph()) # tree rooted at 0 

In [3]: [n for n,d in G.in_degree().items() if d==0] 
Out[3]: [0]

或者你可以使用一個拓撲排序（根是第一項）：

In [4]: nx.topological_sort(G) 
Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]

或者從給定的（隨機）節點開始並跟隨前輩可能會更快，直到找到沒有前輩的節點爲止。

來源

2010-11-08 10:54:30 Aric

+12

Aric寫了networkx。 – hughdbrown 2010-11-08 15:01:51

我嘗試了拓撲排序和工作。速度不是這項行動的主要關注點，所以我可能會堅持這一點，但如果它確實成爲一個問題，我會考慮你的第三種選擇 – mindthief 2010-11-08 18:02:04

在網絡x（Python）中獲取DiGraph的根（頭部）

回答

相關問題