Finding the list of common children (descendants) for any two nodes in a cyclic graph

Question

I have a cyclic directed graph and I was wondering if there is any algorithm (preferably an optimum one) to make a list of common descendants between any two nodes? Something almost opposite of what Lowest Common Ancestor (LCA) does.

Answer 1

As user1990169 suggests, you can compute the set of vertices reachable from each of the starting vertices using DFS and then return the intersection.

If you're planning to do this repeatedly on the same graph, then it might be worthwhile first to compute and contract the strong components to supervertices representing a set of vertices. As a side effect, you can get a topological order on supervertices. This allows a data-parallel algorithm to compute reachability from multiple starting vertices at the same time. Initialize all vertex labels to {}. For each start vertex v, set the label to {v}. Now, sweep all vertices w in topological order, updating the label of w's out-neighbors x by setting it to the union of x's label and w's label. Use bitsets for a compact, efficient representation of the sets. The downside is that we cannot prune as with single reachability computations.

Answer 2

I would recommend using a DFS (depth first search).

For each input node
    Create a collection to store reachable nodes
    Perform a DFS to find reachable nodes
        When a node is reached
            If it's already stored stop searching that path // Prevent cycles
            Else store it and continue

Find the intersection between all collections of nodes

Note: You could easily use BFS (breadth first search) instead with the same logic if you wanted.

---

When you implement this keep in mind there will be a few special cases you can look for to further optimize your search such as:

• If an input node doesn't have any vertices then there are no common nodes
• If one input node (A) reaches another input node (B), then A can reach everything B can.
  This means the algorithm wouldn't have to be ran on B.
• etc.

Answer 3

Why not just reverse the direction of the edge and use LCA?