[BGL] combining kdtree-style operations
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. The classic algorithm for this type of problem is the KD-Tree, a structure optimised for spatial lookups in K-dimensional space. It uses the same technique as a binary search, but at each level, the next dimension is compared... until K, at which point the iteration starts again from 0. Bentley, J. L., Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 A demo for 2 dimensional search: http://www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm 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). 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? - 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>). Basically, between its current version and a final version ("1.0"), the following needs to be done: * clean up the source code to make it less cryptic (1 day) * figure out how to implement erase-and-optimise efficiently (1 week) * figure out a way to make the coordinates mutable so that the tree can accomodate moving objects (although it's probably not the best container for e.g. particle systems). * push decisions down into policies (it already uses comparator and allocator policies). 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. Thanks for your time and patience. -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net "half a bee, philosophically, must ipso facto half not be." -- monty python
Hi Martin, Sounds neat! Though at this time I can do no more than give you my encouragement! Cheers, Jeremy 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.
The classic algorithm for this type of problem is the KD-Tree, a structure optimised for spatial lookups in K-dimensional space. It uses the same technique as a binary search, but at each level, the next dimension is compared... until K, at which point the iteration starts again from 0.
Bentley, J. L., Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975
A demo for 2 dimensional search: http://www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm
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).
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?
- 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>). Basically, between its current version and a final version ("1.0"), the following needs to be done:
* clean up the source code to make it less cryptic (1 day) * figure out how to implement erase-and-optimise efficiently (1 week) * figure out a way to make the coordinates mutable so that the tree can accomodate moving objects (although it's probably not the best container for e.g. particle systems). * push decisions down into policies (it already uses comparator and allocator policies).
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.
Thanks for your time and patience.
-- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net
"half a bee, philosophically, must ipso facto half not be." -- monty python _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________
also sprach Jeremy Siek <jsiek@osl.iu.edu> [2005.05.16.1810 +0200]:
Sounds neat! Though at this time I can do no more than give you my encouragement!
Okay. I hope someone finds the time to walk through the application process (and the code preparation process before that) with me, since I really cannot afford to expend too much time at this stage either. -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net "courage is not the absence of fear, but the decision that something else is more important than fear." -- ambrose redmoon
I just imported the libkdtree CVS into arch, and it may now be conveniently viewed at http://xrl.us/f4r7 [0] The page also offers a tarball download a tarball tree. The arch archive is located at: madduck@arch.madduck.net--2005-coding http://arch.madduck.net/~madduck/pub/2005/coding and the category is libkdtree--main--0. 0. http://arch.madduck.net/cgi-bin/archzoom.cgi/madduck@arch.madduck.net--2005-... -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net last year, out in california, at a pc users group, there was a demo of smart speech recognition software. before the demonstrator could begin his demo, a voice called out from the audience: "format c, return. yes, return." a short demo it was.
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
also sprach Douglas Gregor <doug.gregor@gmail.com> [2005.05.19.0511 +0200]:
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.
Well, I would be honoured. I must warn you though that this process could take months because I am completely overworked right now. If you have no problem working over long periods on the same thing with infrequent change bursts, I would be glad. What would be the first step? The licence is currently artistic, which is probably not a problem. I have no problem in changing that either. Note that one other person has contributed to this licence, and I have asked him about the licence issues. He is okay with the artistic licence, so if that is compatible, there is no problem. One thing I know for sure is the need for unit tests/examples/regression tests (though I have to read up on what exactly regression tests are...), but since I just finished reading Kent Beck's TDD book, I am all too excited to add those when I have another free moment (like in 2006 or so ;>). Documentation is missing. Other than that, I cannot immediately tell what I would have to do to boostify. Note that I have zero (!) experience with portability; I have used GNU/Linux basically all my life.
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
This *does* sound nice. The problem is that the edges in the KDTree are not necessarily the edges in the graph (in fact, they are not most of the time). Thus, in order to be able to answer out_edges(), I would have to keep an edge list for each node -- the primary reason I wanted to use the BGL in the first place so that I don't have to worry about that.
- 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 :)
Really? Here's a quote from the code: if (_S_left(__N)) { _Link_type __l = _M_get_j_max(_S_left(__N), __j, __L+1); if (__cmp(__ret, __l)) { __ret = __l; } } I liked it at the time; it made me feel special and cool. Now I regret using this crap. Also, the leading underscores are a problem with gcc (reserved for internal use), so they will have to go anyway. Cheers, -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net why didn't noah swat those two mosquitoes?
also sprach martin f krafft <madduck@madduck.net> [2005.05.19.1923 +0200]:
What would be the first step? The licence is currently artistic, which is probably not a problem. I have no problem in changing that either. Note that one other person has contributed to this licence, and I have asked him about the licence issues. He is okay with the artistic licence, so if that is compatible, there is no problem.
He would be honoured if any of his submissions made it into boost. Thus, libkdtree is ready for boost in terms of the licence. -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net hi! i'm a .signature virus! copy me into your ~/.signature to help me spread!
participants (3)
-
Douglas Gregor -
Jeremy Siek -
martin f krafft