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

use num_traits::Float;

use condensed::CondensedMatrix;
use dendrogram::Dendrogram;
use method;
use {LinkageState, Method};

/// Perform hierarchical clustering using the minimum spanning tree
/// algorithm as described in Müllner's paper.
///
/// In general, one should prefer to use
/// [`linkage`](fn.linkage.html),
/// since it tries to pick the fastest algorithm depending on the method
/// supplied.
pub fn mst<T: Float>(dis: &mut [T], observations: usize) -> Dendrogram<T> {
    let mut state = LinkageState::new();
    let mut steps = Dendrogram::new(observations);
    mst_with(&mut state, dis, observations, &mut steps);
    steps
}

/// Like [`mst`](fn.mst.html), but amortizes allocation.
///
/// See [`linkage_with`](fn.linkage_with.html) for details.
#[inline(never)]
pub fn mst_with<T: Float>(
    state: &mut LinkageState<T>,
    dis: &mut [T],
    observations: usize,
    steps: &mut Dendrogram<T>,
) {
    let dis = CondensedMatrix::new(dis, observations);

    steps.reset(dis.observations());
    if dis.observations() == 0 {
        return;
    }
    state.reset(dis.observations());

    let mut cluster = 0;
    state.active.remove(cluster);

    for _ in 0..dis.observations() - 1 {
        let mut min_obs = state.active
            .iter()
            .next()
            .expect("at least one active observation");
        let mut min_dist = state.min_dists[min_obs];

        for x in state.active.range(..cluster) {
            let slot = &mut state.min_dists[x];
            method::single(dis[[x, cluster]], slot);
            if *slot < min_dist {
                min_obs = x;
                min_dist = *slot;
            }
        }
        for x in state.active.range(cluster..) {
            let slot = &mut state.min_dists[x];
            method::single(dis[[cluster, x]], slot);
            if *slot < min_dist {
                min_obs = x;
                min_dist = *slot;
            }
        }
        state.merge(steps, min_obs, cluster, min_dist);
        cluster = min_obs;
    }
    state.set.relabel(steps, Method::Single);
}

#[cfg(test)]
mod tests {
    use {Method, generic, primitive};
    use test::DistinctMatrix;
    use super::mst;

    quickcheck! {
        fn prop_mst_primitive(mat: DistinctMatrix) -> bool {
            let dend_prim = primitive(
                &mut mat.matrix(), mat.len(), Method::Single);
            let dend_mst = mst(
                &mut mat.matrix(), mat.len());
            dend_prim == dend_mst
        }

        fn prop_mst_generic(mat: DistinctMatrix) -> bool {
            let dend_generic = generic(
                &mut mat.matrix(), mat.len(), Method::Single);
            let dend_mst = mst(
                &mut mat.matrix(), mat.len());
            dend_generic == dend_mst
        }
    }
}