Graph vs. Multi_index for geometric algorithms

[nobody]

Dear Boost Supporter,

I am working on an implementation of a 2D polygon 
boolean class. I am aware that such classes are 
already available but all have technical (robustness, 
performance, flexibility) or license (commercial, GPL) 
limitations.

I would like to use STL and Boost as much as possible.

Some of my algorithms require various range searches 
and intersection tests. The multi_index_container 
class seems ideal to implement these. On the other 
hand I will need various graph traversal algorithms, 
which suggests using the Graph library, which has very 
limited possibilities for sorting an efficient 
searching.

Do you see an easy way to combine the advantages of 
both libraries? Obviously, I would like to avoid 
maintaining a separate multi_sorted search structure 
next to my graph.

My email address
hans.van.zwol@nxp.com
hans.van.zwol@xs4all.nl

Thank you for any helpful suggestions!

Hans van Zwol

[joaquintides]

Logged In: YES 
user_id=911241

Hello Hans,

You're not the first one trying to use BGL and Boost.MultiIndex jointly.
Unfortunately, this is not an easy task: at first sight seems like
boost::adjacency_list could be customized to use multi_index_container as
its base container, and indeed this can be done, but in this case the
user is not free to choose the type of the elements managed internally by
boost::adjacency_list (this is basically an implementation detail) and
thus cannot take advantage of Boost.MultiIndex to add supplementary
indices.

That said, a Boost user called Alexander (don't have the family name)
explored this same issue in early 2005 and came up with a way to tie the
two structures together, see the whole discussion at:

http://lists.boost.org/Archives/boost/2005/01/79378.php

and in particular this post:

http://lists.boost.org/Archives/boost/2005/02/79630.php

The technique exploits some undocumented implementation details
of BGL and thus cannot be said to constitute a clean solution to
this problem, but it is as of today about the only way to do it.

It might be interesting to initiate a discussion on the Boost list
about possible ways yo integrate BGL and Boost.MultiIndex, but
this would only produce some usable result, if any, in the long
term.

Hope this helps,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

[joaquintides]

Logged In: YES 
user_id=911241

Hello Hans,

You're not the first one trying to use BGL and Boost.MultiIndex jointly.
Unfortunately, this is not an easy task: at first sight seems like
boost::adjacency_list could be customized to use multi_index_container as
its base container, and indeed this can be done, but in this case the
user is not free to choose the type of the elements managed internally by
boost::adjacency_list (this is basically an implementation detail) and
thus cannot take advantage of Boost.MultiIndex to add supplementary
indices.

That said, a Boost user called Alexander (don't have the family name)
explored this same issue in early 2005 and came up with a way to tie the
two structures together, see the whole discussion at:

http://lists.boost.org/Archives/boost/2005/01/79378.php

and in particular this post:

http://lists.boost.org/Archives/boost/2005/02/79630.php

The technique exploits some undocumented implementation details
of BGL and thus cannot be said to constitute a clean solution to
this problem, but it is as of today about the only way to do it.

It might be interesting to initiate a discussion on the Boost list
about possible ways yo integrate BGL and Boost.MultiIndex, but
this would only produce some usable result, if any, in the long
term.

Hope this helps,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo