use std::collections::{BTreeMap, BTreeSet};
use crate::Fixed6;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TrustEdge {
pub from: String,
pub to: String,
pub weight: Fixed6,
pub age_days: u64,
pub subjects: Vec<String>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Seed {
pub key: String,
pub weight: Fixed6,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Params {
pub damping: Fixed6,
pub iterations: u32,
pub decay_half_life_days: Option<u64>,
}
pub type Weights = BTreeMap<String, Fixed6>;
#[must_use]
pub fn propagate(params: &Params, roots: &[Seed], edges: &[TrustEdge]) -> Weights {
propagate_within(params, roots, edges, &[])
}
#[must_use]
pub fn propagate_within(
params: &Params,
roots: &[Seed],
edges: &[TrustEdge],
subjects: &[String],
) -> Weights {
let edges: Vec<TrustEdge> = edges
.iter()
.filter(|e| e.subjects.is_empty() || e.subjects.iter().any(|s| subjects.contains(s)))
.cloned()
.collect();
propagate_all(params, roots, &edges)
}
fn propagate_all(params: &Params, roots: &[Seed], edges: &[TrustEdge]) -> Weights {
let seed_total: Fixed6 = roots.iter().map(|r| r.weight).sum();
let mut seed: Weights = BTreeMap::new();
for root in roots {
let share = root.weight.mul_div(Fixed6::ONE, seed_total);
let entry = seed.entry(root.key.clone()).or_insert(Fixed6::ZERO);
*entry = *entry + share;
}
let mut outbound: BTreeMap<String, BTreeMap<String, Fixed6>> = BTreeMap::new();
for edge in edges {
let weight = match params.decay_half_life_days {
Some(half_life) => edge.weight.halve_fractional(edge.age_days, half_life),
None => edge.weight,
};
let slot = outbound
.entry(edge.from.clone())
.or_default()
.entry(edge.to.clone())
.or_insert(Fixed6::ZERO);
*slot = *slot + weight;
}
let normalized: BTreeMap<String, BTreeMap<String, Fixed6>> = outbound
.into_iter()
.map(|(from, targets)| {
let total: Fixed6 = targets.values().copied().sum();
let shares = targets
.into_iter()
.map(|(to, w)| (to, w.mul_div(Fixed6::ONE, total)))
.collect();
(from, shares)
})
.collect();
let damping = params.damping;
let complement = Fixed6::from_scaled(crate::SCALE) - damping;
let mut weights = seed.clone();
for _ in 0..params.iterations {
let mut next: Weights = BTreeMap::new();
for (key, value) in &seed {
let share = value.times(complement);
let entry = next.entry(key.clone()).or_insert(Fixed6::ZERO);
*entry = *entry + share;
}
for (from, share) in &weights {
let Some(targets) = normalized.get(from) else {
continue;
};
for (to, fraction) in targets {
let contribution = share.times(*fraction).times(damping);
let entry = next.entry(to.clone()).or_insert(Fixed6::ZERO);
*entry = *entry + contribution;
}
}
weights = next;
}
weights.retain(|_, v| !v.is_zero());
weights
}
#[must_use]
pub fn reachable_within(edges: &[TrustEdge], start: &str, distance: u32) -> BTreeSet<String> {
let mut adjacency: BTreeMap<&str, BTreeSet<&str>> = BTreeMap::new();
for edge in edges {
adjacency
.entry(edge.from.as_str())
.or_default()
.insert(edge.to.as_str());
adjacency
.entry(edge.to.as_str())
.or_default()
.insert(edge.from.as_str());
}
let mut seen: BTreeSet<String> = BTreeSet::new();
let mut frontier: BTreeSet<&str> = BTreeSet::from([start]);
seen.insert(start.to_owned());
for _ in 0..distance {
let mut next: BTreeSet<&str> = BTreeSet::new();
for node in &frontier {
if let Some(neighbours) = adjacency.get(node) {
for n in neighbours {
if seen.insert((*n).to_owned()) {
next.insert(n);
}
}
}
}
frontier = next;
}
seen
}