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

===== The Problem =====

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<sub>e</sub>
  * 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<sub>e</sub>
  * //Conservation conditions: For internal nodes, ∑<sub> e into v</sub> //f//(e) = ∑ <sub> e out of v</sub>//f//(e)\\
 --> The //value of a flow f,v(f)// is the amount of flow generated at the source: //v(f)// = ∑<sub> e out of s</sub> //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<sup>R</sup> = (v, u) with capacity f(e)\\
  
--> Residual graph: Gf = (V, Ef )\\
--> Residual edges with positive residual capacity\\
--> E<sub>f</sub> = {e : f(e) < c(e)} ∪ {e<sup>R</sup> : 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<sub>f</sub> 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.