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.
Go module graph
The module graph of github.com/gin-gonic/gin v1.9.1, as go mod graph prints it. Each edge points from a module to a module version it requires.
A directed graph with 62 vertices and 116 edges.
Why is gopkg.in/yaml.v3@v3.0.1 in the build? Find every module that requires it, directly or through other modules.
11 vertices can reach gopkg.in/yaml.v3@v3.0.1: github.com/bytedance/sonic@v1.9.1, github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311, github.com/gin-gonic/gin, github.com/go-playground/validator/v10@v10.14.0, github.com/leodido/go-urn@v1.2.4 and 6 more.
Step by step
- The graph stores only the edges out of each vertex, so read every edge once, 116 in all, to find the edges into each one.
- Start at gopkg.in/yaml.v3@v3.0.1. It has edges from github.com/gin-gonic/gin, github.com/stretchr/testify@v1.8.3, github.com/stretchr/testify@v1.8.1, github.com/stretchr/testify@v1.8.2 and github.com/stretchr/testify@v1.8.0. All 5 are new, so they join the queue.
- Take github.com/gin-gonic/gin from the queue. It has no edges in.
- Take github.com/stretchr/testify@v1.8.3 from the queue. It has edges from github.com/gin-gonic/gin and github.com/pelletier/go-toml/v2@v2.0.8. github.com/pelletier/go-toml/v2@v2.0.8 is new, so it joins the queue. github.com/gin-gonic/gin was found before.
- Take github.com/stretchr/testify@v1.8.1 from the queue. It has edges from github.com/bytedance/sonic@v1.9.1 and github.com/chenzhuoyu/base64x@v0.0.0-20221115062448-fe3a3abad311. Both are new, so they join the queue.
- Take github.com/stretchr/testify@v1.8.2 from the queue. It has an edge from github.com/leodido/go-urn@v1.2.4, which is new, so it joins the queue.
7 more steps lead to the last one:
- Done. 11 vertices can reach gopkg.in/yaml.v3@v3.0.1.
Use it in Go
jobs, err := dag.Ancestors(g, "gopkg.in/yaml.v3@v3.0.1")
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.