weavatrix-graph 0.4.0

Deterministic, evidence-carrying graph primitives for repository intelligence
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

use crate::IndexUndirectedGraphView;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SpanningForest<Edge> {
    edges: Vec<Edge>,
    total_weight: u128,
    component_count: usize,
}

impl<Edge> SpanningForest<Edge> {
    #[must_use]
    pub fn edges(&self) -> &[Edge] {
        &self.edges
    }

    #[must_use]
    pub const fn total_weight(&self) -> u128 {
        self.total_weight
    }

    #[must_use]
    pub const fn component_count(&self) -> usize {
        self.component_count
    }

    #[must_use]
    pub fn into_edges(self) -> Vec<Edge> {
        self.edges
    }
}

pub fn minimum_spanning_forest<G, F>(graph: &G, mut edge_weight: F) -> SpanningForest<G::Edge>
where
    G: IndexUndirectedGraphView,
    F: FnMut(G::Edge) -> u64,
{
    let mut weighted = graph
        .edge_indices()
        .map(|edge| (edge_weight(edge), G::edge_slot(edge), edge))
        .collect::<Vec<_>>();
    weighted.sort_unstable_by_key(|&(weight, slot, _)| (weight, slot));

    let mut sets = DisjointSets::new(graph.node_bound());
    let mut selected = Vec::with_capacity(graph.node_count().saturating_sub(1));
    let mut total_weight = 0_u128;
    let mut component_count = graph.node_count();
    for (weight, _, edge) in weighted {
        let Some(endpoints) = graph.edge_endpoints(edge) else {
            continue;
        };
        let source = G::node_slot(endpoints.source());
        let target = G::node_slot(endpoints.target());
        if sets.union(source, target) {
            selected.push(edge);
            total_weight += u128::from(weight);
            component_count -= 1;
        }
    }
    SpanningForest {
        edges: selected,
        total_weight,
        component_count,
    }
}

struct DisjointSets {
    parent: Vec<usize>,
    rank: Vec<u8>,
}

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

    fn find(&mut self, mut node: usize) -> usize {
        let mut root = node;
        while self.parent[root] != root {
            root = self.parent[root];
        }
        while self.parent[node] != node {
            let parent = self.parent[node];
            self.parent[node] = root;
            node = parent;
        }
        root
    }

    fn union(&mut self, left: usize, right: usize) -> bool {
        let mut left = self.find(left);
        let mut right = self.find(right);
        if left == right {
            return false;
        }
        if self.rank[left] < self.rank[right] {
            std::mem::swap(&mut left, &mut right);
        }
        self.parent[right] = left;
        if self.rank[left] == self.rank[right] {
            self.rank[left] = self.rank[left].saturating_add(1);
        }
        true
    }
}