use crate::domain::{Embedding, Error, Result, SemanticCluster, SemanticClusters, SemanticEdge};
use super::textrank::MAX_SENTENCES;
pub fn semantic_clusters(
embeddings: &[Embedding],
threshold: f32,
model_hash: &str,
) -> Result<SemanticClusters> {
if !threshold.is_finite() {
return Err(Error::InvalidInput(format!(
"threshold must be finite, got {threshold}"
)));
}
if embeddings.len() > MAX_SENTENCES {
return Err(Error::InputTooLarge {
limit: MAX_SENTENCES,
actual: embeddings.len(),
what: "semantic_clusters",
});
}
let dim = embeddings.first().map_or(0, |e| e.0.len());
for (i, e) in embeddings.iter().enumerate() {
if e.0.len() != dim {
return Err(Error::InvalidInput(format!(
"embedding {i} has dimension {}, expected {dim}",
e.0.len()
)));
}
if !e.0.iter().all(|v| v.is_finite()) {
return Err(Error::InvalidInput(format!(
"embedding {i} contains a non-finite value"
)));
}
}
let n = embeddings.len();
let norms: Vec<f32> = embeddings
.iter()
.map(|e| e.0.iter().map(|v| v * v).sum::<f32>().sqrt())
.collect();
let mut parent: Vec<usize> = (0..n).collect();
fn find(parent: &mut [usize], mut x: usize) -> usize {
while parent[x] != x {
parent[x] = parent[parent[x]];
x = parent[x];
}
x
}
let mut edges: Vec<SemanticEdge> = Vec::new();
for a in 0..n {
if norms[a] == 0.0 {
continue;
}
for b in (a + 1)..n {
if norms[b] == 0.0 {
continue;
}
let dot: f32 = embeddings[a]
.0
.iter()
.zip(&embeddings[b].0)
.map(|(x, y)| x * y)
.sum();
let score = dot / (norms[a] * norms[b]);
if score >= threshold {
edges.push(SemanticEdge { a, b, score });
let (ra, rb) = (find(&mut parent, a), find(&mut parent, b));
if ra != rb {
parent[rb] = ra;
}
}
}
}
let mut clusters: Vec<SemanticCluster> = Vec::new();
let mut root_to_cluster: Vec<Option<usize>> = vec![None; n];
for i in 0..n {
let root = find(&mut parent, i);
if root == i {
continue; }
let slot = match root_to_cluster[root] {
Some(s) => s,
None => {
clusters.push(SemanticCluster {
members: vec![root],
edges: Vec::new(),
});
root_to_cluster[root] = Some(clusters.len() - 1);
clusters.len() - 1
}
};
clusters[slot].members.push(i);
}
for edge in edges {
let root = find(&mut parent, edge.a);
if let Some(slot) = root_to_cluster[root] {
clusters[slot].edges.push(edge);
}
}
for cluster in &mut clusters {
cluster.members.sort_unstable();
cluster.edges.sort_unstable_by_key(|e| (e.a, e.b));
}
clusters.sort_unstable_by_key(|c| c.members[0]);
Ok(SemanticClusters {
model_hash: model_hash.to_string(),
threshold,
clusters,
})
}
#[cfg(test)]
mod tests {
use super::*;
fn e(v: &[f32]) -> Embedding {
Embedding(v.to_vec())
}
#[test]
fn chained_similarity_is_one_component_without_the_far_edge() {
let f = std::f32::consts::FRAC_1_SQRT_2;
let emb = [
e(&[1.0, 0.0]),
e(&[0.9239, 0.3827]), e(&[f, f]), ];
let out = semantic_clusters(&emb, 0.92, "h").unwrap();
assert_eq!(out.clusters.len(), 1);
let c = &out.clusters[0];
assert_eq!(c.members, vec![0, 1, 2]);
let pairs: Vec<(usize, usize)> = c.edges.iter().map(|e| (e.a, e.b)).collect();
assert_eq!(pairs, vec![(0, 1), (1, 2)]);
}
#[test]
fn postconditions_hold() {
let emb = [
e(&[1.0, 0.0]),
e(&[1.0, 0.0]),
e(&[0.0, 1.0]),
e(&[0.0, 1.0]),
e(&[-1.0, 0.0]),
];
let out = semantic_clusters(&emb, 0.99, "h").unwrap();
assert_eq!(out.clusters.len(), 2);
let mut seen = std::collections::HashSet::new();
for c in &out.clusters {
for &m in &c.members {
assert!(seen.insert(m), "member {m} in two clusters");
}
for edge in &c.edges {
assert!(edge.score >= out.threshold);
assert!(edge.a < edge.b);
assert!(c.members.contains(&edge.a) && c.members.contains(&edge.b));
}
let mut reach = std::collections::HashSet::from([c.members[0]]);
let mut grew = true;
while grew {
grew = false;
for edge in &c.edges {
if reach.contains(&edge.a) && reach.insert(edge.b) {
grew = true;
}
if reach.contains(&edge.b) && reach.insert(edge.a) {
grew = true;
}
}
}
for &m in &c.members {
assert!(
reach.contains(&m),
"member {m} unreachable over reported edges"
);
}
}
assert!(!seen.contains(&4), "singleton clustered");
}
#[test]
fn empty_input_yields_empty_clusters_not_an_error() {
let out = semantic_clusters(&[], 0.8, "h").unwrap();
assert!(out.clusters.is_empty());
assert_eq!(out.model_hash, "h");
}
#[test]
fn zero_norm_embeddings_get_no_edges_even_at_threshold_zero() {
let emb = [e(&[0.0, 0.0]), e(&[0.0, 0.0]), e(&[1.0, 0.0])];
let out = semantic_clusters(&emb, 0.0, "h").unwrap();
assert!(out.clusters.is_empty());
}
#[test]
fn dimension_disagreement_is_invalid_input() {
let emb = [e(&[1.0, 0.0]), e(&[1.0, 0.0, 0.0])];
match semantic_clusters(&emb, 0.8, "h") {
Err(Error::InvalidInput(msg)) => assert!(msg.contains("dimension")),
other => panic!("expected InvalidInput, got {:?}", other.map(|_| ())),
}
}
#[test]
fn non_finite_embedding_value_is_invalid_input() {
let emb = [e(&[1.0, 0.0]), e(&[f32::NAN, 0.0])];
match semantic_clusters(&emb, 0.8, "h") {
Err(Error::InvalidInput(msg)) => assert!(msg.contains("non-finite")),
other => panic!("expected InvalidInput, got {:?}", other.map(|_| ())),
}
}
#[test]
fn non_finite_threshold_is_invalid_input() {
match semantic_clusters(&[], f32::NAN, "h") {
Err(Error::InvalidInput(msg)) => assert!(msg.contains("finite")),
other => panic!("expected InvalidInput, got {:?}", other.map(|_| ())),
}
}
#[test]
fn sentence_cap_is_enforced_with_its_own_label() {
let n = MAX_SENTENCES + 1;
let emb: Vec<Embedding> = (0..n).map(|_| e(&[1.0])).collect();
match semantic_clusters(&emb, 0.9, "h") {
Err(Error::InputTooLarge { what, .. }) => assert_eq!(what, "semantic_clusters"),
other => panic!("expected InputTooLarge, got {:?}", other.map(|_| ())),
}
}
#[test]
fn output_ordering_is_deterministic() {
let emb = [
e(&[0.0, 1.0]),
e(&[1.0, 0.0]),
e(&[0.0, 1.0]),
e(&[1.0, 0.0]),
];
let out = semantic_clusters(&emb, 0.99, "h").unwrap();
assert_eq!(out.clusters[0].members, vec![0, 2]);
assert_eq!(out.clusters[1].members, vec![1, 3]);
}
}