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.

Time complexity O(V+E), gograph function dag.Levels.

How it works

The levels of a directed graph without cycles are waves of work. The first level holds the vertices with no incoming edges. Each later level holds the vertices whose incoming edges all come from earlier levels, so the vertices of one level have no edges between them and can all run at once.

dag.Levels works like Kahn's topological sort. It counts the incoming edges of each vertex, and each time it removes the edges out of a vertex, a vertex left with none gets the level after the deepest vertex that pointed to it. The level of a vertex is the length of the longest path to it, levels[0] holds the vertices with no incoming edges, and the vertices of each level keep the graph's vertex order. It costs O(V+E).

The number of levels is the fewest rounds the work can take, and the widest level is the most workers a round can use. A round waits for its slowest task, though. To start each task as soon as its own dependencies finish, use the ready-set tracker. Levels returns ErrDAGHasCycle for a graph with a cycle and ErrNotDirected for an undirected one.

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.

Which targets can build at the same time, and how many rounds does the whole build take?

The 100 vertices fall into 12 levels, so the work takes at least 12 rounds. The widest is level 6, with 21 vertices that can run at the same time: T24, T29, T30, T32, T43, T44, T45, T46, T47, T49 and 11 more.

Step by step

Count the incoming edges of each vertex. A vertex with none waits for nothing, so it can go in the first level.
Level 1: T1, T2, T3, T33, T65, T66, T67 and T77 have no incoming edges, so they can run first, at the same time.
Remove the 42 edges out of level 1. That leaves T4, T5, T10, T11, T14, T15, T16, T8, T34, T70 and 1 more with no incoming edges, so they go in level 2.
Level 2: T4, T5, T8, T10, T11, T14, T15, T16, T34, T68 and 1 more have no incoming edges left, so they can run at the same time.
Remove the 48 edges out of level 2. That leaves T12, T6, T35, T36, T38, T41, T69 and T71 with no incoming edges, so they go in level 3.
Level 3: T6, T12, T35, T36, T38, T41, T69 and T71 have no incoming edges left, so they can run at the same time.

18 more steps lead to the last one:

Done. All 100 vertices have a level, 12 levels in all, and every edge goes from a level to a later one.

Use it in Go

levels, err := dag.Levels(g)
if err != nil {
	return err
}
for i, level := range levels {
	var names []string
	for _, v := range level {
		names = append(names, v.Label())
	}
	fmt.Println(i, strings.Join(names, ", "))
}

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