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