Network Flow

Overview

Network flow analyzes how quantities move through a directed graph under edge constraints, making it a core tool in optimization, operations research, and infrastructure planning. The central idea is the flow network, where capacities limit movement from a source node to a sink node. In analytics practice, these models help teams quantify throughput limits, identify bottlenecks, and allocate resources efficiently. This category focuses on practical flow and cut computations that are common in transportation, logistics, and routing problems.

Core Concepts: Network flow methods rely on capacity constraints, flow conservation, and objective-driven optimization. In max-flow settings, the objective is to maximize total feasible throughput from source to sink. In cut analysis, the objective is to find the minimum-capacity partition that separates source and sink, with the max-flow/min-cut theorem linking both values. In cost-aware variants, flow is routed to satisfy supply and demand while minimizing total transport cost, often written as \min \sum_{(u,v)\in E} c_{uv} f_{uv} subject to capacity and balance constraints.

Implementation: These tools are implemented with NetworkX, specifically its flow algorithms in the NetworkX flow reference. NetworkX provides robust graph data structures and tested optimization routines for classical flow problems. This makes it suitable for both quick exploratory modeling and production-grade graph analytics pipelines in Python.

Maximum Throughput and Bottlenecks: The MAX_FLOW_VALUE and MIN_CUT_VALUE functions cover the two most fundamental source-sink diagnostics in flow networks. MAX_FLOW_VALUE returns the greatest feasible throughput through the graph, which is useful for capacity planning and stress-testing network designs. MIN_CUT_VALUE returns the capacity of the weakest separating cut, directly exposing bottleneck structure and failure sensitivity. Because max-flow and min-cut are theoretically coupled, using both functions together gives a clear operational picture of performance limits and critical edges.

Cost-Optimal Routing Under Demand: The MIN_COST_FLOW_COST function addresses cases where feasibility alone is not enough and the routing plan must also be economically efficient. It computes the minimum achievable total cost while satisfying node demands (supplies and sinks) and edge capacities. This is especially relevant in supply chain design, workforce assignment, and multi-commodity distribution when transport or processing costs vary by edge. In practice, this complements throughput metrics by answering not just “can flow be sent?” but “what is the least-cost way to send it?”

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

Show 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 len(row) >= 2:
                u, v = str(row[0]), str(row[1])
                cap = float(row[2]) if len(row) >= 3 else float('inf')
                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.

MIN_COST_FLOW_COST

Minimum cost flow problems involve finding the most cost-effective way to transport a certain amount of “commodity” (flow) through a network. Each edge has a capacity and a cost per unit of flow, and nodes can have demands (positives for sinks, negatives for sources).

This is highly useful for supply chain optimization, transportation logistics, and resource allocation where you need to meet requirements while minimizing expenses.

This function returns the total minimum cost to satisfy the given demands.

Excel Usage

=MIN_COST_FLOW_COST(edges, demands)
  • edges (list[list], required): 2D array of edges [source, target, cost, capacity].
  • demands (list[list], required): 2D array of node demands [node, demand]. Negative for supply, positive for demand.

Returns (float): Minimum cost of flow.

Example 1: Simple supply-demand network

Inputs:

edges demands
A B 3 4 A -5
A C 6 10 D 5
B D 1 9
C D 2 5

Excel formula:

=MIN_COST_FLOW_COST({"A","B",3,4;"A","C",6,10;"B","D",1,9;"C","D",2,5}, {"A",-5;"D",5})

Expected output:

24

Example 2: Multiple sources and sinks

Inputs:

edges demands
S1 A 1 S1 -10
S2 A 2 S2 -10
A T1 3 T1 10
A T2 4 T2 10

Excel formula:

=MIN_COST_FLOW_COST({"S1","A",1;"S2","A",2;"A","T1",3;"A","T2",4}, {"S1",-10;"S2",-10;"T1",10;"T2",10})

Expected output:

100

Example 3: Simple bridge with costs

Inputs:

edges demands
A B 1 10 A -5
B C 1 10 C 5

Excel formula:

=MIN_COST_FLOW_COST({"A","B",1,10;"B","C",1,10}, {"A",-5;"C",5})

Expected output:

10

Example 4: High cost short path vs low cost long path

Inputs:

edges demands
A D 10 10 A -1
A B 1 10 D 1
B C 1 10
C D 1 10

Excel formula:

=MIN_COST_FLOW_COST({"A","D",10,10;"A","B",1,10;"B","C",1,10;"C","D",1,10}, {"A",-1;"D",1})

Expected output:

3

Python Code

Show Code 
import networkx as nx

def min_cost_flow_cost(edges, demands):
    """
    Find the minimum cost to satisfy all demands in a network.

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

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

    Args:
        edges (list[list]): 2D array of edges [source, target, cost, capacity].
        demands (list[list]): 2D array of node demands [node, demand]. Negative for supply, positive for demand.

    Returns:
        float: Minimum cost of flow.
    """
    try:
        def to2d(x):
            return [[x]] if not isinstance(x, list) else x

        edges = to2d(edges)
        demands = to2d(demands)

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

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

        G = nx.DiGraph()

        # Process demands
        for row in demands:
                if len(row) >= 2:
                    node, demand = str(row[0]), float(row[1])
                    G.add_node(node, demand=demand)

        # Process edges
        for row in edges:
            if len(row) >= 2:
                u, v = str(row[0]), str(row[1])
                # [u, v, cost, capacity]
                cost = float(row[2]) if len(row) >= 3 else 0.0
                cap = float(row[3]) if len(row) >= 4 else float('inf')
                G.add_edge(u, v, weight=cost, capacity=cap)

        try:
            total_cost = nx.min_cost_flow_cost(G)
            return float(total_cost)
        except nx.NetworkXUnfeasible:
            return "Error: No flow exists that satisfies all demands (sum of demands must be 0 and capacities must suffice)"
        except nx.NetworkXUnbounded:
            return "Error: Flow is unbounded below (negative cost cycle with infinite capacity)"

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

Online Calculator

2D array of edges [source, target, cost, capacity].
2D array of node demands [node, demand]. Negative for supply, positive for demand.

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

Show 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 len(row) >= 2:
                u, v = str(row[0]), str(row[1])
                cap = float(row[2]) if len(row) >= 3 else float('inf')
                G.add_edge(u, v, capacity=cap)

        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

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