MAX_FLOW_VALUE

Maximum flow (max flow) problems involve finding the maximum amount of flow that can be sent from a source node to a sink node in a network with capacity constraints on its edges.

This is useful for analyzing network capacity, identifying potential improvements in transportation or communication networks, and solving assignment or scheduling problems.

This function returns the total value of the maximum flow as a single scalar.

Excel Usage

=MAX_FLOW_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): Value of the maximum flow.

Example 1: Simple flow network

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:

=MAX_FLOW_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: Single bottleneck

Inputs:

edges source sink
S T 10 S T

Excel formula:

=MAX_FLOW_VALUE({"S","T",10}, "S", "T")

Expected output:

10

Example 3: Large capacity edge

Inputs:

edges source sink
S A 1000000 S T
A T 1000000

Excel formula:

=MAX_FLOW_VALUE({"S","A",1000000;"A","T",1000000}, "S", "T")

Expected output:

1000000

Example 4: Simple weighted flow

Inputs:

edges source sink
A B 10 A D
A C 5
B D 10
C D 10

Excel formula:

=MAX_FLOW_VALUE({"A","B",10;"A","C",5;"B","D",10;"C","D",10}, "A", "D")

Expected output:

15

Example 5: Zero capacity edge

Inputs:

edges source sink
A B 0 A C
B C 5

Excel formula:

=MAX_FLOW_VALUE({"A","B",0;"B","C",5}, "A", "C")

Expected output:

0

Python Code

import networkx as nx

def max_flow_value(edges, source, sink):
    """
    Calculate the maximum flow value between a source and sink.

    See: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.maximum_flow_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: Value of the maximum flow.
    """
    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()
        processed_edges = []
        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])
            processed_edges.append((u, v, cap))

        if not processed_edges:
            return "Error: No valid edges found in input"

        # add_weighted_edges_from uses 'weight', but max_flow uses 'capacity'
        for u, v, cap in processed_edges:
            G.add_edge(u, v, capacity=cap)

        try:
            flow_value = nx.maximum_flow_value(G, str(source), str(sink))
        except nx.NetworkXUnbounded:
            return "Error: Path with infinite capacity exists; flow is unbounded"

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

Online Calculator

2D array of edges [source, target, capacity].
The source node ID.
The sink node ID.