Deobfuscated topological sort

I have a really hard time with algorithm examples that are in books or available online. They might have a bunch of single-letter variable names. Or maybe they rely on language-specific features like list comprehensions. Or maybe lines do multiple things at once. Or even worse, maybe it’s multiple list comprehensions in one line. Or the pseudocode uses 1-indexed array indexes. And what’s the difference between x++ and ++x? I haven’t had to think about that since my second college computer science class.

Maybe it’s just me.

Anyway, I was trying to figure out how to compute topological sorts from a graph. Below is a heavily annotated explanation of it. It’s in Ruby cause it’s the language I’m most familiar with, but I tried avoiding unique features and conventions. So hopefully it makes some sense.

Oh, I should mention that tsort‘s runtime is O(number of nodes) since each node gets processed once. Oh and Ruby has an implementation of topological sort in its standard library. It’s called tsort.

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
def tsort(graph)
  seen = {}
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
  possible_ordering = [nil] * graph.size
  current_position = graph.size - 1

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.
  depth_first_search = lambda do |source|
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
        return true   # Since we can skip this

    seen[source] = true

    # The loop ...

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

    seen[source] = false

    graph[source].each do |dest|
      is_tsortable =

      if !is_tsortable
        return is_tsortable

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

    return seen[source]

  node_is_tsortable = []

  graph.each do |source, dests|
    is_tsortable =

  if node_is_tsortable.all?

I’m curious if this is helpful. Perhaps I’ll try to do some more.

Side note, this is un-code-golfed, but it isn’t code-bowling. What’s a sport that aims for “the middle”? Curling? Is this code curling?

Posted on 2020-06-21 11:10 PM
© Copyright 2008–2020 Zach Ahn