Re: [boost] [graph] question regarding iterators vs descriptors

From: Doug Gregor (dgregor_at_[hidden])
Date: 2007-07-27 12:39:19

On Jul 27, 2007, at 12:25 AM, Hervé Brönnimann wrote:
> In the case that vertices or edges always live in the graph class  
> (i.e., belong to the container), all the problems would be solved  
> by having a descriptor-to-iterator conversion (debated on this  
> mailing list a while ago, IIRC).  Actually, list and set have this  
> capability, but only if you use your own, the standard containers  
> don't give this to you (and rightly so, I guess, it is very unsafe:  
> it is only safe if you can guarantee that the object to which you  
> have a descriptor to does live in the container).

That depends on what your descriptor is... a descriptor could be an  
iterator, or a thin wrapper around that iterator. It depends on your  
data structure. Still, the fundamental issue remains: *what

> Providing your own list and set in Boost.graph would be a bit heavy- 
> handed...  but it would guarantee that you never have to pay more  
> than necessary.  Since you didn't feel the need to do it, I want to  
> ask:  did you ever encounter a case where the extra cost in  
> removing an edge by descriptor affected the overall complexity of  
> the program?

Not personally, but I imagine it could happen. I typically use remove_ 
(out_)edge_if when I need to remove multiple edges.

> On a related question, I could not find an operation on a  
> Bidirectional Graph where you can in O(1) time connect the out-edge  
> (u,v) of u, to the in-edge (u,v) of v.  It is quite standard for  
> undirected graphs to have such links (I do not know if there is a  
> standard terminology).

I think we're tripping over terminology. A bidirectional graph is one  
where we can iterate over both the incoming and the outgoing edges of  
a vertex. In a bidirectional graph, such as an adjacency_list with  
bidirectionalS, an edge (u, v) will show up as an out-edge of u and  
an in-edge of v, but it's exactly the same edge. That's why we need  
edge descriptors: the out-edge and in-edge iterators have completely  
different types, but both of them eventually refer to the same edge  
by its descriptor.

To optimize edge removal, one would want the representation of edges  
to contain copies of the iterators into both the in-edges and out- 
edges list. I thought I had implemented this optimization at one  
point, but perhaps not.

> I ask because for such guarantees you could also guarantee edge  
> removal in O(1) time (amortized for vectors, and worst-case for  
> list).  Such guarantee is important for some graph algorithms. Even  
> if this operation is not provided by any Boost.Graph concept, is it  
> offered by the adjacency_list class?

That's why adjacency_list has overloads of the remove_edge function  
that take in out_edge_iterators. That way, with directed graphs we  
get O(1) removal time; bidirectional and undirected graphs would  
still need more time, unless we store the in-edge iterator inside the  
representation of an edge.

Of course, optimizing for edge-removal time requires us to use more  
storage for edges. So many trade-offs in the design of graph data  
structures.

        - Doug