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.
Spreadsheet formulas
A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each edge points from a cell to a formula that reads it.
A directed graph with 25 vertices and 41 edges.
The March units in D2 and the tax rate in G5 change. Which cells does the sheet have to recompute?
Use it in Go
jobs, err := dag.Affected(g, "D2", "G5")
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.