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.
Monorepo build
One hundred build targets, T1 to T100, in the repository of an online shop. T1 to T32 are shared libraries, T33 to T41 the code generator and API definitions, T42 to T58 services, T59 to T63 batch jobs, T64 to T71 the API client and UI packages, T72 to T76 apps, T77 to T95 container images, and T96 to T100 the deploys and the contract and end-to-end tests. A target takes 1 to 20 minutes to build. Each edge points from a target to a target that builds on it.
A directed graph with 100 vertices and 266 edges.
In what order can the targets build, so that each one builds after every target it builds on?
In this order, every edge points forward, and vertices that are ready together go in alphabetical order: T1, T10, T11, T14, T15, T16, T2, T3, T33, T34, and so on to T100.
Step by step
- Count the incoming edges of each vertex, its in-degree. T1, T2, T3, T33, T65, T66, T67 and T77 have none, so they start the ready list, which stays in alphabetical order. Labels are compared character by character, as cmp.Compare does.
- Take T1, the ready vertex that comes first alphabetically, and add it to the order.
- Remove the 9 edges out of T1. Of those, 7 have no incoming edges left, so they join the ready list. T8 and T13 still have incoming edges.
- Take T10, the ready vertex that comes first alphabetically, and add it to the order.
- Remove the 2 edges out of T10. T24 and T30 still have incoming edges.
- Take T11, the ready vertex that comes first alphabetically, and add it to the order.
191 more steps lead to the last one:
- Done. All 100 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.