1 /* reorder_phylo.c 2012-08-17 */
3 /* Copyright 2008-2012 Emmanuel Paradis */
5 /* This file is part of the R-package `ape'. */
6 /* See the file ../COPYING for licensing issues. */
12 void foo_reorder(int node, int n, int m, int *e1, int *e2, int *neworder, int *L, int *pos)
14 int i = node - n - 1, j, k;
16 /* 'i' is the C index corresponding to 'node' */
18 for (j = 0; j < pos[i]; j++) {
20 neworder[iii++] = k + 1;
21 if (e2[k] > n) /* is it an internal edge? */
22 foo_reorder(e2[k], n, m, e1, e2, neworder, L, pos);
26 void neworder_cladewise(int *n, int *e1, int *e2, int *N, int *neworder)
31 int i, j, k, *L, *pos, m = *N - *n + 1, degrmax = *n - m + 1;
33 /* degrmax is the largest value that a node degree can be */
35 /* L is a 1-d array storing, for each node, the C indices of the rows of
36 the edge matrix where the node is ancestor (i.e., present in the 1st
37 column). It is used in the same way than a matrix (which is actually
38 a vector) is used in R as a 2-d structure. */
40 L = (int*)R_alloc(m * degrmax, sizeof(int));
42 /* pos gives the position for each 'row' of L, that is the number of elements
43 which have already been stored for that 'row'. */
45 pos = (int*)R_alloc(m, sizeof(int));
46 memset(pos, 0, m * sizeof(int));
48 /* we now go down along the edge matrix */
50 for (i = 0; i < *N; i++) {
51 k = e1[i] - *n - 1; /* k is the 'row' index in L corresponding to node e1[i] */
52 j = pos[k]; /* the current 'column' position corresping to k */
53 pos[k]++; /* increment in case the same node is found in another row of the edge matrix */
57 /* L is now ready: we can start the recursive calls. */
58 /* We start with the root 'n + 1': its index will be changed into
59 the corresponding C index inside the recursive function. */
62 foo_reorder(*n + 1, *n, m, e1, e2, neworder, L, pos);
66 #define DO_NODE_PRUNING\
67 /* go back down in `edge' to set `neworder' */\
68 for (j = 0; j <= i; j++) {\
69 /* if find the edge where `node' is */\
70 /* the descendant, make as ready */\
71 if (edge2[j] == node) ready[j] = 1;\
72 if (edge1[j] != node) continue;\
73 neworder[nextI] = j + 1;\
74 ready[j] = 0; /* mark the edge as done */\
78 void neworder_pruningwise(int *ntip, int *nnode, int *edge1,
79 int *edge2, int *nedge, int *neworder)
81 int *ready, *Ndegr, i, j, node, nextI, n;
83 nextI = *ntip + *nnode;
84 Ndegr = (int*)R_alloc(nextI, sizeof(int));
85 memset(Ndegr, 0, nextI*sizeof(int));
86 for (i = 0; i < *nedge; i++) (Ndegr[edge1[i] - 1])++;
88 ready = (int*)R_alloc(*nedge, sizeof(int));
90 /* `ready' indicates whether an edge is ready to be */
91 /* collected; only the terminal edges are initially ready */
92 for (i = 0; i < *nedge; i++)
93 ready[i] = (edge2[i] <= *ntip) ? 1 : 0;
95 /* `n' counts the number of times a node has been seen. */
96 /* This algo will work if the tree is in cladewise order, */
97 /* so that the nodes of "cherries" will be contiguous in `edge'. */
100 while (nextI < *nedge - Ndegr[*ntip]) {
101 for (i = 0; i < *nedge; i++) {
102 if (!ready[i]) continue;
104 /* if found an edge ready, initialize `node' and start counting */
107 } else { /* else counting has already started */
108 if (edge1[i] == node) n++;
110 /* if the node has changed we checked that all edges */
111 /* from `node' have been found */
112 if (n == Ndegr[node - 1]) {
115 /* in all cases reset `n' and `node' and carry on */
119 } /* go to the next edge */
120 /* if at the end of `edge', check that we can't do a node */
121 if (n == Ndegr[node - 1]) {
127 for (i = 0; i < *nedge; i++) {
128 if (!ready[i]) continue;
129 neworder[nextI] = i + 1;