Hi all, On a regular basis, users of my 'tree.hh' library ask me whether I would be interested in submitting it to boost. As you may have guessed from the name, tree.hh is a templated n-ary tree container class in the spirit of the STL, but of course deviating from it in the sense of offering various ways of iterating over the tree. More info at http://www.aei.mpg.de/~peekas/tree/ Back in 2002 I tried to estimate the interest for inclusion in boost, see http://lists.boost.org/Archives/boost/2002/10/37383.php The most serious criticism back then was the 'lack of abstraction' (for more details please consult the original thread), and I didn't have the time to address that. Given the continuing interest by users of tree.hh to propose it for inclusion in boost, I would like to give this another shot and see what's the current opinion. While I would be happy to clean up the code, I do not have the time to do a substantial rewrite (along the lines suggested in 2002), but would be interested to help someone else do that. License-wise, tree.hh is now available under GPL-2 or 3, but all of the above of course implies that I'd be willing to re-license. Cheers, Kasper
Kasper Peeters wrote: [snip]
Given the continuing interest by users of tree.hh to propose it for inclusion in boost, [snip]
I would welcome a tree-like container in Boost. Are you aware of Bernhard Reiter's work? http://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/ Kind regards, Rutger ter Borg
On Mon, Jul 6, 2009 at 9:27 AM, Rutger ter Borg<rutger@terborg.net> wrote:
Kasper Peeters wrote:
[snip]
Given the continuing interest by users of tree.hh to propose it for inclusion in boost, [snip]
I would welcome a tree-like container in Boost. Are you aware of Bernhard Reiter's work?
There is also adobe::forest http://stlab.adobe.com/group__asl__tutorials__forest.html http://stlab.adobe.com/classadobe_1_1forest.html Tony
On a regular basis, users of my 'tree.hh' library ask me whether I would be interested in submitting it to boost. As you may have guessed from the name, tree.hh is a templated n-ary tree container class in the spirit of the STL, but of course deviating from it in the sense of offering various ways of iterating over the tree. More info at
http://www.aei.mpg.de/~peekas/tree/<http://www.aei.mpg.de/%7Epeekas/tree/>
Back in 2002 I tried to estimate the interest for inclusion in boost, see
http://lists.boost.org/Archives/boost/2002/10/37383.php
The most serious criticism back then was the 'lack of abstraction' (for more details please consult the original thread), and I didn't have the time to address that.
I've actually looked at your implementation several times over the last... I don't know... 5 years? and wondered if it would ever become part of a larger library. I certainly seems like a viable addition to Boost. If you're referring to comments about a generic tree abstractions (i.e., tree concepts), then I have to admit that I am farly disappointed in results of the previous discussion. Obviously, you aren't suggesting the implementation of a generic tree library (a la BGL), just one particular implementation. The development of concepts (in the SGI/BGL/C++0x sense) is best done if you have a collection of generic tree algorihms, which would allow you to classify generic trees, and abstract their commonalities. So while we all know that there are tons of kinds of trees (red-black, avl, binary, n-ary, multiway, b-trees, b+-trees, treaps, splay trees, tries, suffix trees, radix trees, etc., etc., ad nauseum) we don't really have a list of generic tree algorithms, nor do we have a lot of tree data structures to throw at them. If there is going to be a discussion about adding tree.hh to Boost, then I would hope that the discussion focuses on your implementation as a standalone data structure, and not as a complete generic library. Comparisons of tree.hh to the STL or BGL seem inappropriate to me. Given the continuing interest by users of tree.hh to propose it for
inclusion in boost, I would like to give this another shot and see what's the current opinion. While I would be happy to clean up the code, I do not have the time to do a substantial rewrite (along the lines suggested in 2002), but would be interested to help someone else do that.
Along these lines, I think it might be a good idea to put tree.hh in the sandbox along with Reiter's 2006 work and see how things develop from there. Comparisons with Adobe's forest class are also interesting. Andrew Sutton andrew.n.sutton@gmail.com
On Mon, Jul 6, 2009 at 4:39 PM, Andrew Sutton<andrew.n.sutton@gmail.com> wrote:
If there is going to be a discussion about adding tree.hh to Boost, then I would hope that the discussion focuses on your implementation as a standalone data structure, and not as a complete generic library. Comparisons of tree.hh to the STL or BGL seem inappropriate to me.
Yes, I think this is what the author means. I think in the old thread 2002 someone misunderstood the library and compared with BGL, which probably confused many. It is not for graphs but storing and querying tree-like data. One of the many apps where this data structure is useful is as a way to store parse results that can later be queried (e.g. DOM tree) http://en.wikipedia.org/wiki/K-ary_tree His implementation of a n-ary tree data structure has been used by a few apps already and there would be a mutual benefit if it becomes part of boost
On Mon, Jul 6, 2009 at 11:58 AM, Jose<jmalv04@gmail.com> wrote:
On Mon, Jul 6, 2009 at 4:39 PM, Andrew Sutton<andrew.n.sutton@gmail.com> wrote:
If there is going to be a discussion about adding tree.hh to Boost, then I would hope that the discussion focuses on your implementation as a standalone data structure, and not as a complete generic library. Comparisons of tree.hh to the STL or BGL seem inappropriate to me.
Yes, I think this is what the author means. I think in the old thread 2002 someone misunderstood the library and compared with BGL, which probably confused many. It is not for graphs but storing and querying tree-like data. One of the many apps where this data structure is useful is as a way to store parse results that can later be queried (e.g. DOM tree) http://en.wikipedia.org/wiki/K-ary_tree
His implementation of a n-ary tree data structure has been used by a few apps already and there would be a mutual benefit if it becomes part of boost
I think the only question is whether it is 'generic enough' to be widely useful. Obviously it isn't BGL. I think of BGL (although I know little of it) of things (algorithms) to do with trees (and other graphs) *once you have one*, not a tree in itself. So is it a 'good enough' tree for most uses? (Seems to be useful enough for some people already.) Can it (should it?) be made a bit more generic for more uses? And/or, should it be more specifically named (k_ary_tree or whatever), to separate it from red_black_tree, splay_tree,... etc? What are the requirements of 'tree-ness'? Containers like std::map/list/deque/vector/... all have well defined requirements. Tony
On Thu, Jul 16, 2009 at 12:26 AM, Gottlob Frege <gottlobfrege@gmail.com>wrote:
What are the requirements of 'tree-ness'? Containers like std::map/list/deque/vector/... all have well defined requirements.
This is one of those questions that seems trivial but is very important to actually lay out. Here's what I can come up with: 1. A tree is a node-based container. If nonempty, every node has exactly one parent, except for one node. This node is called the _root node_. 2. Every node has a finite, non-negative number of children. A node's children is the same as the set of nodes which have that node as a parent. Corollary: There is exactly one simple path between any two different nodes (a simple path is a path that has no repeated vertices). Corollary: A node's parent lies on the path between it and the root node. Definitions: 1. If any node in tree T have at most K children, then T is a _K-ary tree_. 2. A K-ary tree is _full_ if every node has either 0 or K children. 3. The _distance_ between two nodes, A and B, is the number of edges in the path that connects A and B. 4. The _height_ of tree T is equal to the maximum distance from the root node to any other node. 5. The _degree_ of a node is the number of children, plus the number of parents. Since every node (except the root) has exactly one parent, the degree of a non-root node is the number of children plus 1. 6. A node is a _leaf_ node if it has no children. 7. An _ordered tree_ is a tree in which the position of the nodes, and the order of a node's children, is significant. That's all I can think of right now. Someone check my work.
On Thu, Jul 16, 2009 at 2:18 AM, Ross Levine<ross.levine@uky.edu> wrote:
On Thu, Jul 16, 2009 at 12:26 AM, Gottlob Frege <gottlobfrege@gmail.com>wrote:
What are the requirements of 'tree-ness'? Containers like std::map/list/deque/vector/... all have well defined requirements.
This is one of those questions that seems trivial but is very important to actually lay out.
Glad you agree. Many people I work with just like to run ahead and (blindly, in my opinion) type code as fast as they can! <cut/paste>
Someone check my work.
OK! My pure-math proof/theorem/formalism hat popped onto my head, but I'll try not to get too picky.
Here's what I can come up with:
1. A tree is a node-based container. If nonempty, every node has exactly one parent, except for one node. This node is called the _root node_.
node, parent, container, etc undefined. I can live with that. Can't define everything!
2. Every node has a finite, non-negative number of children. A node's children is the same as the set of nodes which have that node as a parent.
In fact, this is the definition of 'child'.
Corollary: There is exactly one simple path between any two different nodes (a simple path is a path that has no repeated vertices).
vertex undefined but I think you meant 'node' :-) simple path undefined this is actually worth defining, somewhat (in my head at least), because, in addition to these requirements, there is nothing stopping a tree from having 'extra' edges (ie linking children together) but obviously these don't form a part of the 'tree-ness' so shouldn't/can't be used as part of a path. (that's just my head trying to imagine how the corrollary could be false, and closing the loop-holes)
Corollary: A node's parent lies on the path between it and the root node.
Definitions: 1. If any node in tree T have at most K children, then T is a _K-ary tree_.
'have at most' at the moment, or 'can have at most' at any time? Maybe it depends on context? (ie T is, at the moment, a K-ary tree...? Or would it better to say, in those case, "T is, at the moment, *like* a K-ary tree, or can be considered a K-ary tree for the purposes of blah blah blah...")
2. A K-ary tree is _full_ if every node has either 0 or K children. 3. The _distance_ between two nodes, A and B, is the number of edges in the path that connects A and B. 4. The _height_ of tree T is equal to the maximum distance from the root node to any other node. 5. The _degree_ of a node is the number of children, plus the number of parents. Since every node (except the root) has exactly one parent, the degree of a non-root node is the number of children plus 1.
what's 'degree' typically used for? is it more for graphs? Seems useless as a concept of its own, separate from 'number of children', at least for trees. (just wondering)
6. A node is a _leaf_ node if it has no children. 7. An _ordered tree_ is a tree in which the position of the nodes, and the order of a node's children, is significant.
That's all I can think of right now. Someone check my work.
excellent stuff. I can't think of any other requirements - anything I could consider adding just makes it a specialization of tree. I guess it might be useful to mention ('corollary') that a tree is thus a type of graph, more specifically a type of DAG. I'm trying to imagine if there are interesting cases between 'tree' and 'DAG' that are worth thinking about... Tony
Gottlob Frege wrote:
excellent stuff. I can't think of any other requirements - anything I could consider adding just makes it a specialization of tree.
I guess it might be useful to mention ('corollary') that a tree is thus a type of graph, more specifically a type of DAG. I'm trying to imagine if there are interesting cases between 'tree' and 'DAG' that are worth thinking about...
The definitions of Ross Levine were actually quite good, considering the many possible ways for faulty definitions. Arash Partow wrote:
Let me shorten that for you: "A tree should be an acyclic simple graph."
I think this is too simplistic, and I will try to explain why (citing shameless from "http://en.wikipedia.org/wiki/Tree_(graph_theory)"). In the context of simple graphs, there exist some tree-related graph-types: - A "tree" is a graph in which any two vertices are connected by exactly one path. - A "forest" is a disjoint union of trees. - A tree is called a "rooted tree" if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science. So if we think that the context of simple graphs is most appropriate to describe tree containers, we should go with the "rooted tree". On the other hand, if we prefer the context of directed graphs, we will start by noticing that a (rooted) tree is a special case of a 'DAG'. Are there any other interesting special cases of 'DAG' that are worth thinking about? Because a 'DAG' seems more like a "forest" than a "rooted tree", defining a 'rooted DAG' in a sensible way might be a good idea. Regards, Thomas
Hello, The tree.hh library should not be the only library that is capable of representing the tree-like data structure and algorithms. But I like its intuitiveness and straight- forwardness. I hope I could make use of it in my program in the furure and also hope boost include such a little library or have it included in any of the existing lib's. B/Rgds Max
Max wrote:
The tree.hh library should not be the only library that is capable of representing the tree-like data structure and algorithms. But I like its intuitiveness and straight- forwardness.
I hope I could make use of it in my program in the furure and also hope boost include such a little library or have it included in any of the existing lib's.
Are you suggesting that you have a tree container to propose or that you want someone else to create one? Either way, you gave insufficient information to understand what you have or want. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Stewart, Robert Sent: Monday, July 27, 2009 8:46 PM To: boost@lists.boost.org Subject: Re: [boost] proposal for tree container
Max wrote:
The tree.hh library should not be the only library that is capable of representing the tree-like data structure and algorithms. But I like its intuitiveness and straight- forwardness.
I hope I could make use of it in my program in the furure and also hope boost include such a little library or have it included in any of the existing lib's.
Are you suggesting that you have a tree container to propose or that you want someone else to create one? Either way, you gave insufficient information to understand what you have or want.
_____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com
IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or
Hello Stewart, Sorry for not making things clearer. I meant this lib (tree.hh): http://www.aei.mpg.de/~peekas/tree/ B/Rgds Max that
this message or any of its attachments is free of viruses. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Let me shorten that for you: "A tree should be an acyclic simple graph." Quoting Ross Levine <ross.levine@uky.edu>:
Here's what I can come up with:
1. A tree is a node-based container. If nonempty, every node has exactly one parent, except for one node. This node is called the _root node_. 2. Every node has a finite, non-negative number of children. A node's children is the same as the set of nodes which have that node as a parent. Corollary: There is exactly one simple path between any two different nodes (a simple path is a path that has no repeated vertices). Corollary: A node's parent lies on the path between it and the root node.
Definitions: 1. If any node in tree T have at most K children, then T is a _K-ary tree_. 2. A K-ary tree is _full_ if every node has either 0 or K children. 3. The _distance_ between two nodes, A and B, is the number of edges in the path that connects A and B. 4. The _height_ of tree T is equal to the maximum distance from the root node to any other node. 5. The _degree_ of a node is the number of children, plus the number of parents. Since every node (except the root) has exactly one parent, the degree of a non-root node is the number of children plus 1. 6. A node is a _leaf_ node if it has no children. 7. An _ordered tree_ is a tree in which the position of the nodes, and the order of a node's children, is significant.
That's all I can think of right now. Someone check my work. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
________________________________________________________ Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net
On Thu, Jul 16, 2009 at 3:12 AM, Arash Partow <arash@partow.net> wrote:
Let me shorten that for you:
"A tree should be an acyclic simple graph."
Haha -- this is true. However, I was trying to look at it from a container-like perspective, not from a graph-like perspective. As already mentioned, the BGL is capable of handling tree structures, but this class is more for a "container with tree relations" sort of things. I tried to stay away from mentioning that it's a planar graph. For example, I would say this class is more suited for menu layouts with submenus: each node is one entry, and non-leaf nodes have submenus. I think BGL would be overkill for this sort of thing and would be more work with which to program. As a side note, does anyone else think it's odd that tree::sort uses sibling iterators? Shouldn't it be templated?
participants (10)
-
Andrew Sutton -
Arash Partow -
Gottlob Frege -
Jose -
Kasper Peeters -
Max -
Ross Levine -
Rutger ter Borg -
Stewart, Robert -
Thomas Klimpel