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.
Build pipeline
The jobs of a CI pipeline for a web service, and how many minutes each one takes. Each edge points from a job to a job that waits for it.
A directed graph with 7 vertices and 9 edges.
In what order can the jobs run, so that each job starts only after the jobs it waits for?
In this order, every edge points forward, and vertices that are ready together go in alphabetical order: Checkout, Install, Compile, Docker image, Lint, Unit tests and Deploy.
Step by step
- Count the incoming edges of each vertex, its in-degree. Only Checkout has none, so it starts the ready list, which stays in alphabetical order. Labels are compared character by character, as cmp.Compare does.
- Take Checkout, the only ready vertex, and add it to the order.
- Remove the 2 edges out of Checkout. Install has no incoming edges left, so it joins the ready list. Docker image still has 1 incoming edge.
- Take Install, the only ready vertex, and add it to the order.
- Remove the 2 edges out of Install. Lint and Compile have no incoming edges left, so they join the ready list.
- Take Compile, the ready vertex that comes first alphabetically, and add it to the order.
8 more steps lead to the last one:
- Done. All 7 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.