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