Flow network

Source-to-sink flow network model.

Flow network

A flow network is a directed graph with capacities on its edges. Two nodes are special: the source (s) and the sink (t).

Flow on each edge is a value between zero and the edge capacity. Flow is conserved: at every internal node, incoming flow equals outgoing flow.

This model represents many real problems: water distribution, traffic, data transmission and matching.

Flow and capacity

Each edge has a capacity: the maximum flow that can pass through it. The actual flow cannot exceed this capacity.

Flow is conserved: at every internal node, the sum of incoming flow equals the sum of outgoing flow. The total flow leaving the source equals the total flow entering the sink.

This conservation principle underlies all network flow algorithms.

Exercise source_capacity function

Write source_capacity(graph, source). graph is an edge list (u, v, c); return the total capacity of edges leaving the source. Print 5 with print(source_capacity([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3)], 's')).

Show example solution

def source_capacity(graph, source):
    # Total capacity leaving the source
    total = 0
    for u, v, c in graph:
        if u == source:
            total += c
    return total
print(source_capacity([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3)], 's'))

Test yourself

What characterizes the source node?
```
graph = [('s','a',3), ('s','b',2)]
```
- It has only incoming edges
- It has only outgoing edges
- Its capacity is zero
- It is the same as the sink
Show answer

It has only outgoing edges — The source has only outgoing edges.

capacity condition

if flow[u][v] <= capacity[u][____]:
    # flow valid

Show answer

if flow[u][v] <= capacity[u][v]:
    # flow valid

Flow network concepts

source

Produces flow
sink

Consumes flow
capacity

Maximum flow
conservation

In = Out

Next lesson: Ford-Fulkerson

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies