## Graph Theory – List all re-convergent paths in a digraph (with cycles)

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.)

Definitions:

• 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.

Example: 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] ]
``````

Posted on