Re: [boost] Generic Trees

From: Yuval Ronen (ronen_yuval_at_[hidden])
Date: 2006-07-18 19:06:09

Gennaro Prota wrote:
> On Tue, 18 Jul 2006 16:42:41 +0100, Paul Giaccone
> <paulg_at_[hidden]> wrote:
> 
>> You're not wrong. A "tree" in which nodes have multiple parents is a 
>> graph; actually, it is (I think) a directed graph.
> 
> Not actually a boost question, but any tree is a graph (in fact "tree
> graph" is another name). Precisely it is a "connected forest" or,
> equivalently, a connected simple undirected acyclic graph.

Why do you assume it's undirected? There are directed trees and 
undirected trees. I guess that the SoC project is about directed trees, 
because they are much more useful as data structures for programming, 
and the lack of them is very well felt. In a directed tree, a node 
indeed cannot have multiple parents. That's the definition of directed 
trees.

> In such a structure, if you say that a node C is child of another node
> P (or equivalently that P is parent of C) iff it is *one* edge away
> from P then a node may well, and obviously, have multiple parents.

Again, this assumes undirected trees (and even then I'm not sure it's 
true, because some might not define an undirected tree as "undirected 
acyclic graph", but instead define it as an "undirected acyclic graph 
with a given node declared as root", then saying that "P is parent of C 
iff it is *one* edge away from P" is not true).