Re: [Boost-users] Re: [boost graph] adjusting vertex_descriptors whenperforming a remove_vertex

From: Jeremy Graham Siek (jsiek_at_[hidden])
Date: 2005-03-15 11:25:32

Hi Yariv,

On Mar 15, 2005, at 10:57 AM, Yariv Tal wrote:
> 1) IMHO it should be documented in remove_vertex that if you use vecS 
> for
> the vertices any of the previous vertex_descriptors held might become
> invalid (due to renumbering).

It is documented. See the section titled "Iterator and Descriptor 
Stability/Invalidation" in
http://www.boost.org/libs/graph/doc/adjacency_list.html

> 2) How about allowing for leaving removed vertices in the vector, 
> marked as
> "deleted", and allow for a "compress" method on the graph instead?

That's an interesting idea.

> 3) If I use listS, would I need to managed the vertex_index prperty 
> myself
> (initially setting it and later renumbering it) or is it done by the 
> BGL?

You would need to.

> 4) I think the main problem with the vector implementation is that I am
> missing a way to access a vertex using a unique identifier. This could
> probably have been solved if I could add a special "id" property map 
> that
> instead of allowing access to the property with a vertex_descriptor key
> would allow access to the vertex_descriptor with some user defined 
> "id" as
> key (a multimap could be used to allow for non-uniqueness of the
> id<->vertex_descriptor association). This property map would of course 
> be
> automatically updated on vertex removal...
> But, maybe it's too much for a single problematic use case, especially 
> since
> listS supplies a solution, even if not one I am happy with...

What don't you like about the listS solution?

Cheers,
Jeremy

_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Candidate, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________