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. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210

// 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/