To do the first kind of problems Graph Matching. I went through William Fiset’s amazing YouTube playlist on Network Flow Since I learned it all from one source, I wanted to write this blog to share what I understood — and more importantly — to ask the community for new perspectives and interesting problems to explore using this algorithm.

Imagine you have a water system:

A big tank (source) that sends water to A fountain (sink) through Several pipes (edges) connected by junctions (nodes).

Each pipe has a limit — called capacity — which represents how much water it can carry.


Our goal? ➡️ Find the maximum amount of water that can flow from the tank (source) to the fountain (sink).

typedef struct{
    int to;
    int flow;
    int capacity;
    int rev; // index of reverse edge
}edge;

int source;
int sink;
vector<vector<edge>> adj;

void addedge(int from, int to, int cap){
    adj[from].push_back({to, 0, cap, (int)adj[to].size()});
    adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1}); // reverse edge
}

int dfs(int curr, vector<bool> & visited, int bottleneck){
    if(curr == sink){
        return bottleneck;
    }
    visited[curr] = true;
    
    for (int i = 0; i < adj[curr].size(); i++){
        edge &e = adj[curr][i];
        if(!visited[e.to] && e.capacity - e.flow > 0){
            int flow = dfs(e.to, visited, min(bottleneck, e.capacity - e.flow));
            if(flow > 0){
                e.flow += flow;
                adj[e.to][e.rev].flow -= flow; // update reverse edge
                return flow;
            }
        }
    }
    return 0;
}

int fordFulkerson(){
    int maxflow = 0;
    while(true){
        vector<bool> visited(adj.size(), false);
        int flow = dfs(source, visited, INT_MAX);
        if(flow == 0) break;
        maxflow += flow;
    }
    return maxflow;
}

...

typedef struct{
    int to;
    int flow;
    int capacity;
    int rev; // index of reverse edge
}edge;
int source;
int sink;
vector<vector<edge>> adj;
void addedge(int from, int to, int cap){
    adj[from].push_back({to, 0, cap, (int)adj[to].size()});
    adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1}); // reverse edge
}
int bfs(vector<int> &parent){
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    q.push(source);
    visited[source] = true;
    parent[source] = -1;

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

        for (int i = 0; i < adj[curr].size(); i++){
            edge &e = adj[curr][i];
            if(!visited[e.to] && e.capacity - e.flow > 0){
                q.push(e.to);
                parent[e.to] = curr;
                visited[e.to] = true;
                if(e.to == sink) return 1;
            }
        }
    }
    return 0;
}
int edmondsKarp(){
    int maxflow = 0;
    vector<int> parent(adj.size());

    while(bfs(parent)){
        int flow = INT_MAX;
        for(int v = sink; v != source; v = parent[v]){
            int u = parent[v];
            flow = min(flow, adj[u][v].capacity - adj[u][v].flow);
        }
        for(int v = sink; v != source; v = parent[v]){
            int u = parent[v];
            adj[u][v].flow += flow;
            adj[v][adj[u][v].rev].flow -= flow; // update reverse edge
        }

        maxflow += flow;
    }
    return maxflow;
}

...