Re: [Boost-users] Using external property map with a mutable boost.graph

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-08-30 09:01:09

On Aug 27, 2004, at 4:02 PM, Jeff Holle wrote:

> I'm using a boost.graph via:
> typedef 
> boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS> 
> GraphT;
>
> In my application, I've decided to use external maps.
> I have discovered a problem using vertex descriptors as a key of a map.
>
> Basically, in doing a remove_vertex sequence involving vertex 
> descriptors
> 5, 3, 2, I discovered that the next vertex descriptor produced by 
> add_vertex was 4.  At this point the insert into my map failed because 
> this element already existed.

Right. There's a section in the adjacency_list docs that discusses when 
descriptors and iterators become invalidated, which may help.

> Given the mutable nature of vertex descriptors, I don't see how they 
> can
> be used as a key in a map.

They usually can't be .

> I'm contemplating two options at this point.
>
>  1.  Switch from map to vector in storing my vertex property 
> externally.
>  2.  Switch to internal properties.
>
> My questions are:
>  1.  Is the first option viable?  As I see things, vertex descriptors 
> are always
>       contiguous and in the range (0..num_vertices(graph)].  Is this 
> true?

Yes, but there's an even better way. When you have  a vertex descriptor 
v in a graph g, you can use:

        get(boost::vertex_index, g, v)

to retrieve the index of vertex v (a value in [0:num_vertices(g))), so 
you can use a vector for storage and an iterator_property_map to pass 
your external properties to BGL algorithms. This formulation is 
actually _much_ better than the std::map formulation because:

        1) It's faster, because it's O(1) lookup
        2) It can work if you change the type of the graph so long as you then 
maintain a vertex_index property

>  2.  Do internal "maps" avoid this type of problem?

Yes. The great thing about internal property maps is that they 
grow/shrink along with the graph and require no extra maintenance on 
your part. They'll be even better in Boost 1.32.0, but that's taking us 
quite a while to finish :)

        Doug