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.

Course prerequisites

Fourteen courses of a computer science degree. Each edge points from a course to a course that requires it.

A directed graph with 14 vertices and 18 edges.

The department rewrites Computer systems and Linear algebra. Which courses may need to change too, because they build on them?

Use it in Go

jobs, err := dag.Affected(g, "Computer systems", "Linear algebra")
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.

All algorithms