I am looking for an algorithm to count and enumerate (separately, in case of different complexity) all the paths reconvergent in a simple graph, directed, unweighted, which can contain cycles. In other words, for each vertex $ v_i $ of degree> 1, determine if a pair of its direct ancestors has a lowest common ancestor $ u_i $ and, if so, count it and list the pathset of $ u_i $ at $ v_i $. (Equivalently, for each vertex $ u_i $ over-degree> 1, find the lowest common successor $ v_i $ of his direct successors in pairs.)
- A pathset is the set of all the single simple paths of $ u $ at $ v $.
- A reconvergent way is the pathset of $ u $ at $ v $, or $ u $ is the lowest common ancestor (predecessor) between two direct predecessors of $ v $.
This problem has applications in VLSI, to find re-convergent paths in a time graph to reduce pessimism.
For the graph above $ G $ defined by his 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 converts back to 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] ]