pardarsh_core/
graph.rs

1//! Relationship queries and bounded traversal.
2
3use std::collections::{HashSet, VecDeque};
4
5use serde::Serialize;
6
7use crate::error::Result;
8use crate::id::RecordId;
9use crate::model::RecordKind;
10use crate::relation::{Relation, RelationKind};
11use crate::storage::Store;
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub enum Direction {
15    Outgoing,
16    Incoming,
17    Both,
18}
19
20/// An edge `source --relation.kind--> relation.target`.
21#[derive(Clone, Debug, PartialEq, Serialize)]
22pub struct Edge {
23    pub source: RecordId,
24    pub relation: Relation,
25}
26
27#[derive(Clone, Debug)]
28pub struct TraversalOptions {
29    pub direction: Direction,
30    /// Only follow these relation kinds (empty = all).
31    pub kinds: Vec<RelationKind>,
32    pub max_depth: usize,
33    /// Hard cap on visited records, to bound work on large graphs.
34    pub max_nodes: usize,
35    pub include_retracted: bool,
36}
37
38impl Default for TraversalOptions {
39    fn default() -> Self {
40        Self { direction: Direction::Both, kinds: Vec::new(), max_depth: 2, max_nodes: 500, include_retracted: false }
41    }
42}
43
44#[derive(Clone, Debug, Default, Serialize)]
45pub struct Traversal {
46    /// Visited records with their distance from the start.
47    pub nodes: Vec<(RecordId, usize)>,
48    pub edges: Vec<Edge>,
49    /// Records referenced by an edge but not present in the local store
50    /// (remote or not yet imported). Kept explicit, never guessed.
51    pub unresolved: Vec<RecordId>,
52    pub truncated: bool,
53}
54
55fn wanted(rel: &Relation, opts: &TraversalOptions) -> bool {
56    (opts.include_retracted || !rel.retracted) && (opts.kinds.is_empty() || opts.kinds.contains(&rel.kind))
57}
58
59/// Outgoing edges of a record.
60pub fn outgoing<S: Store>(store: &S, id: &RecordId, kinds: &[RelationKind]) -> Result<Vec<Edge>> {
61    let Some(record) = store.get(id)? else { return Ok(Vec::new()) };
62    Ok(record
63        .active_relations()
64        .filter(|r| kinds.is_empty() || kinds.contains(&r.kind))
65        .map(|r| Edge { source: id.clone(), relation: r.clone() })
66        .collect())
67}
68
69/// Incoming edges of a record, optionally only from sources of some kinds.
70pub fn incoming<S: Store>(store: &S, id: &RecordId, kinds: &[RelationKind], from: &[RecordKind]) -> Result<Vec<Edge>> {
71    Ok(store
72        .incoming(id)?
73        .into_iter()
74        .filter(|e| !e.relation.retracted)
75        .filter(|e| kinds.is_empty() || kinds.contains(&e.relation.kind))
76        .filter(|e| from.is_empty() || from.contains(&e.source_kind))
77        .map(|e| Edge { source: e.source, relation: e.relation })
78        .collect())
79}
80
81/// Breadth-first traversal from `start`.
82pub fn traverse<S: Store>(store: &S, start: &RecordId, opts: &TraversalOptions) -> Result<Traversal> {
83    let mut out = Traversal::default();
84    let mut seen: HashSet<RecordId> = HashSet::from([start.clone()]);
85    let mut edge_seen = HashSet::new();
86    let mut queue = VecDeque::from([(start.clone(), 0usize)]);
87    while let Some((id, depth)) = queue.pop_front() {
88        let Some(record) = store.get(&id)? else {
89            out.unresolved.push(id);
90            continue;
91        };
92        out.nodes.push((id.clone(), depth));
93        if depth >= opts.max_depth {
94            continue;
95        }
96        let mut next = Vec::new();
97        if opts.direction != Direction::Incoming {
98            for rel in record.relations.iter().filter(|r| wanted(r, opts)) {
99                next.push((Edge { source: id.clone(), relation: rel.clone() }, rel.target.clone()));
100            }
101        }
102        if opts.direction != Direction::Outgoing {
103            for e in store.incoming(&id)? {
104                if wanted(&e.relation, opts) {
105                    let src = e.source.clone();
106                    next.push((Edge { source: e.source, relation: e.relation }, src));
107                }
108            }
109        }
110        for (edge, neighbour) in next {
111            if edge_seen.insert((edge.source.clone(), edge.relation.id)) {
112                out.edges.push(edge);
113            }
114            if seen.contains(&neighbour) {
115                continue;
116            }
117            if seen.len() >= opts.max_nodes {
118                out.truncated = true;
119                continue;
120            }
121            seen.insert(neighbour.clone());
122            queue.push_back((neighbour, depth + 1));
123        }
124    }
125    Ok(out)
126}
pardarsh_core/graph.rs

pardarsh_core/
graph.rs
