问题描述
我想使用Networkx来计算图形中两个节点之间的最小边沿切割，同时考虑到边沿权重。 我尝试了和函数，但它们给出的结果相同，因为它们仅考虑了边的数量。 我制作了一个简单的图形来解决该问题（尝试在其中找到节点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()
这两个函数的输出均为
[(3, 4)]，其总边权重为3。如果考虑权重，则输出边应为[(0,2),(1,3)]且总边缘重量为2。
我不确定Networkx是否提供这种功能，但是如果不提供，则以最简单的方式对其进行计算是否可以解决问题。
1楼
看来可以使用使用最小切割最大流量定理的来完成，并且可以指定边缘的容量以考虑重量。 它返回剪切的权重以及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)]
这是预期的输出。