Transitive reduction
Drops every edge that a longer path already implies. Each vertex still reaches the same vertices.
Time complexity O(V(V+E)), gograph function path.TransitiveReduction.
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.
Which references can a diagram of the sheet leave out, because a longer chain of formulas already connects the same cells?
Use it in Go
reduced, err := path.TransitiveReduction(g)
if err != nil {
return err
}
for _, e := range reduced.AllEdges() {
fmt.Println(e.Source().Label(), "->", e.Destination().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.
- Affected: Finds the changed vertices and every vertex reachable from them, such as all the cells a spreadsheet edit recomputes.