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.

How it works

Descendants follows edges forward from a vertex and collects every vertex it can reach. gograph reads an edge from A to B as B depending on A, so these are all the vertices that depend on it, directly or through others.

dag.Descendants searches breadth first, so the result is nearest first, and it costs O(V+E) for the part of the graph it reaches. The vertex itself is in the result only when it's on a cycle. The graph has to be directed, but despite the package's name it may have cycles.

Use it to find the jobs that wait for one step of a pipeline, the courses that build on a course, or the cells that read a value. If a graph stores its edges the other way, as A requires B, the meanings swap and Ancestors gives the dependents.

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 build on the shared library T20, directly or through other targets?

24 vertices are reachable from T20: T24, T25, T32, T42, T43, T45, T46, T53, T54, T55 and 14 more.

Step by step

  1. Start at T20. It has edges to T24, T25, T32, T43, T45, T46 and T53. All 7 are new, so they join the queue.
  2. Take T24 from the queue. It has edges to T42, T54 and T58. All 3 are new, so they join the queue.
  3. Take T25 from the queue. It has edges to T45, T55 and T58. T55 is new, so it joins the queue. T45 and T58 were found before.
  4. Take T32 from the queue. It has an edge to T98, which is new, so it joins the queue.
  5. Take T43 from the queue. It has an edge to T79, which is new, so it joins the queue.
  6. Take T45 from the queue. It has an edge to T81, which is new, so it joins the queue.

19 more steps lead to the last one:

  1. Done. 24 vertices are reachable from T20.

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

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.
  • 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.
  • Diff: Compares two graphs and returns the vertices, edges, weights and edge labels that differ, matching vertices by label.

All algorithms