On Feb 12, 2008 3:35 AM, Sebastian Weber <sebastian.weber@physik.tu-darmstadt.de> wrote:
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