MIN_CUT_VALUE

The minimum cut of a graph is a partition of the nodes into two sets such that the source is in one set and the sink is in the other, and the total capacity of the edges going from the source set to the sink set is minimized.

According to the max-flow min-cut theorem, the value of the minimum cut is equal to the value of the maximum flow in the network. Identifying the minimum cut is particularly useful for finding the bottlenecks in a system.

Excel Usage

=MIN_CUT_VALUE(edges, source, sink)

edges (list[list], required): 2D array of edges [source, target, capacity].
source (str, required): The source node ID.
sink (str, required): The sink node ID.

Returns (float): Capacity of the minimum cut.

Example 1: Simple cut value

Inputs:

edges			source	sink
X	A	3	X	Y
X	B	1
A	C	3
B	C	5
B	D	4
D	E	2
C	Y	2
E	Y	3

Excel formula:

=MIN_CUT_VALUE({"X","A",3;"X","B",1;"A","C",3;"B","C",5;"B","D",4;"D","E",2;"C","Y",2;"E","Y",3}, "X", "Y")

Expected output:

3

Example 2: 2-node graph

Inputs:

edges			source	sink
A	B	5	A	B

Excel formula:

=MIN_CUT_VALUE({"A","B",5}, "A", "B")

Expected output:

5

Example 3: Parallel paths cut

Inputs:

edges			source	sink
S	A	5	S	T
S	B	5
A	T	10
B	T	10

Excel formula:

=MIN_CUT_VALUE({"S","A",5;"S","B",5;"A","T",10;"B","T",10}, "S", "T")

Expected output:

10

Example 4: Zero capacity cut

Inputs:

edges			source	sink
S	A	0	S	T
A	T	5

Excel formula:

=MIN_CUT_VALUE({"S","A",0;"A","T",5}, "S", "T")

Expected output:

0

Python Code

import networkx as nx

def min_cut_value(edges, source, sink):
    """
    Calculate the capacity of the minimum (source, sink) cut.

    See: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.minimum_cut_value.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        edges (list[list]): 2D array of edges [source, target, capacity].
        source (str): The source node ID.
        sink (str): The sink node ID.

    Returns:
        float: Capacity of the minimum cut.
    """
    try:
        def to2d(x):
            return [[x]] if not isinstance(x, list) else x

        edges = to2d(edges)

        if not isinstance(edges, list) or not edges:
            return "Error: edges must be a non-empty 2D list"

        G = nx.DiGraph()
        for row in edges:
            if not isinstance(row, list) or len(row) < 3:
                continue

            u, v = str(row[0]), str(row[1])
            cap = float(row[2])
            G.add_edge(u, v, capacity=cap)

        if G.number_of_edges() == 0:
            return "Error: No valid edges found in input"

        try:
            cut_value = nx.minimum_cut_value(G, str(source), str(sink))
        except nx.NetworkXUnbounded:
            return "Error: All cuts have infinite capacity"

        return float(cut_value)
    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

edges *

2D array of edges [source, target, capacity].

source *

The source node ID.

sink *

The sink node ID.