vertex descriptors
Dear all, Sorry for the newbie question! 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. 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? Suppose I have done this: // create a typedef for the Graph type typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; // Make convenient labels for the vertices enum { A, B, C, D, E, N }; const int num_vertices = N; const char* name = "ABCDE"; // writing out the edges in the graph typedef std::pair<int, int> Edge; Edge edge_array[] = { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C), Edge(C,E), Edge(B,D), Edge(D,E) }; const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]); // declare a graph object Graph g(num_vertices); Then I remove some vertices. Now I want to check whether edge <A,B> is still there. Calling edge(A,B,g) would not be OK because the descriptors are no longer referring to the same vertices.... Thanks in advance for your answer, Luis
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 Doug
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
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 <i,j> (where i and j are original indexes) is in the graph in a context where descriptors are invalidated. Luis
On Dec 1, 2005, at 5:27 AM, Luis Quesada wrote:
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).
Ah, that's a bit more tricky.
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 <i,j> (where i and j are original indexes) is in the graph in a context where descriptors are invalidated.
Ah, then take Johan's advice :) Invalidating descriptors can be very dangerous, and you will definitely need to clear_vertex before remove_vertex, otherwise your program will become unstable. If you're doing lots of removals, you might want to use a graph type with stable descriptors (e.g., adjacency_list with listS/listS). Doug
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 <i,j> (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
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
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
On 12/1/05, Luis Quesada <luque@info.ucl.ac.be> 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 -- Johan
Johan Oudinet wrote:
On 12/1/05, Luis Quesada <luque@info.ucl.ac.be> 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
On 11/30/05, Luis Quesada <luque@info.ucl.ac.be> 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).
Then I remove some vertices. Now I want to check whether edge <A,B> is still there. Calling edge(A,B,g) would not be OK because the descriptors are no longer referring to the same vertices....
Yes, after removing some vertices without their edges, you have an undefined behavior. -- Johan
Johan Oudinet wrote:
On 11/30/05, Luis Quesada <luque@info.ucl.ac.be> 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
On 12/1/05, Luis Quesada <luque@info.ucl.ac.be> wrote:
Johan Oudinet wrote:
On 11/30/05, Luis Quesada <luque@info.ucl.ac.be> 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.
No, this behavior is specific to vecS container whom vertex descriptors are int. But, if you use listS, setS, multisetS, etc.. vertex descriptors are void* and you can't describe them with an enum. Your example doesn't support remove_vertex. -- Johan
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
On Thu, 2006-12-14 at 04:52 +0000, Silvia Richter wrote:
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.
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. I believe the table is referring to the stability of other vertices in the graph, e.g., clear_vertex(u) does not affect a traversal through a different vertex v's edges. For your case, you'll probably need to either make a copy of the adjacent vertices before calling clear_vertex(), or use a function like remove_out_edge_if that lets you example each edge as just before it is removed. Cheers, Doug
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.
On Dec 17, 2006, at 3:07 AM, Silvia Richter wrote:
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 (?)
I believe that is just a coincidence. Once the call to clear_vertex() has been made, any use of adjacency_iterator for that vertex is "undefined behavior", which means that it might work on might fail... we just won't know. Cheers, Doug
participants (6)
-
Doug Gregor -
Douglas Gregor -
Grégoire Dooms -
Johan Oudinet -
Luis Quesada -
Silvia Richter