Network Flow Analysis

Ford-Fulkerson algorithm:

• Weighted directed graph would be given
• Two vertices, Source S(start), Sink T(finish).
• Constraints:
  1. Flow on an edge doesn't exceed the given capacity of the edge
  2. In-flow is equal to out-flow for every vertex except S and T
• Minimal Cut: Also known as bottle neck capacity.
• Residual Capacity -> Original capacity of the link (edge) - flow
• Augmenting path: Can be done in two ways
  1. Non-full forward edges
  2. Non-empty backward edges

Algorithm Steps: 1. Start with a initial flow as 0 2. While there is an augmenting path from source to sink - Add this path flow to flow 3. Return sink

• Steps for TC
  1. Find an augmenting path O(E)
  2. Compute the bottle neck capacity
  3. Augment each edge and total flow O(F) E -> No. of Edges | F -> Maximum Flow
• Complexity -> (EF)

Push Relabel Algorithm

• Fastest Maximum flow algorithm
• Push Relabel Animation
• Runs is O(\(V^2E\)) time
• Abstract Steps
  1. Initialize PreFlow - init flows and height
  2. While it is possible to do a Push() or Relabel() on a vertex | Do it
  3. Return flow
• Initialize PreFlow()
  • Init height and flow of every vertex to 0
  • Init height of source vertex to number of vertex in graph.
  • Init flow of every edge as 0
  • For all vertices adjacent to source S, flow and excess flow is equal to capacity initially
• Push operation
  • to make flow from a node with excess flow.
  • If Vertex has excess flow and adjancent has smaller height, we push the flow from the vertex to adjacent with lower height.
• Relabel
  • reassign height on transfering water to a neighbour