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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-02-13 08:43:39

On Feb 13, 2008 3:17 AM, Sebastian Weber
<sebastian.weber_at_[hidden]> wrote:
> 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