[graph] question regarding iterators vs descriptors
Hello, I'm developing the geometric library for the summer of code 2007. In our design, we use descriptors similar to the graph library. But we are having problems with the descriptors especially when carrying out the erase methods for containers, where iterators are needed. In our case using iterators for list and set containers seems more natural than using descriptors. On the other hand, descriptors can be handled easily on vector, and they enable a stable way to access container elements under certain operations( such as resize). We are in the process of deciding whether to continue with the descriptors or iterators, or maybe something hybrid. 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. Thanks, huseyin
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
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@mac.com 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
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
participants (4)
-
Doug Gregor -
Douglas Gregor -
Hervé Brönnimann -
Huseyin Akcan