Unit 7: Network Flows

Learning Objectives

• Understand flow networks and maximum flow problems
• Master the Ford-Fulkerson algorithm and its variants
• Learn about augmenting paths and residual graphs
• Apply max-flow min-cut theorem
• Solve real-world problems using network flows

1. Flow Networks

A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The maximum flow problem seeks to find the maximum possible flow from a source to a sink.

2. Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm finds the maximum flow by repeatedly finding augmenting paths from source to sink and pushing flow along these paths.

Ford-Fulkerson Implementation

#include 
#include 
#include 
#include 
#include 

class FordFulkerson {
private:
    int vertices;
    std::vector> capacity;
    std::vector> flow;
    
public:
    FordFulkerson(int v) : vertices(v) {
        capacity.assign(v, std::vector(v, 0));
        flow.assign(v, std::vector(v, 0));
    }
    
    void addEdge(int from, int to, int cap) {
        capacity[from][to] = cap;
    }
    
    int maxFlow(int source, int sink) {
        int totalFlow = 0;
        std::vector parent(vertices);
        
        // While augmenting path exists
        while (bfs(source, sink, parent)) {
            // Find bottleneck capacity
            int pathFlow = INT_MAX;
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                pathFlow = std::min(pathFlow, capacity[u][v] - flow[u][v]);
            }
            
            // Update flows along the path
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                flow[u][v] += pathFlow;
                flow[v][u] -= pathFlow; // Reverse edge
            }
            
            totalFlow += pathFlow;
        }
        
        return totalFlow;
    }
    
private:
    bool bfs(int source, int sink, std::vector& parent) {
        std::vector visited(vertices, false);
        std::queue q;
        
        q.push(source);
        visited[source] = true;
        parent[source] = -1;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v = 0; v < vertices; v++) {
                if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {
                    q.push(v);
                    parent[v] = u;
                    visited[v] = true;
                    
                    if (v == sink) return true;
                }
            }
        }
        
        return false;
    }
    
public:
    // Get current flow on edge
    int getFlow(int from, int to) {
        return flow[from][to];
    }
    
    // Get residual capacity
    int getResidualCapacity(int from, int to) {
        return capacity[from][to] - flow[from][to];
    }
    
    // Find minimum cut
    std::pair, int> minCut(int source, int sink) {
        int maxFlowValue = maxFlow(source, sink);
        
        // Find reachable vertices from source in residual graph
        std::vector visited(vertices, false);
        std::queue q;
        q.push(source);
        visited[source] = true;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v = 0; v < vertices; v++) {
                if (!visited[v] && getResidualCapacity(u, v) > 0) {
                    q.push(v);
                    visited[v] = true;
                }
            }
        }
        
        // Collect cut edges
        std::vector cutEdges;
        int cutCapacity = 0;
        
        for (int u = 0; u < vertices; u++) {
            for (int v = 0; v < vertices; v++) {
                if (visited[u] && !visited[v] && capacity[u][v] > 0) {
                    cutEdges.push_back(u * vertices + v); // Encode edge
                    cutCapacity += capacity[u][v];
                }
            }
        }
        
        return {cutEdges, cutCapacity};
    }
    
    void displayFlow() {
        std::cout << "Current flow:" << std::endl;
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                if (capacity[i][j] > 0) {
                    std::cout << "Edge (" << i << ", " << j << "): "
                             << flow[i][j] << "/" << capacity[i][j] << std::endl;
                }
            }
        }
    }
};

3. Edmonds-Karp Algorithm

Edmonds-Karp is a specific implementation of Ford-Fulkerson that uses BFS to find the shortest augmenting path, guaranteeing O(VE²) time complexity.

Edmonds-Karp Implementation

#include 
#include 
#include 
#include 

class EdmondsKarp {
private:
    struct Edge {
        int to, rev;
        int capacity;
        
        Edge(int to, int rev, int cap) : to(to), rev(rev), capacity(cap) {}
    };
    
    std::vector> graph;
    int vertices;
    
public:
    EdmondsKarp(int v) : vertices(v) {
        graph.resize(v);
    }
    
    void addEdge(int from, int to, int capacity) {
        graph[from].emplace_back(to, graph[to].size(), capacity);
        graph[to].emplace_back(from, graph[from].size() - 1, 0); // Reverse edge
    }
    
    int maxFlow(int source, int sink) {
        int totalFlow = 0;
        
        while (true) {
            std::vector parent(vertices, -1);
            std::vector parentEdge(vertices, -1);
            
            // BFS to find augmenting path
            std::queue q;
            q.push(source);
            parent[source] = source;
            
            while (!q.empty() && parent[sink] == -1) {
                int v = q.front();
                q.pop();
                
                for (int i = 0; i < graph[v].size(); i++) {
                    Edge& e = graph[v][i];
                    if (parent[e.to] == -1 && e.capacity > 0) {
                        parent[e.to] = v;
                        parentEdge[e.to] = i;
                        q.push(e.to);
                    }
                }
            }
            
            if (parent[sink] == -1) break; // No augmenting path
            
            // Find bottleneck
            int pathFlow = INT_MAX;
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                pathFlow = std::min(pathFlow, graph[u][parentEdge[v]].capacity);
            }
            
            // Update capacities
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                Edge& forward = graph[u][parentEdge[v]];
                Edge& backward = graph[v][forward.rev];
                
                forward.capacity -= pathFlow;
                backward.capacity += pathFlow;
            }
            
            totalFlow += pathFlow;
        }
        
        return totalFlow;
    }
    
    // Get original capacity and current flow
    std::pair getEdgeInfo(int from, int to) {
        for (const Edge& e : graph[from]) {
            if (e.to == to) {
                // Find reverse edge to get flow
                for (const Edge& rev : graph[to]) {
                    if (rev.to == from) {
                        return {e.capacity + rev.capacity, rev.capacity};
                    }
                }
            }
        }
        return {0, 0};
    }
};

4. Applications of Maximum Flow

Bipartite Matching using Max Flow

#include 
#include 

class BipartiteMatching {
private:
    FordFulkerson ff;
    int leftSize, rightSize;
    int source, sink;
    
public:
    BipartiteMatching(int left, int right) 
        : leftSize(left), rightSize(right), ff(left + right + 2) {
        source = left + right;
        sink = left + right + 1;
        
        // Connect source to left vertices
        for (int i = 0; i < left; i++) {
            ff.addEdge(source, i, 1);
        }
        
        // Connect right vertices to sink
        for (int i = 0; i < right; i++) {
            ff.addEdge(left + i, sink, 1);
        }
    }
    
    void addEdge(int leftVertex, int rightVertex) {
        if (leftVertex < leftSize && rightVertex < rightSize) {
            ff.addEdge(leftVertex, leftSize + rightVertex, 1);
        }
    }
    
    int maxMatching() {
        return ff.maxFlow(source, sink);
    }
    
    std::vector> getMatching() {
        ff.maxFlow(source, sink); // Ensure flow is computed
        
        std::vector> matching;
        
        for (int left = 0; left < leftSize; left++) {
            for (int right = 0; right < rightSize; right++) {
                if (ff.getFlow(left, leftSize + right) == 1) {
                    matching.emplace_back(left, right);
                }
            }
        }
        
        return matching;
    }
};

Multi-Source Multi-Sink Max Flow

#include 
#include 

class MultiSourceSinkFlow {
private:
    FordFulkerson ff;
    int originalVertices;
    int superSource, superSink;
    
public:
    MultiSourceSinkFlow(int vertices, const std::vector& sources, 
                       const std::vector& sinks) 
        : originalVertices(vertices), ff(vertices + 2) {
        
        superSource = vertices;
        superSink = vertices + 1;
        
        // Connect super source to all sources
        for (int source : sources) {
            ff.addEdge(superSource, source, INT_MAX);
        }
        
        // Connect all sinks to super sink
        for (int sink : sinks) {
            ff.addEdge(sink, superSink, INT_MAX);
        }
    }
    
    void addEdge(int from, int to, int capacity) {
        ff.addEdge(from, to, capacity);
    }
    
    int maxFlow() {
        return ff.maxFlow(superSource, superSink);
    }
};

5. Advanced Flow Algorithms

Dinic's Algorithm (O(V²E))

#include 
#include 
#include 
#include 

class Dinics {
private:
    struct Edge {
        int to, rev, cap;
        Edge(int to, int rev, int cap) : to(to), rev(rev), cap(cap) {}
    };
    
    std::vector> graph;
    std::vector level, iter;
    int vertices;
    
public:
    Dinics(int v) : vertices(v) {
        graph.resize(v);
        level.resize(v);
        iter.resize(v);
    }
    
    void addEdge(int from, int to, int cap) {
        graph[from].emplace_back(to, graph[to].size(), cap);
        graph[to].emplace_back(from, graph[from].size() - 1, 0);
    }
    
    int maxFlow(int source, int sink) {
        int totalFlow = 0;
        
        while (bfs(source, sink)) {
            std::fill(iter.begin(), iter.end(), 0);
            int flow;
            while ((flow = dfs(source, sink, INT_MAX)) > 0) {
                totalFlow += flow;
            }
        }
        
        return totalFlow;
    }
    
private:
    bool bfs(int source, int sink) {
        std::fill(level.begin(), level.end(), -1);
        std::queue q;
        
        level[source] = 0;
        q.push(source);
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            
            for (const Edge& e : graph[v]) {
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        
        return level[sink] >= 0;
    }
    
    int dfs(int v, int sink, int pushed) {
        if (v == sink || pushed == 0) {
            return pushed;
        }
        
        for (int& cid = iter[v]; cid < graph[v].size(); cid++) {
            Edge& e = graph[v][cid];
            
            if (level[v] + 1 != level[e.to] || e.cap <= 0) {
                continue;
            }
            
            int tr = dfs(e.to, sink, std::min(pushed, e.cap));
            if (tr > 0) {
                e.cap -= tr;
                graph[e.to][e.rev].cap += tr;
                return tr;
            }
        }
        
        return 0;
    }
};

6. Performance Comparison

7. Complete Example Program

#include 

int main() {
    std::cout << "=== Unit 7: Network Flows Demo ===" << std::endl;
    
    // Ford-Fulkerson Demo
    std::cout << "\n--- Ford-Fulkerson Max Flow ---" << std::endl;
    FordFulkerson ff(6);
    
    // Add edges (from, to, capacity)
    ff.addEdge(0, 1, 16);
    ff.addEdge(0, 2, 13);
    ff.addEdge(1, 2, 10);
    ff.addEdge(1, 3, 12);
    ff.addEdge(2, 1, 4);
    ff.addEdge(2, 4, 14);
    ff.addEdge(3, 2, 9);
    ff.addEdge(3, 5, 20);
    ff.addEdge(4, 3, 7);
    ff.addEdge(4, 5, 4);
    
    int maxFlowValue = ff.maxFlow(0, 5);
    std::cout << "Maximum flow from 0 to 5: " << maxFlowValue << std::endl;
    
    ff.displayFlow();
    
    // Min Cut Demo
    auto [cutEdges, cutCapacity] = ff.minCut(0, 5);
    std::cout << "\nMinimum cut capacity: " << cutCapacity << std::endl;
    
    // Bipartite Matching Demo
    std::cout << "\n--- Bipartite Matching ---" << std::endl;
    BipartiteMatching bm(4, 4);
    
    // Add edges between left and right vertices
    bm.addEdge(0, 0);
    bm.addEdge(0, 1);
    bm.addEdge(1, 1);
    bm.addEdge(1, 2);
    bm.addEdge(2, 2);
    bm.addEdge(2, 3);
    bm.addEdge(3, 3);
    
    int matching = bm.maxMatching();
    std::cout << "Maximum matching: " << matching << std::endl;
    
    auto matchingPairs = bm.getMatching();
    std::cout << "Matching pairs: ";
    for (auto [left, right] : matchingPairs) {
        std::cout << "(" << left << ", " << right << ") ";
    }
    std::cout << std::endl;
    
    // Edmonds-Karp Demo
    std::cout << "\n--- Edmonds-Karp Algorithm ---" << std::endl;
    EdmondsKarp ek(6);
    
    ek.addEdge(0, 1, 16);
    ek.addEdge(0, 2, 13);
    ek.addEdge(1, 2, 10);
    ek.addEdge(1, 3, 12);
    ek.addEdge(2, 1, 4);
    ek.addEdge(2, 4, 14);
    ek.addEdge(3, 2, 9);
    ek.addEdge(3, 5, 20);
    ek.addEdge(4, 3, 7);
    ek.addEdge(4, 5, 4);
    
    int ekMaxFlow = ek.maxFlow(0, 5);
    std::cout << "Edmonds-Karp max flow: " << ekMaxFlow << std::endl;
    
    return 0;
}