Back to Blog

tsort in ruby and rails initializers

on March 16, 2012

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

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


You might also like

If you liked this blog post, check out similar ones from BigBinary