[R] Implementing trees in R

[Martin Maechler]

>>>>> "Bálint" == Bálint Czúcz <czucz at botanika.hu>
>>>>>     on Wed, 21 Mar 2007 19:54:28 +0100 writes:

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

and the informal (i.e. S3) class  "dendrogram"  in the 'stats'
package, i.e. part of every R, is of that kind as well
{to be used for cluster dendrograms it has attributes for nodes
 and edges, etc}

It features a print(), (too ?!) flexible plot(), a nice str()
method, and more:

 > methods(class = "dendrogram")
 [1] cophenetic.dendrogram* cut.dendrogram*        [[.dendrogram*        
 [4] labels.dendrogram*     plot.dendrogram*       print.dendrogram*     
 [7] reorder.dendrogram*    rev.dendrogram*        str.dendrogram*       

Type 
     example(dendrogram)

to get a first impression.

Martin Maechler, ETH Zurich


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

    Bálint> ______________________________________________
    Bálint> R-help at stat.math.ethz.ch mailing list
    Bálint> https://stat.ethz.ch/mailman/listinfo/r-help
    Bálint> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
    Bálint> and provide commented, minimal, self-contained, reproducible code.