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.

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.

Which module versions does github.com/go-playground/validator/v10@v10.14.0 require, directly or through other modules?

22 vertices are reachable from github.com/go-playground/validator/v10@v10.14.0: github.com/davecgh/go-spew@v1.1.0, github.com/davecgh/go-spew@v1.1.1, github.com/gabriel-vasile/mimetype@v1.4.2, github.com/go-playground/assert/v2@v2.2.0, github.com/go-playground/locales@v0.14.1 and 17 more.

Step by step

  1. Start at github.com/go-playground/validator/v10@v10.14.0. It has edges to github.com/gabriel-vasile/mimetype@v1.4.2, github.com/go-playground/assert/v2@v2.2.0, github.com/go-playground/locales@v0.14.1, github.com/go-playground/universal-translator@v0.18.1, github.com/leodido/go-urn@v1.2.4, golang.org/x/crypto@v0.7.0, golang.org/x/text@v0.8.0, golang.org/x/net@v0.8.0 and golang.org/x/sys@v0.6.0. All 9 are new, so they join the queue.
  2. Take github.com/gabriel-vasile/mimetype@v1.4.2 from the queue. It has an edge to golang.org/x/net@v0.8.0, which was found before.
  3. Take github.com/go-playground/assert/v2@v2.2.0 from the queue. It has no edges out.
  4. Take github.com/go-playground/locales@v0.14.1 from the queue. It has an edge to golang.org/x/text@v0.3.8, which is new, so it joins the queue.
  5. Take github.com/go-playground/universal-translator@v0.18.1 from the queue. It has an edge to github.com/go-playground/locales@v0.14.1, which was found before.
  6. Take github.com/leodido/go-urn@v1.2.4 from the queue. It has an edge to github.com/stretchr/testify@v1.8.2, which is new, so it joins the queue.

17 more steps lead to the last one:

  1. Done. 22 vertices are reachable from github.com/go-playground/validator/v10@v10.14.0.

Use it in Go

jobs, err := dag.Descendants(g, "github.com/go-playground/validator/v10@v10.14.0")
if err != nil {
	return err
}
for _, v := range jobs {
	fmt.Println(v.Label())
}

Example graphs

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.

All algorithms