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

Subject: Re: [Boost-users] [BGL] k-shortest path
From: Vicky Vergara (vicky_vergara_at_[hidden])
Date: 2015-10-23 17:05:09

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.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