Re: [Boost-users] [BGL] Schultes and Sanders Contraction Hierarchies Routing

Subject: Re: [Boost-users] [BGL] Schultes and Sanders Contraction Hierarchies Routing
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-11-10 08:40:05

> 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_at_[hidden]