7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

Graphs are often used to model transportation networks: edges carry some sort of traffic and nodes pass traffic between edges. In this model:

• capacities on the edges: indicate how much traffic the edges can carry
• Source nodes in the graph: are nodes that generate traffic
• sink nodes: are nodes that absorb traffic that arrives
• The traffic itself is transmitted across edges
  

Flow Networks: In graphs of the form described as above, the traffic is referred to as “flow” which is just the abstract thing generated at source nodes, transmitted across edges and absorbed at sink nodes.
A Flow Network is a directed graph G =(V,E) with the following properties:

• A capacity is associated with each edge e and is a non-negative number denoted as c_e
• There is a single source node s ∈ V
• There is a single sink node t ∈ V
• Nodes other than s and t are called internal nodes
  

Assumptions made about network flows treated in this chapter:

• No edge enter s
• No edge leave t
• There is at least one edge incident to each node
• All capacities are integers

Flows
A flow f satisfies the following properties:

• Capacity Conditions: For each edge e, 0≤ f(e)≤ c_e
• Conservation conditions: For internal nodes, ∑ _{e into v} f(e) = ∑ _{e out of v}f(e)
  –> The value of a flow f,v(f) is the amount of flow generated at the source: v(f) = ∑ _{e out of s} f(e)
  The Maximum Flow Problem: Given a flow network, arrange the traffic so as to make as efficient use as possible of the available capacity. –> Given a flow network, find a flow of maximum possible value.
  
  Designing the Algorithm
  
  Greedy algorithm
  –> Start all edges e ∈ E at f(e) = 0
  –> Find an s-t path P with the most capacity: f(e) < c(e)
  –> Augment flow along path P
  –> Repeat until you get stuck
  However, the greedy algorithm doesn't produce a flow of optimal value. We need a new way of pushing flow so as to attain the optimal value.
  Residual Graph: Gf
  –> Original edge: e = (u, v) ∈ E
  –> Flow f(e), capacity c(e)
  –> Residual edge\\:
  . e = (u, v) w/ capacity c(e) - f(e)
  . e^R = (v, u) with capacity f(e)
  –> Residual graph: Gf = (V, Ef )
  –> Residual edges with positive residual capacity
  –> E_f = {e : f(e) < c(e)} ∪ {e^R : f(e) > 0}
  
  Augmenting Path Algorithm
  –> Ford-Fulkerson(G, s, t, c)
  –> foreach e ∈ E f(e) = 0 # initially no flow
  –> Gf = residual graph
  –> while there exists augmenting path P
  .f = Augment(f, c, P) # change the flow
  .update Gf # build a new residual graph
  –> return f
  Augment(f, c, P) –> b = bottleneck(P) # edge on P with least capacity
  –> foreach e ∈ P
  .if (e ∈ E) f(e) = f(e) + b # forward edge, forward flow
  .else f(eR) = f(e) - b # forward edge, backward flow
  –> return f
  Analyzing the Algorithm
  
  –> At every intermediate stage of the Ford-Fulkerson Algorithm, the flow values {f(e)} and the residual capacities in G_f are integers.
  –> With the above assumption, the Ford-Fulkerson Algorithm terminates in at most C iterations of the While loop.
  –> And the Algorithm can be implemented to run in O(mC) time.
  Reading this section outside class time helped me a lot. In all fairness, I was lost in lectures as things were fast in a very bad week for me. I was delighted to read this section and see things gradually unfold and start making sense.
  For this very reason, I give this section an 9/10.