The chances are that the information from this episode will come in handy to you during a coding interview and likely in real life!
In this episode, you'll learn the topological sort algorithm. Along the way, you'll understand what's a dependency graph and how topological sort operates on this data structure. We'll also discuss a few real-life examples where I had to implement topological sort myself!
Transcript
Episode 10 - Topological Sort
00:00:02 - 00:05:11
welcome to the programming podcast. Here you can learn about computers in the brief and accessible way I'm your host mean could get. Hello everyone today. We're going to discuss another graph of course to Portugal. Sort as you know I really love Graph Algorithms. I find extremely applicable in practice until so. They're very common during cutting injuries to political sort. I believe I've had on a couple of reviews and I had to use it at least twice at work wass to figure out the execution order of abuse system and the second time was in you learning system where students was supposed to solve. A bunch of assignments in order and each assignment was depending on other assignments in this episode. Today we're going to cover three different things. We're going to discuss water submerged sort where we can take advantage of. That's and find the new. We're going to discuss health. Political sort works before going there. Though I would want us to talk about dependency graphs. I know that we covered them very briefly in episode six where discuss graphs? Beer fest. Three I want to come up with a couple of more examples and we're going to use this examples along the way so are popular in real life. Imagine that I would want to put some money in my savings account or I won't reinvest him. Well I can do that until I get my paycheck right so see how investing is directly dependent by getting paid. Here's the dependency graph with two different notes. The first note is getting paid and the second note is investing some portion of this money and there is a direct dependency between them. I cannot invest them before I get paid so there is an Arrow pointing from investing the money to get paid dependency. Cross are very popular in systems as well build systems like Bazo or go drummond wetback make and so on so forth. In all of these systems. We have a large dependency graph. One does depends on other and we can proceed. Invoking given task without first executing its dependencies because the particular task it may consume some of the outputs of his dependencies. Well when our bill system is working on a very small dependency graph the right order of execution is really obvious but in some cases the built graph is enormous. Imagine Google imaging building g mail or in Google search well dairies. There are quite a few knows. They're in the dependency graph and there are quite a few things happening so it is not easy. It's not trivial for developers to in cold this execution order manually. Instead will they would use is watch assert. Rhonda's Portugal certain over the dependency graph and finally this to output the right order into which the usual tasks from the dependency graph can be executed. Let's look at the very simple dependency graph for example. Let us suppose that would want to deploy an application? But before that WHO'd want to compile its scripts. Let's say from TAP SCRIPT GEL scripts well in this case. We cannot deploy the application with offers compiling the assets right with I comparing the scripts so we have an explicit dependency where we have an Arrow pointing from deploying the application to compiling the applications scripts sort is traverse this craff and it is going to return a list where the first note is going to be compiling scripts and the second note is going to be deployment. That's pretty much all of it and as I already mentioned. It is going to be particularly useful when you have to work on very large dependency grass. Now when I used to political sorts I I use it in an e learning system. I was building a platform where a student was able to go through a bunch of challenges based on courses that they have taken before. That and you weren't able to proceed further and take your final tests until you have passed through the lesson right after. He had sold assignments. And finally you were able to go to the final tests so these are just different knowles in a dependency graph which had some dependencies between them in order to complete your sign moments. You I suppose to go through the lessons that you were supposed to take and whilst he goes through the lessons and she goes for assignments you are able to complete the final test see. This is just pretty simple abstraction that we already discussed this obstruction occurs everywhere in real life in this educational platform built in systems and so on and so forth so by knowing the political sort.
00:05:12 - 00:10:01
You'll be able to solve this problem in all these domains. Isn't that amazing bright? That's why I like Algorithms because they are so abstract because they operate on Asher data structures and we can use them across many different areas. Anyway I got really excited. So let's take a step back why I ended up finally implementing logical sort in order to figure out towards the right order into which students was supposedly handled individual assignments individual levels. That they were going through. I dig lesson right after goals for assignments and finally compete final test. All right another example I was working on Angura seat project and I tried to obstruct. Go Up there with I was working on this project with a bunch of amazing contributors from the community. We abstracted go because we didn't believe that he's going to survive much longer so we built a small system on top of it and in this Bill System. Individual tasks had their own dependencies. We were writing stuff on the disk and tasks which were depending on the outpost that who have written on this consuming them directly from there. That's something quite similar to Basil. When I think about it well we had to implement logical sword there in order to figure out the right order execution of these desks so I talked a lot about logical cert- let us see how we can implemented algorithm for purpose. I'm sure that will not be able to our every thinking detail. Although the Algorithm itself is maybe on ten or fifteen lines of cult but still graphs are very visual. And this is a podcast. So what we're going to do is look at few different examples. We're going to see how political sort works on them and this way. I hope I'll be able give you a good enough intuition so that you can proceed implemented algorithmic by yourself just in case. I have also provided links to a sample implementation in the page of today's episode. But I you can try to implement the Algorithm yourself without looking at the final implementation. So that you can just practice for a little bit all right. We have our original dependency graph. Where we I want to compile a bunch of scripts and right after deploy them somewhere. What we're going to do with sort you start traversing. The graph wet. Dfs with DEPTFORD search see how useful this algorithm is. We're going to start. Let's say with the note which is associated with the deployment task. So when we go there we're going to traverse all the different dependencies of this particular. Not and we're going to see that there is one edge going out of it and this is the etch which points to the notes that is associated with the task responsible for compiling scripts. We're going to go to this note and here we're going to see that. We don't have any allergy penalties for this tax so we don't have any outgoing edges since we don't have any outgoing edges. We are just going to take this task and push it to our return lists to our result list. It is going to be the first place of our employees order of our two political. Sort from here. We are also going to remove all the edges in the graph that are pointing to this task. We have only wants edge which is pointing from the deployment task to the compilation task. So we were going to remove this edge and we're going to look at all the edges in the graph game. We're going to see that we have the deployment note which does not have any arrows any edges pointing to it so it is free to go. We can take this note and we can put our result list and that's it. We found the logical order of dependency graph. We're first going to compile scripts and tried after that we're going to deploy the application now. Let us look into slightly more complicated example. Let's suppose that we want to cope. Also a bunch of static assets before deploying the obligation so we have our deployment note which points to different notes coping assets and combining scripts cool. So we're going to start from using graph just as we know. We're going to go. First our deployments task we're going to follow all of his dependencies so first we're going to go to the task which is responsible for copying acids. We're going to see that. It doesn't have any outgoing edges. So we're going to take this task. Remove all the incoming edges and push it to our result list right after that. We're going to go back to our deployments task. We're going to see that.
00:10:01 - 00:13:19
It has more outgoing edges. We're going to follow them. We're going to go to our task. Which is responsible for planning scripts we are going to remove all the incoming edges. We're going to push to our result list in our results. Now we're going to have coping assets and compiling scripts and we're going to go back to our deployment task our deployment tasks now doesn't have any outgoing edges at toll so we're going to take it and push to our result list and that's it see how he founded logical order of this graph with three notes now in this case though we could have also swapped the first the first two tasks that we found in push to our result list. It doesn't really matter whether I we're going to copy assets or I. We're going to compile scripts in this particular case. It doesn't really matter because we don't have dependency between two different nodes in the graph so this means that we have two different logical orders of the notes in this graph which means that the logical order boggles sort for a particular graph. He's not unique. This is something important to remember now. In our final example we are going to introduce also a psycho. You mentioned that we have task eight thousand. That's eight depends on thousands and thousands depend on task K. What are we going to the in this case to proceed? You know that taken note and push to our result lists. We need to find out that it doesn't have any ongoing edges but in this case a has an ongoing edge be hasn't ongoing edge and there is nothing we can do well in this case we can keep track of the knows that we visit to this point so we can have visited set. Where I we're pushing a right after proving to be we're pushing B. In our set and here we're following its edge and we're going to again. We're going to see that we have visited a already and here we can throw an error saying that. There is a cycle in the dependency graph. And we don't know what to do. That was pretty much everything we covered how we can handle how we can implement deploy. We discussed that the tortoise not unique and we discussed also what we need to do. In case of a cycle in the graph we do discuss not connected graphs. But in this case. You can imagine that. We're running the logical sort algorithm on top of each individual note in the graph so that were performing the same procedure on all the connected components of the graph and who finally get the result. Now that is everything in general in this episode. We discussed dependency graphs. We talked about deplorables sort and how we can implement it. Every couple of examples that are extremely common for example built systems. Thank you very much for listening to this episode. Learn about the episode's he can fall on twitter at the list of boys. Ursus and recordings is available at podcast dot M. dot com. Thanks for listening.