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.
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: Checkout, Install, Lint, Compile, Unit tests, Docker image and Deploy.
Step by step
- Count the incoming edges of each vertex, its in-degree. Only Checkout has none, so it starts the queue.
- Take Checkout, the only vertex in the queue, and add it to the order.
- Remove the 2 edges out of Checkout. Install has no incoming edges left, so it joins the back of the queue. Docker image still has 1 incoming edge.
- Take Install, the only vertex in the queue, 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 back of the queue in that order.
- Take Lint from the front of the queue 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 := 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.