Stable topological sort
Puts the vertices of a graph without cycles in an order where every edge points forward, taking the ready vertex that comes first alphabetically.
Time complexity O((V+E) log V), gograph function gograph.StableTopologySort.
How it works
The stable topological sort works like Kahn's algorithm, but the ready vertices wait in a priority queue instead of a plain queue. Whenever more than one is ready, it takes the smallest by the compare function you pass, such as cmp.Compare for alphabetical labels.
As long as compare only returns zero for equal labels, the order depends on the labels alone, not on the order the graph was built. Two programs that add the same edges in a different order get the same result, which keeps generated files and test output from changing between runs. The priority queue adds a log factor, for O((V+E) log V). Like gograph.TopologySort, it returns ErrDAGHasCycle when the graph has a cycle.
Use it when the order is shown to people or written to a file, such as the steps of a build plan, and every run has to give the same result.
Go module graph
The module graph of github.com/gin-gonic/gin v1.9.1, as go mod graph prints it. Each edge points from a module to a module version it requires.
A directed graph with 62 vertices and 116 edges.
In what order can the modules be listed, so that each one comes before every module version it requires?
In this order, every edge points forward, and vertices that are ready together go in alphabetical order: github.com/gin-gonic/gin, github.com/bytedance/sonic@v1.9.1, github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311, github.com/bytedance/sonic@v1.5.0, github.com/chenzhuoyu/base64x@v0.0.0-20211019084208-fb5309c8db06, and so on to rsc.io/pdf@v0.1.1.
Step by step
- Count the incoming edges of each vertex, its in-degree. Only github.com/gin-gonic/gin has none, so it starts the ready list, which stays in alphabetical order. Labels are compared character by character, as cmp.Compare does.
- Take github.com/gin-gonic/gin, the only ready vertex, and add it to the order.
- Remove the 27 edges out of github.com/gin-gonic/gin. Of those, 13 have no incoming edges left, so they join the ready list. The other 14 still have incoming edges.
- Take github.com/bytedance/sonic@v1.9.1, the ready vertex that comes first alphabetically, and add it to the order.
- Remove the 6 edges out of github.com/bytedance/sonic@v1.9.1. github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311 has no incoming edges left, so it joins the ready list. The other 5 still have incoming edges.
- Take github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311, the ready vertex that comes first alphabetically, and add it to the order.
92 more steps lead to the last one:
- Done. All 62 vertices are in the order, and every edge points from an earlier vertex to a later one.
Use it in Go
order, err := gograph.StableTopologySort(g, cmp.Compare)
if err != nil {
return err // gograph.ErrDAGHasCycle
}
for _, v := range order {
fmt.Println(v.Label())
}
Example graphs
- Build pipeline, 7 vertices and 9 edges
- Course prerequisites, 14 vertices and 18 edges
- Spreadsheet formulas, 25 vertices and 41 edges
- Go module graph, 62 vertices and 116 edges
- Monorepo build, 100 vertices and 266 edges
More in Ordering
- Topological sort: Puts the vertices of a graph without cycles in an order where every edge points forward, taking vertices in the order they become ready.
- Topological levels: Splits a graph without cycles into levels, so that every edge goes to a later level and each level can run at the same time.
- Ready-set tracker: Hands out the tasks of a graph without cycles as soon as every task they depend on is done, so a slow task holds up only the tasks that wait for it.
- Dynamic topological sort: Keeps a topological order while edges are added one at a time, and moves only the vertices between the two ends of an edge that points backward.