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.
Go module graph
The module graph of github.com/gin-gonic/gin v1.9.1, as go mod graph prints it. Each edge points from a module to a module version it requires.
A directed graph with 62 vertices and 116 edges.
In what order can the modules be listed, so that each one comes before every module version it requires?
In this order, every edge points forward: github.com/gin-gonic/gin, github.com/bytedance/sonic@v1.9.1, github.com/gin-contrib/sse@v0.1.0, github.com/go-playground/validator/v10@v10.14.0, github.com/goccy/go-json@v0.10.2, github.com/json-iterator/go@v1.1.12, and so on to gopkg.in/check.v1@v0.0.0-20161208181325-20d25e280405.
Step by step
- Count the incoming edges of each vertex, its in-degree. Only github.com/gin-gonic/gin has none, so it starts the queue.
- Take github.com/gin-gonic/gin, the only vertex in the queue, and add it to the order.
- Remove the 27 edges out of github.com/gin-gonic/gin. Of those, 13 have no incoming edges left, so they join the back of the queue. The other 14 still have incoming edges.
- Take github.com/bytedance/sonic@v1.9.1 from the front of the queue and add it to the order.
- Remove the 6 edges out of github.com/bytedance/sonic@v1.9.1. github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311 has no incoming edges left, so it joins the back of the queue. The other 5 still have incoming edges.
- Take github.com/gin-contrib/sse@v0.1.0 from the front of the queue and add it to the order.
92 more steps lead to the last one:
- Done. All 62 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.