n-ary ordered tree template in boost ??
Dear Boost Members I was wondering if there is an n-ary ordered tree template in boost, something like template <size_t N, class Type, class Alloc = allocator<Type > > class NTree which is a standard container, and a reversible container, ordered by level. That is, first element is root, next series of elements are childs of roots, next series are grandchilds of root , and so on. This way one could parse level by level like a reversible container. There should be the obvious member functions for inserting/deleting child nodes and subtrees. As far as I can see, there is not such a template in boost, but the question is then: 1) can it be emulated using the grah library ?? or 2) is there already an proposal/prototype for such a thing ?? or 3) would it be interesting to include such a thing in boost ?? your's sincierely, Marc Cromme
You could chose to emulate such an tree using a std::multimap. Which maps the father vertex id to the child vertices. you can also specify your own ordering relation. To access all children is trivial, if you want to access all grandchilds and so own, you'd have to create a nice adapter class, that connects all children of children ranges together. ----- Original Message ----- From: "Marc Cromme" <yg-boost-users@m.gmane.org> Newsgroups: gmane.comp.lib.boost.user Sent: Friday, August 30, 2002 10:49 AM Subject: n-ary ordered tree template in boost ??
Dear Boost Members
I was wondering if there is an n-ary ordered tree template in boost, something like
template <size_t N, class Type, class Alloc = allocator<Type > > class NTree
which is a standard container, and a reversible container, ordered by level. That is, first element is root, next series of elements are childs of roots, next series are grandchilds of root , and so on.
This way one could parse level by level like a reversible container.
There should be the obvious member functions for inserting/deleting child nodes and subtrees.
As far as I can see, there is not such a template in boost, but the question is then:
1) can it be emulated using the grah library ??
or
2) is there already an proposal/prototype for such a thing ??
or
3) would it be interesting to include such a thing in boost ??
your's sincierely,
Marc Cromme
On Mon, 02 Sep 2002 10:47:42 +0200, Matthias Kronenberger wrote:
You could chose to emulate such an tree using a std::multimap. Which maps the father vertex id to the child vertices. you can also specify your own ordering relation. To access all children is trivial, if you want to access all grandchilds and so own, you'd have to create a nice adapter class, that connects all children of children ranges together.
I thought of this, too, but then, there is a simpler emulation using the property that an N-ary ordered tree has nodes with either no child or exactly N childeren. This menas that we can number the nodes of a complete tree by (if N=3) level 0: 0 level 1: 1 2 3 level 2: 4 5 6 7 8 9 10 11 12 and so on. Very simple calculations then give the id numbers of all children of a given parent, or the parent of a given child, and so on. If the tree is not complete, some of the groups are missing, but the same ordering can still be applied. Putting this in a pair<size_t id, Node data>, we can store it in a map, not a multimap, and we have automagically iterators which parse the tree in levels. The concept is quite simple, but usefull, at least if you want to parse efficiently horizontally. If you want to parse up-down, it requires an O(log n) lookup in the map, and then you probably want to implement this thing in a pointer-to-children and pointer-to parent fashion for efficiency. But this get us back to the original question: 2) An N-ary ordered tree is such a basic concept that it is funny that neither STL or Boost offers it. Would it be welcome by the Boost community if it get proposed and included into the Boost libs ??? cheers, Marc Cromme
Well, you could even use a vector for that simple n-ary tree. Anyway, i think that trees are not an important data type. Most of the time, you 're better of with a multimap, or even a simple vector. ----- Original Message ----- From: "Marc Cromme" <yg-boost-users@m.gmane.org> Newsgroups: gmane.comp.lib.boost.user Sent: Monday, September 02, 2002 8:54 PM Subject: Re: n-ary ordered tree template in boost ??
On Mon, 02 Sep 2002 10:47:42 +0200, Matthias Kronenberger wrote:
You could chose to emulate such an tree using a std::multimap. Which maps the father vertex id to the child vertices. you can also specify your own ordering relation. To access all children is trivial, if you want to access all grandchilds and so own, you'd have to create a nice adapter class, that connects all children of children ranges together.
I thought of this, too, but then, there is a simpler emulation using the property that an N-ary ordered tree has nodes with either no child or exactly N childeren. This menas that we can number the nodes of a complete tree by (if N=3)
level 0: 0 level 1: 1 2 3 level 2: 4 5 6 7 8 9 10 11 12
and so on. Very simple calculations then give the id numbers of all children of a given parent, or the parent of a given child, and so on. If the tree is not complete, some of the groups are missing, but the same ordering can still be applied.
Putting this in a pair<size_t id, Node data>, we can store it in a map, not a multimap, and we have automagically iterators which parse the tree in levels.
The concept is quite simple, but usefull, at least if you want to parse efficiently horizontally.
If you want to parse up-down, it requires an O(log n) lookup in the map, and then you probably want to implement this thing in a pointer-to-children and pointer-to parent fashion for efficiency.
But this get us back to the original question:
2) An N-ary ordered tree is such a basic concept that it is funny that neither STL or Boost offers it. Would it be welcome by the Boost community if it get proposed and included into the Boost libs ???
cheers, Marc Cromme
On Mon, 2 Sep 2002, Marc Cromme wrote: yg-boo> yg-boo> But this get us back to the original question: yg-boo> yg-boo> 2) An N-ary ordered tree is such a basic concept that it is funny yg-boo> that neither STL or Boost offers it. Would it be welcome by the yg-boo> Boost community if it get proposed and yg-boo> included into the Boost libs ??? yg-boo> I for one would like to see trees in boost. There's several variations that would be nice both ordered and unordered N-ary, where N is fixed at compile time, and the same for every node N-ary, where each node can have a different run-time specified number of children Also, I'd like the tree interface to jive with the graph interface. There's a couple files in the graph library that are the start of a basic interface for trees: boost/graph/graph_as_tree.hpp This file adapts any BGL graph to have a tree interface, that is, have a children() and a parent() function. boost/graph/tree_traits.hpp A basic traits class for accessing the node descriptor type and the children iterator type. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
On Tue, 03 Sep 2002 04:54:19 +0200, Jeremy Siek wrote:
I for one would like to see trees in boost. There's several variations that would be nice
both ordered and unordered N-ary, where N is fixed at compile time, and the same for every node N-ary, where each node can have a different run-time specified number of children
I think the most useful is a rooted ordered compile-time fixed N-ary tree to start with: ordering is no great hassle and can just be neglected when you do not need it. The notion of a run-time node dependent n-ary tree is in praxis the same as a tree with nodes of arbitrary children count. How often do we really need this ?? Can we lay this out linear in memory space?? Or do we need nodes containing std::vectors of pointers to children nodes ?? Sounds ugly to me ...
Also, I'd like the tree interface to jive with the graph interface. There's a couple files in the graph library that are the start of a basic interface for trees:
boost/graph/graph_as_tree.hpp
boost/graph/tree_traits.hpp
Thanks for the tip - I take a look at it. Cheers, Marc Cromme, ph.d.
Hi Marc, Currently you're thinking about detailed implementation issues and particular data-structures. However, my comments were not directed towards these details, but instead towards what kind of *concepts* we will need to have for a complete framework of tree data structures and algorithms. Of course, you may only be interested in a particular kind of tree and tree implementation, which is fine, but it would be nice if that fit into a broader framework which could at a later time include other kinds of trees and tree implementations. On Tue, 3 Sep 2002, Marc Cromme wrote: yg-boo> On Tue, 03 Sep 2002 04:54:19 +0200, Jeremy Siek wrote: yg-boo> yg-boo> > I for one would like to see trees in boost. There's several variations yg-boo> > that would be nice yg-boo> > yg-boo> > both ordered and unordered yg-boo> > N-ary, where N is fixed at compile time, and the same for every node yg-boo> > N-ary, where each node can have a different run-time specified yg-boo> > number of children yg-boo> yg-boo> I think the most useful is a rooted ordered compile-time fixed yg-boo> N-ary tree to start with: ordering is no great hassle and can just yg-boo> be neglected when you do not need it. yg-boo> yg-boo> The notion of a run-time node dependent n-ary tree is in praxis yg-boo> the same as a tree with nodes of arbitrary children count. How yg-boo> often do we really need this ?? Can we lay this out linear in yg-boo> memory space?? Or do we need nodes containing std::vectors of yg-boo> pointers to children nodes ?? Sounds ugly to me ... There are lots of uses for this. How about representing XML? How about representing the results of a breadth-first search of a graph. I could go on and on... True, you (or whoever implements this kind of tree) won't be able to use some of the fun tricks for reducing memory consumption, but they are still important. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
On Tue, 03 Sep 2002 23:06:38 +0200, Jeremy Siek wrote:
Hi Marc,
Currently you're thinking about detailed implementation issues and particular data-structures. However, my comments were not directed towards these details, but instead towards what kind of *concepts* we will need to have for a complete framework of tree data structures and algorithms. .... There are lots of uses for this. How about representing XML? How about representing the results of a breadth-first search of a graph.
I see your point. Of course, you are right, I had my own problem in mind when looking for a tree template. Unfortunately I have nor the time to develop such a general framework, nor the in-depth experience in generic STL-like template programming, nor the in-depth knowledge of the boost graph library to succed on my own. But I am still interested in learning more about the boost graph lib, extending it with nice tree templates, and I certainly prefer general solutions as much as you do. Would you be interested in participating in such a project ??? Would anybody else ??? Then we can roll ... Cheers, Marc Cromme
On Wed, 4 Sep 2002, Marc Cromme wrote: yg-boo> I see your point. Of course, you are right, I had my own problem in yg-boo> mind when looking for a tree template. Unfortunately I have nor the yg-boo> time to develop such a general framework, nor the in-depth yg-boo> experience in generic STL-like template programming, nor the in-depth yg-boo> knowledge of the boost graph library to succed on my own. No problemo. yg-boo> But I am still interested in learning more about the boost graph lib, yg-boo> extending it with nice tree templates, and I certainly prefer general yg-boo> solutions as much as you do. yg-boo> yg-boo> Would you be interested in participating in such a project ??? yg-boo> Would anybody else ??? Yes, certainly. Basically, here's what I envision could happen. You write up the interface for the particular tree data-structure that you are interested in. I'll then review that interface and suggest changes so that it can fit into the "big picture"... I'm not sure exactly what the "big picture" is yet, but that will firm up as we go along. Once we agree to the interface, you can implement the tree data-structure that you're interested in. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
On Wed, 04 Sep 2002 18:09:40 +0200, Jeremy Siek wrote:
Basically, here's what I envision could happen. You write up the interface for the particular tree data-structure that you are interested in. I'll then review that interface and suggest changes so that it can fit into the "big picture"... I'm not sure exactly what the "big picture" is yet, but that will firm up as we go along. Once we agree to the interface, you can implement the tree data-structure that you're interested in.
Deal - takes a couple of days I recon. Some practical issues though: certainly it is a faux pas sending a whole header on the boost user group. But where to put it - shall I just mail it to you personally, or is there a place to upload ?? Also, isn't it getting out of scope of the boost user group by now ?? Marc
On Wed, 4 Sep 2002, Marc Cromme wrote:
Some practical issues though: certainly it is a faux pas sending a whole header on the boost user group. But where to put it - shall I just mail it to you personally, or is there a place to upload ??
We should use the boost-sandbox sourceforge CVS repository for this. Send me your sourceforge name and I will give you CVS permissions.
Also, isn't it getting out of scope of the boost user group by now ??
Yep, this discussion should migrate to the main boost mailing list. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://www.osl.iu.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
I would also find an n-ary tree very useful. There is one in glib that is available for public use. http://developer.gnome.org/doc/API/glib/glib-n-ary-trees.html However, this one has the usual glib restrictions. They are necessary enough that I have an application that I know will require one. I will have to sit down and write it myself, since I haven't found one I could use for free or buy without buying a large expensive package. Nathan Janken
On Wed, 04 Sep 2002 01:46:25 +0200, eldritchshadows wrote:
I would also find an n-ary tree very useful. There is one in glib that is available for public use. http://developer.gnome.org/doc/API/glib/glib-n-ary-trees.html
However, this one has the usual glib restrictions. They are necessary enough that I have an application that I know will require one. I will have to sit down and write it myself, since I haven't found one I could use for free or buy without buying a large expensive package.
Nathan Janken
Thanks for the tip - I took a short look at it, but I think the boost user group (and I personally) are better off writing our own. If you like, Nathan, you are welcome to participate, or just to look over our shoulders, commenting, if you please more to do so. Hope it will be useful for you too .... cheers, Marc
--- In Boost-Users@y..., Marc Cromme <yg-boost-users@m...> wrote:
On Wed, 04 Sep 2002 01:46:25 +0200, eldritchshadows wrote:
I would also find an n-ary tree very useful. There is one in glib that is available for public use. http://developer.gnome.org/doc/API/glib/glib-n-ary-trees.html
However, this one has the usual glib restrictions. They are necessary enough that I have an application that I know will require one. I will have to sit down and write it myself, since I haven't found one I could use for free or buy without buying a large expensive package.
Nathan Janken
Thanks for the tip - I took a short look at it, but I think the boost user group (and I personally) are better off writing our own.
If you like, Nathan, you are welcome to participate, or just to look over our shoulders, commenting, if you please more to do so.
Hope it will be useful for you too ....
cheers, Marc
I would love to look over your shoulders if I could. Nathan Janken
participants (4)
-
eldritchshadows -
Jeremy Siek -
Marc Cromme -
Matthias Kronenberger