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.
How it works
Affected takes the vertices that changed and returns them with every vertex reachable from any of them. It is one breadth-first search that starts from all the changed vertices at once, so a vertex reachable from several of them is listed once.
The changed vertices come first, in the order given, then the rest, nearest first. It costs O(V+E) for the part of the graph it reaches, however many vertices changed. Running Descendants once for each change finds the same vertices, but repeats the work wherever their descendants overlap.
Use it to decide what to rebuild, retest or redeploy after a commit, which cells a spreadsheet recomputes after an edit, or which targets a change to a shared library touches.
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?
19 vertices are affected: github.com/stretchr/testify@v1.8.3 and golang.org/x/net@v0.10.0, which changed, and github.com/davecgh/go-spew@v1.1.0, github.com/davecgh/go-spew@v1.1.1, github.com/pmezard/go-difflib@v1.0.0, github.com/stretchr/objx@v0.1.0, github.com/stretchr/objx@v0.4.0, github.com/stretchr/objx@v0.5.0 and 11 more.
Step by step
- github.com/stretchr/testify@v1.8.3 and golang.org/x/net@v0.10.0 changed, so they are affected. Put them in the queue.
- Take github.com/stretchr/testify@v1.8.3 from the queue. It has edges to github.com/davecgh/go-spew@v1.1.1, github.com/pmezard/go-difflib@v1.0.0, github.com/stretchr/objx@v0.5.0 and gopkg.in/yaml.v3@v3.0.1. All 4 are new, so they join the queue.
- Take golang.org/x/net@v0.10.0 from the queue. It has edges to golang.org/x/sys@v0.8.0, golang.org/x/term@v0.8.0 and golang.org/x/text@v0.9.0. All 3 are new, so they join the queue.
- Take github.com/davecgh/go-spew@v1.1.1 from the queue. It has no edges out.
- Take github.com/pmezard/go-difflib@v1.0.0 from the queue. It has no edges out.
- Take github.com/stretchr/objx@v0.5.0 from the queue. It has an edge to github.com/stretchr/testify@v1.8.0, which is new, so it joins the queue.
14 more steps lead to the last one:
- Done. 19 vertices are affected: the 2 changed vertices and 17 more reachable from them.
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.
- 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.