Douglas Gregor wrote:

On Nov 30, 2005, at 2:06 PM, Luis Quesada wrote:

...

Given the index of a vertex, how can I get its descriptor? I guess function vertex (page 225 of The Boost Graph Library) does that but the function is not defined.

For adjacency_list, there is a vertex function:

vertex(i, g)

returns the ith vertex in the graph g. It's documented in the "Non- Member Functions" section of

http://www.boost.org/libs/graph/doc/adjacency_list.html

Indeed. However vertex returns the descriptor of the ith vertex in the *current* graph. What I actually need is the descriptor of the ith vertex in the original graph (before any removal has taken place). If descriptors are not invalidated, the simple solution is to have a vector mapping original indexes to descriptors. However, I want to know what is the most appropriate way of checking whether edge (where i and j are original indexes) is in the graph in a context where descriptors are invalidated. Luis

Luis Quesada wrote:

If descriptors are not invalidated, the simple solution is to have a vector mapping original indexes to descriptors. However, I want to know what is the most appropriate way of checking whether edge (where i and j are original indexes) is in the graph in a context where descriptors are invalidated.

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 ? My answer: I don't know, you'd better use listS. Maybe somebody else has an other idea... Best, -- Grégoire Dooms

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

Johan Oudinet wrote:

On 12/1/05, Luis Quesada wrote:

...

First of all, thanks for all the replies!

[snip]

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

Or you can use multi-index containers: http://groups.google.fr/group/boost-list/browse_thread/thread/5bc0b508b8a45c52/4ad8301d16fa7f87?lnk=st&q=graph+multi-index+container&rnum=3#4ad8301d16fa7f87

Thanks a lot for the link! It would be great to support this kind of look up in BGL. Luis

Johan Oudinet wrote:

On 11/30/05, Luis Quesada wrote:

...

In fact, what I want to do is to check whether an edge belongs to a graph in a context where descriptors get invalidated after vertex removals?

You must avoid invalidated descriptors ! Before removing a vertex u, you have to remove all out_edges from u and in_edges to u. use: clear_vertex(u, g) before remove_vertex(u, g).

I may be using the term "invalid" in the wrong way... What I mean, in the example attached, is that descriptor 3 is no longer associated to node D but to E after C's removal. In that sense 3 becomes an "invalid" descriptor of node D. I think this cannot be avoided even though clear_vertex is used. Luis

Hi, I'm not sure whether to post here or create a new thread. But since your topic is very similar to my question, I'll post it here. I have been using listS for both edges and vertices with adjacency_list. According to the online documentation of BGL, clear_vertex() should not invalidate the adjacency_iterator in this case. However, in my code that's exactly what happens: I call adjacent_vertices() on a vertex A, which gives me an adjacency_iterator. Then I remove all edges from A by calling clear_vertex(). Then I want to use the adjacency_iterator obtained previously to check the new degrees of all (previous) neighbours of the removed vertex v. But the program crashes with a segmentation fault, when I try to use the iterator. Has anyone experienced this before? Or do you have any ideas how to make it work? Cheers, Silvia

Douglas Gregor wrote:

On Thu, 2006-12-14 at 04:52 +0000, Silvia Richter wrote:

...

I call adjacent_vertices() on a vertex A, which gives me an adjacency_iterator. Then I remove all edges from A by calling clear_vertex(). Then I want to use the adjacency_iterator obtained previously to check the new degrees of all (previous) neighbours of the removed vertex v. But the program crashes with a segmentation fault, when I try to use the iterator.

Unfortunately, this won't work. Once you've called clear_vertex(), the data that the adjacency_iterator for that vertex relies on has been removed.

Thanks for that. I have in the meantime posted another comment (you may have seen it), when I experienced that my code works with certain older compilers, but not with newer ones. Looks like that is just coincidence, then (?) Cheers, Silvia -------------------------------------------------------------------------- This email and any attachments may be confidential. They may contain legally privileged information or copyright material. You should not read, copy, use or disclose them without authorisation. If you are not an intended recipient, please contact us at once by return email and then delete both messages. We do not accept liability in connection with computer virus, data corruption, delay, interruption, unauthorised access or unauthorised amendment. This notice should not be removed.