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 } => self.apply_add_edge(*from, *to, etype.clone()),
485 GraphOp::DeleteEdge { from, to, etype } => {
486 Ok(self.apply_delete_edge(*from, *to, etype.clone()))
487 }
488 GraphOp::RelabelNode { id, emb } => self.apply_relabel_node(*id, emb, latent_dim),
489 GraphOp::MergeNodes { keep, merged } => self.apply_merge_nodes(*keep, *merged),
490 }
491 }
492
493 fn apply_add_node(
494 &mut self,
495 id: NodeId,
496 ntype: NodeType,
497 emb: &[f64],
498 ts: u64,
499 latent_dim: usize,
500 ) -> Result<UndoOp, GraphOpError> {
501 Self::check_embedding(id, emb, latent_dim)?;
502 let candidate = GraphNode {
503 id,
504 embedding: emb.to_vec(),
505 node_type: ntype,
506 timestamp: ts,
507 };
508 if let Some(existing) = self.nodes.get(&id) {
509 return if *existing == candidate {
512 Ok(UndoOp::Noop)
513 } else {
514 Err(GraphOpError::DuplicateNode(id))
515 };
516 }
517 self.nodes.insert(id, candidate);
518 self.next_id = self.next_id.max(id.saturating_add(1));
519 Ok(UndoOp::DropNode(id))
520 }
521
522 fn apply_delete_node(&mut self, id: NodeId) -> UndoOp {
523 let Some(node) = self.nodes.remove(&id) else {
524 return UndoOp::Noop;
525 };
526 let edges = self.incident(id);
527 for e in &edges {
528 self.edges.remove(e);
529 }
530 UndoOp::RestoreNode { node, edges }
531 }
532
533 fn apply_add_edge(
534 &mut self,
535 from: NodeId,
536 to: NodeId,
537 etype: EdgeType,
538 ) -> Result<UndoOp, GraphOpError> {
539 if !self.nodes.contains_key(&from) {
540 return Err(GraphOpError::MissingNode(from));
541 }
542 if !self.nodes.contains_key(&to) {
543 return Err(GraphOpError::MissingNode(to));
544 }
545 let edge = GraphEdge {
546 from,
547 to,
548 edge_type: etype,
549 };
550 if self.edges.contains(&edge) {
551 return Ok(UndoOp::Noop);
552 }
553 self.edges.insert(edge.clone());
554 Ok(UndoOp::DropEdge(edge))
555 }
556
557 fn apply_delete_edge(&mut self, from: NodeId, to: NodeId, etype: EdgeType) -> UndoOp {
558 let edge = GraphEdge {
559 from,
560 to,
561 edge_type: etype,
562 };
563 if self.edges.remove(&edge) {
564 UndoOp::RestoreEdge(edge)
565 } else {
566 UndoOp::Noop
567 }
568 }
569
570 fn apply_relabel_node(
571 &mut self,
572 id: NodeId,
573 emb: &[f64],
574 latent_dim: usize,
575 ) -> Result<UndoOp, GraphOpError> {
576 Self::check_embedding(id, emb, latent_dim)?;
577 let Some(node) = self.nodes.get_mut(&id) else {
578 return Err(GraphOpError::MissingNode(id));
579 };
580 if node.embedding == emb {
581 return Ok(UndoOp::Noop);
582 }
583 let previous = std::mem::replace(&mut node.embedding, emb.to_vec());
584 Ok(UndoOp::RestoreEmbedding { id, emb: previous })
585 }
586
587 fn apply_merge_nodes(&mut self, keep: NodeId, merged: NodeId) -> Result<UndoOp, GraphOpError> {
588 if keep == merged {
589 return Err(GraphOpError::SelfMerge(keep));
590 }
591 if !self.nodes.contains_key(&keep) {
592 return Err(GraphOpError::MissingNode(keep));
593 }
594 let Some(merged_node) = self.nodes.get(&merged).cloned() else {
595 return Err(GraphOpError::MissingNode(merged));
596 };
597
598 let merged_edges = self.incident(merged);
599 let keep_node = &self.nodes[&keep];
600 let keep_emb = keep_node.embedding.clone();
601 let keep_ts = keep_node.timestamp;
602
603 let mut rewired = Vec::new();
607 for e in &merged_edges {
608 self.edges.remove(e);
609 let moved = GraphEdge {
610 from: if e.from == merged { keep } else { e.from },
611 to: if e.to == merged { keep } else { e.to },
612 edge_type: e.edge_type.clone(),
613 };
614 if moved.from == moved.to {
615 continue;
616 }
617 if self.edges.insert(moved.clone()) {
618 rewired.push(moved);
619 }
620 }
621
622 let keep_node = self.nodes.get_mut(&keep).expect("checked above");
624 for (e, c) in keep_node
625 .embedding
626 .iter_mut()
627 .zip(merged_node.embedding.iter())
628 {
629 *e = MERGE_EMA_KEEP * *e + MERGE_EMA_NEW * *c;
630 }
631 keep_node.timestamp = merged_node.timestamp;
632 self.nodes.remove(&merged);
633
634 Ok(UndoOp::Unmerge {
635 merged: merged_node,
636 merged_edges,
637 keep,
638 keep_emb,
639 keep_ts,
640 rewired,
641 })
642 }
643
644 pub fn same_content(&self, other: &Graph) -> bool {
651 self.nodes == other.nodes && self.edges == other.edges
652 }
653
654 pub fn undo(&mut self, entry: &UndoOp) {
662 match entry {
663 UndoOp::Noop => {}
664 UndoOp::DropNode(id) => {
665 self.nodes.remove(id);
666 self.edges.retain(|e| e.from != *id && e.to != *id);
667 }
668 UndoOp::RestoreNode { node, edges } => {
669 self.nodes.insert(node.id, node.clone());
670 for e in edges {
671 self.edges.insert(e.clone());
672 }
673 }
674 UndoOp::DropEdge(edge) => {
675 self.edges.remove(edge);
676 }
677 UndoOp::RestoreEdge(edge) => {
678 self.edges.insert(edge.clone());
679 }
680 UndoOp::RestoreEmbedding { id, emb } => {
681 if let Some(node) = self.nodes.get_mut(id) {
682 node.embedding.clone_from(emb);
683 }
684 }
685 UndoOp::Unmerge {
686 merged,
687 merged_edges,
688 keep,
689 keep_emb,
690 keep_ts,
691 rewired,
692 } => {
693 for e in rewired {
694 self.edges.remove(e);
695 }
696 if let Some(node) = self.nodes.get_mut(keep) {
697 node.embedding.clone_from(keep_emb);
698 node.timestamp = *keep_ts;
699 }
700 self.nodes.insert(merged.id, merged.clone());
701 for e in merged_edges {
702 self.edges.insert(e.clone());
703 }
704 }
705 }
706 }
707
708 pub fn apply_ops(
711 &mut self,
712 ops: &[GraphOp],
713 latent_dim: usize,
714 ) -> Result<Vec<UndoOp>, GraphOpError> {
715 let mut journal = Vec::with_capacity(ops.len());
716 for op in ops {
717 match self.apply(op, latent_dim) {
718 Ok(entry) => journal.push(entry),
719 Err(e) => {
720 self.undo_ops(&journal);
721 return Err(e);
722 }
723 }
724 }
725 Ok(journal)
726 }
727
728 pub fn undo_ops(&mut self, journal: &[UndoOp]) {
730 for entry in journal.iter().rev() {
731 self.undo(entry);
732 }
733 }
734}
735
736impl Default for Graph {
737 fn default() -> Self {
738 Graph::empty()
739 }
740}
741
742#[cfg(test)]
743mod tests {
744 use super::*;
745
746 const DIM: usize = 2;
747
748 fn node(id: NodeId, emb: [f64; DIM]) -> GraphNode {
749 GraphNode {
750 id,
751 embedding: emb.to_vec(),
752 node_type: NodeType::Observation,
753 timestamp: id,
754 }
755 }
756
757 fn two_node_graph() -> Graph {
758 let mut g = Graph::empty();
759 g.apply(
760 &GraphOp::AddNode {
761 id: 1,
762 ntype: NodeType::Observation,
763 emb: vec![1.0, 0.0],
764 ts: 1,
765 },
766 DIM,
767 )
768 .unwrap();
769 g.apply(
770 &GraphOp::AddNode {
771 id: 2,
772 ntype: NodeType::Hypothesis,
773 emb: vec![0.0, 1.0],
774 ts: 2,
775 },
776 DIM,
777 )
778 .unwrap();
779 g.apply(
780 &GraphOp::AddEdge {
781 from: 1,
782 to: 2,
783 etype: EdgeType::CausallyPrecedes,
784 },
785 DIM,
786 )
787 .unwrap();
788 g
789 }
790
791 #[test]
792 fn graph_ok_accepts_a_well_formed_graph() {
793 let g = two_node_graph();
794 assert!(g.ok(DIM));
795 assert_eq!(g.node_count(), 2);
796 assert_eq!(g.edge_count(), 1);
797 assert_eq!(g.size(), 3);
798 }
799
800 #[test]
801 fn graph_ok_rejects_wrong_dimension_and_dangling_edges() {
802 let g = two_node_graph();
803 assert!(!g.ok(DIM + 1), "wrong latent_dim must fail Inv3");
804
805 let mut dangling = two_node_graph();
806 dangling.edges.insert(GraphEdge {
807 from: 1,
808 to: 999,
809 edge_type: EdgeType::Refines,
810 });
811 assert!(!dangling.ok(DIM), "dangling edge must fail Inv3");
812
813 let mut desynced = two_node_graph();
814 desynced.nodes.insert(7, node(8, [0.0, 0.0]));
815 assert!(!desynced.ok(DIM), "key/id desync must fail Inv3");
816
817 let mut nonfinite = two_node_graph();
818 nonfinite.nodes.get_mut(&1).unwrap().embedding[0] = f64::NAN;
819 assert!(!nonfinite.ok(DIM), "NaN embedding must fail Inv3");
820 }
821
822 #[test]
823 fn ops_are_integrity_checked_before_mutating() {
824 let mut g = two_node_graph();
825 let before = g.clone();
826
827 assert!(matches!(
829 g.apply(
830 &GraphOp::AddNode {
831 id: 3,
832 ntype: NodeType::Action,
833 emb: vec![1.0, 2.0, 3.0],
834 ts: 3
835 },
836 DIM
837 ),
838 Err(GraphOpError::Dim {
839 id: 3,
840 got: 3,
841 want: 2
842 })
843 ));
844 assert!(matches!(
846 g.apply(
847 &GraphOp::AddNode {
848 id: 4,
849 ntype: NodeType::Action,
850 emb: vec![f64::INFINITY, 0.0],
851 ts: 4
852 },
853 DIM
854 ),
855 Err(GraphOpError::NonFinite(4))
856 ));
857 assert!(matches!(
859 g.apply(
860 &GraphOp::AddEdge {
861 from: 1,
862 to: 42,
863 etype: EdgeType::Refines
864 },
865 DIM
866 ),
867 Err(GraphOpError::MissingNode(42))
868 ));
869 assert!(matches!(
871 g.apply(
872 &GraphOp::RelabelNode {
873 id: 42,
874 emb: vec![0.0, 0.0]
875 },
876 DIM
877 ),
878 Err(GraphOpError::MissingNode(42))
879 ));
880 assert!(matches!(
882 g.apply(&GraphOp::MergeNodes { keep: 1, merged: 1 }, DIM),
883 Err(GraphOpError::SelfMerge(1))
884 ));
885
886 assert_eq!(g, before, "a refused op must not mutate the graph");
887 }
888
889 #[test]
890 fn every_op_round_trips_through_its_undo_entry() {
891 let dim = DIM;
892 let ops = vec![
893 GraphOp::AddNode {
894 id: 3,
895 ntype: NodeType::Goal,
896 emb: vec![0.5, 0.5],
897 ts: 3,
898 },
899 GraphOp::DeleteNode { id: 2 },
900 GraphOp::AddEdge {
904 from: 1,
905 to: 2,
906 etype: EdgeType::TemporalNext,
907 },
908 GraphOp::DeleteEdge {
909 from: 1,
910 to: 2,
911 etype: EdgeType::CausallyPrecedes,
912 },
913 GraphOp::RelabelNode {
914 id: 1,
915 emb: vec![9.0, 9.0],
916 },
917 GraphOp::MergeNodes { keep: 1, merged: 2 },
918 ];
919
920 for op in ops {
921 let mut g = two_node_graph();
922 let before = g.clone();
923 let entry = g.apply(&op, dim).expect("op should apply");
924 g.undo(&entry);
925 assert!(
926 g.same_content(&before),
927 "undo of {op:?} did not restore (V, E, ℳ):\n got {:?}\n want {:?}",
928 g.nodes,
929 before.nodes
930 );
931 assert!(
932 g.next_id() >= before.next_id(),
933 "undo must never rewind the id counter"
934 );
935 }
936 }
937
938 #[test]
939 fn rollback_does_not_recycle_node_ids() {
940 let mut g = two_node_graph();
943 let id = g.next_id();
944 let entry = g
945 .apply(
946 &GraphOp::AddNode {
947 id,
948 ntype: NodeType::Observation,
949 emb: vec![0.0, 0.0],
950 ts: 0,
951 },
952 DIM,
953 )
954 .unwrap();
955 g.undo(&entry);
956 assert!(!g.nodes.contains_key(&id), "node must be gone after undo");
957 assert!(
958 g.next_id() > id,
959 "id {id} was recycled after rollback (next_id = {})",
960 g.next_id()
961 );
962 }
963
964 #[test]
965 fn merge_rewires_edges_and_ema_updates_the_survivor() {
966 let mut g = two_node_graph();
967 g.apply(
969 &GraphOp::AddNode {
970 id: 3,
971 ntype: NodeType::Action,
972 emb: vec![0.0, 0.0],
973 ts: 3,
974 },
975 DIM,
976 )
977 .unwrap();
978 g.apply(
979 &GraphOp::AddEdge {
980 from: 3,
981 to: 2,
982 etype: EdgeType::Refines,
983 },
984 DIM,
985 )
986 .unwrap();
987 let before = g.clone();
988
989 let entry = g
990 .apply(&GraphOp::MergeNodes { keep: 1, merged: 2 }, DIM)
991 .unwrap();
992
993 assert!(!g.nodes.contains_key(&2), "merged node must be gone");
994 assert!(
995 g.edges.contains(&GraphEdge {
996 from: 3,
997 to: 1,
998 edge_type: EdgeType::Refines
999 }),
1000 "edge 3→2 must be re-pointed to 3→1, got {:?}",
1001 g.edges
1002 );
1003 assert!(
1004 !g.edges.iter().any(|e| e.from == 2 || e.to == 2),
1005 "no edge may reference the merged node"
1006 );
1007 assert!(
1008 !g.edges.iter().any(|e| e.from == e.to),
1009 "re-pointing must not create a self-loop"
1010 );
1011 let keep = &g.nodes[&1];
1013 assert!((keep.embedding[0] - 0.9).abs() < 1e-15);
1014 assert!((keep.embedding[1] - 0.1).abs() < 1e-15);
1015 assert_eq!(keep.timestamp, 2);
1016 assert!(g.ok(DIM), "merge must preserve Inv3");
1017
1018 g.undo(&entry);
1019 assert!(
1020 g.same_content(&before),
1021 "unmerge must restore both pre-images exactly"
1022 );
1023 }
1024
1025 #[test]
1026 fn ops_are_idempotent() {
1027 let mut g = two_node_graph();
1028 let add = GraphOp::AddNode {
1029 id: 1,
1030 ntype: NodeType::Observation,
1031 emb: vec![1.0, 0.0],
1032 ts: 1,
1033 };
1034 assert_eq!(g.apply(&add, DIM).unwrap(), UndoOp::Noop);
1035 let edge = GraphOp::AddEdge {
1036 from: 1,
1037 to: 2,
1038 etype: EdgeType::CausallyPrecedes,
1039 };
1040 assert_eq!(g.apply(&edge, DIM).unwrap(), UndoOp::Noop);
1041 assert_eq!(
1042 g.apply(&GraphOp::DeleteNode { id: 77 }, DIM).unwrap(),
1043 UndoOp::Noop
1044 );
1045 assert_eq!(
1046 g.apply(
1047 &GraphOp::DeleteEdge {
1048 from: 1,
1049 to: 2,
1050 etype: EdgeType::Refines
1051 },
1052 DIM
1053 )
1054 .unwrap(),
1055 UndoOp::Noop
1056 );
1057 assert_eq!(g.node_count(), 2);
1058 assert_eq!(g.edge_count(), 1);
1059 }
1060
1061 #[test]
1062 fn duplicate_id_with_different_content_is_refused() {
1063 let mut g = two_node_graph();
1064 assert!(matches!(
1065 g.apply(
1066 &GraphOp::AddNode {
1067 id: 1,
1068 ntype: NodeType::Goal,
1069 emb: vec![7.0, 7.0],
1070 ts: 9
1071 },
1072 DIM
1073 ),
1074 Err(GraphOpError::DuplicateNode(1))
1075 ));
1076 }
1077
1078 #[test]
1079 fn delete_node_takes_its_edges_and_restore_brings_them_back() {
1080 let mut g = two_node_graph();
1081 let before = g.clone();
1082 let entry = g.apply(&GraphOp::DeleteNode { id: 2 }, DIM).unwrap();
1083 assert_eq!(g.edge_count(), 0, "incident edges must go with the node");
1084 assert!(g.ok(DIM), "no dangling edge may survive a delete");
1085 g.undo(&entry);
1086 assert!(g.same_content(&before));
1087 }
1088
1089 #[test]
1090 fn batch_apply_is_all_or_nothing() {
1091 let mut g = two_node_graph();
1092 let before = g.clone();
1093 let err = g
1094 .apply_ops(
1095 &[
1096 GraphOp::AddNode {
1097 id: 5,
1098 ntype: NodeType::Action,
1099 emb: vec![0.1, 0.2],
1100 ts: 5,
1101 },
1102 GraphOp::AddEdge {
1103 from: 5,
1104 to: 1,
1105 etype: EdgeType::Refines,
1106 },
1107 GraphOp::AddNode {
1109 id: 6,
1110 ntype: NodeType::Action,
1111 emb: vec![0.0],
1112 ts: 6,
1113 },
1114 ],
1115 DIM,
1116 )
1117 .expect_err("batch must fail");
1118 assert!(matches!(err, GraphOpError::Dim { id: 6, .. }));
1119 assert!(
1120 g.same_content(&before),
1121 "a failed batch must roll back completely"
1122 );
1123
1124 let journal = g
1125 .apply_ops(
1126 &[
1127 GraphOp::AddNode {
1128 id: 5,
1129 ntype: NodeType::Action,
1130 emb: vec![0.1, 0.2],
1131 ts: 5,
1132 },
1133 GraphOp::AddEdge {
1134 from: 5,
1135 to: 1,
1136 etype: EdgeType::Refines,
1137 },
1138 ],
1139 DIM,
1140 )
1141 .expect("batch must apply");
1142 assert_eq!(g.size(), before.size() + 2);
1143 g.undo_ops(&journal);
1144 assert!(
1145 g.same_content(&before),
1146 "undo_ops must restore the pre-state"
1147 );
1148 }
1149
1150 #[test]
1151 fn ids_stay_monotone_and_are_never_reused() {
1152 let mut g = Graph::empty();
1153 assert_eq!(g.next_id(), 0);
1154 let id = g.next_id();
1155 g.apply(
1156 &GraphOp::AddNode {
1157 id,
1158 ntype: NodeType::Observation,
1159 emb: vec![0.0, 0.0],
1160 ts: 0,
1161 },
1162 DIM,
1163 )
1164 .unwrap();
1165 assert_eq!(g.next_id(), 1);
1166 g.apply(&GraphOp::DeleteNode { id }, DIM).unwrap();
1167 assert_eq!(g.next_id(), 1, "deleting must not recycle the id");
1168 }
1169
1170 #[test]
1171 fn acyclicity_detects_cycles_and_self_loops() {
1172 let g = two_node_graph();
1173 assert!(g.is_acyclic());
1174
1175 let mut cyclic = two_node_graph();
1176 cyclic
1177 .apply(
1178 &GraphOp::AddEdge {
1179 from: 2,
1180 to: 1,
1181 etype: EdgeType::CausallyPrecedes,
1182 },
1183 DIM,
1184 )
1185 .unwrap();
1186 assert!(!cyclic.is_acyclic());
1187
1188 let mut loopy = two_node_graph();
1189 loopy
1190 .apply(
1191 &GraphOp::AddEdge {
1192 from: 1,
1193 to: 1,
1194 etype: EdgeType::CausallyPrecedes,
1195 },
1196 DIM,
1197 )
1198 .unwrap();
1199 assert!(!loopy.is_acyclic());
1200 }
1201
1202 #[test]
1203 fn legacy_type_names_load_through_the_alias_table() {
1204 assert_eq!(NodeType::from_wire("latent"), NodeType::Observation);
1206 assert_eq!(EdgeType::from_wire("morph"), EdgeType::CausallyPrecedes);
1207 assert_eq!(
1209 NodeType::from_wire("market_segment"),
1210 NodeType::Custom("market_segment".into())
1211 );
1212
1213 let legacy = r#"{
1214 "nodes": { "0": { "id": 0, "embedding": [1.0, 0.0], "node_type": "latent", "timestamp": 3 } },
1215 "edges": [ { "from": 0, "to": 0, "edge_type": "morph" } ]
1216 }"#;
1217 let g: Graph = serde_json::from_str(legacy).expect("legacy graph must deserialize");
1218 assert_eq!(g.nodes[&0].node_type, NodeType::Observation);
1219 assert_eq!(
1220 g.edges.iter().next().unwrap().edge_type,
1221 EdgeType::CausallyPrecedes
1222 );
1223 }
1224
1225 #[test]
1226 fn serde_round_trips_and_is_stable() {
1227 let g = two_node_graph();
1228 let json = serde_json::to_string(&g).unwrap();
1229 let back: Graph = serde_json::from_str(&json).unwrap();
1230 assert_eq!(g, back);
1231 assert_eq!(json, serde_json::to_string(&back).unwrap());
1233 assert!(
1234 json.contains("\"observation\"") && json.contains("\"causally_precedes\""),
1235 "types must serialize as readable names: {json}"
1236 );
1237 }
1238
1239 #[test]
1240 fn iteration_order_is_deterministic_regardless_of_insertion_order() {
1241 let mut ascending = Graph::empty();
1245 for id in 0..32u64 {
1246 ascending
1247 .apply(
1248 &GraphOp::AddNode {
1249 id,
1250 ntype: NodeType::Observation,
1251 emb: vec![id as f64, 0.0],
1252 ts: id,
1253 },
1254 DIM,
1255 )
1256 .unwrap();
1257 }
1258 let mut descending = Graph::empty();
1259 for id in (0..32u64).rev() {
1260 descending
1261 .apply(
1262 &GraphOp::AddNode {
1263 id,
1264 ntype: NodeType::Observation,
1265 emb: vec![id as f64, 0.0],
1266 ts: id,
1267 },
1268 DIM,
1269 )
1270 .unwrap();
1271 }
1272 let a: Vec<NodeId> = ascending.nodes.keys().copied().collect();
1273 let d: Vec<NodeId> = descending.nodes.keys().copied().collect();
1274 assert_eq!(a, d, "iteration order must not depend on insertion order");
1275 assert_eq!(a, (0..32u64).collect::<Vec<_>>());
1276 }
1277}