Re: [boost] proposal for tree container

Subject: Re: [boost] proposal for tree container
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-07-16 08:06:01

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