Skip to main content
Loading Explore guides…
Graph Theory · Acedra
Home
Explore
Computer Science
Graph Theory
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
333 segments
Copy
Hide video
0:01
Hello and welcome. My name is William and I'm super excited to bring to you this video series focused on graph theory. graph theory is one of my absolute favorite topics in computer science, we're going to see a lot of very awesome algorithms. The whole field is very diverse and hugely applicable to real world applications. I think everybody should be able to learn, love and enjoy graph theory. These first few videos are going to be a ramp up the dose to introduce the topics of how we store represent and traverse graphs on a computer. By the way, this whole video series will be taking on a computer science point of view of graph theory rather than a mathematical one. So we won't be covering proofs, and so on per se. Instead, we'll be looking at algorithm implementation details and code. So what is graph theory? In essence, it is the study of properties and applications of graphs, which common folk or non mathematical folks call networks. This is a very broad topic,
1:13
and my goal with this video series is to teach you how to apply graph theory to real world situations. graphs can be used to represent almost any problem which makes them so interesting, because they pop up absolutely everywhere. A simple problem that can be phrased as a graph theory problem might be given the constraints in this picture, how many different sets of clothes Can I make choosing an article from each category? Of course, this could be phrased and solved using only mathematics. But the advantage to graph theory is that it allows us to visualize the problem using nodes to represent an article of clothing and edges to represent relationships between them. Another canonical example of a graph theory problem is a social network of friends. A graph representation enables us to answer interesting questions such as how many friends this person x have, or how many degrees of separation are there
2:20
between person x and person y. Now, we have talked about different types of graphs. There are many different types of graph representations. And it's really important, I mean really important to be able to recognize what type of graph you're working with, and especially when you're programming and trying to solve a particular problem. This first type of graph is an undirected graph. It's the most simple kind of graph you'll encounter. And it is where edges have no orientation. That is, if there's an edge from node you to node v, it is identical to the edge from V to U. For instance, in the following graph, nodes are cities and edges represent bi directional roads. Since if you drive from one city to another, you can always retrace your steps by driving the other way. In contrast, to undirected graphs, there are also directed graphs, sometimes called die graphs. In these graphs, you've guessed it, the edges are directed. So if we have an edge from u to v, then you can only go from node
3:32
to node v, not the other way around. In this graph, you can see that the edges are directed because of the arrowheads on the edges between nodes. This graph could represent people who bought each other gifts. So an incoming edge represents receiving a gift and an outgoing edge represents giving a gift. Therefore, person e in this graph bought person d a gift, Person A bought themselves and Person B a gift, and person F, about nobody any gifts and received none. So far, we've only seen unweighted graphs, but edges on graphs can contain weights to represent arbitrary values such as cost, distance, quantity, you name it. weighted graphs come in both directed and undirected flavors. As a side note, I will usually denote an edge of a graph as a triplet u, v, w to indicate where an edge is coming from, where it's going to and what its weight is. Of course, with this notation, I also need to specify whether the graph is directed or undirected.
4:50
Next up, I just want to have a quick chat about special types of graphs and graph theory. There are so many different types of graphs that I only had to Select a few which will be most relevant for this upcoming video series. The most important type of special graph is definitely the tree. A tree is simply an undirected graph with no cycles. There are several equivalent definitions of a tree such as a graph with n nodes and n minus one edges. All the graphs below are trees. Yes, even the leftmost one since it has no cycles. A related but totally different type of graph is a rooted tree. The distinction here is that a rooted tree has a designated root node, where every edge either points away from or towards the root node. When edges point away from the root node. The graph is called an ABA ressence, or an outreach and an anti arborescens or entry otherwise, out trees are by far more common than entries. From what I've observed. It is also fairly common for people to refer
6:05
to a rooted tree simply as a tree instead of an in or out tree. But there is an important distinction there. Next are directed acyclic graphs. These are graphs with directed edges and no cycles. these graphs are very important and fairly common in computer science, actually, since they often are present structures with dependencies, such as a scheduler, a build system, a compiler, maybe, or perhaps more relatable University class prerequisites. There are several efficient algorithms that we'll be looking at to deal specifically with directed acyclic graphs, such as how to find the shortest path and produce a topological ordering of nodes. A topological ordering of nodes is an ordering of nodes that tells you how to process the nodes of the graph so you don't perform a task before first having completed all its dependencies. For example, a topological ordering of class prerequisites would tell you to take intro biology and intro chemistry before taking a class on say genomics.
7:20
This next type of special graph is a bipartite graph. It is one whose vertices can be split into two independent groups, u and v such that every edge connects between u and v. This is just a fancy way of saying that the graph is two colorable or that there are no odd length cycles and graph often, a problem we like to ask is what is the maximum matching, we can create on a bipartite graph? Suppose white nodes are jobs and red nodes are people then we can ask how many people can be matched to jobs. In this case, there are a lot of edges in each graph. So I think the answer for both is four. But in general, it's not so easy if there are less edges, tougher constraints and more conflicts. bipartite graphs also play a critical role in the field of network flow, which we will talk about later. This last type of graph is a complete graph is one where there is a unique edge between every pair of nodes in the graph. A complete graph with n vertices is denoted as the graph K
8:39
sub n, I have listed k one through k six on the bottom. And you can easily see how this scales when we add more notes. Complete graphs are often seen as the worst case possible graph you can possibly encounter, because of how many edges there are. So if you want to test your algorithm for performance, a complete graph is an easy way to start. One thing we're going to have to be really cognizant about is how we're actually representing our graphs on the computer. This isn't just what type of graph it is, but what type of data structure it but what type of data structure are we representing our graph with. And this can have a huge impact on performance. The simplest way is inside a 2d adjacency matrix. The idea is that the cell MI j represents the edge weight of going from node i to node j. So in the graph below, there are four nodes. So I create a four by four matrix and populate the graph with the
9:54
edge weights. If you look at the edge weight from node C to know D, you'll see that Hasn't agitative to. So in a row three and column four of the matrix there is a value of two. Note that is often assumed that the edge of going from a node to itself has a cost of zero, which is why the diagonal of the matrix has all zero values. This matrix form has several advantages. First, that it's very space efficient. For dense graphs. Those graphs with a lot of edges, the ED Jwi lookup can be found in constant time, which is quite nice. And lastly, I would argue that it is the simplest form of graph representation you can have. On the downside however, the main reason people don't go for the adjacency matrix as their first pick, is because it requires v squared space, which is, well a lot of space. In practice graphs with 10,000 nodes or more started to become infeasible very quickly. The other issue with the adjacency matrix is that it requires v squared work
11:10
to iterate over all the edges of your graph. This is fine for dense graphs with lots of edges. But it isn't so great for sparse graphs, since most cells will be empty. The main alternative to the adjacency matrix is the adjacency list, which is a way to represent a graph as a map of nodes to list of edges. The idea is that each node tracks all of its outgoing edges. For example, node C has three outgoing edges. So the map entry for C will track the edge from C to A with costs for the Add from C to B, with cost one, and edge from C to D. with cost to notice that, in the list of edges, we only need to track two things, the node we're going to and the cost to get there, we don't need to keep track of where we came from, because that's already implicitly known. The nice thing about adjacency lists is that it is great for sparse graphs, because it only tracks the edges that you have, and doesn't allocate additional memory that you might not use like the adjacency matrix does. This
12:27
also means it's efficient when iterating over all the edges. The main disadvantage to using an adjacency list is that it is less space efficient on denser graphs. Another subtle disadvantage is that it takes big O of E time to access a specific edges weight, although in practice, you rarely or if ever actually need to do this. The last representation I want to talk about is the edge list. an edge list is a way to represent a graph simply as an unordered list of edges. Basically, it's exactly what it sounds like a list of edges. Assume that the notation for any triplet u, v w means the cost from node u to node v is W. So for this graph, the edge list is simply a list of six edges represented has those triplets. This representation is very simple. However, it lacks structure. And that's why it is seldomly used. advantage to the Angeles is is great for sparse graphs. iterating over all the edges is super easy, and the structure is simple. The downside is that
13:46
edge lookup can be slow, and you can run into memory issues on large graphs. Today, I'm going to talk about common problems in graph theory. A lot of problems you will encounter can often be reduced to a famous or well known problem or some variant thereof. So it's important to be able to familiarize ourselves with common graph theory problems and their solutions. Just before getting started falling off from what we learned in the last video about representing graphs, I want you to think about how you would store and represent the graphs. And the upcoming problems I'm going to describe, in particular, is the graph and the problem I'm describing directed or undirected, are the edges of the graph. weighted or unweighted is the common use case, a graph that is likely to be sparse or dense with edges? And lastly, should I use an adjacency matrix and adjacency list and edge lists or some other structure to represent my graph efficiently? So one of the most if not the most common common
15:01
problem in graph theory is the shortest path problem. Given a weighted graph, find the shortest path of edges from node A to node B. So if we pretend this graph represents a road system, and were at node A and want to get to note H, our shortest path algorithm should be able to find us a list of edges to follow that will lead us from A to h with a minimal cost. Lucky for us, many algorithms exist to solve the shortest path problem, including a breadth first search for unweighted graphs. Dykstra is algorithm Bellman Ford, a star and many more. As simple as it sounds, connectivity is a big issue in graph theory. The problem can also be simplified to does there exist a path from node A to node B in this scenario, we don't care about the minimum costs, we just want to know. Can one node reach another node? A typical solution to this problem is to use a union find data structure, or do a very basic search algorithm such as a depth first search or a breadth first search.
16:15
Another common problem is detecting negative cycles in a directed graph. Sometimes we're dealing with graphs that have negative edge weights. And we need to know if a native cycle exists, because if there does, it can throw everything off. In this graph nodes One, two and three form a negative cycle. Because if you cycle through all the nodes, you end up with a cost of negative one if you add up all the edge weights, in fact, you can cycle endlessly getting smaller and smaller costs. In the context of finding the shortest path a negative cycle is like a trap that you can never escape. However, there are some contexts where negative cycles are beneficial. Suppose we're trading currencies across an exchange or multiple exchanges. Currency prices try to remain consistent throughout the day across exchanges, such as trading USD to euros or Canadian t yen. But sometimes there are in consistencies in the currency exchange prices. This makes it possible to do something called
17:25
an arbitrage, which cycles through multiple currencies exchanging one currency for another and coming back to the original currency with more money than you originally started, at a risk free gain. This is something we can use graph theory for, because it uses detecting negative cycles. There are two well known algorithms that can detect negative cycles. And those are Bellman Ford and Floyd warshall. Some thing that comes up now and again is finding strongly connected components within a graph. This is analogous to finding connected components of an undirected graph. But for directed graphs, when looking at strongly connected components, we're looking for self contained cycles within the graph where every vertex in a given cycle should be able to reach every other vertex in that same cycle. This is very useful in many algorithms as usually an intermediate step. So it's important to know how to find these strongly connected components. And there are many very elegant
18:31
algorithms to do so such as Tarzan's algorithm, you probably won't go through your computer science career without hearing about the traveling salesperson problem. The tsp problem is the problem of having n cities and the distances between each of them and finding the shortest path that visits each city and comes back to the original city at minimum cost. For example, if your graph is the one on the left, a possible tsp solution is the graph on the right, which has a cost of nine. The tsp problem is NP hard, meaning it is computationally challenging problem. This is unfortunate because the TSP problem has several very important applications. Some famous algorithms we can use to actually solve this problem or the healed Karp algorithm with dynamic programming doing some kind of branching and bounding algorithm or you can use one of many many approximation algorithms such as the ant colony optimization. This next problem I want to talk about is finding bridges in the graph,
19:42
which is something of a fascination to me. bridges are edges which if removed, increase the number of connected components in a graph. And this graph the edges highlighted in pink are bridges. bridges are important in graph theory because they often hint at what points, bottlenecks or vulnerabilities in a graph, think of your graph as a telephone network or a set of bridges between islands, you can immediately see the usefulness of detecting bridges related to bridges, but not the same articulation points, which are nodes that if removed, increase the number of connected components in the graph. In this same graph, you can see the three articulation points highlighted in pink. Next problem is finding the minimum spanning tree of a graph. A minimum spanning tree is a subset of the edges that connects all the vertices together without any cycles and with minimal possible cost. So in summary, it's a tree meaning it
20:46
has no cycles, and it spans the graph at a minimal cost. Hence why we give it the name minimum spanning tree. For example, in the graph below, one of the possible minimum spanning trees is this graph with a least cost of 12. Note that all minimum spanning trees of a graph have the same minimal cost, but are not necessarily identical. minimum spanning trees are seen in lots of different applications in computer science, including designing and least cost network circuit design, transportation networks, you name it. There's also several approximation algorithms which rely on minimum spanning trees, which is pretty interesting. If you want to find a minimum spanning tree of a graph, I recommend using one of Kuru schools prims, or beruf cause algorithm. This last problem, I think, is the most fascinating and it is about finding the maximum flow through a special type of graph called a flow network. Flow networks are networks where edge weights
21:53
represent capacities and some sense capacities might be things like the maximum amount of cars that fit on a road, or the maximum amount of volume that can flow through a pipe, or even the number of boats a river can sustain without destroying the environment. And these types of flow networks, we often find ourselves asking the question, with an infinite input source, that is cars, water boats, whatever, how much flow? Can I push through the network? Assuming we start at some source and try and make it to some sync node? This question is important, because at some point, there is bound to be a bottleneck somewhere in our flow graph that limits the amount of stuff we can have traveling on the network, making it from point A to point B, the maximum flow would then represent things like the volume of water allowed to flow through the network of pipes, the number of cards, the roads consisting and traffic or the maximum amount of boats allowed on the river. With these maximum flow
23:05
problems, we can identify the bottlenecks that slow down the whole network and fix the edges that have lower capacities. We're moving on to talking about the depth first search algorithm, which plays a central role in several graph theory algorithms. So what is the depth first search? A depth first search is a core algorithm in graph theory, that allows you to explore nodes and edges of a graph. So it's a form of traversal algorithm. The nice thing about a depth first search is that it's really easy to code. And it runs in time complexity of big O of a V plus e, that is vertices plus edges, which is directly proportional to the size of your graph. By itself. A depth first search isn't all that useful. But when argumented to perform other tasks, such as count connected components, determine connectivity between nodes, or find bridges and articulation points, the depth first search algorithm really shines. So let's
24:15
look at an example. As the name suggests, a depth first search plunges depth first into a graph without regard for which edge it selects next, until it cannot go any further at which point it backtracks and continues its exploration. So a depth first search has to start on a node. And I'm going to start our depth first search on node zero. And now we arbitrarily pick a node to go to some from node zero, we're going to go and do nine. Then from no nine, we only have one choice, which is to go to node eight, at node eight arbitrarily picking edge. So we're going to To go outwards to node seven, node seven, we have plenty of edges to choose from. So let's go to node 10, node 10, to node 11, and 11 to seven. So we don't want to revisit already visited nodes or nodes that are currently being visited. So we have to backtrack to indicate backtracking, I'm going to label edges and nodes as gray, so backtrack all the way back to node seven. So we're not finished exploring node seven,
25:36
because there are still edges to be picked. So I'm going to go to node three, and node three, I'm going to go node to node two is a dead end. So we backtrack, then go to node four, node four is also a dead end. So backtrack from node four, back to node three, then pick node threes last edge to go in Node five, five to six, and six to seven, can't go to seven, because we're visiting seven currently, so backtrack all the way back to node eight. from node eight, we still need to visit its last edge, which goes to node one, node one back to node zero, we can't go to node zero, because we're currently exploring it, then backtrack all the way to zero, which completes our depth first search traversal of this graph. So this was one particular depth for search traversal. But as you saw, it could have gone a lot of different ways. So now let's look at some pseudocode. For this depth first search, to get a deeper understanding of how it works. The first thing we need to do is initialize
26:55
these three variables, which are n the number of nodes in our graph, g the adjacency. List, representing the graph and visited a Boolean array containing true or false at index i depending on whether or not node i has been visited. In the beginning, this array should have all false values because we have not visited any nodes in the graph. Once that is set up. At the bottom, I define our starting node to be node zero and then called the depth first search method to do the exploration. The depth first search itself has one argument, the current node we are at which I have conveniently named at this method is recursive. So I checked the base case, which is whether we have already visited this node, if so we have no business here and can return otherwise, let's visit this node by marking it as true and exploring all of its neighbors to explore all the neighbors of the node, reach into the adjacency list
28:05
and pull out all the neighbors of this node and explore them depth first by looping over each and recursively calling the depth first search method. And that's all a depth first search really is in a nutshell, let's look at another simple use case. For a depth first search. I want you to discuss finding connected components in a graph. First, let's understand what we mean by connected component. Sometimes the graph is split into multiple disjoint components, and it's useful to be able to identify and count these components. One way to identify these components might be to color them so we can tell them apart. But what does coloring nodes really mean to a computer coloring nodes is equivalent to labeling each node is a component with the same ID value. For example, every node in the purple component gets an ID of one, and every node in the green component gets an ID of three, we can use a depth first search to identify components this way. First,
29:14
make sure all the nodes are labeled from zero to n non inclusive, where n is the number of nodes, the basic algorithm is to start a depth first search at every node, except if that node has already been visited, and mark all reachable nodes as being part of the same component using the same ID. So if we start at node zero, then we do a depth first search here and then every node in this component gets an ID of zero. So we go to eight, giving it an ID of zero, 14 gets zero 13 or so label it with a zero then backtrack like you do a depth first search, then explore note for given an idea of zero and then finish exploring. That component and then move on to the next node in order. So go to node one next, then node one, so depth for search there. So go node five, label it with a one, five goes to 17, label it with a one, backtrack, go to 16, also label it with a one, we're finished exploring this component, then we would go on to node two, wherever node two
30:26
is, then explore that component, then node three, explore node three is component unless node three has already been visited, and so on. So you do this for every component. Eventually, we get to label all the components, and we use a depth first search to do that. Awesome. So that's how we find connected components using a depth first search. Now let's look at some pseudocode. For how we do this, first, we'll need a couple of things. We'll need everything from the previous code we looked at so n, the number of nodes in our graph, G, our adjacency list, and our visited array, but additionally, we'll also need a variable called count that tracks the number of connected components and components an integer array that holds the integer value of which component a node belongs to. Inside the find components method, we loop over every node and check if the current node has been visited or not, and then execute some logic. This depth first search variant differs slightly from the previous
31:34
in that we execute a depth first search for every unvisited note, why do we actually do the depth first search, we visit nodes and mark them as visited. So we never revisit the same node more than once we either skip over a node because it's been visited in this for loop or start a depth for search there. If we start a new depth first search, we increment the count variable and keep track of how many depth first searches we have done. Inside the depth first search method itself, the two things we do are mark the current node as visited, and set the current node to be part of the component equal to the value of count, then simply iterate over every neighboring node that has not yet been visited, and call the depth for search method to explore them as well. Back inside the find components method, simply return the number of components and the components array that contains the information about which component each node belongs to. So we've covered two of the things you can
32:39
use the depth for search for doing a simple traversal and determining connected components. But we can argument a depth first search to do so much more, such as computer graphs, minimum spanning tree, detect and find cycles in the graph. Check if a graph is bipartite find strongly connected components topologically sought your graph. Find bridges and articulation points find augmenting paths in the flow network generate mazes, and many many more applications. So a depth research is super versatile, and can be extended to do a whole ton of things. Today's topic is the breadth first search graph traversal algorithm. Alongside the depth first search the breadth first search algorithm is another one of those fundamental search algorithms used to explore nodes and edges of a graph. It runs in a time complexity of big O of v plus e that is vertices plus edges, and is often used as a building block in other algorithms. It differs from a depth first search in the way that explores the graph.
33:50
The breadth first search algorithm is particularly useful for one thing, finding the shortest path on an unweighted graph. A breadth first search starts at a node in the graph and explores its neighbor nodes first before moving on to explore the next level of neighbors in the sense of breadth first search explores nodes in layers. So if we start breadth first search at zero, we would visit zero first, then visit all zeros neighbors, then we would visit all zeros neighbors, the nodes in yellow before moving on to the next layer of notes, then we would visit all their neighbors and so on. So as you saw a breadth first search expose a graph in a layered fashion, it does this by maintaining a queue of which node it should visit next, this is most easily seen with an example. Let's begin a breadth first search at node zero once more. So let's add zero to the queue on the left. I will denote the current node. in red. This zero is the current
34:58
node and we want to add Explore all zeros unvisited neighbors and add them to the queue. So we would add nine to the queue seven to the queue and 11 to the queue. So zero has no more unvisited neighbors. So we move on. So nine is next up in the queue. So we add all of nines unvisited neighbors to the queue. So that is 10, and eight, then there are no more neighbors of nine to visit. So we move on to the next node in our queue, which is seven, then we add all of sevens unvisited neighbors to the queue. So we try and visit node 11. But note 11 is already in the queue, so we don't want to add it again. So we skip it, then we will add six to the queue and three to the queue. Then this process goes on and on until we run out of nodes in the queue. So I will let the animation play. And that's how you do a breadth first search in a nutshell. In the previous animation, we relied on a queue to help us track which node we should visit next. Upon reaching a
36:28
new node, the algorithm adds it to the queue to visit it later. The queue dish structure works like a real world queue, such as a waiting line in a restaurant, people can either enter the waiting line that is get in queued or get seeded D queued. Let's look at some pseudocode for the breadth first search. First things first, we'll need to variables and the number of nodes in our graph, and G the adjacency list representing our unweighted graph. This breadth first search function takes two arguments s and E the start and end node indices of the search. The return value for this function is the shortest path of nodes from S to E. I've divided the function into two methods for simplicity. First, we solve the problem by executing the breadth first search and then we reconstruct the path from S to E. So let's take a look at the solve method. So here we are inside the solve method. The first thing I do is initialize the queue data structure that we'll need and add the starting
37:45
node to it. This queue should support at minimum the end q n dq operations I just talked about, then initialize a Boolean array with all false values and mark the starting node as visited. This array tracks whether or not node AI has been visited. If the value at index is true, then the node has either been visited or is being visited and is on the queue. And the animation this corresponds to the gray and yellow nodes. The last thing we'll need is an array called prev, which will help us reconstruct the shortest path from the start to the end node. Initially, this array should be initialized with all null values. This array tracks who the parent of node i was, so we can reconstruct the path later. Let's loop while the queue is not empty and plot the top node from the queue by issuing a dq operation, then reach inside the adjacency list and get all the neighbors have this node loop over each unvisited
38:58
node. Once we find a next unvisited node and queue it to the queue market as visited and keep track of the parent node of the next node in the prev array. Once the queue is empty, and our breadth first search is complete, simply returns the prev array. Back inside the breadth first search method take the output of the solve method which gave us the prev array and call the reconstruct path method. Here we are inside the reconstruct path method. The first thing we do is actually reconstruct the path by looping backwards from the end node and making our way back to the start node. That is assuming we can reach it. The reason the prep array had to be initialized to all null values is because that is the way and checking whether or not the for loop should stop since we loop through the prev array backwards, starting With the end node, we need to reverse the order of the nodes so that the path starts at the start node and ends at the end node. Last but not least,
40:10
we actually have to make sure the path between nodes s and E exists, it might not be possible to reach node II from node s. If the graph is disjoint. If this is the case, then simply return an empty path. Today we're going to talk about using a breadth first search to find the shortest path on a grid. This is going to be a really fun video because we're going to solve a problem. And I'm going to teach you a bunch of handy tricks when doing graph theory on grids. The motivation behind why we're learning about grids in this video is that a surprising number of problems can easily be represented using a grid, which a lot of the times turns into a graph theory problem. grids are interesting because they're a form of implicit graph, which means that we can determine a nodes neighbors based on our location within the grid. For instance, finding a path through a maze is a form of a grid problem you're trying to get from one side of the maze to the other. Well, you need
41:13
to find a path that's a pathfinding problem. Or perhaps you're a person trying to navigate your way through obstacles such as trees, rivers, and rocks to get to a particular location. And this can be modeled using a grid, and in turn, we end up using graph theory to navigate around. A common approach to solving graph theory problems on grids is to first convert the grid to a familiar format, such as an adjacency list or an adjacency matrix, so we can easily work with them. However, this isn't always the most efficient technique, but we'll get to that. Suppose we have a grid on the left, and we want to represent it as both an adjacency list and in the adjacency matrix, what do we do first, first, you should label all the cells in the grid with the numbers zero through n non inclusive, where n is the product of the number of rows and columns. So in this grid, on the left, there are six cells. So I labeled each cell with the numbers zero through six not inclusive, then we actually
42:20
want to construct an adjacency list and an adjacency matrix. Based off this grid, the adjacency list doesn't require any setup because it's simply a map that we initialize, but the adjacency matrix requires us to initialize a matrix of size six by six to represent our graph, there are six rows and six columns in the new adjacency matrix, because it's how many nodes that are in the grid we're trying to represent. Assuming edges are unweighted, and cells connected left, right up and down. Node zero connects with node one and node two, which we reflect in the adjacency list, and adjacency matrix on the right, then node one connects to node zero and node three, node two to node 03, and four, node three, with nodes one, two, and five, and so on. And that's basically how you convert a grid to an adjacency list or an adjacency matrix. Once we have an adjacency list or an adjacency matrix, we are able to easily
43:32
run whatever specialized graph algorithm we need to solve our problems such as finding the shortest path finding connected components, etc. However, transformations between graph representations can usually be avoided due to the structure and the nature of a grid. Let me explain. Suppose where the red ball in the middle and we know we can move left, right up and down to reach adjacent cells. Well, mathematically, if we're the red ball at the row column coordinate r comma C, we can add the row vectors minus 101 comma 00, comma one and zero comma minus one to reach all the adjacent cells. If the problem you're trying to solve allows moving diagonally, then you can also use the row vectors minus one minus one minus 1111 and one minus one. Using row vectors makes it easy to access neighboring cells from the current row column position. First, define the direction vectors for north south east and west broken down into their row column components. Then what
44:47
we want to do is loop over each direction vector and add it to the current position here I iterate I from zero to four non inclusive because we only have four directions, then add the Row direction to the current row to make our our the variable representing the new row, and then add the column direction to the current column to make cc the new column position. So the new position on the grid, our comma cc is an adjacent cell. However, it might not be an adjacent cell if we're on the border of the grid, and the new position is out of bounds. So we check that the new coordinate is within our grid by making sure that the new row column position is greater than or equal to zero and doesn't exceed the number of rows and columns of our grid respectively. So if those two checks pass, then we know that the new position r r comma CC, is a neighboring cell of our current position where the red ball was our car seat. So in summary, this
45:56
technique is really nice, really easy to code and actually naturally extends to higher dimensions. So let's solve a shortest path problem on a grid using the direct Shin vector technique we just learned about. So here's an abridged problem statement that you might encounter during an interview or in a programming competition. And it goes as follows suppose you're trapped inside a 2d dungeon and need to find the quickest way out. The dungeon is composed of unit cubes, which may or may not be filled with a rock. It takes one minute to move one unit north, south, east, or west, you cannot move diagonally and the maze is surrounded by solid rock on all sides. This problem statement is an easier version of the problem Dungeon Master on the caddis online judge see the problem link in the description. The dungeon is a grid of size R by C and you start at the node with an S character. And there's an exit at the
47:07
cell with an IE a cell full of rock is indicated by a pound sign or a hashtag, and empty cells are represented using a.in. This particular setup it's possible to escape the dungeon using this particular route highlighted in green. Remember that we want the shortest path to escape dungeon, not just any path, our approach is going to be to do a breadth first search from the start node until we reach the end node and count the number of cells we traverse during that process. However, it might not be possible to exit the dungeon if we cannot reach the exit, so we'll have to be mindful of that. So like in any breadth first search, we need to start by visiting our start node and adding it to the queue. Assuming we've already found the coordinate of our starting node within the grid we've added to the queue. Then we visit the adjacent unvisited neighbors and add them to the queue as well. And continue this process all the while avoiding adding rock cells to the queue.
48:09
So I'll let the animation play And meanwhile, try and predict which cells will be visited next. All right, after we find our end cell, we know how many steps it takes to get from the start to the end. Notice that we didn't even visit all the cells in the grid. The bottom right cell is still unvisited, so it's possible that we terminate early. If you're interested in actually finding the path itself rather than just the number of steps it takes to escape the dungeon, then you'll need to keep track of the previously visited node for each node. Go in and re watch the last video. If you need a refresher on how to do that. I want to talk a little bit about the way we are representing states in our breadth first search. So far, we have been storing the next x y position in the queue as an XY pair. This works well but requires an array or an object wrapper to store the coordinate values. In practice, this can require a lot of packing and unpacking of values to and
49:34
from our queue. Let's look at an alternative approach which also scales well in higher dimensions, and in my opinion requires less setup and effort. So the alternative approach I'm suggesting is to use one cue for each dimension. So in a three dimensional grid, you would have one q for each of the x, y and z dimensions. Suppose In queueing the coordinate x one y one Zed one, then we would simply place each coordinate in their respective queues. So the x coordinate goes in the x q, the y goes in its own y, q, and so on. As we need to keep in queueing different positions, we simply keep filling up these queues this way. This contrasts the approach of simply having one queue with each of the components packed away inside an object. The one thing we have to be mindful about, however, is that when we either end keyword dq elements, you need to mq and dq elements from each of the queues all at the same time. So when I dq or pull elements from the queue, I need to
50:47
remove an element from each of these queues. I prefer this representation when working with multi dimensional coordinates, which is why I want to share it, try it out and see if it works for you. So now that we have all the knowledge we need, we can solve the dungeon problem, let's look at some pseudocode. Assume that I have already read in the input matrix into memory and did some pre processing to find the coordinate of the starting node. The first two variables are the constants R and C the number of rows and columns in the input matrix following this is m, the input character matrix of size R by C. Next are two variables s, r and s see the row column position of the starting node. We'll need this to start our breadth first search our Q and c q r to Q data structures that represent the row Q and the column q will be enqueuing and D queuing elements from during the breadth first search. This next
51:54
set of variables is to keep track of the number of steps taken to reach the exit move count will actually track the number of steps taken nodes left in layered tracks how many nodes we need to dq before taking a step and nodes in next layer tracks how many nodes we added in the breadth first search expansion so that we can update nodes left and layer accordingly. In the next iteration, this will make more sense soon reached and tracks whether or not we have reached the N cell marked with an E. We're also going to make use of a visited matrix the same size as the input grid to track whether or not a cell has been visited since we do not want to visit a cell multiple times. And lastly, I defined the north south, east and west direction vectors. To solve the dungeon problem. This is all the code we'll need to execute our breadth first search and reach the exit. The first thing I do is add the start cells row and column values to the row Q and column Q, then don't forget
53:03
to mark the start cell as visited because we don't want to go there again, we're not done our breadth first search until both of our cues are empty. I checked the size of the row q is greater than zero, but you can also check the size of the column q is greater than zero since their sizes should always be in sync. Then since I know the queues aren't empty, I can dq the current position from the queues as the row position R and the column position C, then I check if we've reached the dungeon exit by checking if the current character in the grid is an eat. If it is then mark that we've reached the exit and break out early. Otherwise, we're not done exploring and we want to add all the valid neighbors of the current node to the queue, I wrote a function called explore neighbors they'll do just that. Let's have a look. Here we are inside the Explore neighbors method. This is where we'll be using the direction vector technique we learned about earlier.
54:08
Since cells have four directions we care about north south, east and west I loop I from zero to four non inclusive, compute the new coordinate r comma CC by adding the direction vector to the current position, make sure the new position is actually within the grid because we could end up with positions like zero comma minus one which is out of bounds. Even if the new position is within the grid that does not guarantee that is a valid position. The position might already have been visited previously, or it could be a blocked off cell such as a cell that isn't traversable and full of rock. If both of those conditions aren't true then we can en que the new position to visit it later. When en que a new position we are going to visit Make sure to mark it as visited now, so that it doesn't get added to the queue multiple times in the future. Also increment the number of nodes in the next layer, which we'll be needing shortly. This next block of code is used to track the number of steps
55:19
we took. Getting to the dungeon exit. Every time we finish a layer of nodes, we increment the number of steps taken, we know how many nodes are in each layer. Because we kept track of that in the Explore neighbors method. When the number of nodes in the current layer reaches zero, we know to increment the move count. At the end, if we are able to reach the exit, we return the move count, otherwise, we return minus one to indicate that the dungeon exit was not reached. So in summary, things we learned in this video are how to represent a grid as an adjacency list and an adjacency matrix, how to use direction vectors to visit neighboring cells, we explored an alternative way of representing multi dimensional coordinates with multiple queues. And lastly, we looked at how to use a breadth first search on a grid to find the shortest path between two cells. Today's topic is topological sort, also called top source for short, we're going to discuss what is top sort where it's used, and how
56:33
to find a topological ordering with some animation. The motivation for top sort is that many real world situations can be modeled as some graph of nodes, and directed edges where some events have to occur before others. Some simple examples include school class prerequisites, program dependencies, event scheduling, assembly, instruction ordering, and much, much more. Let's begin with an example. Suppose you're a university student, and you really want to take class Ah, well, before you can enroll in class H, you must first take classes D and E. But before taking Class D, you must also take classes A and B which have no prerequisites. So in some sense, there appears to be an ordering on the nodes of the graph. If we needed to take all the classes, the top sort algorithm would be capable of telling us the order in which we should enroll in classes, such that we never enroll in a course, which we do not
57:48
have prerequisites for another canonical example of an application of top sort is for program build dependencies. A program cannot be built unless all its dependencies are first built. For example, consider this graph where each node represents a program. And the edges represent that one program depends on another to run. Well, if we're trying to build program j on the right hand side, then we must first build program H and G. But to build those we also need EMF. But to build those we also need and so on. The idea is to first build the programs without dependencies and then move on with from there. How do we find a valid ordering in which to build all the programs? Well, this is where top sword comes into play. One possible ordering might be to start by building a then building C, B, the F, E, G, H, and then J. Notice that there are unused dependencies in this case, and that will happen from time to time which is fine. So in conclusion, top sort is an algorithm which will give us
59:13
a topological ordering. On a directed graph. A topological ordering is an ordering of nodes for which each edge from node A to node B. node A appears before node B in the ordering. If it helps, this is just a fancy way of saying that we can align all the nodes in that line and have all the edges pointing to the right. An important note to make is that topological orderings are not unique. As you can imagine there are multiple valid ways to enroll in courses, such that you can still graduate or to compile a program and its dependencies in a different order. Than you previously did. Sadly, not every type of graph has a topological ordering. For example, any graph with a directed cycle cannot have a valid ordering. Well think of why this might be true. There cannot be an order if there is a cyclic dependency. Since there was nowhere to start, every node in a cycle depends on another. So any graph with a directed cycle is therefore forbidden. The only graphs that
1:00:34
have valid topological orderings are called directed a cyclic graphs, that is grass directed edges and no cycles. So a natural question to ask is, how do I verify that my graph does not contain a directed cycle? One method is to use Tarzan's strongly connected component algorithm which can detect these cycles. Another neat thing definitely worth mentioning is that every tree has a topological ordering. Since by definition, trees do not have any cycles. and easy way to find a topological ordering with trees is to iteratively pick off the leaf nodes. It is like you're cherry picking from the bottom it doesn't matter the order you do it. Once the root of a subtree has all grayed out children, then it becomes available. This procedure continues until there are no more nodes left. So we know how it works with trees. But how about general directed a cyclic graphs? Well, the algorithm is also simple, just repeat the following steps. First finding unvisited node, it doesn't matter which from
1:02:03
this node, do a depth first search exploring only reachable unvisited nodes. On the recursive callback, add the current node to the topological ordering in reverse order. And that's it. Let's do an example. And things will become much clearer. Here's a directed acyclic graph that we want to find one of many topological orderings for as the algorithm executes, I'll be keeping track of the call stack on the left hand side. And in case you're curious, I will also be posting the current topological ordering at the bottom of the screen. The first step is going to be to pick in an visited note, I'm going to pick node h arbitrarily. Now we do a depth first search out towards from H and all possible directions exploring where we can. Let's go to node j. Now that I might know j, I'm going to keep exploring. And so let's go to m. Now that we're at, there's nowhere left to go so we backtrack and add as last element to the topological ordering
1:03:24
still at j and we still need to explore L. Now we're at L. Now backtrack because there's nowhere left to go. Also backtrack j and add it to the ordering. Notice that the stack frames getting popped off the call stack as I recurse. Now we're at h and we still need to visit node i. So now we're at node i and from node i, we try and visit node L. But then we figure out that note L is already visited so we don't go there, backtrack, backtrack, again add AI to the ordering and mark it as explored. And finally we're back at h as you saw selecting a random unvisited node made us visit a subsection of the graph. We continue this process until all nodes are visited. The next node I'm going to randomly pick is going to be node E in the interest of time and simplicity. I will let the animation run and you can follow along. Note that if you try and predict the next few values and topological ordering, he may not get the same values as me. Because topological orderings are not
1:04:44
unique. However, this does not mean you are incorrect. All right, I will let the animation play and try and follow along So that's it for that sub section of the graph. The next note I'm going to pick is going to be node C to visit. So we start node C and explore this sub section of the graph. Now that all nodes are visited, we have a valid topological ordering at the bottom of the screen. So now that we understand how the algorithm works, what does the code actually look like? Here's some pseudocode. For top sort. Let's walk through it real quick. The first thing I do as I get the number of nodes from the graph, which I assume is passed in as an adjacency list from the function, that I declare an array called v short for visited, which tracks whether a node has been visited or not. The next array called orderings, is the result that we'll be returning from this function. This is equivalent to the ordering
1:06:19
at the bottom of the screen. In the last slides associated with the orderings array is the index i, which tracks the insertion position of the next element the topological ordering. As you have been seeing in the slides, we insert elements backwards, which is why I start at n minus one. Next, we're ready to enter a for loop to iterate over all the nodes in our graph. The loop variable called at tracks the ID of the node we're currently processing. I then check if we're on a visit and node, because those are the only ones we care about. Then I started depth first search, notice that before I do, I initialize an array called visited nodes, which I pass into the depth first search method to add nodes as we find them. Then, after that's done, after the depth first search is finished, I look at the notes we found in our visited nodes array and then add them to the ordering. Now the last bit we need to look at is the depth first search method itself. The depth
1:07:39
first search method is very simple. All I do is I mark the node we're currently at to be visited. Then for each edge going outwards from the node we're at, I make sure the destination node is visited, then call the method again. But this time on the destination node. On the callback when the method returns. This is when we're stuck and need to backtrack. So this is where I add the current node to the visited nodes array, which is essentially the output for this method. Back to the top sorting method, now that we understand how the top sort algorithm works, there's a neat optimization we can do to prove the performance in terms of both time and space. Notice that every time we enter the inner if statement block, we need to allocate memory for an array, that array gets filled with node IDs and then we iterate over them to place them inside the orderings array. But how about we just directly insert found node inside the orderings array, instead of allocating memory and doing
1:08:52
this additional work? Well, that's exactly what we're going to do. Here I got rid of the unnecessary array and modify the depth for search method to return the next valid insertion position in the orderings array. Now we need to pass in the index i and the orderings array so that it can be filled directly inside the depth first search method inside the new depth first search method, one thing that changed is that now we have a return value, and we're passing in some additional variables. Notice that instead of adding the current node to the visit and notes array as we were doing before, now, we simply insert that note directly inside the orderings array. The last thing to do is to return i minus one, because the index of the current insertion position is no longer index i index i minus one. So related to the topic of topological orderings is the topic of shortest and longest path. On directed a cyclic graphs, recall that a directed acyclic graph is a graph with
1:10:09
directed edges and no cycles. By definition, this means that all trees are automatically directed acyclic graphs, since they do not contain any cycles. Here is a graph. My question to you is, is this graph a directed acyclic graph? And the answer is yes. But what about this structure? I'll give you a moment to think about it. The answer is no. Because this graph has undirected edges as opposed to directed edges. The graph may be a tree, but directed edges are a requirement for a directed acyclic graph. What's really great about working with directed acyclic graphs is that the single source shortest path problem can be solved very efficiently. In fact, in linear time, the next fastest single source shortest path algorithm is dextrous algorithm, which may not work if there are negative edge weights. This algorithm I'm about to show you is faster and doesn't care about positive or negative edge weights. The essence of the algorithm is that it finds
1:11:29
a topological ordering on the graph using the top sort algorithm we saw in the last video, and processes each node sequentially to get the shortest path by relaxing each edge as it is seen. Relaxing edge simply means updating to a better value if a shorter path can be obtained using the current edge. Suppose this is the graph we're working with, you can verify that it is in fact a directed acyclic graph. What we wish to do is find the shortest path from node A to all other nodes in the graph. In order to do this, the first thing we'll want to do is generate a topological ordering of the nodes of this graph. Using the top sort algorithm. Below I have selected and arbitrary topological ordering, which is the order we will process the nodes in this graph. I'm also displaying the current best distance to each node and bond the screen, which are all currently set to infinity, the first step of the algorithm is to set the distance to the starting node to be zero.
1:12:46
In this case, since a is the starting node, its initial distance is zero, because we're already there. From a we want to visit all reachable nodes starting with node B, and update the value to be if it is better than what was already there. This is the edge relaxation step of the algorithm, we noticed that a value of three is better than infinity, so we update the best value of b to be three, then the best value to see to be six. And now we've explored of his edges and want to move on to the next node node topological ordering which is B and explore all of its edges. So the first edge brings us to node E and we update its best value to 14. Because the best value add node B was three plus the edge weight to get e was 11 for a total of 14. Notice that edges get grayed out as they're being processed. Next, we update the best value to D to B seven. Now, we've reached the first instance where it is best and not to update the value of
1:14:08
the destination node, since a better path already exists to where we want to update. Now we move on to the next known or topological ordering and keep repeating the same steps where we explore all the nodes trying to relax each edge and then move on to the next node and the topological ordering. If we repeatedly do this the right way the bottom of the screen will contain the shortest path from node A to each node. I will let the animation play and you can try and determine the shortest path to all the remaining nodes which have not yet been processed. Okay, we're done processing all the nodes and know the shortest distance to every note, let's verify our algorithm computed the correct values by finding the shortest path to node H. Indeed, if we look at the path and some of the values along the edges, you will find that they do indeed sum up to 11, which is the shortest path in our array for node H. There's a similar problem to the shortest path problem, which is finding
1:15:41
the longest path in the graph. This problem is actually NP hard on general graphs, but can actually be solved in linear time on a directed acyclic graph. The trick is going to be to multiply each edge by minus one, find the shortest path, and then multiply all the edge values by minus one again, to take the previous graph, we had to find the longest path, simply negate all the edges, then find the shortest path and multiply the answer by minus one. And there we go. That's all you need to do. Okay, now let's have a look at some source code, you can find the code I'm about to show you on github@github.com. Slash William is that slash algorithms. Here I am on GitHub, and we're looking at some code for the shortest path on a directed acyclic graph. Here's our method directed acyclic graphs shortest path, and it returns the distance to each node, stored in an integer array. For some starting node, and as input, we give it the graph we're working with as an adjacency
1:17:08
list. Of course, the starting node and lastly, the number of nodes in our graph. So what we do is find the topological ordering for our nodes, I covered this in the last video, then initialize our distance array, and then set the starting nodes distance to be zero. And all we do is we loop through each node, starting at the first node, looking at what our node index is Four Tops or so this is the first node we need to visit and then check if that node is not equal to No, and then grab all the edges for that node, so we reach in our graph, and then pull out all the edges for the node index. Make sure there actually are some edges. And then for each edge, in the edges that we got, which were the adjacent edges, then all we do is the relaxation step, which is just this. So we compute the new distance. So this is the distance to the node, we're currently at plus the edge weight. So this is like the competing distance the distance we were trying
1:18:32
to improve upon, then we check, okay, has there ever been a distance set to where we want to go? This is basically the equivalent of infinity. And if so then we just want to give the new distance. Otherwise, we're going to take the minimum of the distance that's already there, and our new competing distance, which is this over here, and then we just do this over and over again, processing nodes and topological order, because we're pulling them out of the top sorted array. And at the end, we just return that distance array. And we can get the distance from our starting node to any other node in the graph, just through a lookup and this array. And guys, this is super simple algorithm. And that's all there is to shortest paths on directed acyclic graphs. Today, we're going to tackle Dykstra shortest path algorithm. This is one of the most important algorithms in graph theory for finding the shortest path on a graph. So without further ado, let's
1:19:45
dive right in. The first thing to mention about Dykstra algorithm is that it is a single source shortest path algorithm for graphs. This means that at the beginning of the algorithm you need Specify a starting node to indicate a relative starting point for the algorithm. Once you specify the starting node and execute the algorithm, Dykstra can tell you the shortest path between that node and all other nodes in your graph, which is pretty sweet. So depending on how you implement your Dykstra s and what data structures you use, the time complexity is typically big O of E log V, which is fairly competitive against other shortest path algorithms we see around. However, before we go crazy, trying to find shortest paths on various graphs, you need to know which graphs we are allowed to run dextrous algorithm on the one main constraint for Dykstra is that all edges of the graph need to have a non negative edge
1:20:49
weight. This constraint is imposed to ensure that once a node has been visited, it's optimal distance from the story node cannot be improved any further by finding a shorter path by taking edge with a negative weight. This property is especially important because it enables the extras algorithm to act in a greedy manner by always selecting the next most promising note. For this slide deck. My goal is to help you understand how to implement dichos algorithm and also how to implement it very efficiently. We're going to start by looking at the lazy implementation because it's by far the most common and then we'll look at the eager implementation of Dykstra has algorithm which uses an indexed priority queue alongside the decrease key operation. And lastly, I want to briefly mention how we can use other types of heaps in particular the D airy heap to further boost performance of the algorithm. At a high level, these are
1:21:48
the steps required in executing Dykstra algorithm. Note that there are two bits of information we'll need. The first is an array called dist that keeps track of the shortest distance to every node from the start node. Initially, this array can be populated with the value of positive infinity, except for the index of the starting node, which should be initialized to zero. Additionally, we'll also need to maintain a priority queue of key value pairs, the key value pairs will be node index distance pairs, which tells us which node to visit next, based on a minimum sorted value. At the start of the algorithm, we will begin by inserting the key value pair s comma zero into the priority queue, then we'll loop while the priority queue is not empty, pulling out the next most promising node index distance pair as we go. After that, for each node we visit, we will want to iterate over all the outwards edges and relax each edge appending a new node index distance key value pair to
1:22:56
the priority queue upon every successful relaxation. We do this until our priority queue is empty, at which point the shortest distance to each node will be stored in the disk array we are maintaining. So that explanation may have sounded a little bit abstract. Now let's look at an example with some animation to put all the pieces together. In all these examples, assume node zero is always the starting node. Although any node is perfectly fine. boxed in red is the distance I will be using it to track the optimal distance from the start node to every node in the graph. In the beginning, the distance to every node is initialized to have the value of positive infinity. Since we assume that every node is unreachable if at the end of the algorithm, there's still a value of infinity at a certain index, then we know that that node is unreachable. On the right I will be maintaining key value pairs corresponding to a nodes index and the best distance to get to that node. This priority
1:24:04
queue will tell us which node we should visit next, based on which key value pair has the lowest value. Internally priority queues are usually implemented as heaps, but I'm not going to show that visualization here. To start with assign a distance of zero to the start nodes index, which is index zero in the distance array. Also insert the key value pair zero comma zero into the priority queue to indicate that we intend on visiting node zero with a best distance of zero, then the algorithm actually starts and we look inside the priority queue for the first time and we discover that we should visit node zero from node zero we can visit node one by using the edge with a cost of four. This gives us a best distance of four so we can update the best distance from infinity to four and the dist array. Also add this information to the priority queue. Next, we can visit node two from node zero Just like the last note, we can update the optimal distance to reach no
1:25:04
to from infinity to one. Additionally, add that node to is reachable with a distance of one to the priority queue. So that concludes visiting all the edges for node zero. To decide which node we should visit next day shows always selects the next most promising node in the priority queue. To do this, simply pull the next best key value pair from the priority queue. node two is the next most promising node because it has a distance of one from the start node, while node one has a greater value of four. from node two, if we take the upwards edge, we can improve the best distance to node one by taking the current best distance from node two, which is one plus the edge cost of two to get to node one for a total cost of three, this is better than the previous value of four. For every time we find a better distance like this, we insert that information into the priority queue, then we improve the best distance to node three to be six.
1:26:03
The next most promising node is node one, we can improve the best distance to node three by taking the edge from node one to node three with a cost of one. The next most promising node is node one with value four, but we have already found a better route to get to node one. Since the disk array at index one has a value of three. Therefore we can ignore this entry in the priority queue. Having these duplicate key entries in the priority queue is what constitutes to making this implementation of Dykstra is the lazy implementation because we leisurely delete outdated key value pairs. Next up is no three, update the best distance to node four to be seven. We already found a better route to node three, so skip this entry in the priority queue. Finally, visit node four. And that's all for the lazy implementation of dynatrace. There are only a few moving parts, but enlarge the only things to really keep track of is the distance array, which contains the best distance so far from the
1:27:20
start node to every other node and the priority queue which tells us which node we should visit next, based on the best value found so far. Let's look at some pseudocode. For how this works. I'll be covering the real source code in the next video. For those interested, this pseudocode runs a Shor's algorithm from a start node and returns the distance array which tells us the shortest distance to every node in the graph. However, it will not tell you which sequence of edges to follow. To achieve that optimal distance, this is something that we will need to maintain some additional information for which I will cover as well. So in terms of the variables we'll need in the function definition, I specify three things first is G, the adjacency list of the weighted graph and the number of nodes in the graph. And s the index of the start node inside the function I begin by initializing two arrays to keep track of the information we'll need first is a Boolean array I called V is short
1:28:25
for visited which tracks whether node AI has been visited or not. Then I initialize dist the distance array which will be the output of the function make sure you feel the distance array with positive infinity except for the start node which should be set to zero after this initialize a priority queue that will store the node index best distance pairs sorted by a minimum distance, you should be able to use the built in priority queue in whatever programming language you're using. Remember to insert the start nodes index paired with a distance of zero into the priority queue to kickstart the algorithm. If you're wondering why there are two sets of brackets, that's because the pair x comma zero is meant to represent a tupple or an object with two values a key and a value. So while the priority queue is not empty, remove the next most promising index minimum distance pair and mark that node as visited then loop over all the neighbors of the current node and skip visited neighbors
1:29:28
so that we don't visit them again. Then simply perform the edge relaxation operation. First, compute the distance to the new node which is calculated by adding the best distance from the start node to the current node which is found the distance array plus the edge cost of getting to the next node. Once you know that compare it against the best distance for the next node I update the value if it's better. Then finally insert a new key value pair inside the priority queue. So we visit that node in the future. So in practice most standard priority queues do not support a decreased key operation for the built in barbecue. You can think of a decreased key operation as an operation which updates the value of a key and the party cue. A way to get around this is to add a new note index best distance pair every time we need to update the distance to a node. As a result, it's possible though have duplicate node indices in the priority queue like we saw in the animation. This is
1:30:26
not ideal. But inserting a new key value pair in logarithmic time is much faster than searching for the key, we want to update in the priority queue, which actually takes linear time. Yes, searching for a key in a priority queue takes linear time because the heap is sorted by the keys values, not the keys themselves. So effectively, it's like searching in an unordered list for a particular element. And neat optimization we can do which ignores stale, outdated index min distance pairs in our priority queue is to skip them immediately. As we pull them from the priority queue. We can do this by checking if the value in the distance array is better than the value in the priority queue. And if it is, then we know we have already found a better path routing through other nodes before we got to processing this note, I'll let that sink in for a little bit. But this is definitely a neat optimization you'll want to keep around. Now I want to
1:31:31
talk about finding the shortest path itself and not just the shortest distance to get there. And to do that, we'll need to keep track of some additional information. In particular, we'll want to keep track of the index of the previous node we took to get to the current node. The way to do this is to maintain a previous array I call prev. In this slide, this array tracks the index of the node you took to get to node I initially the previous array should be filled with a sentinel value such as now or minus one. But as you perform edge relaxation operations, you want to update the previous array to say that the node you're going to came from the node you're currently at, then at the end instead of returning the distance right also return the previous array which we will use soon. In another method of perhaps called find shortest path provide all the same arguments with the addition of the end node index and execute Dykstra has to obtain the distance array in the previous
1:32:37
array with these two bits of information, we can reconstruct the shortest path first check that the end node is reachable by checking that its value in the distance array is not infinity, then start at the end node and loop backwards through the previous array until you make it back the start node. You know you made it back to the start node when the value of null is reached. Since the start node does not have a parent node index from which came from the resulting path of node indices to follow for the shortest path from the start node to the end node will be in a reverse order because we started at the end node and worked backwards. Therefore, we want to make sure we reverse this array before returning the result. Now I want to talk about a few optimizations we can use to make dexterous algorithm more efficient. Sometimes we know the index of our destination node and don't necessarily need to know the optimal distance to every node in the graph, just that one particular
1:33:35
node. So the question is do we still have to visit every node in the graph just to figure out the distance of that one particular node we want to get to? The answer is yes, we do. But only in the worst case, which depending on your graph can be somewhat rare the key realization will need to make is that it is possible to stop early once we have finished visiting the destination node. The main idea for stopping early is that tech shows algorithm processes each next most promising node in order. So if the destination node has already been visited, its shortest distance will not change as more future nodes are visited. In terms of code, all we have to do to stop early is check if the current node index is the end node and return early. This can prove to be a very substantial speed up depending on how early you encounter the end node while processing the graph. Our current implementation of dices is what we call the lazy implementation because it inserts duplicate key value pairs
1:34:39
and leisurely deletes them. This is done because it's more efficient to insert a new key value pair in logarithmic time into the priority queue than it is to update an existing keys value in linear time. The lazy approach works but it is inefficient for dense graphs because we end up with all these stale outdated key value appears in our priority queue. The eager version of dank shows aims to solve this by avoiding duplicate key value pairs and supporting efficient value updates in logarithmic time using an indexed priority queue. And index priority queue is a priority queue variant which allows access to key value pairs within the priority queue in constant time, and updates in the log time if you're using a binary heap. This type of priority queue is extremely useful in many applications, and I highly recommend you watch my video on the index priority queue to become enlightened. I'll make sure I leave
1:35:37
a link in the description. But in the meantime, we'll just assume that we have access to an indexed priority queue. Now we're going to take a look at the eager version of dichos algorithm where we don't have duplicate keys and priority queue. So to start with, assign a distance of zero to the start node at index zero in the distance array. Also insert the key value pairs zero comma zero into the priority queue to indicate that we intend on visiting node zero with a best distance of zero, then the algorithm starts and we look inside the priority queue for the first time and we discover we should visit node zero. from node zero, we can visit node one by taking the edge with cost five, this gives us a distance of five so we update the best distance from infinity to five and the distance array also add this information to the priority queue. Next, we can visit node two node zero just like the last node, we can update the optimal distance to reach node two from infinity to one. Additionally
1:36:35
add node two to the priority queue with a distance of one. That includes visiting all the edges for node zero to decide which node to visit next dextra selects the next most promising node in the priority queue. So pull the next best key value pair from the priority queue. node two is that next most promising node because it has a distance of one from the start node, which is better than five. from node two, we can take the sideways edge to improve the best distance to node four to be 13 by taking the current best distance from node two, which is one plus the edge cost of 12. To get to node four, for a total cost of 13. We can update the best distance to node one by taking the upwards edge from node to notice that I did not insert a new key value pair with a value of one comma four inside the party queue, but rather simply updated the existing value in the party queue from five to four. This is the main difference between the lazy and the eager version.
1:37:45
The next most promising node is node one. When taking the downwards edge from node one to node two would discover that node two has already been visited. So we cannot improve it's already best distance. We also cannot improve the best distance note form by taking the diagonal downwards edge since the total cost of 24 outweighs the best distance of 13, which is already known for that note, however, we can improve the best distance node three by taking the edge from node one to node three with a cost of three. I'll let the animation play. And as it does try and predict what the next move for the algorithm will be. So that's the ingar version of Dykstra algorithm, which I would say is the more proper way of implementing texturas algorithm. Now let's look at some pseudocode and see what needs to change. First, notice that we're using an indexed priority queue instead of a regular priority queue. Also, notice that we no longer need to wrap our key value pairs as tuples
1:39:09
in an object because index partly queues have first class support for key value pairs, as opposed to a priority queue, which you would find in your programming languages standard library. The other thing that needs to change is how we insert key value pairs into the queue. If the key or note index does not yet exist in the index primary queue inserted otherwise invoke the decrease key operation to update the best distance to that node in pirna queue. The operation is called decrease key instead of update because it only updates the value if it is strictly less than the current value in the priority queue. All right, we've looked at several Dykstra optimizations already, but there's one key last optimization I want to talk about and that is is improving the heap we're using. Currently, we're probably using an indexed binary heap for our priority queue. But we can do better. The thing to notice is that when executing dextrose, there are a lot more update operations, especially
1:40:15
on dense graphs than there are removal operations. A dare heap is a heap variant in which each node has at most D children instead of two, this speeds up the decrease key operation at the expense of more costly removals. So if we look at an example, real quick, this is a dairy heap with D equals four. Suppose we want to perform an update operation, say we want to perform decreased key for node at index six with a value of one, then we can do the update. And then we reposition the key value pair inside the heap. So we bubble it up, and we bubble it up again. And now it's in the correct position. So that only took a total of two operations. While in contrast, suppose we want to remove the root node, then we swap it with the bottom right node. And then we need to reposition the purple node so that it's in position. So we need to look at all the children find the one with the least value and swap it and the purple node is still not in its correct
1:41:26
position. So again, we need to look at all the children find the one the smallest value and swapping. So that took a total of eight operations, which is clearly more expensive. But remember, there are a lot more decreased key operations and Dykstra than there are removals. So this might be beneficial overall. So the question then becomes what is the optimal dairy heap degree actually used to maximize the performance of Dec Shor's algorithm? And the answer in general is that the value of d should be equal to the number of edges divided by the number of nodes. This is the best degree to use the balance removals against decreased key operations. In turn, This improves Dykstra time complexity to be a big O of E times log base e divided by V of V, which is better, especially for dense graphs, which have a lot of decreased key operations. The last thing I want to mention is the current state of the art when it comes to choosing the right heat for dextrose algorithm. And right now,
1:42:36
the best heap we know of is the Fibonacci heap, which gives Dykstra has algorithm Believe it or not a time complexity of big O of E plus v log V, which is extremely fast. However, in practice, the Fibonacci heap is very difficult to implement, and also has a large constant amortized overhead. So it makes them slightly impractical in practice, because your graph has to be very large, or you to see the benefit. I have yet to implement one of these. So I cannot say whether they're that good, but this is just what I've read from other sources. Today we're going to have a look at some source code for Dykstra is shortest path algorithm. All right, here we are in the source code for Dec shows shortest path algorithm implemented in the Java programming language, let's have a quick run through. So in this class, I define an edge class which represents a directed edge, you'll notice that this directed edge has a certain cost of taking this edge. And it also has a destination node, which I call
1:43:49
to the node which this edge comes from will be implicitly represented in our adjacency list. So we don't need to take care of that. So when you go and create an instance of this class, you need to specify the number of nodes that are going to be in this graph. And that's the variable n. Once you know the number of nodes in your graph, you can go ahead and create an empty graph, this simply initializes our adjacency lists. So as you see here, I create an empty ArrayList with n nodes. And then for each position in the list, I create another list. So this is just an empty recency list. This will help us add edges to our graph, which you can do by calling this add edge method. So when you want to add an edge, the graph you specify the node, the edge starts at the node the edge ends at and the cost of taking that edge. Remember that the cost of taking edge cannot be a negative value. All right, and then there's the just this convenience method to retrieve the constructed
1:45:03
graph. If ever you want to have a look at that, then here comes the interesting method, which actually executes Dykstra is shortest path algorithm. So in this implementation, I provide a start node and the end node. This means we're going to try and go from a starting node index to an end node index. Note that we can also modify dextrose to give us the shortest distance to every node and not just a specific end node. So there is a way we can just remove this parameter, we don't really need it. But providing the end node allows us to do a small optimization, which is to stop early if we know we've reached that end node. So let's keep it in for now. So in the slides, in the last video, I mentioned that we can use an indexed priority queue to speed up dexterous algorithm. And this is exactly what I'm doing below, I have an implementation of a min index Dr. heap, which allows us to avoid duplicate nodes in our priority queue, I won't be going over the details of the min
1:46:11
indexed theory per se, because I already have another video on that in my data structure series, I'll make sure to have a link to that in case you want to check it out. But to construct a min index theory heap, I compute the degree of how many children each node should have in the heap by dividing the edge count by the number of nodes. And finally, inserting that the optimal distance to the start node at the beginning of the algorithm has a distance of zero, which makes sense, then I just initialize a few arrays. So this is the distance array, which is going to keep track the minimum distance to each node. So initially, I fill that with a value of positive infinity, and I set that optimal distance to the start node has a value of zero, perfect. And then these are just two supporting arrays that track whether node II has been visited. And this prep array is going to be used to reconstruct the shortest path should we ever need to Alright, let's look at this while loop which contains the
1:47:22
bulk of the Dykstra algorithm implementation. So while the priority queue is not empty, we're going to first get the ID of the node with the shortest distance. And we're also going to get the minimum value associated with that node. So while we're at it, we're going to mark that this node is visited so that we don't revisit it again in the future, this line right here, which says that the min value if the minimum value we got from the priority queue is greater than the already optimal distance, and the distance array for the node we currently pulled out of the queue, then we can continue this is because we already found a better path of routing through another set of nodes. Before we got to processing this node, which is fine. The next thing we want to do is get all the edges going outwards from this node. So we can reach into our adjacency list and get all the edges coming out of the current node, then we check if the node this edge wants to go to has already been visited,
1:48:33
then we can skip that we don't want to revisit an already visited node, then we compute the new distance of going from the current node to the destination node. And we do this by reaching into the distance array grabbing the already optimal distance for that node and adding the edge cost then we try and relax the edge. So we check if the new distance is better than the distance already in the distance array at the node we want to go to remember that originally, all the indices in the distance array are set to positive infinity. So the first time we visit any node, this condition will always be true, then we just do some housekeeping stuff. So Mark that the optimal distance to get to a certain node came from the current node we're at and also update the distance arrayed have the new optimal distance, then we update our index priority queue. We do this by inserting the cost of going to a node for the first time or we try and employ a decrease key operation to update
1:49:41
the current best distance to that node to be even better than after that loop. We can check if we've reached our end node and if we have we can return the optimal distance to it. So this is the optimization of returning early Otherwise, if we've reached the end of the algorithm, and the while loop has terminated and the priority queue is empty, then return a positive infinity. The rest of this class contains the reconstruct path method in the event that you want to actually reconstruct the shortest path from the start node to the end node. And this is pretty straightforward, simply give it the start node you want to start at the end node index, then run Dykstra algorithm, make sure that the end node is actually reachable from the start node, then simply loop through the previous array and reverse the path and return it as simple as that of all the shortest path algorithms in graph theory. Bellman Ford is definitely one of the simplest, yet I struggled as an undergrad
1:50:55
to trying to learn this algorithm, which is part of the reason I'm making this video. So what is the Bellman Ford algorithm? In short, it's a single source shortest path algorithm. This means that it can find the shortest path from a starting node to all other nodes in the graph. As you can imagine, this is very useful. However, Bellman Ford is not ideal for single source shortest path algorithms, because it has a much worse time complexity than Dykstra his algorithm. In practice, Bellman Ford runs in a time complexity proportional to the product of the number of edges and the number of vertices, while de show can do much better at around big O of E plus v log V with a binary heap. So when would we ever use the Bellman Ford algorithm? The answer is when Dykstra does fails. And this can happen when the graph has negative edge weights. When a graph has negative edge weights, is possible that a negative cycle can manifest itself. And when
1:52:06
it does, it is of critical importance that we are able to detect it. If this happens, and we're using Dykstra is to find the shortest path, we'll get stuck in an infinite loop because the algorithm will keep finding better and better paths. A neat application of Bellman Ford and negative cycles is in finance and economics when performing an arbitrage between two or more markets, I'm not an expert. But this is when prices between different markets are such that you can cycle through each market with a security, such as a stock or a currency, and end up with more profit than you originally started with, essentially getting risk free gains. Let's look at how negative cycles can arise. Because this seems important. Here is a graph I made with directed edges, some of which are negative. I've labeled our starting node to be node zero. And our goal would be to find the distance from zero to every other
1:53:09
node in a single source shortest path context. But right now, we are only interested in detecting negative cycles, I will label blue nodes as regular nodes, red nodes as nodes directly involved in a negative cycle, and yellow nodes as those reachable by a negative cycle. One way negative cycles can emerge is through negative self loops. What happens is that once we reach a self loop, we can stay in that loop for a near infinite amount of time before exiting. As a result, everywhere reachable by the cycle has a best cost of negative infinity, which depending on your problem may either be good or bad. In this graph, nodes 234 and five are all reachable by node one. So they all have a best cost of negative infinity with regards to the single source shortest path problem. Let's look at another example. In this graph, a negative cycle manifests itself but not as the result of a negative self loop. Instead, through a cycle of nodes whose net gain is less than zero. If you add
1:54:29
up the edge values one four and minus six, attached to the nose, one, two, and three, the net change is minus one. If we look at where this cycle can reach, we can see that the entire right side of the graph is affected. So hardly any notes are safe from this negative cycle. Now let's look at the actual steps involved in the Bellman Ford algorithm. First, we'll need to define a few variables. Let e be the number of edges of the graph. Let v be the number of vertices. let S be the ID of the starting node. In this case, S is short for start. And lastly, let D mean an array of size v that tracks the best distance from S to each node. The first thing we'll want to do is set every entry in D to positive infinity. This is because the distance to each node is initially unknown, and we have no idea how far each node is. Next, we'll want to set the distance to the starting node to be zero, because we're already there. The last part of the algorithm is to relax each
1:55:47
edge v minus one times relaxing edge simply means taking an edge and trying to update the value from where the edge starts to where it ends. In terms of code, this is all we need to do. We loop v minus one times, then for each edge, we relax the edge. In the relaxing step, what we do is we look at the value of where the edge starts at the edge cost and see if that's better than where we're trying to go. And if so, update with the shorter path value. To actually detect negative cycles, we don't do anything too special, all we do is run the algorithm a second time, what we're doing in the second pass is checking for any nodes that update to a better value than the known best value. And if they do, then they're part of a negative cycle, and we want to mark that node as having a cost of negative infinity. Let's look at a full example. Here is a graph I made. Again, we will start on node zero, and find the shortest path to every other node. On the right, I have illustrated the
1:57:00
distance array D. Watch the values in this array change as the algorithm executes. Right now, all the values in the array are set to positive infinity, as per the first step of the algorithm. In the second step, we set the starting nodes value to zero. Now the algorithm starts and we are on the first iteration where we attempt to relax each edge. But before we continue, I have an important note at the bottom of the screen, which says that the edges do not need to be processed in any particular order, I may process the edges with one ordering, and you process them with another ordering. And we may not end up with the same values on each iteration. But we will get the same result in the distance right at the very end, I will highlight the edge currently being processed in orange and update the distance array whenever appropriate. Right now, the best value to node one is five, because a distance of five is better than a distance of positive infinity, then nerd who gets its
1:58:12
value updated to 25, because node one had a value of five from the last term, and the edge from node one to node two is 20 for a total of 25. Then a similar thing happens to node five, and node six as well. By the way, an edge is dark gray if it has already been processed in this iteration. Next up, node three gets its value updated from infinity to 35. Because the best value in node two, so far as 25 plus the edge cost of 10 is 35, then the edge from two to four updates to a best value of 100. Up next is an interesting edge because it was able to update node two's best value from 25 to 20 by taking the value in Node three, which is currently 35, adding a weight of minus 15 and giving us a better value of 20. So this is all the algorithm does, it processes each edge performing relaxation operations. I'll let the animation play for the rest of this iteration. So iteration one is over and there are eight more iterations to go. But for simplicity,
1:59:49
I'll just play one more iteration. To give you an idea of how the algorithm works. We reset all the edges and start processing the edge Again, you'll notice that a lot less updating happens in the distance array this round, particularly because I unintentionally selected the edges to be processed in a more or less optimal way. So that's the end of the second iteration. If we fast forward to the end, here's the resulting distance array. However, we're not done, we still need to find the negative cycles. Let's execute the algorithm a second time, same procedure, as usual, just relax each edge. But when we are able to relax edge, update the nodes value to negative infinity Instead, let's process some edges until something interesting happens. So it appears that when we went from node two to node three, we are able to relax the edge and obtain a better value for note three than was previously there. So note three is part of some negative cycle, therefore, I
2:01:04
will mark it as red. Similarly, note four is connected to a negative cycle, although indirectly, in the distance table, I do not distinguish between nodes which are reachable by a negative cycle, and those which are primarily involved in one. So those no way to tell them apart, feel free to add some logic in the Bellman Ford algorithm. If you need to make this distinction. Continuing on, new two is also trapped in the cycle. And the last node also affected by the cycle is no nine on the right. Let's finish up with this iteration by processing the rest of the edges. So that's it. For the first iteration, there are another eight iterations to perform. In this example, we happen to detect all cycles on the first iteration. But this was a coincidence. In general, you really need another eight iterations. This is because you want the negative cycle minus infinity values to propagate throughout the graph. The propagation is highly dependent
2:02:18
on the order in which the edges are being processed. But having v minus one iterations ensures that this propagation occurs correctly. Alright, now I want to have a look at some source code, you can find a link in the description below. Or you can go to github.com slash William fiza slash algorithms. Here we are on GitHub in my algorithms repository. Now if you scroll down and look for Bellman Ford, under the graph theory section, you can see that currently there are two different implementations, one for graph represented as an edge list, another one for a graph represented as an adjacency list. Today, we'll have a look at the edge lists implementation. So in the edge lists implementation, first thing I do is I define a directed edge. And a directed edge simply consists of an edge that goes from a node to a node with a certain cost. Next, let's have a look at the actual algorithm itself. So from Bellman Ford, what we need is, well, a graph. So since this is an edge list, we
2:03:45
just pass in all the edges. I'll also need the number of vertices in the graph and some starting node. And what we're returning is that distance array. All right, so let's initialize the distance array, and then populate it with this special value double dot positive infinity, then set dist of start to be zero. And then just as the pseudocode said, just loop v minus one time, then for each edge, just to relax the edge. So that's what we're doing. And here. Now this second pass of the algorithm is to detect negative cycles. So run the algorithm a second time, so loop the minus one times for each edge, relax the edge, but this time, instead of updating the edge to a value, we set the value two double negative infinity. And this is a special value defined in Java that represents negative infinity and no matter what value you add to double dot negative infinity, it will still be negative infinity. Unless you add double dot positive infinity then I think gives you double dot, not a number
2:05:11
or something like that. And that's the entire algorithm, then we just return the distance array. If you look in the main method, it shows you how to actually create a graph, add some edges, and then run Bellman Ford and find the distance from a starting node to all other nodes in the graph. And that is Bellman Ford. Today's topic is the Floyd warshall. All pairs shortest path algorithm, we will be covering how the algorithm works, how to reconstruct shortest paths, the handling of negative cycles, followed by some code. So let's get started. In graph theory, the Floyd warshall algorithm is an all pairs shortest path algorithm. This means it can find the shortest path between all pairs of nodes. This is very important for many applications across several fields. The time complexity to run Floyd warshall is big O of V cubed, V being the number of vertices in the graph. This makes the algorithm ideal for graphs with no more than a couple 100 nodes.
2:06:20
Before we dive too deeply into the Floyd warshall algorithm, I want to address when you should and should not use this algorithm. This table gives information about various types of graphs and or constraints in the leftmost column, and the performance or outcome of common shortest path algorithms. For example, you can see in the second row that a breadth first search, and Dykstra is can handle large graphs with lots of notes, while Bellman Ford and Ford warshall not so much. I suggest you pause the video and really go through this table and make sure you understand why each cell has the value it does. What I want to highlight is the rightmost column since we're talking about the Floyd warshall algorithm, the void washout algorithm really shines in three places. And those are on small graphs, solving the all pair shortest path problem and detecting negative cycles, you can use the algorithm for other tasks, but there are likely better algorithms out there with Floyd warshall.
2:07:27
The optimal way to represent our graph is with a two dimensional adjacency matrix, which I will denote as the letter M. The cell m ij represents the edge weight of going from node i to node j. So in the image below, I transformed the graph with nodes A, B, C, and D into an adjacency matrix on the right. And important note, I should mention is that I assumed that the distance from a node to itself is zero, which is usually the case. This is why the diagonal has all zero values. When there is no edge between nodes i and j, set the value in the matrix M ij. To be positive infinity. This indicates that two nodes are not directly connected to each other. A very important note to make is that if your programming language doesn't support a special constant in its standard library for positive infinity, such that infinity plus infinity equals infinity, and infinity plus x equals infinity, then you should avoid using two to the power of 31 minus one as infinity.
2:08:44
If you do so, then you will likely get integer overflow, simply use a large constant instead, as we will see the main idea behind the Floyd warshall algorithm builds off the notion that you want to compute all intermediate routes between two nodes to find the optimal path. Suppose our adjacency matrix tells us the distance from a node A to a node B is 11. Now suppose there exists a third node C, if the distance from A to C and then C to B is less than a distance from A to B, then it is better to go through node C. Again, the goal is to consider all possible intermediate paths between triplets of nodes. This means we can have something like this where the optimal path from A to B is first going to C, then going from C to B, but in the process, we actually route through another node, which I labeled with a question mark, because we've already computed the optimal path from C to B and I know that it involves an intermediate node. Similarly, we can get through Longer
2:10:00
paths with more intermediate nodes between A and C and C and B with a smaller cost. We are also not just limited to one intermediate node in between A and C, and C and B, we can have several like in the graph below. Now the question comes up, how do we actually compute all intermediate paths? The answer is we will use dynamic programming to cache previous optimal solutions. Let dp be a three dimensional matrix of size n by n by n, which acts as our memory table, we're going to say that the cell dp at K IJ in our table gives us the shortest path from node i to node j, routing through nodes zero through Kyt. What we'll do is start by computing k equals zero, then k equals one, then k equals two and so on. This gradually builds up the optimal solution rounding through zero, then all optimal solutions writing through zero and one, then all optimal solutions writing through 01, and two, and etc. Up until we covered all nodes, at which
2:11:18
point we have solved the all pairs shortest path problem. Let's talk a bit more about how to populate the DB table. In the beginning, the optimal solution from i to j is simply the distance given to us in the adjacency matrix. So when k equals zero, dp of K ij is equal to m ij, the value of the edge from i to j. Otherwise, in general, dp, k, i j, can be summed up with the following recurrence relation, I'm going to break it down so that we can understand all its components. Because this may look scary to some people. The left hand side of the recurrence simply says, reuse the best distance so far from itj, routing through nodes, zero to k minus one, it's important to note that the solution using nodes, zero to k minus one is a partial solution. It is not the whole picture. This is part of the dynamic programming aspect of the Floyd warshall algorithm. The right hand side of the recurrence finds the best distance from i to j, but routing through node k, reusing the best solutions
2:12:35
from zero to k minus one. If we analyze the right side of the min function in English, it basically says, Go from itk then go from k to J. Visually, this is what it looks like. You start at I route through some notes and get to K and then from K route back to J. Currently, our algorithm uses big O of V cubed memory. Since our memo table dp has one dimension for each of k, i and j. This isn't particularly great. Notice that we will be looping over k starting from zero, then one, then two, and so forth. The important thing to note here is that previous results build off the last, since we need the state of k minus one to compute state. Okay. That being said, it is possible to compute the solution for K in place, saving us a dimension of memory and reducing the space complexity to big O of v squared. Now we have a new recurrence relation which no longer involves the K dimension. This has been replaced by the fact that we're computing the k plus one solution in place inside our matrix.
2:14:00
Okay, that's all the theory we need. For now, let's get our hands dirty and look at some pseudocode. Below is the function that actually solves the Floyd warshall algorithm or rather executes a Floyd warshall algorithm. But before we get into that, let's look at some of the variables I have defined in the global or class scope, which I will be using throughout these functions. The first variable is the number of nodes in our graph, then is the 2d memo table that will contain our all pair shortest path solution. Last is the next to D table that we will use to reconstruct our shortest paths. Now moving on to the Floyd warshall function, you see that it takes one parameter. This is the 2d adjacency matrix representing our graph. The first thing I do in the method is call the setup function. So let's take a look at that real quick. So here we are inside the setup function, the first thing I do is I allocate memory for our tables, the DP matrix should have the
2:15:08
same type as the input adjacency matrix. What I mean by this is if your edges in your input matrix are represented as real numbers, then your dp matrix should also hold real numbers, the next matrix will contain indexes of nodes to reconstruct the shortest paths found from running the Floyd warshall algorithm. It is important that initially this matrix be populated with null values inside the four loops, all I do is copy the input matrix into the DP matrix. Think of this as the base case or rather the K equals zero case. For the next matrix, if the distance from i to j is not positive infinity, then the next node you want to go to from node i is node j by default. Now we're back inside the Floyd warshall function. In here after the setup, loop over k on the exterior loop, it's important that k is on the exterior loop. Since we want to gradually build up the best solutions for k equals zero, then k equals one, then k equals two and so on. Followed by this loop over all pairs of
2:16:22
nodes i and j. Inside the main body actually tests for our condition to improve the shortest path from itj going through K and update the value at dp ij. If there's a better route through K, also inside here, update the next array at ij. to point to the next index. At next ik, the last thing I want to do is to detect and propagate negative cycles. This is an optional step if you know that negative cycles will not manifest themselves within your graph. Although I still recommend you keep this function around. But before we get too far, I want to discuss negative cycles and what they entail because it isn't entirely obvious. So consider the following graph. There are basically two types of nodes to consider here. Nodes directly involved in negative cycles, and nodes unaffected by negative cycles. This red node is the cause of a negative cycle because it can endlessly loop on itself and obtain smaller and smaller costs. While these blue nodes are not directly in a negative
2:17:39
cycle. This however, doesn't mean they're not necessarily safe from negative cycles. As we will see, negative cycles can also manifest themselves as groups of nodes working together like the following. So an important thing to ask ourselves is does the optimal path from node i to node j go through a red note. If so, the path is affected by the negative cycle and is compromised. For example, the shortest path from zero to five is negative infinity. Because I can go from zero to node two, an indefinitely loop in the negative cycle consisting of nodes, one, two and three, obtaining better and better costs before eventually going to five. This is a consequence of traversing a red node on the way to five. Some shortest paths however, avoid red nodes altogether, consider the shortest path from four to six. This doesn't involve any red nodes, so we can safely conclude that the shortest path from four to six is indeed two. So to identify whether or not the optimal path from i to
2:18:59
j is affected by a negative cycle, rerun the Floyd warshall algorithm second time, if the best distance is better than the already known best distance stored in our table dp, then set the value in the matrix from it j to be negative infinity, also mark the index at ij in the next matrix with a minus one to indicate that the path is affected by a negative cycle. We will use this shortly. Back in the Floyd warshall function, all we need to do is return the matrix dp which contains the shortest distance from any node to any other node. This is the solution to the all pairs shortest path problem. The last thing I want to cover is how to reconstruct the shortest path between any two pairs of notes. This method returns the shortest path between the start and end nodes specified or know if there is a negative cycle for Check the distance between the start and end nodes is positive infinity, if so then return an empty path. Then to reconstruct the path, I create a variable
2:20:10
called act to track the current node. And then I loop through the next array, adding the current node to the path as I go. During this process, I check if the current node has the value minus one. If it does, then this means that the optimal path encountered a red node and is trapped in a negative cycle. So return null. Notice that in reality, this method has three key returned values, and empty path, which means that the start and end nodes are not connected, a null value meaning a negative cycle was encountered. And lastly, a non empty path or node indices to mean an actual shortest path was found. Today, we're going to be looking at some source code for the Floyd warshall. All pairs shortest path algorithm. Here we are in the source code for the Floyd warshall algorithm. So let's get started. Let's start by looking at an example of how to use this Floyd warshall solver class to actually find all pairs shortest path. So here in the main method, the first
2:21:22
thing I do is I actually initialize a graph with n nodes, where n is set to seven. And I create our adjacency matrix by calling the Create graph method. And if we look at up here, this is the Create graph method. And all it does is it initializes a matrix of size n by n, it fills the matrix with the special constant positive infinity. And it also sets the diagonals have all zero nodes, by default, because I assume that this is the behavior you want. If it's not, then that's not an issue, because you can just override it when you add some edge values to your adjacency matrix. Alright, so we created a matrix, we added some edge weights. And then what you'll want to do is create an instance of the solver, give it our adjacency matrix, and then call get all pair shortest path matrix function, which will return the all pair shortest path matrix as a matrix called just for a distance. And then here, all I do is I loop over all pairs of nodes i and j. And I print what the
2:22:37
shortest path from node i to j is. Here's a sample output of what that looks like. So there can be roughly three different kinds of outcomes, we get a concrete shortest path, there does not exist the path between the two nodes, they'll be infinity, and we encounter a negative cycle. So that is negative infinity. Similarly, if we want to reconstruct the paths, this is how we're going to do it. Don't be scared by any of this, it's just text being printed on the screen. So here, I want to reconstruct the shortest path between all pairs of nodes. So I loop through all pairs of nodes i and j. And then on the server, again, I call reconstruct shortest path from itj. And that returns a list of nodes. And here, I just print three different options depending on when I get back. If the path is no, then there does not exist. Or rather, sorry, there exists an infinite number of solutions. If the path has zero length, there is no solution. And otherwise, I just do a
2:23:47
pretty formatting of the output. And this is what that would look like. So just prints what the path would be between all pairs of nodes. So for instance, the shortest path from node to our node zero to no two in our graph, goes through nodes, 01, and two, and it does, it just prints all this information for all nodes in our graph, which is really useful. Okay, so what is this Floyd warshall solver actually doing and that's what we're going to look at right now. So inside that class, we have for instance variables, and the number of nodes in our adjacency matrix, a boolean value called solve, which just tracks whether we've solved the all pair shortest path problem or not our dp matrix, and a next matrix which is used to reconstruct the paths, and, oh, there's also this constant, which I just initialize to minus one so we can identify when we've reached naked cycles. Okay, so looking at the constructor, you just pass in the input adjacency matrix, and then I do some initialization.
2:25:09
So simply allocate memory for our matrices that we're going to need, and then populate the DP matrix with whatever is given to us for our input. And also make sure to initialize the next matrix to contain j as the next value going from i to j. And that's all you need to do for the setup, nothing too complicated. Let's look at some of the methods that are provided in this class. The first one is get all pair shortest path matrix, which is the first method we called. And what that does is it looks if we've solved the all pair shortest path problem already, and if not a call is the solver. The reason I do this is so that if we want to get the all pairs shortest path matrix, multiple times that we don't want to run the solve method several times. So the solve method is what actually solves or rather executes the Floyd warshall algorithm. And here's what we're going to do to compute all pairs of shortest paths. First, we iterate through k on the exterior loop. And then we
2:26:28
loop through all pairs of nodes, and then we check for our condition. So if the path going from i to k and then k back to j is less than the path from i to j, then update the value of i to j to route through that node k. And a while doing this also update the next matrix so that we can reconstruct the path later on. So it's is now shorter to go through igk than i to j. So update the indices for ij. This next loop is if you want to identify negative cycles, identifying negative cycles means that we need to propagate the value of negative infinity throughout our graph for every part of the graph that reaches a negative cycle. So basically, if we can improve upon the already optimal solution, then we know that we are reaching a negative cycle somehow, and that that particular edge is compromised, so simply market with negative infinity. That is again one of the special constants provided by Java. Similarly update
2:27:47
the next matrix to also mark the node as being contaminated by negative cycle. But since next stores integer values, we can't give it the value negative infinity, which is a double. So give it the value minus one stored in reaches negative cycle. And once that is done, we have fully executed the Floyd warshall algorithm. And we can mark our boolean value of salt as true. Now if we look at reconstructing the shortest path, from the start node to some ending node, what we want to do is if we haven't done so already, run the solver and then initialize a value called path to an empty ArrayList. Look at if it's even possible to reach the end node from the start node. And if it's not return an empty path. Otherwise, populate the path with the current node which I noted. Note denoted as act and for each current node, check if we reach into a negative cycle. And if we do return null, because the best value or sorry, the shortest path doesn't exist, because there are an infinite number
2:29:05
of shortest paths. And also make sure to check the edge case where the last note is part of an infinite loop and simply return the shortest path. Today we're going to talk about how to develop an algorithm to find bridges and articulation points in an undirected graph from a computer science perspective. For starters, let's talk about what a bridge is a graph. bridges are sometimes also called cut edges. Essentially, if you have a graph, which is a connected component, a bridge is an edge which if removed, increases the number of connected components in the graph. The name bridge makes sense because if you think about connected components as islands, then a bridge is what separates them. So For example, in this graph below, there would be three possible bridges, which are those edges in pink, because if you remove any of them, the graph is divided into two components. And articulation point, also called a cut vertex is very similar to a bridge, and that the criteria for being
2:30:23
an articulation point is that it needs to be any node whose removal will increase the number of connected components. As an example, on this graph, there will be three articulation points, since removing any of these vertices will divide the graph in tip. As we start to think more about bridges and articulation points, we realize how important they are in graph theory. In a real world situations, bridges and articulation points often hint at bottlenecks, or vulnerabilities or weak points in a graph. Therefore, it's important to be able to quickly find and detect where these occur. We'll begin by investigating how to find bridges and then slightly modify that algorithm to also find articulation points. In the simplest way I can explain it. This is the algorithm we'll be following up to find bridges in an undirected graph. First, start at any node in the graph and begin doing a depth first search traversal labeling nodes with an increasing ID as you encounter them.
2:31:44
During the traversal, you will need to keep track of two variables. The first is the nodes ID, which I just mentioned, and the other is the nodes low link value. During the depth first search and bridges will be found. Where the idea of the node your edge is coming from is less than the low link value of the node, the edge is going to the lowest value of a node is defined as the smallest node ID reachable from the node you're currently at when doing the depth first search, including the ID of the node itself. This is an interesting concept we'll get back to later. For now, let's look at an example. Suppose we have the following graph we've been looking at and we want to find out where all the bridges are. Let's begin our depth first search on the node at the top left corner. As we do our first search, we're going to label each node with a unique ID which I will place inside the node i will also mark nodes which are visited as yellow and the nodes
2:32:57
which are blue as unvisited. So let's finish off our depth first search. So explore all nodes transforming undirected edges into directed ones and marking off edges or nodes rather as visited. So that will conclude our depth first search, I want to take a moment to think about what all the low link values would be for these notes. As a reminder, the low link value of a node is defined as the smallest ID reachable from that node. For now initialize all lowing values to be equal to each nodes ID. I placed the low link value of each node on the exterior of that node. If you inspect node one, you will notice that it's low link value should be zero because there exists a path of edges going from node one to node zero and node zero has an ID of zero. So we can update node one's low link value to zero. Similarly, node two is low link value should also be zero. Because node two to node zero there exists a path however, nodes three, four and five are already at their optimal low link value
2:34:39
because there's no other node they can reach with a lower ID. However, node sixes lowering value can be a bit to five since there is a path from node six to node five via these sequence of edges. And we can also update node seven and eights low link value by the same logic. So in general, when we look at all the directed edges we have traversed, the ones which form bridges in our graph are the ones where the ID of the node you started that is less than the low link value of the node, you're going to take a moment to think about why this is true. Let's look at where these bridges actually occur. In each instance, the idea of the node with a directed edge started at is less than the loading value of the node, it's going to rephrasing that in another way, it means there was no edge connecting back to the start of the component, which is really the definition of what a bridge is. Otherwise, if there was an edge connecting backwards to the start of the component, the
2:36:05
loading value of where the edge is pointing to, would be at least as low as the idea of the node, you started that because it would be reachable. For example, if I have an edge from node eight to node two, suddenly, the edge from node two to node five is no longer a bridge, because the loading value on node five got updated to and our bridge property highlighted in teal no longer holds. Let's take an aside and think of the time complexity of the algorithm I just presented. Right now we're doing a depth first search to label all the nodes plus v more depth first searches to find all the low length values for roughly v times v plus e in the worst case, if you're really pessimistic and careless about your programming. Luckily, however, we can do much better than this, and instead update all the loading values in one pass for a linear time complexity. Let's look at some pseudocode. on how to do this in linear time. I'll show you some actual code in the video that follows. But let's
2:37:31
get started. In the global or class scope, I define three variables. The first is ID, which I use to label each node with a unique ID number, then I have an undirected graph G. The last is n, which is the number of nodes in the graph. Following the top level variables are three arrays, which tracked information about each node in the graph, index i in each of these arrays represents node i in the graph. So the first array tracks the ID of node i. The second array tracks the load link value of node i, and the visitor array keeps track of whether or not we have visited note I. Moving on the Find bridges function is what actually finds the bridges. In the method I iterate over all the nodes which have not yet been visited by our depth first search. This is to ensure that we find other bridges in our graph even if our graph consists of multiple connected components. Let's dive into the depth first search method which is where the real work is happening. The first
2:38:50
argument is the current node you're at, which is node i then is the parent node which I set to minus one because there is no previous node. And last is the bridges array which we are populating. So here we are in the depth first search method itself, the arguments to the method or just as I describe them to you. The first variable is at which is the current node ID, then comes parent, the previous node ID, and the array bridges, which stores pairs of nodes which form bridges in a flat rate. In the first three lines of the method, I simply do some housekeeping stuff which is mark the current node as visited increment the ID value variable and assign the current node to have a default ID and low land value. Then we get into the actual depth first search traversal bit. So we iterate over each edge from the node we're at and attempt to go to To each node, which I've labeled two, since this is an undirected graph, there is bound to be an edge that directly returns to the
2:40:12
node we were just previously at, which is the parent node, which we want to avoid doing. So we continue on those cases. If the next node we're going to is not visited, then we recursively call the depth first search method. The two key lines in this method are the main functions which differ ever so slightly, the first one happens on the callback, and is what propagates the low link values, while the second one is when you try to visit an already visited node, which has a chance of having a lower ID than your current low link value. Then the last bit just checks if our bridge condition is met, and appends a pair of node IDs to the bridges array. All right, now let's look at an example of all this in action. Suppose we have the following graph again, and we start our depth first search somewhere. Let's start at node zero and explore from there. So now is the first instance of something interesting happening, we're trying to visit an already visited node. Since node
2:41:34
two is able to reach node zero from where it is, we can update its loading value. And that was the second main statement executing. Continuing on our depth first search, which takes us downward. Now we get to explore the other branch we have not visited. Again, we have in an edge which reaches out to find a node with the lower ID, so we need to update our loling value for the current node, which is node eight. Now we can update node sevens loling value to five, on the callback of the death for search method. This is an instance of the first main function actually doing something just to put everything into context. The red box is the line which was just invoked. And now that statement, we just saw, it gets executed for every node on the call back all the way back to the root node. And now we have the same result as before, but we did it with just one pass. So again, here are all the bridges that we found.
2:43:14
Perfect. Now let's move away from bridges and started discussing how we can find articulation points by modifying the algorithm for bridges. A first simple observation we can make about articulation points is that on a connected component with three or more vertices, if an edge UV is a bridge, then either u or V is an articulation point. This is a good starting point because it allows us to easily find where articulation points occur. For example, consider the following graph, you will notice that there is a bridge between nodes zero and one, meaning that either node zero or node one is an articulation point. Unfortunately, this condition is not sufficient to capture all articulation points. There exists cases where there is an articulation point, but there is no bridge nearby. For example, in the following graph, node two is an articulation point because its removal would cause the graph to split into two components. So the new question is, when do these cases occur?
2:44:37
And the short answer is that it has to do with cycles in the graph. To understand why, let's look at an example. Suppose you're traversing a graph and eventually, you somehow arrive a node zero. Initially, suppose node zero has a low link value also zero and like in any depth, Research, you would continue on to explore the graph. And eventually, if you ever encountered the node that started the cycle with an edge, its ID gets propagated throughout the cycle during the call back. So the depth first search. This is the case because we're reassigning the new loling value to equal the men of the current loading value and the ID of the node we were just visiting. You see now that node five has a loading value of zero, acquired from the ID of node zero. This gets spread or propagated as I like to say, throughout the cycle. Now, what you'll notice is that the ID of the node you started that is equal to the loading value of where it's going to this indicates that there is a cycle. What is key
2:46:03
here is that the presence of a cycle implies that the node is an articulation point. This is because a cycle and a graph corresponds to a strongly connected component. and removing the node which started the cycle, who is also connected to another component will sever the graph in two. However, there's just one exception to this. And this is when the starting node you choose has either no outgoing edges, or as part of a cycle and only has one outgoing edge. This is because either the node is a singleton standalone node. That is the case with zero outgoing edges, or the notice trapped in a cycle where it only has one outgoing edge. To be an articulation point, you need to have more than one outgoing edge. For example, in the graph on the right, we start a node zero the green node and is not an articulation point, despite our condition of the ID equaling the low link value. However, as soon as we add another edge to our starting node, it becomes an articulation point. So this is
2:47:23
something to watch out for and is unique to the starting note. Let's now take a quick look at the changes we need to do to our finding bridges algorithm to find articulation points. To begin with, we'll need a way to track the number of outcoming edges, the storing node has so I define a new variable called out edge count. Next I define a Boolean array called is art, which has true or false depending on whether or not note i is an articulation point. Ultimately, this will be the return value of the find art points function. In the body of the find art points function, I reset the edge count variable for every connected component. And after the depth first search mark, the starting node is either an articulation point or not based on how many outcoming edges were found. Inside the depth first search method, all I added was an if statement to increment the number of outcoming edges from the starting node. Besides that, I added the equals case to drag articulation
2:48:38
points found via cycles and kept the less than keys to find articulation points found via bridges. In a real implementation, you can merge these two if statements into a single clause. However, I want to distinguish finding articulation points from bridges via those from cycles. In today's video, we're going to look at the algorithm to find articulation points in bridges, but this time with actual source code. All right, here we are in the source code find bridges, we will look at the source code to find articulation points shortly. So this source code is written in the Java programming language. And here I have a class which will find all the bridges and an undirected graph stored as an adjacency list. But before I get into the details of the code actually want to show you how the code works and how we're supposed to use it. So this is the main method that will set up the graph. But before we even do that, I'm just going to scroll down here and look at
2:49:45
some of the methods used to actually create the graph and make something useful. So this first method will create a graph with n nodes. So I create a list of lists. type integer, which is basically an adjacency list with directed edges. So all I do is I create a new ArrayList. And then fill that list of lists with empty lists, and then return the graph. That's our graph for now. And then later on, what we'll do is we'll call this add edges method to add directed edges into the graph. So you see, first we add an edge from a node to a node and then to that node, from that node, the naming is a little confusing from into, I use from to mean the the node, the edge starts out and to to be the node the edges going to. So in this example, I have a graph with nine nodes. So I initialize n to be nine, then I create the graph and then add all my edges, you will notice that this graph is actually the graph from the slides in the last video. And then what we're going to do is we're going
2:51:09
to pass this graph and the number of nodes into the class above, which is going to be our solver. And then the solver is going to be able to find all the bridges and return all the bridges as a list of integers. Then once you have this list of bridges, and bridges are going to be stored as pairs. So every two integers that are adjacent and, and pairs are going to be bridges. So I pull those out, and I print them, and this is the result you would expect for this graph. Alright, great. Now you're wondering how does the magic happening here. So let's scroll up to the constructor. And, actually, let's look at the instance variables. So we have n, which is the number of nodes in the graph, ID, which is that ID number to label each node. So we're gonna give each node A unique ID. And we need to keep track of well, what was the last ID, then I have two arrays, which track information about the nodes. So low is for the low link values and IDs is to track the ID of each
2:52:32
node, we gave a node with the ID variable, then just a Boolean array to track whether or not the node was visited. And finally, the graph. So in the constructor, of course, get the graph and the number of nodes, it checks some conditions to make sure the graph is legit. Okay, so now we've constructed the object, or the solver object. And the method we're interested in is find the bridges. So the find bridges just initializes all of our variables. So set ID to be zero, initialize or allocate some memory for the low link values and the ID values and the visited array. It's good practice not to do this work into the constructor, just because if you just create a bunch of these objects, but never use them, you might surprise the person initializing the object, why they're having so much memory usage, then initialize the bridges array to be initially empty. And then we pass that into the depth for search method. It gets populated and then returned afterwards. So
2:53:46
for each node, or node ID right now, loop through all the nodes. And if that node hasn't been visited, yet started depth first search on that note, and called depth first search method with eyes The first argument so the current node minus one for the parent, and then pass in the bridges array. So some housekeeping stuff, like any usual depth first search, visit the node, and then we're going to do is we're going to initialize the load link value, and the ID of that node to just be a unique ID, which we increment. All right, then we visit from from the current node, all the nodes, we can reach and skip, skip the node that we were just at. So that is the parent node. So we don't want to do our depth first search and then immediately returned to the node we just visited. So continue on those cases. And we'll do this because we have an undirected graph, remember. So if you haven't visited the node yet, then recursively call our depth first search method and keep
2:54:58
probing While if you have, if you're trying to visit a node you've already visited, then you want to take the minimum of the current link value and the ID of the node you're going to. Otherwise, on the callback of depth first search method is the other low link command statement, which differs from this one slightly in that we have, we're taking the minimum now not of the idea of the node, but the low link of the other node. And, as you saw in the slides, the condition for bridge is if the ID of the node we're at is less than the low link of the node, we're going to this means we have a bridge and removing that bridge will cause the number of connected components to increase. So append both at and two, which are the node IDs of the bridge, and put them in the bridges array, and fill that up, and then eventually return that down here. So that is all for bridges. Now let's look at articulation points, which is really almost the same algorithm. So if we look at this,
2:56:15
the only thing that's really different is we have a variable to track the number of outcoming edges from the start node or what I call the root node in this script. And other than that, differences are that we have another Boolean array called his articulation point instead of the bridges array to track bridges. And that we have to reset the number of upcoming edges for every depth first search we do. That makes sense. What else is different? Oh, yes, we have a less than or less than or equal to, as opposed to just less than two track cycles as well and mark off those as articulation points. And I think those are the major differences for didn't forget anything between articulation points and bridges. Oh, of course, we have to count the number of upcoming edges from the root. That's pretty important. And here's the same graph as before, but instead of printing bridges, it prints articulation points. So some very subtle differences between finding articulation points in bridges,
2:57:28
but still very important ones. Today, I want to talk about a fascinating topic, and that is strongly connected components, and how we can use Tarzan's algorithm to find them. So what are strongly connected components or es CCS? I like to think of them as self contained cycles within a directed graph, where for every vertex in a given cycle, you can reach every other vertex in the same cycle. For example, in the graph below, there are four strongly connected components. I've outlined them here in different colors. If you inspect each strongly connected component, you'll notice that each has its own self contained cycle and that for each component, there's no way to find a path that leaves a component and comes back. Because of that property, we can be sure that strongly connected components are unique within a directed graph. To understand Tarzan's strongly connected components algorithm, we're going to need to understand the concept of a low link value. Simply put, a low value
2:58:43
is the smallest node ID reachable from that node including itself. For that, to make sense, we're going to need to label the nodes in our graph using a depth first search. Suppose we start at the top left corner and label that node with an ID of zero. Now we continue exploring that graph until we visit all the edges and have labeled all the notes. Alright, now that we're done labeling the nodes inspect the graph and try and determine the low link value of each node. Again the low link value of a node is the smallest node ID reachable from that node including itself. For example, the loading value of node one should be zero since node zero is reachable from node one via some series of edges. Similarly, node for us low link value should be three since node three is the lowest node that is reachable from note four. So if we assign all the loading values, we get the following setup. From this view, you realize that all nodes which have the same loading value Do
3:00:00
you belong to the same strongly connected component? If I now assign colors to each strongly connected component, we can clearly see that for each component, all the low end values are the same. This seems too easy, right? Well, you're not wrong, there is a catch. The flaw with this technique is that it is highly dependent on the traversal order of the depth first search, which for our purposes, is at random. For instance, in the same graph, I rearranged the note IDs, as though the depth first search started at the bottom middle node. In such an event, the loling values will be incorrect. In this specific case, all the low link values are the same. But there clearly are multiple strongly connected components. So what is going on? Well, what's happening is that the link values are highly dependent on the order in which the nodes are explored in our depth first search. So we might not end up with a correct arrangement of node IDs for our loling values to tell
3:01:13
us which nodes are in which strongly connected component. This is where Tarzan's algorithm kicks in with its stack invariant to prevent strongly connected components from interfering with each other's low link values. So to cope with a random traversal order of the depth first search, Tarzan's algorithm maintains a set often as a stack of valid nodes from which to update low link values from how the stack works is that nodes are added to the stack as nodes are explored for the first time, and nodes are removed from the stack each time a strongly connected component is found. Taking a step back if the variables u and v are nodes in our graph, and we are currently exploring No Do you then our new low link update condition is that to update node use loading value to node V's low link value, there has to be a path of edges from u to v and node v must be on the stack. Another small difference we're going to make to finding the correct loading values is that instead
3:02:33
of finding all the loading values after the fact, we're going to update them as we do our depth first search on the fly, if you will. This will allow us to obtain a linear time complexity. We'll be doing an example in the following slides. But this is Tarzan's algorithm nutshell. Start out and mark each node as unvisited start the depth first search somewhere and don't stop until all the nodes are visited. Upon visiting a node, assign it an ID and a low link value. Additionally, also mark the node as visited and add it to the scene stack. On the depth first search callback after the recursion comes back. If the previous node is on a stack than men, the current nodes is low link value with the last node is low and value. This is essentially what will allow loling values to propagate throughout cycles. After visiting all nodes neighbors, if the current nodes started the strongly connected component, then pop of all nodes from the stack which are in the strongly connected
3:03:45
component. You know, a node started a strongly connected component if its ID is equal to its loling value. I'll let you think about that a bit more, and it'll start making sense. Let's do an example. I'm going to mark unvisited nodes as blue nodes for which the depth first search is still exploring some neighbors as orange and nodes, which the depth first search has explored all of its neighbors as gray. Note that if a node is orange, or gray, then it is on the stack and we can update its loading value. I will also be tracking the nodes which are on the stack in the left column. So keep your eyes peeled on that as well. So let's start our depth first search. So just randomly pick a node and start there. as we explore unvisited nodes give each node an ID and a low link value equal to the ID. So now we're at node two and our only option is to now visit node zero. Since node zero is already visited, we don't want to visit it again. So now we backtrack. All the backtracking.
3:05:02
Since node zero is on the stack, we take the minimum of the current nodes, low link value and node zeros low link value. Similarly, now min, the low link value of the node we were just at, which is node one with node two. And also the same for node zero. Upon returning back to node zero, we realize that we've actually finished a strongly connected component. Since we visited all the neighbors have node zero and its ID is equal to its low link value. This means we need to remove all the nodes associated with a strongly connected component from the stack. However, we're not done exploring the graph, so pick another node at random. Let's start at node three. And go right. Now, our only option is to go down. Now we're at node five, let's take the edge to node zero. So node zero is already visited. So we can't go there. On the callback, we notice that node zero is not on the stack at the moment. So we can't min node five is loling value against node zero. This is actually
3:06:27
very, very good, because if we did, then we would contaminate the strongly connected component node five as part of with a lower low link value, which node zero has to offer. So let's go to node six. So now we have three edges to choose from. Let's take the one on the right, node two is not on stack. So don't men with its low like value. Now let's take the left edge to node four, node four is on the stack. So we can make this low link value, giving node six also a low link value of four that the last edge we need to visit is the one going to node zero. This is a situation where node zero is not on the stack, so we can't min with its low link value. On the callback node five can min with node six is low and value because it is on the stack. Similarly, for node four. Coming back to node four, we've visited all its neighbors and its ID is equal to its lowest value. So it marks the start of a strongly connected component. So we now have to remove all associated nodes
3:07:42
in this strongly connected component from the stack, these would be all of the purple nodes. Now coming back to node three, we cannot min its loling value with node four, because we just removed node four from the stack. You will also notice that node threes ID is equal to its loling value. So it should be the start of a strongly connected component. However, we have not finished visiting all of node threes neighbors, so we cannot make that assessment just yet. Now see the downward edge to visit node seven. Now take the edge to node five. On the callback, notice that node five is not in the stack, so we don't mean with its low link value. Now up to node three. On the callback, we can min with no threes low link since node three is on the stack. Also man with node seven. So now we've finished with the last strongly connected component, all we need to do is remove all associated nodes from the stack. And that's how tyrosianse algorithm works to find a strongly connected
3:09:02
components. Very beautiful, isn't it? Let's look at some pseudocode. For how this works, I think it will solidify your understanding. To get started in the global or class scope, I define a few variables that we'll need. The first is a constant to represent unvisited nodes, then comes n the number of nodes in the graph, and G an adjacency list of directed edges. Both n and g are inputs to this algorithm. Then comes two variables ID to give each node an ID and s cc count to track the number of strongly connected components. After I define a few arrays which store auxilary information about the nodes not graph. The first array is IDs which As the ID of each node, then is low to store the loling values. And finally on stack to track whether or not a node is on the stack, finally is the stack data structure itself, which should at minimum support, push and pop operations. Inside the find es CCS method. The first thing I do is assign the ID of each node to be unvisited. The IDs array
3:10:31
will be serving to track whether or not a node has been visited, as well as what a nodes ID is. In the following loop, I iterate through all the nodes in the graph. There I start a depth first search on node i, if node AI has not yet been visited, at the end, I return the array lo an array of Boolean values, which will be the final output of the algorithm. Now let's look at what's happening inside the depth first search method which is really where all the magic happens. So this is the inside of the depth first search method. The input argument to the depth first search method is a variable called at which I use to denote the ID of the node we are currently at. On the first three lines, I do some housekeeping stuff, which is add the current node to the stack, mark the current node as being on the stack, and give an ID and a little link value to the current note thing comes to the part where I visit all the neighbors of the current node. To do this, I reach into our graph store
3:11:42
as an adjacency list and loop over a variable called two which represents the ID of the node we're going to the next line says that if the node we're going to is unvisited, then visit ID. Remember, the IDS array tracks the ID of note I, but also whether or not node AI has been visited. This next slide is very important. In fact, it's probably the most important line on the slide. The first thing to notice is that this line happens after the recursive call to the depth first search method, meaning that this line gets called on the call back from the depth first search line says that if the node we just came from is on stack, than men, the current loling value with a node we were just at this is what allows the loling values to propagate throughout a cycle. So after we finish the for loop that visited all the neighbors of the current node, we need to check if we're at the start of a strongly connected component. To check if we're at the start of a strongly
3:12:54
connected component check if the ID of the current node is equal to the low link value for that node. After we have identified that we're at the beginning of a completed strongly connected component, pop off all the nodes inside the stripe connected component from the stack. As we're popping nodes from the stack also mark off nodes as no longer being on stack. One more critical thing we need to do while we're removing nodes from our stack is make sure that all nodes which are part of the same strongly connected component have the same ID. So here I just assigned each note have the same ID as the ID of the node which started the strongly connected component. Last things are to start popping off nodes from the stack once we reach the start of the strongly connected component, and also increment the strongly connected component count. If you want to track the number of connected components that were found. Today, we will be looking over some source
3:13:57
code for Tarzan's strongly connected components algorithm. Here we are in the source code for Tarzan's algorithm to find strongly connected components. You'll notice that this source code is written in the Java programming language. So to get started, let's have a look at the constructor for the class. And you'll notice that it takes a graph as an adjacency list as an argument. But before we get into the details of this actual algorithm, I want to show you how the algorithm actually works in practice if you're going to execute it. So if we look at the main method, you'll notice that here is how the algorithm is meant to be used. You set up the graph and then you run the solver. So to begin with, you declare a variable called n which is the number of nodes that are going to be in your graph. Then you create the graph. So this initializes, the adjacency list for n nodes. If we look at that Create graph method up here, all the does is it initializes, the adjacency list,
3:15:05
and then populates that with empty lists, so that we can be ready to add edges to our directed graph. So if you want to add an edge to the graph, then you would call this method, give it the graph, give it the directed edge. So from a node to another node, and then it will add that edge to the graph. So I believe this graph is the one from the slides, the very last graph, if I recall correctly. So to actually find the strongly connected components, you create an object of the solver, you give it the graph, and then you run the solver on the graph. So this is what actually finds the strongly connected components. And this will return the the array of low link values, then what I do is I dump all of these inside a multi map so we can know for each connected component, which are the nodes associated with that connected component. And then all I do is I print out which groups which nodes are part of. So you notice that I print that
3:16:21
there are three connected components. And here are the nodes and what connected components they belong to. So that's how you use the algorithm. Let's see what it's doing. So we already went over the constructor, which passes in the graph extracts the size of the graph, and caches the adjacency list. as other instance variables, we have a boolean variable with tracks whether or not we have already solved the problem, then two variables to count the number of strongly connected components and assign an ID to each node, an array to track whether or not a node is on the stack, and then two integer arrays to track the ID of each node and the low link values of each node. And finally, a stack. So if we look at the SEC count method, it runs the solver if has not yet been solved and simply returns the number of strongly connected components. The get sccs method also simply runs the solver if it has not yet been run, and returns the loling values array. Now let's look at the
3:17:42
solver itself. So it returns if it's already been solved, because we don't want to do more work than we need to. Inside the solve method, I initialize all our arrays, I also fill the IDS array with the unvisited token. So we can know whether or not a node has been visited or not. Recall that the IDS array keeps track of the ID of a node, but it also keeps track of whether or not a node has been visited. So iterate through each node and if node i is unvisited then start a depth first search at node i finally, mark that we have solved the strongly connected components for this graph. Inside the depth first search method, it's almost exactly like the slides. So do the housekeeping stuff, which is like push the current node on the stack, mark the current node as being on the stack, give the current node and ID and the loading value because the first time we're visiting it, then iterate over all the neighbors of this node, do a depth first search if the node we're going
3:18:58
to is unvisited on the call back check if it's on the stack, and men that's low link value with where we were just at. And back here after we've visited all the neighbors of the node, then we check if we're at the start of a strongly connected component. And if we are we want to pop off all the nodes associated with that strongly connected component which are on the stack. So I start with a first node and my condition has to pop until I return back to the start of that strongly connected component. And as I'm popping off nodes from the stack, I mark the node as no longer being on the stack. And I also assign every node part of that strongly connected components have the same ID as the node which started the strongly connected component. Just so that we know after the fact which nodes belong to it strongly connected component, finally, increment the number of strongly connected components in case we are interested in that. And that's basically intelligence
3:20:09
algorithm in a nutshell. Hello, and welcome to this tutorial on how to solve the Traveling Salesman Problem with dynamic programming. Today, we're going to look at two things. First is how to find the cost of the best tour, and then how to actually find that tour. All right, so let's get started. What is the Traveling Salesman Problem? In a nutshell, it's when you're given a list of cities and the distances between each pair of cities, and you want to find the shortest possible route that visits each city exactly once and then returns to the city of origin. In some other words, we can say that the problem is given a complete graph with weighted edges, what is the Hamiltonian cycle of minimum cost? A Hamiltonian cycle is simply a path which visits each node exactly once. In practice, you will probably want to represent whatever graph you have as an adjacency matrix for simplicity, if an edge between two nodes does not exist, simply set the edges value to be
3:21:26
positive infinity. So in the graph I had, you can see that one optimal tour consists of going from A to D to C to B, and then finally, back to a, with a minimum cost of nine. Note that it is entirely possible that there are many possible valid optimal tours, but they will all have the same minimum cost. As it turns out, solving the Traveling Salesman Problem is extremely difficult. In fact, the problem has been proven to be NP complete, meaning it's very difficult to find an optimal solution for large inputs. However, numerous approximation algorithms exists, if you want to get an algorithm that runs very quickly, even for large inputs. So the brute force way to solve this problem is to actually compute all possible tours. And this means we have to try all permutation of node orderings, which will take big O of n factorial time, which is very slow. But as you can see, I've listed all the permutation of nodes and highlighted the ones which yield the optimal solution.
3:22:47
The dynamic programming solution we're going to develop today is able to improve on this naive approach, by reducing the complexity to big O of n squared times to the end. At first glance, this may not seem like a substantial improvement. However, it now makes graphs with roughly 23 nodes give or take feasible for modern home computers. Here's a table of n factorial versus n squared to the N. At first, you notice that n factorial is optimal for small numbers. But this quickly changes favor to n squared to the n, which can give a significant improvement over n factorial. You can already see that how large the numbers get for n factorial when we hit n equals 15 versus the n squared to the N. All right, time to talk about how to solve this problem using dynamic programming. The main idea is going to be to compute the optimal solution for paths of length n, we will have to reuse information from paths of length
3:24:04
and minus one. But before we get started, there's some setup information we need to talk about. The first thing we're going to need to do is pick a starting node s, it doesn't matter which notice picked, just make sure that this nodes index is between zero and n non inclusive. Suppose we have this graph with four nodes, and we choose our starting node to be node zero. The next thing we need to do is store the optimal value from s the starting node to every other node. This will solve the Traveling Salesman Problem for all paths with exactly two notes. The optimal value for paths with two nodes is given in the input through the adjacency matrix. And this is all the setup we need to do. Visually, if you want to look at it, we can see that we store the value from zero to one, zero to two, and finally zero to three. In the last slide, I talked about storing the solution for n equals two. But what is it we really need to store, there are two key things. The
3:25:31
first is obvious. And that's the set of visited nodes and the partially completed tour. The other is the index of the last visited node in the path. For each partially completed tour, we need to save which node was the last node we were on so that we can continue extending that partially completed Tor. From that node we were on and not from some other node. This is very important. So together these two things, the set of visited nodes, and the index of the last visit node forum, what I call the dynamic programming state. Since there are n possible last nodes, and to the power of n node subsets, our storage space is bounded by big O of n times to the n. An issue we're going to face when trying to store the DP state is representing the set of visited nodes. And the way and I mean, the way to do this is to use a single 32 bit integer. The main idea is that if the eighth node has been visited, we flip on the eighth bit to a one in the binary representation of the integer. The
3:26:57
advantage to this representation is that a 32 bit integer is compact, quick and allows for easy caching in a memo table. For example, on the leftmost graph, we have visited the zeroeth and first nodes, so the binary representation is 0011, if the least significant bit is on the right, similarly, the binary representation of the middle graph is 1001, or just the number nine in decimal since nodes zero and three have been visited. Now, suppose we're trying to expand on our previous state. One particular instance of a two node partial tour is shown below. What we want to do from our last node, which in this graph is no three is expand to visit all other unvisited nodes. These are the gray nodes one and two, to make our partial tour a little longer, with three notes. For this particular stage, we were able to generate an additional two states. But we would also need to do this for all states with two nodes,
3:28:19
not just this one with zero, and three. In total, this process would result in six new states four partial tours with three nodes. This process continues with gradually longer and longer paths until all paths are of mine. And the last thing we need to do to wrap up the Traveling Salesman Problem is to reconnect the tour to the designated starting note s. To do this loop over the N state in the memo table for all possible end positions, excluding the start node, and minimize the lookup value plus the cost of going back to s. Note that the end state is the one where the binary representation is composed of all ones, meaning each node has been visited. It's finally time to look at some pseudocode. For the Traveling Salesman Problem. Just a heads up to everyone who's still a beginner. The following slides make use of advanced bit manipulation techniques. So make sure you're comfortable with how binary shifts ands ORS and x ORS work. Here's the function that solves the Traveling Salesman
3:29:43
Problem. It takes two inputs. The first is a two dimensional adjacency matrix representing the input graph and s the index of the starting node. The first thing we do Get the size of the matrix and stored in a variable called n, which tells us how many nodes there are. Then we initialize the two dimensional memo table, the table should have size n by n to the power of n, I recommend filling the table with null values, so that programmatic errors, throw runtime exceptions. Then we're going to call four functions set up, solve, find min cost and find optimal tour. Let's begin by looking at what happens inside the setup method. The setup method is very easy, it simply does what I illustrated a few slides ago. by storing the optimal value from the start node to every other node, you loop through each node skipping over the start node. And then you cache the optimal value from S to AI, which can be found in the distance matrix. The DB state you store is the end node as
3:31:08
I and the mask with bits s and I set to one, hence the double bit shift. Visually, the green node is the start node and the orange node is node i, which changes with every iteration. You notice now that the orange node is never on top of the green node, which is why I have a continue statement to skip that case. Now let's look at how the solve method works. The solid method is by far the most complicated, but I've broken that down to be easy to understand. The first line in the method loops over r equals three up to n inclusive. Think of R as the number of nodes in a partial tour. So we're increasing this number one at a time. The next line says for a subset in combinations, the combinations function generates all bit sets of size and with exactly our bits set to one. For example, as seen in the comments. When calling the combinations function with R equals three and n equals four, we get four
3:32:30
different bits sets, each distinct and with three ones turned on. These are meant to represent a subset of visited nodes. Moving on, notice that I enforce the node s to be part of the generated subset. Otherwise, the subset of nodes is not valid since it could not have started at our designated starting node. Notice that this if statement calls the not in function defined at the bottom of the slide. All it does is it checks if if the bit in the subset is a zero. Then we loop over a variable called next, which represents the index of the next node. The next node must be part of the current subset. This may sound strange, but know that the subset variable generated by the combinations function has a bit which is meant for the next node. This is why the variable state on the next line represents the subset excluding the next node. This is so we can look up in our memo table to figure out what the best partial tour value
3:33:55
is when the next node was not yet in a subset. Being able to look back and reuse parts of other partially completed tours is essential to the dynamic programming aspect of this algorithm. The following variable to consider is E short for end node. Because I ran out of room this variable is quite important because while the next node is temporarily fixed in the scope of the inner loop, we try all possible end nodes of the current subset and try to see which end node best optimizes this partial tour. Of course, the end node cannot be any of the start node, the next node or not be part of their current subset that we're considering. So we skip all those possibilities. So we compute the new distance and compare it to the minimum distance. If the new Distance is better than the minimum distance, then we update the best minimum distance. afterwards. Once we've considered all possible end nodes to connect to the next node, we store the
3:35:13
best partial tour in the memo table. And this concludes the solve method. The only unanswered question in this slide is how the combinations method works. And I do not mean to leave this unanswered. So let's see how this gets done. This method is actually far simpler than you might imagine, for what it does. What the first combinations method does is it fills up the subsets array using the second combinations method, and then returns that result. So what does the second the combinations method do? I already covered this in more detail in my tutorial, backtracking the power set if you want more detail, but I'll give you a quick rundown of what this recursive method does, basically, starting with the empty set, which is zero, you want to set r out of n bits to be one for all possible combinations. So you keep track of which index position you're currently at, and then try and set the bid position to a one and then keep moving forward, hoping that at the end, you have exactly our
3:36:33
bits. But if you didn't, you backtrack flip off the bit, you flipped on and then move to the next position. This is a classic backtracking problem, you might want to research. This is how you solve it. But I don't want to focus on this in this video, per se. So I want to get back the Traveling Salesman Problem. Watch my backtracking video on the power set for more guidance. If you're lost, I'll try to remember to put a link in the description. So right now in our memo table, we have the optimal value for each partial tour with a nose. So let's see how we can reuse that information to find the minimum Torah value. The trick is going to be to construct a bitmask for the end state and use that to do a lookup in our memo table. The end state is the bitmask with n bits set to one which we can obtain by doing a bit shift and then subtracting one. Then what we do is look at each end node candidate and minimize over the Tor costs by looking
3:37:50
at what's in our memo table, and the distance from the end node back to the start node s. The last method we need to look at is the find optimal tour function because what good is our algorithm if it cannot actually find you what the optimal tour is. For this method, what we're going to do to find the actual tour is work backwards from the end state and do lookups in our memo table to find the next optimal node, we will keep track of the last index we were at. And the current state which begins with all visited nodes, then we loop over I from n minus one to one which tracks the index position for the tour. to actually find the next optimal node going backwards, we're going to use a variable called index which will track the best note the inner loop loops over j which represents all possible candidates for the next node, we must ensure that j is not the starting node that is part of the state meaning it has not yet been visited. If this is the first valid iteration, the
3:39:11
variable index will be set to minus one. So sell it to J otherwise compare the optimal values of the best distances between nodes index and J and update index if node j is better. Once the optimal index is found, store that as part of the tour and flip off the bit in the state which represents the index note. Finally set the first and last nodes of the tour to be as the starting node because the tour needs to start and end. On that note, then simply return the tour. And that is how you solve the Traveling Salesman Problem with dynamic programming. Hello and welcome to This video on the Traveling Salesman Problem with dynamic programming. Today we're going to have a look at some source code. All right, here we are in the source code for the Traveling Salesman Problem with dynamic programming. This is the iterative implementation. If you look in the repository, you should see that there is also a recursive implementation if you are interested in that this implementation
3:40:26
is in the Java programming language, but you should be able to translate it pretty easily to any programming language. So let's get started. So if we want to solve this problem, we're going to have to create this object called TSB dynamic programming iterative and it has two constructors, one with a distance matrix as an input. And the other optional constructor is the distance matrix, but also with a designated starting node. So by default, I have the starting node to be zero, but you can set that to be whichever node you like. And then I simply store how many nodes are in the graph. And then check for some edge cases, I haven't supported n equals two yet, but that should be pretty trivial to do. And then just check some edge cases, make sure the matrix is square, you know, just that kind of stuff. And then I cache the start position and the distance in these instance variables. And then here are the two methods that you will be interested in the first called
3:41:47
Get a tour, and it returns a list of integers representing the optimal tour for the input graph. And this other method called get tour cost returns the minimum tour cost. And notice that they both call the solve method if the solver has not been run yet. I could call the solve method in the constructor. But that's generally considered bad practice to do work in the constructor. So I leave it up to the methods to call the solve method. Or you can explicitly call it yourself doesn't matter. So the solid method is what basically solves the traveling salesman person problem. So the first thing I do is I initialize a variable called the end state. And this is the state with all nodes visited. So all bits are set to one. Then I initialize a memo table of size and times to the end, and it takes type double. So initially, this entire table is filled with null values. And then I do an initialization step, where I add all edges
3:43:07
from the starting node to every other node, which is not start node. So this is like the first step in the slides, if you remember correctly, and then you set it equal to the value in the adjacency matrix. Then we start the phase where we're trying to create tours of path that are one a longer. So R is once again, the number of nodes in the partially completed tour. Then we loop through all subsets with our bits set produced from our combinations function, which is below. I guess I'll jump to that right now. So that's right here. And this method basically generates all the bit sets of size and where our bits are set to one. And then you can see that the result is returned in this variable called subsets. So this is the combinations method and then this calls the private combinations method down here. So ignoring this part, which is just an optimization, if r is zero, meaning we've selected exactly our elements, then we find found the ballots subset and then
3:44:35
add it to our subsets array. Otherwise, we flip on the ice bit recursively call the method and then backtrack and flip off the ice bit. Alright, so going back over here. Now we make sure that the starting node is Inside the subset, otherwise, we're not going to be able to create a valid tour. Next, Next, we loop over the variable called next, from zero to n. And the next node is going to be our next slide target nodes, the one we're trying to expand to, if you will. So we make sure that the next note is not the starting node. And we also make sure that it is in the subset produced by the combinations function. Otherwise, we're not interested in it. Then we generate the mask, which is called subset without next. And this is the the state or the partially completed tour without that next node. So we basically flip off the next node and set it to zero. And this allows us to do a lookup in our memo table later on. So we can compute the new distance. But before that, we initialize a
3:46:13
variable called min distance, which I initialize to positive infinity. And this is the variable we're trying to minimize for the next node. Then, for every possible end node, every possible end node, which is not the start node, or the end node, and is part of our subset, we calculate the new distance from the end node using the subset without next, and then from the end node to the next node. And then if that new distance is less than the global, or sorry, the just the min distance we declared up here, then just update the min distance. And finally cache that in the memo table. So this is the bulk of the algorithm right here. But we're not done yet. We still want to calculate the minimum cost, like the overall minimum cost of the optimal tour. And to do that, we simply loop from I zero to n, skipped over the starting node. And, and then do a look up in our table for that end node, I and the state and state. So we finished a tour. And the tour ended on node i and then
3:47:45
go from I, which we ended on back to the start node. So that's the tour cost. Now we just minimize over this variable and update the mentor costs, which if we go back, you can see was one of our instance variables, which had set the positive infinity. So we're minimizing this. And this is why it gets returned on the get tore cost function. All right. So this finds the minimum tour cost. And this section you see right here finds what the actual torque is, which is really useful, and does that by looking inside the the memo table at the values we've computed. So we initialize a variable called the last index, and it initialized the starting node, because that's essentially the very last node if you want, when we do the tour, we end up at the start node again. And the state is the end state. So we're working our way backwards. So we start at the end state and then we're going to slowly, I guess, reduce our tour until we're back to the starting node. So
3:49:04
So in our tour, we add that starting node. And then we're going to loop n minus one times. And this variable i is just for, for counter. So it's not, it's not used anywhere in here. So we loop n minus one times and for this index variable, so this is like the, the node we want to to go to next. So it's the best as the index of the best next node. But define that next best node, we need to look at where we were last, which is the last index and go to the next best node which is going to be j so we loop over We're all possible j nodes, if you will start j at zero and loop up to n, and then skip over when j is equal to the start or is not in the state, because we would have already visited a node otherwise. And if index is minus one, then it's the first valid node we encounter. So set index equal to J. Otherwise, look at the previous distance. So for the node at index versus the node j, and then if selecting node j gives us a smaller value, then we know we want to update index
3:50:47
to be J. And, and doing this for all of the nodes will find us the next best node going backwards, then we want to add that nodes index to the tour, and then toggle the that bit off, and then set the last index to be the current index. So we're going backwards and basically starting from a fully completed tour and like shrinking the tour down to just the starting node again. And at the very end, we want to add that starting node to the tour, and then reverse the order of the tour. This is because we're going backwards, we're starting at the end state and then working our way backwards. So our tour is in effect in reverse order. So we want to reverse the tour order. And then we can mark the solver as completed. And tour if we look up here was just a list of integers. And tour is the variable we return when we call get tour. The only thing I did not cover was this not in function, which just checks if a bit or the element was not set in subset, so you check if that bit is
3:52:24
equal to zero. Today we're going to talk about oil arian paths and circuits. From a computer science perspective. We're going to start with discussing what Euler paths and circuits are, how to determine their existence, how to find them. And lastly, we're going to look at some code to wrap things up. Let's begin with what an oil arian path is. an Euler path, also called an oil area and trail is a path of edges in a graph that visits every edge exactly once. Suppose we have the undirected graph below and we want to find an Euler return path. First off not every graph has an oil arian path this one does, but even still, we need to be careful about which node we start our path at. Suppose we begin the path at the middle rate node and decide to follow the path left Down, up up began and finally left this completes the oil arian path. However, suppose we start at the top node. What happens if we decide to find a path from this node? If we take
3:53:36
the edge going down, you'll notice that we are now stuck. We cannot go anywhere else from this node since there are no edges left to follow. More importantly, the issue is that we have unvisited edges that we still have not used or traversed. So we'll see how to resolve or rather avoid this issue altogether later so that we always find an oil arian path when we no one exists. Moving on let's talk about oil arian circuits, also called oil arian cycles and oil arian circuit is an oil layer in path which starts and ends on the same vertex. So similar to oil arian paths, not every graph has an oil arian circuit, but the following graph does. If you know your graph has an oil arian circuit, then you can begin the circuit at any note. I'm going to begin the circuit on the orange note and also end it on the orange note. And that's the full circuit if your graph does not contain an oil arian circuit, you may not be able to return to the start node or you will not
3:55:00
Be able to visit all the edges of the graph. For example, let's start another circuit starting from the same node on this slightly modified graph. So by randomly selecting edges to traverse, we weren't able to make it back to the starting node. Furthermore, we also have unvisited edges, so that's double bad. Luckily for us, we don't have to guess whether or not a graph contains an oil arian path or an oil arion circuit, we can inspect the graph we're dealing with by counting the in and out degrees of each node to determine whether or not the graph meets one of the conditions. In this table. There are four flavors of or Larian paths and circuits that we care about. And those are whether the graph is directed or undirected, and whether or not we want to find an Euler in path or an ordinary circuit. All of these variants talk about no degrees. So I want to have a quick look at that before coming back to this table. The degree of unknown
3:56:09
means different things depending on whether the graph we're dealing with is directed or undirected. In an undirected graph, the node degree is simply how many edges are attached to a particular node, the blue node in this picture has three edges attached to it. So it's degrees three in a directed graph, there are two forms have no degrees there are in degrees and out degrees. Because the edges are directed the end degree is the number of incoming edges to a node and the out degree of a node is the number of outgoing edges from that node. So in the example on the right, the end degree of the notice to while the out degree is one pretty simple. Coming back to the table, you should be able to understand the constraints required for each variant of the oil arian path and oil arian circuit problem. However, let's go over them one by one anyways, the simplest cases when we have an undirected graph and we want to find an oil layer in circuit the requirement for this
3:57:12
is that every node in the graph has an even degree. The oil arian path problem on an undirected graph is very similar, except that in addition that every vertex has an even degree you can also have exactly two vertices which have an odd degree those two vertices, if they exist, would be the start and end nodes of the oil arian path I a directed graph, you can have an Euler circuit if every vertex has an equal internet degree. This is the counterpart to the undirected graph version. The last variant is finding an Euler path on a directed graph for there to exist in over there and path on a directed graph. at most one vertex has an out degree minus and in degree, which is equal to one and at most one vertex as an indie GRI minus out degree equal to one and all other verse vertices have equal internet degrees. So it's now Quiz time, and I'm going to make sure you've been paying attention. I'm going to present to you various graphs, and you need to determine
3:58:19
whether the following graph has an oil layer in path and over there in circuit or both. So we'll start with undirected graphs, and then later move on to directed graphs. Please feel free to pause the video to think things over. So this graph has no oil arian path or circuit you can tell because there are too many nodes with an odd degree. How about this graph? Again, feel free to pause the video. This graph has an oil arian path and the green nodes represent the valid Start and End notes for the oil arian path. What about this graph? This graph has both an oil arian path and an oil arian circuit. As a side question, true or false, if a graph has an oil arian circuit, it also has an oil arian path like give you a moment to think about the answer is true. Any circuit is an oil arian path. Here's another one, are there any paths or circuits in this graph? This one is a bit of a trick question, but there are no order
3:59:44
in paths or circuits here and the additional requirement I have not yet mentioned is that when finding paths and circuits is that all vertices with nonzero degree need to belong to a single connected component and here We have two connected components. So we cannot have an overlay or in path or circuit. Now let's have a look at an example with a directed graph. Does the following graph have any or they're in paths or circuits? I'll give you a moment to think about it. Yes, this graph has both an Euler path and an Euler in circuit because all in and out degrees are equal. What about this graph? This graph has no oil arian paths or circuits. The red nodes either have too many incoming or outgoing edges for an oil arian path or circuit to exist. What about this graph, I'll give you a bit more time because there are a lot of edges. This graph only has an Euler path, but no Euler in circuit, it also has a unique start
4:01:05
and end node for the path. Note that the singleton node has no incoming or outgoing edges, so it doesn't impact whether or not we have an oil arian path. Today we're talking about how to algorithmically find oil, Larian paths and circuits on graphs. So finding oil arian paths and or they're in circuits are actually very similar problems for both directed and undirected graphs. If you have an algorithm that finds an oil arian path, finding oil arian circuit comes for free, all you need to do is feed the graph with the oil layer in circuit into the oil area and path algorithm and outcomes the oil arian circuit. For that reason. Today we'll be looking at an algorithm that finds an oil arian path on a directed graph. So the first step to finding an oil arian path is to verify that one exists, because maybe it's impossible to find an oil arian path that traverses all the edges of your graph. And it's good to know that before you actually find your ordering path. So recall
4:02:14
that for now, or they're in path to exist, at most one vertex has a degree minus in degree equal to one and at most one vertex has in degree minus out degree equal to one and all other vertices have equal in and out degrees, we're going to count the in and out degrees of each node. By looping through all the edges, we'll be needing two arrays, which I've called in and out to track the in and out degrees of each node. So for each edge, increment the integral of a node if a node has an incoming edge and increment the out degree if it has an outgoing edge, and so on for all the other edges. Once we've verified that no node has too many outgoing edges, or too many incoming edges, and there are just the right amount of Start and End nodes, we can be certain that our oil arian path exists, the next step is to find a valid starting node. Because we can't start the algorithm at any node we choose necessarily.
4:03:30
node one is the only node with exactly one extra outgoing edge, so it's our only valid starting node. Similarly, node six is the only node with exactly one extra incoming edge so it will end up being our ended node. Note that if all in and out degrees are equal, then we have an oil arian circuit. And we can choose to start the algorithm at any node which has a nonzero degree. So we have everything we need to find an oil arian path. Let's see what happens if we try and do a naive depth first search to traverse as many edges as possible until we get stuck. Let's begin at our starting note and execute a random depth first search. Let's take a write another write up, down diagonally up diagonally right. And right again, you'll notice that even though we started at the correct starting node, and that we knew in oil arian path existed, and furthermore, that we did end up at the correct end node that we still did not find the valid oil arian path since we didn't traverse all
4:04:43
the edges. So what's going on? Well, what's happening is that we're doing our depth first search wrong, we need to modify the depth first search algorithm to force the depth first search to visit all the edges of our graph to illustrate this Consider this simpler smaller graph. Suppose we start our depth first search at node zero and try to find an oil arian path. Suppose we take the edge the right, then suppose the depth first search takes us right. Again, this causes us to accidentally skip the edges going to node two and back, which we know will need to be part of the oil era and path solution. For now let's not worry about it and keep executing our depth for search. So once we get stuck, meaning the current node has no unvisited outgoing edges, we backtrack and add the current node to the solution. So four gets added to the solution and we return to the node we were just at. We are stuck again because node three has no outgoing edges that are unvisited.
4:05:49
So we add three to the front of the solution and backtrack when backtracking if the current node has any remaining unvisited edges, that is white edges, we follow any of them calling our depth first search method recursively to extend the ordering path, so we follow the edge up to node two, and then there's still another edge going downwards. So we take that one too. Now we're stuck again, because there aren't any unvisited edges anymore, what we do is we backtracking add the current node to the front of the solution. Effectively, we do this until we return to the start node and the recursion unwinds. So in summary, how we forced the depth first search to take all the edges is to keep taking unvisited edges on the recursive call back until no unvisited edges remain. Coming back to the previous example. Let's restart the algorithm. But this time, let's track the number of unvisited edges, we still have left to take at each node. In fact, we have already computed the
4:06:55
number of outgoing edges for each node in the out array, which we can reuse, we won't be needing the inner array anymore once we validated that an Euler in path exists, so we can ignore it. Let's begin at the starting node once again. Now one thing we're going to do slightly differently is that every time an edge is taken will reduce the outgoing edge count for that node. Doing this will enable us to know when a certain node has no more unvisited edges. So let's just follow the same path we had last time until we get stuck. So now we are where we were last time, but we're not going to terminate the algorithm just yet. Instead, we're going to backtrack because we're stuck and there are no more outgoing edges to take from node six. One way to know this without looking at the graph is to check whether the outer array at index six has a value of zero, and it does. So let's backtrack and add six to the front of our solution. Now we are at node four and node
4:08:09
four has remaining unvisited edges, those are the white edges, which we still need to take. So we call our depth first search method recursively and follow all the unvisited edges for note four, similar situation at node three, and node one and node two. For node two, we're going to take the edge going to the right, which brings us back to node four. But this time there are no more unvisited edges at node four. So what do we do, we backtrack and add four to the front of our solution. Now we're at node two and node two still has an unvisited edge since the outer array at index two is not equal to zero. So what we do is we follow that unvisited edge, which brings us back to node two, and node two now has no more unvisited edges. So we backtrack and add to the solution. And we're back at node two, and we backtrack now we're at node one, and backtrack from node one. Now we're at node three, and so on since all the edges have been visited, and at this point, we're
4:09:17
just going to unwind the stack and add the current note to the front of the solution. I'll let the animation play. And that's how you find an oil arian path on a graph. In terms of the time complexity required to find an oil arian path, we know that it has to be big O of E. The reason is that the calculations we're doing to compute the oil arian path are all linear in the number of edges. Think about computing the internet degrees or the depth for search both of those only take big O of a time. So the whole thing is linear. And the number of edges. And now let's have a look at some pseudocode. To find an oil arian path, let's have a look at some of the variables we're going to need. The first three here are inputs to the algorithm, which are n, the number of nodes in the graph, M, the number of edges in the graph. And lastly, g the graph itself stored as an adjacency list. Then there's the in and out arrays I
4:10:30
talked about earlier to track the in and out degrees of every node. Lastly, there's a variable called path, which is a linked list which is going to store the oil arian path solution. You can also use an array or some other data structure to store the solution. But I find that a linked list simplifies the code to actually find an oil arian path on our graph G we're going to call the find oil arian path method. The first thing we want to do is verify that an oil arian path exists. To do that, we first need to count the in and out degree of each node. And once we know that, we can verify that the graph is a good candidate for nor Larian path. So here we are looking at the methods which count the in and out degrees of each node. And verifies that Euler and path can exist. The count in and out degrees method is very simple. Simply loop over all the edges in the graph and increment the internet degree arrays for incoming and outgoing edges. The graph has Euler and path method checks
4:11:43
all the preconditions for an oil arian path we're going to keep track of the number of start nodes and n nodes that we encounter. A start node is a node with one extra outgoing edge and an end node is a node with one extra incoming edge. If at any point we encounter a node which either has more than one extra outgoing edge or more than one extra incoming edge, we know that this graph is not oil, Larian. And we can return false immediately because of symmetry I believe you only need one of these checks. But to be explicit, I put both conditions there. Next up, I check if the current node is a start node or an end node, you cannot be a start node and an end node which is why this is an else if clause. The last thing to do is check if we have a valid number of start nodes and add nodes for our path either there are no designated Start and End nodes that is the oil arian circuit case which is also an Euler path, or there are exactly one start node and one
4:12:54
and nodes. Coming back to the main method. The next step is to find that starting node and perform a depth first search to actually find the oil there in path. Let's begin with finding the starting node. We're going to start by assuming that the start node is node zero, although this will likely change in the future. Since we know that at this point, our graph is an Euler area and graph. This means that if we encounter a node with one extra outgoing edge that this node must be the unique starting node and we can return that nodes index immediately. Otherwise, we just want to ensure that we begin on a node with an outgoing edge, our default node node zero might not have an outgoing edge. In fact, this check prevents us from starting the depth first search on a singleton node, then return the start node after the loop. The depth first search method is where things start to get interesting. This depth first search method takes one argument and that is the current
4:13:59
node. We're at the while loop in the depth first search loops while the current node still has outgoing unvisited edges. It does this by looking in the outer array at the current node and checking if there are still outgoing edges. The next line selects the next unvisited outgoing edge from the current node from our adjacency list. It also decrements the number of outgoing unvisited edges from the current node. So if you haven't caught on already, the outer array is currently serving two purposes. one purpose is to track whether or not there are still outgoing edges and the other is to index into the adjacency list to select the next outgoing edge. This assumes the adjacency list stores edges in a data structure that is indexable and constant time just like me, right? If not, say you're using an adjacency list composed of linked lists, then you can use an iterator to iterate over For all the edges once we've selected the next unvisited edge, we visit that edge by
4:15:06
calling the depth first search method recursively. Once we exit the loop, append the current node to the front of the solution. Returning back to the main method. The last thing we need to do is check that we have actually found the correct number of edges for an oil arian path. It might be the case that our graph is disconnected and we found an oil arian path on one of the many connected components of our graph, in which case it's impossible to actually have an oil arian path so we return null in that case, otherwise, we simply return our path Today we're going to look at some source code for the oil arian path algorithm. Awesome. Here we are in the source code for the oil arian path algorithm. This code works by first instantiating this oil Larian path solver class and then calling a method to fetch the oil arian path itself should it exist. Let's begin by taking a look at the class constructor in the constructor, what you do is you pass in a directed graph to
4:16:17
the algorithm as input and then the constructor verifies that you actually passed in a graph that's not know and it also initializes a few variables including n the number of nodes in the graph and the path linked list. Before we go too far. Let's have a look at some of the instance variables for this class. We already talked about n the number of nodes in the graph. Next we have edge count which we will compute dynamically from the input graph followed by in and out which are integer arrays to track the in and out degree of each node. Then we have path which is the oil arian path solution, as well as a reference to the input graph. So once you create an instance of this class, there's only one public method and that's get or Larian path, which does exactly what it says it will return to you an integer path consisting of the nodes you need to traverse to get a valid or Larian path or know if no path exists. So there's a few things that get Euler and path does which we'll cover
4:17:23
step by step. The first thing in the get Euler and path method is the setup method. So let's have a look at that first. All this method does is loop through all the edges and increment the in and out array degrees, as well as compute the number of edges in the graph, which is being tracked by the edge count variable. Back to the get Euler and path method. The next thing is to check if the edge count is zero and return null if we don't have any edges to work with. Following this I called the graph has Euler and path method which verifies that our graph actually has no relation path because most graphs don't. The graph has Euler and path method is also fairly simple. What we want to do is make sure that no node has too many outgoing edges or too many incoming edges as well as ensure that there's the correct amount of Start and End nodes for an oil arian path to exist, the variables start nodes and end nodes keep track of how many nodes have either exactly one extra outgoing edge or
4:18:37
one extra incoming edge for an Euler and path to exist, there has to be at most one start and end node. So when we're inside the for loop, we have three conditions. The first is to identify if the current node has too many incoming or outgoing edges, which mathematically means that the difference between the in and out degree or vice versa is greater than one. In this case return false because the path is impossible, there will be no oil arian path in such an event. The other conditions we care about are whether the current node might be a start node or an end node. And if it is, then we increment the start node and node counters respectively. The last step is to actually check that we have the correct number of storage nodes and n nodes and return the boolean value. Returning back to the get Euler and path method. The next thing in the algorithm is to actually find the earlier and path now that we know what exists. To do this, we find a valid starting node and
4:19:38
feed that as the first node to the depth first search method. So let's have a look at both of those. We don't want to start out or they're in path anywhere as we saw in the first video, because this doesn't ensure that we find an Euler and path even though we know one exists, the fine start node method does exactly what it sounds Like it looks for a node which is a valid starting node, meaning a node with exactly one extra outgoing edge or in the case of an oil arian circuit, just any node with an outgoing edge, it's important that we start at a node with an outgoing edge because our graph might contain Singleton nodes that have no outgoing edges, but another component in the graph might have outgoing edges, which is where we really want to start if we are to find an oil arian path. Next up is the depth first search method where things get interesting. It turns out the depth for search method is really short and could even be shorter but at the expense of readability.
4:20:41
Remember that when calling this method the first note is the starting node, which is the at variable in this method, which if you haven't guessed that yet is the current node index we're currently at. In essence, what's happening in this method is that while the current node still has unvisited edges, we're going to select the next node to explore and call the depth first search method recursively. Each time we take an edge, we decrease the number of outgoing edges for that note, which means that eventually there will be no more outgoing edges for the current node and the loop will terminate. Once this happens, we can add the current node to the front of the solution. The key realization In this method, I think, is that you have to notice that the out array is being used as both a way of determining if there are any unvisited edges left at the current node as well as an index for reaching into his adjacency list to grab the next note to visit. Let's go back up to the get oil
4:21:46
arian path method. Once we've finished executing the depth first search, the next thing to do is ensure that we found an oil arian path, it could be the case that the graph is disconnected into multiple components, in which case the correct thing to do is to return null because no oil arian path exists. Checking that the graph is disconnected is not something the graph has Euler and path method verifies. And this is intentional, because it's easier to do after running the depth first search by ensuring that the solution actually has a size equal to edge count plus one. The next thing I do before returning the solution, which is optional, is simply to empty the contents of the link list into a primitive integer array. just for convenience. I do this because it's easier for the caller to index an array than it is a linked list. The rest of this file are just helper methods for creating a directed graph and adding directed edges to the graph. I also provide two examples,
4:22:51
one from the previous slides and another that I made up, I encourage you to look them over to understand how this program works. Today we're talking about minimum spanning trees. And in particular, we're talking about prims algorithm and how it is used to find minimum spanning trees. So what is a minimum spanning tree on a weighted graph, a minimum spanning tree or just MST for short is a tree, which spans the whole graph connecting all nodes together while minimizing the total edge cost. It's important to note that your spanning tree cannot contain cycles. Otherwise, it's not a tree. Here's a weighted graph with nodes labeled zero through six with various edges of different costs. One possible minimum spanning tree is the following edges highlighted in green, whose edge costs some tonight, there's no way to connect all the nodes together and get a lower cost then this, note that even though the minimum spanning tree in this graph is unique, in general, it's possible for a
4:24:02
graph to have multiple msts of equal costs. Alright, hopefully you've been paying attention because now it's your turn. I'm going to present to you some weighted graphs, and your job is to identify any possible minimum spanning tree you can find. Let's begin with this graph. Take a moment, pause the video and find any minimum spanning tree you can. So one possible minimum spanning tree is the following with a cost of 14. Again, minimum spanning trees are not unique. So there could be another valid minimum spanning tree here, but they'll all have a cost of 14. Let's do another one. Can you find a minimum spanning tree here? I'll give you a moment. Here's one possible answer with the minimum spanning tree. Hi In green with a cost of 39. All right, one last graph, I promise. This one is a bit of a trick question. Because there is no minimum spanning tree, all the nodes must be connected on a single component for a spanning tree to exist.
4:25:22
Let's change focus and start talking about prims algorithm. prims is one of my favorite minimum spanning tree algorithms because of how simple and how intuitive it is. By nature, it's a greedy algorithm, which always selects the next best edge and adds it to the minimum spanning tree. So it works very well on dense graphs, which have a lot of edges. However, a few downsides to prims is that it's not easily parallelizable, or at least not as parallelizable as other well known minimum spanning tree algorithms. And it's slightly harder but not impossible to find the minimum spanning forest of a graph. There are two well known versions of prims I want to discuss. The first is the common the lazy version, which runs in big O of E log e. And then there's the improved eager version, which runs in big O of E log V, but requires a slightly different data structure. We're going to have a look at both, but this video is primarily going to focus on the lazy version. Let's
4:26:27
start by looking at the lazy version, just because it's slightly easier to implement. Here's the general idea, maintain a priority queue that sorts edges based on minimum edge cost. This prior queue is used to tell you which node to go to next and what edge which is used to get there. Then the algorithm begins and we start on any starting node s and Mark s as visited and iterate over all the edges of s and add them to the priority queue. From this point on, while the priority queue is not empty, and the minimum spanning tree has not been formed, dq the next best edge from the priority queue. If the dq edge is not outdated, which it could be if we visit the node that edge points to via another path before getting to the edge we just pulled. Then we want to mark the current node as visited and add the selected edge to the priority queue. If you selected a stale outdated edge, then you can simply pull again, then repeat the process of iterating over the current
4:27:35
nodes edges, adding them to the part of the queue. And while doing all this, take care not to add edges, which already point two visited notes. This will reduce the number of outdated edges in the priority queue. Let's have a look at an example. Suppose we have this weighted undirected graph, and we want to find any minimum spanning tree. An important thing to keep in mind is that while the graph above represents an undirected graph, our internal adjacency list representation has each undirected edge stored as two directed edges. So the actual internal representation typically looks something like this, which is a lot easier to work with. Along with a graph I will also be keeping track of the edges currently in the priority queue on the right, I will be representing edges as triplets containing the start node of the edge, the end node of the edge and the edge cost. Lastly, I will be coloring nodes as either blue for unvisited orange revisiting or gray for visited.
4:28:47
So let's begin prims on node zero. So iterate over all the outgoing edges and add them to the priority. The first edge we're going to add to the priority queue is the edge from zero to one with a cost of 10. Then the edge from zero to two with a cost of one, and finally the edge from zero to three with a cost of four. Now we look inside our priority queue and we pull the next most promising edge and add it to the minimum spanning tree the edge from zero to two with a cost of one has the lowest value in the priority queue. So it gets added to the minimum spanning tree. This also means that the next node we process is node two. So next we iterate through all the edges of node two and add them to the priority queue while iterating over the outgoing edges of node to realize that we may encounter edges which point to already visited notes. We do not want to add these to the party queue because they are of no use the reason we Don't include edges which
4:30:01
already point to visited nodes is that either they overlap with an edge already part of the minimum spanning tree, as is the case with the edge on the slide. Or they would introduce a cycle in the minimum spanning tree if included, which is forbidden. So the next best edge in the priority queue is the edge from two to three with a cost of two, so it gets added to the minimum spanning tree. This also means that the next node we process is node three. The same process of adding edges to the priority queue and pulling the smallest edge continues until the minimum spanning tree is complete. I'll let the animation play until something interesting happens. All right, notice that the next best edge we pull from the priority queue is an edge which already points to a visiting node node one. This means that the edge is outdated and stale, because we found a cheaper path to node one. So we can safely ignore this edge and pull again. The next edge is also stale. So let's keep pulling.
4:31:48
So what happens when we have two edges with the same cost in the priority queue, which one gets pulled first, in practice, this doesn't matter. So we can assume that edge 258 gets pulled first because it was added first. We can now start premise because the minimum spanning tree is complete. We know the minimum spanning tree is complete because the number of edges in the tree is one less than the number of nodes in the graph. This is precisely the definition of a tree. If we collapse the graph back into the undirected edge view, it becomes clear which edges are included in the minimum spanning tree. To find the cost of the minimum spanning trees simply sum up the cost of all the edges which were selected to be part of the minimum spanning tree and this totals to 20. Great, we now understand the gist of the lazy implementation of prims. Let's have a look at some pseudocode. Let me first define a few variables that we
4:33:04
will need. First is n the number of nodes and graph. The variable pq represents the priority queue data structure, it stores the edge objects based on minimum edge cost. Again, each edge object consists of a start node and node and an edge cost. Next is G which represents the graph we're working with. g represents an adjacency list of weighted edges in G every undirected edge is represented as two directed edges. As a side note, if your graph is extremely dense, meaning it has numerous edges, you should probably prefer using an adjacency matrix instead of an adjacency list for efficiency and space gains. And lastly, a visited Boolean array of size n, which keeps track of whether node AI has been visited or not. So on this slide is the whole algorithm for the lazy implementation of krems. Let's go over it one step at a time. The function takes one argument s which is the start node index and by default S is set to note zero. That I define a few more variables that will
4:34:29
need just inside this function. M is a constant representing the number of expected edges in the minimum spanning tree. Edge count is the number of edges we currently have included in the minimum spanning tree. This variable is to make sure that the tree spans the whole graph. MST cast tracks the total cost of the minimum spanning tree and finally MST edges is an array which holds edges which we have in Included in the minimum spanning tree. The first actual a bit of logic we do is add all the outgoing edges from S to the priority queue with the Add edges method. So let's look at this method and see what's going on in there. Alright, here we are at the Add edges function, the first thing I do is mark the current node as visited. Next, I iterate through all the outgoing edges of the current node. And if the destination node is unvisited add the edge to the priority queue. So that's all this method does is it goes through all the edges of a node and adds them to the priority
4:35:40
queue, if appropriate. Once we've added the first set of edges to the priority queue, the algorithm really begins and we enter a while loop while the priority queue is not empty and the minimum spanning tree is not complete, keep iterating then inside the loop, we pull the next best edge out of the priority queue and grab a reference to the destination node index. This is a node the edge is pointing at this next line is a very important it's the logic that skips adding an edge to the priority queue. If that edge points to an already visited node again, edges can become stale or outdated in the priority queue if the node they're pointing at becomes visited via another path. Next, actually add the edge to the minimum spanning tree by adding it to the MST edges array. And while adding the edge to the tree also sum over the edge costs. The last thing we want to do is call the Add edges method with the new current node. Recall that this will
4:36:47
add all the outgoing edges pointing to unvisited nodes to the priority queue. And the very last thing is we make sure that we have actually found a minimum spanning tree that spans the entire graph. And we return the edges along with the MST cost. Today we're talking about finding minimum spanning trees with prims algorithm. The lazy implementation of prims inserts edges into a priority queue. This results in each pole operation on the priority queue to be big O of log e in the eager version, we maintain the idea that instead of adding edges to the priority queue, which can later become stale that instead we should track node edge key value pairs that can easily be updated and pulled to determine the next best edge we should add to the minimum spanning tree. For this ultimate sense, there's a key realization that needs to happen. And that is for any MST with directed edges, each node is paired with exactly one of its incoming edges. That is except for the start node.
4:37:58
One way to see this is on a minimum spanning tree with multiple edges leaving a node but only ever one edge entering a node. Let's have a closer look at what I mean. Suppose we have this undirected graph. The equivalent directed version of this graph looks like this. A possible minimum spanning tree starting at node zero might be the following highlighted in green. Now notice that on this directed MST, each node is paired with exactly one edge except for the starting node. So in a sense, there seems to be a relationship we can take advantage of here, which is that each node is paired with exactly one incoming edge. In the eager version, we are trying to determine which of a nodes incoming edges we should select to include in the MST. The main difference coming from the lazy version is that instead of adding edges to a priority queue, as we iterate over the edges of a node, we're going to relax that is to update the destination nodes most promising incoming
4:39:14
edge. So you might be asking yourself the question, how are we going to efficiently update and retrieve these node edge pairs? Well, one solution is to use an index priority queue, or simply IP queue for short, which can efficiently update and pull key value pairs. You can think of an IP queue as the data structure you would get if a hash table and a priority queue had a baby together. It supports sorted key value pair updates and pull operations in a logarithmic time. Using this new approach would reduce the overall time complexity from big O of E like E to big O of E log V, since there can only Li b v node edge pairs in the IP queue. If you're interested in learning more about the index priority queue data structure and how it's implemented, I would highly recommend my dish structures video on the subject. I will link it in the description below if you need to catch up, the implementation for the eager version is slightly different and the algorithm
4:40:23
goes as follows maintain an IP queue of size v that sorts vertex edge pairs v e, based on minimum edge cost of he started the algorithm on any node s. Marchesa has visited and relax all the edges of S. Relaxing this context refers to updating the entry for node v in the IP q from V old edge to V new edge. If the new edge has a better cost than the old edge, then while the index priority queue is not empty, and a minimum spanning tree has not been formed, in dq the next best vertex edge pair v e from the IP Q, Mark note v as visited and add edge e to the MST. Lastly, relax all edges of V while making sure not to relax any edge pointing to a node which has already been visited. All right, I think it's time to see an example. Suppose we have the following weighted undirected graph and we want to find any minimum spanning tree. One thing to remember is that while we're dealing with an undirected graph, we will be internally representing it as a directed
4:41:44
graph, where each undirected edge is stored as two directed edges, I will be keeping track of all node edge key value pairs on the right and update them accordingly as the algorithm executes. So you can think of the red box as the contents of the index priority queue. Let's begin the algorithm on node zero, start by iterating over all the edges of zero and relax them during the relaxing process. Add a node edge pair to the index priority queue if it does not exist yet, otherwise update the value if the new edge has a better cost than what already exists. The first node edge pair we add is node two with the incoming edge from zero to two with a cost of zero. And similarly for the rest of zeros edges. The next best node edge pair based on the minimum edge cost is node two with the incoming edge from node zero. Now iterate through all the edges of node two and relax all edges character ignore edges pointing to already visited nodes like the one on this slide.
4:43:06
The Edge 256 has a better cost going to node five than the edge from node zero to node five with a cost of seven. So update the index party queue with this new edge I will denote IP q updates with a purple box around the edge being updated. The next best node edge pair is no three with the edge coming from node zero with a cost of five. Now iterate through all the edges of node three and relax all edges. The Edge coming from node three offers a better value. So I update the value for node one in the index party queue with the new edge. Add a new key value pair entry for node six since node six has not yet inside the index priority queue. Update the value for node five with the new better edge we just found. And from this point on, I will let the animation play please try and follow along. All right, and that's the algorithm you can see that the minimum spanning tree we found consists of the edges highlighted in green. If we collapse the graph back into its undirected
4:44:56
edge view it becomes clear which edges are included. In the minimum spanning tree, you can also get the MST cost by adding the values of all the edges in the spanning tree for a cost of nine. Let's have a look at some pseudocode. For the eager implementation of prims. You'll notice that it's almost identical to the lazy version except for a few key details which I will highlight. First is n, which is still the number of nodes in the graph, followed by the variable IP Q, which represents the index party Q. Instead of a traditional priority queue which stores node index edge object pairs edge objects are still represented as start node and node edge cost triplets with the node index being an integer. G is once again our graph adjacency list of weighted edges. Remember that in je every undirected edge is represented as two directed edges. There's also the whole story about whether we should be using an adjacency list or using an adjacency matrix to represent our graph
4:46:09
when running prims. Because we know that this can greatly impact performance. I was curious and did some analysis comparing the adjacency list versus the adjacency matrix. And the results I got were interesting. this dotted line graph shows the performance of using an adjacency list in blue versus an adjacency matrix in green, and the x axis represents the graph edge density percentage, and the y axis indicates performance measured in milliseconds. As you can see, for graphs with fewer edges, the adjacency list outperforms the adjacency matrix. But as the edge density increases, the adjacency matrix becomes the obvious choice. You may be wondering why the adjacency matrix, his performance starts to increase after the middle point where the graph starts to become more and more dense. This is an excellent question. And my guess is that the denser the graph, the fewer relaxation operations need to be performed, which is an expensive part of prims algorithm. Since the time to
4:47:19
iterate over all the edges of a node is constant, but fewer relaxation operations are needed, performance should increase as a result, but I may be wrong. Even still, the results are interesting. And the takeaway is that the graph representation you choose can greatly impact the performance of your algorithm depending on whether your graph is sparse or dense. All right, back to the pseudocode. The last variable is the visited Boolean array of size n, which tracks whether node AI has been visited or not. Now let's have a look at the actual algorithm for eager prims. In the first block, I define a few more variables that will need m the number of expected edges in the MST edge count the number of edges we currently have included in the MST, this variable is used to make sure the tree spans the whole graph, then is MST cost which tracks the total cost of our minimum spanning tree. And finally, MST edges, which is an array that holds the edges we have included in the
4:48:28
MST. After this, I call the relaxed edges at node method passing in the start node as an argument. Let's have a look at the relax edges that node method to understand what's happening in there. Alright, here we are, you'll notice that this method takes a single argument which is the current node we care about. The first thing we do is mark the current node as visited so we don't visit again in the future. Then I reach into our graph adjacency list and get all the edges going outwards from the current node. As we enter the loop and start iterating over all the outgoing edges. The first thing I do inside the loop is grab a reference to the destination node index. This is the node the edges pointing at next skip edges which point at already visited nodes. Now here's the bit where we actually relax the edge first check if the IP q contains the key with the value of the destination node. If it doesn't, then add the edge to the IP queue for the first time.
4:49:37
Otherwise try and improve the cheapest edge at desk node index with the current edge in the priority queue back inside the main method. Next up keep looping while the IP queue is not empty. And we have not yet completed the MST after extract the next best node index, edge object pair From the IP queue based on minimum edge cost, include the selected edge as part of the MST and some over the edge costs. Lastly, relax all edges of the current node and repeat until the loop breaks outside the main loop check if we have successfully created a spanning tree. This might not be the case if some of the nodes are unreachable. But assuming that that is not the case, return the MST cost and the edges which make up the spanning tree. And that concludes the pseudocode for prims algorithm. All right, here we are on the source code for prims implemented in Java. At the top here, I posted some instructions on how to download and run the script in case you want to play around with it a little bit.
4:50:51
Let's begin by taking a look at the main method right over here. The first thing I do is set up a graph we want to find the minimum spanning tree of In fact, it's the same graph we had in the slides in the previous video. To create the graph I call the helper method create empty graph and initialize an adjacency list of size and and afterwards add various undirected edges of different weights to the graph. Once the graph is set up, I create a minimum spanning tree solver and pass in the graph we just created. The solver is able to tell us whether a minimum spanning tree exists, what the cost of the MST is, as well as get all the edges, which make up the MST. The output of running the script is illustrated below right here, you can see that this particular minimum spanning tree has a class of nine and it has these six edges. If you were curious as to how the adjacency list gets initialized and how I add this to the graph, here's the code that does exactly that. Next up is a class struct
4:52:12
which represents a directed edge used in the graph. One important thing to note about this class is that it implements the comparable interface and overrides the Compare to method. This simply means that edges are able to be sorted in reference to one another. Based on the minimum edge cost. This is important for the index priority queue because it needs to know how to compare edge objects with one another to sort them. After the edge class is the minimum spanning tree solver, where all the interesting logic happens. In this class, I store a whole bunch of variables to help us out. The first two inputs are n the number of nodes in the graph, which I get from the constructor, and the graph adjacency list itself. Internally I store a Boolean solve variable to track whether we have already computed the minimum spanning tree so that we don't need to do it again. Once we've already solved the problem, the MST exists variable tells you whether a minimum
4:53:20
spanning tree was found in the input graph. It's important to note that by default, this value is false. The Boolean visited array is used to keep track of whether node AI has been visited or not. And lastly is the variable IP queue, which is short for indexed priority queue which is a data structure I have defined below. The outputs to this class include the minimum spanning tree costs and edges which make up the minimum spanning tree if one exists. After the constructor initialization there are two important methods to know about there is the get MST method for retrieving the MST edges and get MST cost which gets the spanning tree cost both of these methods work in the same manner they both call the solve method and then check whether the minimum spanning tree exists and returns a value or no therefore the real method we care about is the solve method. So let's have a look at that. The solve method is only ever executed once because we mark the solve the boolean value
4:54:41
as true the first time solve is called and the other times the method returns early. The first thing I do in the solve method is initialize some more variables and allocate some memory for the arrays we will be using. M is the expected number of edges in a minimum spanning tree And edge count is the number of edges we have currently included in the minimum spanning tree so far. Next I initialize an index the priority queue of size. And this particular index barbecue is implemented using a dare heap. So we need to provide a node degree for the underlying supporting heap structure, I arbitrarily choose the base two logarithm of the number of nodes, which actually seems to give a pretty good performance, although Typically, this is an implementation detail that you do not need to worry about. The first actual bit of logic we're going to do is call relax edges at node four, node zero, this adds the initial set of edges to the priority queue. Let's scroll down and take a closer
4:55:49
look at that method, which is right here. The first thing we do is marked the current note as visited so that we don't visit it again in the future. Then I reach into the adjacency list and get all the outgoing edges from the current node. As we enter the loop and start iterating over all the outgoing edges. The first thing I do inside the loop is grab a reference to the destination node index, this is the node that edge is pointing at next skip edges which point to already visited nodes because we know that we don't want to process those. Now here's the bit where we actually relax the edge. First check if the index priority queue contains the key with the value of the destination node. If it doesn't, then add the edge to the index priority queue for the first time. Otherwise, try and improve the cheapest edge at the destination node index with the current edge in the priority queue by calling the decrease function. So that's all for the relax edges at node method.
4:56:52
Let's scroll back up to the main implementation right here. So after we add the initial set of edges to the index priority queue, we enter a while loop and loop while the index party queue is not empty and a minimum set burning tree has not been formed inside the loop pull out the next best node index edge pair. The destination node can also be found by checking which node the directed edge we just pulled out of the queue is pointing at after that add the pulled edge to the minimum spanning tree by placing it inside the MST edges array and sum over the edge costs. Finally, relax all the edges of the new current node. This process continues and we keep pulling the next best edge and slowly start building our minimum spanning tree until eventually the loop breaks. For last thing we need to do is set the MST exists variable to check if we have actually found a minimum spanning tree. If the edge count is equal to m, then we have successfully computed a minimum spanning
4:58:01
tree Otherwise, the graph is disconnected in some way and no spanning tree exists. So that's all for the eager implementation of prims. The only piece of the puzzle that might still be unclear is how the index party queue implementation works. Here's the index priority queue implementation. However, this data structure merits a video on its own. Today we're going to start tackling the field of network flow by understanding what max flow is and in particular how we can use the Ford Fulkerson method. To find it, finding the maximum flow begins with having what's called a flow graph. This is a graph where edges have a certain maximum capacity which cannot be exceeded. edges also have a flow value, which is how many units of flow are passing through that edge. Initially, the flow is zero for all edges everywhere until we run a max flow algorithm on it. There are also two special types of nodes in the flow graph the source node and the sync node,
4:59:16
usually denoted as s and t respectively. The maximum flow problem asks with an infinite input source, how much flow can we push through the network without exceeding the capacity of any edge and it's not at all obvious how one should figure that out. maximum flow can be used in numerous situations where edges and nodes can represent any number of things. For instance, suppose the edges are roads, cars or pipes of water, wires with electric current, and so on. Each of those has a certain capacity value we can associate with the maximum flow on the other hand would represent the volume have water that can flow through the pipe. So the number of cars the roads can sustain and traffic or the net electric current that your system can sustain. Effectively, the maximum flow is a bottleneck value for the amount of traffic your network can handle. And that is going from the source to the sink. Under all those constraints. The maximum flow for this particular network is seven. And
5:00:27
you can tell because after running the maximum flow algorithm, the sum of the flows attached to the sink node is seven. Running a maximum flow algorithm is used to determine how much flow each edge should receive to achieve the overall maximum flow. Note that there might be multiple ways of achieving the maximum flow by giving each edge different flow values, but overall solutions will have the same maximum flow value. Let's dig deeper into how to find the maximum flow. To begin with, you will need a flow graph which consists of directed edges, which are also called arcs. Each directed edge has a certain capacity which can receive a certain amount of flow at all times the flow running through an edge must be less than or equal to the capacity. This intuitively makes sense. Because if we allow more flow than what the capacity permits, it means something has to go wrong. When an edge becomes overcapacity in some manner, in means that we've pushed the system past its limit. In the context
5:01:37
of edges representing pipes with water it means your pipe broke or it leaked. If your edges a wire with electric current, it means your wire literally fried or melted exploded or something bad happened to it because there was too much electric current. This is not good. So this is why we don't allow more flow than capacity. each edge in the flow graph has a certain flow and capacity specified by the two values separated by a slash adjacent to each edge. Originally, the flow through each edge is zero and the capacity is a non negative value to find the maximum flow and also the min cut as a byproduct. The Ford Fulkerson method repeatedly finds augmenting paths through the residual graph and augments the flow until no more augmenting paths can be found. So you're probably asking yourself at this moment, what is an augmenting path? What the heck is a residual graph? And what do you mean by augment the flow? All right, let me explain. We'll do them one by one.
5:02:42
an augmenting path is a path of edges in the residual graph with capacity greater than zero from the source s to the sink t in orange. Here I have highlighted a possible augmenting path. The key thing to remember about an augmenting path is that it can only flow through edges which aren't fully saturated yet. In fact, you know you've achieved the maximum flow when there are no more augmenting paths left to be found. How to actually find an augmenting path is a detail left unspecified by the Ford Fulkerson method for flexibility. For now let's assume that we're using a depth first search. Something else to know is that every augmenting path will have what I call a bottleneck value, which is the smallest edge along the path, you can find the value of the bottleneck by taking the difference between the capacity and the current flow of an edge. For this augmenting path, the bottleneck value is six, we can use the bottleneck value to argument the flow along the path. augmenting the flow
5:03:49
simply means to update the flow values of the edges along the augmenting path. Here you can see that I've increased the flow of each edge along the augmenting path by exactly six units. However, we're not done augmenting the flow, we not only need to increase the flow along the forward edges, but also decrease the flow along the backwards edges, which are called residual edges, the residual edges or the dotted edges going backwards in the reverse order of the augmenting path. The logic behind having residual edges is to undo bad choices of augmenting paths which do not lead to a maximum flow effectively, we don't know which are the best or even correct augmenting paths to take. So this mechanism enables us to freely find any augmenting paths without having to worry about whether or not we'll be able to achieve the maximum flow. It should be mentioned that residual edges become valid edges to take when finding an augmenting path in later iterations. So if we take a step
5:04:58
back, you can think of every edge in the original graph as having a residual edge with a flow and capacity of zero, which is not usually shown now that we know what residual edges are. The term residual graph simply means the graph which also contains residual edges, not just the original edges given and flow graph. So generally speaking, when I mentioned the flow graph, I usually mean the residual graph. So, here's a good question you might have at this point, the residual edges shown have a capacity of zero, aren't those forbidden? How does that work? So here's the thing. With this method of augmenting the flow, you have to think of the remaining capacity of an edge IE residual or not as the difference between the capacity and the flow of that edge. That is the difference between the capacity and the flow is the true remaining capacity for that edge. This ensures that the remaining capacity of an edge is always non negative, even if the flow can be negative. For example,
5:06:08
in the residual edges we have right now, zero minus minus six is six, so we know that all our residual edges actually have a remaining capacity of six. So the algorithm proceeds and the Ford Fulkerson method continues to repeatedly find augmenting path after augmenting path and to augment the flow until no more augmenting paths from s to t can be found the QE ideation to make at this point is that the some of the bottleneck values that we acquire with each augmenting paths will result in the maximum flow. And that's the whole premise of this algorithm. It doesn't matter so much how to find augmenting paths. But so long as you keep solving the bottleneck values which they produce, you'll find the maximum flow. So let's keep finding augmenting paths. Remember that we can only select edges whose remaining capacity is greater than zero to be part of the augmenting path. So the bottleneck for this augmenting path is four since four is the minimum of all the remaining
5:07:17
capacities along this augmenting path. Here's another augmenting path from the source to the sink, you'll notice that we're actually using one of the residual edges we created earlier in this path. You'll also notice that there are two purple edges in this slide. This is just a coincidence, since both of those edges have the same bottleneck value of six, then we argument the flow as we do. I'll let the animation play for this next one. And at the end, we can see that if we sum all our bottleneck values 646 and four, we're able to achieve the maximum flow which is 20. In terms of the time complexity, the Ford Fulkerson method derives its complexity from how we actually find those augmenting paths, which as we know is left as an unspecified detail. If you assume that finding augmenting paths are found by doing a depth first search, then the algorithm runs in a time complexity of a big O of F being the maximum flow times
5:08:30
IE the number of edges in the graph. Here's a graph where we can derive the time complexity. Suppose that the side edges have very high capacity values of 100. And the middle edge has a capacity of one, you can clearly tell that the maximum flow should be 200. Because you can run two augmenting paths with the flow values of 100 on the top and the bottom of the graph from the source to the sink. However, recall that a depth for search traversal is essentially random. So it's possible for you to pick that middle edge with a capacity of one every single time. And what that'll do is it'll limit flow, you can push from the source the sink to be one, so one is always going to be your bottleneck value, so you're never going to be able to argument the flow by more than one unit. This results in flipping back and forth between the same two alternating paths for 200 iterations, which really kills your time complexity. Luckily, much faster algorithms and better heuristics exist to
5:09:43
find the maximum flow value. One example is Edmonds Karp, which is Ford Fulkerson. But instead of using a depth first search, use a breadth first search to find the shortest augmenting path from the source to the sink in every iteration. There's also capacity scaling, which is the idea of picking larger paths. First to reduce the number of paths you need to find overall. And this turns out to work really well, at least from my empirical tests. Then there's dynex, which uses a combination of a breadth first search to first find a layered graph that guides edges towards the sink, which you then use a depth first search to actually find the augmenting paths. There's also this idea of push relabel algorithms which were differently than the algorithms we've discussed here, which try and find augmenting paths instead, push reliable algorithms maintain this concept of a pre flow if you will, to find the maximum flow of a network. Please be mindful that the time complexities posted
5:10:47
here are very pessimistic and practice running maximum flow if any of these operates much faster. So it's very hard to compare the performance of two flow algorithms solely based on the complexity today, we're taking a look at the source code for the Ford Fulkerson method implemented with a depth first search. The goal of this video is to show you how to set up the following flow graph and find the maximum flow through it. So after we run the maximum flow algorithm, we should get a graph similar to this one with flow running through some but not all of the edges and achieving the maximum flow of 23. The source code and the example I have lined up for you today can both be found on GitHub. There's a link in the description for today, I encourage you to check that out and also play along as we're going over the source code. All right, here we are in the source code written in Java. This program has three main supporting classes, an edge class, a network flow solver base,
5:11:55
and the Ford Focus in depth first search solver. However, before we get into any of those, I want to take a look at the main method where I actually use the classes above to solve the flow problem we just saw. I know a lot of people struggle setting up the flow graph, which is usually somewhat of a mystery. So I want to clear that up. The first thing I recommend you do every time you set up a flow problem is initialize three variables, and the number of nodes in your graph that is including the source and the sink nodes. And then what I recommend you do is you actually label the source and the sink nodes and assign them indices. And what I usually end up doing is I say, the source node equals index n minus one and the sink equals and minus two, the rest of the nodes in your graph should then have indices between zero and n minus three inclusive, I've always found this to be the easiest way to set up your flow graph. Next, I create the flow solver by providing the
5:12:59
three variables n, s and t as inputs to the solver so it knows how many nodes there are and which nodes are labeled the source on the sink. Then I use the solver to actually create the flow graph by adding edges with different capacities. The next step is to hook up the edges to the source, those would be the ones shown in this picture. Then I carefully hook up all the middle edges. And lastly, the edges leading into the sink. It's usually always these three steps. And for most of the time, your graph is bipartite. So the middle edges are even simpler to set up. After this I call the get max flow method on the solver which actually runs the Ford Fulkerson max flow depth first search and returns an integer value for this graph, we're expecting a maximum of 23 followed by printing the max flow, I also display all the interesting edges of the residual graph. First, I get the residual graph from the solver after executing
5:14:08
the max flow and iterate over all the edges and just display the flow on each edge. Let's actually run this program and see what the output looks like. So I just popped open a terminal. And for those of you who also have a terminal open and want to play along first, you can just clone the GitHub repo by typing git clone followed by the repo URL, which is github.com slash William fiza slash algorithms. You see that I've already cloned the repo so I don't need to do it again. Then just change directory into the algorithms folder. So the file we're working with is called the Ford Fulkerson example, dot java file. And it's in the graph theory network flow examples package. And luckily for us, it doesn't have any dependencies yet. So we can just compile it on its own with shafaq so if you type Java c followed by comm, Wm is the algorithms graph doing network flow examples. And then you find that file Ford Focus, in example, that Java, you compile it, it will produce a dot
5:15:14
class file in that directory. So you can execute it by typing Java, and then the name of the class and then pressing Enter and then you get this beautiful output. So this prints a lot of interesting information. Notably, it prints the max flow of 23, and all of the edges plus four columns. The first column represents the start and end nodes of the directed edge, then the amount of flow running through the edge, the capacity of the edge. And lastly, a boolean value indicating whether the edge is a residual edge or not, which is quite handy for debugging. So let's go back to the code. So let's scroll back up the code and take a look at the first of the three classes which is the edge class the edge class is composed of a few instance variables in particular, every edge has a start node called from and an end node called to each edge in the flow graph has a certain amount of flow and capacity, the capacity of the edge is constant and does not change the flow
5:16:22
is dynamic and adjusts. As we argument the flow when you create a new edge, it should have a start and end node plus an initial capacity, the flow defaults to zero, you might notice that the residual edge instance variable does not get initialized here or through the constructor. The reason is that I initialize the residual edge together with the forward edge and hook them up together in a helper method, which we'll see later. The next method is the is residual method, which determines whether an edge is a residual edge or not, because forward edges are not permitted to have a capacity of zero, you know an edge is residual if the capacity is zero pretty easy. There is also the remaining capacity method which can be used to determine the maximum amount of flow that we can push through this edge. This method works whether the flow is positive or negative. Next is the augment method which augments the flow for this edge
5:17:25
alone. All it does is it increases the flow on the forward edge by the bottleneck value we found along the augmenting path and it also decreases the flow along the residual edge. Last is the to string method which is responsible for displaying those nice columns we saw in the terminal. The next class we're going to take a look at is the network flow solver base. This class is a generic base for max flow solvers, which all solvers should extend to gain access to reuse variables and setup methods and so on. For example, a simple task like adding an edge to a flow graph should be the same whether the max flow algorithm is Edmonds Karp dynetics, some capacity scaling algorithm, it shouldn't matter. Therefore, it makes sense to abstract that behavior and capture it in a base class. So there are many variables in this class. The first one is in short for infinity, which is just a handy large constant that doesn't overflow. If you add numbers to it, or at least they can handle
5:18:35
having large numbers added to it, then there are the three input variables and the number of nodes in the graph is the index of the source node and T the index of the sync followed by this are two special variables I usually end up using because they greatly help boost performance. So the rationale behind using the visited token in combination with an integer array that tracks the visited state of a node is that when we are finding augmenting paths, whether via depth first search or breadth first search or whatever graph traversal method you want to use, you generally want to ensure that your augmenting path doesn't visit the same node twice. Otherwise, that could result in a cycle which we don't want. The way to check if node AI is visited is to check if the state in the visited array at index is equal to the visited token. This is super handy, because in the next iteration, when we yet again want to find another augmenting path, we can simply reset all the visited
5:19:45
states of every node simultaneously by simply incrementing. The visitor token I know it's kind of hacky, but it's super efficient and really handy to have. The alternative is actually to maintain a Boolean visitor array and you fill that with false values every time just before you find an automatic path. That's not great because it requires an additional order and work every time you want to find an augmenting path. Next is a boolean variable called solved, which indicates whether or not we have actually run the network flow solver, the solver only needs to run once, because that always yields the same result. So for example, if the user calls the get max flow method multiple times the solver only needs to run once. The next value that we have right here is the max flow variable, which is the value we're actually trying to calculate. And finally is the adjacency list representing the flow graph itself. Looking at the constructor, we require the user to
5:20:54
specify the number of nodes along with the index of the source and the sink nodes. Then inside this method, I also take the opportunity to initialize the flow graph. And as well allocate some memory for the visited array we'll be making use of later in the initialize empty flow graph method I do is initialize an empty array list of edges for each node index so that we don't get a nullpointerexception. When we try and add an edge to the graph. Talking about adding edges to the graph, let's have a look at the Add edge method. Here, we need to provide the start node and the end node of the directed edge and also provide a positive capacity for that edge. If the capacity is negative or zero, we throw an exception because that is an illegal argument, then what we do is that we actually create the forward edge and the residual edge, you'll notice that the residual edge actually has a capacity of zero, then what we do is we make the forward edges residual edge, the
5:22:03
residual edge and the residual edges residual edge, the forward edge. And finally we add them both to the flow graph. So in effect, each edge is each other's inverse. And this is exactly what we want, we want a pointer that we can simply access when we need to access and edges residual edge. The remaining methods here are simply client facing methods, they can be used to get the residual graph after the solver has been executed. And to obtain the maximum flow of the graph. You'll notice that there's also this one special method down here, which is the solve method. And this is the method that the subclass needs to override. This is the method which actually solves the network flow problem and actually pushes the flow through the network. And you can see that every time the client goes and calls on these methods like get graph or get max flow, he calls the execute method, and the execute method will run the solver. So
5:23:08
we will call this method if it hasn't been executed already. So it's got that smart logic built in. Now let's take a look at the Ford Focus in depth first, or solver which you can see actually extends the network flow based solver so we know it actually implements the solve method that we need for the get Maxwell method. Awesome. Let's let's have a look at this. So the first thing you'll notice is that this method also takes the inputs and s&t and all we do here is we call the superclass constructor in the network flow based solver which does all that nice initialization that we know about. Next is the most important method, which is that solve method I was talking to you about. And you can see that I actually overrides the method in the superclass. So in this method, you can see that I'm repeatedly calling the depth first search method returns as output the bottleneck value found along the augmenting path, I store that value as F and increase
5:24:07
the max flow by F in each iteration, because we know that the sum of the bottleneck values equals the max flow, we do this until the bottleneck value is zero, at which point we know that no more augmenting paths exist and the algorithm can terminate in between finding each augmenting path you can see that increment the visited token This is used to make the state of every node unvisited. The depth first search method itself takes two arguments, the node ID and the flow. Initially, the starting node is passed in as the node index and the flow is set to be infinity. As we progress through the flow graph, the flow value eventually becomes the bottleneck value as we find smaller and smaller edges with more restricting capacities and we stopped the Alex Once the node index equals the sink, so that's actually our base case right here. Afterwards since we know that the current node is not the sink, what we do is we explore it by marking the current node as visited. We do this by assigning the
5:25:17
current index or the current node index to be equal to the visited token, then comes the interesting part. First, we get all the outgoing edges of this node residual otherwise, and then loop over them. If the remaining capacity is greater than zero, meaning we can push flow through that edge and the next know that we're going to is unvisited meaning we don't risk creating a cycle, then we can enter this inner if block right here, inside the if block. The first thing I do is call the depth first search method recursively. What I do is I pass in the index of the next node we want to go to and the new flow value which should equal the minimum of the current flow or the current edges remaining capacity. Remember that that flow parameter is trying to capture the bottleneck value that intuitively makes sense. It's saying either keep the previously found bottleneck value or if this new edge is even smaller than it should be the new bottleneck value, this process continues recursively
5:26:26
until a base case is hit and the sink was reached. This returns the bottleneck of the augmenting path, we can then use that value to augment the flow of our augmenting path. However, first check that the bottleneck value is greater than zero, it could be the case that we never actually made it to the sink, and we hit a dead end. assuming that's not the case, simply argument the flow by increasing the flow in the forward edge by the bottleneck value and decreasing the flow in the residual edge by the bottleneck value. After that, simply return the bottleneck value. This propagates it up the stack so that all the other edges along the augmenting path can also be augmented. This also ensures that the bottleneck value is returned to the solve method where the max flow is actually calculated. So that's about everything I want to cover for the Ford Fulkerson method implemented with a depth for search. Today we're going to start diving a little deeper into network flow, we're going
5:27:29
to talk about unweighted bipartite graph matching, and specifically how we can use max flow to find a matching for us. Before we get started, though, I should mention what a bipartite graph is, a bipartite graph is one whose vertices can be split into two independent groups, u and v, such that every edge connects between u and v. Other definitions exists, such as the graph is too colorable, or there is a cycle with an odd length. bipartite graphs often arise when we're trying to match one group of items to another in some way. Think of situations such as matching suitable candidates to jobs. There could be multiple jobs are multiple candidates, but not every candidate is suitable for each job. If jobs are red nodes and candidates are white nodes, then there would be an edge between the two if the candidate is good fit. Another situation could be matching surfers to surfboards. Suppose there are multiple servers and multiple surfboards. But the surfers have preferences and requirements
5:28:43
for the boards, such as color, size and so on. Then the same thing happens we placed an edge between the surfer and the surfboard to indicate that they are able to be matched. Generally when we're setting up a bipartite graph, we're interested in what's called a maximum cardinality bipartite. Matching. This is when we've maximized the pairs that can be matched with each other. For example, we've maximize the number of candidates that can be matched to jobs or the number of servers to surfboards. Finding a matching is not unique to bipartite graphs. However, you can also have a matching on a non bipartite graph, this variant is a lot harder to solve and also much less common. Another variant is finding a maximum matching on a weighted graph where you can either maximize or minimize the cost of the matching. This variant is also much harder to solve than the unweighted version in the unweighted version, no edge is better in any sense than any other edge.
5:29:52
So it makes finding a matching much much easier. We're mostly going to focus on the top left box which is the easiest of the four variants, but hopefully it will get poke around in some of the other boxes as well. So if you want to find a maximum matching on an unweighted bipartite graph, you have lots of options, you can either set the graph as a flow problem and push flow through it, which is what we'll look at in this video. But you can also repeatedly find augmenting paths which maximize the matching using a depth first search. Or you can use the specialized Hopcroft Karp algorithm to do the same thing a lot faster. If your edges are weighted, and your graph is still bipartite, you also have a lot of options, you can use a min cost max flow algorithm, or you can run the Hungarian algorithm. And lastly, there's the more sophisticated network simplex algorithm which uses linear programming. If however,
5:30:52
you graph is not bipartite, but your edges are unweighted, you can use admins blossom algorithm. And lastly, the hardest of the four variants is when your graph is non bipartite. And the edges are weighted. I didn't find much information about this one online. But the recommendation seems to be to use dynamic programming on smart graphs. Now let's look at an example. This is going to be for the unweighted bipartite case, the easiest of the four variants. So I want you to imagine that there are five people and five books in the library and that some people express interest in some of the books. This results in a bipartite graph with people on one side and books on the other. So far, so good. Now suppose we want to find the maximum cardinality bipartite matching, or in other words, we want to match as many people with as many books as we can. Let's try the greedy approach to this matching problem. Let's start with person green. Their first edge connects to
5:32:00
the second book on the right side. The second book is unallocated so person green is matched with what is now book green. Next up is person orange. The first book they want is the same book as person green, which is already matched, so we cannot select person greens book. Their next choice is the third book which is unallocated, so they get matched to that one. Next up is person purple, they instantly matched to an unallocated book on the right hand side. Now person Read, read only has one edge, meaning that they're only willing to read that one book. However, that book has already been allocated to person orange, so person read cannot have it. Next up is person Brown. They also want person oranges book, but they also cannot have it. Fortunately, they have other options of books they're willing to read. So person brown gets one of those. So in the end, the greedy approach only found a matching of four, only four people were able to be matched with books. But can we do any better?
5:33:17
Is this the true maximum cardinality matching. Turns out that it's not a greedy approach to the maximum matching problem will not work. As we just saw, we need a more sophisticated approach to ensure that we are able to get that maximum matching. So we're going to solve this maximum matching problem by turning our problem into a network flow problem and finding the max flow. The first thing we're going to do is make every edge directed and add one unit capacity to each edge. The zero slash one besides each edge means zero flow and a maximum capacity of one. Next we're going to introduce two new nodes, the source and the sink and hook up edges at words from the source to the people with a capacity of one and hook up edges from books to the sink also with a capacity of one. Once that's all set up, use any maxo algorithm to push flow through the network. What this will do is show us what edges get populated with flow with that information, we will be able to reconstruct
5:34:35
the maximum matching. Here's a graph after the flow algorithm has ran. You can see that some of the edges have one unit of flow. Those were the edges selected by the max flow algorithm. The most interesting edges are the middle edges with one unit of flow. These are the edges which formed the maximum cardinality matching if We call her in the middle edges, which have one unit of flow, you can see that this time everybody goes home with a book and no one is left empty handed. Okay, so now we understand how this basic setup works and how it leads to a matching. Let's play around with this model a little bit to truly understand what all the weights here mean. We originally set the capacity of each edge from the source to each person to be one. But what constraint is that really enforcing? I'll let you pause the video and think about that for a second because it's so important. The answer is that that capacity of one ensures that each person can get up to one book and
5:35:47
no more. If we increase this number. For some people, we can allow them to possibly pick up more than one book. If we rerun the max flow algorithm through this network, we see that it's now possible for one person to be matched with multiple books. The next thing we want to do is change the flow network to allow a book to be selected multiple times. Pause the video and think about how we can modify this flow graph to support having multiple copies of the same book in the library. I'll give you a short moment. The number of copies of a book is controlled by the capacity of the edges leading to the sink T. Increasing this value will allow more flow to run through those designated edges. This effectively limits or controls the number of copies of a book, let's change the capacity of those edges leading into the sink to allow having multiple copies of the same book and see what happens. If we rerun the max flow algorithm. Once again through the network, we see that we now have
5:37:08
people matched with the same book multiple times because multiple copies exist. For example, Book Three and book five, both have two people grabbing a copy of them, the actual assignment of people to books would be as follows. I'll let the animation play. After the flow algorithm has ran, if you want to know how many copies of each book were actually given out, you can inspect the flow value on the edge leading to the sink. Currently, each person is only allowed to pick up one copy of each book, even though there are multiple copies of each book. How can we modify the flow network to support this? You've guessed it, we need to modify the edge capacity between a person and the book to allow that person to pick up multiple copies of that book. Today, we're going to look at how to use network flow to actually solve a useful problem. The problem we're going to tackle is what I call the mice and owls problem, which is a slightly harder variation of another competitive programming
5:38:26
problem, which I'll link in the description. I love this problem because of its simple and elegant solution, but also it's realistic real world application. Let's have a look. Suppose there are m mice out on a field and there's a hungry owl about to make a move. Assume that the owl can reach every single one of these mice. Further suppose that there are h holes scattered across the ground, and that each hole has a certain capacity for a number of mice they can hide in it. We also happen to know that every mouse is capable of running a distance of are in any direction before being caught by the owl. The question asks, what is the maximum number of mice they can hide safely before being caught. If you want to give this problem a try, now's a good time to pause the video and try and write some code. The first step is to figure out which holes each mouse can reach. visualize this by drawing a radius of our around each mouse. And if inside the radius, there's a hole or the circle
5:39:34
touches a hole will assume that the mouse can make it to the hole safely. So if we draw an edge between a mouse and a hole, if the mouse can make it to that hole, we get the following graph. The next step is to actually match mice to holes to maximize the overall safety of the group. By doing a simple quick inspection, it's clear that not every mouse should be matched to any hole, for example, this orange mouse should probably not try and run to the hole with a capacity of three, because it's the only mouse that can reach the hole behind it with a capacity of one, making any bad decision like this has the chance to jeopardize the maximum number of overall mice, they can hide safely. The key realization with this problem is that the graph is actually bipartite. And once we know that, it actually becomes a much simpler problem, because we can set up a flow graph and run a maximum flow algorithm to maximize the overall number of nice, which can hide safely, here
5:40:42
are the steps I would do to set the flow graph and run a max flow. First, I would create n mice nodes labeled zero through m minus one inclusive, then on the other side, I will create h nodes, each representing a whole, I would label or index these nodes from m to m plus h minus one inclusive to give them a different ID than the mouse nodes, then I would place an edge with a capacity of one between the mouse and the hole. If the mouse can reach that particular hole in time. After that, I would connect an edge with a capacity of one from the source to each mouse to indicate that each node can have at most one maps. And lastly, connecting edge from each hole node to the sink node with the capacity of the hole. The problem has now been transformed into a maximum flow problem, we can run any maximum flow algorithm to get the maximum number of mice that can be safe. This is really neat. And it's worth looking at some source code to really understand how this setup works.
5:41:51
All right, here we are in the source code. I have laid out some instructions on the top here in case you wanted to download the code and actually play around with it on your machine. This program also uses the Ford Fulkerson flow solver we saw two videos ago. So I highly recommend you go and watch that video before continuing. I'll link to it in the description below, just in case you haven't seen it. So let's get started. The first thing I do here is I create a mouse class, which is essentially a wrapper around a point object. Effectively, a mouse is just the point on a plane. I also do the same thing with the whole class except that the whole class with addition to having a 2d point object, it also has a certain capacity because we know that holes can only contain a certain number of mice. Next up in the main method, I create a bunch of mouse objects and place them in an array, I scour the mice more or less randomly across the field. And then I do the same thing with holes. The last
5:42:57
thing I do in the main method is called the solve method which actually takes as input the two arrays we just created and a radius. The radius is how far a mouse can run from its current position before being caught by the hour. The sole method is where things really start to get interesting. Let's define some constants that will make our lives a lot easier. First is M which is just the number of mice then is h the number of holes we have. Following that I compute n the number of nodes, which is the number of mice plus the number of holes plus two. The plus two is to account for the source and the sink node. And as per convention I always index s&t the source and the sink two indices and minus one and minus two to ensure that they are unique. After that I initialize the network flow solver base by providing and s&t the solver classes defined below. It's the exact same one from the Ford Fulkerson source code video. In short, the solver lets you add edges with various
5:44:09
capacities to the flow graph and then find the max flow. Once it's all set up. The goal of this video is not to explain to you how the max flow itself is found, or how the solver works. I already discussed that previously. What I really want to focus on in this video is how to set up the flow graph for this problem and push some flow through it when the graph is bipartite. Like it is in this problem. The setup is actually pretty straightforward. The first step is to hook up edges from the source asked to each mouse with a capacity of one. Intuitively, this limits each mouse node to represent at most one mouse. This is necessary because we don't want a mouse node to represent more than one mouse that doesn't really make sense. The next part is to hook up mouse nodes with holes. nodes in the flow graph. This is the middle section of the flow graph where we add an edge between a mouse node and a hole if the distance from a mouse to the hole is less than the radius.
5:45:14
In other words, if the mouse can make it to the hole on time, add an edge connecting the mouse and the hole. The last step is also important, you need to remember to hook up the edges between the holes and the sink. These edges are slightly different, because their capacity represents the number of mice which can fit into each particular hole, say a hole has a capacity of three. But there are five mice which can make it to that hole. Well, we cannot allow more than three of those mice to fit in the hole. So we set the capacity of the edge to the sink to be three, those two leftover mice will need to find another hole, or gets scooped up by the apple. The very last thing we need to do to actually get the max flow is to run the solver which will return the number of safe mice, which for this configuration happens to be four, we're still talking about network flow. And today's topic is one of my all time favorite four problems, which is the elementary math
5:46:18
problem. This problem is so interesting, because its solution uses flow. But it really doesn't hit you as a flow problem to begin with. One of the hardest things about network flow, I believe is actually identifying that a problem is a flow problem, and then setting it up as so this is why I'm spending so many videos solving some flow problems, so you really start understanding how to approach them and how they are solved. So let's dive into the elementary math problem. This problem is actually on caddis. Should you want to attempt it, the link is at the bottom of this slide and also in the description. Here's the problem statement. Ellen is a math teacher who is preparing and questions for her exam. In each question, the students have to add, subtract or multiply a pair of numbers. Ellen has already chosen the N pairs of numbers, all that remains is the side for each pair which of the following three possible operations the students should perform. To avoid students getting bored.
5:47:30
Elon wants to make sure that the end correct answers on her exam are all different. For each pair of numbers a B in the same order as the input output a line containing a valid equation. Each equation should consist of five parts, a, one of the three operators be an equal sign and the result of the expression. All that n expression results must be different. If there are multiple valid solutions, output any of them if there are no valid answers, output a single line with the string impossible Instead, let's have a look at an example. So Ellen goes and picks four pairs of numbers, say one and five, three and three, four and five. And lastly minus one and minus six. She wants to assign operators either plus minus or multiply to yield the unique answers on the right hand side of the equation. One assignment of operators might be the following. However, this assignment of operators doesn't quite work because the answers are not unique on the right hand side. Here's another way
5:48:43
of assigning operators to the pairs of numbers. This assignment does work because the answers are unique on the right hand side, which is one of the requirements for the problem. So we just saw that not any arbitrary assignment of operators yields a valid solution. But it's also possible for no answer to exist, consider the following pairs of numbers. In this case, there can be no solution because there are not enough unique answers that can be produced using the operators plus minus and multiply. As it happens, this problem presents itself as a network flow problem, even though that might not be obvious at first. So take a moment and attempt to set up a flow graph that can actually solve this problem. It's actually a really great exercise along the way. While you're doing this, there are a few questions you should ask yourself, or at least that I asked myself when I first did this. The first is there a way that this problem can be simplified into a bipartite
5:49:50
graph. I asked myself this because I know that solving a flow problem when it's a bipartite graph can be done very efficiently and also because by Titan graphs are very easy to set up, then I asked myself, how am I going to detect impossible sets of parents? Will my flow graph be able to handle that? Or do I need to do some pre or post processing to actually figure that out? And lastly, I'm thinking about edge cases. So how, how do I handle multiple repeated input pairs? And how is I going to change the flow graph? These are all super important questions you need to ask yourself when solving this problem, this slide deck explains the first two. And the third is somewhat left as an exercise, I don't want to give away the full solution to this really awesome problem. So thinking about how we're going to solve this problem a little more, a key realization to make is that for every input pair, at most three unique solutions are produced, think of the input
5:50:51
pair, two and three. Well, for that pair, we can either add two and three, subtract two and three, or multiply two and three. So there can be at most three unique results, there may be less if there are collisions, think of the input pairs 000, plus 000, multiplied by 00. And zero subtracted by zero is also zero. So we may end up with less than three unique solutions, and that's fine. The great thing about this is that we can easily set up a bipartite flow graph from this because we can have input pairs on one side and solutions on the other side, let's see if we can set the flow graph and solve the set of input pairs, we have the pairs 1533, minus one minus six, and finally to two so how we're going to set up this bipartite graph is we're going to have input nodes on the left side and answer nodes on the right side, for our first input pair one, five, if we compute one minus five, one plus five, and one multiplied by five, we get minus four, six, and five, which become
5:52:04
answer nodes on the right hand side, then we want to attach an edge between that input pair and the answer. Do the same thing for the next input pair, make an input pair node and attach edges to the answer nodes. However, don't create another answer node if there already exists one with the value we need. In this example, you'll see that three plus three equals six, and we already have an answer node for six. So simply attach an edge from three three to six do not create another answer node. This is to ensure that our answers remain unique. And do the same thing for the other two remaining input pairs, you'll notice that the last input pair only produced two outgoing edges and not three. This is because there was a collision in particular, two plus two equals four, but also two multiplied by two equals four, and this is fine. Just put one edge don't put two edges. Then like every bipartite graph you're trying to find a matching for, you'll want to add the source s and the
5:53:10
sync T. And the matching is really what we're after. Here, we want to match input pairs to answers. And then we've actually solved the problem. The next step, after adding the source and the sink is to actually assign capacities to the edges of the flow graph. Let's start on the right side, the capacities from the answer nodes to the sink should all have a capacity of one since the answers need to be unique and limiting the edge capacity to one ensures that capacities for the input pairs two answers should also have a capacity of one since only one of plus minus or multiply should actually be matched to enhance capacities from the source two, the input pairs should reflect the frequency of the input pair. In this example, all frequencies are one. But as we know, that's not always the case. Now the flow graph is set up, let's run a max flow algorithm on it. The flow algorithm does its thing and some edges are filled with flow. These are the edges that were selected to
5:54:17
be part of the maximum flow. From this, we can derive what the matching was. More specifically, we're interested in the middle edges. Those are the edges which give us information about the matching. every edge in the middle with one unit of flow represents a matching from an input pair a B to its answer. For example, the input pair one five was matched to the answer node six because there's one unit of flow going through that edge. From this we can even deduce the operator used for each matching, which is actually needed for the final output. This can be done by trying which of the plus minus or multiply on Operator results in the found matching. Basically, we first solve the problem by figure out which answers we get and then working backwards to figure out which operator was used. In theory, we could tag each middle edge with what operator was used, but I didn't bother doing that. It's, it's more work. Let's wrap up this problem, the last thing we need to
5:55:23
do is look at the matchings and figure out what operators were used. The first matching is the input pair, one five matched to six. So we ask ourselves, which of the three operators plus minus or multiply our results in one five equaling six? So we try all three options, and we figure out that, hey, one plus five is six. So the operator is the plus, then we move on to the next pair, and then we do the same thing. If there are multiple operators that result in the right answer, pick any of them. And that's basically it, we can verify that all our operators yield the correct result and that all our answers are unique. I didn't go into great detail on how to support multiple repeated pairs, but I'll leave that as an exercise to the listener. Today, we're going to probe even further into network flow. We're going to be talking about a specific implementation of the Ford Fulkerson method, which is the Edmonds Karp algorithm. Edmonds Karp is another
5:56:32
maximum flow algorithm, which uses a different technique to find augmenting paths through the flow graph. Before we get started, let me give you a refresher on what we're trying to do. We are trying to find the maximum flow on a flow graph because we know that finding the maximum flow is really useful for finding bipartite matchings and also the solve a whole host of problems. So far, we've looked at one other technique to find the maximum flow, which is to use the Ford Fulkerson method with a depth first search. At a high level, it says that all we want to do is repeatedly find augmenting paths from the source to the sink argument in the flow and then repeat this process until no more paths exist. The key takeaway here is that the Ford Fulkerson method does not specify how to actually find these augmenting paths. So this is where we can optimize the algorithm. A few videos ago, we saw that the Ford Fulkerson method can be implemented with a depth first search to
5:57:41
find the maximum flow. However, the pitfall with that technique was that the time complexity depended on the capacity values of the edges in the graph. This is because the depth for search picks edges to traverse in such a way that we might only ever be able to push one unit of flow in each iteration. This is really bad and can kill the time complexity even though it's highly unlikely to happen in practice, but it's absolutely something we want to avoid. should it happen right now the time complexity of Ford Fulkerson with a depth first search is big O of E times f, where e is the number of edges and f is the maximum flow. The idea behind Edmonds Karp says that instead of using a depth first search to find augmenting paths, we should use a breadth first search instead, to get a better time complexity. big O of V times e squared may not look like a better time complexity, but it actually is. What's different is that the time complexity while it might not look great, does not depend on
5:58:54
the capacity value of any edge in the flow graph, which is crucial recall such an algorithm that doesn't depend on the actual input values a strongly polynomial algorithm and that's exactly what Edmonds Karp is and why it was so revolutionary at the time. Edmonds Karp can also be thought of as an algorithm which finds the shortest augmenting path from s to t that is, in terms of the number of edges used in each iteration. Using a breadth first search during Edmonds Karp ensures that we find the shortest path This is a consequence of each edge being unweighted. When I say unweighted, I mean that as long as the edge has a positive capacity, we don't distinguish it between one edge being a better or worse than any other edge. Now, let's look at why we might care about using Edmonds Karp. Suppose we have this flow graph and we want to find what the maximum flow is. If we're using a depth first search, we might do something like this. Start at the source Do a random
6:00:01
depth first search forwards. So after a lot of zigzagging through the flow graph, we are able to find the sink. As we just saw a depth first search has the chance to cause long augmenting paths and longer paths are generally undesirable because the longer the path, the higher the chance for a small model neck value, which results in a longer run time. Finding the shortest path from s to t, again in terms of number of edges is a great approach to avoid the depth first search worst case scenario and reduce the length of augmenting paths to find the shortest path from s to t do a breadth first search starting at the source and end to get the sink while exploring the flow graph. Remember that we can only take an edge if the remaining capacity of that edge is greater than zero. In this example, all edges outwards from s have a remaining capacity greater than zero. So we can add all the neighbors to the queue when we're doing the breadth first search step. And then we keep going forwards, so
6:01:17
add all reachable neighbors to the queue and continue. And now the breadth first search has reached the sink, so we can stop. In the real algorithm, we would stop as soon as any of the edges reached the sink. But just for symmetry, I show three edges here entering the sink, while in reality, we would stop as soon as one of them reaches the sink. If we assume that the bottom edge made it to the sink first, and we retrace the path, we get the following augmenting path. But we didn't just find any augmenting path, we found a shortest length augmenting path. So to augment the flow, do the usual find the bottleneck value by finding the smallest remaining capacity of all the edges along the path, then augment the flow values along the path that by the bottleneck. So that was the first path however, we're not done yet. Let's continue finding paths until the entire graph is saturated. Recall that while exploring the flow graph, we can only reach a node if the remaining
6:02:24
capacity of the edge to get to that node is greater than zero. For instance, all the reachable neighbors of the source node in this case does not include the bottom left node because the edge from the source to the bottom left node has a remaining capacity of zero. All right, keep exploring until the sink is reached. And now we've reached the sink once more. So find the bottleneck value along this path. Then use the bottleneck value to update the flow along the augmenting path. Don't forget to update the residual edges. And we're still not done because there still exists another augmenting path. So now there only exists one edge outwards from the source with a capacity greater than zero, so it's the only edge we can take. So we follow it. There's also only one edge to follow from the second node because the other edges have a remaining capacity of zero. And now the breadth first search has reached the sink, we can trace back the edges that
6:03:38
were used. We can find the bottleneck by finding the minimum capacity along the path and also augment the flow. And now you can see that there are no more augmenting paths left to be found because all the edges leading outwards from the source have a remaining capacity of zero. However, more generally, we know to stop Edmonds Karp, when there are no more augmenting paths from s to t, because we know we cannot increase the flow anymore. If this is the case, the maximum flow we get from running Edmonds Karp is the sum of the bottleneck values. If you recall in the first iteration, we were able to push five units of flow in the second iteration 10 units and in the last iteration, five units for a total of 20 units of flow. Another way to find the maximum flow is the sum the capacity values going into the sink, which I have circled in red. In summary, this is what we learned using depth first search on a flow graph can sometimes find a long, windy path from the source to
6:04:44
the sink. This is usually undesirable because the longer the path, the smaller the bottleneck value, and the longer the runtime. Edmonds Karp tries to resolve this problem by finding the shortest length augmenting paths from the source to the sink using a breadth first search. However, more importantly, the big achievement of admins Corp is that it's time complexity of big O of the times e squared is independent of the max flow. So it doesn't depend on the capacity values of the flow graph. And that's admins carp in a nutshell. Today, we're going to have a look at some source code for the Edmonds Karp algorithm. Alright, here we are in the source code written in Java, I've laid out some instructions here in the header in case you wanted to download the code, play around with it and run it yourself. If I scroll down, you can see that we still have the same setup as before with the edge class, right here and the network flow base solver. But there is one important change
6:05:46
I have made since the Ford Fulkerson video. And that is I have added three new methods. If we scroll down, you can see that three new methods are right here. The three methods I added abstract away visiting nodes and marking all known says unvisited now, this is all done efficiently internally, through the network flow based solver class using a visited token you don't have to worry about it also helps readability for anybody who's new to the code. Alright, now let's have a look at the Edmonds Karp solver which is the only thing different in this file. First, notice that the Edmonds Karp solver extends the network flow solver base. In doing so we get a whole bunch of things for free, including the ability to construct a flow graph, before we push flow through it. In the constructor for the Edmonds Karp solver, all I do is call the superclass constructor. This performs various initializations, including allocating memory for the flow graph and registering which nodes are the source
6:06:50
and sink. The most important method and the Edmonds Karp solver is the solve method right here. The sole method is called just before we get the maximum flow, this method is really short. All we do is repeatedly find augmenting paths from the source of the sink until the flow we get is zero, at which point we know that the graph is fully saturated and no more augmenting paths can be found line by line. And what we do is mark all nodes as unvisited before each iteration, run a breadth first search and get the bottleneck value, and then some overall bottleneck values to calculate the maximum flow. Now let's take a closer look at the breadth first search method. The first thing I do is initialize an empty queue data structure. Because I know that we're going to need one to do a breadth first search after the creation of the queue. What I do is I visit the source node and add it to the queue so that the breadth first search starts at the source.
6:08:00
Then do your standard breadth first search loop. While there are still nodes in the queue, remove the first node found in the queue. If it's the sink, stop, otherwise iterate through all valid adjacent neighbors, we can add a node to the queue if it is not already visited, and the edge leading to the node has a capacity greater than zero. However, before we add the node to the queue, we visit it and track where it came from by placing an edge in the prep array to rebuild the augmenting path later on. Alright, so moving on, we know that the breadth first search did not actually make it to the sink if we have no entry at the index of the sink in the prep array, so we can return early after this point. We know that there exists in augmenting path. Since we know an augmenting path exists, we can find the bottleneck value that is the smallest remaining edge capacity along the path. We do that by starting at the sink and reconstructing the augmenting path going backwards by repeatedly
6:09:04
reaching into the prev array until we are back at the source, then we need to update the flow along the augmenting path to adjust the flow values. So once again loop through the edges forming the augmenting path, then the I've met method takes care of increasing the flow along the forward edges and decreasing the flow along the residual edges. The very last thing to do is to return the bottleneck value so that we can sum the max flow and the solve method. And that's basically it for Edmonds Karp. to actually build a flow graph. Have a look at the example right here in the main class. It sets up the flow graph from the previous video and pushes flow through it. You can see down here where we actually create the solver and run the solver to get the maximum flow and then finally display the resulting graph after the maximum flow has been pushed through it. So this is really handy to understand. So please have a look at this in more detail. If you're struggling
6:10:05
to understand it and Karp, today, we're still talking about network flow. And in particular, we're going to cover something called capacity scaling, which is really more of a heuristic than it is an algorithm. Capacity scaling is a heuristic which says that we shouldn't attempt to push flow only through the largest edges first, and then allow using edges which have smaller capacities and do this to achieve the maximum flow more rapidly. Just before we dive into capacity scaling, I want to quickly revisit finding the max flow using a depth first search and the issues surrounding that. I keep coming back to this because I think it's important that we understand the intuition behind why all these new max flow algorithms were developed and why they came about. When we're looking at finding augmenting paths. The worst case is when we can only augment the flow by one unit, and it goes something like this, we start at the source node, we take any edge with a remaining capacity greater
6:11:11
than zero. And we just keep going until we reach the sink. And once we've reached the sink, we find the bottle max value that is the edge with the smallest remaining capacity along our augmenting path, which in this case happens to be one. Then we argument or update the flow by adding the bottleneck value to the flow along the forward edges and subtracting flow by the bottleneck value along the residual edges. However, we're not done. So we're going to start once again at the source and start finding another path. Suppose this time we take the edge going down, then take the residual edge going up and sideways, and then down again. And now we have found another augmenting path, and we can find its bottleneck value. Recall that the remaining capacity of an edge is calculated as the capacity minus the flow. This allows residual edges with a negative flow to have a positive remaining capacity. Notice that yet again, the bottleneck value for this path is only one unit of flow. Now
6:12:25
update or augment the flow. Do this by adding the bottleneck value to the flow along the forward edges and subtracting the flow by the bottleneck value along the residual edges. You could imagine the depth first search algorithm repeatedly taking an edge with a capacity value of one each time, which would ultimately limit how much flow we can push through the network in each iteration, as shown in the next few slides. So it would look like this we just keep alternating between the forward and the residual edge with a capacity of one. Capacity scaling is the idea that we should prioritize taking edges with larger capacities first to avoid ending up with a path with a small bottleneck. If we adjust the size of each edge based on its capacity value, then we can more easily visualize which edges we should give more attention to the capacity scaling algorithm is pretty straightforward. But first, we need to define two variables that we will need. let u equal the value of
6:13:35
the largest edge capacity in the initial flow graph. And also let Delta be the largest power of two which is less than or equal to the value of view. The capacity scaling heuristic says that we should always take edges whose remaining capacity is greater than or equal to delta in order to achieve a better runtime. But that's not everything to the algorithm. The algorithm will repeatedly find augmenting paths through the flow graph which have a remaining capacity greater than or equal to delta. Until no more paths satisfy this criteria. Once this criteria is no longer met, what we do is decrease the value of delta by dividing it by two. And then we repeat this process while delta is greater than zero. So the reason you would want to implement capacity scaling is because it's very easy to code up and it works very, very well in practice. In terms of time complexity, capacity scaling with a depth first search runs in big O of E squared log Q. And in big O of E times v log you if
6:14:52
the shortest augmenting path is found, which is basically Edmonds Karp but with capacity scaling, although I have found that to be much slower, so I would recommend the depth for search if you are going to implement this. Let's do an example, let's find the maximum flow of the following flow graph using capacity scaling. First, compute you as the maximum of all initial capacity values. In this example, use the maximum of 614 157 10 111 and 12, which happens to be 14. Next, compute the starting value for delta, which is the smallest power of two less than or equal to u, which we know is 14. Therefore, the starting value of delta is eight since the next power of two after eight is 16. But 16 is larger than 14. Now that we have delta, we can start finding paths from s to t, which have a remaining capacity greater than or equal to eight, start our search at the source from the source, there's only one edge which has a remaining capacity of eight or more, which is the edge
6:16:04
with the capacity of 14 going downwards, then there's the edge sideways with a remaining capacity of 10, we can take and finally an edge with the remaining capacity of 12 going upwards, which we can also take. Now we've reached the sink. So we can find the bottleneck value which is 10. Because 10 is the smallest remaining capacity along the found path. Next, augment the flow along the path, I scaled down the size of each edge to reflect how much remaining capacity they have left, you can analyze the flow graph, but there are no more augmenting paths from s to t which have a remaining capacity greater than or equal to eight. So the new delta is haften two, and is now equal to four. One path we can take with all remaining capacities of four or more is the following. Start at the source. Go up, sideways and sideways again, then do the usual find the bottleneck and augment the flow. There is also another path with all remaining capacities rather than
6:17:13
four which we can take from stt, which is down to one diagonally up to node two and to the sink again, find the bottleneck value, which we know to be four, because four is the smallest remaining capacity along a path, then we can augment the flow. If you now inspect the flow graph, there are no more paths with a remaining capacity with all values greater than or equal to four from s to t, so half the value of delta and two However, there are also no paths with the remaining capacity of all two or more. So we need to have the value of delta again. So now delta is equal to one, I believe there is one remaining path we can take before the graph is fully saturated. Let's start at the source and find it. Alright, now we found the path. And we can also find the bottleneck which has a value of one. And now the last step is to augment the flow. And now there are no more paths from s to t which have a remaining capacity greater than or equal to one. So the new value
6:18:26
of delta is zero, which terminates the algorithm, we can compute the maximum flow by summing up all the bottleneck values we found in each iteration, which we know to be 10 Five, four and one for a total of 20. We can also compute the maximum flow by summing the flow values going into the st highlighted in red. So in summary of what we have learned about, we know that Ford Fulkerson implemented with a depth first search can result in having a bottleneck value of one in each iteration, which kills the time complexity. Capacity scaling is when we push flow only through larger edges first, to try and achieve a better runtime. One approach to capacity scaling is to maintain a decreasing parameter Delta, which acts as a threshold for which edges should be accepted and which should be rejected based on their remaining capacity. This is a pretty simple but extremely powerful idea that greatly speeds up finding the maximum flow. Today we're going to have a look at
6:19:34
some source code for the capacity scaling algorithm. Okay, here we are on the source code written in Java. I've laid out some instructions here in the header in case you actually want to get the code play around with it and run it yourself. Scrolling down you can see we have the familiar edge class here. This is the class used to represent an edge that connects two nodes with a certain company. If I scroll a little further down, we have the network flow solver base, which acts as a template for all the different flow algorithms we have been implementing. I have already covered how these two classes work in the previous videos linked below. So please have a look at those before continuing. However, the class we're really interested in is the capacity scaling solver. Right here. The capacity scaling solver is an implementation of the network flow solver base, which uses capacity scaling to find the maximum flow, you will notice that I have defined one new instance variable
6:20:38
in this class, which is called Delta. This is the same Delta that we saw from the slides, it's the parameter we use to determine whether an edge should be accepted or rejected based on the remaining capacity relative to the value of delta. The constructor for this class simply calls the super classes constructor to initialize the flow graph and allocate some memory that will need to actually push flow through the network. Just below is the Add edge method. The Add edge method is particularly interesting for capacity scaling to work, we need to know the value of the edge with the largest capacity in our flow graph. Since we also need to construct the flow graph to actually do anything interesting, we can capture the largest capacity value as we build the graph. The implementation of the Add edge method is defined in the network flow solver base, which we don't actually want to change the functionality of. So inside this add edge method, which I'm overriding here I do is
6:21:37
I call the super classes add edge method. And I also initialize delta to be the largest capacity we encounter as edges come through simple enough. Inside the solve method, which gets called to compute the maximum flow, the first thing we do is initialize delta to be the largest value of two less than or equal to the largest capacity. And one way to do this is to find the floor of the base two logarithm and then raise that value to a power of two or in Java, you can simply use the built in function highest one bit to do that for you more efficiently. Following that we repeatedly find augmenting paths from the source to the sink using only edges with the remaining capacity greater than or equal to delta. After each iteration, we have the value of delta to allow taking smaller edges and being able to find more augmenting paths from the source to the sink until the graph is fully saturated. Inside the inner loop, we mark all the nodes as unvisited then we do
6:22:39
a depth first search and sum over the bottleneck values to calculate the maximum flow we repeatedly do this until delta is equal to zero. Now let's have a look at the depth for search method. The depth first search method takes two arguments the current node and the minimum flow found along the path so far, when we initially call this method, the source node is the current node and the flow is set to positive infinity. This method performs the depth first search recursively. And we know we can stop searching when we have reached the sync node t. If the current node is not the sync node, then visit the current node and iterate through all the neighbors of the current node. However, here's the catch though we cannot take an edge going to a neighboring node if the remaining capacity of that edge is smaller than delta because this violates the capacity scaling heuristic, we must also ensure that the node we're going to has not
6:23:38
already been visited. We do this to avoid cycles in the flow graph. Inside the inner if statement we call the depth first search method recursively passing the node or going to as the current node and the new flow as the minimum of the current flow and this edges remaining capacity, the depth for search returns the bottleneck value along the augmenting path. So after the depth first search call, we are unwinding the call stack from the sink back to the source. This is a perfect time to augment the flow of each edge along the augmenting path since we have the bottleneck value right there. So if the bottleneck value is greater than zero, this means we have found a valid augmenting path and we want to augment the flow, which is remember adding flow along forward edges and subtracting flow along residual edges. This is all done through the argument method in the edge class and finally, return the bottleneck value. If we scroll down even more, you can see that this is the main method
6:24:39
right here. In here I set up an example of how to set up a flow graph. Specifically, this is the flow graph from the slides. So I create a flow solver. I add all the edges and then I push some flow through it and get the maximum flow. I also display the resulting flow graph after the flow algorithm has been executed so you can see what happened. Awesome. That's all I wanted to cover for capacity scaling. Today, we're still talking about network flow. And in particular, we're looking at finding the maximum flow and a new, very efficient method of solving the unweighted bipartite matching problem. denix algorithm is one of those extremely fast and revolutionary algorithms, which really push the field of network flow forwards. It was one, if not the first algorithm to introduce a bunch of new concepts like building a level graph, combining multiple graph traversal techniques together and the concept of a blocking flow, all of which we'll get into. So what is the
6:25:38
next algorithm? It's a fast, strongly polynomial maximum flow algorithm. The fact that it's strongly polynomial is important, it means that the run time doesn't depend on the capacity values of the flow graph for which all we know could be very large. What's remarkable about dynex is that not only is it fast in practice for general graphs, but it boasts performance on bipartite graphs running and the time complexity of big O of square root v times E. The importance of this cannot be overstated. It makes it possible to handle bipartite graphs of a ridiculous size. If you're doing competitive programming. dynex is the de facto standard algorithm to solve maximum flow algorithms. The algorithm was conceived in 69 by Ephraim Dennis and published in 1970. The algorithm was later modified slightly and popularized by Shaiman. Evan mispronouncing denotes algorithm as demyx algorithm. Let's start by talking about the algorithm itself. But first, beginning with
6:26:45
an analogy. Suppose you and a friend are planning to meet up at the coffee shop a few streets east of where you are, you've never been to this coffee shop, and you don't exactly know where it is, but you know, it's somewhere east. So how would you get there? With the information you have? Would it make sense to head south? What about Northwest, the only sensible directions are East, North East and Southeast This is because you know that those directions in guarantee that you make a positive progress towards the coffee shop. This form of heuristic ensures that we continuously make progress towards whatever place of interest we desire to go. So how can we apply this concept to solving the maximum flow? In this analogy, you were the source node and the coffee shop is the sink. The main idea behind dynex algorithm is to guide augmenting paths from the source to the sink using the level graph. And in doing so greatly reducing the runtime. The way dynex determines what edges make progress
6:27:54
towards the sink T and which do not is by building what's called a level graph. The levels of a graph are those obtained by doing a breadth first search from the source. Furthermore, an edge is only part of the level graph, if it makes progress towards the sink, that is an edge must go from a node at level l to another node at level l plus one, the requirement that edges must go from L to L plus one prunes backwards or what I call sideways edges. Those are all the gray edges in the slide. So ask yourself if you're trying to get from s to t as quickly as possible, does it make sense to take the red edge going in the backwards direction on the slide? No, taking the red edge doesn't bring you any closer to the sink, so it should only be taken if a detour is required. This is why backwards edges are omitted from the level of graph, the same thing can be said about edges which cut across sideways across the same level since no progress is made. It's also worth mentioning that residual
6:29:05
edges can be made part of the level graph but they must have a remaining capacity greater than zero. So that's the level graph the actual steps to executing denix are as follows First construct a level graph by doing a breadth first search from the source to label all the levels of the current flow graph. Then, if the sink was never reached, while building the level graph, you know, he can stop and return the value of the maximum flow. Then using only valid edges in the level graph do multiple depth first searches from the source to the sink until a blocking flow is reached and sum over the bottleneck values of all augmenting paths calculate the maximum flow as you do this. Repeat steps 123 a blocking flow is when we cannot find any more paths from the source to the sink because too many edges in the level of graph have been saturated. This will all become clear with an example, let's use the next algorithm to find the maximum flow of this flow graph. If this were a bipartite
6:30:12
graph, we would also be able to get a maximum matching as a result. All right, step one is to figure out which edges are part of the current level graph, you don't need to think of the level of graph as a totally separate graph, you can think of it rather as a subset of the edges. So we start at the source and do a breadth first search outwards. The first layer includes all the red nodes, then this is the second layer, and so on until we reach the sink. Now, if we focus on the edges, which formed the level graph, we can see that they are all edges which go from L to L plus one and level and have a remaining capacity greater than zero. Step two of the algorithm is to find paths from s to t until a blocking flow is reached. That is, we cannot find any more paths through the level graph. So we start at the source and do a depth first search on the edges of level graph until the sink is reached. So we've found our first augmenting path and the bottleneck value along this path
6:31:19
is five since five is the smallest remaining capacity, so update the flow values along the path by five. If you inspect the graph, the blocking flow has not yet been reached, since there still exists paths from s to t. Start once again the source and do a depth first search forwards. Now we found another path, this one has a bottleneck value of 15. So augment the flow along the path by 15 units. Now let's try and find another path from s to t. What happens now is that we get stuck performing the depth first search, there are no edges in the level of graph with a remaining capacity greater than zero, which can lead us to the sink. So the blocking flow has been reached, we just finished the first blocking flow iteration. Now we reset and rebuild the level graph. This time it should look different because the remaining capacities of multiple edges has changed. Start at the source expand outwards taking all edges with a remaining capacity greater than zero, which in this case is only
6:32:33
the middle edge leading us to the red node, the top edge going outwards from the source of saturated and so is the one going downwards. We keep doing this and building the level graph layer by layer. Awesome. So this is our new level graph. You can see that this time we have one extra layer to play with. Let's try and find a path from s to t. Once again, we start at the source and probe forwards using only edges part of the level graph. Oops, we have now reached a dead end in our depth first search because we can no longer go forwards. What we need to do is backtrack and keep going until we reach the sink. Perfect We made it to the sink the current path has a bottleneck value of 10 now augment the flow by 10 units. And now if you inspect the flow graph, you will notice that the blocking flow has once again been reached. Now no more flow can be pushed through the network when we build the level of graph, which means the algorithm terminates. The maximum flow is
6:33:53
the sum of all the ball and x values which if you recall were 515 and 10. For a maximum flow of 30. The maximum flow can also be calculated by looking at the flow values of the edges leading into the sink highlighted in red on the slide. However, one of the pitfalls of the current implementation of Linux algorithm at the moment is that it may encounter multiple dead ends during a depth first search phase. This is especially bad if the same dead end is taken multiple times during a blocking flow iteration. To resolve this issue in his original paper denotes suggested cleaning the level graph and getting rid of all the dead ends before each blocking flow phase. Then later in 1975. Shaiman Evans suggested pruning dead ends when backtracking during the depth for search phase, effectively getting rid of dead ends on the fly as the algorithm executes. This trick greatly speeds up and simplifies the algorithm because that ends are only ever encountered once. Awesome. So
6:35:13
that's basically everything you need to know about Linux. So let's summarize everything that we've learned. First, we talked about the motivation behind Linux, and why having a guiding heuristic can greatly speed up our algorithm. Then we talked about the intuition and practicality behind having a level graph that directs edges towards the sink. Then we talked about the concept of a blocking flow, which is achieved by doing multiple depth first searches on the level graph until the graph is saturated. Afterwards, we looked at the process of rebuilding the level graph, and finding the blocking flow and doing this process repeatedly until no more augmenting paths exist and the maximum flow is found. And lastly, we talked about a critical optimization of minutes algorithm, which is pruning dead ends so that we do not encounter them again. Today, we're going to have a look at some source code for dynex algorithm. Okay, let's get started. Here we
6:36:16
are in the source code written in Java, I laid out some instructions here in the header in case you wanted to get the code play around with it and run it yourself. Scrolling down as before, you can see the familiar edge class this class is used to represent an edge that connects to nodes with a certain capacity. It also has two important methods remaining capacity, which returns the true remaining capacity of an edge along with the argument method, which updates the flow along this edge and also the residual edge by a certain amount. A little further down is also the network flow solver base, which acts as a template for all the different flow algorithms we have been implemented. I already covered how this class and the edge class work and in previous videos linked below, so I won't spend too much time here. But what you need to know is that this class initializes the flow graph, it allows edges to add the flow graph, I like to call the get max flow method,
6:37:21
which is somewhere down here, right here. Internally, they get Maxwell method calls the abstract solid method, which we need to implement by subclassing, the network flow software base. So the part that we are really interested in is this dynex solver right here, you will notice that the dynex solver class extends the network flow solver base network flows or base gets initialized when we call super by feeding it the three inputs n s and t n is the number of nodes in our graph, S is the index of the source node and T is the index of the sinking node. Just after that I initialize an array instance variable column level to be a size and the level instance variable keeps track of the level of each note. Now we're a level graph. Moving on the following method is the solve method. Recall that this is the method that we need to override and compute the maximum flow in. Remember, what we're trying to do did an algorithm begins by building a level graph using a breadth
6:38:27
first search that is the outer loop. And for each level graph, we need to find the blocking flow by repeatedly doing multiple depth for searches from the source to the sink until the level graph is saturated, and the blocking flow is reached. Once that happens, rebuild the level graph and repeat the process until the graph is truly saturated. Let's have a look at the breadth first search method. So the breadth first search method really serves two purposes. One is to build the level graph and assign a level to each node in the level array. And the other purpose is captured by the return value of the function. And that is to determine if we are able to reach the sink during the breadth first search phase. And if not, this means that the graph is fully saturated and the algorithm can stop. The first thing I do in this method is mark each note as unvisited by setting each entry in the level array to be minus one. Then I initialize a queue data structure that we will need when performing
6:39:28
the breadth first search. After that I immediately add the source node to the queue. That's because we're starting the breadth first search at the source node. Since we're already at the source node, we can mark the distance to the source node to be zero. Once we start the breadth first search loop while the queue is not empty, each iteration we remove the first node index we find in the queue and iterate through all the adjacent edges of that node. When building the level graph, we want to ensure two things first, that the remaining capacity of the edges We take r greater than zero and that we are selecting unvisited nodes. If both those cases hold, then we can compute the level for that node we're about to visit and add it to the queue. This process continues until the queue is empty and the entire level graph is built. The last thing we do is return if we were able to reach the sync node during the breadth first search phase. Okay, coming back to the
6:40:23
solve method, now we understand how the breadth first search method works and how the level graph is constructed. Now let's have a look at the depth research method. However, before we do that, there's a key piece of information you need to know about and that is the next array in this method, the next array is part of the Shaiman evon optimization, and it is how we are able to prune dead ends efficiently. The idea is that since our graph is stored as an adjacency list, the list of edges going outwards from each node is indexed. And we can use this to our advantage to get the next edge to to reverse and skip all the edges, which we know lead to dead ends. Say we're at node i and we take the first edge in our adjacency list for node i suppose that this turns out to lead us to a dead end. Well, next time as in the next step, the first search in which we encounter the same node, we should not take the first edge in the adjacency list for that node, because we know it will lead
6:41:23
us to a dead end. The next array is a way of tracking for each node, which edge we should take next, each iteration, you want to reset the next array to allow taking previously forbidden edges. All right, so we call the depth research method and we pass in three argument, the current node being the source, the next array and the minimum flow along the path, which starts at positive infinity, then for each augmenting path that we find sum over the bottleneck values to compute the maximum flow. All right, let's have a look at the depth first search method itself. The depth through search method takes three arguments, the current node, the next array, and the minimum flow along the path. So far, this method performs a breadth first search recursively. And we know we can stop searching when we have reached the sync node t. Then I captured the number of edges going out of this node, the for loop loops through all the edges. While we have not tried
6:42:22
taking each edge for the current node, the next edge to take is the next outgoing edge from this node at the index in the next array. The thing we have to watch out for is that we must ensure that the selected edge has a remaining capacity greater than zero, and that it goes up a level. Remember that we're always trying to make progress towards the sink and taking an edge at the next level guarantees that unless of course, it leads to a dead end. But we end up pruning those so it doesn't really matter. So if all goes well, we get to enter the inner if statement. Inside the inner if statement, we call the depth for search method recursively passing in the node, we're going to as the current node and the next array and the flow as the minimum of the current flow and the edges remaining capacity. The depth for search returns the bottleneck value along the augmenting path after the this death research call, we are unwinding the call stack if you will,
6:43:21
and we're going from the sink back to the wards the source, this is a perfect time to augment the flow for each edge along the augmenting path. Since we already know what the bottleneck value is. So if the bottleneck value is greater than zero, meaning we actually found an augmenting path augment the flow, which means to add flow along the forward edge and subtract flow along the residual edge. And once all that is done, simply return the bottleneck value. So assuming we were not able to take the selected edge from the current node, because it did not have enough remaining capacity, or didn't increase in level or we hit a dead end or whatever reason, we need to mark the selected edge as invalid so we can prune it and future iterations. This is exactly what the next at plus plus line does, which gets executed after the iteration of the loop. It increments the index of the edge take at the current node. If we scroll down to the main method, you see that I show you how to set up a flow
6:44:25
graph by initializing the flow solver and pushing some flow through the graph. In particular, this is the flow graph from the slides last video. So you can verify that the maximum flow we get should be 31.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat