I'm looking for an algorithm to count and enumerate (separately, if differing complexity) all the reconvergent pathsets in a simple, directed, non-weighted graph, which may contain cycles. That is, for every vertex $v_i$ of in-degree >1, determine if any pair of its direct ancestors have a lowest common ancestor $u_i$ and, if so, count it and enumerate the pathset from $u_i$ to $v_i$. (Equivalently, for every vertex $u_i$ of out-degree >1, find the lowest common successor $v_i$ of its pairwise direct successors.)
- A pathset is the set of all unique simple paths from $u$ to $v$.
- A reconvergent pathset is the pathset from $u$ to $v$, where $u$ is a lowest common ancestor (predecessor) between any two direct predecessors $p_i,p_j$ of $v$.
- A lowest common ancestor (LCA) between $p_i$ and $p_j$ is the first common node reachable by walking the digraph backwards from each node. A pair of nodes may have multiple LCAs, which should be counted and enumarated separately.
This problem has applications in VLSI, for finding re-convergent paths in a timing graph for pessimism reduction.
For the above graph $G$ defined by its edgelist:
G.edges = [(0, 1), (1, 8), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 3), (9, 6)]
We can see that the graph diverges at node 1 and re-converges at nodes 3 and 8. It also diverges at node 9 and reconverges at node 6.
The algorithm would thus return a result such as:
G.reconvergent_count = 3 G.reconvergent_pathsets = [ [ [1,2,3], [1,8,9,3] ] [ [1,2,3,4,5,6,7,8], [1,8] ] [ [9,3,4,5,6], [9,6] ]