在NetworkX中尋找繼任者在有向圖中的後繼者

我正在研究NetworkX中有向圖的一些代碼，並且遇到了可能是我的可疑編程經驗的結果。我想要做的是以下幾點：在NetworkX中尋找繼任者在有向圖中的後繼者

我有一個有向圖G，頂部有兩個「父節點」，所有其他節點都從中流動。在繪製這個網絡時，我想將每個節點稱爲「父節點1」的後代一種顏色，而所有其他節點則是另一種顏色。這意味着我需要一個列表Parent 1的繼任者。

現在，我可以很容易地得到他們的第一層使用：

descend= G.successors(parent1)

問題是，這只是給我的第一代接班人。優選地，我希望繼任者的繼任者，繼任者的繼任者等等。任意地，因爲能夠運行分析並製作圖表而不必確切地知道其中有多少代人是非常有用的。

任何想法如何處理這個？

來源

2011-07-31 Fomite

你不需要後代列表，你只需要給它們着色。爲此，您只需選擇一種遍歷圖的算法並使用它對邊進行着色。

例如，你可以做

from networkx.algorithms.traversal.depth_first_search import dfs_edges 

G = DiGraph(...) 
for edge in dfs_edges(G, parent1): 
    color(edge)

見http://networkx.lanl.gov/reference/algorithms.traversal.html

來源

2011-07-31 01:10:57

它看起來像一個DFS算法可能是我最好的選擇。我沒有使用上面提到的代碼，而是使用了dfs_successors，它看起來像給了我一個來自父級1的所有繼承者的字典。現在只需要將該字典變爲有用的格式。 *討厭*字典。 – Fomite

稍微修改上面的答案，最後使用dfs_successors（G，parent1）確實返回所有後繼的字典，將該字典轉換爲列表，然後奉承該列表http://stackoverflow.com/questions/952914 /製作-A-平列表外的列表，列表功能於蟒/ 952952＃952952。感謝兩位評論者的幫助。 – Fomite

那麼，繼任者的繼任者只是後代的繼承人嗎？

# First successors 
descend = G.successors(parent1) 
# 2nd level successors 
def allDescendants(d1): 
    d2 = [] 
    for d in d1: 
     d2 += G.successors(d) 
    return d2 

descend2 = allDescendants(descend)

要獲得3級的後代，呼叫allDescendants（D2）等

編輯：問題1： allDescend = descend + descend2給你兩套組合，後代的進一步水平做同樣的。

Issue2：如果您在您的圖形有循環，那麼你需要先修改代碼來測試，如果你之前已經訪問過的後代，如：

def allDescendants(d1, exclude): 
    d2 = [] 
    for d in d1: 
     d2 += filter(lambda s: s not in exclude, G.successors(d)) 
    return d2

這樣，你通過allDescend作爲上述函數的第二個參數，所以它不包含在未來的後代中。你一直這樣做直到allDescandants()返回一個空數組，在這種情況下，你知道你已經探索了整個圖，然後你就停下來。

由於這開始看起來像作業，我會讓你弄清楚如何將所有這些組合在一起。 ;）

來源

2011-07-31 00:56:26

兩個問題。 1：運行上面的代碼只給出二級後代。有沒有辦法追加結果來獲得所有後代的基本運行列表？ 2：這個解決方案假設我知道我有多少個關卡。有沒有辦法讓它運行n級，直到它基本上停止獲得新的後代？ – Fomite

順便說一句，不是作業。我已經足夠遠了，因爲我已經完成了作業，並進入「很棒，這聽起來像一個出色的想法，去實現它...」 – Fomite

快速評論：使用'+ ='比'append'更昂貴，因爲新'list'對象在每次循環迭代中被銷燬並創建。可以使用['pympler']（https://github.com/pympler/pympler）和['line_profiler']（https://github.com/rkern/line_profiler）來觀察差異。 –

所以答案是有點清潔和更容易找到在其誰絆倒未來的人，這裏是我最後使用的代碼：

G = DiGraph() # Creates an empty directed graph G 
infile = open(sys.argv[1]) 
for edge in infile: 
    edge1, edge2 = edge.split() #Splits data on the space 
    node1 = int(edge1) #Creates integer version of the node names 
    node2 = int(edge2) 
    G.add_edge(node1,node2) #Adds an edge between two nodes 

parent1=int(sys.argv[2]) 
parent2=int(sys.argv[3]) 

data_successors = dfs_successors(G,parent1) 
successor_list = data_successors.values() 
allsuccessors = [item for sublist in successor_list for item in sublist] 

pos = graphviz_layout(G,prog='dot') 
plt.figure(dpi=300) 
draw_networkx_nodes(G,pos,node_color="LightCoral") 
draw_networkx_nodes(G,pos,nodelist=allsuccessors, node_color="SkyBlue") 
draw_networkx_edges(G,pos,arrows=False) 
draw_networkx_labels(G,pos,font_size=6,font_family='sans-serif',labels=labels)

來源

2011-07-31 19:05:30 Fomite

我相信自從幾年前@Jochen Ritzel的回答以來，Networkx已經發生了變化。

現在以下情況成立，只更改導入語句。

import networkx 
from networkx import dfs_edges 

G = DiGraph(...) 
for edge in dfs_edges(G, parent1): 
    color(edge)

來源

2013-05-15 20:16:59 HeyWatchThis

如果你想獲得的所有後繼節點，而不通過邊緣，另一種可能是：

import networkx as nx 
G = DiGraph(...) 
successors = nx.nodes(nx.dfs_tree(G, your_node))

我注意到，如果你調用來代替：

successors = list(nx.dfs_successors(G, your_node)

的底層的節點以某種方式不包括在內。

來源

2017-08-07 17:53:08 abreschi

在NetworkX中尋找繼任者在有向圖中的後繼者

回答

相關問題