snarl 0.0.1

Compute a planar layout for a weighted graph.
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

use std::cmp::{max, min};
use std::vec::Vec;

/// Implement union-find for elements with indices [0, ..., N-1].
pub struct UnionFind {
    /// Whether the merging phase has been completed.
    is_finalized: bool,

    /// The number of distinct components.
    components: i32,

    /// The index of the representative element of the component of each element.
    ///
    /// A value of -1 indicates the element is the representative of a component.
    /// Otherwise, the representative index is always larger than the element index.
    representatives: Vec<i32>,
}

impl UnionFind {
    /// Create new union-find data where initially each element is a separate component.
    pub fn new(size: i32) -> UnionFind {
        assert!(size > 0);
        UnionFind {
            is_finalized: false,
            components: size,
            representatives: vec![-1; size as usize],
        }
    }

    /// Return the index of the current representative of the component the element belong to.
    ///
    /// This mutates the data, as it needs to modify the representatives to short-cut further
    /// lookups.
    pub fn representative(&mut self, mut element: i32) -> i32 {
        assert!(element >= 0);
        let first = element;
        let mut next = self.representatives[element as usize];
        while next >= 0 {
            assert!(next > element);
            element = next;
            next = self.representatives[element as usize];
        }
        if element != first {
            self.representatives[first as usize] = element;
        }
        element
    }

    /// Merge the two distinct components the left and right elements belong to.
    pub fn merge(&mut self, left: i32, right: i32) {
        assert!(!self.is_finalized);

        let left_representative = self.representative(left);
        let right_representative = self.representative(right);
        assert!(left_representative != right_representative);

        let low = min(left_representative, right_representative);
        let high = max(left_representative, right_representative);
        self.representatives[low as usize] = high;
        self.components -= 1;

        if left != high {
            self.representatives[left as usize] = high;
        }
        if right != high {
            self.representatives[right as usize] = high;
        }
    }

    /// The current number of distinct components.
    pub fn components(&self) -> i32 {
        self.components
    }

    /// Collect the final root representatives of the components.
    ///
    /// This must be called once, after all merging were done.
    /// Once it was called, it is no longer possible to perform any more merged.
    pub fn finalize(&mut self) {
        assert!(!self.is_finalized);
        let mut component: i32 = 0;
        for representative in self.representatives.iter_mut() {
            if *representative < 0 {
                *representative = -1 - component as i32;
                component += 1;
            }
        }
        self.is_finalized = true;
    }

    /// Return the index of the component the element belongs to.
    ///
    /// Component indices are [0, ..., M-1] for some small M, as opposed to representatives
    /// This may only be invoked after `finalize` has been called.
    pub fn component(&mut self, element: i32) -> i32 {
        let representative = self.representative(element);
        -1 - self.representatives[representative as usize]
    }
}