Re: [Boost-users] [BGL, Graph] choose the correct container to handlegraph with a property

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-11-21 08:48:14

Johan Oudinet ha escrito:

> Hello,
> I have a graph representing the Network topology and I want to replace
> it by a BGL graph.
> My problem is that I need to find a vertex by its IP address (an
> internal property), but I think we can only find a vertex with its
> vertex_descriptor. A solution is to maintain a map from IP address to
> vertex_descriptor.
> But removing a vertex with vecS for VertexList invalidates all vertex
> descriptors. Unfortunately, I need some efficiently to find a vertex,
> so listS seems not appropriated.

[...]

> Hence, my questions are:
> - Can I use setS for VertexList ? And if I can't, why ?

[...]

I think a multi_index_container would be a perfect fit here,
because it can provide a sequenced index as the VertexList
interface and additional ordered indices for lookup.
Unfortunately, this cannot be made to work without some serious
hacking, unless BGL provided additional guarantees on some
internal details of adjacency_list. The complete story can be read
at

http://thread.gmane.org/gmane.comp.lib.boost.devel/116970

where you can find the efforts of a guy called Alexander to blend
BGL and Boost.MultiIndex. In the end he succeeded, but only at
the expense of relying on the internal implementation of
adjacency_list. 100% unsafe.

Of course, it this a recurrent need I think it'd be great if
adjacency_list
can be extended/overspecified so as to work with multi_index_containers.
My hunch is that little actual work would be needed.

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