使用networkX的karger min cut算法運行時間很慢

python新增了。嘗試使用networkX包來完成工作，但它似乎比「創建列表清單」來表示圖形的運行時間要長得多。那是因爲nextworkX的數據結構對於這個簡單的任務太多了嗎？順便說一句，結果會輸出兩倍的答案。因爲read_adjlist函數將爲文件中的u和v節點計算相同的邊兩次。有什麼辦法可以避免這種情況，並允許識別並行邊緣？使用networkX的karger min cut算法運行時間很慢

謝謝大家。

import networkx as nx 
import random 

Graph_Adjacency_List = "***.txt" 
handle = open(Graph_Adjacency_List, 'r') 
G=nx.read_adjlist(handle,create_using=nx.MultiGraph(), nodetype=int) 

def cut(G): 
    while G.number_of_nodes()>2 : 
     u,v= random.choice(G.edges()) 
     G = nx.contracted_edge(G, (u, v), self_loops=False) 
    return G.number_of_edges() 

m=100 
for i in range(1000): 
    random.seed() 
    c=cut(G) 
    if c< m: 
     m=c 
     print m

來源

2016-07-04 Michael

剛上爲什麼這是一個緩慢的快速評論：'nx.contracted_edge'返回與一個全新的圖形邊收縮。它僅保留原始圖。所以每次通過'cut'中的'while'時，它會生成一個新圖。這可能是減慢速度的原因。您可以通過創建自己的函數來避免這種情況，以收縮修改圖形的邊。如果你這樣做，你應該發送一份G而不是G的副本。 – Joel

是的，契約功能保持原來的完好無損。但G是功能削減中的局部變量，並在每次收縮時得到更新。 for循環中的G始終是相同的，但是在每次迭代時發送的副本都將被剪切。 @joel – Michael

我的觀點是這很慢。每次調用'nx.contracted_edge'時，都會創建一個新圖。這意味着，所有的節點和所有的邊都被重新創建。這幾乎可以肯定是運行時的絕大部分。如果您只需在「剪切」之前創建一個副本，然後修改該副本，則不必每次都重新創建一個新圖。 – Joel

來解決，我只是返回的邊緣重複計算：

int(G.number_of_edges()/2)

相反的：

G.number_of_edges()

爲了與算法是解決問題慢我didn't使用nx.contracted_edge，該函數返回一個新圖形，需要很長時間像其他人一樣評論。我沒有到位的操作，看着爲nx.contracted_edge源代碼，以G交換H：

new_edges = ((u, w, d) for x, w, d in G.edges(v, data=True) 
       if False or w != u) 
v_data = G.node[v] 
G.remove_node(v) 
G.add_edges_from(new_edges) 
if 'contraction' in G.node[u]: 
    G.node[u]['contraction'][v] = v_data 
else: 
    G.node[u]['contraction'] = {v: v_data}

來源

2016-09-24 18:41:41

使用networkX的karger min cut算法運行時間很慢

回答

相關問題