考慮邊緣權重的最小s-t邊緣切割

我想在考慮邊緣權重的同時使用Networkx計算圖形中兩個節點之間的最小邊緣切割。我嘗試了minimum_edge_cut和minimum_st_edge_cut函數，但它們給出了相同的結果，因爲它們只考慮邊的數量。我公司生產的簡單的圖形來解決這個問題（其中，我試圖找到節點0和4之間的最小邊切割）如下：其具有總邊加權考慮邊緣權重的最小s-t邊緣切割

G = nx.Graph() 
G.add_nodes_from([0,1,2,3,4]) 
G.add_edges_from([(0,1),(0,2),(1,3),(3,4),(2,3)], weight = 1) 
G[3][4]['weight']=3 
G[0][1]['weight']=2 
G[2][3]['weight']=2 
print minimum_st_edge_cut(G, 0, 4) 
print nx.minimum_edge_cut(G,0,4) 
node_pos=nx.spring_layout(G) 
nx.draw_networkx(G,node_pos,with_labels = True) 
edge_labels = dict (((i,j),G[i][j]['weight']) for (i,j) in G.edges()) 
nx.draw_networkx_edge_labels(G, node_pos, edge_labels=edge_labels) 
plt.show()

從兩個函數的輸出是[(3, 4)] 3.雖然如果權重被考慮在內時，輸出邊緣應[(0,2),(1,3)]具有2

總邊緣權重我不知道如果Networkx provid如果不是這樣，那麼用最簡單的方法計算它就能解決問題。

來源

2015-10-25 Abdallah Sobehy

道歉最初誤讀你以後。會多想一想。 – Joel

@joel檢查我寫的答案，這是我的想法，但如果您有任何意見，將不勝感激。即使是我回答我自己的問題，因爲這是我第一次這樣做。 –

它似乎可以使用minimum_cut，它使用最小切割最大流量定理，邊緣的容量可以指定考慮重量。它返回切割重量以及2組節點（由切割創建的每個分區的集合）。然後找到通過切割的邊緣可以通過2個嵌套循環完成，其中存儲2組節點之間的邊緣。這是我用於實現在問題給出的例子中的解決方案的代碼的一部分：

cut_weight, partitions = nx.minimum_cut(G, 0, 4, capacity='weight') 
edge_cut_list = [] 
for p1_node in partitions[0]: 
    for p2_node in partitions[1]: 
     if G.has_edge(p1_node,p2_node): 
      edge_cut_list.append((p1_node,p2_node))

其中（通過打印）：

cut_weight = 2 
partitions[0] = set([0, 1]) 
partitions[1] = set([2, 3, 4]) 
edge_cut_list = [(0, 2), (1, 3)]

這是預期的輸出。

來源

2015-10-26 14:09:47

考慮邊緣權重的最小s-t邊緣切割

回答

相關問題