Re: [Boost-users] [BGL] k-shortest path

Subject: Re: [Boost-users] [BGL] k-shortest path
From: Ireneusz Szcześniak (irek.szczesniak_at_[hidden])
Date: 2015-10-24 02:36:21

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.cpp
> 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#L28
>
> we include the following file:
> https://github.com/pgRouting/pgrouting/blob/master/src/dijkstra/src/pgr_dijkstra.hpp
> because we use dijkstra.
>
> And
> https://github.com/pgRouting/pgrouting/blob/master/src/common/src/baseGraph.hpp
> 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_at_[hidden]
>  > To: boost-users_at_[hidden]
>  > 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_at_[hidden]
>  > > > To: boost-users_at_[hidden]
>  > > > 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_at_[hidden]
> <mailto:irek.szczesniak_at_[hidden]>> 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_at_[hidden]
>  > > > > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>  > > > >
>  > > >
>  > > > _______________________________________________
>  > > > Boost-users mailing list
>  > > > Boost-users_at_[hidden]
>  > > > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>  > >
>  > >
>  > > _______________________________________________
>  > > Boost-users mailing list
>  > > Boost-users_at_[hidden]
>  > > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>  > >
>  >
>  > _______________________________________________
>  > Boost-users mailing list
>  > Boost-users_at_[hidden]
>  > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>