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.

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.

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.

All algorithms