I own a fair number of computer books that I have never read from cover-to-cover (and a slim few that I have). I tend to dip in-and-out of programming books—absorbing a chapter here and a chapter there. One of the books I pick up with some frequency is Algorithms Unlocked by Thomas H. Cormen, who is one of the authors of the often cited CLRS which is a hugely comprehensive textbook covering the topic of algorithms.

Algorithms Unlocked, in contrast to its massive textbook counterpart, is a slim and snappy little book filled with all kinds of neat algorithms. It doesn’t focus on any specific language implementations, but rather describes algorithms in pseudo-code and plain English. After an algorithm is introduced, there is a discussion of the Big-O and Big-Θ run-times.

One of the things I like to do is read about a particular algorithm and test my understanding by implementing the pseudo code in some programming language. Since I recently ran into a graph problem while working on blubber —which is a Go project—I figured I’d implement the first algorithm in the Directed Acyclic Graph (DAG) chapter in Go.

Also, since I haven’t written anything on my blog in a while, I figured I’d write up my adventure!

Directed Graphs Represented in Go

The first problem when attempting to create a topographic sort of a graph in any programming language is figuring out how to represent a graph. I chose a map with an int as a key (which seems pretty much like a slice but the use of a map makes this implementation type agnostic). Each vertex n is represented with a key in the map, each vertex that adjacent to n—m—is stored as a slice in the map referenced by the key n.

package main

import "fmt"

func main() {
    // Directed Acyclic Graph
    vertices := map[int][]int{
        1:  []int{4},
        2:  []int{3},
        3:  []int{4, 5},
        4:  []int{6},
        5:  []int{6},
        6:  []int{7, 11},
        7:  []int{8},
        8:  []int{14},
        9:  []int{10},
        10: []int{11},
        11: []int{12},
        13: []int{13},
        14: []int{},
    }

    // As yet unimplemented topographicalSort
    fmt.Println(topographicalSort(vertices))
}

Topographical Sort

I implemented the algorithm in a function named topographicalSort. The inline comments are the pseudo-code from the book—also noteworthy I stuck with the unfortunate variable names from the book (although somewhat adapted to camelCase to stick, a bit, to Go conventions):

// topographicalSort Input: g: a directed acyclic graph with vertices number 1..n
// Output: a linear order of the vertices such that u appears before v
// in the linear order if (u,v) is an edge in the graph.
func topographicalSort(g map[int][]int) []int {
    linearOrder := []int{}

    // 1. Let inDegree[1..n] be a new array, and create an empty linear array of
    //    verticies
    inDegree := map[int]int{}

    // 2. Set all values in inDegree to 0
    for n := range g {
        inDegree[n] = 0
    }

    // 3. For each vertex u
    for _, adjacent := range g {
        // A. For each vertex *v* adjacent to *u*:
        for _, v := range adjacent {
            //  i. increment inDegree[v]
            inDegree[v]++
        }
    }

    // 4. Make a list next consisting of all vertices u such that
    //    in-degree[u] = 0
    next := []int{}
    for u, v := range inDegree {
        if v != 0 {
            continue
        }

        next = append(next, u)
    }

    // 5. While next is not empty...
    for len(next) > 0 {
        // A. delete a vertex from next and call it vertex u
        u := next[0]
        next = next[1:]

        // B. Add u to the end of the linear order
        linearOrder = append(linearOrder, u)

        // C. For each vertex v adjacent to u
        for _, v := range g[u] {
            // i. Decrement inDegree[v]
            inDegree[v]--

            // ii. if inDegree[v] = 0, then insert v into next list
            if inDegree[v] == 0 {
                next = append(next, v)
            }
        }
    }

    // 6. Return the linear order
    return linearOrder
}

In our vertices DAG, the only vertices with an inDegree of 0 are 1, 2, and 9, so in a topographic sort one of those number would be first. Running this code seems to support that assertion:

$ go build -o topo_sort
$ ./topo_sort
[9 1 2 10 3 4 5 6 7 11 8 12 14]

In fact, all the vertices with no inDegrees ended up right at the beginning of this slice.

Can you dig it?

DAGs are ubiquitous and have many uses both inside and outside of computers. I keep running into them again and again: I stare this dad-joke cold in the face, once again, this evening.

Algorithms Unlocked talks in approachable language about using a DAG to graph and understand things like the order of operations for cooking a meal or for putting on hockey goalie equipment—I find the plain-spoken explanations charming and helpful. I dig this book, and this is far from the first exercise I’ve hacked through out of it. I’m sure I’ll be picking up this book again sometime in the near future–who knows?–I might even finish it!