weavatrix-graph 0.6.3

Deterministic, evidence-carrying graph core for Weavatrix 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

use crate::{GraphError, IndexUndirectedGraphView, Measure, Result, String, Vec};
use core::cmp::Ordering;

pub(super) struct Candidate<M> {
    pub(super) weight: M,
    pub(super) partition: Vec<usize>,
    pub(super) complement: Vec<usize>,
}

pub(super) fn canonical_candidate<M: Measure>(
    weight: M,
    group: &[usize],
    nodes: &[usize],
) -> Candidate<M> {
    let mut partition = group.to_vec();
    partition.sort_unstable();
    let complement = nodes
        .iter()
        .copied()
        .filter(|node| partition.binary_search(node).is_err())
        .collect::<Vec<_>>();
    if partition.len() > complement.len()
        || (partition.len() == complement.len() && partition > complement)
    {
        Candidate {
            weight,
            partition: complement,
            complement: partition,
        }
    } else {
        Candidate {
            weight,
            partition,
            complement,
        }
    }
}

pub(super) fn better<M: Measure>(candidate: &Candidate<M>, best: Option<&Candidate<M>>) -> bool {
    let Some(best) = best else {
        return true;
    };
    match candidate.weight.compare(best.weight) {
        Some(Ordering::Less) => true,
        Some(Ordering::Equal) => candidate.partition < best.partition,
        _ => false,
    }
}

pub(super) fn nodes<G: IndexUndirectedGraphView>(graph: &G) -> (Vec<Option<G::Node>>, Vec<usize>) {
    let mut by_slot = vec![None; graph.node_bound()];
    let mut slots = Vec::with_capacity(graph.node_count());
    for node in graph.node_indices() {
        let slot = G::node_slot(node);
        by_slot[slot] = Some(node);
        slots.push(slot);
    }
    slots.sort_unstable();
    (by_slot, slots)
}

pub(super) fn map_nodes<Node: Copy>(slots: &[usize], nodes: &[Option<Node>]) -> Result<Vec<Node>> {
    slots
        .iter()
        .map(|&slot| {
            nodes.get(slot).copied().flatten().ok_or_else(|| {
                GraphError::InvalidAlgorithmParameter {
                    algorithm: "Stoer-Wagner",
                    parameter: "active node mapping",
                    value: String::from("active slot has no corresponding graph node"),
                }
            })
        })
        .collect()
}

pub(super) fn validate_weight<M: Measure>(weight: M) -> Result<()> {
    if weight.is_valid() && !weight.is_negative() {
        Ok(())
    } else {
        Err(GraphError::InvalidAlgorithmParameter {
            algorithm: "Stoer-Wagner",
            parameter: "edge weight",
            value: String::from("must be finite and non-negative"),
        })
    }
}