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.
Time complexity O(V+E), gograph function traverse.Topological.
traverse.Topological sorts with gograph.TopologySort, so the two give the same order, and so does traverse.NewTopologicalIterator.
How it works
A topological sort puts the vertices of a directed graph without cycles in an order where every edge points forward: for an edge from A to B, A comes before B. gograph uses Kahn's algorithm. It counts the incoming edges of each vertex and queues the vertices that have none. Each time it takes a vertex from the queue, it removes that vertex's outgoing edges, and a vertex left with no incoming edges joins the back of the queue.
If the queue empties before every vertex is placed, the rest are on a cycle or after one, and gograph.TopologySort returns ErrDAGHasCycle instead of an order. It costs O(V+E). The order depends only on the order the vertices and edges were added, so a graph built the same way gives the same order every time.
Use it to schedule work with dependencies, such as build steps, course plans or database migrations. To break ties between ready vertices by a fixed rule instead of by the order the graph was built, use the stable topological sort.
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: Programming 1, Discrete math, Calculus 1, Programming 2, Calculus 2, Linear algebra, Computer systems, Data structures, Probability, Operating systems, and so on to Machine learning.
Step by step
- Count the incoming edges of each vertex, its in-degree. Programming 1, Discrete math and Calculus 1 have none, so they start the queue in the order they were added to the graph.
- Take Programming 1 from the front of the queue and add it to the order.
- Remove the edge from Programming 1 to Programming 2. Programming 2 has no incoming edges left, so it joins the back of the queue.
- Take Discrete math from the front of the queue and add it to the order.
- Remove the 3 edges out of Discrete math. Data structures, Probability and Algorithms still have incoming edges.
- Take Calculus 1 from the front of the queue 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 := traverse.Topological(g)
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
- 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.
- 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.