Re: [Boost-users] vertex descriptors

From: Luis Quesada (luque_at_[hidden])
Date: 2005-12-01 14:51:06

First of all, thanks for all the replies!

Grégoire Dooms wrote:

> Do you mean you want to use vecS for the vertex_list of G and be able 
> to do something along these lines :
> assert(edge(b,c,G).second && b!=a && c!=a);
> clear_vertex(a,G);
> remove_vertex(a,G);
> //then
> assert(edge( smthg(b), smthg(c) , G).second);
>
> And your question would be :
> what can I use to implement the smthg in order to have this last 
> assertion correct ?
>
I think this is my question. However, just to be sure, let me rephrase 
it as follows:

Suppose we have given names to the nodes (by using the /property map/ 
interface), what I want to have is a function getDescriptor(g,name) that 
returns the descriptor of the vertex that has name "name".

It is clear that function is constant if listS is used (because 
descriptors are stable so we can just use a map). It is also clear that 
you can implement such a function in linear time when vecS is used (just 
traverse the list of edges in order to find the vertex with that name). 
However, I wonder whether you can do better than that....

Luis