Network Flow - Learning Module

Loading content...

0/276

Flow Networks — Source, Sink, and Capacity

Anatomy of a Flow Network

Every flow network is a story of origin, destination, and constraints. The source is where value originates—water from a reservoir, data from a server, goods from a warehouse. The sink is where value is consumed—a city, a user, a retail outlet. The capacities are the physical, contractual, or logical limits on what can flow between any two points.

Understanding these components deeply is essential because the art of solving flow problems lies in modeling. The same real-world situation can be modeled well (yielding an efficient, solvable problem) or poorly (yielding an intractable mess). This page develops your modeling intuition.

Learning Objectives

By the end of this page, you'll master: (1) the formal and intuitive roles of sources and sinks, (2) how to handle multiple sources/sinks using supersources and supersinks, (3) edge capacity interpretation and assignment, (4) modeling vertex capacities using edge splitting, and (5) handling undirected edges in flow problems.

The Source — Where Flow Originates

The source vertex (typically denoted s) is the origin point of all flow in the network. In the physical intuition, it's an infinite reservoir—it can produce as much flow as the network can carry.

Formal Properties of the Source:

No incoming edges (in standard formulation): Flow doesn't enter the source; it only leaves. Mathematically: $$\sum_{v \in V} f(v, s) = 0$$
Net flow producer: The source is the only vertex with positive net outflow: $$\sum_{v \in V} f(s, v) > 0$$
Unlimited supply (implicitly): The source can produce any amount of flow the network can handle. The limitation is downstream capacity, not source capability.

Real-World Source Examples:

What Acts as a Source in Various Domains
Domain	Source Represents	What It Produces
Water distribution	Reservoir or treatment plant	Clean water
Computer networks	Server or data center	Data packets
Supply chain	Factory or warehouse	Manufactured goods
Electrical grid	Power plant or solar farm	Electrical power
Transportation	Airport hub or origin city	Passengers or cargo
Bipartite matching	Set of workers/students/donors	Assignments or allocations

Source as an Abstraction

In many problems, the 'source' isn't a single physical entity but a conceptual aggregation point. For instance, in a city with multiple water treatment plants, we might model a 'super-source' connected to all plants. The source is wherever we define flow to originate for our analysis.

Identifying the Source in Problem Statements:

When analyzing a potential flow problem, ask:

Where does the "stuff" being transported originate?
What entity has unlimited supply relative to the network's capacity?
What's the starting point from which we want to maximize delivery?

Sometimes the source is explicit ("Ship goods from the factory..."). Other times it's implicit ("Assign workers to jobs" — workers are the source of labor capacity).

The Sink — Where Flow Terminates

The sink vertex (typically denoted t) is the destination of all flow in the network. It's an infinite consumer—it can absorb as much flow as arrives.

Formal Properties of the Sink:

No outgoing edges (in standard formulation): Flow doesn't leave the sink; it only enters: $$\sum_{v \in V} f(t, v) = 0$$
Net flow consumer: The sink is the only vertex with positive net inflow: $$\sum_{v \in V} f(v, t) > 0$$
Unlimited demand (implicitly): The sink can absorb any amount of flow the network delivers.

Real-World Sink Examples:

What Acts as a Sink in Various Domains
Domain	Sink Represents	What It Consumes
Water distribution	City or industrial facility	Clean water
Computer networks	Client or user device	Data packets
Supply chain	Retail store or customer	Manufactured goods
Electrical grid	City or industrial load	Electrical power
Transportation	Destination airport or city	Passengers or cargo
Bipartite matching	Set of jobs/schools/patients	Assignments or allocations

The Source-Sink Duality:

Notice the perfect symmetry between source and sink:

Property	Source (s)	Sink (t)
Net flow direction	Outward	Inward
Incoming edges	None (or ignored)	Any number
Outgoing edges	Any number	None (or ignored)
Role in conservation	Exempt—produces flow	Exempt—consumes flow
Value of flow	Equals total outflow	Equals total inflow

This duality is not coincidental. In fact, you can reverse any flow network (swap source and sink, reverse edge directions) and the maximum flow remains the same—a property that has theoretical significance.

Identifying the Sink

When modeling, ask: Where does the 'stuff' ultimately need to end up? What entity represents demand or consumption? What's the endpoint we're trying to maximize delivery to? The sink is where you measure success.

Multiple Sources and Sinks — The Supersource/Supersink Technique

Real-world networks rarely have a single source or single sink. A logistics network might have multiple warehouses. A power grid has numerous power plants and countless consumers. How do we handle this?

The Supersource/Supersink Technique:

We reduce the multi-source/multi-sink problem to the single-source/single-sink problem by adding auxiliary vertices:

Supersource (S): Create a new vertex S connected to ALL original sources with infinite (or very large) capacity edges.
Supersink (T): Create a new vertex T to which ALL original sinks connect with infinite capacity edges.

Now the problem has a single source (S) and single sink (T), and standard algorithms apply.

Visual Example:

Original network with sources s₁, s₂ and sinks t₁, t₂:

    [s₁]----->[ ]----->[ ]----->[t₁]
                \     /
                 \   /
                  \ /
    [s₂]----->[ ]----->[ ]----->[t₂]

Transformed with supersource S and supersink T:

           [s₁]----->[ ]----->[ ]----->[t₁]
          ↗            \     /           ↘
       ∞ /              \   /             \ ∞
        /                \ /               \
      [S]                                  [T]
        \                / \               /
       ∞ \              /   \             / ∞
          ↘            /     \           ↙
           [s₂]----->[ ]----->[ ]----->[t₂]

The ∞ (or large enough) capacities ensure the original network's constraints are the bottlenecks, not the artificial edges.

Capacity of Auxiliary Edges

If an original source sᵢ has limited production capacity Cᵢ, the edge (S, sᵢ) should have capacity Cᵢ, not infinity. Similarly for sink consumption limits. The supersource/supersink technique can incorporate individual source/sink capacities by using finite edge capacities.

supersource_supersink.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def add_supersource_supersink(graph, sources, sinks, 
                                  source_capacities=None, sink_capacities=None):
    """
    Transform a multi-source/multi-sink network to single source/sink.
    
    Args:
        graph: Dict[node, Dict[neighbor, capacity]] - original network
        sources: List[node] - original source vertices
        sinks: List[node] - original sink vertices
        source_capacities: Optional[Dict[node, int]] - per-source limits
        sink_capacities: Optional[Dict[node, int]] - per-sink limits
    
    Returns:
        Tuple of (modified_graph, supersource, supersink)
    """
    SUPERSOURCE = 'S_super'
    SUPERSINK = 'T_super'
    INF = float('inf')
    
    # Copy original graph
    new_graph = {v: dict(edges) for v, edges in graph.items()}
    
    # Add supersource with edges to all original sources
    new_graph[SUPERSOURCE] = {}
    for src in sources:
        capacity = (source_capacities or {}).get(src, INF)
        new_graph[SUPERSOURCE][src] = capacity
    
    # Add supersink with edges from all original sinks
    new_graph[SUPERSINK] = {}
    for sink in sinks:
        capacity = (sink_capacities or {}).get(sink, INF)
        if sink not in new_graph:
            new_graph[sink] = {}
        new_graph[sink][SUPERSINK] = capacity
    
    return new_graph, SUPERSOURCE, SUPERSINK
 
 
# Example: Logistics network with 2 warehouses, 3 stores
graph = {
    'W1': {'Hub': 100},
    'W2': {'Hub': 80},
    'Hub': {'S1': 50, 'S2': 50, 'S3': 50},
    'S1': {}, 'S2': {}, 'S3': {}
}
 
sources = ['W1', 'W2']  # Warehouses
sinks = ['S1', 'S2', 'S3']  # Stores
source_caps = {'W1': 100, 'W2': 80}  # Warehouse capacities
 
new_graph, ss, st = add_supersource_supersink(
    graph, sources, sinks, source_caps
)
print(f"Supersource: {ss}, Supersink: {st}")

Edge Capacities — The Constraints That Shape Flow

Edge capacities are the fundamental constraints of flow networks. They determine what's possible and, ultimately, the maximum achievable flow.

Formal Definition:

The capacity function c: E → ℝ⁺ ∪ {0} assigns a non-negative real number to each edge, representing the maximum flow that edge can carry.

What Capacities Represent in Different Domains:

Capacity Interpretations Across Domains
Domain	Capacity Represents	Units
Water/Oil pipelines	Pipe diameter, pressure limits	Liters/second, barrels/day
Roads/Highways	Lane count, speed limits	Vehicles/hour
Computer networks	Bandwidth, cable type	Mbps, Gbps
Supply chains	Truck fleet, warehouse space	Units/day, containers/week
Power grids	Wire gauge, transformer limits	Megawatts
Matching problems	Constraint on assignment	Often 1 (binary)

Capacity Properties and Implications:

Non-negativity: c(u, v) ≥ 0. Negative capacities are meaningless (you can't have negative flow limit).
Zero capacity = No edge: If c(u, v) = 0, effectively there's no edge from u to v.
Infinite capacity: Sometimes edges are unconstrained. We model this as c(u, v) = ∞ (in practice, a very large number).
Asymmetry is allowed: c(u, v) ≠ c(v, u) in general. A highway might have 3 lanes northbound but 2 southbound.
Bottleneck effect: The maximum flow through any path is limited by its minimum-capacity edge.

Choosing Capacity Values

When modeling, be deliberate about units. All capacities in a network should use consistent units (e.g., all in gallons/minute, not some in liters/second). Inconsistent units lead to incorrect maximum flow values.

Integer vs. Real Capacities:

In theory, capacities can be real numbers. In practice:

Integer capacities are most common and ensure integer-valued maximum flow (important for matching problems).
Rational capacities can be converted to integers by multiplying by a common denominator.
Irrational capacities can cause Ford-Fulkerson to fail to terminate (though this is pathological and doesn't occur with BFS-based path selection).

Most algorithms assume integer or at least rational capacities. This is not a practical limitation since real-world measurements are inherently rational.

Vertex Capacities — The Edge Splitting Transformation

Standard flow networks only have edge capacities. But what if a vertex itself has limited throughput? For example:

A distribution center can only process 1000 packages per day
A router can only handle 10 Gbps total traffic
A person can only work 8 hours per day

Such vertex capacities require a modeling transformation.

The Edge Splitting (Vertex Splitting) Technique:

To model a vertex v with capacity C, we replace v with two vertices: v_in and v_out, connected by an edge of capacity C.

Transformation Rules:

Replace vertex v with two vertices: v_in (receives all incoming edges) and v_out (sends all outgoing edges).
Connect v_in to v_out with an edge of capacity equal to the vertex capacity.
Redirect edges:
- All edges (u, v) become (u, v_in)
- All edges (v, w) become (v_out, w)

Visual Example:

Original (vertex B has capacity 5):

[A] --10--> [B] --8--> [C]
             ^
             | (capacity 5)

Transformed:

[A] --10--> [B_in] --5--> [B_out] --8--> [C]

Now the vertex capacity is enforced as an edge capacity, and standard algorithms apply.

When to Use Vertex Splitting

Use vertex splitting whenever a node has limited processing capacity. Common scenarios: router bandwidth limits, warehouse handling limits, personnel time constraints, and meeting room occupancy limits in scheduling problems.

vertex_splitting.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
def split_vertices_with_capacity(graph, vertex_capacities):
    """
    Transform vertices with capacity constraints into edge constraints.
    
    Args:
        graph: Dict[node, Dict[neighbor, capacity]]
        vertex_capacities: Dict[node, int] - capacity limits for vertices
    
    Returns:
        Modified graph with split vertices
    """
    new_graph = {}
    
    # Find all incoming edges for each vertex
    incoming = {v: [] for v in graph}
    for u in graph:
        for v in graph[u]:
            if v in incoming:
                incoming[v].append(u)
    
    for v in graph:
        if v in vertex_capacities:
            # Split vertex v into v_in and v_out
            v_in = f"{v}_in"
            v_out = f"{v}_out"
            
            # v_in receives all incoming edges
            new_graph[v_in] = {}
            
            # v_in -> v_out with vertex capacity
            if v_in not in new_graph:
                new_graph[v_in] = {}
            new_graph[v_in][v_out] = vertex_capacities[v]
            
            # v_out sends all outgoing edges
            new_graph[v_out] = {}
            for neighbor, cap in graph[v].items():
                target = f"{neighbor}_in" if neighbor in vertex_capacities else neighbor
                new_graph[v_out][target] = cap
        else:
            # Copy vertex unchanged
            new_graph[v] = {}
            for neighbor, cap in graph[v].items():
                target = f"{neighbor}_in" if neighbor in vertex_capacities else neighbor
                new_graph[v][target] = cap
    
    # Redirect incoming edges to split vertices
    for u in list(new_graph.keys()):
        updated_edges = {}
        for v, cap in new_graph[u].items():
            if v.endswith('_in') or '_' not in v:
                updated_edges[v] = cap
            else:
                updated_edges[v] = cap
        new_graph[u] = updated_edges
    
    return new_graph
 
 
# Example: Distribution network with hub capacity limit
graph = {
    'Source': {'Hub': 100, 'Bypass': 30},
    'Hub': {'Dest1': 50, 'Dest2': 50},
    'Bypass': {'Dest1': 20},
    'Dest1': {}, 'Dest2': {}
}
 
# Hub can only process 40 units total
vertex_caps = {'Hub': 40}
 
transformed = split_vertices_with_capacity(graph, vertex_caps)
print("Transformed graph:", transformed)

Undirected Edges — Handling Bidirectional Flow

Flow networks are defined on directed graphs, but many real-world networks are naturally undirected:

Ethernet cables can carry data in both directions
Roads (without one-way restrictions) allow traffic both ways
Pipes can theoretically carry fluid in either direction

How do we model undirected edges in a directed flow framework?

The Standard Transformation:

Replace each undirected edge {u, v} with capacity c with two directed edges:

(u, v) with capacity c
(v, u) with capacity c

This allows flow in either direction, up to the shared capacity.

A Subtle Issue — Anti-Parallel Edges

If the original directed graph already has an edge (u, v) and you add (v, u) for an undirected edge, you have anti-parallel edges. Some algorithms handle this naturally; others need the edges to be distinguished (e.g., by introducing an intermediate vertex).

Two Semantics for Undirected Edges:

Semantics 1 — Independent Capacities:

Flow can go both ways simultaneously
u→v and v→u can both carry positive flow
Total capacity is 2c (c in each direction)

Semantics 2 — Shared Capacity:

Flow goes one direction at a time (net flow)
If f(u,v) > 0, then f(v,u) = 0
Total capacity is c

Most applications use Semantics 1. The algorithms naturally produce optimal solutions that don't waste capacity sending flow in circles.

Example Transformation:

Undirected:           Directed:
[A] ===10=== [B]  →   [A] --10--> [B]
                      [A] <--10-- [B]

Both directed edges have capacity 10. The maximum flow algorithm will use whichever direction(s) are most beneficial.

Directed vs Undirected Edge Handling
Scenario	Original Edge	Flow Network Representation
One-way street	A → B (cap 50)	A → B (cap 50)
Two-way road	A ↔ B (cap 50)	A → B (cap 50), B → A (cap 50)
Asymmetric capacity	A ↔ B (30/50)	A → B (cap 30), B → A (cap 50)
Existing anti-parallel	A → B, B → A	Keep both, distinguish if needed

Flow Network Modeling Patterns

Mastering flow networks requires recognizing common modeling patterns. Here are essential transformations that appear repeatedly in practice.

Essential Modeling Patterns

•Lower bound on flow: If an edge must carry at least L units, transform by: reduce capacity by L, and track that L units are "committed." Feasibility requires finding a valid flow with these committed units.
•Node splitting for vertex capacity: Replace v with v_in → v_out with edge capacity = vertex capacity. All incoming edges go to v_in, all outgoing from v_out.
•Time-expanded networks: For dynamic flows over time, replicate the network for each time period with edges connecting time slices.
•Supersource/supersink: Unify multiple sources/sinks into single source/sink with auxiliary edges.
•Cost on edges: For minimum-cost maximum-flow, each edge has both capacity and cost per unit flow. This requires different algorithms (e.g., successive shortest paths).
•Multiple commodities: Different types of flow (e.g., different products) sharing capacity leads to multi-commodity flow—significantly harder and often NP-hard.

The Modeling Mindset

When facing a new problem, ask: (1) What's the source? (2) What's the sink? (3) What are the capacity constraints? (4) Do vertices have constraints needing splitting? (5) Are there edges needing bidirectional handling? (6) Are there multiple sources/sinks needing unification?

The Reduction Skill:

Many problems don't look like flow problems at first glance:

"What's the minimum number of paths needed to cover all edges?" — This is related to flow decomposition.
"Can we assign n workers to n jobs with all constraints satisfied?" — Bipartite matching, reducible to max flow.
"What's the minimum cut separating these sets of vertices?" — Minimum cut is the dual of maximum flow.

Developing an eye for flow reductions is a superpower in algorithm design. When you recognize a flow structure, you gain access to efficient polynomial-time solutions.

Common Modeling Mistakes

Even experienced practitioners make modeling errors. Here are common pitfalls and how to avoid them.

Common Mistakes

•Forgetting vertex capacity constraints (treating hubs as unlimited)
•Using inconsistent units across edges
•Missing edges in the residual graph (forgetting backward edges)
•Incorrect supersource capacity (using ∞ when source has production limits)
•Not handling anti-parallel edges correctly
•Confusing flow with capacity in computations

Best Practices

•Always check if vertices have throughput limits
•Normalize all capacities to a single unit before modeling
•Carefully construct residual graph with both edge types
•Set supersource edges to min(∞, production_limit)
•Introduce intermediate vertices for anti-parallel edges if needed
•Keep flow and capacity in separate data structures

The Silent Error

Modeling errors often don't cause algorithm failures—they produce incorrect answers silently. The algorithm runs fine, but on the wrong network. Always verify your model against small examples where you can compute the answer by hand.

Summary and Preview

We've explored the fundamental components of flow networks in depth. Let's consolidate:

Key Takeaways

•The source is the origin of all flow—it produces, never consumes (exempt from conservation).
•The sink is the destination of all flow—it consumes, never produces (exempt from conservation).
•Multiple sources/sinks are unified using supersource and supersink vertices with carefully chosen capacities.
•Edge capacities are the primary constraints—they limit throughput per edge.
•Vertex capacities are modeled by splitting vertices and creating internal capacity edges.
•Undirected edges become pairs of anti-parallel directed edges.
•Modeling skill is as important as algorithm knowledge—recognizing flow structure unlocks efficient solutions.

What's Next:

With the network components mastered, we're ready for the algorithmic heart of network flow: the Ford-Fulkerson method. We'll explore how augmenting paths systematically increase flow, why the method terminates at optimality, and how to implement it efficiently using BFS (Edmonds-Karp variant).

Modeling Mastery

You now have the vocabulary and techniques to transform real-world problems into flow networks. The transformations you've learned—supersource/supersink, vertex splitting, undirected edge handling—are the bridge between problem statements and solvable flow instances.

Flow Networks — Source, Sink, and Capacity

Anatomy of a Flow Network

Learning Objectives

The Source — Where Flow Originates

Formal Properties of the Source:

No incoming edges (in standard formulation): Flow doesn't enter the source; it only leaves. Mathematically: $$\sum_{v \in V} f(v, s) = 0$$
Net flow producer: The source is the only vertex with positive net outflow: $$\sum_{v \in V} f(s, v) > 0$$
Unlimited supply (implicitly): The source can produce any amount of flow the network can handle. The limitation is downstream capacity, not source capability.

Real-World Source Examples:

What Acts as a Source in Various Domains
Domain	Source Represents	What It Produces
Water distribution	Reservoir or treatment plant	Clean water
Computer networks	Server or data center	Data packets
Supply chain	Factory or warehouse	Manufactured goods
Electrical grid	Power plant or solar farm	Electrical power
Transportation	Airport hub or origin city	Passengers or cargo
Bipartite matching	Set of workers/students/donors	Assignments or allocations

Source as an Abstraction

Identifying the Source in Problem Statements:

When analyzing a potential flow problem, ask:

Where does the "stuff" being transported originate?
What entity has unlimited supply relative to the network's capacity?
What's the starting point from which we want to maximize delivery?

Sometimes the source is explicit ("Ship goods from the factory..."). Other times it's implicit ("Assign workers to jobs" — workers are the source of labor capacity).

The Sink — Where Flow Terminates

The sink vertex (typically denoted t) is the destination of all flow in the network. It's an infinite consumer—it can absorb as much flow as arrives.

Formal Properties of the Sink:

No outgoing edges (in standard formulation): Flow doesn't leave the sink; it only enters: $$\sum_{v \in V} f(t, v) = 0$$
Net flow consumer: The sink is the only vertex with positive net inflow: $$\sum_{v \in V} f(v, t) > 0$$
Unlimited demand (implicitly): The sink can absorb any amount of flow the network delivers.

Real-World Sink Examples:

What Acts as a Sink in Various Domains
Domain	Sink Represents	What It Consumes
Water distribution	City or industrial facility	Clean water
Computer networks	Client or user device	Data packets
Supply chain	Retail store or customer	Manufactured goods
Electrical grid	City or industrial load	Electrical power
Transportation	Destination airport or city	Passengers or cargo
Bipartite matching	Set of jobs/schools/patients	Assignments or allocations

The Source-Sink Duality:

Notice the perfect symmetry between source and sink:

Property	Source (s)	Sink (t)
Net flow direction	Outward	Inward
Incoming edges	None (or ignored)	Any number
Outgoing edges	Any number	None (or ignored)
Role in conservation	Exempt—produces flow	Exempt—consumes flow
Value of flow	Equals total outflow	Equals total inflow

Identifying the Sink

Multiple Sources and Sinks — The Supersource/Supersink Technique

The Supersource/Supersink Technique:

We reduce the multi-source/multi-sink problem to the single-source/single-sink problem by adding auxiliary vertices:

Supersource (S): Create a new vertex S connected to ALL original sources with infinite (or very large) capacity edges.
Supersink (T): Create a new vertex T to which ALL original sinks connect with infinite capacity edges.

Now the problem has a single source (S) and single sink (T), and standard algorithms apply.

Visual Example:

Original network with sources s₁, s₂ and sinks t₁, t₂:

    [s₁]----->[ ]----->[ ]----->[t₁]
                \     /
                 \   /
                  \ /
    [s₂]----->[ ]----->[ ]----->[t₂]

Transformed with supersource S and supersink T:

           [s₁]----->[ ]----->[ ]----->[t₁]
          ↗            \     /           ↘
       ∞ /              \   /             \ ∞
        /                \ /               \
      [S]                                  [T]
        \                / \               /
       ∞ \              /   \             / ∞
          ↘            /     \           ↙
           [s₂]----->[ ]----->[ ]----->[t₂]

The ∞ (or large enough) capacities ensure the original network's constraints are the bottlenecks, not the artificial edges.

Capacity of Auxiliary Edges

supersource_supersink.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def add_supersource_supersink(graph, sources, sinks, 
                                  source_capacities=None, sink_capacities=None):
    """
    Transform a multi-source/multi-sink network to single source/sink.
    
    Args:
        graph: Dict[node, Dict[neighbor, capacity]] - original network
        sources: List[node] - original source vertices
        sinks: List[node] - original sink vertices
        source_capacities: Optional[Dict[node, int]] - per-source limits
        sink_capacities: Optional[Dict[node, int]] - per-sink limits
    
    Returns:
        Tuple of (modified_graph, supersource, supersink)
    """
    SUPERSOURCE = 'S_super'
    SUPERSINK = 'T_super'
    INF = float('inf')
    
    # Copy original graph
    new_graph = {v: dict(edges) for v, edges in graph.items()}
    
    # Add supersource with edges to all original sources
    new_graph[SUPERSOURCE] = {}
    for src in sources:
        capacity = (source_capacities or {}).get(src, INF)
        new_graph[SUPERSOURCE][src] = capacity
    
    # Add supersink with edges from all original sinks
    new_graph[SUPERSINK] = {}
    for sink in sinks:
        capacity = (sink_capacities or {}).get(sink, INF)
        if sink not in new_graph:
            new_graph[sink] = {}
        new_graph[sink][SUPERSINK] = capacity
    
    return new_graph, SUPERSOURCE, SUPERSINK
 
 
# Example: Logistics network with 2 warehouses, 3 stores
graph = {
    'W1': {'Hub': 100},
    'W2': {'Hub': 80},
    'Hub': {'S1': 50, 'S2': 50, 'S3': 50},
    'S1': {}, 'S2': {}, 'S3': {}
}
 
sources = ['W1', 'W2']  # Warehouses
sinks = ['S1', 'S2', 'S3']  # Stores
source_caps = {'W1': 100, 'W2': 80}  # Warehouse capacities
 
new_graph, ss, st = add_supersource_supersink(
    graph, sources, sinks, source_caps
)
print(f"Supersource: {ss}, Supersink: {st}")

Edge Capacities — The Constraints That Shape Flow

Edge capacities are the fundamental constraints of flow networks. They determine what's possible and, ultimately, the maximum achievable flow.

Formal Definition:

The capacity function c: E → ℝ⁺ ∪ {0} assigns a non-negative real number to each edge, representing the maximum flow that edge can carry.

What Capacities Represent in Different Domains:

Capacity Interpretations Across Domains
Domain	Capacity Represents	Units
Water/Oil pipelines	Pipe diameter, pressure limits	Liters/second, barrels/day
Roads/Highways	Lane count, speed limits	Vehicles/hour
Computer networks	Bandwidth, cable type	Mbps, Gbps
Supply chains	Truck fleet, warehouse space	Units/day, containers/week
Power grids	Wire gauge, transformer limits	Megawatts
Matching problems	Constraint on assignment	Often 1 (binary)

Capacity Properties and Implications:

Non-negativity: c(u, v) ≥ 0. Negative capacities are meaningless (you can't have negative flow limit).
Zero capacity = No edge: If c(u, v) = 0, effectively there's no edge from u to v.
Infinite capacity: Sometimes edges are unconstrained. We model this as c(u, v) = ∞ (in practice, a very large number).
Asymmetry is allowed: c(u, v) ≠ c(v, u) in general. A highway might have 3 lanes northbound but 2 southbound.
Bottleneck effect: The maximum flow through any path is limited by its minimum-capacity edge.

Choosing Capacity Values

Integer vs. Real Capacities:

In theory, capacities can be real numbers. In practice:

Integer capacities are most common and ensure integer-valued maximum flow (important for matching problems).
Rational capacities can be converted to integers by multiplying by a common denominator.
Irrational capacities can cause Ford-Fulkerson to fail to terminate (though this is pathological and doesn't occur with BFS-based path selection).

Most algorithms assume integer or at least rational capacities. This is not a practical limitation since real-world measurements are inherently rational.

Vertex Capacities — The Edge Splitting Transformation

Standard flow networks only have edge capacities. But what if a vertex itself has limited throughput? For example:

A distribution center can only process 1000 packages per day
A router can only handle 10 Gbps total traffic
A person can only work 8 hours per day

Such vertex capacities require a modeling transformation.

The Edge Splitting (Vertex Splitting) Technique:

To model a vertex v with capacity C, we replace v with two vertices: v_in and v_out, connected by an edge of capacity C.

Transformation Rules:

Replace vertex v with two vertices: v_in (receives all incoming edges) and v_out (sends all outgoing edges).
Connect v_in to v_out with an edge of capacity equal to the vertex capacity.
Redirect edges:
- All edges (u, v) become (u, v_in)
- All edges (v, w) become (v_out, w)

Visual Example:

Original (vertex B has capacity 5):

[A] --10--> [B] --8--> [C]
             ^
             | (capacity 5)

Transformed:

[A] --10--> [B_in] --5--> [B_out] --8--> [C]

Now the vertex capacity is enforced as an edge capacity, and standard algorithms apply.

When to Use Vertex Splitting

vertex_splitting.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
def split_vertices_with_capacity(graph, vertex_capacities):
    """
    Transform vertices with capacity constraints into edge constraints.
    
    Args:
        graph: Dict[node, Dict[neighbor, capacity]]
        vertex_capacities: Dict[node, int] - capacity limits for vertices
    
    Returns:
        Modified graph with split vertices
    """
    new_graph = {}
    
    # Find all incoming edges for each vertex
    incoming = {v: [] for v in graph}
    for u in graph:
        for v in graph[u]:
            if v in incoming:
                incoming[v].append(u)
    
    for v in graph:
        if v in vertex_capacities:
            # Split vertex v into v_in and v_out
            v_in = f"{v}_in"
            v_out = f"{v}_out"
            
            # v_in receives all incoming edges
            new_graph[v_in] = {}
            
            # v_in -> v_out with vertex capacity
            if v_in not in new_graph:
                new_graph[v_in] = {}
            new_graph[v_in][v_out] = vertex_capacities[v]
            
            # v_out sends all outgoing edges
            new_graph[v_out] = {}
            for neighbor, cap in graph[v].items():
                target = f"{neighbor}_in" if neighbor in vertex_capacities else neighbor
                new_graph[v_out][target] = cap
        else:
            # Copy vertex unchanged
            new_graph[v] = {}
            for neighbor, cap in graph[v].items():
                target = f"{neighbor}_in" if neighbor in vertex_capacities else neighbor
                new_graph[v][target] = cap
    
    # Redirect incoming edges to split vertices
    for u in list(new_graph.keys()):
        updated_edges = {}
        for v, cap in new_graph[u].items():
            if v.endswith('_in') or '_' not in v:
                updated_edges[v] = cap
            else:
                updated_edges[v] = cap
        new_graph[u] = updated_edges
    
    return new_graph
 
 
# Example: Distribution network with hub capacity limit
graph = {
    'Source': {'Hub': 100, 'Bypass': 30},
    'Hub': {'Dest1': 50, 'Dest2': 50},
    'Bypass': {'Dest1': 20},
    'Dest1': {}, 'Dest2': {}
}
 
# Hub can only process 40 units total
vertex_caps = {'Hub': 40}
 
transformed = split_vertices_with_capacity(graph, vertex_caps)
print("Transformed graph:", transformed)

Undirected Edges — Handling Bidirectional Flow

Flow networks are defined on directed graphs, but many real-world networks are naturally undirected:

Ethernet cables can carry data in both directions
Roads (without one-way restrictions) allow traffic both ways
Pipes can theoretically carry fluid in either direction

How do we model undirected edges in a directed flow framework?

The Standard Transformation:

Replace each undirected edge {u, v} with capacity c with two directed edges:

(u, v) with capacity c
(v, u) with capacity c

This allows flow in either direction, up to the shared capacity.

A Subtle Issue — Anti-Parallel Edges

Two Semantics for Undirected Edges:

Semantics 1 — Independent Capacities:

Flow can go both ways simultaneously
u→v and v→u can both carry positive flow
Total capacity is 2c (c in each direction)

Semantics 2 — Shared Capacity:

Flow goes one direction at a time (net flow)
If f(u,v) > 0, then f(v,u) = 0
Total capacity is c

Most applications use Semantics 1. The algorithms naturally produce optimal solutions that don't waste capacity sending flow in circles.

Example Transformation:

Undirected:           Directed:
[A] ===10=== [B]  →   [A] --10--> [B]
                      [A] <--10-- [B]

Both directed edges have capacity 10. The maximum flow algorithm will use whichever direction(s) are most beneficial.

Directed vs Undirected Edge Handling
Scenario	Original Edge	Flow Network Representation
One-way street	A → B (cap 50)	A → B (cap 50)
Two-way road	A ↔ B (cap 50)	A → B (cap 50), B → A (cap 50)
Asymmetric capacity	A ↔ B (30/50)	A → B (cap 30), B → A (cap 50)
Existing anti-parallel	A → B, B → A	Keep both, distinguish if needed

Flow Network Modeling Patterns

Mastering flow networks requires recognizing common modeling patterns. Here are essential transformations that appear repeatedly in practice.

Essential Modeling Patterns

•Lower bound on flow: If an edge must carry at least L units, transform by: reduce capacity by L, and track that L units are "committed." Feasibility requires finding a valid flow with these committed units.
•Node splitting for vertex capacity: Replace v with v_in → v_out with edge capacity = vertex capacity. All incoming edges go to v_in, all outgoing from v_out.
•Time-expanded networks: For dynamic flows over time, replicate the network for each time period with edges connecting time slices.
•Supersource/supersink: Unify multiple sources/sinks into single source/sink with auxiliary edges.
•Cost on edges: For minimum-cost maximum-flow, each edge has both capacity and cost per unit flow. This requires different algorithms (e.g., successive shortest paths).
•Multiple commodities: Different types of flow (e.g., different products) sharing capacity leads to multi-commodity flow—significantly harder and often NP-hard.

The Modeling Mindset

The Reduction Skill:

Many problems don't look like flow problems at first glance:

"What's the minimum number of paths needed to cover all edges?" — This is related to flow decomposition.
"Can we assign n workers to n jobs with all constraints satisfied?" — Bipartite matching, reducible to max flow.
"What's the minimum cut separating these sets of vertices?" — Minimum cut is the dual of maximum flow.

Developing an eye for flow reductions is a superpower in algorithm design. When you recognize a flow structure, you gain access to efficient polynomial-time solutions.

Common Modeling Mistakes

Even experienced practitioners make modeling errors. Here are common pitfalls and how to avoid them.

Common Mistakes

•Forgetting vertex capacity constraints (treating hubs as unlimited)
•Using inconsistent units across edges
•Missing edges in the residual graph (forgetting backward edges)
•Incorrect supersource capacity (using ∞ when source has production limits)
•Not handling anti-parallel edges correctly
•Confusing flow with capacity in computations

Best Practices

•Always check if vertices have throughput limits
•Normalize all capacities to a single unit before modeling
•Carefully construct residual graph with both edge types
•Set supersource edges to min(∞, production_limit)
•Introduce intermediate vertices for anti-parallel edges if needed
•Keep flow and capacity in separate data structures

The Silent Error

Summary and Preview

We've explored the fundamental components of flow networks in depth. Let's consolidate:

Key Takeaways

•The source is the origin of all flow—it produces, never consumes (exempt from conservation).
•The sink is the destination of all flow—it consumes, never produces (exempt from conservation).
•Multiple sources/sinks are unified using supersource and supersink vertices with carefully chosen capacities.
•Edge capacities are the primary constraints—they limit throughput per edge.
•Vertex capacities are modeled by splitting vertices and creating internal capacity edges.
•Undirected edges become pairs of anti-parallel directed edges.
•Modeling skill is as important as algorithm knowledge—recognizing flow structure unlocks efficient solutions.

What's Next:

Modeling Mastery