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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-02-12 23:12:22

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