Re: [Boost-users] vertex descriptors

From: Luis Quesada (luque_at_[hidden])
Date: 2005-12-01 16:00:29

Luis Quesada wrote:

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

I meant list of vertices.

> in order to find the vertex with that name). However, I wonder whether 
> you can do better than that....
>

Well, one way could be to adopt a lazy approach: instead of updating the 
map each time a removal takes place, one can update the map when 
getDescriptor is called only if a removal has taken place before.

Luis