考虑边缘重量的最小 s-t 边缘切割

Question

我想使用 Networkx 计算图中两个节点之间的最小边切割，同时考虑边权重。我尝试了两个 minimum_edge_cut and minimum_st_edge_cut 函数，但它们给出了相同的结果，因为它们只考虑了边的数量。我制作了一个简单的图表来解决这个问题（我试图找到节点 0 和 4 之间的最小边缘切割）如下：

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()

The output from both functions was [(3, 4)] which has a total edge weight of 3. While if weights are taken into consideration, the output edges should be [(0,2),(1,3)] with a total edge weight of 2.

我不确定 Networkx 是否提供这种能力，但如果没有，用最简单的方法计算就可以解决问题。

Answer 1

看来可以用minimum_cut来完成，它使用了min-cut max flow theorem，并且可以指定边的容量来考虑权重。它 returns 切割权重以及 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)]

这是预期的输出。

考虑边缘重量的最小 s-t 边缘切割

Minimum s-t Edge cut which takes edge weight into consideration

python

networkx

graph-algorithm