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