=begin
This implementation of topological-sort requires that the graph is represented
as a Hash with the form of { source => [destination1, destination2, ...] }.
Here's an example of one:

    a ---> b ---> c
     \
      \--> d

    {
      a => [b, d],  # Because a points to b and d
      b => [c],     # Because b points to c
      c => [],      # Because c doesn't point to anything
      d => [],      # Because d doesn't point to anything either
    }

It returns an array of topologically sorted nodes. If it encounters a cycle, it
returns an empty array
=end
def tsort(graph)
  seen = {}
=begin
This algorithm fills out the array from the end to the start. Optionally you can
append nodes to the end of an array, then flip the array right before returning
it.
=end
  possible_ordering = [nil] * graph.size
  current_position = graph.size - 1

=begin
Lambdas are basically functions... In Python, you can define methods in methods,
and those inner methods have access to the variables that were defined in the
outer one. You can't do that in Ruby, but you can basically do the same thing
with lambdas

Anyway. This "inner function" is an implementation of depth first search with a
couple variations. If there are any circular dependencies, it returns false.
Otherwise it returns true.
=end
  depth_first_search = lambda do |source|
=begin
The `seen` hash is often implemented with "colors", where { node => color }.
This is basically that too, but it gives us a bit of a shortcut.

    seen[source] = false  # This means that a search is in progress. If this
                          # `depth_first_search` function comes across a
                          # `seen[source] == false`, that means that there is a
                          # circular dependency
    seen[source] = true   # This means that we already ran DFS successfully for
                          # this node and can be ignored while we continue to
                          # compute the tsort

In other words, `seen` is being used for two purposes. We can easily split them
into two different variables which might be cleaner to understand but would
require a bit more code.

    current_search = []  # This is a stack where we can `push` and `pop` the
                         # current node.
    seen = {}            # The value of `seen` will always be true

If we went with that, the code might look something like this. Note though that
`current_search.include?(source)` runs at `O(N)`, so that would increase the
worse case runtime to `O(N^2)`.

    if seen[source]
      if current_search.include?(source)
        return false  # Because there's a cycle
      else
        return true   # Since we can skip this
      end
    end

    seen[source] = true
    current_search.push(source)

    # The loop ...

    # And replace the `seen[source] = true` after the loop with:
    current_search.pop
=end
    if seen.key?(source)
      return seen[source]
    end

    seen[source] = false

    graph[source].each do |dest|
      is_tsortable = depth_first_search.call(dest)

      if !is_tsortable
        return is_tsortable
      end
    end

    seen[source] = true
    possible_ordering[current_position] = source
    current_position -= 1

    return seen[source]
  end

  node_is_tsortable = []

  graph.each do |source, dests|
    is_tsortable = depth_first_search.call(source)
    node_is_tsortable.push(is_tsortable)
  end

  if node_is_tsortable.all?
    possible_ordering
  else
    []
  end
end