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.
How it works
The transitive reduction keeps the fewest edges that still let every vertex reach the same vertices. An edge from A to C goes when there is already a longer path from A to C, such as A to B to C, since the path says the same thing. In a graph without cycles, only one graph fits that description.
path.TransitiveReduction takes each vertex's direct neighbors and drops any neighbor that another of those neighbors can already reach. The edges to the neighbors that are left are the ones the graph needs. It caches the vertices each neighbor reaches, so the work is O(V(V+E)) at most.
It returns a new graph with the weights of the edges it keeps, and leaves the input as it was. It returns an error for an undirected graph or one with a cycle. Use it to draw a dependency graph without the clutter of implied edges, or to see which requirements are direct.
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. A target takes 1 to 20 minutes to build. 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?
The reduction keeps 240 of the 266 edges. It drops T1 to T13, T2 to T57, T2 to T63, T4 to T22, T4 to T25, T4 to T27, T4 to T28, T5 to T7, T5 to T18, T9 to T58 and 16 more.
Step by step
- Check the edges out of each vertex in turn. An edge is implied when a longer path already leads from its start to its end, so the reduction drops it.
- Check the 9 edges out of T1.
- T1 to T13 is implied by the longer path T1, T4, T12, T13. Drop it.
- Keep the 8 remaining edges out of T1.
- Check the 4 edges out of T2, to T8, T9, T57 and T63.
- T2 to T57 is implied by the longer path T2, T8, T18, T57. Drop it.
131 more steps lead to the last one:
- Done. The 4 vertices with no outgoing edges have nothing to check. The reduction keeps 240 of the 266 edges and drops 26 implied edges. Every vertex still reaches the same vertices.
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.
- 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.