dsfb_dscd/
graph.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
4pub struct EventId(pub u64);
5
6#[derive(Debug, Clone)]
7pub struct Event {
8    pub id: EventId,
9    pub timestamp: Option<f64>,
10    pub structural_tag: Option<f64>,
11}
12
13#[derive(Debug, Clone)]
14pub struct DscdEdge {
15    pub edge_id: u64,
16    pub from: EventId,
17    pub to: EventId,
18    pub observer_id: u32,
19    pub trust_value: f64,
20    pub trust_at_creation: f64,
21    pub rewrite_rule_at_source: u32,
22}
23
24#[derive(Debug, Default, Clone)]
25pub struct DscdGraph {
26    pub events: Vec<Event>,
27    pub edges: Vec<DscdEdge>,
28}
29
30impl DscdGraph {
31    pub fn add_event(&mut self, event: Event) {
32        if let Some(existing) = self
33            .events
34            .iter_mut()
35            .find(|candidate| candidate.id == event.id)
36        {
37            *existing = event;
38            return;
39        }
40
41        self.events.push(event);
42        self.events.sort_by_key(|candidate| candidate.id);
43    }
44
45    pub fn has_event(&self, event_id: EventId) -> bool {
46        self.events.iter().any(|event| event.id == event_id)
47    }
48}
49
50pub fn add_trust_gated_edge(
51    graph: &mut DscdGraph,
52    from: EventId,
53    to: EventId,
54    observer_id: u32,
55    trust_value: f64,
56    trust_threshold: f64,
57) {
58    add_trust_gated_edge_with_provenance(
59        graph,
60        from,
61        to,
62        observer_id,
63        trust_value,
64        trust_threshold,
65        0,
66    );
67}
68
69pub fn add_trust_gated_edge_with_provenance(
70    graph: &mut DscdGraph,
71    from: EventId,
72    to: EventId,
73    observer_id: u32,
74    trust_value: f64,
75    trust_threshold: f64,
76    rewrite_rule_at_source: u32,
77) {
78    if from >= to || trust_value < trust_threshold {
79        return;
80    }
81
82    if !(graph.has_event(from) && graph.has_event(to)) {
83        return;
84    }
85
86    if graph
87        .edges
88        .iter()
89        .any(|edge| edge.from == from && edge.to == to && edge.observer_id == observer_id)
90    {
91        return;
92    }
93
94    if reachable_from(graph, to, None).contains(&from) {
95        return;
96    }
97
98    let edge_id = graph.edges.len() as u64;
99    graph.edges.push(DscdEdge {
100        edge_id,
101        from,
102        to,
103        observer_id,
104        trust_value,
105        trust_at_creation: trust_value,
106        rewrite_rule_at_source,
107    });
108}
109
110pub fn reachable_from(graph: &DscdGraph, start: EventId, max_depth: Option<usize>) -> Vec<EventId> {
111    if !graph.has_event(start) {
112        return Vec::new();
113    }
114
115    let mut adjacency: HashMap<EventId, Vec<EventId>> = HashMap::new();
116    for edge in &graph.edges {
117        adjacency.entry(edge.from).or_default().push(edge.to);
118    }
119    for neighbors in adjacency.values_mut() {
120        neighbors.sort_unstable();
121    }
122
123    let mut visited = HashSet::new();
124    let mut queue = VecDeque::from([(start, 0_usize)]);
125    visited.insert(start);
126
127    while let Some((node, depth)) = queue.pop_front() {
128        if max_depth.is_some_and(|limit| depth >= limit) {
129            continue;
130        }
131
132        if let Some(neighbors) = adjacency.get(&node) {
133            for &next in neighbors {
134                if visited.insert(next) {
135                    queue.push_back((next, depth + 1));
136                }
137            }
138        }
139    }
140
141    let mut out: Vec<_> = visited.into_iter().collect();
142    out.sort_unstable();
143    out
144}
145
146pub fn expansion_ratio(graph: &DscdGraph, start: EventId) -> f64 {
147    if graph.events.is_empty() {
148        return 0.0;
149    }
150
151    reachable_from(graph, start, None).len() as f64 / graph.events.len() as f64
152}
153
154#[cfg(test)]
155mod tests {
156    use super::*;
157
158    fn toy_graph() -> DscdGraph {
159        let mut graph = DscdGraph::default();
160        for raw_id in 0..4_u64 {
161            graph.add_event(Event {
162                id: EventId(raw_id),
163                timestamp: Some(raw_id as f64),
164                structural_tag: None,
165            });
166        }
167        graph
168    }
169
170    #[test]
171    fn trust_gated_edges_remain_acyclic() {
172        let mut graph = toy_graph();
173        add_trust_gated_edge(&mut graph, EventId(0), EventId(1), 0, 0.9, 0.5);
174        add_trust_gated_edge(&mut graph, EventId(1), EventId(2), 0, 0.9, 0.5);
175        add_trust_gated_edge(&mut graph, EventId(2), EventId(0), 0, 0.9, 0.5);
176        add_trust_gated_edge(&mut graph, EventId(2), EventId(2), 0, 0.9, 0.5);
177
178        assert_eq!(graph.edges.len(), 2);
179        assert!(graph.edges.iter().all(|edge| edge.from < edge.to));
180    }
181
182    #[test]
183    fn reachable_nodes_are_sorted_and_include_start() {
184        let mut graph = toy_graph();
185        add_trust_gated_edge(&mut graph, EventId(0), EventId(1), 0, 0.9, 0.5);
186        add_trust_gated_edge(&mut graph, EventId(1), EventId(3), 0, 0.9, 0.5);
187
188        assert_eq!(
189            reachable_from(&graph, EventId(0), None),
190            vec![EventId(0), EventId(1), EventId(3)]
191        );
192    }
193}
dsfb_dscd/graph.rs

dsfb_dscd/
graph.rs
