use serde::de::{self, Deserializer, Visitor};
use serde::{Deserialize, Serialize, Serializer};
use std::collections::{BTreeMap, BTreeSet};
use std::fmt;
pub type NodeId = u64;
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub enum NodeType {
#[default]
Observation,
Hypothesis,
Action,
Goal,
InvariantCheckpoint,
Custom(String),
}
impl NodeType {
pub fn as_str(&self) -> &str {
match self {
NodeType::Observation => "observation",
NodeType::Hypothesis => "hypothesis",
NodeType::Action => "action",
NodeType::Goal => "goal",
NodeType::InvariantCheckpoint => "invariant_checkpoint",
NodeType::Custom(s) => s,
}
}
pub fn from_wire(s: &str) -> Self {
match s {
"latent" | "observation" => NodeType::Observation,
"hypothesis" => NodeType::Hypothesis,
"action" => NodeType::Action,
"goal" => NodeType::Goal,
"invariant_checkpoint" => NodeType::InvariantCheckpoint,
other => NodeType::Custom(other.to_string()),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub enum EdgeType {
#[default]
CausallyPrecedes,
Contradicts,
Refines,
TemporalNext,
Custom(String),
}
impl EdgeType {
pub fn as_str(&self) -> &str {
match self {
EdgeType::CausallyPrecedes => "causally_precedes",
EdgeType::Contradicts => "contradicts",
EdgeType::Refines => "refines",
EdgeType::TemporalNext => "temporal_next",
EdgeType::Custom(s) => s,
}
}
pub fn from_wire(s: &str) -> Self {
match s {
"morph" | "causally_precedes" => EdgeType::CausallyPrecedes,
"contradicts" => EdgeType::Contradicts,
"refines" => EdgeType::Refines,
"temporal_next" => EdgeType::TemporalNext,
other => EdgeType::Custom(other.to_string()),
}
}
}
macro_rules! string_serde {
($t:ty, $expecting:literal) => {
impl Serialize for $t {
fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
s.serialize_str(self.as_str())
}
}
impl<'de> Deserialize<'de> for $t {
fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
struct V;
impl Visitor<'_> for V {
type Value = $t;
fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str($expecting)
}
fn visit_str<E: de::Error>(self, v: &str) -> Result<$t, E> {
Ok(<$t>::from_wire(v))
}
}
d.deserialize_str(V)
}
}
};
}
string_serde!(NodeType, "a node type name");
string_serde!(EdgeType, "an edge type name");
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct GraphNode {
pub id: NodeId,
pub embedding: Vec<f64>,
#[serde(default)]
pub node_type: NodeType,
#[serde(default)]
pub timestamp: u64,
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct GraphEdge {
pub from: NodeId,
pub to: NodeId,
pub edge_type: EdgeType,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct Graph {
pub nodes: BTreeMap<NodeId, GraphNode>,
pub edges: BTreeSet<GraphEdge>,
#[serde(default)]
next_id: NodeId,
}
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum GraphOpError {
#[error("graph op references missing node {0}")]
MissingNode(NodeId),
#[error("node {0} already exists with different content")]
DuplicateNode(NodeId),
#[error("node {id}: embedding has dim {got}, expected {want}")]
Dim {
id: NodeId,
got: usize,
want: usize,
},
#[error("node {0}: embedding contains a non-finite component")]
NonFinite(NodeId),
#[error("MergeNodes requires distinct nodes, got {0} twice")]
SelfMerge(NodeId),
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum GraphOp {
AddNode {
id: NodeId,
ntype: NodeType,
emb: Vec<f64>,
ts: u64,
},
DeleteNode {
id: NodeId,
},
AddEdge {
from: NodeId,
to: NodeId,
etype: EdgeType,
},
DeleteEdge {
from: NodeId,
to: NodeId,
etype: EdgeType,
},
RelabelNode {
id: NodeId,
emb: Vec<f64>,
},
MergeNodes {
keep: NodeId,
merged: NodeId,
},
}
#[derive(Debug, Clone, PartialEq)]
pub enum UndoOp {
DropNode(NodeId),
RestoreNode {
node: GraphNode,
edges: Vec<GraphEdge>,
},
DropEdge(GraphEdge),
RestoreEdge(GraphEdge),
RestoreEmbedding {
id: NodeId,
emb: Vec<f64>,
},
Unmerge {
merged: GraphNode,
merged_edges: Vec<GraphEdge>,
keep: NodeId,
keep_emb: Vec<f64>,
keep_ts: u64,
rewired: Vec<GraphEdge>,
},
Noop,
}
const MERGE_EMA_KEEP: f64 = 0.9;
const MERGE_EMA_NEW: f64 = 0.1;
impl Graph {
pub fn empty() -> Self {
Graph {
nodes: BTreeMap::new(),
edges: BTreeSet::new(),
next_id: 0,
}
}
pub fn seed(node: GraphNode) -> Self {
let mut g = Graph::empty();
g.next_id = node.id + 1;
g.nodes.insert(node.id, node);
g
}
pub fn node_count(&self) -> usize {
self.nodes.len()
}
pub fn edge_count(&self) -> usize {
self.edges.len()
}
pub fn size(&self) -> usize {
self.node_count() + self.edge_count()
}
pub fn next_id(&self) -> NodeId {
self.next_id
}
pub fn node(&self, id: NodeId) -> Option<&GraphNode> {
self.nodes.get(&id)
}
pub fn get_embedding(&self, id: NodeId) -> Option<&Vec<f64>> {
self.nodes.get(&id).map(|n| &n.embedding)
}
pub fn incident(&self, id: NodeId) -> Vec<GraphEdge> {
self.edges
.iter()
.filter(|e| e.from == id || e.to == id)
.cloned()
.collect()
}
pub fn ok(&self, latent_dim: usize) -> bool {
for edge in &self.edges {
if !self.nodes.contains_key(&edge.from) || !self.nodes.contains_key(&edge.to) {
return false;
}
}
for (id, node) in &self.nodes {
if *id != node.id
|| node.embedding.len() != latent_dim
|| !node.embedding.iter().all(|v| v.is_finite())
{
return false;
}
}
true
}
pub fn is_acyclic(&self) -> bool {
let mut indegree: BTreeMap<NodeId, usize> = self.nodes.keys().map(|&k| (k, 0)).collect();
let mut out: BTreeMap<NodeId, Vec<NodeId>> = BTreeMap::new();
for e in &self.edges {
if !self.nodes.contains_key(&e.from) {
continue;
}
if let Some(d) = indegree.get_mut(&e.to) {
*d += 1;
out.entry(e.from).or_default().push(e.to);
}
}
let mut queue: Vec<NodeId> = indegree
.iter()
.filter(|(_, &d)| d == 0)
.map(|(&k, _)| k)
.collect();
let mut visited = 0usize;
while let Some(n) = queue.pop() {
visited += 1;
for &m in out.get(&n).into_iter().flatten() {
if let Some(d) = indegree.get_mut(&m) {
*d -= 1;
if *d == 0 {
queue.push(m);
}
}
}
}
visited == self.nodes.len()
}
fn check_embedding(id: NodeId, emb: &[f64], latent_dim: usize) -> Result<(), GraphOpError> {
if emb.len() != latent_dim {
return Err(GraphOpError::Dim {
id,
got: emb.len(),
want: latent_dim,
});
}
if !emb.iter().all(|v| v.is_finite()) {
return Err(GraphOpError::NonFinite(id));
}
Ok(())
}
pub fn apply(&mut self, op: &GraphOp, latent_dim: usize) -> Result<UndoOp, GraphOpError> {
match op {
GraphOp::AddNode { id, ntype, emb, ts } => {
self.apply_add_node(*id, ntype.clone(), emb, *ts, latent_dim)
}
GraphOp::DeleteNode { id } => Ok(self.apply_delete_node(*id)),
GraphOp::AddEdge { from, to, etype } => self.apply_add_edge(*from, *to, etype.clone()),
GraphOp::DeleteEdge { from, to, etype } => {
Ok(self.apply_delete_edge(*from, *to, etype.clone()))
}
GraphOp::RelabelNode { id, emb } => self.apply_relabel_node(*id, emb, latent_dim),
GraphOp::MergeNodes { keep, merged } => self.apply_merge_nodes(*keep, *merged),
}
}
fn apply_add_node(
&mut self,
id: NodeId,
ntype: NodeType,
emb: &[f64],
ts: u64,
latent_dim: usize,
) -> Result<UndoOp, GraphOpError> {
Self::check_embedding(id, emb, latent_dim)?;
let candidate = GraphNode {
id,
embedding: emb.to_vec(),
node_type: ntype,
timestamp: ts,
};
if let Some(existing) = self.nodes.get(&id) {
return if *existing == candidate {
Ok(UndoOp::Noop)
} else {
Err(GraphOpError::DuplicateNode(id))
};
}
self.nodes.insert(id, candidate);
self.next_id = self.next_id.max(id.saturating_add(1));
Ok(UndoOp::DropNode(id))
}
fn apply_delete_node(&mut self, id: NodeId) -> UndoOp {
let Some(node) = self.nodes.remove(&id) else {
return UndoOp::Noop;
};
let edges = self.incident(id);
for e in &edges {
self.edges.remove(e);
}
UndoOp::RestoreNode { node, edges }
}
fn apply_add_edge(
&mut self,
from: NodeId,
to: NodeId,
etype: EdgeType,
) -> Result<UndoOp, GraphOpError> {
if !self.nodes.contains_key(&from) {
return Err(GraphOpError::MissingNode(from));
}
if !self.nodes.contains_key(&to) {
return Err(GraphOpError::MissingNode(to));
}
let edge = GraphEdge {
from,
to,
edge_type: etype,
};
if self.edges.contains(&edge) {
return Ok(UndoOp::Noop);
}
self.edges.insert(edge.clone());
Ok(UndoOp::DropEdge(edge))
}
fn apply_delete_edge(&mut self, from: NodeId, to: NodeId, etype: EdgeType) -> UndoOp {
let edge = GraphEdge {
from,
to,
edge_type: etype,
};
if self.edges.remove(&edge) {
UndoOp::RestoreEdge(edge)
} else {
UndoOp::Noop
}
}
fn apply_relabel_node(
&mut self,
id: NodeId,
emb: &[f64],
latent_dim: usize,
) -> Result<UndoOp, GraphOpError> {
Self::check_embedding(id, emb, latent_dim)?;
let Some(node) = self.nodes.get_mut(&id) else {
return Err(GraphOpError::MissingNode(id));
};
if node.embedding == emb {
return Ok(UndoOp::Noop);
}
let previous = std::mem::replace(&mut node.embedding, emb.to_vec());
Ok(UndoOp::RestoreEmbedding { id, emb: previous })
}
fn apply_merge_nodes(&mut self, keep: NodeId, merged: NodeId) -> Result<UndoOp, GraphOpError> {
if keep == merged {
return Err(GraphOpError::SelfMerge(keep));
}
if !self.nodes.contains_key(&keep) {
return Err(GraphOpError::MissingNode(keep));
}
let Some(merged_node) = self.nodes.get(&merged).cloned() else {
return Err(GraphOpError::MissingNode(merged));
};
let merged_edges = self.incident(merged);
let keep_node = &self.nodes[&keep];
let keep_emb = keep_node.embedding.clone();
let keep_ts = keep_node.timestamp;
let mut rewired = Vec::new();
for e in &merged_edges {
self.edges.remove(e);
let moved = GraphEdge {
from: if e.from == merged { keep } else { e.from },
to: if e.to == merged { keep } else { e.to },
edge_type: e.edge_type.clone(),
};
if moved.from == moved.to {
continue;
}
if self.edges.insert(moved.clone()) {
rewired.push(moved);
}
}
let keep_node = self.nodes.get_mut(&keep).expect("checked above");
for (e, c) in keep_node
.embedding
.iter_mut()
.zip(merged_node.embedding.iter())
{
*e = MERGE_EMA_KEEP * *e + MERGE_EMA_NEW * *c;
}
keep_node.timestamp = merged_node.timestamp;
self.nodes.remove(&merged);
Ok(UndoOp::Unmerge {
merged: merged_node,
merged_edges,
keep,
keep_emb,
keep_ts,
rewired,
})
}
pub fn same_content(&self, other: &Graph) -> bool {
self.nodes == other.nodes && self.edges == other.edges
}
pub fn undo(&mut self, entry: &UndoOp) {
match entry {
UndoOp::Noop => {}
UndoOp::DropNode(id) => {
self.nodes.remove(id);
self.edges.retain(|e| e.from != *id && e.to != *id);
}
UndoOp::RestoreNode { node, edges } => {
self.nodes.insert(node.id, node.clone());
for e in edges {
self.edges.insert(e.clone());
}
}
UndoOp::DropEdge(edge) => {
self.edges.remove(edge);
}
UndoOp::RestoreEdge(edge) => {
self.edges.insert(edge.clone());
}
UndoOp::RestoreEmbedding { id, emb } => {
if let Some(node) = self.nodes.get_mut(id) {
node.embedding.clone_from(emb);
}
}
UndoOp::Unmerge {
merged,
merged_edges,
keep,
keep_emb,
keep_ts,
rewired,
} => {
for e in rewired {
self.edges.remove(e);
}
if let Some(node) = self.nodes.get_mut(keep) {
node.embedding.clone_from(keep_emb);
node.timestamp = *keep_ts;
}
self.nodes.insert(merged.id, merged.clone());
for e in merged_edges {
self.edges.insert(e.clone());
}
}
}
}
pub fn apply_ops(
&mut self,
ops: &[GraphOp],
latent_dim: usize,
) -> Result<Vec<UndoOp>, GraphOpError> {
let mut journal = Vec::with_capacity(ops.len());
for op in ops {
match self.apply(op, latent_dim) {
Ok(entry) => journal.push(entry),
Err(e) => {
self.undo_ops(&journal);
return Err(e);
}
}
}
Ok(journal)
}
pub fn undo_ops(&mut self, journal: &[UndoOp]) {
for entry in journal.iter().rev() {
self.undo(entry);
}
}
}
impl Default for Graph {
fn default() -> Self {
Graph::empty()
}
}
#[cfg(test)]
mod tests {
use super::*;
const DIM: usize = 2;
fn node(id: NodeId, emb: [f64; DIM]) -> GraphNode {
GraphNode {
id,
embedding: emb.to_vec(),
node_type: NodeType::Observation,
timestamp: id,
}
}
fn two_node_graph() -> Graph {
let mut g = Graph::empty();
g.apply(
&GraphOp::AddNode {
id: 1,
ntype: NodeType::Observation,
emb: vec![1.0, 0.0],
ts: 1,
},
DIM,
)
.unwrap();
g.apply(
&GraphOp::AddNode {
id: 2,
ntype: NodeType::Hypothesis,
emb: vec![0.0, 1.0],
ts: 2,
},
DIM,
)
.unwrap();
g.apply(
&GraphOp::AddEdge {
from: 1,
to: 2,
etype: EdgeType::CausallyPrecedes,
},
DIM,
)
.unwrap();
g
}
#[test]
fn graph_ok_accepts_a_well_formed_graph() {
let g = two_node_graph();
assert!(g.ok(DIM));
assert_eq!(g.node_count(), 2);
assert_eq!(g.edge_count(), 1);
assert_eq!(g.size(), 3);
}
#[test]
fn graph_ok_rejects_wrong_dimension_and_dangling_edges() {
let g = two_node_graph();
assert!(!g.ok(DIM + 1), "wrong latent_dim must fail Inv3");
let mut dangling = two_node_graph();
dangling.edges.insert(GraphEdge {
from: 1,
to: 999,
edge_type: EdgeType::Refines,
});
assert!(!dangling.ok(DIM), "dangling edge must fail Inv3");
let mut desynced = two_node_graph();
desynced.nodes.insert(7, node(8, [0.0, 0.0]));
assert!(!desynced.ok(DIM), "key/id desync must fail Inv3");
let mut nonfinite = two_node_graph();
nonfinite.nodes.get_mut(&1).unwrap().embedding[0] = f64::NAN;
assert!(!nonfinite.ok(DIM), "NaN embedding must fail Inv3");
}
#[test]
fn ops_are_integrity_checked_before_mutating() {
let mut g = two_node_graph();
let before = g.clone();
assert!(matches!(
g.apply(
&GraphOp::AddNode {
id: 3,
ntype: NodeType::Action,
emb: vec![1.0, 2.0, 3.0],
ts: 3
},
DIM
),
Err(GraphOpError::Dim {
id: 3,
got: 3,
want: 2
})
));
assert!(matches!(
g.apply(
&GraphOp::AddNode {
id: 4,
ntype: NodeType::Action,
emb: vec![f64::INFINITY, 0.0],
ts: 4
},
DIM
),
Err(GraphOpError::NonFinite(4))
));
assert!(matches!(
g.apply(
&GraphOp::AddEdge {
from: 1,
to: 42,
etype: EdgeType::Refines
},
DIM
),
Err(GraphOpError::MissingNode(42))
));
assert!(matches!(
g.apply(
&GraphOp::RelabelNode {
id: 42,
emb: vec![0.0, 0.0]
},
DIM
),
Err(GraphOpError::MissingNode(42))
));
assert!(matches!(
g.apply(&GraphOp::MergeNodes { keep: 1, merged: 1 }, DIM),
Err(GraphOpError::SelfMerge(1))
));
assert_eq!(g, before, "a refused op must not mutate the graph");
}
#[test]
fn every_op_round_trips_through_its_undo_entry() {
let dim = DIM;
let ops = vec![
GraphOp::AddNode {
id: 3,
ntype: NodeType::Goal,
emb: vec![0.5, 0.5],
ts: 3,
},
GraphOp::DeleteNode { id: 2 },
GraphOp::AddEdge {
from: 1,
to: 2,
etype: EdgeType::TemporalNext,
},
GraphOp::DeleteEdge {
from: 1,
to: 2,
etype: EdgeType::CausallyPrecedes,
},
GraphOp::RelabelNode {
id: 1,
emb: vec![9.0, 9.0],
},
GraphOp::MergeNodes { keep: 1, merged: 2 },
];
for op in ops {
let mut g = two_node_graph();
let before = g.clone();
let entry = g.apply(&op, dim).expect("op should apply");
g.undo(&entry);
assert!(
g.same_content(&before),
"undo of {op:?} did not restore (V, E, ℳ):\n got {:?}\n want {:?}",
g.nodes,
before.nodes
);
assert!(
g.next_id() >= before.next_id(),
"undo must never rewind the id counter"
);
}
}
#[test]
fn rollback_does_not_recycle_node_ids() {
let mut g = two_node_graph();
let id = g.next_id();
let entry = g
.apply(
&GraphOp::AddNode {
id,
ntype: NodeType::Observation,
emb: vec![0.0, 0.0],
ts: 0,
},
DIM,
)
.unwrap();
g.undo(&entry);
assert!(!g.nodes.contains_key(&id), "node must be gone after undo");
assert!(
g.next_id() > id,
"id {id} was recycled after rollback (next_id = {})",
g.next_id()
);
}
#[test]
fn merge_rewires_edges_and_ema_updates_the_survivor() {
let mut g = two_node_graph();
g.apply(
&GraphOp::AddNode {
id: 3,
ntype: NodeType::Action,
emb: vec![0.0, 0.0],
ts: 3,
},
DIM,
)
.unwrap();
g.apply(
&GraphOp::AddEdge {
from: 3,
to: 2,
etype: EdgeType::Refines,
},
DIM,
)
.unwrap();
let before = g.clone();
let entry = g
.apply(&GraphOp::MergeNodes { keep: 1, merged: 2 }, DIM)
.unwrap();
assert!(!g.nodes.contains_key(&2), "merged node must be gone");
assert!(
g.edges.contains(&GraphEdge {
from: 3,
to: 1,
edge_type: EdgeType::Refines
}),
"edge 3→2 must be re-pointed to 3→1, got {:?}",
g.edges
);
assert!(
!g.edges.iter().any(|e| e.from == 2 || e.to == 2),
"no edge may reference the merged node"
);
assert!(
!g.edges.iter().any(|e| e.from == e.to),
"re-pointing must not create a self-loop"
);
let keep = &g.nodes[&1];
assert!((keep.embedding[0] - 0.9).abs() < 1e-15);
assert!((keep.embedding[1] - 0.1).abs() < 1e-15);
assert_eq!(keep.timestamp, 2);
assert!(g.ok(DIM), "merge must preserve Inv3");
g.undo(&entry);
assert!(
g.same_content(&before),
"unmerge must restore both pre-images exactly"
);
}
#[test]
fn ops_are_idempotent() {
let mut g = two_node_graph();
let add = GraphOp::AddNode {
id: 1,
ntype: NodeType::Observation,
emb: vec![1.0, 0.0],
ts: 1,
};
assert_eq!(g.apply(&add, DIM).unwrap(), UndoOp::Noop);
let edge = GraphOp::AddEdge {
from: 1,
to: 2,
etype: EdgeType::CausallyPrecedes,
};
assert_eq!(g.apply(&edge, DIM).unwrap(), UndoOp::Noop);
assert_eq!(
g.apply(&GraphOp::DeleteNode { id: 77 }, DIM).unwrap(),
UndoOp::Noop
);
assert_eq!(
g.apply(
&GraphOp::DeleteEdge {
from: 1,
to: 2,
etype: EdgeType::Refines
},
DIM
)
.unwrap(),
UndoOp::Noop
);
assert_eq!(g.node_count(), 2);
assert_eq!(g.edge_count(), 1);
}
#[test]
fn duplicate_id_with_different_content_is_refused() {
let mut g = two_node_graph();
assert!(matches!(
g.apply(
&GraphOp::AddNode {
id: 1,
ntype: NodeType::Goal,
emb: vec![7.0, 7.0],
ts: 9
},
DIM
),
Err(GraphOpError::DuplicateNode(1))
));
}
#[test]
fn delete_node_takes_its_edges_and_restore_brings_them_back() {
let mut g = two_node_graph();
let before = g.clone();
let entry = g.apply(&GraphOp::DeleteNode { id: 2 }, DIM).unwrap();
assert_eq!(g.edge_count(), 0, "incident edges must go with the node");
assert!(g.ok(DIM), "no dangling edge may survive a delete");
g.undo(&entry);
assert!(g.same_content(&before));
}
#[test]
fn batch_apply_is_all_or_nothing() {
let mut g = two_node_graph();
let before = g.clone();
let err = g
.apply_ops(
&[
GraphOp::AddNode {
id: 5,
ntype: NodeType::Action,
emb: vec![0.1, 0.2],
ts: 5,
},
GraphOp::AddEdge {
from: 5,
to: 1,
etype: EdgeType::Refines,
},
GraphOp::AddNode {
id: 6,
ntype: NodeType::Action,
emb: vec![0.0],
ts: 6,
},
],
DIM,
)
.expect_err("batch must fail");
assert!(matches!(err, GraphOpError::Dim { id: 6, .. }));
assert!(
g.same_content(&before),
"a failed batch must roll back completely"
);
let journal = g
.apply_ops(
&[
GraphOp::AddNode {
id: 5,
ntype: NodeType::Action,
emb: vec![0.1, 0.2],
ts: 5,
},
GraphOp::AddEdge {
from: 5,
to: 1,
etype: EdgeType::Refines,
},
],
DIM,
)
.expect("batch must apply");
assert_eq!(g.size(), before.size() + 2);
g.undo_ops(&journal);
assert!(
g.same_content(&before),
"undo_ops must restore the pre-state"
);
}
#[test]
fn ids_stay_monotone_and_are_never_reused() {
let mut g = Graph::empty();
assert_eq!(g.next_id(), 0);
let id = g.next_id();
g.apply(
&GraphOp::AddNode {
id,
ntype: NodeType::Observation,
emb: vec![0.0, 0.0],
ts: 0,
},
DIM,
)
.unwrap();
assert_eq!(g.next_id(), 1);
g.apply(&GraphOp::DeleteNode { id }, DIM).unwrap();
assert_eq!(g.next_id(), 1, "deleting must not recycle the id");
}
#[test]
fn acyclicity_detects_cycles_and_self_loops() {
let g = two_node_graph();
assert!(g.is_acyclic());
let mut cyclic = two_node_graph();
cyclic
.apply(
&GraphOp::AddEdge {
from: 2,
to: 1,
etype: EdgeType::CausallyPrecedes,
},
DIM,
)
.unwrap();
assert!(!cyclic.is_acyclic());
let mut loopy = two_node_graph();
loopy
.apply(
&GraphOp::AddEdge {
from: 1,
to: 1,
etype: EdgeType::CausallyPrecedes,
},
DIM,
)
.unwrap();
assert!(!loopy.is_acyclic());
}
#[test]
fn legacy_type_names_load_through_the_alias_table() {
assert_eq!(NodeType::from_wire("latent"), NodeType::Observation);
assert_eq!(EdgeType::from_wire("morph"), EdgeType::CausallyPrecedes);
assert_eq!(
NodeType::from_wire("market_segment"),
NodeType::Custom("market_segment".into())
);
let legacy = r#"{
"nodes": { "0": { "id": 0, "embedding": [1.0, 0.0], "node_type": "latent", "timestamp": 3 } },
"edges": [ { "from": 0, "to": 0, "edge_type": "morph" } ]
}"#;
let g: Graph = serde_json::from_str(legacy).expect("legacy graph must deserialize");
assert_eq!(g.nodes[&0].node_type, NodeType::Observation);
assert_eq!(
g.edges.iter().next().unwrap().edge_type,
EdgeType::CausallyPrecedes
);
}
#[test]
fn serde_round_trips_and_is_stable() {
let g = two_node_graph();
let json = serde_json::to_string(&g).unwrap();
let back: Graph = serde_json::from_str(&json).unwrap();
assert_eq!(g, back);
assert_eq!(json, serde_json::to_string(&back).unwrap());
assert!(
json.contains("\"observation\"") && json.contains("\"causally_precedes\""),
"types must serialize as readable names: {json}"
);
}
#[test]
fn iteration_order_is_deterministic_regardless_of_insertion_order() {
let mut ascending = Graph::empty();
for id in 0..32u64 {
ascending
.apply(
&GraphOp::AddNode {
id,
ntype: NodeType::Observation,
emb: vec![id as f64, 0.0],
ts: id,
},
DIM,
)
.unwrap();
}
let mut descending = Graph::empty();
for id in (0..32u64).rev() {
descending
.apply(
&GraphOp::AddNode {
id,
ntype: NodeType::Observation,
emb: vec![id as f64, 0.0],
ts: id,
},
DIM,
)
.unwrap();
}
let a: Vec<NodeId> = ascending.nodes.keys().copied().collect();
let d: Vec<NodeId> = descending.nodes.keys().copied().collect();
assert_eq!(a, d, "iteration order must not depend on insertion order");
assert_eq!(a, (0..32u64).collect::<Vec<_>>());
}
}