[Routing] Routing algorithms

Alex Wilson alex_wilson at pobox.com
Thu Nov 8 16:30:21 GMT 2007


Interesting. I must confess that I've only been dealing with graphs
constructed from a UK subset of the db at the moment - and breaking the
graph down so that there is node created only for the intersections of ways
and the beginning and end of ways. I'll have a look at the HH approach this
evening - sounds very interesting.

Currently I've been using sqlite for the db backend - again because I'm only
using the UK subset. I'd be very interested to hear your experiences if
you've been using the planet db in its entirety.

A.

On 08/11/2007, Artem Pavlenko <artem.mapnik at googlemail.com> wrote:
>
> Hi Alex,
>
> Sounds good. I'm too implemented routing over OSM data using
> boost::graph and gigabase as a storage.
> While standard graph algorithms work well for small graphs, for
> larger ones some extra steps can be useful.
> I wonder if you know/interested in implemented HH approach - http://
> algo2.iti.uka.de/schultes/hwy/ which would allow for efficient route
> planning over OSM data (will be very large one day!)
>
> Regards
> Artem
>
> On 8 Nov 2007, at 15:58, Alex Wilson wrote:
>
> > I've also been implementing routing over OSM data - using the Boost
> > graph library (BGL). I have a GUI written in PyQT4 interfacing with
> > a routing backend written in C++, using Boost python to create the
> > interface between the two languages.
> > It's a nice solution because there are a large number of algorithms
> > in the BGL and they've all been very thoroughly tested.
> >
> > I was also considering using the boost spirit parser to allow users
> > to specify edge costs using expressions - so if, for instance, you
> > were a law-breaking cyclist, you could specify that you were happy
> > too cycle down one-way streets the wrong way if ever it would save
> > you significant time over a legal route ;-)
> >
> > I'm very happy to contribute any code I have or to pitch in if
> > anyone needs any help (I have a lot of experience with graph
> > algorithms).
> >
> > Alex Wilson
> > _______________________________________________
> > Routing mailing list
> > Routing at openstreetmap.org
> > http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20071108/51478395/attachment.html>


More information about the Routing mailing list