#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};
use std::collections::HashMap;
use uuid::Uuid;
use crate::error::FoldError;
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct AnchorRef {
pub id: Uuid,
pub kind: String,
pub stable_id: Option<String>,
}
#[derive(Debug, Clone, Default)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct AnchorGraph {
pub nodes: Vec<AnchorRef>,
pub edges: Vec<(Uuid, Uuid, String)>,
}
impl AnchorGraph {
pub fn new() -> Self {
Self::default()
}
pub fn add_node(&mut self, anchor: AnchorRef) {
self.nodes.push(anchor);
}
pub fn add_edge(&mut self, from: Uuid, to: Uuid, relation: impl Into<String>) {
self.edges.push((from, to, relation.into()));
}
pub fn find_node(&self, id: Uuid) -> Option<&AnchorRef> {
self.nodes.iter().find(|n| n.id == id)
}
pub fn outgoing(&self, from: Uuid) -> impl Iterator<Item = (Uuid, &str)> {
self.edges
.iter()
.filter(move |(f, _, _)| *f == from)
.map(|(_, to, rel)| (*to, rel.as_str()))
}
pub fn incoming(&self, to: Uuid) -> impl Iterator<Item = (Uuid, &str)> {
self.edges
.iter()
.filter(move |(_, t, _)| *t == to)
.map(|(from, _, rel)| (*from, rel.as_str()))
}
}
pub trait Anchor: Send + Sync {
fn trace(
&self,
graph: &AnchorGraph,
start: &AnchorRef,
max_depth: usize,
) -> Result<Vec<AnchorRef>, FoldError>;
fn credit(
&self,
graph: &AnchorGraph,
outcome: &AnchorRef,
max_depth: usize,
) -> Result<Vec<(AnchorRef, f64)>, FoldError>;
}
#[derive(Debug, Clone, Copy, Default)]
pub struct BfsAnchor;
struct TraversalIndex<'a> {
nodes: HashMap<Uuid, &'a AnchorRef>,
neighbors: HashMap<Uuid, Vec<Uuid>>,
}
impl<'a> TraversalIndex<'a> {
fn new(graph: &'a AnchorGraph, reverse: bool) -> Self {
let mut nodes = HashMap::new();
for node in &graph.nodes {
nodes.entry(node.id).or_insert(node);
}
let mut neighbors: HashMap<Uuid, Vec<Uuid>> = HashMap::new();
for (from, to, _) in &graph.edges {
let (key, neighbor) = if reverse { (*to, *from) } else { (*from, *to) };
neighbors.entry(key).or_default().push(neighbor);
}
Self { nodes, neighbors }
}
fn find_node(&self, id: Uuid) -> Option<&'a AnchorRef> {
self.nodes.get(&id).copied()
}
fn neighbors(&self, id: Uuid) -> impl Iterator<Item = Uuid> + '_ {
self.neighbors.get(&id).into_iter().flatten().copied()
}
}
impl Anchor for BfsAnchor {
fn trace(
&self,
graph: &AnchorGraph,
start: &AnchorRef,
max_depth: usize,
) -> Result<Vec<AnchorRef>, FoldError> {
if graph.find_node(start.id).is_none() {
return Err(FoldError::AnchorNotFound(start.id.to_string()));
}
if max_depth == 0 {
return Ok(Vec::new());
}
let index = TraversalIndex::new(graph, false);
let mut visited = std::collections::HashSet::new();
let mut result = Vec::new();
let mut queue = std::collections::VecDeque::new();
visited.insert(start.id);
queue.push_back((start.id, 0usize));
while let Some((current_id, depth)) = queue.pop_front() {
if let Some(node) = index.find_node(current_id) {
if current_id != start.id {
result.push(node.clone());
}
if depth < max_depth {
for next_id in index.neighbors(current_id) {
if visited.insert(next_id) {
queue.push_back((next_id, depth + 1));
}
}
}
}
}
Ok(result)
}
fn credit(
&self,
graph: &AnchorGraph,
outcome: &AnchorRef,
max_depth: usize,
) -> Result<Vec<(AnchorRef, f64)>, FoldError> {
if graph.find_node(outcome.id).is_none() {
return Err(FoldError::AnchorNotFound(outcome.id.to_string()));
}
if max_depth == 0 {
return Ok(Vec::new());
}
let index = TraversalIndex::new(graph, true);
let mut visited = std::collections::HashSet::new();
let mut result = Vec::new();
let mut queue = std::collections::VecDeque::new();
visited.insert(outcome.id);
queue.push_back((outcome.id, 0usize, 1.0f64));
while let Some((current_id, depth, weight)) = queue.pop_front() {
if current_id != outcome.id {
if let Some(node) = index.find_node(current_id) {
result.push((node.clone(), weight));
}
}
if depth < max_depth {
let predecessors: Vec<(Uuid, f64)> = index
.neighbors(current_id)
.filter(|id| visited.insert(*id))
.map(|id| (id, weight * 0.5))
.collect();
for (pred_id, pred_weight) in predecessors {
queue.push_back((pred_id, depth + 1, pred_weight));
}
}
}
Ok(result)
}
}
#[cfg(test)]
#[path = "anchor_tests.rs"]
mod tests;