Capacity Scaling Algorithm

Algorithm Description

The Capacity Scaling algorithm is used to find the maximum flow in a flow network. It operates by repeatedly augmenting flow along paths with capacities greater than a scaling parameter, adjusting this parameter until all edges can no longer accommodate flow, ensuring an efficient O(E * (V^2 log(U))) time complexity in typical cases.

C++ Code

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define V 6

struct Edge {
    int to, capacity, flow, rev;
};

class CapacityScaling {
    int n;
    vector<vector<Edge>> adj;
    vector<int> dist, start;

    bool bfs(int source, int sink, int scalingFactor) {
        dist.assign(n, -1);
        queue<int> q;
        q.push(source);
        dist[source] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (auto &e : adj[u]) {
                if (dist[e.to] == -1 && e.capacity - e.flow >= scalingFactor) {
                    q.push(e.to);
                    dist[e.to] = dist[u] + 1;
                }
            }
        }
        return dist[sink] != -1;
    }

    int dfs(int u, int sink, int flow, int scalingFactor) {
        if (u == sink)
            return flow;

        for (int &i = start[u]; i < adj[u].size(); i++) {
            Edge &e = adj[u][i];
            if (dist[e.to] == dist[u] + 1 && e.capacity - e.flow >= scalingFactor) {
                int current_flow = min(flow, e.capacity - e.flow);
                int pushed_flow = dfs(e.to, sink, current_flow, scalingFactor);

                if (pushed_flow > 0) {
                    e.flow += pushed_flow;
                    adj[e.to][e.rev].flow -= pushed_flow;
                    return pushed_flow;
                }
            }
        }
        return 0;
    }

public:
    CapacityScaling(int n) : n(n), adj(n), dist(n), start(n) {}

    void addEdge(int from, int to, int capacity) {
        adj[from].push_back({to, capacity, 0, (int)adj[to].size()});
        adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1});
    }

    int maxFlow(int source, int sink) {
        int max_flow = 0;
        for (int scalingFactor = 1 << 30; scalingFactor > 0; scalingFactor >>= 1) {
            while (bfs(source, sink, scalingFactor)) {
                start.assign(n, 0);
                while (int flow = dfs(source, sink, INT_MAX, scalingFactor))
                    max_flow += flow;
            }
        }
        return max_flow;
    }
};

int main() {
    CapacityScaling cs(V);

    cs.addEdge(0, 1, 16);
    cs.addEdge(0, 2, 13);
    cs.addEdge(1, 2, 10);
    cs.addEdge(1, 3, 12);
    cs.addEdge(2, 1, 4);
    cs.addEdge(2, 4, 14);
    cs.addEdge(3, 2, 9);
    cs.addEdge(3, 5, 20);
    cs.addEdge(4, 3, 7);
    cs.addEdge(4, 5, 4);

    int source = 0;
    int sink = 5;
    cout << "The maximum possible flow is " << cs.maxFlow(source, sink);

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Initialization	O(V + E)	O(V + E)
Capacity Scaling	O(E * (V^2 log(U)))	O(V^2)

Where:

• V: Number of vertices in the graph.
• E: Number of edges in the graph.
• U: Maximum capacity of any edge in the graph.

← Back to Homepage