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.
Monorepo build
One hundred build targets, T1 to T100, in the repository of an online shop. T1 to T32 are shared libraries, T33 to T41 the code generator and API definitions, T42 to T58 services, T59 to T63 batch jobs, T64 to T71 the API client and UI packages, T72 to T76 apps, T77 to T95 container images, and T96 to T100 the deploys and the contract and end-to-end tests. Each edge points from a target to a target that builds on it.
A directed graph with 100 vertices and 266 edges.
Which dependencies between targets can a picture of the build leave out, because a path through other targets already implies them?
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.