File: reorderRobust.c

package info (click to toggle)
r-cran-phylobase 0.8.6-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 1,308 kB
  • sloc: cpp: 306; ansic: 247; xml: 135; lisp: 38; sh: 9; makefile: 5
file content (62 lines) | stat: -rw-r--r-- 1,585 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
  reorderRobust.c:
    Given a root node, reorder a tree either as postorder or preorder.
  Works on any valid tree, including those with singleton nodes and/or
  polytomies. Function inputs are derived from a phylo4 edge matrix. The
  new descendant node ordering is stored in descendantNew.
*/

#include <R.h>

typedef struct {
    int *descendantNew;
    int *ancestor;
    int *descendant;
    int nEdges;
    int index;
    } tree;

void postorderRobust(tree*, int node);
void preorderRobust(tree*, int node);

void reorderRobust(int *descendantNew, int *root, int *ancestor,
    int *descendant, int *nEdges, int *order) {

    tree tr;
    tr.ancestor = ancestor;
    tr.descendant = descendant;
    tr.descendantNew = descendantNew;
    tr.nEdges = *nEdges;
    tr.index = 0;

    if (*order==0) {
        postorderRobust(&tr, *root);
    } else if (*order==1) {
        preorderRobust(&tr, *root);
    } else {
        error("invalid order type");
    }

}

// postorder: continue traversing to the end, then record node
void postorderRobust(tree *tr, int node) {
    for (int i=0; i<tr->nEdges; i++) {
        if (tr->ancestor[i]==node) {
            postorderRobust(tr, tr->descendant[i]);
        }
    }
    tr->descendantNew[tr->index] = node;
    tr->index += 1;
}

// preorder: record node before continuing traversal
void preorderRobust(tree *tr, int node) {
    tr->descendantNew[tr->index] = node;
    tr->index += 1;
    for (int i=0; i<tr->nEdges; i++) {
        if (tr->ancestor[i]==node) {
            preorderRobust(tr, tr->descendant[i]);
        }
    }
}