Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk