From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2007-07-27 00:25:49
Doug: thanks for your answer. Just to clarify Huseyin's question:
in his work on a generic planar subdivision library (based on
halfedges), we follow the Boost.Graph approach of concepts and model
using container tags, descriptors, etc. I don't know that we need
descriptors for the reason you stated - or rather, our descriptors
could well be iterators. We'll have to see.
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). 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?
Now that I went back to see the MutableGraph complexity guarantees,
it makes sense. I had always assumed edge removal was guaranteed O
(1), not O(E).
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 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?
-- Hervé Brönnimann hervebronnimann_at_[hidden] On Jul 26, 2007, at 8:26 PM, Douglas Gregor wrote: > > On Jul 26, 2007, at 1:34 PM, Huseyin Akcan wrote: >> I guess my main question is does using descriptors have advantages >> over iterators in the design or the runtime of the graph library? >> Also are there other specific reasons to use descriptors that you >> experienced? >> Any insight on this issue would be appreciated. > > The reason we need descriptors in the Graph library is that there are > many different ways to iterate over a particular data structure, all > with different iterator types, but we need a common type to talk > about what those iterators refer to... that's why all of the > iterators into a graph (say, into the adjacency_list) point to vertex > or edge descriptors. That extra level of indirection allows us to > talk about vertices or edges in the abstract sense, regardless of the > way that we found those vertices or edges (enumerating out-edges, in- > edges, neighbors, etc.) > > Now, we have run into similar problems with descriptors not always > being the best answer for inserting or removing values from > containers. To get around this, there are a few extra overloads for > routines such as remove_out_edge (in the adjacency_list) that accept > out_edge_iterators rather than edge descriptors. The iterator-based > versions are more efficient, but the descriptor-based versions are > more flexible (since they can take the descriptors returned from > other kinds of iterators). > > - Doug > _______________________________________________ > Unsubscribe & other changes: http://lists.boost.org/mailman/ > listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk