[graph] edge_descriptor invalidation
Hello everyone! I'm asking myself, why edge-descriptors become invalid if I remove the edge and reinsert it? In my case the graph is represented by an adjacency list with vecS storage for vertices and edges. If I'm not mistaken, then the edge_descriptor's are just represented by pairs of vertex indices, right? So why are edge_descriptors invalid if I delete these edges, reinsert the edges and then want to use the old edge_descriptors to address those recreated edges? Most interestingly, a very cumbersome edge(source(old_descriptor, graph), target(old_descriptor, graph), graph).first gives me perfectly valid edge_descriptors again after removal and insertion. I'm confused. Thanks for any help in advance. Sebastian Weber
On Feb 12, 2008 3:35 AM, Sebastian Weber
Hello everyone!
I'm asking myself, why edge-descriptors become invalid if I remove the edge and reinsert it? In my case the graph is represented by an adjacency list with vecS storage for vertices and edges. If I'm not mistaken, then the edge_descriptor's are just represented by pairs of vertex indices, right? So why are edge_descriptors invalid if I delete these edges, reinsert the edges and then want to use the old edge_descriptors to address those recreated edges? Most interestingly, a very cumbersome
edge(source(old_descriptor, graph), target(old_descriptor, graph), graph).first
gives me perfectly valid edge_descriptors again after removal and insertion.
I'm confused.
Hi Sebastian, An edge_descriptor for an adjacency_list has a source, target, and some property information. So, your call to source(old_descriptor, graph) and target(old_descriptor, graph) above just return the source and target members of the edge descriptor (without ever actually looking at the graph to see that the edge has been removed). Then, when you call edge(source(old_descriptor, graph), target(old_descriptor,graph), graph).first, you get a dummy edge descriptor back - but if you check the second member of the pair returned, you'll see that it's false, meaning that the edge isn't actually in the graph. One reason why edge_descriptors to become invalid once you remove them and reinsert an edge with the same source, target pair is that a source and target don't uniquely define an edge in the type of graph you're using - an edge also contains property information. And since your graph allows parallel edges, it makes even more sense: edge_descriptor e = add_edge(0,1,g).first; edge_descriptor f = add_edge(0,1,g).first; What should the expression e == f return now? It returns false, since these descriptors represent two different edges. What happens when you call edge(0,1,g) now? It returns (e,true) - the edge function just searches through the list of edges in the graph, and it happens to find e first. If you're using a vector, list, or anything else that allows parallel edges as the edge storage for your graph, the source, target pair isn't a unique key for edges. If you need the source,target pair to be a unique key, use a std::set to store the edges (using the setS selector) - it will enforce the uniqueness of a source,target pair and it will dispatch to std::set's find method when you call edge(source,target,graph) instead of resorting to a linear search. Regards, Aaron
Hi Aaron,
One reason why edge_descriptors to become invalid once you remove them and reinsert an edge with the same source, target pair is that a source and target don't uniquely define an edge in the type of graph you're using - an edge also contains property information. And since your graph allows parallel edges, it makes even more sense:
edge_descriptor e = add_edge(0,1,g).first; edge_descriptor f = add_edge(0,1,g).first;
What should the expression e == f return now? It returns false, since these descriptors represent two different edges. What happens when you call edge(0,1,g) now? It returns (e,true) - the edge function just searches through the list of edges in the graph, and it happens to find e first.
If you're using a vector, list, or anything else that allows parallel edges as the edge storage for your graph, the source, target pair isn't a unique key for edges. If you need the source,target pair to be a unique key, use a std::set to store the edges (using the setS selector) - it will enforce the uniqueness of a source,target pair and it will dispatch to std::set's find method when you call edge(source,target,graph) instead of resorting to a linear search.
Thanks Aaron for your answer. However, in my case my graphs do not have any edge properties attached to them. Therefore, in my opinion, a remove_edge and add_edge should not invalidate an edge-descriptor. Regarding the uniqueness of edges: Well, yes, a pair source and target is not unique if parallel edges are allowed, but this does not matter in my case. I only care if there is some connection from source to target. Thus, a pair (source,target) carries this information and this should not become invalidated my removal/adding edges. I guess this scheme of non-unique edge-descriptors is not supported by the BGL, but I think it should be. Uniqueness is always very costly to maintain and it is not always necessary. BTW, I think by now that in my case of an undirected (or directed as well) graph without any edge properties, it would be faster to use the vector_as_graph adapter or am I wrong here? The performance of the vector_as_graph adapter (using a vector as EdgeList) is nowhere documented, but I suspect it to be faster than the corresponding adjacency list. One would loose the PropertyGraph refinement, but gain some speed, right? I think this is very interesting for a lot of people. Greetings, Sebastian Weber
Regards, Aaron _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Feb 13, 2008 3:17 AM, Sebastian Weber
Hi Aaron,
One reason why edge_descriptors to become invalid once you remove them and reinsert an edge with the same source, target pair is that a source and target don't uniquely define an edge in the type of graph you're using - an edge also contains property information. And since your graph allows parallel edges, it makes even more sense:
edge_descriptor e = add_edge(0,1,g).first; edge_descriptor f = add_edge(0,1,g).first;
What should the expression e == f return now? It returns false, since these descriptors represent two different edges. What happens when you call edge(0,1,g) now? It returns (e,true) - the edge function just searches through the list of edges in the graph, and it happens to find e first.
If you're using a vector, list, or anything else that allows parallel edges as the edge storage for your graph, the source, target pair isn't a unique key for edges. If you need the source,target pair to be a unique key, use a std::set to store the edges (using the setS selector) - it will enforce the uniqueness of a source,target pair and it will dispatch to std::set's find method when you call edge(source,target,graph) instead of resorting to a linear search.
Thanks Aaron for your answer.
However, in my case my graphs do not have any edge properties attached to them. Therefore, in my opinion, a remove_edge and add_edge should not invalidate an edge-descriptor. Regarding the uniqueness of edges: Well, yes, a pair source and target is not unique if parallel edges are allowed, but this does not matter in my case. I only care if there is some connection from source to target. Thus, a pair (source,target) carries this information and this should not become invalidated my removal/adding edges. I guess this scheme of non-unique edge-descriptors is not supported by the BGL, but I think it should be. Uniqueness is always very costly to maintain and it is not always necessary.
BTW, I think by now that in my case of an undirected (or directed as well) graph without any edge properties, it would be faster to use the vector_as_graph adapter or am I wrong here? The performance of the vector_as_graph adapter (using a vector as EdgeList) is nowhere documented, but I suspect it to be faster than the corresponding adjacency list. One would loose the PropertyGraph refinement, but gain some speed, right? I think this is very interesting for a lot of people.
Yes, in your case, you could use vector_as_graph to get the desired behavior, but keep in mind that vector_as_graph is a directed graph. I've never seen any timings of it versus adjacency_list, but yes, based on the implementation, a std::vector< X < std::size_t > > used with vector_as_graph should be no slower than an adjacency_list< X, vecS, directedS >, where X is any std container. Regards, Aaron
participants (2)
-
Aaron Windsor -
Sebastian Weber