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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//! Rigidity Percolation using Laman's Theorem
use std::collections::HashMap;
/// Result of rigidity percolation analysis
///
/// Provides comprehensive metrics about the rigidity properties of a graph
/// based on Laman's theorem for structural rigidity.
pub struct RigidityResult {
/// Whether the graph satisfies Laman's condition for minimal rigidity
pub is_rigid: bool,
/// The rank of the rigidity matrix (number of independent constraints)
pub rank: usize,
/// Deficiency from minimal rigidity (0 = minimally rigid)
pub deficiency: usize,
/// Number of connected clusters in the graph
pub n_clusters: usize,
/// Fraction of nodes that are part of rigid clusters
pub rigid_fraction: f32,
}
/// Fast union-find data structure for rigidity percolation
///
/// Uses path compression and union by rank for efficient
/// connectivity analysis of large graphs.
pub struct FastPercolation {
parent: Vec<usize>,
rank: Vec<usize>,
size: Vec<usize>,
}
impl FastPercolation {
/// Creates a new percolation structure for n nodes
pub fn new(n: usize) -> Self {
Self {
parent: (0..n).collect(),
rank: vec![0; n],
size: vec![1; 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) {
let xr = self.find(x);
let yr = self.find(y);
if xr == yr {
return;
}
if self.rank[xr] < self.rank[yr] {
self.parent[xr] = yr;
self.size[yr] += self.size[xr];
} else if self.rank[xr] > self.rank[yr] {
self.parent[yr] = xr;
self.size[xr] += self.size[yr];
} else {
self.parent[yr] = xr;
self.rank[xr] += 1;
self.size[xr] += self.size[yr];
}
}
/// Computes rigidity metrics for a graph
///
/// Uses Laman's theorem to determine if a graph is minimally rigid.
/// A graph with V vertices is minimally rigid if it has exactly 2V-3 edges
/// and every subgraph with k vertices has at most 2k-3 edges.
///
/// # Arguments
///
/// * `edges` - Slice of (u, v) tuples representing edges
/// * `n_nodes` - Total number of nodes in the graph
///
/// # Returns
///
/// RigidityResult containing comprehensive rigidity metrics
pub fn compute_rigidity(&mut self, edges: &[(usize, usize)], n_nodes: usize) -> RigidityResult {
for &(u, v) in edges {
if u < n_nodes && v < n_nodes {
self.union(u, v);
}
}
let mut clusters: HashMap<usize, usize> = HashMap::new();
for i in 0..n_nodes {
let root = self.find(i);
*clusters.entry(root).or_insert(0) += 1;
}
let n_clusters = clusters.len();
let n_edges = edges.len();
// Laman's theorem (2V - 3) only applies for V >= 3
// For smaller graphs, use special cases
let (is_rigid, rank, deficiency) = if n_nodes < 3 {
// Graphs with < 3 vertices are trivially non-rigid
(false, n_edges, if n_edges > 0 { n_edges } else { 0 })
} else {
let expected_edges = 2 * n_nodes - 3;
let is_rigid = n_edges >= expected_edges;
let rank = n_edges.min(expected_edges);
let deficiency = if n_edges >= 2 * n_nodes - 2 {
n_edges - expected_edges
} else {
expected_edges - n_edges
};
(is_rigid, rank, deficiency)
};
let rigid_nodes: usize = clusters.values().filter(|&&s| s >= 3).sum();
let rigid_fraction = rigid_nodes as f32 / n_nodes as f32;
RigidityResult {
is_rigid,
rank,
deficiency,
n_clusters,
rigid_fraction,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_percolation() {
let mut perc = FastPercolation::new(5);
let edges = [(0, 1), (1, 2), (2, 3), (3, 4)];
let result = perc.compute_rigidity(&edges, 5);
assert!(result.rigid_fraction > 0.0);
}
}