[BGL] Schultes and Sanders Contraction Hierarchies Routing

[Stephen Woodbridge]

Hi all,

Has anyone looked at supporting Drs Schultes and Sanders Contraction
Hierarchies Routing using Boost Graph?

See here for more info on this:
http://algo2.iti.kit.edu/english/routeplanning.php

This requires lots of preprocessing of the graph, but offers 10-100
times faster performance on shortest path solutions.

If Andrew, Jeremiah or others have time to look at some of the papers, I
would be interested in your thoughts on supporting this or even knowing
that BGL might be the wrong tool to implement this with.

Thanks for any feedback you might be able to offer.

Best regards,
   -Stephen Woodbridge
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Michael Fawcett]

On Sat, Nov 7, 2009 at 7:21 PM, Stephen Woodbridge
<woodbri@...> wrote:

> Hi all,
>
> Has anyone looked at supporting Drs Schultes and Sanders Contraction
> Hierarchies Routing using Boost Graph?
>
> See here for more info on this:
> http://algo2.iti.kit.edu/english/routeplanning.php
>
> This requires lots of preprocessing of the graph, but offers 10-100 times
> faster performance on shortest path solutions.
>
> If Andrew, Jeremiah or others have time to look at some of the papers, I
> would be interested in your thoughts on supporting this or even knowing that
> BGL might be the wrong tool to implement this with.
>
> Thanks for any feedback you might be able to offer.

I really hope to hear a response on this - I just read the paper and
it looks fascinating.

Thanks for the link!

--Michael Fawcett
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Andrew Sutton-2]

Has anyone looked at supporting Drs Schultes and Sanders Contraction Hierarchies Routing using Boost Graph?

No. For some reason, good results in graph algorithms don't filter down to us too quickly :)
 

If Andrew, Jeremiah or others have time to look at some of the papers, I would be interested in your thoughts on supporting this or even knowing that BGL might be the wrong tool to implement this with.

I only have time to give the paper a very brief look this morning, but it seems like it might be feasible to reproduce this with the BGL. However, there are so many components to the technique, that it would require careful planning. For example, contraction may be difficult to implement. The vast majority of our use cases target graph construction and query. Fully dynamic graphs... well, they're supported, but maybe not as well as we'd like.

I would certainly be interested to see somebody try to put this together for the BGL. I think it might drive a lot of interesting requirements for the library, and identify areas that we could improve on.

Andrew Sutton
andrew.n.sutton@...

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Tobias Columbus]

Hi everybody,

I have some very simple, non-generic implementation of contraction
hierarchies for boost graph.
In about 2-3 weeks, I would like to develop it further and try to
generalize it, but this would be the first time for me to develop
generic algorithms, so it might happen I need some help :D

Regards
Tobias Columbus


On Tuesday 10 November 2009 02:40:05 pm Andrew Sutton wrote:
> > Has anyone looked at supporting Drs Schultes and Sanders
Contraction
> > Hierarchies Routing using Boost Graph?
> >
>
> No. For some reason, good results in graph algorithms don't filter
down to
> us too quickly :)
>
>
> > If Andrew, Jeremiah or others have time to look at some of the
papers, I
> > would be interested in your thoughts on supporting this or even
knowing that
> > BGL might be the wrong tool to implement this with.
> >
>
> I only have time to give the paper a very brief look this morning,
but it
> seems like it might be feasible to reproduce this with the BGL.
However,
> there are so many components to the technique, that it would require
careful
> planning. For example, contraction may be difficult to implement. The
vast
> majority of our use cases target graph construction and query. Fully
dynamic
> graphs... well, they're supported, but maybe not as well as we'd
like.
>
> I would certainly be interested to see somebody try to put this
together for
> the BGL. I think it might drive a lot of interesting requirements for
the
> library, and identify areas that we could improve on.
>
> Andrew Sutton
> andrew.n.sutton@...
>

--


Tobias Columbus

___________________________
t.columbus@...
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Stephen Woodbridge]

Hi Tobias,

I would be interested in see the code you have developed so far. I have
been working with Ashraf (CC'd) who was 2009 GSoC student. We have an
OpenSource project http://opengraphrouter.sourceforge.net/ and we are
very interested in this algorithm. Our goals are to create an commercial
grade OpenSource router along with the tools needed to import road
network datasets into the router.

I'm not sure how much help we will be making your code generic but we
would be interesting in contributing if we can and certainly in using
the code which would imply testing and reporting issues we run into.

Best regards,
   -Stephen Woodbridge

Tobias Columbus wrote:

> Hi everybody,
>
> I have some very simple, non-generic implementation of contraction
> hierarchies for boost graph.
> In about 2-3 weeks, I would like to develop it further and try to
> generalize it, but this would be the first time for me to develop
> generic algorithms, so it might happen I need some help :D
>
> Regards
> Tobias Columbus
>
>
> On Tuesday 10 November 2009 02:40:05 pm Andrew Sutton wrote:
>>> Has anyone looked at supporting Drs Schultes and Sanders
> Contraction
>>> Hierarchies Routing using Boost Graph?
>>>
>> No. For some reason, good results in graph algorithms don't filter
> down to
>> us too quickly :)
>>
>>
>>> If Andrew, Jeremiah or others have time to look at some of the
> papers, I
>>> would be interested in your thoughts on supporting this or even
> knowing that
>>> BGL might be the wrong tool to implement this with.
>>>
>> I only have time to give the paper a very brief look this morning,
> but it
>> seems like it might be feasible to reproduce this with the BGL.
> However,
>> there are so many components to the technique, that it would require
> careful
>> planning. For example, contraction may be difficult to implement. The
> vast
>> majority of our use cases target graph construction and query. Fully
> dynamic
>> graphs... well, they're supported, but maybe not as well as we'd
> like.
>> I would certainly be interested to see somebody try to put this
> together for
>> the BGL. I think it might drive a lot of interesting requirements for
> the
>> library, and identify areas that we could improve on.
>>
>> Andrew Sutton
>> andrew.n.sutton@...
>>
>

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Andrew Sutton-2]

I have some very simple, non-generic implementation of contraction
hierarchies for boost graph.
In about 2-3 weeks, I would like to develop it further and try to
generalize it, but this would be the first time for me to develop
generic algorithms, so it might happen I need some help :D

 I'd say that it shouldn't be too hard, but I would probably be wrong :)

Making something generic is an iterative process. I would probably start by abstracting (genericizing, making template parameters, etc.) the graph types that your operate on. You could modify your code to operate on graphs that conform to the BGL concepts. Then post up some code, and we can review it.

The next steps would be to slowly parameterize the functionality of the algorithms--abstract operators into functor parameters. That can actually be a fairly difficult process to get "just right".

If you're interested, give it a try and post the results here.

Andrew Sutton
andrew.n.sutton@...

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users