BigBinary Blog

We write about Ruby on Rails, React.js, React Native, remote work, open source, engineering and design.

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

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 .


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 ={|h,k| h[k] = []}

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

  def tsort_each_node(&block)

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


p =
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.


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 = []

class Sorter
  include TSort

  def initialize(col)
    @col = col

  def tsort_each_node(&block)

  def tsort_each_child(project, &block) { |i| == }.first.dependents.each(&block)

r2  = :r2
r3  = :r3
r5  = :r5
r7  = :r7
r8  = :r8
r9  = :r9
r10 = :r10
r11 = :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 =

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]

class Sorter
  include TSort

  def initialize(col)
    @col = col

  def tsort_each_node(&block)

  def tsort_each_child(project, &block) { |i| i.before == || == project.after }.each(&block)

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

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

result =

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|

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.after }.each(&block)
initializers.tsort.each do |initializer|*args) if initializer.belongs_to?(group)

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:

Neeraj Singh in Rails
16, 2012

You might also like

Rails 6.1 adds support for PostgreSQL interval data type

Rails 6.1 allows per environment configuration support for Active Storage

Rails 6.1 adds support for belongs_to to has_many inversing

Rails 6.1 adds strict_loading to warn lazy loading associations

Rails 6.1 adds where.associated to check association presence

Subscribe to our newsletter