Descendants

Finds every vertex reachable from a vertex, such as all the jobs that wait for one step of a build.

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

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. Each edge points from a target to a target that builds on it.

A directed graph with 100 vertices and 266 edges.

Which targets build on the shared library T20, directly or through other targets?

Use it in Go

jobs, err := dag.Descendants(g, "T20")
if err != nil {
	return err
}
for _, v := range jobs {
	fmt.Println(v.Label())
}

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

More in Dependencies

• Ancestors: Finds every vertex that can reach a vertex, such as all the courses one course needs first.
• Affected: Finds the changed vertices and every vertex reachable from them, such as all the cells a spreadsheet edit recomputes.
• Transitive reduction: Drops every edge that a longer path already implies. Each vertex still reaches the same vertices.

All algorithms