1
$\begingroup$

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

Definitions:

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

Example:

enter image description here

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] ]
$\endgroup$
  • $\begingroup$ Your example does not have parallel edges. If that is also true in its applications in VLSI, can you add that condition? $\endgroup$ – Apass.Jack Dec 7 '18 at 22:17
  • $\begingroup$ Correct, simple graph with no loops or edges, but may contain cycles. $\endgroup$ – teadotjay Dec 7 '18 at 22:45
  • 1
    $\begingroup$ "$u$ is the lowest common ancestor (predecessor) between any two direct predecessors of $v$". Can you confirm that both 3 and 6 are lowest common ancestors of 2 and 8, two direct predecessors of 1? If yes, strictly speaking, we can only say one of the lowest common ancestors. In fact, can you define formally what is lowest common ancestor? $\endgroup$ – Apass.Jack Dec 10 '18 at 0:13
  • $\begingroup$ I agree in general there may be multiple LCAs, and these should count as separate reconvergent paths. In this graph, however, 2 and 8 have only two ancestors, which are in common, and node 1 would be the LCA. I updated the question to clarify. $\endgroup$ – teadotjay Dec 11 '18 at 2:37
  • $\begingroup$ To find all paths for a vertex $v$ with at least two in-edges, reverse all edge directions, and perform a breadth-first search starting at all $u$ such that $(u, v)$ was an edge in the original graph, recording for each visited vertex $x$ the set $reachedFrom[x]$ of all $v$-neighbours it has been reached from so far. (Yes, BFS can be generalised to start from multiple vertices: Just push all of these vertices on the queue at the start.) The first time that $|reachedFrom[x]| > 1$ occurs for some $x$, you have found the other end of at least 2 distinct shortest $x$-to-$v$ paths. $\endgroup$ – j_random_hacker Dec 11 '18 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.