Edmonds Karp Algorithm In C++

The Edmonds-Karp algorithm stands out as a robust and effective technique for determining the highest flow in a flow network, characterized by a directed graph with each edge having a capacity denoting the maximum flow it can accommodate. This algorithm enhances the Ford-Fulkerson approach by enhancing its worst-case time complexity.

At the heart of the Edmonds-Karp algorithm lies the employment of Breadth-First Search (BFS) to identify augmenting paths within the residual graph. This altered graph is derived from the initial graph, illustrating the capacity left on each edge post transmission of the current flow. Through the iterative discovery of augmenting paths and subsequent flow adjustments along these paths, the algorithm progresses towards achieving the maximum flow.

Key Insights:

The main concept behind the Edmonds-Karp algorithm is that employing the Breadth-First Search (BFS) technique to discover augmenting paths guarantees that the shortest paths, in relation to the number of edges, are prioritized initially. This results in a worst-case time complexity of O(VE^2), with V representing the vertices and E representing the edges in the graph. By utilizing BFS, each augmenting path is limited to a maximum length of O(VE), effectively avoiding potential infinite loop scenarios that could occur when arbitrary augmenting paths are chosen in the original Ford-Fulkerson algorithm.

The process begins with an initial flow value of zero and incrementally increases the flow until all possible augmenting paths have been exhausted. In each step, a Breadth-First Search (BFS) algorithm is employed to identify a path that can accommodate additional flow. The capacity of the bottleneck in this path is identified, and the flow within the path is adjusted accordingly. This sequence persists until there are no more augmenting paths available, resulting in the attainment of the maximum flow.

Edmonds-Karp has gained significant popularity because of its straightforwardness, accuracy, and assurance of polynomial-time complexity. Even though there are more sophisticated algorithms available for calculating maximum flow, Edmonds-Karp is still a great option for educational use and real-world situations where the graph sizes are moderate. Its utilization of BFS specifically suits dense graphs or graphs with lower edge capacities.

History:

The Edmonds-Karp algorithm represents a notable advancement in the realm of computer science and graph theory, with a specific focus on addressing the maximum flow problem within network flow analysis. This algorithm bears the names of its creators, Jack Edmonds and Richard Karp, and made its debut in the year 1972.

The evolution of the algorithm is intricately linked to the wider landscape of network flow challenges, which became more prominent during the middle of the 20th century. During the late 1940s and 1950s, scholars such as George Dantzig and T.C. Koopmans delved into issues concerning transportation and flow within networks. The notion of maximum flow, which revolves around identifying the highest quantity of material that can move through a network, emerged as a key area of study.

In the 1970s, Jack Edmonds and Richard Karp separately focused on solving the maximum flow problem. Edmonds had previously made substantial advancements in matroid theory and optimization, whereas Karp was well-known for his research in complexity theory and algorithms. Their partnership led to the development of the Edmonds-Karp algorithm, an enhancement of the Ford-Fulkerson algorithm that was initially introduced by L.R. Ford Jr. and D.R. Fulkerson back in 1956.

The Edmonds-Karp algorithm utilizes the concept of augmenting paths, which involves boosting the residual capacity within the network along a path from the source to the sink. The key feature that sets Edmonds-Karp apart is its employment of breadth-first search (BFS) for efficiently identifying the augmenting path. This approach guarantees a polynomial worst-case time complexity of O(VE^2), enhancing the algorithm's predictability and reliability compared to the Ford-Fulkerson algorithm.

The inception of the algorithm signified a significant advancement in algorithmic development and graph theory, offering a more resilient resolution to the maximum flow dilemma. Through time, it has been implemented across diverse sectors such as transportation, communication networks, and operational analysis. Its historical importance is not solely attributed to its effectiveness but also to its impact on future studies in network flow algorithms and associated optimization challenges.

Example:

Here is a C++ implementation of the Edmonds-Karp algorithm:

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = INT_MAX;
const int MAX_V = 100; // Adjust this according to your maximum number of vertices
int capacity[MAX_V][MAX_V];
int parent[MAX_V];
int bfs(int source, int sink, vector<vector<int>> &graph) {
 fill(parent, parent + MAX_V, -1);
 parent[source] = source;
 queue<pair<int, int>> q;
 q.push({source, INF});
 while (!q.empty()) {
 int current = q.front().first;
 int flow = q.front().second;
 q.pop();
 for (int next : graph[current]) {
 if (parent[next] == -1 && capacity[current][next] > 0) {
 parent[next] = current;
 int new_flow = min(flow, capacity[current][next]);
 if (next == sink)
 return new_flow;
 q.push({next, new_flow});
 }
 }
 }
 return 0;
}
int edmondsKarp(int source, int sink, vector<vector<int>> &graph) {
 int max_flow = 0;
 int new_flow;
 while ((new_flow = bfs(source, sink, graph)) > 0) {
 max_flow += new_flow;
 int current = sink;
 while (current != source) {
 int prev = parent[current];
 capacity[prev][current] -= new_flow;
 capacity[current][prev] += new_flow;
 current = prev;
 }
 }
 return max_flow;
}
int main() {
 // Example usage:
 int source = 0;
 int sink = 5;
 vector<vector<int>> graph(MAX_V);
 // Add directed edges with capacities
 capacity[0][1] = 10;
 capacity[0][2] = 5;
 capacity[1][2] = 15;
 capacity[1][3] = 5;
 capacity[2][3] = 10;
 capacity[2][4] = 10;
 capacity[3][4] = 5;
 capacity[3][5] = 10;
 capacity[4][5] = 10;
 // Create adjacency list representation
 for (int i = 0; i < MAX_V; ++i) {
 for (int j = 0; j < MAX_V; ++j) {
 if (capacity[i][j] > 0) {
 graph[i].push_back(j);
 }
 }
 }
 int max_flow = edmondsKarp(source, sink, graph);
 cout << "Maximum Flow: " << max_flow << endl;
 return 0;
}

Output:

Maximum Flow: 20
.................................
Process executed in 1.11 seconds
Press any key to continue

Explanation:

• ✅ Include Statements: #include <iostream>: Includes the Input/Output Stream Library for input and output operations. #include <climits>: Includes the Limits Library for using the INT_MAX #include <cstring>: Includes the C String Library for string-related functions. #include <queue>: Includes the Queue Library for using queues. #include <vector>: Includes the Vector Library for dynamic array implementation.
• ✅ Namespace Declaration: using namespace std;: Indicates the usage of the std (standard) namespace to simplify code referencing.
• ✅ Constants Declaration: const int INF = INTMAX;: Defines a constant INF with the maximum possible integer value. const int MAXV = 100;: Defines a constant MAX_V as the maximum number of vertices (adjust according to your needs).
• ✅ Global Variables: int capacityMAXV;: Defines a 2D array to store the capacity of edges in the graph. int parent[MAXV];: Defines an array to store the parent of each vertex during the BFS traversal.
• ✅ BFS Function: int bfs(int source, int sink, vector<vector<int>> &graph) { ... }: Implements Breadth-First Search to find augmenting paths in the graph. Fills the parent array with -1 to indicate no parent initially. Uses a queue to traverse the graph and find augmenting paths.
• ✅ Edmonds-Karp Function: int edmondsKarp(int source, int sink, vector<vector<int>> &graph) { ... }: Implements the Edmonds-Karp algorithm for finding the maximum flow. Calls the bfs function in a loop until no more augmenting paths can be found. Updates the capacities and returns the maximum flow.
• ✅ Main Function: int main { ... }: Entry point of the program. Example usage of the Edmonds-Karp algorithm. Initializes source and sink vertices. Creates an adjacency list representation (graph) based on the capacities defined in the capacity matrix. Calls the edmondsKarp function to find the maximum flow. Prints the result.
• ✅ Example Usage: int source = 0;: Sets the source vertex for the flow network. int sink = 5;: Sets the sink vertex for the flow network. Creates an adjacency list representation (graph) based on the capacities defined in the capacity matrix. Adds directed edges with capacities. Calls the edmondsKarp function to find and print the maximum flow.
• ✅ Graph Initialization: Loops through the capacity matrix to populate the adjacency list representation (graph). If the capacity between vertices is greater than 0, adds the edge to the adjacency list.
• ✅ Output: cout << "Maximum Flow: " << max_flow << endl;: Prints the maximum flow computed by the Edmonds-Karp algorithm.
• ✅ #include <iostream>: Includes the Input/Output Stream Library for input and output operations.
• ✅ #include <climits>: Includes the Limits Library for using the INT_MAX
• ✅ #include <cstring>: Includes the C String Library for string-related functions.
• ✅ #include <queue>: Includes the Queue Library for using queues.
• ✅ #include <vector>: Includes the Vector Library for dynamic array implementation.
• ✅ using namespace std;: Indicates the usage of the std (standard) namespace to simplify code referencing.
• ✅ const int INF = INT_MAX;: Defines a constant INF with the maximum possible integer value.
• ✅ const int MAXV = 100;: Defines a constant MAXV as the maximum number of vertices (adjust according to your needs).
• ✅ int capacityMAX_V;: Defines a 2D array to store the capacity of edges in the graph.
• ✅ int parent[MAX_V];: Defines an array to store the parent of each vertex during the BFS traversal.
• ✅ int bfs(int source, int sink, vector<vector<int>> &graph) { ... }: Implements Breadth-First Search to find augmenting paths in the graph.
• ✅ Fills the parent array with -1 to indicate no parent initially.
• ✅ Uses a queue to traverse the graph and find augmenting paths.
• ✅ int edmondsKarp(int source, int sink, vector<vector<int>> &graph) { ... }: Implements the Edmonds-Karp algorithm for finding the maximum flow.
• ✅ Calls the bfs function in a loop until no more augmenting paths can be found.
• ✅ Updates the capacities and returns the maximum flow.
• ✅ int main { ... }: Entry point of the program.
• ✅ Example usage of the Edmonds-Karp algorithm.
• ✅ Initializes source and sink vertices.
• ✅ Creates an adjacency list representation (graph) based on the capacities defined in the capacity matrix.
• ✅ Calls the edmondsKarp function to find the maximum flow.
• ✅ Prints the result.
• ✅ int source = 0;: Sets the source vertex for the flow network.
• ✅ int sink = 5;: Sets the sink vertex for the flow network.
• ✅ Creates an adjacency list representation (graph) based on the capacities defined in the capacity matrix.
• ✅ Adds directed edges with capacities.
• ✅ Calls the edmondsKarp function to find and print the maximum flow.
• ✅ Loops through the capacity matrix to populate the adjacency list representation (graph).
• ✅ If the capacity between vertices is greater than 0, adds the edge to the adjacency list.
• ✅ cout << "Maximum Flow: " << max_flow << endl;: Prints the maximum flow computed by the Edmonds-Karp algorithm.

Time and Space Complexity Analysis

The Edmonds-Karp algorithm presents a variation of the Ford-Fulkerson technique for determining the maximum flow within a network. Below is an evaluation of the time and space complexities associated with the given C++ implementation.

Time Complexity:

• ✅ Breadth-First Search (BFS): The main loop of the algorithm consists of a series of BFS operations, where each BFS operation traverses the graph in a layer-wise manner. The worst-case time complexity of BFS on an adjacency list representation of the graph is O(V + E), where V is the number of vertices and E is the number of edges. In each iteration, BFS is used to find an augmenting path from the source to the sink.
• ✅ Iterations: In the worst case, the Edmonds-Karp algorithm may need to iterate through all edges in the residual graph until no augmenting paths are found. In each iteration, BFS is applied, and since BFS takes O(V + E) time, the worst-case time complexity of the algorithm is O(VE^2) , where V is the number of vertices and E is the number of edges.
• ✅ Capacity Updates: In each iteration, the algorithm updates the capacities of the residual graph along the augmenting path. Updating the capacities takes constant time per edge.

In general, the time complexity of the Edmonds-Karp algorithm is primarily influenced by the Breadth-First Search (BFS) procedures, leading to a worst-case scenario of O(VE^2).

Space Complexity:

• ✅ Graph Representation: The space complexity is primarily determined by the graph representation. In this implementation, an adjacency list is used to represent the graph. The adjacency list is stored in the graph vector, which has a size of O(V + E), where V is the number of vertices and E is the number of edges.
• ✅ Parent Array: The parent array is used to trace the augmenting path found by BFS. The size of the parent array is O(V), where V is the number of vertices.
• ✅ Capacity Matrix: The capacity matrix represents the capacities of edges in the graph. Its size is O(V^2), where V is the number of vertices.
• ✅ Queue: The BFS algorithm uses a queue to keep track of vertices to be visited. In the worst case, all vertices may be enqueued, leading to a space complexity of O(V).
• ✅ Considering all these components, the overall space complexity of the Edmonds-Karp algorithm is O(V + E).

In essence, the Edmonds-Karp algorithm offers an efficient solution in polynomial time to determine the maximum flow within a network. It proves to be practical for graphs of modest sizes, with both time and space complexities being manageable. Nonetheless, when dealing with larger graphs, alternative algorithms such as the Push-Relabel algorithm could be more appropriate.

Applications of Edmonds Karp Algorithm

The Edmonds-Karp algorithm, which is a modified version of the Ford-Fulkerson algorithm, has been widely utilized in a range of industries for its effectiveness in resolving the maximum flow problem. Below are some noteworthy implementations:

Network Flow Optimization:

The main use of the Edmonds-Karp algorithm lies in optimizing network flow. It finds extensive application in transportation and logistics sectors for simulating and enhancing the movement of products, aiming at resource efficiency and cost reduction in transportation operations.

Communication Networks:

In the development and administration of communication networks, like the internet, the Edmonds-Karp algorithm is utilized to enhance data transmission. It assists in calculating the highest volume of data that can move through various paths, thereby enhancing network effectiveness.

Resource Allocation in Computing Systems:

Algorithms are utilized in computer systems to enhance resource distribution. When there are competing processes or applications vying for resources, the Edmonds-Karp algorithm assists in allocating resources effectively to maximize the performance of the entire system.

Water and Energy Distribution:

In water distribution and energy supply systems, the algorithm plays a key role in enhancing the allocation of resources, guaranteeing the efficient delivery of water and energy to their respective endpoints. This optimization is essential for effective urban development and the sustainable management of limited resources.

Supply Chain Management:

Edmonds-Karp algorithm is commonly used in supply chain management to enhance the movement of products within distribution networks. This method aids in identifying the optimal pathways for delivering goods from producers to end-users, reducing expenses and increasing capacity.

Image Segmentation:

In the field of computer vision, the algorithm has been modified to cater to image segmentation. By considering pixels as nodes and employing the algorithm to determine paths with the highest flow, it aids in recognizing and segregating individual objects within an image.

Biological and Medical Applications:

Algorithms are utilized in biological studies to simulate phenomena such as blood flow in the human body. Within medical imaging, they assist in the assessment and enhancement of the movement of contrast agents or various substances within biological structures.

Game Theory:

Edmonds-Karp algorithm has been utilized in representing and resolving specific challenges in game theory, especially in situations related to strategic engagements and distribution of resources among participants.

In essence, the broad applicability of the Edmonds-Karp algorithm has resulted in its integration across a diverse array of use cases, enhancing effectiveness and streamlining solutions in multiple fields. Its efficient management of network flow challenges has established it as a crucial asset in both academic exploration and real-world deployments.

Advantages and Disadvantages

The Edmonds-Karp algorithm, an enhancement of the Ford-Fulkerson algorithm, is a commonly employed technique for determining the maximum flow within a flow network. Flow networks play a crucial role in a multitude of scenarios including transportation systems, communication networks, and resource distribution. Similar to all algorithms, the Edmonds-Karp algorithm has its own array of benefits and drawbacks, which we will delve into extensively.

Advantages:

1. Guaranteed Convergence:

One of the main benefits of the Edmonds-Karp algorithm is its assurance of reaching the maximum flow in a definite number of iterations. This is achieved by employing augmenting paths with the shortest length possible, guaranteeing a swift termination of the algorithm.

1. Efficiency in Polynomial Time Complexity:

Efficiency in Implementation: The Edmonds-Karp algorithm's time complexity is O(VE^2), where V represents the vertices and E represents the edges. This computational efficiency surpasses that of certain alternative algorithms when it comes to determining maximum flow, particularly in graphs with fewer connections.

1. Ease of Implementation:

The process is quite simple to execute, which makes it user-friendly for programmers and researchers. Its ease of use adds to its widespread use in academic and real-world scenarios.

1. Utilizing the Breadth-First Search (BFS) Method:

Edmonds-Karp utilizes a Breadth-First Search (BFS) approach to discover augmenting routes. This guarantees that the shortest augmenting paths are prioritized initially, resulting in faster convergence in real-world scenarios.

1. Suitability for Bipartite Matching:

The algorithm can be customized to efficiently solve the maximum bipartite matching issue, showcasing its adaptability. This is particularly valuable as bipartite matching finds utility in various domains such as task distribution, resource allotment, and network flow management.

1. Integral Capacity Network Flows:

Edmonds-Karp algorithm excels in situations where all capacities are whole numbers. This aspect is crucial in contexts where fractional capacities are impractical, like determining the number of vehicles on a roadway or the bandwidth of a communication channel.

Disadvantages:

1. Space Complexity:

The algorithm necessitates storing residual capacities for every edge. In graphs that are dense or networks with substantial capacities, the issue of space complexity may arise. This is especially crucial when working with networks that have a significant amount of vertices and edges.

1. Relying on Integer Capacities:

When dealing with capacities that are real numbers or involve floating-point arithmetic, Edmonds-Karp's efficiency may be compromised. This is due to the susceptibility to rounding errors that can impact result precision.

1. Challenges with High Capacities:

The time complexity of the algorithm may become problematic when working with networks that have substantial capacities. The quadratic component in the time complexity (O(VE^2)) can result in extended computation durations, particularly when the value of E is significant.

1. Not Ideal for Networks with Limited Flows:

In cases where the maximum flow is considerably lower than the overall flow capacity of the network, the algorithm may be excessive. There exist more tailored algorithms that could deliver superior performance in such situations.

1. Reliance on BFS for Path Selection:

While BFS guarantees convergence, it might not always prioritize the most efficient augmenting routes. Occasionally, this approach can lead to suboptimal flow outcomes, particularly when there are alternative paths with greater capacities available.

1. Vulnerability to Input Sequence:

The sequence in which the edges are handled can impact the efficiency of the algorithm. Various input sequences might result in varied execution durations, impacting the consistency of outcomes.

Conclusion:

In summary, the Edmonds-Karp algorithm offers various benefits such as assured termination, practical efficiency with sparse graphs, optimality, flexibility, and a clear representation of residual graphs. Nonetheless, it is important to take into account its performance with dense graphs, space usage, sensitivity to initial flow, and constraints related to non-integer capacities and negative edge weights when selecting an algorithm for a particular use case. Evaluating these aspects against the needs and attributes of the specific flow network under examination is crucial for deciding whether the Edmonds-Karp algorithm is the right choice or if alternative methods should be considered.