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.
Build pipeline
The jobs of a CI pipeline for a web service, and how many minutes each one takes. Each edge points from a job to a job that waits for it.
A directed graph with 7 vertices and 9 edges.
If the Compile job fails, which jobs can't run, because they wait for it directly or through other jobs?
3 vertices are reachable from Compile: Deploy, Docker image and Unit tests.
Step by step
- Start at Compile. It has edges to Unit tests and Docker image. Both are new, so they join the queue.
- Take Unit tests from the queue. It has an edge to Deploy, which is new, so it joins the queue.
- Take Docker image from the queue. It has an edge to Deploy, which was found before.
- Take Deploy from the queue. It has no edges out.
- Done. 3 vertices are reachable from Compile.
Use it in Go
jobs, err := dag.Descendants(g, "Compile")
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.
- 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.