Affected
Finds the changed vertices and every vertex reachable from them, such as all the cells a spreadsheet edit recomputes.
Time complexity O(V+E), gograph function dag.Affected.
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.
An update brings in github.com/stretchr/testify@v1.8.3 and golang.org/x/net@v0.10.0. Which module versions come with them, counting the two and everything they require?
Use it in Go
jobs, err := dag.Affected(g, "github.com/stretchr/testify@v1.8.3", "golang.org/x/net@v0.10.0")
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.
- Ancestors: Finds every vertex that can reach a vertex, such as all the courses one course needs first.
- Transitive reduction: Drops every edge that a longer path already implies. Each vertex still reaches the same vertices.