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

From: Yariv Tal (yariv_tal2003_at_[hidden])
Date: 2005-03-15 10:57:35

Hi Jeremy,

"Jeremy Graham Siek" <jsiek_at_[hidden]> wrote in message
news:2122524C-955A-11D9-B4F0-000D932B7330_at_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 <jsiek_at_[hidden]>
> http://www.osl.iu.edu/~jsiek
> Ph.D. Candidate, Indiana University Bloomington
> C++ Booster (http://www.boost.org)
> _______________________________________________

Yariv.