[R] Implementing trees in R

[Gabor Grothendieck]

Let me rephrase that.  Lists do not support references but they
could be used to represent trees.

list(a = list(a = 1, b = list(2, 3, d = list(4, 5)), c = list(4, 5))

is a tree whose top nodes are a, b, c and b contains three nodes
2, 3 and d and d contains 2 nodes.

However, if you want to do it via references as requested then lists
are not appropriate.

On 3/16/07, Gabor Grothendieck <ggrothendieck at gmail.com> wrote:
> Lists are not good for this.  There is an example in section 3.3 of
> the proto vignette of using proto objects for this.  That section
> also references an S4 example although its pretty messy with S4.
>
> You might want to look at the graph, RBGL and graphviz packages
> in Bioconductor and the dynamicgraph, mathgraph and sna packages
> on CRAN.
>
> On 3/16/07, Yuk Lap Yip (Kevin) <yuklap.yip at yale.edu> wrote:
> > Hi all,
> >
> >    I am rather new to R. Recently I have been trying to implement some
> > tree algorithms in R. I used lists to model tree nodes. I thought
> > something like this would work:
> >
> >    parent <- list();
> >    child <- list();
> >    parent$child1 <- child;
> >    child$parent <- parent;
> >
> >    When I tried to check whether a node is its parent's first child
> > using "if (node$parent$child1 == node)", it always returned false. Then
> > I realized that it does not really work because "parent$child1 <- child"
> > actually makes a copy of child instead of referencing it. I think one
> > possible fix is to keep a list of node objects, and make references
> > using the positions in the list. For example, I think the following
> > would work:
> >
> >    parent <- list();
> >    child <- list();
> >    nodes <- list(parent, child);
> >    parent$child1 <- 2;
> >    child$parent <- 1;
> >
> >    Then the "first child" test can be rewritten as "if
> > (nodes[[nodes[[nodeId]]$parent]]$child1 == nodeId)". However, I would
> > prefer not to implement trees in this way, as it requires the
> > inconvenient and error-prone manipulations of node IDs.
> >
> >    May I know if there is a way to make object references to lists? Or
> > are there other ways to implement tree data structures in R?
> >
> >    BTW, I checked how hclust was implemented, and noticed that it calls
> > an external Fortran program. I would want a solution not involving any
> > external programs.
> >
> >    Thanks.
> >
> > --
> >
> >
> >        God bless.
> >
> >        Kevin
> >
> > ______________________________________________
> > R-help at stat.math.ethz.ch mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> > and provide commented, minimal, self-contained, reproducible code.
> >
>