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.
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 C++ Shortest Path - Dijkstra PQ Implementation, Bellman-Ford Code As Backup, and Floyd Warshall4/5/2018
Introduction: Shortest Paths
We've already had a blog post on graph theory, adjacency lists/matrixes for representing a graph, and BFS/DFS for traversing a graph. So how do we find the shortest path in a graph if there are edge weights? The answer is...we use the famous Dijkstra algorithm. (Assuming there are no negative edge weights.) If there are negative edge weights, then we use Bellman Ford.
What we want is, for a starting vertex/node, a list containing the shortest path from the starting node to every other node.
The above graph is what we'll be using in our algorithms. You can see that there are some nodes (vertices) labeled 0 to 6, and there are some edges that each have weights on them. We want the shortest path (lowest weight total) from one node to another. To the right is the adjacency list representation of the graph, where for adjList[i], there's a vector of pair<int, int>s at each index, where the first int represents the neighbor node, and the second int represents the edge weight between them.
Djikstra's Algorithm For Shortest Paths, using Priority Queue
Djikstra's algorithm is going to maintain a list of shortest paths from the starting node to all other nodes. Initially, the starting node has 0 distance to itself, but infinity distance to all other nodes. Then, by looking at all neighbors, of the node we're processing (starting with the start node), we'll update the shortest distances by checking if we can do better.
In this implementation, we use a priority queue, which will prioritize checking the shortest edge weights first.
Our code will generate that adjacency list, and perform the algorithm we mentioned before.
Bellman-Ford - Good For Negative Edges
Dijkstra is a greedy algorithm and will fail if there are cycles or negative edge weights. Because of this, we need the Bellman-Ford algorithm in that case. (But it's slower than Dijkstra, so use Dijkstra depending on the problem constraints.)
The results of running this should be exactly the same as Dijkstra. (But this takes longer.)
Floyd Warshall - Efficient For All Sources To All Nodes
Dijkstra and Bellman-Ford calculate the shortest path in a graph from one source node to all other nodes. But what if we need to calculate the shortest distance from all sources as the starting node, to all other nodes? That's what the Floyd Warshall algorithm is for.
We'll need an adjacency matrix representation of our graph for this problem. This time, edge weights that don't exist are set to infinity, and the distance of a node from itself is 0.
The output for node 0 is the same as Dijkstra and Bellman-Ford.
To Get The Path Itself
In our code, we saved the distance for each node from the source. But what if we need to know the actual shortest path (meaning what the nodes are, and not just the distance)?
Basically, in our distance list, we store not only the distance from "source node" to "current node", we also store the "previous node" in an int variable. Here's some updated code to show Dijkstra's algorithm where paths are stored.
The changes are to "vector<int> dist"" to "vector< pair<int, int> > dist" in our Dijkstra function (as well as line 116 where we store the previous node), the main function where the result is returned, and in the print function.
Conclusion
It takes some time to understand shortest path algorithms, but with some practice, it becomes second nature.
Next up in the graphing algorithm series is the Ford-Fulkerson algorithm for Maximum Flow. Check out this bloc post to see it.
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 Introduction: Graph Algorithms
A lot of problems in real life are modeled as graphs, and we need to be able to represent those graphs in our code. In this (short) tutorial, we're going to go over graphs, representing those graphs as adjacency lists/matrices, and then we'll look at using Breadth First Search (BFS) and Depth First Search (DFS) to traverse a graph. We'll be writing our code in C++, although the concepts can be extended to any programming language.
This tutorial is supposed to focus on the code, so the drawings are going to be ugly, and the definitions are going to be quick reminders instead of in-depth explanations. Graphs
To put it simply, graphs are a set of edges that connect some vertices. To say it "less mathy", there are some points, and some lines that connect those points.
In the graph above, we have four vertices (4, 1, 2, 5) that are connected by some edges. In this case, the edges are bidirectional, meaning 1 is connected to 4 and 4 is connected to 1. Some graphs have directed edges, meaning travel is only allowed in one direction.
Now someone at node 4 can get to node 1, but node 1 can't directly travel to node 4.
Finally, sometimes edges have weights on them.
A reason edges would have weights are to represent distances, as an example. For instance, one road could be 10 miles long, and another is 13.
So how do we represent these graphs in our code? We create what are called adjacency matrices and adjacency lists. Adjacency Matrices
An adjacency matrix is basically a table/spreadsheet, where each row and column represent a vertex. If the vertex 1 and vertex 4 are connected, then cell (1, 4) is a 1. If they aren't connected, then the cell is a 0.
If there's a certain edge weight, then you can represent that edge weight instead of 1 in the cell.
Adjacency matrices take up O(N^2) space. To find if a connection between two vertices exist takes O(1) time, since it's a quick lookup in the table. To add a vertex takes O(N) time, since you need to add a whole row for the new vertex (which also means initialization of the graph takes O(N^2) time).
Adjacency Lists
An adjacency list is another way to represent the edges of a graph. You create a list/array/vector that represents each vertex, and inside of each index for that vertex exists another list/vector/array for all of the vertices that the owner is connected too.
An adjacency list takes up less space than an adjacency matrix. The actual space it takes up varies based on the graph, but in the worse case, it could take up O(N^2) space if all vertices are connected to each other, which makes it MUCH worse than an adjacency matrix.
To look up a connection takes up O(N) time, as you have to search through a vertex's friend list to see if the friend exists. To add a new vertex is simple, though, and takes O(1) time, since you're just adding it to the end of a list. Traversing The Graph
So we can represent graphs in our code. (Well, you'll see the coding representations soon.) But how do we traverse through a graph? Specifically, if we're at vertex 1, can we get to vertex 3? What path do we take?
To traverse through a graph, we use BFS and DFS. For the sake of our examples, we're going to traverse through the following graph: Breadth First Search (BFS)
BFS is a technique for traversing through a graph where we start at a certain vertex, visit all of that vertex's neighbors, then visit the neighbor's neighbors, then visit the neighbor's neighbor's neighbors, etc. (In that order.)
Read through the comments to see what's going on.
Depth First Search (DFS)
Similar to BFS, DFS is a way to traverse a graph. However, instead of using a visiting all of a vertices neighbors before visiting the neighbor's neighbors, DFS just keeps visiting each new node it sees, meaning that it will usually go down a long path, and then come back to visit what it missed. As opposed to a queue, DFS works using recursion.
Read the comments to see how it works.
Conclusion
We went over Graphs, Adjacency Lists, Adjacency Matrices, BFS, and DFS. These data structures and traversal techniques are vital to using graphs.
The next step is to learn about calculating the shortest paths in graphs. See the next blog post to do this. Then, take a look at maximum flow in this blog post..
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 |
AuthorHi, I'm srcmake. I play video games and develop software. Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.
|