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

I'm using a boost.graph via: typedef boost::adjacency_listboost::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