Hi all: Lately I've taken look at the available material re Boost SoC Generic Tree container, and find many parallels in what I am trying to attempt here at work (with seemingly one exception, see query below), and making good headway with a relatively robust and generic design (, though I'd hate to be reinventing the wheel). However, what I could not pick out is whether or not the proposed tree can or intends to support a node owning multiple parents(?) Apologies to all others for the noise, but I wasn't sure where else to post the question. Cheers, -- Manfred Doudar - Research Engineer National ICT Australia - Canberra Research Lab | www.nicta.com.au Research School of Information Sciences and Engineering (RSISE) The Australian National University - Canberra, ACT 0200 AUSTRALIA
loufoque wrote:
Manfred Doudar wrote :
However, what I could not pick out is whether or not the proposed tree can or intends to support a node owning multiple parents(?)
AFAIK when a node has multiple parents it's not a tree, it's a graph. I may be wrong though.
You're not wrong. A "tree" in which nodes have multiple parents is a graph; actually, it is (I think) a directed graph.
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. 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. -- [ Gennaro Prota, C++ developer for hire ] [ resume: available on request ]
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. 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).
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 ]
Gennaro Prota wrote:
On Wed, 19 Jul 2006 02:06:09 +0300, Yuval Ronen <ronen_yuval@yahoo.com> wrote:
Gennaro Prota wrote: 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". Really? No mathematician I have ever met (and I have met very many) would do that. "Strictly positive" is tautologous. "Positive" is defined as "greater than zero", so anyone who uses it differently is mistaken and liable to be misunderstood. If someone means "x >= 0", then the term for that is "non-negative".
On the other hand, the set of natural numbers is defined by some as the set of positive integers and by others as the set of non-negative integers[1], but the term "positive" is well-defined. Sorry for going somewhat off-topic, but as Gennaro suggests, we have to be clear about what our terminology denotes. Paul [1] Weisstein, Eric W. "Natural Number.", MathWorld, http://mathworld.wolfram.com/NaturalNumber.html
Paul Giaccone wrote:
Really? No mathematician I have ever met (and I have met very many) would do that. "Strictly positive" is tautologous. "Positive" is defined as "greater than zero", so anyone who uses it differently is mistaken and liable to be misunderstood. If someone means "x >= 0", then the term for that is "non-negative". There are two different definitions of natural numbers (see http://en.wikipedia.org/wiki/Natural_numbers ) so sometimes one has to qualify what definition he uses: "natural numbers with zero" or "natural numbers without zero" :)
This can sometimes lead to confusion with the meaning of "positive", so terms like "strictly positive" and "non-negative" are used. PS: I'm a mathematician by training. -- With respect, Alex Besogonov (cyberax@elewise.com)
On Wed, 19 Jul 2006 10:05:25 +0100, Paul Giaccone <paulg@cinesite.co.uk> wrote:
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". Really? No mathematician I have ever met (and I have met very many) would do that.
I haven't met Bourbaki guys either ;) And, needless to say, I hate that terminology. -- [ Gennaro Prota, C++ developer for hire ] [ resume: available on request ]
Am Dienstag, den 18.07.2006, 14:52 +1000 schrieb Manfred Doudar:
Hi all:
Lately I've taken look at the available material re Boost SoC Generic Tree container, and find many parallels in what I am trying to attempt here at work (with seemingly one exception, see query below), and making good headway with a relatively robust and generic design (, though I'd hate to be reinventing the wheel).
Hello Manfred, and nice to know about other people's ongoing efforts! (I'm the SoC student in charge of trees).
However, what I could not pick out is whether or not the proposed tree can or intends to support a node owning multiple parents(?)
Well, I'm trying to keep everything as generic (and hopefully extensible) as possible, but I have to admit that I haven't given that 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...
Apologies to all others for the noise, but I wasn't sure where else to post the question.
There's boostsoc2006tree@googlegroups.com, set up by my mentor, René Rivera. I'd be glad about any input and/or share... ;-) Regards, Bernhard
On Tue, 18 Jul 2006 23:02:27 +0200, Bernhard Reiter <ockham@gmx.net> wrote:
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?
Out of curiosity, what definition of "tree" does you library assume? -- [ Gennaro Prota, C++ developer for hire ] [ resume: available on request ]
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
participants (8)
-
Alex Besogonov -
Bernhard Reiter -
Gennaro Prota -
loufoque -
Manfred Doudar -
Paul Giaccone -
Topher Cooper -
Yuval Ronen