TSort: Ruby's built-in topological sort algorithm

How does Bundler work out the order to install dependencies? How does rake know which tasks to run? It does a topological sort to work out what depends on what and so which dependency or task to process first.

Take a look at this dependency graph:

Here 1 depends on 2 and 3, 2 depends on 4, 3 depends on 2 and 4, and 4 depends on nothing. Note that his graph is not cyclic – it has no loops – and this technique depends on that.

If we wanted to work out which order of processing, we'd start with 4, that would let 2 be next, then 3 and finally 1. The topological sort order is 4, 2, 3, 1.

Ruby's stdlib has a built-in topological sorting algorithm in the TSort module (and its tsort) method. We just need to tell the algorithm how to find all the nodes and how to find all the children of any node.

Here is the example straight from the API docs (though I feel a bit yuk about monkey patching Hash and prefer the lambda approach demonstrated elsewhere in the docs, but I think this example is easier to understand).

require 'tsort'

class Hash
  include TSort
  alias tsort_each_node each_key
  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

Then we can ask for our data structure to be sorted for us:

h = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
p h.tsort #=> [4, 2, 3, 1]

(And that is how I solved Advent of Code, 2024, day 5)