On Wed, 19 Jul 2006 02:06:09 +0300, Yuval Ronen <ronen_yuval@yahoo.com> wrote:
Gennaro Prota wrote:
On Tue, 18 Jul 2006 16:42:41 +0100, Paul Giaccone <paulg@cinesite.co.uk> 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 ]