BGL defining my own iterator?
Hi all, For traversing the faces of a planar BGL graph I store 'next' pointers in a bundled property for each edge. I can go round a face of the graph like this: BGLGraph g; edge_descriptor current,start; // initialize these! do { // do something with current current=g[current].next; } while(current!=start); Now I was thinking that a lot of 'boilerplate' code would be eliminated if I could do these loops with BOOST_FOREACH. Following the tutorial for iterator_facade I am trying something like this: https://github.com/aewallin/sandbox/blob/master/bgl_iterator/main.cpp However as commented in the code it doesn't quite work. I get either no iterations, one iteration, or all but one edge. Also, holding a pointer to an edge_descriptor in the iterator class doesn't strike me as very elegant, could I store an edge_descriptor directly? suggestions? thanks, AW
On Thu, 22 Dec 2011, Anders Wallin wrote:
Hi all,
For traversing the faces of a planar BGL graph I store 'next' pointers in a bundled property for each edge. I can go round a face of the graph like this: BGLGraph g; edge_descriptor current,start; // initialize these! do { // do something with current current=g[current].next; } while(current!=start);
Now I was thinking that a lot of 'boilerplate' code would be eliminated if I could do these loops with BOOST_FOREACH. Following the tutorial for iterator_facade I am trying something like this: https://github.com/aewallin/sandbox/blob/master/bgl_iterator/main.cpp
However as commented in the code it doesn't quite work. I get either no iterations, one iteration, or all but one edge.
In your second test, begin and end have the same edge, so they compare equal using your iterator's == operator, breaking the loop immediately. Does the do loop you use in your first test case work with iterators? If so, you will need some special-case way to create an end iterator; I know Boost.Intrusive has a circular linked list class (slist), so checking that code might show how to set up the iterators.
Also, holding a pointer to an edge_descriptor in the iterator class doesn't strike me as very elegant, could I store an edge_descriptor directly?
Yes, as long as it isn't invalidated by any of the graph modifications you do. -- Jeremiah Willcock
In your second test, begin and end have the same edge, so they compare equal using your iterator's == operator, breaking the loop immediately. Does the do loop you use in your first test case work with iterators? If so, you will need some special-case way to create an end iterator; I know Boost.Intrusive has a circular linked list class (slist), so checking that code might show how to set up the iterators.
I now got both a do-while and a BOOST_FOREACH loop working, but only when building in debug mode. When built in release mode (NDEBUG and -O3) I the iterator gives incorrect results in both cases. Output along with a compilation warning is here: http://pastebin.ca/2096568 updated code is here: https://github.com/aewallin/sandbox/blob/master/bgl_iterator/main.cpp what causes this difference in behaviour with NDEBUG and -O3 ? thanks, AW
On Tue, 27 Dec 2011, Anders Wallin wrote:
In your second test, begin and end have the same edge, so they compare equal using your iterator's == operator, breaking the loop immediately. Does the do loop you use in your first test case work with iterators? If so, you will need some special-case way to create an end iterator; I know Boost.Intrusive has a circular linked list class (slist), so checking that code might show how to set up the iterators.
I now got both a do-while and a BOOST_FOREACH loop working, but only when building in debug mode. When built in release mode (NDEBUG and -O3) I the iterator gives incorrect results in both cases. Output along with a compilation warning is here: http://pastebin.ca/2096568
updated code is here: https://github.com/aewallin/sandbox/blob/master/bgl_iterator/main.cpp
what causes this difference in behaviour with NDEBUG and -O3 ?
Sorry about not responding to this earlier. The code you posted will not work for an empty iterator range (due to the check for m_inc) and it seems like comparisons of arbitrary edge_iterators (rather than just a comparison to the end) are not supported. I looked at how boost::intrusive::slist does their iterators, and they have a dummy node in the circular list that is used to represent the end. It looks like CGAL doesn't try to provide the iterator-pair interface to their circular lists at all. Maybe you could store a pointer to the last element of the list (or the first) in each iterator, and special-case incrementing onto that element to act like a non-circular list would (using an invalid list element). Would that make sense for you? Are you going to be changing these edge cycles often? -- Jeremiah Willcock
participants (2)
-
Anders Wallin -
Jeremiah Willcock