Re: Question on JGraphT

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Question on JGraphT

John Sichi
Administrator
Olivier Lefevre wrote:

> Hi,
>
> What is the algorithm used for K-shortest paths in JGraphT:
> the REA algorithm of Jimenez and Marzal?
>
> Regards,
>
> Olivier Lefevre
> Freelance bioinformatics developer
> Berlin, Germany

Greetings Olivier,

I don't know the answer, so I'm cc'ing your question to the users
mailing list, as well as Guillaume Boulmier, who developed this code.

Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have
O(K*m*n) for the running time.

JVS


Reply | Threaded
Open this post in threaded view
|

Re: Question on JGraphT

gu boulmi
Hi,
 
I'm Implmentation

--- En date de : Mer 4.3.09, John V. Sichi <[hidden email]> a écrit :
De: John V. Sichi <[hidden email]>
Objet: Re: Question on JGraphT
À: [hidden email]
Cc: [hidden email], [hidden email]
Date: Mercredi 4 Mars 2009, 1h09

Olivier Lefevre wrote:
> Hi,
> 
> What is the algorithm used for K-shortest paths in JGraphT: the REA
algorithm of Jimenez and Marzal?
> 
> Regards,
> 
> Olivier Lefevre
> Freelance bioinformatics developer
> Berlin, Germany

Greetings Olivier,

I don't know the answer, so I'm cc'ing your question to the users
mailing list, as well as Guillaume Boulmier, who developed this code.

Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have
O(K*m*n) for the running time.

JVS

Reply | Threaded
Open this post in threaded view
|

Re: Question on JGraphT

gu boulmi
In reply to this post by John Sichi
Hi,
 
I have not implemented this algorithm based on a reference paper, though I'm sure that what I've written is not new and must have been explained previously in many papers.
 
The algorithm is a variant of the Bellman-Ford algorithm but instead of only storing the best path I store the "k" best paths at each pass (se differences between KShortestPathsIterator#next and BellmanFordIterator#next).
 
Complexity "m*n" is because it's a variant of Bellman-Ford and the "k" factor is because the method RankingPathElementList#addPathElements is O(k).
 
If you find 
 

--- En date de : Mer 4.3.09, John V. Sichi <[hidden email]> a écrit :
De: John V. Sichi <[hidden email]>
Objet: Re: Question on JGraphT
À: [hidden email]
Cc: [hidden email], [hidden email]
Date: Mercredi 4 Mars 2009, 1h09

Olivier Lefevre wrote:
> Hi,
> 
> What is the algorithm used for K-shortest paths in JGraphT: the REA
algorithm of Jimenez and Marzal?
> 
> Regards,
> 
> Olivier Lefevre
> Freelance bioinformatics developer
> Berlin, Germany

Greetings Olivier,

I don't know the answer, so I'm cc'ing your question to the users
mailing list, as well as Guillaume Boulmier, who developed this code.

Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have
O(K*m*n) for the running time.

JVS

Reply | Threaded
Open this post in threaded view
|

Re: Question on JGraphT

gu boulmi
In reply to this post by John Sichi
Hi,
 
I have not implemented this algorithm based on a reference paper. So, it's not Jimenez and Marzal!
Though I'm sure that what I've written is not new and must have been explained previously in many papers.
 
The algorithm is a variant of the Bellman-Ford algorithm but instead of only storing the best path I store the "k" best paths at each pass (se differences between methods KShortestPathsIterator#next and BellmanFordIterator#next).
 
Complexity "m*n" is because it's a variant of Bellman-Ford (whose complexity is O(m*n)) and the "k" factor is because the method RankingPathElementList#addPathElements is O(k) where k is the number of expected paths to be computed (by the way I notice that this "O(k)" piece of information is not in the javadoc documentation).
 
If you find a paper pointing to this kind of algorithm, feel free to update the javadoc documentation.
 
Regards,
 
Guillaume

--- En date de : Mer 4.3.09, John V. Sichi <[hidden email]> a écrit :
De: John V. Sichi <[hidden email]>
Objet: Re: Question on JGraphT
À: [hidden email]
Cc: [hidden email], [hidden email]
Date: Mercredi 4 Mars 2009, 1h09

Olivier Lefevre wrote:
> Hi,
> 
> What is the algorithm used for K-shortest paths in JGraphT: the REA
algorithm of Jimenez and Marzal?
> 
> Regards,
> 
> Olivier Lefevre
> Freelance bioinformatics developer
> Berlin, Germany

Greetings Olivier,

I don't know the answer, so I'm cc'ing your question to the users
mailing list, as well as Guillaume Boulmier, who developed this code.

Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have
O(K*m*n) for the running time.

JVS

Reply | Threaded
Open this post in threaded view
|

Re: Question on JGraphT

John Sichi
Administrator
Thanks Guillaume.  I'll poke around a bit and update the Javadoc with
what I find.

Olivier, if you are interested in implementing one of the newer
algorithms, we can incorporate that into the library too.

JVS

gu boulmi wrote:

> Hi,
>  
> I have not implemented this algorithm based on a reference paper. So,
> it's not Jimenez and Marzal!
> Though I'm sure that what I've written is not new and must have
> been explained previously in many papers.
>  
> The algorithm is a *variant of the Bellman-Ford algorithm* but instead
> of only storing the best path I store the "*k*" best paths at each pass
> (se differences between methods KShortestPathsIterator#next and
> BellmanFordIterator#next).
>  
> Complexity "*/m*n/*" is because it's a variant of Bellman-Ford (whose
> complexity is /*O(m*n)*/) and the "*/k/*" factor is because the method
> RankingPathElementList#addPathElements is /*O(k)*/ where *k* is the
> number of expected paths to be computed (by the way I notice that this
> "O(k)" piece of information is not in the javadoc documentation).
>  
> If you find a paper pointing to this kind of algorithm, feel free to
> update the javadoc documentation.
>  
> Regards,
>  
> Guillaume
>
> --- En date de : *Mer 4.3.09, John V. Sichi /<[hidden email]>/* a écrit :
>
>     De: John V. Sichi <[hidden email]>
>     Objet: Re: Question on JGraphT
>     À: [hidden email]
>     Cc: [hidden email], [hidden email]
>     Date: Mercredi 4 Mars 2009, 1h09
>
>     Olivier Lefevre wrote:
>     > Hi,
>     >
>     > What is the algorithm used for K-shortest paths in JGraphT: the REA
>     algorithm of Jimenez and Marzal?
>     >
>     > Regards,
>     >
>     > Olivier Lefevre
>     > Freelance bioinformatics developer
>     > Berlin, Germany
>
>     Greetings Olivier,
>
>     I don't know the answer, so I'm cc'ing your question to the users
>     mailing list, as well as Guillaume Boulmier, who developed this code.
>
>     Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have
>     O(K*m*n) for the running time.
>
>     JVS
>
>



Reply | Threaded
Open this post in threaded view
|

Re: Question on JGraphT

SSovine
I see that this is a fairly old post, but hopefully this will be useful anyway.

I have experimented with this same algorithm, and unfortunately I think it may not always correctly produce the K shortest paths.

Consider a graph with the following edges (posted as .dot file for graphviz), where we are searching for the 3-shortest paths from S to U:

graph G {
autosize=false;
size="20,12!";
rankdir=LR;

S -- U [label="1"];
S -- a1 [label="1"];
a1 -- a2 [label="1"];
a2 -- a3 [label="1"];
a3 -- a4 [label="1"];
a4 -- V [label="1"];
S -- b1 [label="3"];
b1 -- b2 [label="1"];
b2 -- b3 [label="1"];
b3 -- b4 [label="1"];
b4 -- b5 [label="1"];
b5 -- U [label="1"];
S -- c1 [label="2"];
c1 -- b2 [label="1"];

V -- U [label="1"];
V -- d1 [label="1"];
d1 -- U [label="1"];
V -- e1 [label="1"];
e1 -- e2 [label="1"];
e2 -- U [label="1"];
}

The path (S, a1, a2, a3, a4, V, U) should be one of the 3-shortest paths from S to U. However, after four iterations, the three shortest paths stored for V will be {(S, U, V), (S, U, d1, V), (S, U, e2, e1, V)}. This will prevent the path {(S, a1, a2, a3, a4, V)} from being stored for V at the fifth iteration, which will prevent it from being passed on to U at the sixth iteration.

The problem comes from the fact that we only store simple paths for each vertex at each iteration. If we allow paths to have loops, then we can prove correctness for the algorithm using essentially the same method that is used to prove correctness for Bellman-Ford.

SRS
Reply | Threaded
Open this post in threaded view
|

Re: Question on JGraphT

gu boulmi
Hi,
In a mood of making a clean-up of my unused email addresses, I came across your e-mail.
It might be useful that I answer you before I give up for good to visit my Yahoo mailbox :)

I will not answer exactly to your question (you may consider to attach a JUnit test case for the members willing to look at the bug you mentioned), on the hand I want to clarify the poor performance of the algorithm to warn new JGraphT users.

Initially I designed the algorithm (a long time ago...) mainly for the purpose of complete graphs with possibly negative weight cycles. However, as the name of the class 'KShortestPaths' does not refer to this specific property (of possible negative cycles), it might be misleading for the majority of users whose graphs are only with non-negative edge weights.
Indeed, what is 100% true is that it is far far too slow compared to other algorithms for non-negative edge weights :(
Unfortunately everybody seems to perform the 'KShortestPaths' algorithm with non-negative edge weights... 

In order not to mislead users, it might be worth to rename the class or to remove the class completely (I will feel hurt) and replace it with a best-in-class algorithm. You may think of the REA algorithm (Recursive Enumeration Algorithm) by Jimenez and Marzal (see http://www.springerlink.com/content/pl0054nt2d0d2u3t/ ) or to the Yen's algorithm (as already pointed by somebody at http://stackoverflow.com/questions/12773525/k-shortest-alternative-path-algorithm-java-implementations ).

I definitely submitted to JGraphT a not satisfying implementation for the 'KShortestPaths' class. Sorry for that.



Le Mercredi 29 juillet 2015 14h05, SSovine <[hidden email]> a écrit :


I see that this is a fairly old post, but hopefully this will be useful
anyway.

I have experimented with this same algorithm, and unfortunately I think it
may not always correctly produce the K shortest paths.

Consider a graph with the following edges (posted as .dot file for
graphviz), where we are searching for the 3-shortest paths from S to U:

graph G {
autosize=false;
size="20,12!";
rankdir=LR;

S -- U [label="1"];
S -- a1 [label="1"];
a1 -- a2 [label="1"];
a2 -- a3 [label="1"];
a3 -- a4 [label="1"];
a4 -- V [label="1"];
S -- b1 [label="3"];
b1 -- b2 [label="1"];
b2 -- b3 [label="1"];
b3 -- b4 [label="1"];
b4 -- b5 [label="1"];
b5 -- U [label="1"];
S -- c1 [label="2"];
c1 -- b2 [label="1"];

V -- U [label="1"];
V -- d1 [label="1"];
d1 -- U [label="1"];
V -- e1 [label="1"];
e1 -- e2 [label="1"];
e2 -- U [label="1"];
}

The path (S, a1, a2, a3, a4, V, U) should be one of the 3-shortest paths
from S to U. However, after four iterations, the three shortest paths stored
for V will be {(S, U, V), (S, U, d1, V), (S, U, e2, e1, V)}. This will
prevent the path {(S, a1, a2, a3, a4, V)} from being stored for V at the
fifth iteration, which will prevent it from being passed on to U at the
sixth iteration.

The problem comes from the fact that we only store simple paths for each
vertex at each iteration. If we allow paths to have loops, then we can prove
correctness for the algorithm using essentially the same method that is used
to prove correctness for Bellman-Ford.

SRS



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Re-Question-on-JGraphT-tp107942p4025031.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

------------------------------------------------------------------------------
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users