Flow Network | Ford-Fulkerson Algorithm

Flow Network is a directed graph in which each edge has a capacity and each edge receives a flow. 

In this blog, we will discuss the following things:

• Introduction of: 
• network, max-flow problem
• capacity, flow
• Ford-Fulkerson method
• pseudo code, residual networks, augmenting paths
• cuts of networks

Introduction - 

Network

We can understand Network by looking into some examples: liquids flowing in pipes, parts through assembly lines in a factory, the current through electrical network.

Flow Network: Directed graph, G=(V, E)

                        where V is set of vertices,

                                   E is set of Edges.

Max-Flow problem

Max-flow problem is about finding the feasible flow through a flow network and with maximum possible flow rate.

Capacity(of an edge)

Capacity is the maximum limit of flow that edge can allow.

If (u,v) ∉ E ⇒ c(u,v) = 0

Flow

It is the amount that is currently flowing now in an edge.

Flow in G=(V, E) : f: VxV -> R with 3 properties:

1. Capacity constraint: for all (u,v)∈ V, we need f (u, v) ≤ c (u, v).
2. Skew Symmetry: For all (u, v) ∈ V, we need f (u, v) = - f (u, v).
3. Flow Conservation: For all u ∈ V-{s, t}, 
   

Net flow: Net flow is the positive or negative value of flow f(u,v).

Value of a flow f: It is the amount that can flow in a network.

|f| = Σ f(s, v)

Ford-Fulkerson Method

This algorithm was developed by L. R. Ford, Jr. and D. R. Fulkerson in 1956.

Before understanding this algorithm let us look at the ideas behind this. This algorithm consists of the following three main ideas:

1. Residual network: The residual network G(f) of flow network G with flow f consists of the same vertices v ∈ V as in G which are linked with residual edges (u,v)∈ E(f) which can admit more positive flow.
   The residual capacity c(f) is the amount of additional net flow f(u,v) before exceeding the capacity c(u,v).
   c(f) (u,v) = c(u,v) – f(u,v)
   
   
   
   
   
2. Augmenting Paths: An augmenting path "p" is a path from s(source) to t(destination) in the residual network G(f). It should be free of the cycle.
   

   Residual capacity of p: c(f) (p) = min{c(f) (u,v): (u,v) is on p}

   
   
   
   
   
3. Cuts of Flow Network: A cut (S, T) of a flow network G=(V, E) is a partition of V into S and T = V \ S such that s ∈ S and t ∈ T.

Basic Ford Fulkerson algorithm(Pseudo code):

for each edge(u,v) in E

    do f(u, v) = 0

       f(v, u) = 0

while there exists a path p from s to t in residual network G(f)

    do c(f)[p] = min{c(f)(u, v) | (u, v) is in p}

        for each edge (u, v) in p

            do f(u,v) += c(f)[p]

            f(v, u) = -f(u, v)