DSA Edmonds-Karp Algorithm

Finding the maximum flow can be helpful in many areas: for optimizing network traffic, for manufacturing, for supply chain and logistics, or for airline scheduling.

The flow comes from a source vertex (\(s\)) and ends up in a sink vertex (\(t\)), and each edge in the graph allows a flow, limited by a capacity.

Breadth First Search (BFS) to find augmented paths to increase flow. /

The Edmonds-Karp algorithm works by using Breadth-First Search (BFS) to find a path with available capacity from the source to the sink (called an augmented path ), and then sends as much flow as possible through that path.

In the simulation above, the Edmonds-Karp algorithm solves the maximum flow problem: It finds out how much flow can be sent from the source vertex \(s\), to the sink vertex \(t\), and that maximum flow is 8. The numbers in the simulation above are written in fractions, where the first number is the flow, and the second number is the capacity (maximum possible flow in that edge). So for example,

flow, with a capacity of

on that edge. You can see the basic step-by-step description of how the Edmonds-Karp algorithm works below, but we need to go into more detail later to actually understand it.

Start with zero flow on all edges. Use BFS to find an augmented path where more flow can be sent. Do a bottleneck calculation to find out how much flow can be sent through that augmented path. Increase the flow found from the bottleneck calculation for each edge in the augmented path.

The Edmonds-Karp algorithm works by creating and using something called a residual network, which is a representation of the original graph. In the residual network, every edge has a residual capacity, which is the original capacity of the edge, minus the the flow in that edge. The residual capacity can be seen as the leftover capacity in an edge with some flow. For example, if there is a flow of 2 in the \( v_3 \rightarrow v_4 \) edge, and the capacity is 3, the residual flow is 1 in that edge, because there is room for sending 1 more unit of flow through that edge.

The Edmonds-Karp algorithm also uses something called reversed edges to send flow back. This is useful to increase the total flow. To send flow back, in the opposite direction of the edge, a reverse edge is created for each original edge in the network. The Edmonds-Karp algorithm can then use these reverse edges to send flow in the reverse direction. A reversed edge has no flow or capacity, just residual capacity. The residual capacity for a reversed edge is always the same as the flow in the corresponding original edge. In our example, the edge \( v_1 \rightarrow v_3 \) has a flow of 2, which means there is a residual capacity of 2 on the corresponding reversed edge \( v_3 \rightarrow v_1 \). This just means that when there is a flow of 2 on the original edge \( v_1 \rightarrow v_3 \), there is a possibility of sending that same amount of flow back on that edge, but in the reversed direction. Using a reversed edge to push back flow can also be seen as undoing a part of the flow that is already created. The idea of a residual network with residual capacity on edges, and the idea of reversed edges, are central to how the Edmonds-Karp algorithm works, and we will go into more detail about this when we implement the algorithm further down on this page.

There is no flow in the graph to start with. The Edmonds-Karp algorithm starts with using Breadth-First Search to find an augmented path where flow can be increased, which is \(s \rightarrow v_1 \rightarrow v_3 \rightarrow t\). After finding the augmented path, a bottleneck calculation is done to find how much flow can be sent through that path, and that flow is: 2. So a flow of 2 is sent over each edge in the augmented path. /

The next iteration of the Edmonds-Karp algorithm is to do these steps again: Find a new augmented path, find how much the flow in that path can be increased, and increase the flow along the edges in that path accordingly. The next augmented path is found to be \(s \rightarrow v_1 \rightarrow v_4 \rightarrow t \). The flow can only be increased by 1 in this path because there is only room for one more unit of flow in the \( s \rightarrow v_1 \) edge. /

The next augmented path is found to be \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\). The flow can be increased by 3 in this path. The bottleneck (limiting edge) is \( v_2 \rightarrow v_4 \) because the capacity is 3. /

The last augmented path found is \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\). The flow can only be increased by 2 in this path because of edge \( v_4 \rightarrow t \) being the bottleneck in this path with only space for 2 more units of flow (\(capacity-flow=1\)). /

At this point, a new augmenting path cannot be found (it is not possible to find a path where more flow can be sent through from \(s\) to \(t\)), which means the max flow has been found, and the Edmonds-Karp algorithm is finished. The maximum flow is 8. As you can see in the image above, the flow (8) is the same going out of the source vertex \(s\), as the flow going into the sink vertex \(t\). Also, if you take any other vertex than \(s\) or \(t\), you can see that the amount of flow going into a vertex, is the same as the flow going out of it. This is what we call conservation of flow, and this must hold for all such flow networks (directed graphs where each edge has a flow and a capacity).

Graph class.

Graph represents the graph with its vertices and edges: class Graph:

We create the adj_matrix to hold all the edges and edge capacities. Initial values are set to .

size is the number of vertices in the graph.

The vertex_data holds the names of all the vertices.

The add_edge method is used to add an edge from vertex u to vertex v, with capacity c.

The add_vertex_data method is used to add a vertex name to the graph. The index of the vertex is given with the vertex argument, and data is the name of the vertex.

while queue:

for ind, val in enumerate(self.adj_matrix[u]): if not visited[ind] and val > 0: queue.append(ind) visited[ind] = True parent[ind] = u

The visited array helps to avoid revisiting the same vertices during the search for an augmented path. The queue holds vertices to be explored, the search always starts with the source vertex s.

As long as there are vertices to be explored in the queue, take the first vertex out of the queue so that a path can be found from there to the next vertex.

For every adjacent vertex to the current vertex.

If the adjacent vertex is not visited yet, and there is a residual capacity on the edge to that vertex: add it to the queue of vertices that needs to be explored, mark it as visited, and set the parent of the adjacent vertex to be the current vertex u. The parent array holds the parent of a vertex, creating a path from the sink vertex, backwards to the source vertex. The parent is used later in the Edmonds-Karp algorithm, outside the bfs method, to increase flow in the augmented path.

The last line returns visited[t], which is true if the augmented path ends in the sink node t. Returning true means that an augmenting path has been found. The edmonds_karp method is the last method we add to the

while self.bfs(source, sink, parent):

path = []

path.append(source) path.reverse() path_names = [self.vertex_data[node] for node in path]

Initially, the parent array holds invalid index values, because there is no augmented path to begin with, and the max_flow is , and the while loop keeps increasing the max_flow as long as there is an augmented path to increase flow in.

The outer while loop makes sure the Edmonds-Karp algorithm keeps increasing flow as long as there are augmented paths to increase flow along.

The initial flow along an augmented path is infinite, and the possible flow increase will be calculated starting with the sink vertex.

The value for path_flow is found by going backwards from the sink vertex towards the source vertex. The lowest value of residual capacity along the path is what decides how much flow can be sent on the path.