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