Flow network
- Algorithms course
- Expert
- Lesson 25/41
- 4 min
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.
Practice 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')).
Starter code
def source_capacity(graph, source):
# Total capacity leaving the sourceSample 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'))Expected output
5
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What characterizes the source node?
graph = [('s','a',3), ('s','b',2)]- It has only incoming edges
- It has only outgoing edges Correct answer
- Its capacity is zero
- It is the same as the sink
Explanation: The source has only outgoing edges.
2 capacity condition
if flow[u][v] <= capacity[u][____]:
# flow validif flow[u][v] <= capacity[u][v]:
# flow validExplanation: Compare against capacity[u][v].
3 Flow network concepts
| Term | Meaning |
|---|---|
source |
Produces flow |
sink |
Consumes flow |
capacity |
Maximum flow |
conservation |
In = Out |