Ancestors
Finds every vertex that can reach a vertex, such as all the courses one course needs first.
Time complexity O(V+E), gograph function dag.Ancestors.
How it works
Ancestors runs the same search backward. It follows edges in reverse from a vertex and collects every vertex that can reach it. With an edge from A to B read as B depending on A, these are everything the vertex depends on, directly or through others.
A gograph graph doesn't index incoming edges, so dag.Ancestors first reads every edge once to find them, then searches breadth first. It costs O(V+E) and returns the vertices nearest first. The vertex itself is in the result only when it's on a cycle.
Use it to find what has to finish before a job can start, which courses come before another, or why a module is in a build. In go mod graph, an edge goes from a module to one it requires, so the ancestors of a module are the modules that pull it in.
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 does the service T58 build on, directly or through other targets?
21 vertices can reach T58: T1, T2, T4, T5, T6, T7, T8, T9, T10, T12 and 11 more.
Step by step
- The graph stores only the edges out of each vertex, so read every edge once, 266 in all, to find the edges into each one.
- Start at T58. It has edges from T9, T22, T24, T25, T35, T36 and T37. All 7 are new, so they join the queue.
- Take T9 from the queue. It has edges from T2 and T6. Both are new, so they join the queue.
- Take T22 from the queue. It has edges from T4, T7, T9 and T13. T4, T7 and T13 are new, so they join the queue. T9 was found before.
- Take T24 from the queue. It has edges from T10, T20, T22 and T23. T10, T20 and T23 are new, so they join the queue. T22 was found before.
- Take T25 from the queue. It has edges from T4 and T20. Both were found before.
17 more steps lead to the last one:
- Done. 21 vertices can reach T58.
Use it in Go
jobs, err := dag.Ancestors(g, "T58")
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
- Descendants: Finds every vertex reachable from a vertex, such as all the jobs that wait for one step of a build.
- 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.