You have been assigned the task of figuring out in what order following tasks should be executed given their dependencies on other tasks.
If you look at these tasks and draw a graph then it might look like this.
Directed acyclic graph
The graph shown above is a “Directed acyclic graph” . In Directed acyclic graphs if you start following the arrow then you should never be able to get to the node from where you started.
Directed acyclic graphs are great at describing problems where a task is dependent on another set of tasks.
We started off with a set of tasks that are dependent on another set of tasks. To get the solution we need to sort the tasks in such a way that first task is not dependent on any task and the next task is only dependent on task previously done. So basically we need to sort the directed acyclic graph such that the prerequisites are done before getting to the next task.
Sorting of directed acyclic graph in the manner described above is called topological sorting .
Lets write code to find solution to the original problem.
If I execute above code in
ruby 1.9.2 I get following result.
So that is the order in which tasks should be executed .
How Tsort works
tsort requires that following two methods must be implemented.
#tsort_each_node - as the name suggests it is used to iterate over all the nodes in the graph. In the above example all the requirements are stored as a hash key . So to iterate over all the nodes we need to go through all the hash keys. And that can be done using
#each_key method of hash.
#tsort_each_child - this method is used to iterate over all the child nodes for the given node. Since this is directed acyclic graph all the child nodes are the dependencies. We stored all the dependencies of a project as an array. So to get the list of all the dependencies for a node all we need to do is
To make things clearer lets try to solve the same problem in a different way.
When I execute the above code this is the result I get
If you look at the code here I am doing exactly the same thing as in the first case.
Using before and after option
Let’s try to solve the same problem one last time using
after option. Here is the code.
Here is the result.
Sorting of rails initializer
If you have written a rails plugin then you can use code like this
The way rails figures out the exact order in which initializer should be executed is exactly same as I illustrated above. Here is the code from rails.
When Rails boots it invokes a lot of initializers. Rails uses tsort to get the order in which initializers should be invoked. Here is the list of unsorted initializers. After sorting the initializers list is this .
Where else it is used
Bundler uses tsort to find the order in which gems should be installed.
Tsort can also be used to statically analyze programming code by looking at method dependency graph.
Image source: http://en.wikipedia.org/wiki/Directed_acyclic_graph