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

Question

I would like to compute the minimum edge cut between two nodes in a graph using Networkx while taking Edge weights into consideration. I tried both minimum_edge_cut and minimum_st_edge_cut functions but they give the same result as they take only the number of edges into consideration. I produced a simple graph to address the problem (where I try to find the minimum edge cut between nodes 0 and 4) as follows:

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.

I am not sure if Networkx provides such capability but if not, computing it by the simplest means would solve the problem.

Answer 1

It appears that it can be done using the minimum_cut which use the min-cut max flow theorem, and the capacity of edge can be specified to take weight into consideration. It returns the cut weight as well as 2 sets of nodes (a set for each partition created by the cut). Then finding the edges passing through the cut can be done by 2 nested loops where edges between the 2 sets of nodes are stored. Here is the part of the code I used to implement the solution for the example given in the question:

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

where (by printing out):

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

Which is the expected output.