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.
Course prerequisites
Fourteen courses of a computer science degree, each one semester long. Each edge points from a course to a course that requires it.
A directed graph with 14 vertices and 18 edges.
In what order can a student take the courses, so that every course comes after the courses it requires?
In this order, every edge points forward, and vertices that are ready together go in alphabetical order: Calculus 1, Calculus 2, Discrete math, Linear algebra, Probability, Programming 1, Programming 2, Computer systems, Data structures, Algorithms, and so on to Operating systems.
Step by step
- Count the incoming edges of each vertex, its in-degree. Calculus 1, Discrete math and Programming 1 have none, so they start the ready list, which stays in alphabetical order. Labels are compared character by character, as cmp.Compare does.
- Take Calculus 1, the ready vertex that comes first alphabetically, and add it to the order.
- Remove the 2 edges out of Calculus 1. Calculus 2 and Linear algebra have no incoming edges left, so they join the ready list.
- Take Calculus 2, the ready vertex that comes first alphabetically, and add it to the order.
- Remove the edge from Calculus 2 to Probability. Probability still has 1 incoming edge.
- Take Discrete math, the ready vertex that comes first alphabetically, and add it to the order.
19 more steps lead to the last one:
- Done. All 14 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.