5
$\begingroup$

Given a graph G= (V, E) that is:

  1. directed,
  2. acyclic,
  3. non-weighted,
  4. may have more than one edge between two vertices (thus, source and destination are not enough to determine an edge).

And given a set of vertices, let's call them vSet; that contains a vertex vRoot; I need to find ALL paths pSet between vSet elements respecting the following:

  1. any vertex that appears as a source for some path in pSet must be reachable from vRoot.
  2. any path in pSet must has its source and destination from vSet, and must not contain any other vertex of vSet.

I've developed an algorithm similar to BFS, that starts from vRoot (according to 1 above), grow each of the current paths with one edge per an iteration until it reaches another vertex v1 of vSet; then store this reaching path and start growing new set of paths staring from v1.

Here is a pseudo code

output = ∅;
maxLengthPaths = ∅;
1. add all edges that vRoot is there source to maxLengthPaths
2. while size(maxlengthpaths) != ∅ do
  (a) paths := ∅;
  (b) extendedPaths := ∅;
  (c) foreach path p in maxLengthPaths do
    i. if (destination of p in vSet)
      1. add p to output 
      2. for each edge e that destination of p is its source
        A. add e to extendedPaths
    ii. else
      1. add p to paths
    iii. for path p1 in paths 
      1. for each edge that destination of p1  is its source
        A. extend p1 by a edge and add it to extendedPaths
  (d) maxLengthPaths = extendedPaths

Here are my questions: 1. Is this the best way to achieve my task? 2. I was trying to figure out its time complexity; I found that its exponential of pow(maxNumberOfOutGoingEdgesFormAVertex, maxLengthPath). Is this really the complexity?

$\endgroup$
3
$\begingroup$

Any algorithm for your problem will have to take exponential time in the worst case. However, if you're willing to live with this, there is a straightforward recursive algorithm to solve your problem. Details below.

Generalizing a little bit, your problem is essentially the following:

Input: a dag $G=(V,E)$, three sets $S_0,S_1,S_2 \subseteq V$ of vertices

Output: the set of all paths that start some element of $S_0$, end at some element of $S_1$, and all of whose intermediate vertices are from $S_2$

To see the relationship to your problem statement, let $S_0$ be the set of vertices that are reachable from vRoot and also contained in vSet; let $S_1$ be vSet; and let $S_2$ be the complement of vSet.

There is no efficient algorithm for this problem, because in the worst case there could be exponentially many such paths. Therefore, any algorithm to print all such paths will necessarily have to take exponential time, in the worst case. Of course you could build algorithms that are efficient on some inputs, but no algorithm will be efficient on all possible inputs.

However if you are willing to live with this limitation, here is an approach you could use. Basically, it's easy to come up with a recursive algorithm for this problem:

  • Compute the set $S_0$ of vertices that are reachable from vRoot and are contained in vSet. This can be found in linear time using DFS or BFS. You can also compute $S_1$ and $S_2$ in linear time.

  • Enumerate all paths of the desired form recursively. We will build a procedure $F$ so that, for a vertex $v \in V$, $F(v)$ returns the set of all paths that start at vertex $v$ and end at some vertex in $S_1$ and where all other nodes (the intermediate nodes) are all within $S_2$. You can compute $F$ via a simple recursive procedure:

    • For each $w \in S_2$ such that there is an edge $(v,w) \in E$, compute $F(w)$.

    • Now we can return $$F(v) = B(v) \cup B'(v) \cup \{v@p : w \in S_2, (v,w) \in E, p \in F(w)\},$$

      where $v@p$ denotes the path that starts at $v$, goes to $w$, and then follows the path $p$; and where $B(v),B'(v)$ are defined as follows:

      • if $v \in S_1$, then $B(v)$ is a singleton set containing the path of length 0 that starts at $v$ and stops there; if $v \notin S_1$, then $B(v)$ is the empty set.

      • $B'(v) = \{v \to w : w \in S_1, (v,w) \in E\}$.

  • Finally, calculate $F(v)$ for each $v \in S_0$ and output the union of all of those paths.

  • For better performance, I recommend that you use memoization to avoid ever calculating $F(v)$ more than once for any particular vertex $v$.

This immediately gives you a recursive algorithm that solves your problem, and whose running time is linear in the size of the graph plus the size of the desired output. In other words, this algorithm is about as efficient as you could possibly hope for, given the problem statement.

$\endgroup$
  • $\begingroup$ thank you for this effort. However, I think that you misunderstand my question; 1- the root r is an element of R, 2- any path between two elements of S may contain multiple edges that do connect vertices from S, only the source and destination of the whole path (i.e. not each individual edge) have to be from S, 3- each path of the output must not have any vertices of S except for its source and destination. $\endgroup$ – Median Hilal May 1 '15 at 23:34
  • 1
    $\begingroup$ @MedianHilal, thank you for the comments. I've corrected my answer accordingly. This should now meet all your requirements. $\endgroup$ – D.W. May 2 '15 at 0:31
  • $\begingroup$ Thank you again. However, I want to point out some things, regarding my original problem: 1- Please note that your suppose about S0 and S1 is not precise, because they are the same set, i.e. there is no such explicit differentiation made between sources and destinations, one node can be both a source and a destination for two paths of my output -2- Please note that root is an element of of this set of nodes, so paths from root to any vertex of this set have to be computed, it's not just an issue of reachability. $\endgroup$ – Median Hilal May 2 '15 at 10:10
  • 1
    $\begingroup$ @MedianHilal, 1- My algorithm works fine even if $S_0=S_1$. I'm solving a more general problem. 2- I don't know what you mean. 1- Yes. 2- If $|G| is the size of the graph and $|L|$ is the size of the output, its running time is $O(|G|+|L|)$. $\endgroup$ – D.W. May 2 '15 at 17:06
  • 1
    $\begingroup$ @MedianHilal, yes, I got that. That's why I wrote in my answer that the number of paths might be exponential. The running time is $O(|G|+|L|)$, where $|L|$ is the length of the output, i.e., the number of paths -- so $|L|$ can be exponential in the size of the graph. The running time is linear in the length of the output, which can be exponential in the size of the input. $\endgroup$ – D.W. May 3 '15 at 0:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.