Descendants

Finds every vertex reachable from a vertex, such as all the jobs that wait for one step of a build.

Time complexity O(V+E), gograph function dag.Descendants.

How it works

Descendants follows edges forward from a vertex and collects every vertex it can reach. gograph reads an edge from A to B as B depending on A, so these are all the vertices that depend on it, directly or through others.

dag.Descendants searches breadth first, so the result is nearest first, and it costs O(V+E) for the part of the graph it reaches. The vertex itself is in the result only when it's on a cycle. The graph has to be directed, but despite the package's name it may have cycles.

Use it to find the jobs that wait for one step of a pipeline, the courses that build on a course, or the cells that read a value. If a graph stores its edges the other way, as A requires B, the meanings swap and Ancestors gives the dependents.

Course prerequisites

Fourteen courses of a computer science degree, each one semester long. Each edge points from a course to a course that requires it.

A directed graph with 14 vertices and 18 edges.

Which courses can a student take only after passing Data structures, directly or through other courses?

5 vertices are reachable from Data structures: Algorithms, Compilers, Databases, Machine learning and Operating systems.

Step by step

  1. Start at Data structures. It has edges to Operating systems, Databases and Algorithms. All 3 are new, so they join the queue.
  2. Take Operating systems from the queue. It has no edges out.
  3. Take Databases from the queue. It has no edges out.
  4. Take Algorithms from the queue. It has edges to Compilers and Machine learning. Both are new, so they join the queue.
  5. Take Compilers from the queue. It has no edges out.
  6. Take Machine learning from the queue. It has no edges out.
  7. Done. 5 vertices are reachable from Data structures.

Use it in Go

jobs, err := dag.Descendants(g, "Data structures")
if err != nil {
	return err
}
for _, v := range jobs {
	fmt.Println(v.Label())
}

Example graphs

More in Dependencies

  • 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.
  • Transitive reduction: Drops every edge that a longer path already implies. Each vertex still reaches the same vertices.
  • 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.

All algorithms