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

  1. 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.
  2. 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.
  3. Take github.com/gin-gonic/gin from the queue. It has no edges in.
  4. 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.
  5. 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.
  6. 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:

  1. 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

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.

All algorithms