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