proposal for tree container

[Kasper Peeters]

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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Rutger ter Borg-2]

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




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Gottlob Frege]

On Mon, Jul 6, 2009 at 9:27 AM, Rutger ter Borg<rutger@...> 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?
>
> http://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/
>

There is also adobe::forest

http://stlab.adobe.com/group__asl__tutorials__forest.html
http://stlab.adobe.com/classadobe_1_1forest.html

Tony
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Andrew Sutton-2]

>
> 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@...
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jose-3]

On Mon, Jul 6, 2009 at 4:39 PM, Andrew Sutton<andrew.n.sutton@...> 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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Gottlob Frege]

On Mon, Jul 6, 2009 at 11:58 AM, Jose<jmalv04@...> wrote:

> On Mon, Jul 6, 2009 at 4:39 PM, Andrew Sutton<andrew.n.sutton@...> 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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Ross Levine]

On Thu, Jul 16, 2009 at 12:26 AM, Gottlob Frege <gottlobfrege@...>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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Gottlob Frege]

On Thu, Jul 16, 2009 at 2:18 AM, Ross Levine<ross.levine@...> wrote:
> On Thu, Jul 16, 2009 at 12:26 AM, Gottlob Frege <gottlobfrege@...>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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Arash Partow]

Let me shorten that for you:

"A tree should be an acyclic simple graph."


Quoting Ross Levine <ross.levine@...>:

> 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




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Ross Levine]

On Thu, Jul 16, 2009 at 3:12 AM, Arash Partow <arash@...> 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?
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Thomas Klimpel]

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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Max-156]

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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

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@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Max-156]

Hello Stewart,

Sorry for not making things clearer.

I meant this lib (tree.hh):
http://www.aei.mpg.de/~peekas/tree/

B/Rgds
Max

> -----Original Message-----
> From: boost-bounces@... [mailto:boost-bounces@...]
> On Behalf Of Stewart, Robert
> Sent: Monday, July 27, 2009 8:46 PM
> To: boost@...
> 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@...
> 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.
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost