Re: [boost] Generic Trees

From: Topher Cooper (topher_at_[hidden])
Date: 2006-07-18 19:19:42

At 05:02 PM 7/18/2006, Bernhard Reiter  wrote:
>much thought yet. As people point out in the other thread, isn't
>multiple parent nodes something you'd rather want a graph library (like
>the BGL) for? If not, I'd be glad if you could give me an idea about the
>cases that might be interesting for trees...

It is certainly true that "trees" that have nodes with multiple 
parents are not trees.  They are, however, tree-like, and are 
frequently used as an extension to algorithms that use trees.  They 
are quite a bit more specialized than a general graph.

A tree-like data structure in which some nodes have more than one 
parent is a "singly-rooted directed acyclic graph".  Generally people 
just refer to them as directed acyclic graphs or DAGs.

If you have a simple inheritance hierarchy, such as for types, 
classes or to represent a thesaurus then you can use a tree assuming 
that there is one root concept from which everything else inherits 
(if not, you can always add one), and that every entity (except the 
root) inherits from only one other.  If you allow multiple 
inheritance, however, or allow terms to belong to more than one 
category, then you use a DAG.

If you parse a language you can represent the results as a tree 
(parse tree or abstract syntax tree).  In many cases, though, it is 
handy to identify common sub-expressions only a single instance for 
each such common sub-expression, then one way of handling this is to 
convert the tree into a DAG by merging nodes.

A file hierarchy with links may be considered a DAG.

There is certainly a lot of utility to having a tree package actually 
be able to represent and work with DAGs, but some things do get 
harder.  Obviously, you can no longer refer to THE parent of a 
node.  Shubert numbering can be used to identify whether one node is 
a descendent of another in constant time in a tree, but the extension 
of this to DAGs is complicated.

Its a question of whether the extra utility makes the extra 
complexity worth-while.

Topher