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.

Monorepo build

One hundred build targets, T1 to T100, in the repository of an online shop. T1 to T32 are shared libraries, T33 to T41 the code generator and API definitions, T42 to T58 services, T59 to T63 batch jobs, T64 to T71 the API client and UI packages, T72 to T76 apps, T77 to T95 container images, and T96 to T100 the deploys and the contract and end-to-end tests. A target takes 1 to 20 minutes to build. Each edge points from a target to a target that builds on it.

A directed graph with 100 vertices and 266 edges.

In what order can the targets build, so that each one builds after every target it builds on?

In this order, every edge points forward: T1, T2, T3, T33, T65, T66, T67, T77, T4, T5, and so on to T100.

Step by step

  1. Count the incoming edges of each vertex, its in-degree. T1, T2, T3, T33, T65, T66, T67 and T77 have none, so they start the queue in the order they were added to the graph.
  2. Take T1 from the front of the queue and add it to the order.
  3. Remove the 9 edges out of T1. Of those, 7 have no incoming edges left, so they join the back of the queue. T8 and T13 still have incoming edges.
  4. Take T2 from the front of the queue and add it to the order.
  5. Remove the 4 edges out of T2. T8 has no incoming edges left, so it joins the back of the queue. T9, T57 and T63 still have incoming edges.
  6. Take T3 from the front of the queue and add it to the order.

191 more steps lead to the last one:

  1. Done. All 100 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

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.

All algorithms