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.
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 formulas read the tax rate in G5, directly or through other cells?
8 vertices are reachable from G5: B6, B7, C6, C7, D6, D7, E7 and E8.
Step by step
- Start at G5. It has edges to B6, C6 and D6. All 3 are new, so they join the queue.
- Take B6 from the queue. It has an edge to B7, which is new, so it joins the queue.
- Take C6 from the queue. It has an edge to C7, which is new, so it joins the queue.
- Take D6 from the queue. It has an edge to D7, which is new, so it joins the queue.
- Take B7 from the queue. It has an edge to E7, which is new, so it joins the queue.
- Take C7 from the queue. It has an edge to E7, which was found before.
3 more steps lead to the last one:
- Done. 8 vertices are reachable from G5.
Use it in Go
jobs, err := dag.Descendants(g, "G5")
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.