Skip to main content

aria_engine_core/
graph.rs

1use serde::{Deserialize, Serialize};
2use std::collections::{HashMap, HashSet};
3
4/// A node in the experience graph.
5#[derive(Debug, Clone, Serialize, Deserialize)]
6pub struct GraphNode {
7    /// Unique node identifier
8    pub id: String,
9    /// Embedding in latent space Z
10    pub embedding: Vec<f64>,
11    /// Optional node type label
12    pub node_type: Option<String>,
13}
14
15/// A typed edge between two nodes.
16#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
17pub struct GraphEdge {
18    pub from: String,
19    pub to: String,
20    pub edge_type: String,
21}
22
23/// Experience/thought graph G — 𝔸3
24///
25/// Nodes carry embeddings in Z (latent space).
26/// Edges are typed morphisms.
27/// Only Match mutates G.
28#[derive(Debug, Clone, Serialize, Deserialize)]
29pub struct Graph {
30    pub nodes: HashMap<String, GraphNode>,
31    pub edges: HashSet<GraphEdge>,
32}
33
34impl Graph {
35    /// Create an empty graph.
36    pub fn empty() -> Self {
37        Graph {
38            nodes: HashMap::new(),
39            edges: HashSet::new(),
40        }
41    }
42
43    /// Create a seed graph with a single root node.
44    pub fn seed(node: GraphNode) -> Self {
45        let mut g = Graph::empty();
46        g.nodes.insert(node.id.clone(), node);
47        g
48    }
49
50    /// Number of nodes.
51    pub fn node_count(&self) -> usize {
52        self.nodes.len()
53    }
54
55    /// Number of edges.
56    pub fn edge_count(&self) -> usize {
57        self.edges.len()
58    }
59
60    /// Total size |G| = |V| + |E|.
61    pub fn size(&self) -> usize {
62        self.node_count() + self.edge_count()
63    }
64
65    /// GraphOK — Inv3: typed nodes/edges, embeddings in Z.
66    ///
67    /// Checks:
68    /// - Every edge endpoint is an existing node
69    /// - All embeddings have matching dimension
70    /// - All embeddings are finite (in Z)
71    pub fn ok(&self, latent_dim: usize) -> bool {
72        // Every edge endpoint must be a node
73        for edge in &self.edges {
74            if !self.nodes.contains_key(&edge.from) || !self.nodes.contains_key(&edge.to) {
75                return false;
76            }
77        }
78
79        // All embeddings must have matching dimension and be finite
80        for node in self.nodes.values() {
81            if node.embedding.len() != latent_dim {
82                return false;
83            }
84            for &v in &node.embedding {
85                if !v.is_finite() {
86                    return false;
87                }
88            }
89        }
90
91        true
92    }
93
94    /// Add a node with a latent embedding.
95    pub fn add_node(&mut self, id: String, embedding: Vec<f64>, node_type: Option<String>) {
96        self.nodes.insert(
97            id.clone(),
98            GraphNode {
99                id,
100                embedding,
101                node_type,
102            },
103        );
104    }
105
106    /// Delete a node and all incident edges.
107    pub fn delete_node(&mut self, id: &str) {
108        self.nodes.remove(id);
109        self.edges.retain(|e| e.from != id && e.to != id);
110    }
111
112    /// Add a typed edge.
113    pub fn add_edge(&mut self, from: String, to: String, edge_type: String) -> bool {
114        if !self.nodes.contains_key(&from) || !self.nodes.contains_key(&to) {
115            return false;
116        }
117        self.edges.insert(GraphEdge {
118            from,
119            to,
120            edge_type,
121        });
122        true
123    }
124
125    /// Delete an edge.
126    pub fn delete_edge(&mut self, from: &str, to: &str, edge_type: &str) -> bool {
127        self.edges.remove(&GraphEdge {
128            from: from.to_string(),
129            to: to.to_string(),
130            edge_type: edge_type.to_string(),
131        })
132    }
133
134    /// Relabel a node's embedding.
135    pub fn relabel_node(&mut self, id: &str, new_embedding: Vec<f64>) -> bool {
136        if let Some(node) = self.nodes.get_mut(id) {
137            node.embedding = new_embedding;
138            true
139        } else {
140            false
141        }
142    }
143
144    /// Replace the entire graph with a target (rebuild to G*).
145    pub fn rebuild(&mut self, target: &Graph) {
146        self.nodes = target.nodes.clone();
147        self.edges = target.edges.clone();
148    }
149
150    /// Get a node's embedding.
151    pub fn get_embedding(&self, id: &str) -> Option<&Vec<f64>> {
152        self.nodes.get(id).map(|n| &n.embedding)
153    }
154
155    /// Whether the directed dependency spine is acyclic (Inv7 candidate gate).
156    ///
157    /// Kahn's algorithm: a DAG has a topological order covering every node.
158    pub fn is_acyclic(&self) -> bool {
159        let mut indegree: HashMap<&str, usize> =
160            self.nodes.keys().map(|k| (k.as_str(), 0)).collect();
161        let mut out: HashMap<&str, Vec<&str>> = HashMap::new();
162
163        for e in &self.edges {
164            // Ignore dangling edges here; Inv3 owns that failure mode.
165            let (Some(d), true) = (
166                indegree.get_mut(e.to.as_str()),
167                self.nodes.contains_key(&e.from),
168            ) else {
169                continue;
170            };
171            *d += 1;
172            out.entry(e.from.as_str()).or_default().push(e.to.as_str());
173        }
174
175        let mut queue: Vec<&str> = indegree
176            .iter()
177            .filter(|(_, &d)| d == 0)
178            .map(|(&k, _)| k)
179            .collect();
180
181        let mut visited = 0;
182        while let Some(n) = queue.pop() {
183            visited += 1;
184            for &m in out.get(n).into_iter().flatten() {
185                if let Some(d) = indegree.get_mut(m) {
186                    *d -= 1;
187                    if *d == 0 {
188                        queue.push(m);
189                    }
190                }
191            }
192        }
193
194        visited == self.nodes.len()
195    }
196}
197
198impl Default for Graph {
199    fn default() -> Self {
200        Graph::empty()
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use super::*;
207
208    fn test_graph() -> Graph {
209        let mut g = Graph::empty();
210        g.add_node("n1".into(), vec![1.0, 0.0], None);
211        g.add_node("n2".into(), vec![0.0, 1.0], None);
212        g.add_edge("n1".into(), "n2".into(), "morph".into());
213        g
214    }
215
216    #[test]
217    fn graph_ok_valid() {
218        let g = test_graph();
219        assert!(g.ok(2));
220    }
221
222    #[test]
223    fn graph_ok_wrong_dim() {
224        let g = test_graph();
225        assert!(!g.ok(3));
226    }
227
228    #[test]
229    fn acyclic_chain_is_acyclic() {
230        assert!(test_graph().is_acyclic());
231    }
232
233    #[test]
234    fn a_cycle_is_detected() {
235        let mut g = test_graph();
236        g.add_edge("n2".into(), "n1".into(), "morph".into());
237        assert!(!g.is_acyclic());
238    }
239
240    #[test]
241    fn a_self_loop_is_a_cycle() {
242        let mut g = test_graph();
243        g.add_edge("n1".into(), "n1".into(), "morph".into());
244        assert!(!g.is_acyclic());
245    }
246
247    #[test]
248    fn graph_ok_dangling_edge() {
249        let mut g = test_graph();
250        g.edges.insert(GraphEdge {
251            from: "n1".into(),
252            to: "ghost".into(),
253            edge_type: "morph".into(),
254        });
255        assert!(!g.ok(2));
256    }
257}