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