使用Networkx遍歷圖（Python）

我在使用Networkx管理一個依賴關係圖。比方說，我有這個圖表，每個字母代表一個服務器使用Networkx遍歷圖（Python）

>>> G = nx.Graph() 
>>> G.add_edge("A","B") 
>>> G.add_edge("A","H") 
>>> G.add_edge("H","C") 
>>> G.add_edge("B","C") 
>>> G.add_edge("B","D") 

      A 
     / \ 
     H  B 
    / /\ 
    C   C  D

所以在這裏我們可以看出，起始於A之前，我們需要開始H和B和開始^ h我們需要開始C，然後到入門C凌晨需要啓動C和d

通過擺弄了一下與Networkx我發現我可以通過做一個DFS遍歷

print nx.dfs_successors(G,"A") 
{A:[H,B], H:[C], B:[D] }

但我有這種方法的問題。正如你所看到的，當樹中有兩個相同的字母時，Networkx只選擇將它們中的一個放入最終結構中（這是正確的）但我需要具有完整的結構如何強制Networkx添加結構B：[D，C] ??

我要精確，通過做

>>> nx.dfs_successors(G,"B") 
{'B': ['C', 'D']}

所以一切都是「內部」是正確的，它只是顯示它不是我希望的方式dfs_successors。

謝謝

來源

2013-01-10 Johny19

考慮到你的代碼，你的圖形不會像你期望的那樣出來。如果你這樣做：

import pylab as p 
import networkx as nx 

G = nx.Graph() 
G.add_edge("A","B") 
G.add_edge("A","H") 
G.add_edge("H","C") 
G.add_edge("B","C") 
G.add_edge("B","D") 

nx.draw(G) 
p.show()

，你會看到你的圖表爲： Graph

這是由於G.add_edge("A", "B")邏輯：

如果G沒有ID爲「A」的節點，添加它。
如果G沒有ID爲「B」的節點，則添加它。
將「A」連接到具有新邊緣的「B」。

因此，您只能創建五個節點，而不是像您的圖片中那樣創建六個節點。

編輯 Networkx可以將任何可散列值作爲節點的值，並且在圖中它使用str（節點）來標記每個圓。因此，我們可以簡單地定義我們自己的Node類（您可能想要調用Server？）並給它所需的行爲。

import pylab as p 
import networkx as nx 


class Node(object): 
    nodes = [] 

    def __init__(self, label): 
     self._label = label 

    def __str__(self): 
     return self._label 

nodes = [Node(l) for l in ["A","B","C","C","D","H"]] 
edges = [(0,1),(0,5),(5,2),(1,3),(1,4)] 

G = nx.Graph() 
for i,j in edges: 
    G.add_edge(nodes[i], nodes[j]) 

nx.draw(G) 
p.show()

給我們 New graph 還等什麼你想要的。

來源

2013-01-10 14:31:11

謝謝你繪製圖表。這就是我認爲的「Networkx在我背後做的事情。因此，我的問題是：如何使用Networkx創建一個像我的例子中的樹？最適合我的是當我創建G.add_edge（「B」，「C」）一個新的節點「C」創建重用連接到H的insead。 – Johny19

然後，你需要調用新的節點別的東西。可能是C1和C2。就我所知，NetworkX不允許具有相同標籤的多個節點。 – brentlance

但我需要節點具有相同的。就像我在主線中所說的那樣。我的節點是服務器名，我不能更改名稱，否則我不知道哪一個是哪個... 但真的Thorsten Kranz不是「錯」的圖是正確的，B依賴於「C AND D」。它只是算法「dfs_successors（）」輸出B只依賴於D，並且這是錯誤的如果我的樹不可能與Networkx一起使用，那麼其他lib可能嗎？謝謝 – Johny19

我知道你在尋找的是一個拓撲排序 http://networkx.github.com/documentation/latest/reference/generated/networkx.algorithms.dag.topological_sort.html

這隻能如果你有一個DAG（有向無環圖）。如果是這樣你能得到你想要過的樹 - 是這樣的：

import uuid 
import networkx as nx 
import matplotlib.pyplot as plt 
G = nx.DiGraph() 
G.add_edge("A","B") 
G.add_edge("A","H") 
G.add_edge("H","C") 
G.add_edge("B","C") 
G.add_edge("B","D") 

order = nx.topological_sort(G) 
print "topological sort" 
print order 

# build tree 
start = order[0] 
nodes = [order[0]] # start with first node in topological order 
labels = {} 
print "edges" 
tree = nx.Graph() 
while nodes: 
    source = nodes.pop() 
    labels[source] = source 
    for target in G.neighbors(source): 
     if target in tree: 
      t = uuid.uuid1() # new unique id 
     else: 
      t = target 
     labels[t] = target 
     tree.add_edge(source,t) 
     print source,target,source,t 
     nodes.append(target) 

nx.draw(tree,labels=labels) 
plt.show()

繪圖使用標籤映射到節點的ID映射到原來的標籤。

enter image description here

來源

2013-01-11 00:49:37 Aric

使用Networkx遍歷圖（Python）

回答

相關問題