Re: [boost] Generic Trees

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2006-07-18 20:55:31

On Wed, 19 Jul 2006 02:06:09 +0300, Yuval Ronen
<ronen_yuval_at_[hidden]> wrote:

>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.

The usual terminology uncertainty which should have no place in
mathematics. We have come to a point where even telling "the real
number x is positive" is ambiguous, as someone intends it as "x >= 0",
and uses "strictly positive" for "> 0". Yes, some authors distinguish
between "directed trees" and "undirected trees". In my personal
experience that's more common in programming texts than mathematical
ones (where, by the way, you more easily find the graph/digraph
terminology --and, well, in C++ "digraph"... you got the point :-))

>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.

Yes, and there can only be one root.

>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"

"Rooted tree", for some authors. But then others --again, very often
in programming circles/textbooks-- assume "trees" to be rooted, and
eventually call "free trees" those that don't have a root (informally
speaking).

Anyway, "rooted" is conceptually distinct from "directed", though the
choice of a root induces a "natural" direction (all the edges
"pointing away from it").

>, then saying that "P is parent of C 
>iff it is *one* edge away from P" is not true).

I don't see the implication. But we are off-topic now, sorry. You are
welcome to mail me, if you like. In the context of the OP question all
this is irrelevant, as he is clearly looking for a data structure
where a node may have multiple parents, regardless of how we might
call it :-)

--
[ Gennaro Prota, C++ developer for hire ]
[    resume:  available on request      ]