mutex-watersheds 0.1.1

Mutex Watershed based off the original C++ implementation by Steffen Wolf and Constantin Pape.
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

extern crate disjoint_sets;

pub mod mutex;

#[cfg(test)]
mod tests {

    extern crate pretty_env_logger;


    use std::collections::HashMap;
    use disjoint_sets::UnionFind;
    use pretty_env_logger as _log;

    #[test]
    fn mutex_ws() {
        let _ = _log::try_init();
        let uf = super::mutex::compute_mutex_watershed_clustering(
            3,
            &vec![
                (0, 1, 1.0, false),
                (1, 2, 2.0, false),
                (0, 2, 1.9, true),
            ][..]
        );
        assert_ne!(uf.find(0), uf.find(1));
        assert_ne!(uf.find(0), uf.find(2));
        assert_eq!(uf.find(1), uf.find(2));
    }

    const EDGES_BASE: [(u32, u32, f64, bool); 7] = [
        (0, 1, 1.0, false),
        (1, 2, 1.0, false),
        (2, 3, 1.0, false),
        (4, 5, 1.0, false),
        (5, 6, 1.0, false),
        (6, 7, 1.0, false),
        (6, 8, 1.0, false)
        // add this edge to make single cluste:
        // (3, 4, 1.1, false),
        // add this edge to make two clusters instead of one:
        // (3, 4, 1.1, true),
    ];

    #[test]
    fn mutex_ws_variable_edge() {
        let _ = _log::try_init();
        mutex_ws_for_edges(
            &EDGES_BASE,
            &[vec![0, 1, 2, 3], vec![4, 5, 6, 7, 8]]);

        let mut edges_without_mutex = EDGES_BASE.to_vec();
        edges_without_mutex.push((3, 4, 1.1, false));
        mutex_ws_for_edges(
            &edges_without_mutex[..],
            &[vec![0, 1, 2, 3, 4, 5, 6, 7, 8]]);

        let mut edges_with_mutex = EDGES_BASE.to_vec();
        edges_with_mutex.push((3, 4, 1.1, true));
        mutex_ws_for_edges(
            &edges_with_mutex[..],
            &[vec![0, 1, 2, 3], vec![4, 5, 6, 7, 8]]);

        // add edge between 3 and 5, to try to get around mutex edge

        let mut edges_without_mutex = EDGES_BASE.to_vec();
        edges_without_mutex.push((3, 5, 0.9, false));
        mutex_ws_for_edges(
            &edges_without_mutex[..],
            &[vec![0, 1, 2, 3, 4, 5, 6, 7, 8]]);

        let mut edges_with_mutex = EDGES_BASE.to_vec();
        edges_with_mutex.push((3, 4, 1.1, true));
        // value for 3-5 has to be smaller than all values within true cluters;
        // otherwise, it is not guaranteed that clusters are sufficiently populated
        // for mutex 3-4 to block 3-5
        edges_with_mutex.push((3, 5, 0.9, false));
        mutex_ws_for_edges(
            &edges_with_mutex[..],
            &[vec![0, 1, 2, 3], vec![4, 5, 6, 7, 8]]);
        
    }

    fn mutex_ws_for_edges(
        edges: &[(u32, u32, f64, bool)],
        expected: &[Vec<u32>]
    ) {
        let uf = super::mutex::compute_mutex_watershed_clustering(9, &edges);
        let actual = group_by_smallest_element(&uf);
        assert_eq!(actual, expected);
    }

    fn group_by_smallest_element(uf: &UnionFind<u32>) -> Vec<Vec<u32>> {
        let mut hm: HashMap<u32, Vec<u32>> = HashMap::new();
        for id in 0..uf.len() {
            let id_u32 = id as u32;
            let root = uf.find(id_u32);
            if !hm.contains_key(&root) {
                hm.insert(root, vec![id_u32]);
            } else {
                hm.get_mut(&root).unwrap().push(id_u32);
            }
        }

        let mut clusters: Vec<Vec<u32>> = hm.values().cloned().collect();
        for cluster in clusters.iter_mut() { cluster.sort(); }
        clusters.sort_by(|c1, c2| c1[0].cmp(&c2[0]));

        clusters
    }

    
}