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