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/srcthe ksp.h & ksp.h are for linking into the database
This one:
https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/ksp_driver.cppIs 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.cppIn this line :
https://github.com/pgRouting/pgrouting/blob/master/src/ksp/src/pgr_ksp.hpp#L28we include the following file:
https://github.com/pgRouting/pgrouting/blob/master/src/dijkstra/src/pgr_dijkstra.hppbecause we use dijkstra.
And
https://github.com/pgRouting/pgrouting/blob/master/src/common/src/baseGraph.hppis 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 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
> >
> >
> > _______________________________________________
> > 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