Partitioning a graph by the min cut given the `MaximumFlowResult` from `scipy.sparse.csgraph.maximum_flow`

Question

SciPy provides an implementation of a max flow algorithm: https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.maximum_flow.html

I would like to partition the input graph by the min cut into vertex sets S and T.

The SciPy MaximumFlow object contains a flow member, which according to the SciPy GitHub PR 16004:

represents the flow function of the maximum flow, whereas the residual is given by the difference between the input graph and this flow function.

Given the MaximumFlow object, how do I partition the graph into the source and sink nodes by cutting along the min cut?

Answer 1

To do this, we can perform a flood fill with either depth-first or breadth-first search from the source node on the residual graph.

The residual graph is the difference between the original capacity graph and the flow graph returned by maximum_flow. Please note that the residual field in the MaximumFlow object is a misnomer and has been removed (renamed to flow).

To perform depth-first search, we can use the built-in scipy.sparse.csgraph.depth_first_order.

import scipy.sparse
import numpy as np

# create some sample data
"""
  1       5
 / \     / \
0   3 - 4   7
 \ /     \ /
  2       6
"""
source = 0
sink = 7
n_vertices = 8

row = [0, 1, 1, 3, 0, 2, 2, 3, 3, 4, 4, 5, 5, 7, 4, 6, 6, 7]
col = [1, 0, 3, 1, 2, 0, 3, 2, 4, 3, 5, 4, 7, 5, 6, 4, 7, 6]

graph_csr = scipy.sparse.csr_matrix(
    (np.ones(len(row), dtype=np.int32), (np.array(row), np.array(col))),
    shape=(n_vertices, n_vertices),
)
flow = scipy.sparse.csgraph.maximum_flow(graph_csr, source, sink, method="edmonds_karp")

source_nodes = scipy.sparse.csgraph.depth_first_order(graph_csr - flow.flow, source)[0]

source_component = list(source_nodes)
sink_component = list(set(range(n_vertices)) - set(source_component))

print(source_component, sink_component)  # prints [0, 2, 3, 1] [4, 5, 6, 7]

Make sure that your input graph_csr has all the edges, including the reverse edges.

Tested on scipy-1.10.1 with python 3.8.10