Hi, I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me. I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL. Thanks & best, Irek
Hi Irek, On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need. You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865 You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have piqued my curiosity and now I will probably have a go. Cheers. Jeremy
Hi Jeremy, Thanks for your email. No, I haven't tried implementing Yen or Eppstein in BGL. I was hoping to use something that already exist. I guess I'll just go for edge-disjoint shortest paths with the min-cost max-flow algorithm already present in Boost, i.e.: successive_shortest_path_nonnegative_weights Best, Irek On 11.10.2015 08:36, Jeremy Murphy wrote:
Hi Irek,
On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.
You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865
You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have piqued my curiosity and now I will probably have a go.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
You can find an implementation of Yen Algorithm using Boost.Graph in pgRouting http://pgrouting.org/ In version 2.1 which is the latest release, can be found here: https://github.com/pgRouting/pgrouting/releases/tag/pgrouting-2.1.0
Date: Mon, 12 Oct 2015 14:35:52 +0200 From: irek.szczesniak@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] k-shortest path
Hi Jeremy,
Thanks for your email. No, I haven't tried implementing Yen or Eppstein in BGL. I was hoping to use something that already exist.
I guess I'll just go for edge-disjoint shortest paths with the min-cost max-flow algorithm already present in Boost, i.e.:
successive_shortest_path_nonnegative_weights
Best, Irek
On 11.10.2015 08:36, Jeremy Murphy wrote:
Hi Irek,
On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.
You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865
You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have piqued my curiosity and now I will probably have a go.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Vicky, Thanks for the pointer, but I didn't find in your code the implementation of the Yen algorithm using Boost. There was an implementation, but without Boost. Could you please point to the exact implementation? Thanks, Irek On 20.10.2015 18:02, Vicky Vergara wrote:
You can find an implementation of Yen Algorithm using Boost.Graph in pgRouting http://pgrouting.org/ In version 2.1 which is the latest release, can be found here: https://github.com/pgRouting/pgrouting/releases/tag/pgrouting-2.1.0
Date: Mon, 12 Oct 2015 14:35:52 +0200 From: irek.szczesniak@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] k-shortest path
Hi Jeremy,
Thanks for your email. No, I haven't tried implementing Yen or Eppstein in BGL. I was hoping to use something that already exist.
I guess I'll just go for edge-disjoint shortest paths with the min-cost max-flow algorithm already present in Boost, i.e.:
successive_shortest_path_nonnegative_weights
Best, Irek
Hi Irek,
On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.
You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865
You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have
On 11.10.2015 08:36, Jeremy Murphy wrote: piqued
my curiosity and now I will probably have a go.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hello Irek: Sorry for the complex implementation we have. The main idea is that the data is on a data base so you call using an SQL query. ksp= k shortest Paths The main directory is: https://github.com/pgRouting/pgrouting/tree/master/src/ksp/src the ksp.h & ksp.h are for linking into the database This one: https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/ksp_driver.cp... Is where the data we got from the data base gets passed to the algorithm Here is the algorithm: https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.hpp https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.cpp In this line : https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.hpp#L... we include the following file: https://github.com/pgRouting/pgrouting/blob/master/src/dijkstra/src/pgr_dijk... because we use dijkstra. And https://github.com/pgRouting/pgrouting/blob/master/src/common/src/baseGraph.... is a wrapper that simplifies boost.Graph to what we use. I hope this "small guide" helps. Vicky
Date: Fri, 23 Oct 2015 22:13:47 +0200 From: irek.szczesniak@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] k-shortest path
Hi Vicky,
Thanks for the pointer, but I didn't find in your code the implementation of the Yen algorithm using Boost. There was an implementation, but without Boost.
Could you please point to the exact implementation?
Thanks, Irek
On 20.10.2015 18:02, Vicky Vergara wrote:
You can find an implementation of Yen Algorithm using Boost.Graph in pgRouting http://pgrouting.org/ In version 2.1 which is the latest release, can be found here: https://github.com/pgRouting/pgrouting/releases/tag/pgrouting-2.1.0
Date: Mon, 12 Oct 2015 14:35:52 +0200 From: irek.szczesniak@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] k-shortest path
Hi Jeremy,
Thanks for your email. No, I haven't tried implementing Yen or Eppstein in BGL. I was hoping to use something that already exist.
I guess I'll just go for edge-disjoint shortest paths with the min-cost max-flow algorithm already present in Boost, i.e.:
successive_shortest_path_nonnegative_weights
Best, Irek
Hi Irek,
On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.
You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865
You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have
On 11.10.2015 08:36, Jeremy Murphy wrote: piqued
my curiosity and now I will probably have a go.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Vicky, Thank you for the guide. Maybe I'll look deeper into your code, but at first glance, it seems difficult to disentangle the Yen from your data structures, and make it pure Boost. Maybe I'll implement Yen myself. Thanks & best, Irek W dniu 23.10.2015 o 23:05, Vicky Vergara pisze:
Hello Irek:
Sorry for the complex implementation we have.
The main idea is that the data is on a data base so you call using an SQL query.
ksp= k shortest Paths
The main directory is: https://github.com/pgRouting/pgrouting/tree/master/src/ksp/src the ksp.h & ksp.h are for linking into the database
This one: https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/ksp_driver.cp... Is where the data we got from the data base gets passed to the algorithm
Here is the algorithm: https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.hpp <https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.hpp>https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.cpp
In this line : https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.hpp#L...
we include the following file: https://github.com/pgRouting/pgrouting/blob/master/src/dijkstra/src/pgr_dijk... because we use dijkstra.
And https://github.com/pgRouting/pgrouting/blob/master/src/common/src/baseGraph.... is a wrapper that simplifies boost.Graph to what we use.
I hope this "small guide" helps.
Vicky
Date: Fri, 23 Oct 2015 22:13:47 +0200 From: irek.szczesniak@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] k-shortest path
Hi Vicky,
Thanks for the pointer, but I didn't find in your code the implementation of the Yen algorithm using Boost. There was an implementation, but without Boost.
Could you please point to the exact implementation?
Thanks, Irek
On 20.10.2015 18:02, Vicky Vergara wrote:
You can find an implementation of Yen Algorithm using Boost.Graph in pgRouting http://pgrouting.org/ In version 2.1 which is the latest release, can be found here: https://github.com/pgRouting/pgrouting/releases/tag/pgrouting-2.1.0
Date: Mon, 12 Oct 2015 14:35:52 +0200 From: irek.szczesniak@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] k-shortest path
Hi Jeremy,
Thanks for your email. No, I haven't tried implementing Yen or Eppstein in BGL. I was hoping to use something that already exist.
I guess I'll just go for edge-disjoint shortest paths with the min-cost max-flow algorithm already present in Boost, i.e.:
successive_shortest_path_nonnegative_weights
Best, Irek
On 11.10.2015 08:36, Jeremy Murphy wrote:
Hi Irek,
On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.
You may also wish to consider K*:
http://www.sciencedirect.com/science/article/pii/S0004370211000865
You don't have to be a BGL guru to implement algorithms that
BGL graphs: have you tried giving it a go? Admittedly, you have
work on piqued
my curiosity and now I will probably have a go.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Jeremy and others, I implemented the edge-disjoint KSP, but without a min-cost max-flow algorithm. You can find the implementation here: https://svn.boost.org/trac/boost/ticket/11804 Jeremy, did you try to implement Yen? I think I'll have a stab at it. Best, Irek On 12.10.2015 14:35, Ireneusz Szcześniak wrote:
Hi Jeremy,
Thanks for your email. No, I haven't tried implementing Yen or Eppstein in BGL. I was hoping to use something that already exist.
I guess I'll just go for edge-disjoint shortest paths with the min-cost max-flow algorithm already present in Boost, i.e.:
successive_shortest_path_nonnegative_weights
Best, Irek
On 11.10.2015 08:36, Jeremy Murphy wrote:
Hi Irek,
On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.
You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865
You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have piqued my curiosity and now I will probably have a go.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Irek, On 22 November 2015 at 19:11, Ireneusz Szcześniak <irek.szczesniak@gmail.com
wrote:
Hi Jeremy and others,
I implemented the edge-disjoint KSP, but without a min-cost max-flow algorithm. You can find the implementation here:
That's great, it looks good. I don't have time to take a detailed look at it right now, but at first glance, I'm wondering whether you really have to use multimap, set and list? Have you benchmarked against a different implementation using a data structure with better locality of storage (e.g. vector)?
Jeremy, did you try to implement Yen? I think I'll have a stab at it.
No, not yet, I've been busy with polynomial division in Boost.Math. I probably won't really have time to look at it for a few weeks. Cheers. Jeremy
Hi Jeremy, Thanks for your comments. I made some minor changes and motivated the data types used: https://svn.boost.org/trac/boost/ticket/11804#comment:1 https://svn.boost.org/trac/boost/ticket/11804#comment:2 Best, Irek On 23.11.2015 04:44, Jeremy Murphy wrote:
Hi Irek,
On 22 November 2015 at 19:11, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
Hi Jeremy and others,
I implemented the edge-disjoint KSP, but without a min-cost max-flow algorithm. You can find the implementation here:
https://svn.boost.org/trac/boost/ticket/11804
That's great, it looks good. I don't have time to take a detailed look at it right now, but at first glance, I'm wondering whether you really have to use multimap, set and list? Have you benchmarked against a different implementation using a data structure with better locality of storage (e.g. vector)?
Jeremy, did you try to implement Yen? I think I'll have a stab at it.
No, not yet, I've been busy with polynomial division in Boost.Math. I probably won't really have time to look at it for a few weeks.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Jeremy and others, FYI, I implemented the Yen algorithm: https://svn.boost.org/trac/boost/ticket/11838 Best, Irek On 11.10.2015 08:36, Jeremy Murphy wrote:
Hi Irek,
On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak@gmail.com <mailto:irek.szczesniak@gmail.com>> wrote:
I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.
I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.
As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.
You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865
You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have piqued my curiosity and now I will probably have a go.
Cheers.
Jeremy
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (3)
-
Ireneusz Szcześniak -
Jeremy Murphy -
Vicky Vergara