tsort in ruby and rails initializers

You have been assigned the task of figuring out in what order following tasks should be executed given their dependencies on other tasks.

Task11 takes input from task5 and task7.
Task10 takes input from task11 and task3.
Task9 takes input from task8 and task11.
Task8 takes input from task3 and task7.
Task2 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.

require "tsort"

class Project
  include TSort

  def initialize
    @requirements = Hash.new{|h,k| h[k] = []}
  end

  def add_requirement(name, *requirement_dependencies)
    @requirements[name] = requirement_dependencies
  end

  def tsort_each_node(&block)
    @requirements.each_key(&block)
  end

  def tsort_each_child(name, &block)
    @requirements[name].each(&block) if @requirements.has_key?(name)
  end

end

p = Project.new
p.add_requirement(:r2, :r11)
p.add_requirement(:r8, :r3, :r7)
p.add_requirement(:r9, :r8, :r11)
p.add_requirement(:r10, :r3, :r11)
p.add_requirement(:r11, :r7, :r5)

puts p.tsort

If I execute above code in ruby 1.9.2 I get following result.

r7
r5
r11
r2
r3
r8
r9
r10

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.

require "tsort"

class Project
  attr_accessor :dependents, :name
  def initialize(name)
    @name = name
    @dependents = []
  end
end

class Sorter
  include TSort

  def initialize(col)
    @col = col
  end

  def tsort_each_node(&block)
    @col.each(&block)
  end

  def tsort_each_child(project, &block)
    @col.select { |i| i.name == project.name }.first.dependents.each(&block)
  end
end

r2  = Project.new :r2
r3  = Project.new :r3
r5  = Project.new :r5
r7  = Project.new :r7
r8  = Project.new :r8
r9  = Project.new :r9
r10 = Project.new :r10
r11 = Project.new :r11

r2.dependents << r11

r8.dependents << r3
r8.dependents << r7

r9.dependents << r8
r9.dependents << r11

r10.dependents << r3
r10.dependents << r11

r11.dependents << r7
r11.dependents << r5

col = [r2, r3, r5, r7, r8, r9, r10, r11]

result = Sorter.new(col).tsort
puts result.map(&:name).inspect

When I execute the above code this is the result I get

[: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.

require "tsort"

class Project
  attr_accessor :before, :after, :name
  def initialize(name, options = {})
    @name = name
    @before, @after = options[:before], options[:after]
  end
end

class Sorter
  include TSort

  def initialize(col)
    @col = col
  end

  def tsort_each_node(&block)
    @col.each(&block)
  end

  def tsort_each_child(project, &block)
    @col.select { |i| i.before == project.name || i.name == project.after }.each(&block)
  end
end

r2  = Project.new :r2, after: :r11
r3  = Project.new :r3, before: :r8
r5  = Project.new :r5, before: :r11
r7  = Project.new :r7, before: :r11
r8  = Project.new :r8, after: :r7, before: :r9
r9  = Project.new :r9, after: :r11
r10 = Project.new :r10, after: :r3
r11 = Project.new :r11, before: :r10


col = [r5, r2, r11, r3, r10, r9, r7, r8, r5]

result = Sorter.new(col).tsort
puts result.map(&:name).inspect

Here is the result.

[: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

initializer 'my_plugin_initializer',after: 'to_prepare', before: 'before_eager_load' do |app|
 ....
end

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.

alias :tsort_each_node :each
def tsort_each_child(initializer, &block)
  select { |i| i.before == initializer.name || i.name == initializer.after }.each(&block)
end
............
............
initializers.tsort.each do |initializer|
  initializer.run(*args) if initializer.belongs_to?(group)
end

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