# An All-in-One DAG Toolkit

*HTR has kindly translated this post to Russian.*

I’d like to tell you about an algorithm that I’m frankly annoyed I didn’t discover earlier.

The algorithm is Tarjan’s Strongly Connected Components (or SCCs) algorithm, and as the name suggests, it decomposes a directed graph into its strongly connected components. A directed graph is one where the edges have a direction associated with them, and a strongly connected component of a graph is a subgraph where each node can be reached from every other node, i.e. there’s a directed cycle somewhere in this subgraph.

So why does this matter? I don’t recall ever having the desire to deeply know the SCCs of a particular graph.

Let’s look at a different problem. Given a directed graph, how do we know if it is acyclic? The context here is that I was wondering how difficult it would be literally draw a Git commit history as a graph and render that to a repo. Git commits form a directed acyclic graph (DAG), which is a directed graph without cycles, and I wanted to validate a user-drawn graph as well as process it.

Consulting the
oracle
yielded the concept of a topological
sort, which is where
vertices are ordered such that for all vertices *u* and *v*, if there is an
edge from *u* to *v*, *u* appears earlier than *v* in the sorted output. The
directed edges for a Git commit graph are in the opposite direction from what
we want though, because they point from children to parents. What we really
want is a reverse topological sort. It would also be nice if I could somehow
highlight the subgraphs of an invalid graph that are responsible for it being
invalid.

This is where we come back to the SCCs of a graph. If there are any SCCs of more than one vertex, the graph is not a DAG and those SCCs are the cause of this. Collapsing the SCCs of a directed graph to a single vertex always leads to a DAG and this is known as the condensation of a directed graph, which I think is a nice way to visualise the relationship between SCCs and DAGs.

Alright, so we do actually want to know the SCCs of this graph, but first we
want to try to sort it topologically and reverse that order if that is
possible, otherwise we calculate the SCCs and identify the offending ones. This
seems a bit messy for graph properties that seem somewhat related. How cool
would it be if there were an algorithm that could calculate the SCCs and a
reverse topological sort for us *at the same time*?

It turns out that Tarjan’s SCCs algorithm does exactly that! You’d think that its performance might not be great because it does two things at once, but it is linear in the number of edges and vertices, and has better constant factors than Kosaraju’s algorithm, which only computes SCCs. Here it is as pseudocode:

```
algorithm tarjan is
input: graph G = (V, E)
output: set of strongly connected components (sets of vertices)
index := 0
S := empty array
for each v in V do
if (v.index is undefined) then
strongconnect(v)
end if
end for
function strongconnect(v)
// Set the depth index for v to the smallest unused index
v.index := index
v.lowlink := index
index := index + 1
S.push(v)
v.onStack := true
// Consider successors of v
for each (v, w) in E do
if (w.index is undefined) then
// Successor w has not yet been visited; recurse on it
strongconnect(w)
v.lowlink := min(v.lowlink, w.lowlink)
else if (w.onStack) then
// Successor w is in stack S and hence in the current SCC
// Note: The next line may look odd - but is correct.
// It says w.index not w.lowlink; that is deliberate and from the original paper
v.lowlink := min(v.lowlink, w.index)
end if
end for
// If v is a root node, pop the stack and generate an SCC
if (v.lowlink = v.index) then
start a new strongly connected component
repeat
w := S.pop()
w.onStack := false
add w to current strongly connected component
while (w != v)
output the current strongly connected component
end if end function
```

The algorithm does a depth-first search, keeping track of two properties for
each vertex: when it was encountered (the *index*) and the lowest index of any
vertex reachable from this vertex (the *lowlink*). It pushes vertices on to a
stack as it goes and outputs a strongly connected component when it finds a
completely processed vertex whose index and lowlink are the same.

As presented it is very imperative and I like Haskell, but fortunately imperative Haskell is pretty straightforward and I have an implementation here.

This seems like an incredibly niche use case, but validating and processing DAGs in this way happens surprisingly frequently. Consider a build process where inputs and outputs are nodes and their relationships are directed edges. The presence of an SCC with more than one vertex indicates a cyclic dependency, and dependencies need to be built before the nodes that depend on them, which implies a reverse topological sort. This generalises to dataflow programming, where loops need to be identified (and usually eliminated). I like to think of this algorithm as an all-in-one DAG toolkit.

We can also use it to solve
2SAT, which is the problem of
determining whether boolean variables in series of constraints of the form `a || b`

can be assigned T and F values such that all constraints hold. This is
discussed
here
but boils down to encoding the constraints as nodes and edges, calculating the
SCCs, and processing the output in reverse topologically sorted order. An
advantage to doing it this way is that the process can stop at the first SCC
that indicates unsatisfiability. I have an implementation of this
here.

Discovering this algorithm got me excited about theoretical computer science and reminded me that algorithms can be fun, interesting, and an opportunity to marvel at the music of the spheres. I’m curious to know what other equally awesome algorithms are out there. Which one’s your favourite?

Thanks to Annie Cherkaev for the title and feedback, and Iain McCoy for suggesting a more functional approach.