Re: [boost] Re: BGL - how to find end of predecessor chain?

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2000-10-17 15:04:59

Hi everyone:

I'm new to the list, but I find it interesting. Thanks to all the
contributors. Upon reading a thread:

On Tue, Oct 17, 2000 at 02:39:43PM -0500, jsiek_at_[hidden] wrote:
> Thinking about this some more, an even better (and more generic) way
> to mark the end of the predecessor chain is to initialize the source
> vertex's predecessor to itself and leave the rest uninitialized. Or,
> in the case of depth-first search (which creates a forest), intialize
> the predecessor of each vertex to itself. Thereby a root node is
> distinguished by being its own parent.

This discussion reminds me of an invention of Lutz Kettner. He called it
circulator. Intuitively, iterators iterate over a range, and circulators
add the capability to have a "circular range". Lutz needed it in his
implementation of half-edge data structures, and it is also needed in
planar maps and other geometric structures. This is why they are part of
the CGAL library.

Circulators would provide a nice library for boost, I'll make sure to
mention it to Lutz. Meanwhile, check out:

CGAL: computational geometry algorithms library ( http://www.cgal.org/ )
and especially the reference manual for circulators (can view it at
http://www.cgal.org/Manual/doc_html/frameset/fsSupport.html )

Lutz's article "Using Generic Programming for Designing a Data Structure
for Polyhedral Surfaces", CGT&A (first article on the page
http://www.cs.unc.edu/~kettner/pub/index.html )

Cheers,
-- 
Hervé