Clarify and Find Common Ancestors in a Graph

The first step is not to pick an algorithm, but to fix exactly what “common ancestor” means for the graph in question. Semantics to clarify Edge direction: If an edge means “parent to child” (p -> c), then an ancestor of x is any vertex that can reach x. If edges are stored as “child to parent,” the traversal direction is reversed. Graph structure: Is the graph a tree, a DAG, or an arbitrary directed graph? A DAG is the usual meaningful setting. In a general directed graph…