Critical path

Finds the longest chain of tasks that wait on each other, which sets how long the whole run takes however many tasks run in parallel.

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

How it works

When tasks run in parallel, the total time is set by the longest chain of tasks that wait on each other. That chain is the critical path. Making a task on it faster shortens the whole run, and making any other task faster doesn't, since that task already has time to spare.

dag.CriticalPath takes the vertices in topological order, as Kahn's algorithm does. Each vertex finishes at the latest finish among the vertices it depends on, plus its own weight and the weight of the edge from that dependency. The path ends at the vertex with the latest finish among those nothing depends on, and following each vertex back to the dependency that set its start gives the path. It costs O(V+E).

Weights are read with Vertex.Weight and Edge.Weight, so the graph needs no Weighted option, and an unset weight counts as 0. On a tie, the path found first in topological order wins. CriticalPathFunc takes the costs from functions instead, such as durations measured on the last run. For a graph with cycles, condense it first: each loop of tasks becomes one vertex, which WithComponentWeight can give the sum of its tasks.

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.

With as many build machines as it needs, how long does the build take, and which targets are worth making faster?

The critical path is T1, T5, T6, T7, T23, T24, T42, T78, T96, T97, and so on to T100, 12 tasks taking 52 in all. Every task one after another takes 337, so running in parallel saves 285. Only a faster task on the path makes the whole run shorter.

Step by step

Take the tasks in topological order, so every task comes after the tasks it depends on. A task finishes at the latest finish among its dependencies, plus its own weight. The tasks with no dependencies, T1, T2, T3, T33, T65, T66, T67 and T77, start at 0.
T1 depends on nothing. It starts at 0 and takes 2, so it finishes at 2. 9 tasks that depend on T1 can't start before 2.
T2 depends on nothing. It starts at 0 and takes 2, so it finishes at 2. T9, T57 and T63 can't start before 2. T8 already waits at least that long for another task.
T3 depends on nothing. It starts at 0 and takes 2, so it finishes at 2. T18 and T21 can't start before 2.
T33 depends on nothing. It starts at 0 and takes 3, so it finishes at 3. T34 can't start before 3.
T65 depends on nothing. It starts at 0 and takes 2, so it finishes at 2. T68, T70 and T74 can't start before 2.

96 more steps lead to the last one:

Done. The critical path takes 52, against 337 for every task one after another. The other tasks finish before anything on the path needs them.

Use it in Go

path, cost, err := dag.CriticalPath(g)
if err != nil {
	return err
}
for _, v := range path {
	fmt.Println(v.Label(), v.Weight())
}
fmt.Println(cost)

Example graphs

Build pipeline, 7 vertices and 9 edges
Course prerequisites, 14 vertices and 18 edges
Spreadsheet formulas, 25 vertices and 41 edges
Monorepo build, 100 vertices and 266 edges