Re: [Boost-users] [graph] edge_descriptor invalidation

From: Sebastian Weber (sebastian.weber_at_[hidden])
Date: 2008-02-13 03:17:24

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users