C++ Ford Fulkerson Algorithm for Maximum Flow

Introduction: Max Flow

We already had a blog post on graph theory, adjacency lists, adjacency matrixes, BFS, and DFS. We also had a blog post on shortest paths via the Dijkstra, Bellman-Ford, and Floyd Warshall algorithms.

The next thing we need to know, to learn about graphs, is about Maximum Flow.

The maximum flow problem is about finding the maximum amount of capacity, through a set of edges, that can get to an end destination. Think about it like us owning a factory that sends an infinite number of trucks out to an airport to ship our products, there being a set of roads to cities (and each road can only handle a certain amount of trucks at a time), and us trying to find the maximum number of trucks we can send to the airport at any given time, if we choose the best possible routes.

Max Flow Concepts - Residual Graphs, Min Cut, Capacity, Source/Sink

Let's go over a bit of theory before moving onto the algorithm and coding.

The source is the starting point where our (endless amount of) resources come from. The sink is where we're trying to send all of our resources.

Of course, we're working in a graph with vertices and edges. The vertices don't really matter in this case, but the edges will have certain weights on them that represent a capacity. A capacity is the amount of resource we can have travel along that edge at a given time.

A cut is literally some cut/drawn-line in the graph that partitions the graph into two sets. A cut is valid as long as the source is on one side and the sink is on the other. The minimum cut is equal to the maximum flow. (We're not actually going to use that information, but just remember it.)

An augmenting path in our graph is a path along the graph starting from the source, leading to the sink, along which we define some flow to go along the edge (as long as it's within the capacity).

We want to pick a bunch of augmenting paths from our source to the sink, but how do we make sure it's optimal? The concept of the algorithm that we're going to use is to build what's called a residual graph, which is basically the same graph that we start out with, but keep track of where our flow is so that we can undo some of the augmenting paths we chose before.

The Ford Fulkerson Algorithm

I can't go over the theory. It's too hard.

Basically we create our graph, represented as an adjacency matrix. Then we copy it to form a residual graph. Then we run BFS a bunch to find as many paths with unused capacity as we can.

// Copyright srcmake 2018.
// C++ Example Ford Fulkerson Algorithm

/* Ford Fulkerson Algorithm:
    // 0. Initialize an adjacency matrix to represent our graph.
    // 1. Create the residual graph. (Same as the original graph.)
    // 2. Create an default parent vector for BFS to store the augmenting path. 
    // 3. Keep calling BFS to check for an augmenting path (from the source to the sink...
        // 4. Find the max flow through the path we found.
        // 5. Update the residual capacities of the edges and reverse edges. 
        // 6. Add this path's flow to our total max flow so far.
*/

// The example graph: https://www.srcmake.com/uploads/5/3/9/0/5390645/maxflow_1_orig.jpg

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////
// See the picture here: https://www.srcmake.com/uploads/5/3/9/0/5390645/adjmatrix_1_orig.jpg
vector< vector<int> > FormAdjMatrix()
    {
    // Our adjacency list.
    vector< vector<int> > adjMatrix;
    
    const int n = 6;
    
    // Initialize our matrix to all 0s.
    for(int i = 0; i < n; i++)
        {
        vector<int> row;
        adjMatrix.push_back(row);
        for(int j = 0; j < n; j++)
            {
            adjMatrix[i].push_back(0);
            }
        }
    
    // First number is the vertex, second is the edge capacity.
    adjMatrix[0][1] = 15;
    adjMatrix[0][2] = 12;
    adjMatrix[1][2] = 9;
    adjMatrix[1][3] = 11;
    adjMatrix[2][1] = 5;
    adjMatrix[2][4] = 13;
    adjMatrix[3][2] = 9;
    adjMatrix[3][5] = 25;
    adjMatrix[4][3] = 8;
    adjMatrix[4][5] = 6;
    
    // Our graph is now represented as an adjacency list. 
    return adjMatrix;
    }
//////////////////////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////////////////////
// A special BFS version that returns true if there's a path from source to sink.
bool BFS(vector< vector<int> > &resAdjMatrix, int &source, int &sink, vector<int> &parent)
    {
    // Create an array for all nodes we visited. Initialized to false.
    int n = resAdjMatrix.size();
    bool visited[n] = { false };
        
    // Create a queue to check each node.
    queue<int> q;
    
    // Push our source into the queue and mark it as visited. It has no parent.
    q.push(source);
    visited[source] = true;
    parent[source] = -1;
        
    // Keep visiting vertices.
    while(q.empty() == false)
        {
        int u = q.front();
        q.pop();
        
        // Check all of u's friends.
        for(int i = 0; i < n; i++)
            {
            int v = i;
            int capacity = resAdjMatrix[u][v];
            
            // We find a neighbor that hasn't been visited, and the capacity is bigger than 0.
            if(visited[v] == false && capacity > 0)
                {
                // Push the neighbor onto the queue, mark it's parent, and mark it as visited.
                q.push(v);
                parent[v] = u;
                visited[v] = true;
                }
            }
        }
        
    // If the sink got visited, then we found a path to it. 
    if(visited[sink] == true) 
        { return true; }
        
    return false;
    }
//////////////////////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////////////////////
// Use the Ford Fulkerson algorithm. Return the max flow.
int FordFulkerson(vector< vector<int> > &adjMatrix, int &source, int &sink)
    {
    int maxflow = 0;
    
    // 1. Create the residual graph. (Same as the original graph.)
    vector< vector<int> > resAdjMatrix;
    int n = adjMatrix.size();
    for(int i = 0; i < n; i++)
        {
        vector<int> row;
        resAdjMatrix.push_back(row);
        for(int j = 0; j < adjMatrix[i].size(); j++)
            {
            resAdjMatrix[i].push_back(adjMatrix[i][j]);
            }
        }
    
    // 2. Create an empty parent array for BFS to store the augmenting path. 
    vector<int> parent;
    for(int i = 0; i < n; i++)
        {
        parent.push_back(-1);
        }
    
    // 3. Keep calling BFS to check for an augmenting path (from the source to the sink...
    while(BFS(resAdjMatrix, source, sink, parent) == true)
        {
        // 4. Find the max flow through the path we just found.
        int pathflow = 10000007;
        
        // Go through the path we just found. Iterate through the path.
        int v = sink;
        while(v != source)
            {
            int u = parent[v]; // The parent.
            
            // Update the pathflow to this capacity if it's smaller
            int capacity = resAdjMatrix[u][v];
            pathflow = min(pathflow, capacity);
            
            // Setup for the next edge in the path.
            v = u;
            }
        
        // 5. Update the residual capacities of the edges and reverse edges. 
        v = sink;
        while(v != source)
            {
            int u = parent[v]; // The parent.
            
            // Update the capacities.
            
            resAdjMatrix[u][v] -= pathflow;
            resAdjMatrix[v][u] += pathflow;
            
            // Setup for the next edge in the path.
            v = u;
            }
        
        // 6. Add this path's flow to our total max flow so far.
        maxflow += pathflow;
        }
    
    return maxflow;
    }
//////////////////////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////////////////////    
int main() 
    {
    cout << "Program started.\n";
    
    // Create our adjacency list.
    vector< vector<int> > adjMatrix = FormAdjMatrix();
    
    // Call FordFulkerson to get the max flow from the source to the sink.
    int source = 0;
    int sink = 6;
    
    for(int i = 0; i < 6; i++)
        {
        for(int j = 0; j < 6; j++)
            {
            int source = i;
            int sink = j;
            
            if(i == j) { continue; }
            
            cout << "The max flow from " << source << " to " << sink << " is: ";
            cout << FordFulkerson(adjMatrix, source, sink) << endl;
            }
        cout << endl;
        }
    
    
    cout << "Program ended.\n";
    
    return 0;
    }
//////////////////////////////////////////////////////////////////////////////////////////////

Conclusion

We looked at the Ford Fulkerson Algorithm for Max Flow. Actually, our implementation is the "Edmond's Karp Algorithm", which just means you use BFS instead of DFS to find the augmenting paths. (It's faster.) But we'll give the credit to Ford and Fulkerson...

In the next blog post, we'll look at using the Ford Fulkerson algorithm for bipartite matching.

Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
Github: srcmake

References
1. www.geeksforgeeks.org/max-flow-problem-introduction/
2. www.youtube.com/watch?v=VYZGlgzr_As&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp
3. cs.stackexchange.com/questions/55041/residual-graph-in-maximum-flow
4. www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/