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:

enter the description of the image here

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] ]