考虑边缘权重的最小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边缘切割

回答

相关问题