Prev: Crew scheduling/rostering problem, Some questions
Next: Sorted heap trees
From: Ginu on 9 Apr 2008 17:00
Hello all. I have a graph (that is not necessarily directed) of a
number of nodes. I'm trying to enumerate through all directed paths
between source and destination (to avoid routing loops). There
shouldn't be an infinite number of solutions to this problem because
nodes cannot be traversed more than once in the solution. Has anybody
come across a solution for this? Thanks in advance.
From: cwenner on 10 Apr 2008 13:50
On Apr 9, 11:00 pm, Ginu <osheik...(a)gmail.com> wrote:
> Hello all. I have a graph (that is not necessarily directed) of a
> number of nodes. I'm trying to enumerate through all directed paths
> between source and destination (to avoid routing loops). There
> shouldn't be an infinite number of solutions to this problem because
> nodes cannot be traversed more than once in the solution. Has anybody
> come across a solution for this? Thanks in advance.

The trivial solution would be to simply iterate over all paths
starting at the source, s, i.e. pick the first edge of s, (s,v), try
all possible paths from v to the destination, t, without going through
s, choose the next edge of s, try all possible paths ..., and so on.
No path will be enumerated twice. You could preprocess the graph with
e.g. a DFS, removing all vertices such that they are either not
reachable from s or cannot reach the destination, t, as well as
contracting edges between pairs of degree-two vertices. This way, you
should be able to prove a, in a sense optimal, Theta(E + k)-complexity
in a uniform-cost RAM with k being the number of enumerated paths.
Perhaps the space complexity, O(V log V), can be significantly
improved.
From: tchow on 10 Apr 2008 16:23
In article <ba2d5990-d172-4bcf-8d86-99d601778ac4(a)v26g2000prm.googlegroups.com>,
Ginu <osheikh81(a)gmail.com> wrote:
>Hello all. I have a graph (that is not necessarily directed) of a
>number of nodes. I'm trying to enumerate through all directed paths
>between source and destination (to avoid routing loops). There
>shouldn't be an infinite number of solutions to this problem because
>nodes cannot be traversed more than once in the solution. Has anybody
>come across a solution for this? Thanks in advance.

Try asking Google about "k shortest paths Yen". Strictly speaking this is
not exactly what you asked for but it's very close.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Paul E. Black on 11 Apr 2008 12:30
On Wednesday 09 April 2008 17:00, Ginu wrote:
> Hello all. I have a graph (that is not necessarily directed) of a
> number of nodes. I'm trying to enumerate through all directed paths
> between source and destination (to avoid routing loops). There
> shouldn't be an infinite number of solutions to this problem because
> nodes cannot be traversed more than once in the solution. ... [PEB]

Your problem may be ill-formed, in that you can get different answers
depending on how you enumerate the paths.

The simple example I can think of has 4 nodes.
B
/|\
A | C
\|/
D
In text, A and C are source and destination. The edges are
(A, B)
(B, C)
(A, D)
(D, C)
(B, D)

If you choose A-B-D-C, you're done: just 1 path. But you can choose
A-B-C, then A-D-C, which gives 2 paths.

What answer do you want? 2 (maximum)? Or is either of 1 or 2
acceptable? Or are there other things that make the problem clearer?

-paul-
From: Ginu on 15 Apr 2008 12:06
On Apr 11, 12:30 pm, "Paul E. Black" <p.bl...(a)acm.org> wrote:
> On Wednesday 09 April 2008 17:00, Ginu wrote:
>
> > Hello all. I have a graph (that is not necessarily directed) of a
> > number of nodes. I'm trying to enumerate through all directed paths
> > between source and destination (to avoid routing loops). There
> > shouldn't be an infinite number of solutions to this problem because
> > nodes cannot be traversed more than once in the solution. ... [PEB]
>
> Your problem may be ill-formed, in that you can get different answers
> depending on how you enumerate the paths.
>
> The simple example I can think of has 4 nodes.
>   B
>  /|\
> A | C
>  \|/
>   D
> In text, A and C are source and destination.  The edges are
>    (A, B)
>    (B, C)
>    (A, D)
>    (D, C)
>    (B, D)
>
> If you choose A-B-D-C, you're done: just 1 path.  But you can choose
> A-B-C, then A-D-C, which gives 2 paths.
>
> What answer do you want? 2 (maximum)?  Or is either of 1 or 2
> acceptable?  Or are there other things that make the problem clearer?
>
> -paul-

Thanks for the responses. Essentially I would like to determine all
directed paths between A and C, so all three that you suggested. I
then have an optimization function to select one above the others.
 | 
Pages: 1
Prev: Crew scheduling/rostering problem, Some questions
Next: Sorted heap trees