Find minimum s-t cut in a flow network in C++
In this article, we will discuss how to find minimum s-t cut in a flow network in C++ with several examples.
Introduction:
In a flow network, a minimum s-t cut is a partition of the network into two sets of nodes, one containing the source node 's' and the other containing the sink node 't', such that the sum of capacities of edges crossing from the source side to the sink side is minimized. This concept is crucial in network flow algorithms, such as the Ford-Fulkerson algorithm and the Max-Flow Min-Cut theorem.
If we want to find the minimum s-t cut in a flow network in C++, we can use the Ford-Fulkerson algorithm with the Edmonds-Karp method, which is an efficient implementation using Breadth-First Search (BFS).
Algorithm:
1. Initialization:
- Begin with a flow network consisting of vertices, edges, and their capacities.
- Initially, set the flow on each edge to 0.
- Define the source node (s) and the sink node (t).
2. Find Augmenting Paths:
- Use a search algorithm, often Breadth-First Search (BFS), to find augmenting paths from the source (s) to the sink (t) in the residual graph.
- The residual graph represents the remaining capacity on each edge after considering the current flow. Edges may have forward and backward directions.
3. Augment Flow:
- Once an augmenting path is found, determine the minimum capacity among the edges on the path. This value is called the "path flow".
- Increment the flow on each edge of the path by the path flow in the forward direction and decrement it in the backward direction.
- This step effectively routes flow along the path, increasing the total flow in the network.
4. Repeat:
- Continue steps 2 and 3 until there are no more augmenting paths from the source to the sink in the residual graph. It indicates that no further flow can be added without violating edge capacities.
5. Calculate Minimum S-T Cut:
- Once the algorithm terminates, the maximum flow from the source to the sink is equal to the minimum cut capacity.
- The minimum cut represents the maximum amount of flow that can be sent from the source to the sink without exceeding the network's capacity.
6. Termination:
- The algorithm terminates when there are no more augmenting paths from the source to the sink in the residual graph. It implies that we've reached the maximum flow possible in the network, and the flow is at its capacity.
Program:
Let's take an example to demonstrate how to find minimum s-t cut in a flow network in C++:
#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; // Define the maximum number of vertices in the flow network const int MAX_V = 100; // Structure to represent an edge in the flow network struct Edge { int to, capacity, flow; Edge(int t, int c) : to(t), capacity(c), flow(0) {} }; // Graph class representing the flow network class FlowNetwork { public: int V; // Number of vertices vector<Edge> adj[MAX_V]; FlowNetwork(int vertices) { V = vertices; } // Add an edge to the flow network void addEdge(int from, int to, int capacity) { Edge forward(to, capacity); Edge backward(from, 0); adj[from].push_back(forward); adj[to].push_back(backward); } // Perform a BFS to find an augmenting path in the residual graph bool findAugmentingPath(int parent[], int s, int t) { vector<bool> visited(V, false); queue<int> q; q.push(s); visited[s] = true; parent[s] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (const Edge& e : adj[u]) { int v = e.to; int residualCapacity = e.capacity - e.flow; if (!visited[v] && residualCapacity > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } return visited[t]; } // Ford-Fulkerson algorithm with Edmonds-Karp method int findMinCut(int s, int t) { int parent[MAX_V]; int maxFlow = 0; while (findAugmentingPath(parent, s, t)) { int pathFlow = INT_MAX; for (int v = t; v != s; v = parent[v]) { int u = parent[v]; for (const Edge& e : adj[u]) { if (e.to == v) { pathFlow = min(pathFlow, e.capacity - e.flow); break; } } } for (int v = t; v != s; v = parent[v]) { int u = parent[v]; for (Edge& e : adj[u]) { if (e.to == v) { e.flow += pathFlow; break; } } for (Edge& e : adj[v]) { if (e.to == u) { e.flow -= pathFlow; break; } } } maxFlow += pathFlow; } return maxFlow; } }; int main() { int V, E; // Number of vertices and edges cin >> V >> E; FlowNetwork flowNetwork(V); // Input the edges and their capacities for (int i = 0; i < E; i++) { int u, v, capacity; cin >> u >> v >> capacity; flowNetwork.addEdge(u, v, capacity); } int source, sink; // Source and sink nodes cin >> source >> sink; int minCut = flowNetwork.findMinCut(source, sink); cout << "Minimum S-T Cut Capacity: " << minCut << endl; return 0; }
Input:
6 9 // Number of vertices (V) and edges (E) 0 1 10 0 2 10 1 2 2 1 3 4 2 4 9 3 5 10 4 3 8 4 5 10 5 0 5 0 3 // Source and sink nodes (s and t)
Output:
Minimum S-T Cut Capacity: 12
Complexity analysis:
Time Complexity:
- In this example, the Ford-Fulkerson algorithm with the Edmonds-Karp method has a time complexity of O(VE^2), where V is the number of vertices, and E is the number of edges in the flow network.
- In the worst case, the algorithm might require O(VE) iterations to find the maximum flow, and each iteration involves a Breadth-First Search (BFS), which takes O(E) time.
- The O(E^2) term arises from the fact that BFS might traverse all E edges in the worst-case augmenting path.
Space Complexity:
The space complexity of the algorithm depends on the data structures used and the representation of the graph.
- It's typically O(V + E), where V is the number of vertices and E is the number of edges in the flow network.
- The space is primarily used to store the graph, the residual graph (which is similar in size to the original graph), and data structures for bookkeeping, such as arrays for parent pointers and flags to track visited nodes. These require additional space on the order of O(V).
- The space complexity grows linearly with the number of vertices and edges in the flow network.
Program:
Let's take another example to demonstrate how to find minimum s-t cut in a flow network in C++:
#include <iostream> #include <vector> #include <climits> using namespace std; const int MAX_V = 100; // Define a structure to represent an edge in the flow network struct Edge { int to, capacity, flow, revIndex; Edge(int t, int c, int r) : to(t), capacity(c), flow(0), revIndex(r) {} }; // Define, a class to represent the flow network class FlowNetwork { public: int V; vector<Edge> adj[MAX_V]; vector<int> height; vector<int> excess; vector<int> count; // Constructor to initialize the flow network FlowNetwork(int vertices) { V = vertices; height.resize(V, 0); excess.resize(V, 0); count.resize(2 * V, 0); } // Function to add an edge to the flow network void addEdge(int from, int to, int capacity) { Edge forward(to, capacity, adj[to].size()); Edge backward(from, 0, adj[from].size()); adj[from].push_back(forward); adj[to].push_back(backward); } //Function to push flow from node u to node v void push(int u, int v) { int remainingCapacity = adj[u][count[u]].capacity - adj[u][count[u]].flow; int delta = min(remainingCapacity, excess[u]); adj[u][count[u]].flow += delta; adj[v][adj[u][count[u]].revIndex].flow -= delta; excess[u] -= delta; excess[v] += delta; } // Function to relabel node u void relabel(int u) { int minHeight = INT_MAX; for (int i = 0; i < adj[u].size(); i++) { if (adj[u][i].capacity - adj[u][i].flow > 0) { minHeight = min(minHeight, height[adj[u][i].to]); } } height[u] = minHeight + 1; } //Function to discharge excess flow from node u void discharge(int u) { while (excess[u] > 0) { if (count[u] < adj[u].size()) { int v = adj[u][count[u]].to; if (adj[u][count[u]].capacity - adj[u][count[u]].flow > 0 && height[u] == height[v] + 1) { push(u, v); } else { count[u]++; } } else { relabel(u); count[u] = 0; } } } //Function to find the minimum s-t cut int findMinCut(int s, int t) { height[s] = V; // Set height of the source to maximum excess[s] = INT_MAX; // Set excess of the source to maximum for (int i = 0; i < adj[s].size(); i++) { push(s, adj[s][i].to); } int current = 0; while (current < V - 1) { for (int u = 0; u < V; u++) { if (u != s && u != t) { discharge(u); if (excess[u] > 0) { current = 0; } } } current++; } return excess[t]; } }; int main() { int V, E; cin >> V >> E; FlowNetwork flowNetwork(V); for (int i = 0; i < E; i++) { int u, v, capacity; cin >> u >> v >> capacity; flowNetwork.addEdge(u, v, capacity); } int source, sink; cin >> source >> sink; int minCut = flowNetwork.findMinCut(source, sink); cout << "Minimum S-T Cut Capacity: " << minCut << endl; return 0; }
Input:
6 9 0 1 10 0 2 10 1 2 2 1 3 4 2 4 9 3 5 10 4 3 8 4 5 10 5 0 5 0 3
Output:
Minimum S-T Cut Capacity: 6
Explanation:
- The code defines a FlowNetwork class to represent the flow network. This class includes data members to store edges, heights, excess, and counts for nodes.
- The addEdge function adds edges to the flow network, creating forward and backward edges to represent the flow in both directions.
- The push function transfers flow from node u to node v while respecting the capacity constraints.
- The relabel function updates the height of a node u based on its neighbors and their flow.
- The discharge Function pushes excess flow out of a node u by repeatedly calling the push function or relabeling the node.
- The findMinCut Function initializes the source node's height and excess, pushes flow out of the source node, and then repeatedly discharges nodes until no more excess flow can be pushed. The result is the minimum s-t cut capacity.
- In the main function, the code reads the input for the flow network's structure, including vertices, edges, capacities, source, and sink. After that, it calculates and prints the minimum s-t cut capacity.
Complexity analysis:
Time Complexity:
- The time complexity of the Push-Relabel algorithm is typically O(V^3), where V is the number of vertices in the flow network.
- The main loop of the algorithm runs for a maximum of V iterations, and in each iteration, we perform operations that take O(V^2) time. These operations include discharging excess flow, pushing flow, and relabeling nodes.
- In practice, the algorithm often converges much faster so that it can be significantly faster than O(V^3) for many real-world cases.
Space Complexity:
The space complexity of the code is determined by the data structures used to represent the flow network and the working variables of the algorithm.
The key space-consuming components are:
- Storage for the flow network itself: O(V + E), where V is the number of vertices and E is the number of edges.
- Data structures for bookkeeping, such as height, excess, and count arrays: O(V).
- The overall space complexity of the code is O(V + E), which is linear in terms of the number of vertices and edges in the flow network.