Flow Network Theory using Edmonds-Karp Algorithm

Introduction

The Edmonds-Karp Algorithm is an implementation of the Ford-Fulkerson method. Its purpose is to compute the maximum flow in a flow network. The algorithm was published by Jack Edmonds and Richard Karp in 1972 in the paper entitled:

Edmonds, Jack; Karp, Richard M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. Association for Computing Machinery. 19 (2): 248–264. doi:10.1145/321694.321699.

The Edmonds-Karp Algorithm has a time complexity of: $O (V^{2}, E)$

Flow Network

A Flow Network is a directed graph, where each edge has a maximum flow capacity. Each edge can receive some amount of flow as long as that flow is less than or equal to that edge's capacity. The vertices in a flow network are called nodes. The edges are called links or arcs. Every flow network contains a source and sink node. A source node only contains outgoing links to the network and can be thought of as having an infinite supply. A sink node's flow output is only limited by the network. With the exception for source and sink nodes, the amount of flow entering a node must equal the amount of flow leaving the node.

\sum i n p u t = \sum o u t p u t

The Flow Network Problem:

We are given:

A directed graph with a set of edges and vertices
A source vertex capable of providing infinite flow
A target/sink vertex that we wish to measure the maximum flow output
Every edge has a capacity limit

Goal: We want to find the actual flow through the network so that we maximize the output at the sink node. Let S be the source node, T be the target/sink node, and v be some vertex.

Flow Value = $\sum_{a l l v} f (S, v) = \sum_{a l l v} f (v, T)$

Our constraints

The flow through an edge is limited by the edge's capacity constraint:

L e t c (x, y) e q u a l c a p a c i t y o f e d g e \vec{x y}

L e t f (x, y) e q u a l a c t u a l f l o w i n e d g e \vec{x y}

0 \leq f (x, y) \leq c (x, y)

Flow conservation:

For all $u \neq S, T$ $\sum_{a l l v} f (v, u) = \sum_{a l l v} f (u, v)$

Observations and Simplifications:

Cycles: If a cycle has flow on all edges, then we can get an equivalent solution with greater than or equal to one of the edges having zero flow. Why send product (flow) in a cycle with positive flow?
Notice: Any edge $\vec{v S}$ must be part of a cycle. Any solution has an equivalent with $f (v, S) = 0$

Sinks: Any vertex, other than our target sink node, which contains only incoming edges can be removed. In this circumstance flow would never make it to the target node.

Applications

Some applications where it is desirable to find the maximum flow through a network are:

Modeling traffic in a road system
Fluids in pipes
Currents flowing through an electical circuit

The following paper describes some applications of the maximum flow network problem: link

Residual Graph

The residual graph is a tool used in the maximum flow calculations that helps us determine how much you can change in the original graph.

Definition: Given a network $G = (V, E)$ and a flow f, the residual graph r G = ( V ′ , E ′ ) of graph G with respect to the flow f is:

V' = V
Forward Edges: For each edge $e \in E$ with $f (e) < c (e)$ , $e \in E^{'}$ with capacity $c (e) - f (e)$ .
Backward Edges: For each edge $e = (u, v) \in E$ with $f (e) > 0$ , $(v, u) \in E^{'}$ with capacity $f (e)$ .

The following diagram represents the graph at a specific iteration of the maximum flow calcuations. Each edge is annotated with the flow/capacity values.

The residual graph is constructed by creating a new graph with identical edges to the original graph. The weights on the edges in this graph represent the residual capacity available on each edge at the current instance of time during the maximum flow calculations. The residual flow is simply the edge capacity minus the edge flow. Edges with an edge capcity equal to 0 can be elimnated from the graph.

We then create a new graph containing all the original edges but with their directions reversed. Each of these edges contain weights equal to the current flow rates. Any edges that have a weight of zero can be removed.

These two graphs are then merged together to produce the Residual Graph

Augmenting Paths

An Augmenting path is any path from the source to the sink that can currently take more flow. The method for finding an augmenting path is the key feature of the Edmonds-Karp Algorithm. The Edmonds-Karp algorithm uses a Breadth First Search (BFS) to find the augmenting path. Over the course of the algorithm, flow is monotonically increased. There are instances where a path from the source to the sink can take on more flow, and that is an augmenting path.

The Residual Network contains all potential flow changes. Every edge in the network is represented in the Residual Network at lease once. Any directed path from source to sink in the Residual Network means we improve the solution. Once we find an augmenting path, we find the smallest weight on that path and use that value to increase the flow. This value is added to edges in the Flow Network if the edge in the Residual Graph is a forward edge. This value is subtracted from edges in the Flow Network if the edge is the Residual Graph is a backward edge. We then regenerate the Residual Graph and repeat until we no longer find an augmenting path.

Maximum Flow and Minimum Cut

Theorem

maximum-flow minimum-cut theorem states that The maximum flow through any network from a given source to a given sink is exactly the sum of the edge weights that, if removed, would totally disconnect the source from the sink.

So what is a flow?

A flow can be anything.

It could be data that passes through an Information Technology (IT) network.
It could be packages that need to be shipped from source to destination.
It could be automobiles traveling through a network of roads.

What does a Flow Network Diagram look like?

The simplest of all Flow Network Diagrams appears in the figure below. There exist two nodes, a source, labeled s, and a sink, labeled t. The source and sink nodes are connected by a single edge. The edge is labeled with the flow rate on that edge and the maximum flow capacity allowed across that edge. In this example, the flow rate is 0 and the maximum capacity of the link is 1 and is represented in the form 0/1.

In this Flow Network Diagram, there exists only one edge with a capacity of 1 from the source node to the target node. The maximum flow is equal to the minimum cut through the Flow Network, which can easily be seen to have a value of 1.

The next simple example adds a node in between the source and target with no direct link from source to target. This means the the flow must travel through this node to get to the target. We can then demonstrate the minimum cut is still 1 in this example since the edge from a to t produces the smallest cut that separates the source from the target.

A s-t cut partitions the vertices, V, of a graph into two sets, S and T, where the source node $s \in S$ and the sink or target node $t \in T$ . Furthermore the cut set contains all edges that cross from a node in set S to a node in set T.

Claim: A minimum cut-set is a s-t cut whose capacity is minimal.

Proof:

Let G = (V, E) be a directed graph with s=source node and t=sink node of G respectively.

Now consider the calculated flow=f for G by the Flow Network method. In the residual graph (rG) that is calculated from G after the final flow assignment is generated by the Flow Network method, we can divide the vertices into two subsets:

A: the set of vertices reachable from s in rG
B: the set of remaining vertices. In other words, B = V − A

Claim: f = c(A, B), where the flow is equal to the capacity of the s-t cut.

c (S, T) = \sum_{(u, v) \in S x T} c_{u v}

Given that the flow out from the subset A minus the flow in from the subset A equals the flow for any subset of vertices, A. We need the value of f = c(A, B) to be:

All outgoing edges from the cut to be fully saturated.
All incoming edges to the cut to have zero flow.

Let's consider the following cases:

In graph G, there exists an outgoing edge (x,y) and x is a member of subset A and y is a member of subset B. Let this edge not be saturated. If this is the case, then there must exist a forward edge from x to y in rG. This implies there is a path from S to y in rG, which is a contradiction. Therefore, all outgoing edges are fully saturated.
In graph G, there exists an incoming edge (y,x) and x is a member of subset A and y is a member of subset B. Let this edge carry some non-zero flow. If this is the case, then ther must exist a backward edge from x to y in rG. This implies there is a path from S to y in rG, which is a contradiction. Therefore, all incoming edges must have zero flow.

In conclusion: The capacity of the cut obtained from the description above is equal to the flow obtained in the network.

◻

The Edmonds-Karp Algorithm

The Edmonds-Karp Algorithm is a specific implementation of the Ford-Fulkerson method. In particular, Edmonds-Karp algorithm implements the searching for an augmenting path using the Breadth First Search (BFS) algorithm. Other implementations of the Ford-Fulkerson method use the Depth First Search (DFS) algorithm to find augmenting paths.

Algorithm Pseudocode

               inputs
                  capacityMatrix[n x n] : Capacity Matrix
                  adjMatrix[n x n]      : Adjacency Matrix
                  src                   : Source
                  target                : sink or target
               output 
                  maxFlow               : Maximum Flow Rate

               The Edmonds-Karp:
                  maxFlow = 0             // Initialize the flow to 0
                  residualMatrix[n x n]   // The residual capacity array
  
                  while true:
                    min, augmentPath = BFS(capacityMatrix, adjMatrix, source, target, residualMatrix)
      
                    if m = 0:
                      break
                   
                    maxFlow = maxFlow + min
                   
                    // Walk the augmenting path 
                    v = target
                    while v != src:
                      u = P[v] 
                      residualMatrix[u,v] = residualMatrix[u,v] - min // Reduce the residual capacity            
                      residualMatrix[v,u] = residualMatrix[v,u] + min // Increase the residual capacity of reverse edges 
                      v = u

                  return maxFlow

This algorithm code starts with the maximum flow initially set to 0. The while loop executes until there are no more augmenting paths. Within the while loop, we call BFS to find the shortest path from source to sink and the minimum residual capacity along that path, min. We then walk the augmenting path from target to source. Using the minium residual capacity, we reduce all residual capacities on the augmenting path by min and increase the residual capacities on the reverse edges (representing the flow).

Complexity Analysis

The Edmonds-Karp algorithm runs in $O (V E^{2})$

In each iteration of the algorithm, the shortest path (BFS) between the source and all other vertices must increase monotonically. We need to prove that one iteration of the Edmonds-Karp algorithm is bounded by $O (E)$ . We then need to prove that the number of iterations of the algorithm to find the maximum flow of a network is bounded by $O (VE)$ iterations. Proving these two parts implies that the Edmonds-Karp algorithm is bounded by $O (V E^{2})$ .

Proof:

Part 1: Show that the for every vertex, v, the length of the shortest path from source to v must increase.

This is a proof by contradiction.

Consider a flow augmentation that causes the shortest path to decrease. Let f be the flow before such an augmentation and let f' be the flow just after. There must exist a vertex, v, such that:

d i s t a n c e_{f^{^{'}}} (s, v) < d i s t a n c e_{f} (s, v)

Now, suppose there is a shortest path from s to v that has to travel through vertex u in the residual graph. Let's assume the shortest path from s to v is 1 more the shortest path from s to u:

d i s t a n c e_{f^{^{'}}} (s, u) = d i s t a n c e_{f^{^{'}}} (s, v) - 1

The shortest path from s to u did not decrease with the new flow as result of how we choose v, therefore:

d i s t a n c e_{f^{^{'}}} (s, u) \geq d i s t a n c e_{f} (s, u)

However, the edge (u,v) can not exist in the residual graph. Assuming we are using integer edge lengths, the following relationships would exist if the edge existed:

$d i s t a n c e_{f} (s, v) \leq d i s t a n c e_{f} (s, u) + 1$ (triangle inequality)
$d i s t a n c e_{f} (s, v) \leq d i s t a n c e_{f^{^{'}}} (s, u) + 1$ (shortest path decreases with f')
$d i s t a n c e_{f} (s, v) \leq d i s t a n c e_{f^{^{'}}} (s, v)$ (the relationship between (s,u) and (s,v)

The third relationship would be violated. The shortest path did not decrease with flow f'. A contradiction.

Recap:
The shortest path increases monontonically in the residual graph. Therefore the length of one iteration is bounded in the Edmonds-Karp algorithm to O(E).

Part 2: Show the bound on the number of iterations that the Edmonds-Karp algorithm must perform to find maximum flow.

Let's define some terminolgy first:

Critical Edge: is an edge on the augmenting path whose residual capacity equals the residual capacity of the path.

Given an augmenting path with a critical edge, the critical edge's capacity will be filled by this augmenting path. Once this happens, the edge will be removed from the residual network. This proof will show that each edge of the graph's edge set can be critical at most $\frac{| V |}{2}$ times.

Let an edge in the graph be defined by the vertices u and v. Furthermore, let s be the source node in the graph. Now, when the edge is first considered to be critical, then the distance realtionship becomes:

d i s t a n c e_{f} (s, v) = d i s t a n c e_{f} (s, u) + 1

When the flow is augmented, the edge (u,v) will disappear in the residual network. Now, for it to reappear, the flow from u to v must be decreased. This can only occur if the edge (v,u) appears on the augmenting path. Let f', be the flow when this situation occurs.

d i s t a n c e_{f^{^{'}}} (s, u) = d i s t a n c e_{f^{^{'}}} (s, v) + 1

From the proof in Part 1, we have the relationship of (s,u) and (s,v) defined by $d i s t a n c e_{f} (s, v) \leq d i s t a n c e_{f^{^{'}}} (s, v)$ . We can then perform substitions to get:

d i s t a n c e_{f^{^{'}}} (s, u) \geq d i s t a n c e_{f} (s, v) + 1

Now, during the time that edge (u,v) first became critical to when the it became critical again, the distance between the source and u increases by at least 2.

d i s t a n c e_{f^{^{'}}} (s, u) \geq d i s t a n c e_{f} (s, v) + 2

The itermediate vertices on the shortest path from s to u cannot contain vertices s, u, or t. Therefore, the distance to vertex u is at most $| V | - 2$ . Since the distance from the source increases by at least 2 every time an edge becomes critical, the edge (u,v) can become critical at most $\frac{| V | - 2}{2}$ times. An edge can become critical at most $O (| V |)$ times. Now, there are a total of $O (| E |)$ edges. Therefore, the number of iterations that the Edmonds-Karp algorithm must go through is $O (| V | | E |)$ .

Conclusion:

Now that we proved the bound on the number of iterations and the bound on each iteration, we get an overall time complexity of $O (| V | | E^{2} |)$ .

$◻$