Re: [Boost-users] [BGL] combining kdtree-style operations

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-05-18 22:11:01

Hello,

On May 16, 2005, at 10:13 AM, martin f krafft wrote:
> I am looking at a complex project I am about to implement with BGL.
> Among regular graph operations, we need each vertex/edge to be
> located in Cartesian space (a Coordinate property will do) and for
> any point P in this Cartesian space (which may coincide with
> a vertex or edge) determine the set of geographically close
> vertices/edges (within the sphere of radius r, centred at P). Thus,
> the result set is essentially completely independent of the graph's
> structure, only dependent on the Coordinate property of the graph
> elements.

Interesting.

> I have written a nice, flexible STL-container-style KDTree
> implementation:
>   http://freshmeat.net/projects/libkdtree
>
> This uses its own tree implementation along with bidirectional
> iterators. Since it stores edges and vertices in the same data
> structure, it does not really make for a good base container for the
> BGL. It would be possible to use separate trees for edges and
> vertices, but another problem makes that really difficult: changes
> to the Cartesian coordinates basically require the object to be
> removed and reinserted into the tree, and erasure does not work
> reliably currently (I have not found a viable update strategy).

libkdtree could clearly be proposed as a Boost library with primarily 
cosmetic changes ("Boostifying" the code, as it were). If you would 
like to pursue this, I'd be glad to help guide you through the process.

> Now I am faced with the task of combining that with the BGL. Thus,
> I am weighing options:
>
>   - does anyone work with KD Trees and the BGL who'd be willing to
>     share experiences with me? In particular, I wonder whether it is
>     possible
>
>       * to use the same data structures for both, such that I do not
>         have to store multiple pointers for my objects, one in the
>         graph and one in the KD tree?
>
>       * to implement KD trees with BGL?

I have a shallow understanding of KD trees but a rather deep 
understanding of the BGL. While you could implement KD trees as a 
graph, it doesn't strike me as being the right abstraction. Rather, I 
think your central data structure will be something very like a KD tree 
(although perhaps drawing a more pronounced distinction between 
vertices and edges in the data structure). Then, you can give it a BGL 
interface just by writing free functions that make the KD tree look 
like a graph... vertices(), edges(), out_edges(), etc. If the data 
structure can support these operations, it will be easy to make it work 
with BGL algorithms.

>   - would this library be a candidate for Boost and/or the BGL?
>     I realise that it's way too STL-centric right now (I somehow got
>     a kick out of using the same variable naming scheme as the SGI
>     STL implementation, which was made by people with obvious
>     psychiatric needs (</humour>).

Boost tends to use a similar naming scheme. I'll let you draw your own 
conclusions :)

> So this email does two things:
>
> If you are familiar with KD trees and the BGL, please give me some
> insight into your approach.
>
> If you are interested in the KD tree implementation and think that
> it would be a good candidate for boost, consider helping out to
> attack the TODO list, and if only with conceptual discussion.

I'm far too overcommitted to help with development of such a library, 
but I can often guidance through the Boost review process, read through 
and comment on source code and interface design, and (perhaps) give 
some feedback on data structure designs with respect to graphs.

        Doug