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.
Spreadsheet formulas
A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each cell takes 1 to 4 milliseconds to work out. Each edge points from a cell to a formula that reads it.
A directed graph with 25 vertices and 41 edges.
In what order should the sheet recompute its cells, so that every formula reads cells that are already up to date?
In this order, every edge points forward: B2, C2, D2, G2, G3, G4, G5, B3, C3, D3, and so on to E8.
Step by step
- Count the incoming edges of each vertex, its in-degree. B2, C2, D2, G2, G3, G4 and G5 have none, so they start the queue in the order they were added to the graph.
- Take B2 from the front of the queue and add it to the order.
- Remove the 2 edges out of B2. B3 and B4 still have incoming edges.
- Take C2 from the front of the queue and add it to the order.
- Remove the 2 edges out of C2. C3 and C4 still have incoming edges.
- Take D2 from the front of the queue and add it to the order.
44 more steps lead to the last one:
- Done. All 25 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.