[R] Implementing trees in R

[Bálint Czúcz]

Dear Kevin,

for an example how this idea is implemented in a working package, have
a look at the help page of BinaryTree class in package party. The
@tree node of such an object is a recursive list of this kind.

HTH,
Bálint


On 3/16/07, Gabor Grothendieck <ggrothendieck at gmail.com> wrote:
> 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.
> > >
> >
>
> ______________________________________________
> 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.
>