You have been assigned the task of figuring out in what order following tasks should be executed given their dependencies on other tasks.
1Task11 takes input from task5 and task7. 2Task10 takes input from task11 and task3. 3Task9 takes input from task8 and task11. 4Task8 takes input from task3 and task7. 5Task2 takes input from task11.
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 .
TSort
Ruby provides TSort which allows us to implement "topological sorting". Here is source code or tsort .
Lets write code to find solution to the original problem.
1require "tsort" 2 3class Project 4 include TSort 5 6 def initialize 7 @requirements = Hash.new{|h,k| h[k] = []} 8 end 9 10 def add_requirement(name, *requirement_dependencies) 11 @requirements[name] = requirement_dependencies 12 end 13 14 def tsort_each_node(&block) 15 @requirements.each_key(&block) 16 end 17 18 def tsort_each_child(name, &block) 19 @requirements[name].each(&block) if @requirements.has_key?(name) 20 end 21 22end 23 24p = Project.new 25p.add_requirement(:r2, :r11) 26p.add_requirement(:r8, :r3, :r7) 27p.add_requirement(:r9, :r8, :r11) 28p.add_requirement(:r10, :r3, :r11) 29p.add_requirement(:r11, :r7, :r5) 30 31puts p.tsort
If I execute above code in ruby 1.9.2 I get following result.
1r7 2r5 3r11 4r2 5r3 6r8 7r9 8r10
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 @requirements[name].each.
Another example
To make things clearer lets try to solve the same problem in a different way.
1require "tsort" 2 3class Project 4 attr_accessor :dependents, :name 5 def initialize(name) 6 @name = name 7 @dependents = [] 8 end 9end 10 11class Sorter 12 include TSort 13 14 def initialize(col) 15 @col = col 16 end 17 18 def tsort_each_node(&block) 19 @col.each(&block) 20 end 21 22 def tsort_each_child(project, &block) 23 @col.select { |i| i.name == project.name }.first.dependents.each(&block) 24 end 25end 26 27r2 = Project.new :r2 28r3 = Project.new :r3 29r5 = Project.new :r5 30r7 = Project.new :r7 31r8 = Project.new :r8 32r9 = Project.new :r9 33r10 = Project.new :r10 34r11 = Project.new :r11 35 36r2.dependents << r11 37 38r8.dependents << r3 39r8.dependents << r7 40 41r9.dependents << r8 42r9.dependents << r11 43 44r10.dependents << r3 45r10.dependents << r11 46 47r11.dependents << r7 48r11.dependents << r5 49 50col = [r2, r3, r5, r7, r8, r9, r10, r11] 51 52result = Sorter.new(col).tsort 53puts result.map(&:name).inspect
When I execute the above code this is the result I get
1[:r7, :r5, :r11, :r2, :r3, :r8, :r9, :r10]
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 before and after option. Here is the code.
1require "tsort" 2 3class Project 4 attr_accessor :before, :after, :name 5 def initialize(name, options = {}) 6 @name = name 7 @before, @after = options[:before], options[:after] 8 end 9end 10 11class Sorter 12 include TSort 13 14 def initialize(col) 15 @col = col 16 end 17 18 def tsort_each_node(&block) 19 @col.each(&block) 20 end 21 22 def tsort_each_child(project, &block) 23 @col.select { |i| i.before == project.name || i.name == project.after }.each(&block) 24 end 25end 26 27r2 = Project.new :r2, after: :r11 28r3 = Project.new :r3, before: :r8 29r5 = Project.new :r5, before: :r11 30r7 = Project.new :r7, before: :r11 31r8 = Project.new :r8, after: :r7, before: :r9 32r9 = Project.new :r9, after: :r11 33r10 = Project.new :r10, after: :r3 34r11 = Project.new :r11, before: :r10 35 36 37col = [r5, r2, r11, r3, r10, r9, r7, r8, r5] 38 39result = Sorter.new(col).tsort 40puts result.map(&:name).inspect
Here is the result.
1[:r5, :r7, :r11, :r2, :r3, :r10, :r8, :r9]
Sorting of rails initializer
If you have written a rails plugin then you can use code like this
1initializer 'my_plugin_initializer',after: 'to_prepare', before: 'before_eager_load' do |app| 2 .... 3end
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.
1alias :tsort_each_node :each 2def tsort_each_child(initializer, &block) 3 select { |i| i.before == initializer.name || i.name == initializer.after }.each(&block) 4end 5............ 6............ 7initializers.tsort.each do |initializer| 8 initializer.run(*args) if initializer.belongs_to?(group) 9end
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