# magical shell utilities: tsort

Written: 2020-10-30 to 2020-10-31Graph theory comes up a lot more often than you think. Whenever you run a search, download packages, or do anything on the Internet really, you’re reaping its benefits without even realizing. You might be familiar with `sort`

if you’ve done any work in the shell beyond `rm -rf /*`

. It’s useful for working with huge unsorted files, and it’s pretty much an essential tool for any serious scripting. There’s another program with similar intentions, but completely different usecases - `tsort`

. It’s a relative newcomer to the `POSIX.1`

standard that was only canonized in 2017, although it’s been around since 1979.

`tsort`

takes any number of space-separated pairs that represent directed edges in a graph, and outputs each node in topologically sorted order. Its original purpose was for use in `ld`

, the UNIX standard linker. Back in the days when `tar`

actually referred to tape archives, the linker could only do a single pass over a series of object files, in order. With this processing format, problems would arise when the linker tried to figure out symbols or functions that were invoked before they were defined. The solution for this? Represent a program as a directed graph, and generate a topological sorting of symbol references first.

What’s a topological sort?

If you’re unfamiliar with graph theory, here’s a short refresher. A directed graph is a collection of nodes with arrows between each other, pointing towards another node.

I made these figures in `Snapchat`

, bear with me.

If we have two nodes like so,

We can turn it into a directed graph by drawing an arrow that points from A to B. You can look at these arrows as family trees, flow-charts, morphisms, or sloppy artwork.

A special subset of directed graphs are directed acyclic graphs, where you can travel along every path emanating from a node and eventually run out of paths to take. This turns out to be extremely useful in a ton of domains. Whenever you compile a project, you’re creating a dependency graph of modules. Your `Main`

module might depend on `Lib`

, which in turns depends on `Bloat, Parse`

, and `is-even`

. Any dependent relationship between modules forms a directed edge in the overall graph representing the set of all your modules.

When we have cycles in our graph, however, that’s when issues arise. If you don’t keep track of which nodes you’ve been to, you’ll end up going around in circles as you walk the graph. You’ll go from `A`

to `B`

, see that there’s a path from `B`

to `A`

, and keep going. This is a trivial example obviously. You might be thinking, “I’m not that stupid, I’ll just keep track of which nodes I’ve been to.” Sure, but what if the graph was bigger? How could you represent this graph as a 1-dimensional array?

Cycles are fine depending on what you’re trying to do. If you’re writing a game and you need to implement pathfinding around obstacles, you might rely on a breadth-first search or some version of A*. Generally, if you know *where* you want to go, cycles aren’t that big of a deal. Assuming you know which McDonald’s you wanna head to, you probably won’t get tripped up by cloverleaf interchanges on the highway. If you’re trying to map the highway however, this becomes an issue.

By the way, trees are always directed acylic graphs, with the special restriction that a node can only ever be pointed to by one node.

A topological sort is a transformation that’s only valid for graphs without cycles. The idea is to permute every node in such a way that, if a node `A`

points to a node `B`

, `A`

will come before `B`

in the final sorted permutation.

Let’s say we have a DAG that looks like this:

The nodes are approximately sized according to how many outgoing edges they have. If you wanted to walk this graph, visiting every single emoji, which one would you start at? You can only go in the direction that the arrows point.

Clearly, you would start at the emoji that doesn’t have any arrows pointing *toward* it. From there, you can head to `explodey-head`

, `yeehaw`

, and `kewl-dude`

. `explodey-head`

points to `think`

, and `yeehaw`

points to `balloon-face`

. From `balloon-face`

, you head to `kewl-dude`

once more, and you’re out of options. You can see that even though some nodes can share directions, we still don’t have any cycles. The order in which we walked the graph corresponds to its topological sort - we always have to visit the *originating* node of an edge before we can visit the *destination* node. For nodes with the same “depth”, their relative order doesn’t really matter. It doesn’t matter whether we visit `yeehaw`

or `explodey-head`

first, they won’t take it personally.

This kind of traversal strategy is exactly what `tsort`

does. If we convert every edge to a pair of nodes, we can find a traversal path in mere milliseconds. Note that the original permutation of our pairs doesn’t matter.

```
cat emojiGraph.txt
$ explode think
cowboy laugh
ahegao explode
ahegao sunglasses
laugh sunglasses
explode cowboy
ahegao cowboy
tsort emojiGraph.txt
$ ahegao
explode
cowboy
think
laugh
sunglasses
```

Notice that `think`

comes after `cowboy`

, even though they both have edges that are 2 degrees of separation away from our origin. There’s a shorter, 1-degree path to `cowboy`

, so he comes first.

We have our topological sorting now, a 1-dimensional representation of the DAG and a souvenir of our time reenacting of the Emoji Movie:

There’s a really interesting Leetcode problem that involves graph traversal in this way. The prompt goes something like this:

You have a list of `n`

courses you need to take, labeled from `0`

to `n - 1`

. Some courses have prerequisites that need to be satisfied before you can take them. Given `n`

, and a list of pairs `[(a, b)]`

, denoting that `b`

is a prerequisite of `a`

, return the order in which you need to take these courses. Notice that the ordering of edges is backwards from our `tsort`

example.

So let’s go with a simple example. We’ll use part of my old university transcript.

```
= [ (HMB265, BIO120)
courses BCH311, BCH210)
, (HAJ453, HMB312)
, (HMB204, BIO130)
, (HAJ453, BIO220)
, (BCH210, CHM136)
, (PSL301, BIO130)
, (HMB312, HMB265)
, (HMB312, HMB204)
, (BIO220, BIO120)
, (HMB265, BIO130)
, ( ]
```

Where do we go with this? How the hell do I graduate if my course schedule is a complete mess? (In real life, there are credit requirements, corequisites and sometimes prerequisite requirements aren’t actually mandatory, but we’ll assume a simple dependency graph here.)

Let’s reshuffle this list a bit by hand now to make it a little more clear where we’re starting. Let’s try grouping together our courses by their incoming edges - in other words, assembling their total prerequisites.

```
= {
courseRequirements BIO120: [],
BIO130: [],
CHM136: [],
BIO220: [BIO120],
HMB204: [BIO130],
HMB265: [BIO120],
BCH210: [CHM136],
PSL301: [BIO130]
BCH311: [BCH210],
HMB312: [HMB265, HMB204],
HAJ453: [BIO220, HMB312]
}
```

If we look at these courses as nodes, we can see immediately that there are 3 sources in our graph, nodes without any incoming edges. Their `in-degrees`

are zero, and so we know that we need to start from there. In our context, `BIO120, BIO130,`

and `CHM136`

are courses that we can take immediately, and not have to worry about the registrar kicking us out halfway through the semester.

Now what? It seems like `BCH210`

requires `CHM136`

, so we would have to take it one semester afterwards. Same goes for `HMB265, BIO220, HMB204,`

and `PSL301`

. Let’s skip ahead to Christmas break.Our first courses are done. We don’t care about them anymore, and they’re on our transcript.

```
= [ BIO120
transcript BIO130
, CHM136
,
]
```

We can now remove these completed courses from our graph, and all their outgoing edges pointing to higher-level courses. This also means removing the incoming edges as well. Here’s our new graph:

```
= {
courseRequirements HMB265: [],
BIO220: [],
HMB204: [],
PSL301: [],
BCH210: [],
BCH311: [BCH210],
HAJ453: [HMB312, BIO220]
HMB312: [HMB204]
}
```

Nice! We’ve finished all the requirements for 5 courses! It’s pretty clear what our next semester is gonna to look like. After our second semester, our transcript has grown:

```
= [ BIO120
transcript BIO130
, CHM136
, -- second semester
HMB265
, BIO220
, HMB204
, PSL301
, BCH210
, ]
```

Are we done yet? Nope. Looking back at `courseRequirements`

, `HAJ453`

still requires courses that we haven’t gotten around to yet. Let’s reorder our requirements list again.

```
= {
courseRequirements BCH311: [],
HMB312: []
HAJ453: [HMB312]
}
```

We take `BCH311`

and `HMB312`

next, before we can do `HAJ453`

in our senior year. Electives and failed courses aside - in total, it took us 4 iterations to go from being clueless freshmen to becoming well-respected biologists.

```
= [ BIO120
transcript BIO130
, CHM136
, -- second semester
HMB265
, BIO220
, HMB204
, PSL301
, BCH210
, -- third semester
BCH311
, HMB312
, -- fourth semester
HAJ453
, ]
```

Do you see the pattern in our strategy? We did a topological sort by hand, using Kahn’s algorithm. Starting off with a randomly permuted list of elements `(a, b)`

, where `b`

has to be fulfilled before `a`

, we identify which courses we’re eligible for (nodes with no incoming edges). Next, we “visit” these nodes by taking the courses, confident that we’re not lacking any background knowledge. After removing our visited nodes from the graph, we delete their edges and take note of the next batch of zero-degree nodes. Keep doing this until we’re out of courses to take, and the University shoves a diploma in our hands then cancels our health insurance.

This sucks to work out by hand, and we only had to deal with 11 courses. What about 40? (flashbacks to dealing with U of T’s degree explorer). What if we wanted to take every single course at the University? Where do we even start then? We need computers - let’s express this in their language.

```
def gradPlan(requirements):
= []
transcript
# each entry corresponds to a set of unfulfilled requirements
= defaultdict(set)
preReqs
for (prereq, course) in requirements:
preReqs[course].add(prereq)
# start our frosh week by selecting courses we can enroll in
=
eligibleCourses list(
filter(lambda course: not preReqs[course], preReqs)
)
while eligibleCourses:
= eligibleCourses.pop() # take any course that we're allowed to
current # add that to our transcript
transcript.append(current)
# now that we've taken the class, see which courses we've fulfilled a prereq for
= filter(lambda course: current in preReqs[course], preReqs)
nextCourses
for nxt in nextCourses:
# mark current as done
preReqs[nxt].discard(current) if not preReqs[nxt]:
eligibleCourses.append(nxt)# if we've satisfied the requirements, we're eligible to enroll now
return transcript # magna cum laude, baby
```

This isn’t syntactically valid `Python`

, and there are optimizations we can make. But I think it illustrates the algorithm pretty well. At any point in time, we can only take courses that we’re eligible to enroll in. The relative order of courses doesn’t matter if they’re at the same “depth” within the graph. For instance, we can take `BIO120`

at the same time as `CHM136`

since neither of them rely on any prerequisites, so it doesn’t matter which of the two comes first in our transcript. For courses that directly depend on these, however, we can only take them after we’re finished. How are you supposed to know understand glycolysis if you don’t even know what electrons are?

Now that we know the theory behind topological sorting, we can add it to our toolkit. Luckily, you won’t have to implement `tsort`

by hand very often, because real engineers avoid code duplication at all costs. Here’s an easy solution to the Leetcode problem:

```
from subprocess import check_output, DEVNULL
def courseSchedule(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
= [" ".join(map(str, reversed(pair))) for pair in prerequisites]
rev_pair_strs = bytes("\n".join(rev_pair_strs), 'UTF-8')
formatted
= check_output(["tsort"], input=formatted, stderr=DEVNULL)
tsorted
return list(map(int, tsorted.splitlines()))
```

Beautiful.

It turns out that `tsort`

isn’t used in `ld`

anymore (`grep`

ped for it just now), but it’s a cool utility that can come in handy. Don’t listen to O’Reilly and their pessimism. Next time you run into a problem where you have to consider the relationships between objects within a category, see if you can reduce it to graph traversal. This is usually my go-to intuition when I’m doing Leetcode problems, but the site is biased towards graph-type questions anyway.