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.

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.

Which cells can the sheet recompute at the same time, each round reading only cells an earlier round finished?

The 25 vertices fall into 7 levels, so the work takes at least 7 rounds. The widest is level 1, with 7 vertices that can run at the same time: B2, C2, D2, G2, G3, G4 and G5.

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: B2, C2, D2, G2, G3, G4 and G5 have no incoming edges, so they can run first, at the same time.
Remove the 18 edges out of level 1. That leaves B3, C3, D3, B4, C4 and D4 with no incoming edges, so they go in level 2.
Level 2: B3, C3, D3, B4, C4 and D4 have no incoming edges left, so they can run at the same time.
Remove the 9 edges out of level 2. That leaves E3, B5, C5 and D5 with no incoming edges, so they go in level 3.
Level 3: B5, C5, D5 and E3 have no incoming edges left, so they can run at the same time.

8 more steps lead to the last one:

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