1use serde::de::{self, Deserializer, Visitor};
26use serde::{Deserialize, Serialize, Serializer};
27use std::collections::{BTreeMap, BTreeSet};
28use std::fmt;
29
30pub type NodeId = u64;
32
33#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
35pub enum NodeType {
36 #[default]
38 Observation,
39 Hypothesis,
41 Action,
43 Goal,
45 InvariantCheckpoint,
47 Custom(String),
49}
50
51impl NodeType {
52 pub fn as_str(&self) -> &str {
54 match self {
55 NodeType::Observation => "observation",
56 NodeType::Hypothesis => "hypothesis",
57 NodeType::Action => "action",
58 NodeType::Goal => "goal",
59 NodeType::InvariantCheckpoint => "invariant_checkpoint",
60 NodeType::Custom(s) => s,
61 }
62 }
63
64 pub fn from_wire(s: &str) -> Self {
78 match s {
79 "latent" | "observation" => NodeType::Observation,
81 "hypothesis" => NodeType::Hypothesis,
82 "action" => NodeType::Action,
83 "goal" => NodeType::Goal,
84 "invariant_checkpoint" => NodeType::InvariantCheckpoint,
85 other => NodeType::Custom(other.to_string()),
86 }
87 }
88}
89
90#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
92pub enum EdgeType {
93 #[default]
95 CausallyPrecedes,
96 Contradicts,
98 Refines,
100 TemporalNext,
102 Custom(String),
104}
105
106impl EdgeType {
107 pub fn as_str(&self) -> &str {
109 match self {
110 EdgeType::CausallyPrecedes => "causally_precedes",
111 EdgeType::Contradicts => "contradicts",
112 EdgeType::Refines => "refines",
113 EdgeType::TemporalNext => "temporal_next",
114 EdgeType::Custom(s) => s,
115 }
116 }
117
118 pub fn from_wire(s: &str) -> Self {
121 match s {
122 "morph" | "causally_precedes" => EdgeType::CausallyPrecedes,
123 "contradicts" => EdgeType::Contradicts,
124 "refines" => EdgeType::Refines,
125 "temporal_next" => EdgeType::TemporalNext,
126 other => EdgeType::Custom(other.to_string()),
127 }
128 }
129}
130
131macro_rules! string_serde {
134 ($t:ty, $expecting:literal) => {
135 impl Serialize for $t {
136 fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
137 s.serialize_str(self.as_str())
138 }
139 }
140
141 impl<'de> Deserialize<'de> for $t {
142 fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
143 struct V;
144 impl Visitor<'_> for V {
145 type Value = $t;
146 fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
147 f.write_str($expecting)
148 }
149 fn visit_str<E: de::Error>(self, v: &str) -> Result<$t, E> {
150 Ok(<$t>::from_wire(v))
151 }
152 }
153 d.deserialize_str(V)
154 }
155 }
156 };
157}
158
159string_serde!(NodeType, "a node type name");
160string_serde!(EdgeType, "an edge type name");
161
162#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
164pub struct GraphNode {
165 pub id: NodeId,
167 pub embedding: Vec<f64>,
169 #[serde(default)]
171 pub node_type: NodeType,
172 #[serde(default)]
174 pub timestamp: u64,
175}
176
177#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
179pub struct GraphEdge {
180 pub from: NodeId,
182 pub to: NodeId,
184 pub edge_type: EdgeType,
186}
187
188#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
190pub struct Graph {
191 pub nodes: BTreeMap<NodeId, GraphNode>,
197 pub edges: BTreeSet<GraphEdge>,
200 #[serde(default)]
203 next_id: NodeId,
204}
205
206#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
208pub enum GraphOpError {
209 #[error("graph op references missing node {0}")]
211 MissingNode(NodeId),
212 #[error("node {0} already exists with different content")]
214 DuplicateNode(NodeId),
215 #[error("node {id}: embedding has dim {got}, expected {want}")]
217 Dim {
218 id: NodeId,
220 got: usize,
222 want: usize,
224 },
225 #[error("node {0}: embedding contains a non-finite component")]
227 NonFinite(NodeId),
228 #[error("MergeNodes requires distinct nodes, got {0} twice")]
230 SelfMerge(NodeId),
231}
232
233#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
236pub enum GraphOp {
237 AddNode {
239 id: NodeId,
241 ntype: NodeType,
243 emb: Vec<f64>,
245 ts: u64,
247 },
248 DeleteNode {
250 id: NodeId,
252 },
253 AddEdge {
255 from: NodeId,
257 to: NodeId,
259 etype: EdgeType,
261 },
262 DeleteEdge {
264 from: NodeId,
266 to: NodeId,
268 etype: EdgeType,
270 },
271 RelabelNode {
273 id: NodeId,
275 emb: Vec<f64>,
277 },
278 MergeNodes {
281 keep: NodeId,
283 merged: NodeId,
285 },
286}
287
288#[derive(Debug, Clone, PartialEq)]
294pub enum UndoOp {
295 DropNode(NodeId),
297 RestoreNode {
299 node: GraphNode,
301 edges: Vec<GraphEdge>,
303 },
304 DropEdge(GraphEdge),
306 RestoreEdge(GraphEdge),
308 RestoreEmbedding {
310 id: NodeId,
312 emb: Vec<f64>,
314 },
315 Unmerge {
317 merged: GraphNode,
319 merged_edges: Vec<GraphEdge>,
321 keep: NodeId,
323 keep_emb: Vec<f64>,
325 keep_ts: u64,
327 rewired: Vec<GraphEdge>,
329 },
330 Noop,
332}
333
334const MERGE_EMA_KEEP: f64 = 0.9;
337const MERGE_EMA_NEW: f64 = 0.1;
338
339impl Graph {
340 pub fn empty() -> Self {
342 Graph {
343 nodes: BTreeMap::new(),
344 edges: BTreeSet::new(),
345 next_id: 0,
346 }
347 }
348
349 pub fn seed(node: GraphNode) -> Self {
351 let mut g = Graph::empty();
352 g.next_id = node.id + 1;
353 g.nodes.insert(node.id, node);
354 g
355 }
356
357 pub fn node_count(&self) -> usize {
359 self.nodes.len()
360 }
361
362 pub fn edge_count(&self) -> usize {
364 self.edges.len()
365 }
366
367 pub fn size(&self) -> usize {
369 self.node_count() + self.edge_count()
370 }
371
372 pub fn next_id(&self) -> NodeId {
375 self.next_id
376 }
377
378 pub fn node(&self, id: NodeId) -> Option<&GraphNode> {
380 self.nodes.get(&id)
381 }
382
383 pub fn get_embedding(&self, id: NodeId) -> Option<&Vec<f64>> {
385 self.nodes.get(&id).map(|n| &n.embedding)
386 }
387
388 pub fn incident(&self, id: NodeId) -> Vec<GraphEdge> {
390 self.edges
391 .iter()
392 .filter(|e| e.from == id || e.to == id)
393 .cloned()
394 .collect()
395 }
396
397 pub fn ok(&self, latent_dim: usize) -> bool {
403 for edge in &self.edges {
404 if !self.nodes.contains_key(&edge.from) || !self.nodes.contains_key(&edge.to) {
405 return false;
406 }
407 }
408 for (id, node) in &self.nodes {
409 if *id != node.id
410 || node.embedding.len() != latent_dim
411 || !node.embedding.iter().all(|v| v.is_finite())
412 {
413 return false;
414 }
415 }
416 true
417 }
418
419 pub fn is_acyclic(&self) -> bool {
423 let mut indegree: BTreeMap<NodeId, usize> = self.nodes.keys().map(|&k| (k, 0)).collect();
424 let mut out: BTreeMap<NodeId, Vec<NodeId>> = BTreeMap::new();
425
426 for e in &self.edges {
427 if !self.nodes.contains_key(&e.from) {
429 continue;
430 }
431 if let Some(d) = indegree.get_mut(&e.to) {
432 *d += 1;
433 out.entry(e.from).or_default().push(e.to);
434 }
435 }
436
437 let mut queue: Vec<NodeId> = indegree
438 .iter()
439 .filter(|(_, &d)| d == 0)
440 .map(|(&k, _)| k)
441 .collect();
442
443 let mut visited = 0usize;
444 while let Some(n) = queue.pop() {
445 visited += 1;
446 for &m in out.get(&n).into_iter().flatten() {
447 if let Some(d) = indegree.get_mut(&m) {
448 *d -= 1;
449 if *d == 0 {
450 queue.push(m);
451 }
452 }
453 }
454 }
455
456 visited == self.nodes.len()
457 }
458
459 fn check_embedding(id: NodeId, emb: &[f64], latent_dim: usize) -> Result<(), GraphOpError> {
461 if emb.len() != latent_dim {
462 return Err(GraphOpError::Dim {
463 id,
464 got: emb.len(),
465 want: latent_dim,
466 });
467 }
468 if !emb.iter().all(|v| v.is_finite()) {
469 return Err(GraphOpError::NonFinite(id));
470 }
471 Ok(())
472 }
473
474 pub fn apply(&mut self, op: &GraphOp, latent_dim: usize) -> Result<UndoOp, GraphOpError> {
479 match op {
480 GraphOp::AddNode { id, ntype, emb, ts } => {
481 self.apply_add_node(*id, ntype.clone(), emb, *ts, latent_dim)
482 }
483 GraphOp::DeleteNode { id } => Ok(self.apply_delete_node(*id)),
484 GraphOp::AddEdge { from, to, etype } => {
485 self.apply_add_edge(*from, *to, etype.clone())
486 }
487 GraphOp::DeleteEdge { from, to, etype } => {
488 Ok(self.apply_delete_edge(*from, *to, etype.clone()))
489 }
490 GraphOp::RelabelNode { id, emb } => {
491 self.apply_relabel_node(*id, emb, latent_dim)
492 }
493 GraphOp::MergeNodes { keep, merged } => self.apply_merge_nodes(*keep, *merged),
494 }
495 }
496
497 fn apply_add_node(
498 &mut self,
499 id: NodeId,
500 ntype: NodeType,
501 emb: &[f64],
502 ts: u64,
503 latent_dim: usize,
504 ) -> Result<UndoOp, GraphOpError> {
505 Self::check_embedding(id, emb, latent_dim)?;
506 let candidate = GraphNode {
507 id,
508 embedding: emb.to_vec(),
509 node_type: ntype,
510 timestamp: ts,
511 };
512 if let Some(existing) = self.nodes.get(&id) {
513 return if *existing == candidate {
516 Ok(UndoOp::Noop)
517 } else {
518 Err(GraphOpError::DuplicateNode(id))
519 };
520 }
521 self.nodes.insert(id, candidate);
522 self.next_id = self.next_id.max(id.saturating_add(1));
523 Ok(UndoOp::DropNode(id))
524 }
525
526 fn apply_delete_node(&mut self, id: NodeId) -> UndoOp {
527 let Some(node) = self.nodes.remove(&id) else {
528 return UndoOp::Noop;
529 };
530 let edges = self.incident(id);
531 for e in &edges {
532 self.edges.remove(e);
533 }
534 UndoOp::RestoreNode { node, edges }
535 }
536
537 fn apply_add_edge(
538 &mut self,
539 from: NodeId,
540 to: NodeId,
541 etype: EdgeType,
542 ) -> Result<UndoOp, GraphOpError> {
543 if !self.nodes.contains_key(&from) {
544 return Err(GraphOpError::MissingNode(from));
545 }
546 if !self.nodes.contains_key(&to) {
547 return Err(GraphOpError::MissingNode(to));
548 }
549 let edge = GraphEdge {
550 from,
551 to,
552 edge_type: etype,
553 };
554 if self.edges.contains(&edge) {
555 return Ok(UndoOp::Noop);
556 }
557 self.edges.insert(edge.clone());
558 Ok(UndoOp::DropEdge(edge))
559 }
560
561 fn apply_delete_edge(&mut self, from: NodeId, to: NodeId, etype: EdgeType) -> UndoOp {
562 let edge = GraphEdge {
563 from,
564 to,
565 edge_type: etype,
566 };
567 if self.edges.remove(&edge) {
568 UndoOp::RestoreEdge(edge)
569 } else {
570 UndoOp::Noop
571 }
572 }
573
574 fn apply_relabel_node(
575 &mut self,
576 id: NodeId,
577 emb: &[f64],
578 latent_dim: usize,
579 ) -> Result<UndoOp, GraphOpError> {
580 Self::check_embedding(id, emb, latent_dim)?;
581 let Some(node) = self.nodes.get_mut(&id) else {
582 return Err(GraphOpError::MissingNode(id));
583 };
584 if node.embedding == emb {
585 return Ok(UndoOp::Noop);
586 }
587 let previous = std::mem::replace(&mut node.embedding, emb.to_vec());
588 Ok(UndoOp::RestoreEmbedding { id, emb: previous })
589 }
590
591 fn apply_merge_nodes(
592 &mut self,
593 keep: NodeId,
594 merged: NodeId,
595 ) -> Result<UndoOp, GraphOpError> {
596 if keep == merged {
597 return Err(GraphOpError::SelfMerge(keep));
598 }
599 if !self.nodes.contains_key(&keep) {
600 return Err(GraphOpError::MissingNode(keep));
601 }
602 let Some(merged_node) = self.nodes.get(&merged).cloned() else {
603 return Err(GraphOpError::MissingNode(merged));
604 };
605
606 let merged_edges = self.incident(merged);
607 let keep_node = &self.nodes[&keep];
608 let keep_emb = keep_node.embedding.clone();
609 let keep_ts = keep_node.timestamp;
610
611 let mut rewired = Vec::new();
615 for e in &merged_edges {
616 self.edges.remove(e);
617 let moved = GraphEdge {
618 from: if e.from == merged { keep } else { e.from },
619 to: if e.to == merged { keep } else { e.to },
620 edge_type: e.edge_type.clone(),
621 };
622 if moved.from == moved.to {
623 continue;
624 }
625 if self.edges.insert(moved.clone()) {
626 rewired.push(moved);
627 }
628 }
629
630 let keep_node = self.nodes.get_mut(&keep).expect("checked above");
632 for (e, c) in keep_node
633 .embedding
634 .iter_mut()
635 .zip(merged_node.embedding.iter())
636 {
637 *e = MERGE_EMA_KEEP * *e + MERGE_EMA_NEW * *c;
638 }
639 keep_node.timestamp = merged_node.timestamp;
640 self.nodes.remove(&merged);
641
642 Ok(UndoOp::Unmerge {
643 merged: merged_node,
644 merged_edges,
645 keep,
646 keep_emb,
647 keep_ts,
648 rewired,
649 })
650 }
651
652 pub fn same_content(&self, other: &Graph) -> bool {
659 self.nodes == other.nodes && self.edges == other.edges
660 }
661
662 pub fn undo(&mut self, entry: &UndoOp) {
670 match entry {
671 UndoOp::Noop => {}
672 UndoOp::DropNode(id) => {
673 self.nodes.remove(id);
674 self.edges.retain(|e| e.from != *id && e.to != *id);
675 }
676 UndoOp::RestoreNode { node, edges } => {
677 self.nodes.insert(node.id, node.clone());
678 for e in edges {
679 self.edges.insert(e.clone());
680 }
681 }
682 UndoOp::DropEdge(edge) => {
683 self.edges.remove(edge);
684 }
685 UndoOp::RestoreEdge(edge) => {
686 self.edges.insert(edge.clone());
687 }
688 UndoOp::RestoreEmbedding { id, emb } => {
689 if let Some(node) = self.nodes.get_mut(id) {
690 node.embedding.clone_from(emb);
691 }
692 }
693 UndoOp::Unmerge {
694 merged,
695 merged_edges,
696 keep,
697 keep_emb,
698 keep_ts,
699 rewired,
700 } => {
701 for e in rewired {
702 self.edges.remove(e);
703 }
704 if let Some(node) = self.nodes.get_mut(keep) {
705 node.embedding.clone_from(keep_emb);
706 node.timestamp = *keep_ts;
707 }
708 self.nodes.insert(merged.id, merged.clone());
709 for e in merged_edges {
710 self.edges.insert(e.clone());
711 }
712 }
713 }
714 }
715
716 pub fn apply_ops(
719 &mut self,
720 ops: &[GraphOp],
721 latent_dim: usize,
722 ) -> Result<Vec<UndoOp>, GraphOpError> {
723 let mut journal = Vec::with_capacity(ops.len());
724 for op in ops {
725 match self.apply(op, latent_dim) {
726 Ok(entry) => journal.push(entry),
727 Err(e) => {
728 self.undo_ops(&journal);
729 return Err(e);
730 }
731 }
732 }
733 Ok(journal)
734 }
735
736 pub fn undo_ops(&mut self, journal: &[UndoOp]) {
738 for entry in journal.iter().rev() {
739 self.undo(entry);
740 }
741 }
742}
743
744impl Default for Graph {
745 fn default() -> Self {
746 Graph::empty()
747 }
748}
749
750#[cfg(test)]
751mod tests {
752 use super::*;
753
754 const DIM: usize = 2;
755
756 fn node(id: NodeId, emb: [f64; DIM]) -> GraphNode {
757 GraphNode {
758 id,
759 embedding: emb.to_vec(),
760 node_type: NodeType::Observation,
761 timestamp: id,
762 }
763 }
764
765 fn two_node_graph() -> Graph {
766 let mut g = Graph::empty();
767 g.apply(
768 &GraphOp::AddNode {
769 id: 1,
770 ntype: NodeType::Observation,
771 emb: vec![1.0, 0.0],
772 ts: 1,
773 },
774 DIM,
775 )
776 .unwrap();
777 g.apply(
778 &GraphOp::AddNode {
779 id: 2,
780 ntype: NodeType::Hypothesis,
781 emb: vec![0.0, 1.0],
782 ts: 2,
783 },
784 DIM,
785 )
786 .unwrap();
787 g.apply(
788 &GraphOp::AddEdge {
789 from: 1,
790 to: 2,
791 etype: EdgeType::CausallyPrecedes,
792 },
793 DIM,
794 )
795 .unwrap();
796 g
797 }
798
799 #[test]
800 fn graph_ok_accepts_a_well_formed_graph() {
801 let g = two_node_graph();
802 assert!(g.ok(DIM));
803 assert_eq!(g.node_count(), 2);
804 assert_eq!(g.edge_count(), 1);
805 assert_eq!(g.size(), 3);
806 }
807
808 #[test]
809 fn graph_ok_rejects_wrong_dimension_and_dangling_edges() {
810 let g = two_node_graph();
811 assert!(!g.ok(DIM + 1), "wrong latent_dim must fail Inv3");
812
813 let mut dangling = two_node_graph();
814 dangling.edges.insert(GraphEdge {
815 from: 1,
816 to: 999,
817 edge_type: EdgeType::Refines,
818 });
819 assert!(!dangling.ok(DIM), "dangling edge must fail Inv3");
820
821 let mut desynced = two_node_graph();
822 desynced.nodes.insert(7, node(8, [0.0, 0.0]));
823 assert!(!desynced.ok(DIM), "key/id desync must fail Inv3");
824
825 let mut nonfinite = two_node_graph();
826 nonfinite.nodes.get_mut(&1).unwrap().embedding[0] = f64::NAN;
827 assert!(!nonfinite.ok(DIM), "NaN embedding must fail Inv3");
828 }
829
830 #[test]
831 fn ops_are_integrity_checked_before_mutating() {
832 let mut g = two_node_graph();
833 let before = g.clone();
834
835 assert!(matches!(
837 g.apply(
838 &GraphOp::AddNode {
839 id: 3,
840 ntype: NodeType::Action,
841 emb: vec![1.0, 2.0, 3.0],
842 ts: 3
843 },
844 DIM
845 ),
846 Err(GraphOpError::Dim { id: 3, got: 3, want: 2 })
847 ));
848 assert!(matches!(
850 g.apply(
851 &GraphOp::AddNode {
852 id: 4,
853 ntype: NodeType::Action,
854 emb: vec![f64::INFINITY, 0.0],
855 ts: 4
856 },
857 DIM
858 ),
859 Err(GraphOpError::NonFinite(4))
860 ));
861 assert!(matches!(
863 g.apply(
864 &GraphOp::AddEdge {
865 from: 1,
866 to: 42,
867 etype: EdgeType::Refines
868 },
869 DIM
870 ),
871 Err(GraphOpError::MissingNode(42))
872 ));
873 assert!(matches!(
875 g.apply(&GraphOp::RelabelNode { id: 42, emb: vec![0.0, 0.0] }, DIM),
876 Err(GraphOpError::MissingNode(42))
877 ));
878 assert!(matches!(
880 g.apply(&GraphOp::MergeNodes { keep: 1, merged: 1 }, DIM),
881 Err(GraphOpError::SelfMerge(1))
882 ));
883
884 assert_eq!(g, before, "a refused op must not mutate the graph");
885 }
886
887 #[test]
888 fn every_op_round_trips_through_its_undo_entry() {
889 let dim = DIM;
890 let ops = vec![
891 GraphOp::AddNode {
892 id: 3,
893 ntype: NodeType::Goal,
894 emb: vec![0.5, 0.5],
895 ts: 3,
896 },
897 GraphOp::DeleteNode { id: 2 },
898 GraphOp::AddEdge {
902 from: 1,
903 to: 2,
904 etype: EdgeType::TemporalNext,
905 },
906 GraphOp::DeleteEdge {
907 from: 1,
908 to: 2,
909 etype: EdgeType::CausallyPrecedes,
910 },
911 GraphOp::RelabelNode {
912 id: 1,
913 emb: vec![9.0, 9.0],
914 },
915 GraphOp::MergeNodes { keep: 1, merged: 2 },
916 ];
917
918 for op in ops {
919 let mut g = two_node_graph();
920 let before = g.clone();
921 let entry = g.apply(&op, dim).expect("op should apply");
922 g.undo(&entry);
923 assert!(
924 g.same_content(&before),
925 "undo of {op:?} did not restore (V, E, ℳ):\n got {:?}\n want {:?}",
926 g.nodes,
927 before.nodes
928 );
929 assert!(
930 g.next_id() >= before.next_id(),
931 "undo must never rewind the id counter"
932 );
933 }
934 }
935
936 #[test]
937 fn rollback_does_not_recycle_node_ids() {
938 let mut g = two_node_graph();
941 let id = g.next_id();
942 let entry = g
943 .apply(
944 &GraphOp::AddNode {
945 id,
946 ntype: NodeType::Observation,
947 emb: vec![0.0, 0.0],
948 ts: 0,
949 },
950 DIM,
951 )
952 .unwrap();
953 g.undo(&entry);
954 assert!(!g.nodes.contains_key(&id), "node must be gone after undo");
955 assert!(
956 g.next_id() > id,
957 "id {id} was recycled after rollback (next_id = {})",
958 g.next_id()
959 );
960 }
961
962 #[test]
963 fn merge_rewires_edges_and_ema_updates_the_survivor() {
964 let mut g = two_node_graph();
965 g.apply(
967 &GraphOp::AddNode {
968 id: 3,
969 ntype: NodeType::Action,
970 emb: vec![0.0, 0.0],
971 ts: 3,
972 },
973 DIM,
974 )
975 .unwrap();
976 g.apply(
977 &GraphOp::AddEdge {
978 from: 3,
979 to: 2,
980 etype: EdgeType::Refines,
981 },
982 DIM,
983 )
984 .unwrap();
985 let before = g.clone();
986
987 let entry = g.apply(&GraphOp::MergeNodes { keep: 1, merged: 2 }, DIM).unwrap();
988
989 assert!(!g.nodes.contains_key(&2), "merged node must be gone");
990 assert!(
991 g.edges.contains(&GraphEdge {
992 from: 3,
993 to: 1,
994 edge_type: EdgeType::Refines
995 }),
996 "edge 3→2 must be re-pointed to 3→1, got {:?}",
997 g.edges
998 );
999 assert!(
1000 !g.edges.iter().any(|e| e.from == 2 || e.to == 2),
1001 "no edge may reference the merged node"
1002 );
1003 assert!(
1004 !g.edges.iter().any(|e| e.from == e.to),
1005 "re-pointing must not create a self-loop"
1006 );
1007 let keep = &g.nodes[&1];
1009 assert!((keep.embedding[0] - 0.9).abs() < 1e-15);
1010 assert!((keep.embedding[1] - 0.1).abs() < 1e-15);
1011 assert_eq!(keep.timestamp, 2);
1012 assert!(g.ok(DIM), "merge must preserve Inv3");
1013
1014 g.undo(&entry);
1015 assert!(
1016 g.same_content(&before),
1017 "unmerge must restore both pre-images exactly"
1018 );
1019 }
1020
1021 #[test]
1022 fn ops_are_idempotent() {
1023 let mut g = two_node_graph();
1024 let add = GraphOp::AddNode {
1025 id: 1,
1026 ntype: NodeType::Observation,
1027 emb: vec![1.0, 0.0],
1028 ts: 1,
1029 };
1030 assert_eq!(g.apply(&add, DIM).unwrap(), UndoOp::Noop);
1031 let edge = GraphOp::AddEdge {
1032 from: 1,
1033 to: 2,
1034 etype: EdgeType::CausallyPrecedes,
1035 };
1036 assert_eq!(g.apply(&edge, DIM).unwrap(), UndoOp::Noop);
1037 assert_eq!(g.apply(&GraphOp::DeleteNode { id: 77 }, DIM).unwrap(), UndoOp::Noop);
1038 assert_eq!(
1039 g.apply(
1040 &GraphOp::DeleteEdge {
1041 from: 1,
1042 to: 2,
1043 etype: EdgeType::Refines
1044 },
1045 DIM
1046 )
1047 .unwrap(),
1048 UndoOp::Noop
1049 );
1050 assert_eq!(g.node_count(), 2);
1051 assert_eq!(g.edge_count(), 1);
1052 }
1053
1054 #[test]
1055 fn duplicate_id_with_different_content_is_refused() {
1056 let mut g = two_node_graph();
1057 assert!(matches!(
1058 g.apply(
1059 &GraphOp::AddNode {
1060 id: 1,
1061 ntype: NodeType::Goal,
1062 emb: vec![7.0, 7.0],
1063 ts: 9
1064 },
1065 DIM
1066 ),
1067 Err(GraphOpError::DuplicateNode(1))
1068 ));
1069 }
1070
1071 #[test]
1072 fn delete_node_takes_its_edges_and_restore_brings_them_back() {
1073 let mut g = two_node_graph();
1074 let before = g.clone();
1075 let entry = g.apply(&GraphOp::DeleteNode { id: 2 }, DIM).unwrap();
1076 assert_eq!(g.edge_count(), 0, "incident edges must go with the node");
1077 assert!(g.ok(DIM), "no dangling edge may survive a delete");
1078 g.undo(&entry);
1079 assert!(g.same_content(&before));
1080 }
1081
1082 #[test]
1083 fn batch_apply_is_all_or_nothing() {
1084 let mut g = two_node_graph();
1085 let before = g.clone();
1086 let err = g
1087 .apply_ops(
1088 &[
1089 GraphOp::AddNode {
1090 id: 5,
1091 ntype: NodeType::Action,
1092 emb: vec![0.1, 0.2],
1093 ts: 5,
1094 },
1095 GraphOp::AddEdge {
1096 from: 5,
1097 to: 1,
1098 etype: EdgeType::Refines,
1099 },
1100 GraphOp::AddNode {
1102 id: 6,
1103 ntype: NodeType::Action,
1104 emb: vec![0.0],
1105 ts: 6,
1106 },
1107 ],
1108 DIM,
1109 )
1110 .expect_err("batch must fail");
1111 assert!(matches!(err, GraphOpError::Dim { id: 6, .. }));
1112 assert!(
1113 g.same_content(&before),
1114 "a failed batch must roll back completely"
1115 );
1116
1117 let journal = g
1118 .apply_ops(
1119 &[
1120 GraphOp::AddNode {
1121 id: 5,
1122 ntype: NodeType::Action,
1123 emb: vec![0.1, 0.2],
1124 ts: 5,
1125 },
1126 GraphOp::AddEdge {
1127 from: 5,
1128 to: 1,
1129 etype: EdgeType::Refines,
1130 },
1131 ],
1132 DIM,
1133 )
1134 .expect("batch must apply");
1135 assert_eq!(g.size(), before.size() + 2);
1136 g.undo_ops(&journal);
1137 assert!(
1138 g.same_content(&before),
1139 "undo_ops must restore the pre-state"
1140 );
1141 }
1142
1143 #[test]
1144 fn ids_stay_monotone_and_are_never_reused() {
1145 let mut g = Graph::empty();
1146 assert_eq!(g.next_id(), 0);
1147 let id = g.next_id();
1148 g.apply(
1149 &GraphOp::AddNode {
1150 id,
1151 ntype: NodeType::Observation,
1152 emb: vec![0.0, 0.0],
1153 ts: 0,
1154 },
1155 DIM,
1156 )
1157 .unwrap();
1158 assert_eq!(g.next_id(), 1);
1159 g.apply(&GraphOp::DeleteNode { id }, DIM).unwrap();
1160 assert_eq!(g.next_id(), 1, "deleting must not recycle the id");
1161 }
1162
1163 #[test]
1164 fn acyclicity_detects_cycles_and_self_loops() {
1165 let g = two_node_graph();
1166 assert!(g.is_acyclic());
1167
1168 let mut cyclic = two_node_graph();
1169 cyclic
1170 .apply(
1171 &GraphOp::AddEdge {
1172 from: 2,
1173 to: 1,
1174 etype: EdgeType::CausallyPrecedes,
1175 },
1176 DIM,
1177 )
1178 .unwrap();
1179 assert!(!cyclic.is_acyclic());
1180
1181 let mut loopy = two_node_graph();
1182 loopy
1183 .apply(
1184 &GraphOp::AddEdge {
1185 from: 1,
1186 to: 1,
1187 etype: EdgeType::CausallyPrecedes,
1188 },
1189 DIM,
1190 )
1191 .unwrap();
1192 assert!(!loopy.is_acyclic());
1193 }
1194
1195 #[test]
1196 fn legacy_type_names_load_through_the_alias_table() {
1197 assert_eq!(NodeType::from_wire("latent"), NodeType::Observation);
1199 assert_eq!(EdgeType::from_wire("morph"), EdgeType::CausallyPrecedes);
1200 assert_eq!(
1202 NodeType::from_wire("market_segment"),
1203 NodeType::Custom("market_segment".into())
1204 );
1205
1206 let legacy = r#"{
1207 "nodes": { "0": { "id": 0, "embedding": [1.0, 0.0], "node_type": "latent", "timestamp": 3 } },
1208 "edges": [ { "from": 0, "to": 0, "edge_type": "morph" } ]
1209 }"#;
1210 let g: Graph = serde_json::from_str(legacy).expect("legacy graph must deserialize");
1211 assert_eq!(g.nodes[&0].node_type, NodeType::Observation);
1212 assert_eq!(
1213 g.edges.iter().next().unwrap().edge_type,
1214 EdgeType::CausallyPrecedes
1215 );
1216 }
1217
1218 #[test]
1219 fn serde_round_trips_and_is_stable() {
1220 let g = two_node_graph();
1221 let json = serde_json::to_string(&g).unwrap();
1222 let back: Graph = serde_json::from_str(&json).unwrap();
1223 assert_eq!(g, back);
1224 assert_eq!(json, serde_json::to_string(&back).unwrap());
1226 assert!(
1227 json.contains("\"observation\"") && json.contains("\"causally_precedes\""),
1228 "types must serialize as readable names: {json}"
1229 );
1230 }
1231
1232 #[test]
1233 fn iteration_order_is_deterministic_regardless_of_insertion_order() {
1234 let mut ascending = Graph::empty();
1238 for id in 0..32u64 {
1239 ascending
1240 .apply(
1241 &GraphOp::AddNode {
1242 id,
1243 ntype: NodeType::Observation,
1244 emb: vec![id as f64, 0.0],
1245 ts: id,
1246 },
1247 DIM,
1248 )
1249 .unwrap();
1250 }
1251 let mut descending = Graph::empty();
1252 for id in (0..32u64).rev() {
1253 descending
1254 .apply(
1255 &GraphOp::AddNode {
1256 id,
1257 ntype: NodeType::Observation,
1258 emb: vec![id as f64, 0.0],
1259 ts: id,
1260 },
1261 DIM,
1262 )
1263 .unwrap();
1264 }
1265 let a: Vec<NodeId> = ascending.nodes.keys().copied().collect();
1266 let d: Vec<NodeId> = descending.nodes.keys().copied().collect();
1267 assert_eq!(a, d, "iteration order must not depend on insertion order");
1268 assert_eq!(a, (0..32u64).collect::<Vec<_>>());
1269 }
1270}