speedytree 0.1.0

Canonical and RapidNJ implementations of Neighbor-joining in Rust
Documentation 
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

// http://qspace.qu.edu.qa/bitstream/handle/10576/9747/A%20random%20binary%20trees%20generation%20method.pdf?sequence=10

use petgraph::graph::NodeIndex;
use petgraph::prelude::UnGraph;
use rand::Rng;

use crate::distances::DistanceMatrix;
use crate::Tree;

#[allow(dead_code)]
fn random_rooted_binary_tree(leaves: usize) -> UnGraph<String, f64> {
    let mut tree = UnGraph::new_undirected();
    let mut next_node = leaves;
    let mut nodes: Vec<NodeIndex> = (0..leaves).map(|_| tree.add_node("".to_string())).collect();
    while next_node <= 2 * leaves - 2 {
        let mut rng = rand::thread_rng();
        // Pop random node from range
        let a = nodes.swap_remove(rng.gen_range(0..nodes.len()));
        let b = nodes.swap_remove(rng.gen_range(0..nodes.len()));
        let u = tree.add_node("".to_string());
        nodes.push(u);
        tree.add_edge(u, a, rng.gen_range(0.1..100.0));
        tree.add_edge(u, b, rng.gen_range(0.1..100.0));
        next_node += 1;
    }
    for node in tree.node_indices() {
        // If has one edge, it's a leaf
        if tree.edges(node).count() == 1 {
            tree[node] = format!("L{}", node.index());
        }
    }
    tree
}
/// Generate a random unrooted binary tree with n_leaves leaves
/// The tree is generated by first generating a random rooted binary tree
/// and then removing the root and adding an edge between two leaves
#[allow(dead_code)]
pub fn random_unrooted_binary_tree(n_leaves: usize) -> UnGraph<String, f64> {
    let mut t = random_rooted_binary_tree(n_leaves);
    // Remove root as node with degree 2
    let root = t
        .node_indices()
        .find(|node| t.edges(*node).count() == 2)
        .expect("Valid rooted binary tree");
    let mut neighbors = t.neighbors_undirected(root);
    let a = neighbors.next().expect("Enough leaves");
    let b = neighbors.next().expect("Enough leaves");
    t.remove_node(root);
    // Add edge between a and b
    let mut rng = rand::thread_rng();
    t.add_edge(a, b, rng.gen_range(0.1..100.0));
    t
}
/// Generate a DistanceMatrix from a Tree
/// The distance matrix is generated by computing the distance between
/// all pairs of leaves. It uses the astar algorithm from petgraph, so it's not efficient.
/// It's only used for testing purposes.
#[allow(dead_code)]
pub fn distance_matrix_from_tree(t: Tree) -> DistanceMatrix {
    // Find all leaves
    let leaves: Vec<NodeIndex> = t
        .node_indices()
        .filter(|node| t.edges(*node).count() == 1)
        .collect();
    let mut mat = vec![vec![0.0; leaves.len()]; leaves.len()];
    for (i, a) in leaves.iter().enumerate() {
        for (j, b) in leaves.iter().enumerate() {
            mat[i][j] =
                petgraph::algo::astar(&t, *a, |finish| finish == *b, |e| *e.weight(), |_| 0.0)
                    .expect("All nodes are connected")
                    .0;
        }
    }
    DistanceMatrix {
        names: leaves.iter().map(|node| t[*node].clone()).collect(),
        matrix: mat,
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_random_rooted_binary_tree() {
        for _ in 0..50 {
            let mut rng = rand::thread_rng();
            let n_leaves = rng.gen_range(5..30);
            let tree = random_rooted_binary_tree(n_leaves);
            // Count number of non "" nodes
            let mut n = 0;
            for node in tree.node_indices() {
                if !tree[node].is_empty() {
                    n += 1;
                }
            }
            assert_eq!(n, n_leaves);
            assert_eq!(tree.node_count(), 2 * n_leaves - 1);
        }
    }
    #[test]
    fn test_random_unrooted_binary_tree() {
        for _ in 0..50 {
            let mut rng = rand::thread_rng();
            let n_leaves = rng.gen_range(5..30);
            let tree = random_unrooted_binary_tree(n_leaves);
            // Count number of non "" nodes
            let mut n = 0;
            for node in tree.node_indices() {
                if !tree[node].is_empty() {
                    n += 1;
                }
            }
            assert_eq!(n, n_leaves);
            assert_eq!(tree.node_count(), 2 * n_leaves - 2);
            // Assert any leave has degree 1 and any other node has degree 3
            for node in tree.node_indices() {
                if !tree[node].is_empty() {
                    assert_eq!(tree.edges(node).count(), 1);
                } else {
                    assert_eq!(tree.edges(node).count(), 3);
                }
            }
        }
    }
}