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.

Build pipeline

The jobs of a CI pipeline for a web service. Each edge points from a job to a job that waits for it.

A directed graph with 7 vertices and 9 edges.

Which waits between jobs can the pipeline drop, because a longer chain of jobs already forces the same order?

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.

All algorithms