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.

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.

Which modules can be built at the same time, each round needing only modules an earlier round built?

The 62 vertices fall into 10 levels, so the work takes at least 10 rounds. The widest is level 3, with 16 vertices that can run at the same time: github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311, github.com/gabriel-vasile/mimetype@v1.4.2, github.com/go-playground/assert/v2@v2.2.0, github.com/go-playground/universal-translator@v0.18.1 and 12 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: only github.com/gin-gonic/gin has no incoming edges, so it runs first, on its own.
Remove the 27 edges out of level 1. That leaves 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, github.com/klauspost/cpuid/v2@v2.2.4 and 7 more with no incoming edges, so they go in level 2.
Level 2: 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, github.com/klauspost/cpuid/v2@v2.2.4 and 7 more have no incoming edges left, so they can run at the same time.
Remove the 31 edges out of level 2. That leaves github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311, github.com/gabriel-vasile/mimetype@v1.4.2, github.com/go-playground/assert/v2@v2.2.0, github.com/go-playground/universal-translator@v0.18.1 and 12 more with no incoming edges, so they go in level 3.
Level 3: github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311, github.com/gabriel-vasile/mimetype@v1.4.2, github.com/go-playground/universal-translator@v0.18.1, github.com/leodido/go-urn@v1.2.4, github.com/modern-go/reflect2@v1.0.2 and 11 more have no incoming edges left, so they can run at the same time.

14 more steps lead to the last one:

Done. All 62 vertices have a level, 10 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