DSAEdmonds-Karp Algorithm

The Edmonds-Karp Algorithm

The Edmonds-Karp algorithm solvesthe maximum flow problem for a directed graph.

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.

The Edmonds-Karp algorithm is very similar tothe Ford-Fulkerson algorithm, except the Edmonds-Karp algorithm usesBreadth 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 anaugmented path), and then sends as much flow as possible through that path.

The Edmonds-Karp algorithm continues to find new paths to send more flow through until the maximum flow is reached.

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,0/7 on edge \(s \rightarrow v_2\), means there is0 flow, with a capacity of7 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.

Residual Network in Edmonds-Karp

The Edmonds-Karp algorithm works by creating and using something called aresidual network, which is a representation of the original graph.

In the residual network, every edge has aresidual 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.

Reversed Edges in Edmonds-Karp

The Edmonds-Karp algorithm also uses something calledreversed 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.

Manual Run Through

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 callconservation of flow, and this must hold for all such flow networks (directed graphs where each edge has a flow and a capacity).

Implementation of The Edmonds-Karp Algorithm

To implement the Edmonds-Karp algorithm, we create aGraph class.

TheGraph represents the graph with its vertices and edges:

class Graph:    def __init__(self, size):        self.adj_matrix = [[0] * size for _ in range(size)]        self.size = size        self.vertex_data = [''] * size    def add_edge(self, u, v, c):        self.adj_matrix[u][v] = c    def add_vertex_data(self, vertex, data):        if 0<= vertex< self.size:            self.vertex_data[vertex] = data

Line 3:We create theadj_matrix to hold all the edges and edge capacities. Initial values are set to0.

Line 4:size is the number of vertices in the graph.

Line 5:Thevertex_data holds the names of all the vertices.

Line 7-8:Theadd_edge method is used to add an edge from vertexu to vertexv, with capacityc.

Line 10-12:Theadd_vertex_data method is used to add a vertex name to the graph. The index of the vertex is given with thevertex argument, anddata is the name of the vertex.

TheGraph class also contains thebfs method to find augmented paths, using Breadth-First-Search:

    def bfs(self, s, t, parent):        visited = [False] * self.size        queue = []  # Using list as a queue        queue.append(s)        visited[s] = True        while queue:            u = queue.pop(0)  # Pop from the start of the list            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        return visited[t]

Line 15-18:Thevisited array helps to avoid revisiting the same vertices during the search for an augmented path. Thequeue holds vertices to be explored, the search always starts with the source vertexs.

Line 20-21:As long as there are vertices to be explored in thequeue, take the first vertex out of thequeue so that a path can be found from there to the next vertex.

Line 23:For every adjacent vertex to the current vertex.

Line 24-27: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 theparent of the adjacent vertex to be the current vertexu.

Theparent array holds the parent of a vertex, creating a path from the sink vertex, backwards to the source vertex. Theparent is used later in the Edmonds-Karp algorithm, outside thebfs method, to increase flow in the augmented path.

Line 29:The last line returnsvisited[t], which istrue if the augmented path ends in the sink nodet. Returningtrue means that an augmenting path has been found.

Theedmonds_karp method is the last method we add to theGraph class:

    def edmonds_karp(self, source, sink):        parent = [-1] * self.size        max_flow = 0        while self.bfs(source, sink, parent):            path_flow = float("Inf")            s = sink            while(s != source):                path_flow = min(path_flow, self.adj_matrix[parent[s]][s])                s = parent[s]            max_flow += path_flow            v = sink            while(v != source):                u = parent[v]                self.adj_matrix[u][v] -= path_flow                self.adj_matrix[v][u] += path_flow                v = parent[v]            path = []            v = sink            while(v != source):                path.append(v)                v = parent[v]            path.append(source)            path.reverse()            path_names = [self.vertex_data[node] for node in path]            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)        return max_flow

Initially, theparent array holds invalid index values, because there is no augmented path to begin with, and themax_flow is0, and thewhile loop keeps increasing themax_flow as long as there is an augmented path to increase flow in.

Line 35:The outerwhile loop makes sure the Edmonds-Karp algorithm keeps increasing flow as long as there are augmented paths to increase flow along.

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

Line 38-40:The value forpath_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.

Line 42:path_flow is increased by thepath_flow.

Line 44-48:Stepping through the augmented path, going backwards from sink to source, the residual capacity is decreased with thepath_flow on the forward edges, and the residual capacity is increased with thepath_flow on the reversed edges.

Line 50-58:This part of the code is just for printing so that we are able to track each time an augmented path is found, and how much flow is sent through that path.

After defining theGraph class, the vertices and edges must be defined to initialize the specific graph, and the complete code for the Edmonds-Karp algorithm example looks like this:

class Graph:    def __init__(self, size):        self.adj_matrix = [[0] * size for _ in range(size)]        self.size = size        self.vertex_data = [''] * size    def add_edge(self, u, v, c):        self.adj_matrix[u][v] = c    def add_vertex_data(self, vertex, data):        if 0<= vertex< self.size:            self.vertex_data[vertex] = data    def bfs(self, s, t, parent):        visited = [False] * self.size        queue = []  # Using list as a queue        queue.append(s)        visited[s] = True        while queue:            u = queue.pop(0)  # Pop from the start of the list            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        return visited[t]    def edmonds_karp(self, source, sink):        parent = [-1] * self.size        max_flow = 0        while self.bfs(source, sink, parent):            path_flow = float("Inf")            s = sink            while(s != source):                path_flow = min(path_flow, self.adj_matrix[parent[s]][s])                s = parent[s]            max_flow += path_flow            v = sink            while(v != source):                u = parent[v]                self.adj_matrix[u][v] -= path_flow                self.adj_matrix[v][u] += path_flow                v = parent[v]            path = []            v = sink            while(v != source):                path.append(v)                v = parent[v]            path.append(source)            path.reverse()            path_names = [self.vertex_data[node] for node in path]            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)        return max_flow# Example usage:g = Graph(6)vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']for i, name in enumerate(vertex_names):    g.add_vertex_data(i, name)g.add_edge(0, 1, 3)  # s  -> v1, cap: 3g.add_edge(0, 2, 7)  # s  -> v2, cap: 7g.add_edge(1, 3, 3)  # v1 -> v3, cap: 3g.add_edge(1, 4, 4)  # v1 -> v4, cap: 4g.add_edge(2, 1, 5)  # v2 -> v1, cap: 5g.add_edge(2, 4, 3)  # v2 -> v4, cap: 3g.add_edge(3, 4, 3)  # v3 -> v4, cap: 3g.add_edge(3, 5, 2)  # v3 -> t,  cap: 2g.add_edge(4, 5, 6)  # v4 -> t,  cap: 6source = 0; sink = 5print("The maximum possible flow is %d " % g.edmonds_karp(source, sink))

Time Complexity for The Edmonds-Karp Algorithm

The difference between Edmonds-Karp and Ford-Fulkerson is that Edmonds-Karp uses Breadth-First Search (BFS) to find augmented paths, while Ford-Fulkerson uses Depth-First Search (DFS).

This means that the time it takes to run Edmonds-Karp is easier to predict than Ford-Fulkerson, because Edmonds-Karp is not affected by the maximum flow value.

With the number of vertices \(V\), the number of edges \(E\), the time complexity for the Edmonds-Karp algorithm is

\[ O(V \cdot E^2) \]

This means Edmonds-Karp does not depend on the maximum flow, like Ford-Fulkerson does, but on how many vertices and edges we have.

The reason we get this time complexity for Edmonds-Karp is that it runs BFS which has time complexity \(O(E+V)\).

But if we assume a bad case scenario for Edmonds-Karp, with a dense graph, where the number of edges \(E\) is much greater than the number of vertices \(V\), time complexity for BFS becomes \(O(E)\).

BFS must run one time for every augmented path, and there can actually be found close to \(V \cdot E \) augmented paths during running of the Edmonds-Karp algorithm.

So, BFS with time complexity \(O(E)\) can run close to \(V \cdot E \) times in the worst case, which means we get a total time complexity for Edmonds-Karp: \( O(V \cdot E \cdot E) = O(V \cdot E^2) \).