algos 0.6.8

A collection of algorithms 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

use rand::seq::SliceRandom;
use rand::thread_rng;

pub type Edge = (usize, usize, f64);

struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        Self {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }

    fn union(&mut self, x: usize, y: usize) -> bool {
        let x_root = self.find(x);
        let y_root = self.find(y);
        if x_root == y_root {
            return false;
        }
        match self.rank[x_root].cmp(&self.rank[y_root]) {
            std::cmp::Ordering::Less => self.parent[x_root] = y_root,
            std::cmp::Ordering::Greater => self.parent[y_root] = x_root,
            std::cmp::Ordering::Equal => {
                self.parent[y_root] = x_root;
                self.rank[x_root] += 1;
            }
        }
        true
    }
}

/// Implements a randomized variant of Kruskal's algorithm for finding a minimum spanning tree.
/// It shuffles the edges before sorting to randomize tie-breaking among edges with equal weight.
///
/// # Arguments
/// - `num_vertices`: Total number of vertices.
/// - `edges`: Vector of edges as (u, v, weight) tuples.
///
/// # Returns
/// A tuple containing the list of edges in the MST and the total weight.
pub fn randomized_kruskal(num_vertices: usize, mut edges: Vec<Edge>) -> (Vec<Edge>, f64) {
    let mut rng = thread_rng();
    edges.shuffle(&mut rng);
    edges.sort_by(|a, b| a.2.partial_cmp(&b.2).unwrap());

    let mut uf = UnionFind::new(num_vertices);
    let mut mst_edges = Vec::new();
    let mut total_weight = 0.0;

    for edge in edges {
        if uf.union(edge.0, edge.1) {
            mst_edges.push(edge);
            total_weight += edge.2;
        }
        if mst_edges.len() == num_vertices - 1 {
            break;
        }
    }
    (mst_edges, total_weight)
}

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

    #[test]
    fn test_randomized_kruskal() {
        // Graph: 4 vertices with 6 edges.
        let num_vertices = 4;
        let edges = vec![
            (0, 1, 1.0),
            (0, 2, 4.0),
            (0, 3, 3.0),
            (1, 2, 2.0),
            (1, 3, 5.0),
            (2, 3, 1.5),
        ];
        let (mst, total_weight) = randomized_kruskal(num_vertices, edges);
        // MST should have 3 edges.
        assert_eq!(mst.len(), num_vertices - 1);
        // Depending on random tie-breaking, the total weight should be around 4.5 or 5.0.
        assert!(total_weight - 4.5 < 1e-6 || total_weight - 5.0 < 1e-6);
    }
}