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

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