Why your topological sort gives a different answer on every run

You have a few tasks, and some of them depend on others. You put them in a graph, sort it topologically, and print the order. Then you run the program again and get a different order. Both are correct, but your test that compares against an expected slice fails every few runs. And the file you generate from the order changes every time you rebuild it, even though nothing changed.

This happened in gograph, the Go graph library I maintain, until version 0.8. This post explains where the randomness came from, how the library got rid of it without changing its API, and what to do when insertion order isn't enough. The pipeline from the next section is on gograph.dev, where you can step through the sort instead of only reading the code.

Where the randomness comes from

Here's a small build pipeline. Four tasks can run in any order, and release has to wait for all of them:

g := gograph.New[string](gograph.Acyclic())

release := g.AddVertexByLabel("release")
for _, name := range []string{"lint", "vet", "test", "build"} {
    _, _ = g.AddEdge(g.AddVertexByLabel(name), release)
}

for i := 0; i < 5; i++ {
    order, _ := gograph.TopologySort(g)
    // print the labels
}

With gograph v0.7.2, five calls in the same process gave this:

vet test build lint release
lint vet test build release
lint vet test build release
test build lint vet release
lint vet test build release

A topological sort only promises that every vertex comes after the vertices it depends on. Whenever more than one vertex is ready at the same time, the algorithm has to pick one, and any choice is valid. Here, all four tasks are ready from the start.

The graph stored its vertices in a map[T]*Vertex[T], and GetAllVertices built its result by ranging over it. TopologySort then counted the incoming edges of each vertex in another map and found the starting vertices by ranging over that one. The Go spec says the iteration order of a map "is not specified and is not guaranteed to be the same from one iteration to the next", and the runtime randomizes it on purpose, so code can't come to depend on it. So the tie-break was random, and so was the result. That's also why the fix needed more than one change. The maps are still there for lookups, but every loop over a map on that path had to become a loop over a slice.

The same thing happened in every function built on top of the vertex list: the strongly connected component algorithms (Tarjan, Kosaraju and Gabow), maximal cliques, Girvan-Newman communities and transitive reduction. They all gave correct results, but not the same correct result twice. gograph.dev runs those too. Tarjan on a call graph is the one that finds the groups of vertices that can all reach each other.

Keeping the insertion order

The fix is to remember the order the vertices were added. The graph still needs the map, because finding a vertex by its label has to stay fast. Next to it, it now keeps a slice, and each vertex stores its index in that slice:

func (g *baseGraph[T]) addVertex(v *Vertex[T]) *Vertex[T] {
    // ...
    g.vertices[v.label] = v
    v.position = len(g.order)
    g.order = append(g.order, v)
    // ...
}

Adding is an append. Removing is the only tricky part, since deleting from the middle of a slice means moving everything after it. Instead, a removed vertex leaves an empty slot, and once more than half of the slots are empty, the remaining vertices move to the front:

func (g *baseGraph[T]) removeFromOrder(v *Vertex[T]) {
    g.order[v.position] = nil
    g.removedCount++
    if g.removedCount <= len(g.order)/2 {
        return
    }

    n := 0
    for _, u := range g.order {
        if u != nil {
            u.position = n
            g.order[n] = u
            n++
        }
    }
    clear(g.order[n:])
    g.order = g.order[:n]
    g.removedCount = 0
}

Each compaction moves at most as many vertices as were removed since the last one, so a removal still costs O(1) on average.

GetAllVertices now walks the slice and skips the empty slots. Edges got the same treatment: AllEdges groups them by source vertex in insertion order, and within each vertex they're in the order they were added. After that, the algorithms that ranged over maps were changed to range over these slices.

The same program with v0.8.1:

lint vet test build release
lint vet test build release
lint vet test build release
lint vet test build release
lint vet test build release

lint was added first, so it comes first. When several vertices are ready, TopologySort now takes them in the order they were added. All the algorithms listed above give the same result on every run for a graph built the same way. The build pipeline on gograph.dev is this case: lint, vet, test, build, then release.

The change was also faster. Walking a slice beats ranging over a map, and in my benchmarks GetAllVertices got about 6 times faster, AllEdges 3 times and EdgesOf 5 times. On a graph with 100,000 vertices, TopologySort takes about 7 ms.

None of the signatures changed. The order was never documented before, so code that didn't depend on it keeps working, and the docs now say what the order is.

When insertion order isn't enough

Insertion order moves the problem to whoever builds the graph. If you fill the graph from a map, from files listed in directory order, or from results that come back from goroutines, the insertion order is random again, and so is the sort. Here's the same pipeline built twice, with the tasks added in a different order:

a := build([]string{"lint", "vet", "test", "build"})
b := build([]string{"build", "test", "vet", "lint"})

TopologySort follows each graph's insertion order, so the results differ:

lint vet test build release
build test vet lint release

For this case, 0.8 added StableTopologySort. It takes a compare function, and whenever several vertices are ready, it picks the smallest one:

stableA, _ := gograph.StableTopologySort(a, cmp.Compare[string])
stableB, _ := gograph.StableTopologySort(b, cmp.Compare[string])

build lint test vet release
build lint test vet release

The ready vertices go in a heap ordered by the compare function, so the sort runs in O((V + E) log V) instead of O(V + E). On the 100,000 vertex graph it takes about 15 ms, twice as long as TopologySort. That's the price of an order that doesn't depend on how the graph was built. If you build the graph in a fixed order anyway, TopologySort is enough. gograph.dev runs that stable sort on the same pipeline, and both graphs come out build lint test vet release.

The general lesson

Any algorithm that has to make an arbitrary choice, like which ready vertex goes next or which neighbor to visit first, takes that choice from whatever order its data is in. If the data is in a map, the choice is random. The algorithm is still correct, but its output can't be tested with a simple comparison, cached or diffed.

The fix doesn't have to be expensive. Keep a slice next to the map when you need insertion order, or sort the candidates when you need an order that doesn't depend on history. It's worth deciding which one your API promises and writing it in the docs, because someone will eventually depend on it.

gograph is a generic graph library for Go with no dependencies outside the standard library. Besides topological sorting, it covers traversal, shortest paths, strongly connected components and partitioning. Version 0.8 also added a dag package for dependency questions and encoding/mermaid for drawing graphs. gograph.dev runs the ones in the current release, step by step, and each page shows how long that run took on the server.

• The sort from this post: https://gograph.dev/algorithms/topological-sort/build-pipeline
• The stable sort: https://gograph.dev/algorithms/stable-topological-sort/build-pipeline
• All of the runs: https://gograph.dev
• Repository: https://github.com/hmdsefi/gograph
• Documentation: https://pkg.go.dev/github.com/hmdsefi/gograph
• The change itself: https://github.com/hmdsefi/gograph/pull/167