aria_engine_core/
graph.rs1use serde::{Deserialize, Serialize};
2use std::collections::{HashMap, HashSet};
3
4#[derive(Debug, Clone, Serialize, Deserialize)]
6pub struct GraphNode {
7 pub id: String,
9 pub embedding: Vec<f64>,
11 pub node_type: Option<String>,
13}
14
15#[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#[derive(Debug, Clone, Serialize, Deserialize)]
29pub struct Graph {
30 pub nodes: HashMap<String, GraphNode>,
31 pub edges: HashSet<GraphEdge>,
32}
33
34impl Graph {
35 pub fn empty() -> Self {
37 Graph {
38 nodes: HashMap::new(),
39 edges: HashSet::new(),
40 }
41 }
42
43 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 pub fn node_count(&self) -> usize {
52 self.nodes.len()
53 }
54
55 pub fn edge_count(&self) -> usize {
57 self.edges.len()
58 }
59
60 pub fn size(&self) -> usize {
62 self.node_count() + self.edge_count()
63 }
64
65 pub fn ok(&self, latent_dim: usize) -> bool {
72 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 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 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 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 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 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 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 pub fn rebuild(&mut self, target: &Graph) {
146 self.nodes = target.nodes.clone();
147 self.edges = target.edges.clone();
148 }
149
150 pub fn get_embedding(&self, id: &str) -> Option<&Vec<f64>> {
152 self.nodes.get(id).map(|n| &n.embedding)
153 }
154
155 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 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}