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

Hi Jeremy, "Jeremy Graham Siek" wrote in message news:2122524C-955A-11D9-B4F0-000D932B7330@osl.iu.edu...

Hi Yariv,

On Mar 15, 2005, at 6:44 AM, Yariv Tal wrote:

...

Even worse: as far as I undertand if I use listS then vertex_desfcriptor is no longer an index an no renumbering occurs in remove_vertex!

Sure, but you don't want renumbering, do you? And if you do, then you can do the renumbering yourself.

...

So, unless I want to commit to using vecS and to a specific implementation I need to somehow KNOW whether or not to perform renumbering. I coulld do this via a traits template with sepcialization for each vertices container type, but it seems to me that the library should have (and probably has) a better way of abstracting this, no?

Yes, vertex indices and renumbering are a trouble-spot for adjacency list and could use improvement.

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). 2) How about allowing for leaving removed vertices in the vector, marked as "deleted", and allow for a "compress" method on the graph instead?

...

Perhaps the problem is that I'm storing vertex_descriptors in the ObjVertexMap, which may be defined as transient entities that (like iterators after an erase) might be invalidated after a remove_vertex - but then, how can I hold some persistent and efficient identifier into the graph that remains valid after remove_vertex?

It sounds like you need to use listS and manage the vertex indices yourself.

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? 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...

Cheers, Jeremy

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

Yariv.