src/tree_phylo.c

   1 /* tree_phylo.c    2012-04-30 */
   2
   3 /* Copyright 2008-2012 Emmanuel Paradis */
   4
   5 /* This file is part of the R-package `ape'. */
   6 /* See the file ../COPYING for licensing issues. */
   7
   8 #include "me.h"
   9
  10 static int curnod, curtip, iedge;
  11
  12 #define DO_EDGE\
  13         el[iedge] = EDGE->distance;\
  14         if (leaf(EDGE->head)) {\
  15                 edge2[iedge] = curtip;\
  16                 ilab[curtip - 1] = EDGE->head->label;\
  17                 iedge++;\
  18                 curtip++;\
  19         } else {\
  20                 edge2[iedge] = curnod;\
  21                 iedge++;\
  22                 subtree2phylo(EDGE->head, edge1, edge2, el, ilab);\
  23         }
  24
  25 int leaf(node *v)
  26 {
  27         int count = 0;
  28         if (NULL != v->parentEdge) count++;
  29         if (NULL != v->leftEdge) count++;
  30         if (NULL != v->rightEdge) count++;
  31         if (NULL != v->middleEdge) count++;
  32         if (count > 1) return(0);
  33         return(1);
  34 }
  35
  36 void subtree2phylo(node *parent, int *edge1, int *edge2, double *el, int *ilab)
  37 {
  38         edge *EDGE; int localnode;
  39
  40         EDGE = parent->leftEdge;
  41 /* 'localnode' keeps a copy of the node ancestor # between
  42    the two (recursive) calls of subtree2phylo */
  43         localnode = edge1[iedge] = curnod;
  44         curnod++;
  45         DO_EDGE
  46
  47         EDGE = parent->rightEdge;
  48         edge1[iedge] = localnode;
  49         DO_EDGE
  50 }
  51
  52 /*
  53 transforms a 'tree' struc of pointers into an object of class "phylo"
  54 assumes the tree is unrooted and binary, so there are 2n - 3 edges
  55 assumes labels are int
  56 */
  57 void tree2phylo(tree *T, int *edge1, int *edge2, double *el, int *ilab, int n)
  58 {
  59         edge *EDGE;
  60         curnod = n + 1; /* the root for ape */
  61
  62 /* there's in fact only one edge from the "root" which is
  63    a tip in ape's terminology (i.e., a node of degree 1) */
  64
  65         EDGE = T->root->leftEdge;
  66         edge1[0] = curnod;
  67         edge2[0] = 1; /* <- the 1st tip */
  68         ilab[0] = T->root->label;
  69         el[0] = EDGE->distance;
  70         /* now can initialize these two: */
  71         curtip = 2; /* <- the 2nd tip */
  72         iedge = 1; /* <- the 2nd edge */
  73         edge1[iedge] = curnod;
  74
  75 /* 'T->root->leftEdge->head' is the root for ape,
  76    so don't need to test if it's a leaf */
  77
  78         subtree2phylo(EDGE->head, edge1, edge2, el, ilab);
  79 }