Skip to main content

ison_graph/
lib.rs

1//! ISONGraph - A Token-Efficient Graph Store for Rust
2//!
3//! A property graph implementation with ISON persistence.
4//! Supports multi-hop traversal, path finding, and fluent API.
5//!
6//! # Example
7//!
8//! ```rust
9//! use ison_graph::{ISONGraph, NodeRef, Direction, props};
10//!
11//! let mut graph = ISONGraph::new("social");
12//! // Properties keep their type: 30 is a number, "30" would be a string,
13//! // and the two serialize differently.
14//! graph.add_node("person", "1", props![("name", "Alice"), ("age", 30i64)]).unwrap();
15//! graph.add_node("person", "2", props![("name", "Bob"), ("age", 25i64)]).unwrap();
16//! graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![("since", 2020i64)]).unwrap();
17//!
18//! let friends = graph.neighbors(&("person", "1"), Some("KNOWS"), Direction::Out);
19//! let fof = graph.multi_hop(&("person", "1"), Some("KNOWS"), 2, Direction::Out);
20//! ```
21
22use std::collections::{HashMap, HashSet, VecDeque};
23use std::fs;
24use std::path::Path as StdPath;
25use std::sync::OnceLock;
26use ison_rs::{
27    dumps_canonical, dumps_canonical_isonl, loads, loads_isonl,
28    Block as IsonBlock, Document as IsonDocument, Reference as IsonReference,
29};
30
31/// Converts a Rust primitive into an ISON property value.
32///
33/// `ison_rs::Value` has no `From` impls and the orphan rule stops this crate
34/// adding them, so the conversions live here. This is sugar only - the value
35/// stored is always `ison_rs::Value`, never a parallel model.
36pub trait IntoValue {
37    fn into_value(self) -> Value;
38}
39
40impl IntoValue for Value {
41    fn into_value(self) -> Value { self }
42}
43impl IntoValue for &str {
44    fn into_value(self) -> Value { Value::String(self.to_string()) }
45}
46impl IntoValue for String {
47    fn into_value(self) -> Value { Value::String(self) }
48}
49impl IntoValue for i64 {
50    fn into_value(self) -> Value { Value::Int(self) }
51}
52impl IntoValue for i32 {
53    fn into_value(self) -> Value { Value::Int(self as i64) }
54}
55impl IntoValue for f64 {
56    fn into_value(self) -> Value { Value::Float(self) }
57}
58impl IntoValue for bool {
59    fn into_value(self) -> Value { Value::Bool(self) }
60}
61
62/// Build a property list with mixed value types.
63///
64/// A `Vec` is homogeneous, so a literal mixing an int and a string cannot be
65/// written directly; this converts each value before collecting, which is
66/// what makes `props![("staff", 42), ("name", "Acme")]` compile.
67#[macro_export]
68macro_rules! props {
69    () => { ::std::vec::Vec::<(&str, $crate::Value)>::new() };
70    ($(($k:expr, $v:expr)),* $(,)?) => {
71        ::std::vec![$(($k, $crate::IntoValue::into_value($v))),*]
72    };
73}
74
75/// Render a property value as text - the form every value had before
76/// properties carried types. Query string operators and schema validation
77/// use it so their behaviour is unchanged by typing the storage.
78pub fn value_to_text(value: &Value) -> String {
79    match value {
80        Value::Null => String::new(),
81        Value::Bool(b) => b.to_string(),
82        Value::Int(i) => i.to_string(),
83        Value::Float(f) => f.to_string(),
84        Value::String(s) => s.clone(),
85        Value::Reference(r) => r.to_ison(),
86    }
87}
88
89/// Property values are ISON values, re-exported so callers do not need a
90/// direct ison-rs dependency. Storing anything else would mean a second
91/// value model beside the parser's, which is what made this port emit every
92/// value as a quoted string and disagree with the typed ports.
93pub use ison_rs::Value;
94use ison_rs::Value as IsonValue;
95use thiserror::Error;
96use regex::Regex;
97
98#[cfg(feature = "serde")]
99use serde::{Deserialize, Serialize};
100
101/// Version of the library
102pub const VERSION: &str = env!("CARGO_PKG_VERSION");
103
104// Query module (ISONQL)
105pub mod query;
106
107// Schema validation module
108pub mod schema;
109
110// =============================================================================
111// Types
112// =============================================================================
113
114/// Node reference: (type, id)
115pub type NodeRef<'a> = (&'a str, &'a str);
116
117/// Owned node reference
118#[derive(Debug, Clone, PartialEq, Eq, Hash)]
119#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
120pub struct NodeId {
121    pub node_type: String,
122    pub id: String,
123}
124
125impl NodeId {
126    pub fn new(node_type: impl Into<String>, id: impl Into<String>) -> Self {
127        Self {
128            node_type: node_type.into(),
129            id: id.into(),
130        }
131    }
132
133    pub fn as_ref(&self) -> NodeRef<'_> {
134        (&self.node_type, &self.id)
135    }
136
137    pub fn to_key(&self) -> String {
138        format!("{}:{}", self.node_type, self.id)
139    }
140
141    pub fn to_ison_ref(&self) -> String {
142        format!(":{}:{}", self.node_type, self.id)
143    }
144}
145
146impl From<(&str, &str)> for NodeId {
147    fn from(tuple: (&str, &str)) -> Self {
148        NodeId::new(tuple.0, tuple.1)
149    }
150}
151
152/// Traversal direction
153#[derive(Debug, Clone, Copy, PartialEq, Eq)]
154#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
155pub enum Direction {
156    Out,
157    In,
158    Both,
159}
160
161// =============================================================================
162// Data Structures
163// =============================================================================
164
165/// Represents a graph node with properties
166#[derive(Debug, Clone)]
167#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
168pub struct Node {
169    pub node_type: String,
170    pub id: String,
171    pub properties: HashMap<String, Value>,
172}
173
174impl Node {
175    pub fn new(node_type: impl Into<String>, id: impl Into<String>) -> Self {
176        Self {
177            node_type: node_type.into(),
178            id: id.into(),
179            properties: HashMap::new(),
180        }
181    }
182
183    pub fn with_properties(mut self, props: Vec<(&str, Value)>) -> Self {
184        for (k, v) in props {
185            self.properties.insert(k.to_string(), v);
186        }
187        self
188    }
189
190    pub fn node_id(&self) -> NodeId {
191        NodeId::new(&self.node_type, &self.id)
192    }
193
194    pub fn to_key(&self) -> String {
195        format!("{}:{}", self.node_type, self.id)
196    }
197}
198
199/// Represents a graph edge with properties
200#[derive(Debug, Clone)]
201#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
202pub struct Edge {
203    pub rel_type: String,
204    pub source: NodeId,
205    pub target: NodeId,
206    pub properties: HashMap<String, Value>,
207}
208
209impl Edge {
210    pub fn new(rel_type: impl Into<String>, source: NodeId, target: NodeId) -> Self {
211        Self {
212            rel_type: rel_type.into(),
213            source,
214            target,
215            properties: HashMap::new(),
216        }
217    }
218
219    pub fn with_properties(mut self, props: Vec<(&str, Value)>) -> Self {
220        for (k, v) in props {
221            self.properties.insert(k.to_string(), v);
222        }
223        self
224    }
225
226    pub fn to_key(&self) -> String {
227        format!(
228            "{}:{}:{}",
229            self.rel_type,
230            self.source.to_key(),
231            self.target.to_key()
232        )
233    }
234}
235
236/// Represents a path through the graph
237#[derive(Debug, Clone)]
238#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
239pub struct Path {
240    pub nodes: Vec<NodeId>,
241    pub edges: Vec<Edge>,
242}
243
244impl Path {
245    pub fn new(nodes: Vec<NodeId>, edges: Vec<Edge>) -> Self {
246        Self { nodes, edges }
247    }
248
249    /// Number of hops in the path
250    pub fn length(&self) -> usize {
251        self.edges.len()
252    }
253
254    /// Starting node
255    pub fn start(&self) -> Option<&NodeId> {
256        self.nodes.first()
257    }
258
259    /// Ending node
260    pub fn end(&self) -> Option<&NodeId> {
261        self.nodes.last()
262    }
263}
264
265// =============================================================================
266// Errors
267// =============================================================================
268
269#[derive(Error, Debug)]
270pub enum GraphError {
271    #[error("Node not found: :{0}:{1}")]
272    NodeNotFound(String, String),
273
274    #[error("Edge not found: {0} -> {1}")]
275    EdgeNotFound(String, String),
276
277    #[error("Duplicate node: :{0}:{1}")]
278    DuplicateNode(String, String),
279
280    #[error("Duplicate edge: {0}")]
281    DuplicateEdge(String),
282
283    #[error("Parse error: {0}")]
284    ParseError(String),
285
286    #[error("{0}")]
287    InvalidIdentifier(String),
288
289    #[error("I/O error: {0}")]
290    Io(#[from] std::io::Error),
291}
292
293pub type Result<T> = std::result::Result<T, GraphError>;
294
295// =============================================================================
296// ISONGraph - Main Graph Structure
297// =============================================================================
298
299/// In-memory property graph store with ISON persistence.
300///
301/// Features:
302/// - Property graph model (nodes and edges with properties)
303/// - Multiple node types and relationship types
304/// - O(1) node lookup by (type, id)
305/// - Multi-hop traversal
306/// - Shortest path finding (BFS)
307/// - All paths finding (DFS)
308/// - ISON/ISONL persistence
309#[derive(Debug)]
310#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
311#[cfg_attr(feature = "serde", serde(try_from = "GraphData"))]
312pub struct ISONGraph {
313    /// Graph name
314    pub name: String,
315
316    /// Whether edges are directed
317    pub directed: bool,
318
319    /// Node storage: type -> id -> Node
320    nodes: HashMap<String, HashMap<String, Node>>,
321
322    /// Edge storage: rel_type -> Vec<Edge>
323    edges: HashMap<String, Vec<Edge>>,
324
325    /// Index: outgoing edges per node (node_key -> edges).
326    /// Derived from `edges`; not serialized, rebuilt on deserialization.
327    #[cfg_attr(feature = "serde", serde(skip))]
328    out_edges: HashMap<String, Vec<Edge>>,
329
330    /// Index: incoming edges per node (node_key -> edges).
331    /// Derived from `edges`; not serialized, rebuilt on deserialization.
332    #[cfg_attr(feature = "serde", serde(skip))]
333    in_edges: HashMap<String, Vec<Edge>>,
334
335    /// Edge uniqueness set.
336    /// Derived from `edges`; not serialized, rebuilt on deserialization.
337    #[cfg_attr(feature = "serde", serde(skip))]
338    edge_set: HashSet<String>,
339}
340
341/// Serde shadow struct: the persisted form of [`ISONGraph`] without the
342/// derived indexes. Indexes are rebuilt after deserialization.
343#[cfg(feature = "serde")]
344#[derive(Deserialize)]
345struct GraphData {
346    name: String,
347    directed: bool,
348    nodes: HashMap<String, HashMap<String, Node>>,
349    edges: HashMap<String, Vec<Edge>>,
350}
351
352#[cfg(feature = "serde")]
353impl TryFrom<GraphData> for ISONGraph {
354    type Error = GraphError;
355
356    /// Deserialization bypasses `add_node`/`add_edge` (it reconstructs the
357    /// index maps directly from untrusted JSON), so the ':' / '|'
358    /// identifier guard has to be re-applied here explicitly - otherwise a
359    /// crafted or corrupted payload could smuggle in identifiers that
360    /// `add_node`/`add_edge` would have rejected, and the graph would only
361    /// fail later, confusingly, on to_ison()/to_isonl().
362    fn try_from(data: GraphData) -> Result<Self> {
363        for (node_type, type_nodes) in &data.nodes {
364            ISONGraph::check_identifier("Node type", node_type)?;
365            for node_id in type_nodes.keys() {
366                ISONGraph::check_identifier("Node id", node_id)?;
367            }
368        }
369        for (rel_type, edges) in &data.edges {
370            ISONGraph::check_identifier("Relationship type", rel_type)?;
371            for edge in edges {
372                ISONGraph::check_identifier("Node type", &edge.source.node_type)?;
373                ISONGraph::check_identifier("Node id", &edge.source.id)?;
374                ISONGraph::check_identifier("Node type", &edge.target.node_type)?;
375                ISONGraph::check_identifier("Node id", &edge.target.id)?;
376            }
377        }
378
379        let mut graph = ISONGraph {
380            name: data.name,
381            directed: data.directed,
382            nodes: data.nodes,
383            edges: data.edges,
384            out_edges: HashMap::new(),
385            in_edges: HashMap::new(),
386            edge_set: HashSet::new(),
387        };
388        graph.rebuild_indexes();
389        Ok(graph)
390    }
391}
392
393impl Default for ISONGraph {
394    fn default() -> Self {
395        Self::new("graph")
396    }
397}
398
399impl ISONGraph {
400    /// Create a new graph
401    pub fn new(name: impl Into<String>) -> Self {
402        Self {
403            name: name.into(),
404            directed: true,
405            nodes: HashMap::new(),
406            edges: HashMap::new(),
407            out_edges: HashMap::new(),
408            in_edges: HashMap::new(),
409            edge_set: HashSet::new(),
410        }
411    }
412
413    /// Create an undirected graph
414    pub fn undirected(name: impl Into<String>) -> Self {
415        let mut graph = Self::new(name);
416        graph.directed = false;
417        graph
418    }
419
420    /// Rebuild the derived indexes (`out_edges`, `in_edges`, `edge_set`)
421    /// from the canonical `edges` storage.
422    #[cfg(feature = "serde")]
423    fn rebuild_indexes(&mut self) {
424        self.out_edges.clear();
425        self.in_edges.clear();
426        self.edge_set.clear();
427
428        for edges in self.edges.values() {
429            for edge in edges {
430                let edge_key = edge.to_key();
431                if !self.edge_set.insert(edge_key) {
432                    continue;
433                }
434                self.out_edges
435                    .entry(edge.source.to_key())
436                    .or_default()
437                    .push(edge.clone());
438                self.in_edges
439                    .entry(edge.target.to_key())
440                    .or_default()
441                    .push(edge.clone());
442            }
443        }
444    }
445
446    // =========================================================================
447    // Node Operations
448    // =========================================================================
449
450    /// Add a node to the graph.
451    ///
452    /// Node keys are formed as `type:id`, so neither the type nor the id may
453    /// contain `':'` (it would make keys ambiguous).
454    /// Reject ':' or '|' in a node type, node id, or relationship type. Both
455    /// are structurally significant to the wire format (':' delimits
456    /// `:type:id` references, '|' delimits ISONL columns); allowing them
457    /// here would build a graph that fails on to_ison()/to_isonl()
458    /// round-trip instead of at construction.
459    fn check_identifier(kind: &str, value: &str) -> Result<()> {
460        // Types become block names, which ISONL additionally cannot quote;
461        // ids only have to survive a reference, which has no quoting at all.
462        let is_type = kind.to_lowercase().contains("type");
463        let bad = value.is_empty()
464            || value.chars().any(|ch| {
465                ch.is_whitespace()
466                    || ch == ':'
467                    || ch == '|'
468                    || (is_type && (ch == '"' || ch == '\\'))
469            });
470        if bad {
471            return Err(GraphError::InvalidIdentifier(format!(
472                "{} {:?} is not representable: it must not be empty or contain \
473                 whitespace, ':' or '|'{}",
474                kind,
475                value,
476                if is_type { ", '\"' or '\\'" } else { "" }
477            )));
478        }
479        Ok(())
480    }
481
482    /// Reject property names that cannot survive a serialization round trip.
483    ///
484    /// Property names become ISON field names, and the format quotes values
485    /// but not names: a space splits the field in two, ':' has the remainder
486    /// eaten as a type annotation, '.' is a dot path, and a leading '#' turns
487    /// the header into a comment and loses the whole block.
488    fn check_property_names<'a, I>(kind: &str, names: I) -> Result<()>
489    where
490        I: IntoIterator<Item = &'a str>,
491    {
492        for name in names {
493            let bad = name.is_empty()
494                || name.starts_with('#')
495                || name.chars().any(|ch| {
496                    ch.is_whitespace()
497                        || ch == ':'
498                        || ch == '|'
499                        || ch == '"'
500                        || ch == '\\'
501                        || ch == '.'
502                });
503            if bad {
504                return Err(GraphError::InvalidIdentifier(format!(
505                    "{} name {:?} cannot be encoded: property names must not be \
506                     empty, start with '#', or contain whitespace, ':', '|', \
507                     '\"', '\\' or '.'",
508                    kind, name
509                )));
510            }
511        }
512        Ok(())
513    }
514
515    pub fn add_node(
516        &mut self,
517        node_type: &str,
518        node_id: &str,
519        properties: Vec<(&str, Value)>,
520    ) -> Result<&Node> {
521        Self::check_identifier("Node type", node_type)?;
522        Self::check_identifier("Node id", node_id)?;
523        Self::check_property_names("Node property", properties.iter().map(|(k, _)| *k))?;
524
525        let type_nodes = self.nodes.entry(node_type.to_string()).or_default();
526
527        if type_nodes.contains_key(node_id) {
528            return Err(GraphError::DuplicateNode(
529                node_type.to_string(),
530                node_id.to_string(),
531            ));
532        }
533
534        let node = Node::new(node_type, node_id).with_properties(properties);
535        type_nodes.insert(node_id.to_string(), node);
536        Ok(type_nodes.get(node_id).unwrap())
537    }
538
539    /// Get a node by type and ID
540    pub fn get_node(&self, node_type: &str, node_id: &str) -> Result<&Node> {
541        self.nodes
542            .get(node_type)
543            .and_then(|m| m.get(node_id))
544            .ok_or_else(|| GraphError::NodeNotFound(node_type.to_string(), node_id.to_string()))
545    }
546
547    /// Get a node by NodeId
548    pub fn get_node_by_id(&self, node_id: &NodeId) -> Result<&Node> {
549        self.get_node(&node_id.node_type, &node_id.id)
550    }
551
552    /// Check if node exists
553    pub fn has_node(&self, node_type: &str, node_id: &str) -> bool {
554        self.nodes
555            .get(node_type)
556            .map(|m| m.contains_key(node_id))
557            .unwrap_or(false)
558    }
559
560    /// Remove a node and all its edges
561    pub fn remove_node(&mut self, node_type: &str, node_id: &str) -> Result<()> {
562        if !self.has_node(node_type, node_id) {
563            return Err(GraphError::NodeNotFound(
564                node_type.to_string(),
565                node_id.to_string(),
566            ));
567        }
568
569        let node_key = format!("{}:{}", node_type, node_id);
570
571        // Collect edges to remove
572        let out_edges: Vec<Edge> = self.out_edges.get(&node_key).cloned().unwrap_or_default();
573        let in_edges: Vec<Edge> = self.in_edges.get(&node_key).cloned().unwrap_or_default();
574
575        for edge in out_edges.iter().chain(in_edges.iter()) {
576            self.remove_edge_internal(edge);
577        }
578
579        // Remove node
580        if let Some(type_nodes) = self.nodes.get_mut(node_type) {
581            type_nodes.remove(node_id);
582            if type_nodes.is_empty() {
583                self.nodes.remove(node_type);
584            }
585        }
586
587        Ok(())
588    }
589
590    /// Update node properties
591    pub fn update_node(
592        &mut self,
593        node_type: &str,
594        node_id: &str,
595        properties: Vec<(&str, Value)>,
596    ) -> Result<()> {
597        let node = self
598            .nodes
599            .get_mut(node_type)
600            .and_then(|m| m.get_mut(node_id))
601            .ok_or_else(|| GraphError::NodeNotFound(node_type.to_string(), node_id.to_string()))?;
602
603        for (k, v) in properties {
604            node.properties.insert(k.to_string(), v);
605        }
606        Ok(())
607    }
608
609    /// Iterate over all nodes
610    pub fn nodes(&self) -> impl Iterator<Item = &Node> {
611        self.nodes.values().flat_map(|m| m.values())
612    }
613
614    /// Iterate over nodes of a specific type
615    pub fn nodes_of_type(&self, node_type: &str) -> impl Iterator<Item = &Node> {
616        self.nodes
617            .get(node_type)
618            .into_iter()
619            .flat_map(|m| m.values())
620    }
621
622    /// Count all nodes
623    pub fn node_count(&self) -> usize {
624        self.nodes.values().map(|m| m.len()).sum()
625    }
626
627    /// Count nodes of a specific type
628    pub fn node_count_of_type(&self, node_type: &str) -> usize {
629        self.nodes.get(node_type).map(|m| m.len()).unwrap_or(0)
630    }
631
632    /// Get all node types
633    pub fn node_types(&self) -> Vec<&String> {
634        self.nodes.keys().collect()
635    }
636
637    // =========================================================================
638    // Edge Operations
639    // =========================================================================
640
641    /// Add an edge to the graph
642    pub fn add_edge(
643        &mut self,
644        rel_type: &str,
645        source: (&str, &str),
646        target: (&str, &str),
647        properties: Vec<(&str, Value)>,
648    ) -> Result<()> {
649        Self::check_identifier("Relationship type", rel_type)?;
650        Self::check_property_names("Edge property", properties.iter().map(|(k, _)| *k))?;
651
652        // Validate nodes exist
653        if !self.has_node(source.0, source.1) {
654            return Err(GraphError::NodeNotFound(
655                source.0.to_string(),
656                source.1.to_string(),
657            ));
658        }
659        if !self.has_node(target.0, target.1) {
660            return Err(GraphError::NodeNotFound(
661                target.0.to_string(),
662                target.1.to_string(),
663            ));
664        }
665
666        let source_id = NodeId::new(source.0, source.1);
667        let target_id = NodeId::new(target.0, target.1);
668        let edge = Edge::new(rel_type, source_id.clone(), target_id.clone()).with_properties(properties.clone());
669        let edge_key = edge.to_key();
670
671        if self.edge_set.contains(&edge_key) {
672            return Err(GraphError::DuplicateEdge(edge_key));
673        }
674
675        // Add to storage
676        self.edges
677            .entry(rel_type.to_string())
678            .or_default()
679            .push(edge.clone());
680
681        let source_key = source_id.to_key();
682        let target_key = target_id.to_key();
683
684        self.out_edges
685            .entry(source_key.clone())
686            .or_default()
687            .push(edge.clone());
688        self.in_edges
689            .entry(target_key.clone())
690            .or_default()
691            .push(edge.clone());
692
693        self.edge_set.insert(edge_key);
694
695        // For undirected graphs, add reverse edge
696        if !self.directed {
697            let reverse_edge = Edge::new(rel_type, target_id.clone(), source_id.clone())
698                .with_properties(properties);
699            let reverse_key = reverse_edge.to_key();
700
701            if !self.edge_set.contains(&reverse_key) {
702                self.edges
703                    .entry(rel_type.to_string())
704                    .or_default()
705                    .push(reverse_edge.clone());
706                self.out_edges
707                    .entry(target_key)
708                    .or_default()
709                    .push(reverse_edge.clone());
710                self.in_edges
711                    .entry(source_key)
712                    .or_default()
713                    .push(reverse_edge);
714                self.edge_set.insert(reverse_key);
715            }
716        }
717
718        Ok(())
719    }
720
721    fn remove_edge_internal(&mut self, edge: &Edge) {
722        let edge_key = edge.to_key();
723        if !self.edge_set.contains(&edge_key) {
724            return;
725        }
726
727        self.edge_set.remove(&edge_key);
728
729        // Remove from edges
730        if let Some(rel_edges) = self.edges.get_mut(&edge.rel_type) {
731            rel_edges.retain(|e| e.to_key() != edge_key);
732        }
733
734        // Remove from out_edges
735        let source_key = edge.source.to_key();
736        if let Some(out) = self.out_edges.get_mut(&source_key) {
737            out.retain(|e| e.to_key() != edge_key);
738        }
739
740        // Remove from in_edges
741        let target_key = edge.target.to_key();
742        if let Some(in_e) = self.in_edges.get_mut(&target_key) {
743            in_e.retain(|e| e.to_key() != edge_key);
744        }
745    }
746
747    /// Remove an edge
748    pub fn remove_edge(
749        &mut self,
750        rel_type: &str,
751        source: (&str, &str),
752        target: (&str, &str),
753    ) -> Result<()> {
754        let source_id = NodeId::new(source.0, source.1);
755        let target_id = NodeId::new(target.0, target.1);
756        let edge = Edge::new(rel_type, source_id, target_id);
757        let edge_key = edge.to_key();
758
759        if !self.edge_set.contains(&edge_key) {
760            return Err(GraphError::EdgeNotFound(
761                format!("{}:{}", source.0, source.1),
762                format!("{}:{}", target.0, target.1),
763            ));
764        }
765
766        self.remove_edge_internal(&edge);
767        Ok(())
768    }
769
770    /// Check if edge exists
771    pub fn has_edge(&self, rel_type: &str, source: (&str, &str), target: (&str, &str)) -> bool {
772        let source_id = NodeId::new(source.0, source.1);
773        let target_id = NodeId::new(target.0, target.1);
774        let edge = Edge::new(rel_type, source_id, target_id);
775        self.edge_set.contains(&edge.to_key())
776    }
777
778    /// Count all edges
779    pub fn edge_count(&self) -> usize {
780        self.edge_set.len()
781    }
782
783    /// Count edges of a specific type
784    pub fn edge_count_of_type(&self, rel_type: &str) -> usize {
785        self.edges.get(rel_type).map(|v| v.len()).unwrap_or(0)
786    }
787
788    /// Get all edge types
789    pub fn edge_types(&self) -> Vec<&String> {
790        self.edges.keys().collect()
791    }
792
793    /// Get all edges of a specific type
794    pub fn edges_of_type(&self, rel_type: &str) -> impl Iterator<Item = &Edge> {
795        self.edges.get(rel_type).into_iter().flatten()
796    }
797
798    /// Check if the graph has a cycle for edges of a specific type
799    pub fn has_cycle(&self, rel_type: Option<&str>) -> bool {
800        // Iterative DFS-based cycle detection
801        let mut visited = HashSet::new();
802
803        for node_types in self.nodes.values() {
804            for node in node_types.values() {
805                let node_key = format!("{}:{}", node.node_type, node.id);
806                if !visited.contains(&node_key)
807                    && self.has_cycle_from(&node_key, &mut visited, rel_type)
808                {
809                    return true;
810                }
811            }
812        }
813        false
814    }
815
816    /// Outgoing `(target_key, rel_type)` pairs for cycle detection.
817    ///
818    /// For undirected graphs, the single auto-reverse of the edge used to
819    /// enter this node (`skip`) is excluded, so a lone undirected edge does
820    /// not read as a cycle. Only one matching reverse edge is skipped:
821    /// a genuine parallel edge back to the parent still counts.
822    fn cycle_successors(
823        &self,
824        node_key: &str,
825        rel_type: Option<&str>,
826        skip: Option<(&str, &str)>,
827    ) -> Vec<(String, String)> {
828        let mut result = Vec::new();
829        let mut skip_remaining = if self.directed { None } else { skip };
830
831        if let Some(edges) = self.out_edges.get(node_key) {
832            for edge in edges {
833                if rel_type.is_some() && rel_type != Some(edge.rel_type.as_str()) {
834                    continue;
835                }
836                let target_key = edge.target.to_key();
837                if let Some((skip_rel, skip_key)) = skip_remaining {
838                    if edge.rel_type == skip_rel && target_key == skip_key {
839                        skip_remaining = None;
840                        continue;
841                    }
842                }
843                result.push((target_key, edge.rel_type.clone()));
844            }
845        }
846        result
847    }
848
849    fn has_cycle_from(
850        &self,
851        start_key: &str,
852        visited: &mut HashSet<String>,
853        rel_type: Option<&str>,
854    ) -> bool {
855        struct Frame {
856            key: String,
857            successors: Vec<(String, String)>,
858            idx: usize,
859        }
860
861        let mut rec_stack: HashSet<String> = HashSet::new();
862        visited.insert(start_key.to_string());
863        rec_stack.insert(start_key.to_string());
864
865        let mut stack = vec![Frame {
866            key: start_key.to_string(),
867            successors: self.cycle_successors(start_key, rel_type, None),
868            idx: 0,
869        }];
870
871        while !stack.is_empty() {
872            let next = {
873                let frame = stack.last_mut().unwrap();
874                if frame.idx < frame.successors.len() {
875                    let (target_key, edge_rel) = frame.successors[frame.idx].clone();
876                    frame.idx += 1;
877                    Some((target_key, edge_rel, frame.key.clone()))
878                } else {
879                    None
880                }
881            };
882
883            match next {
884                Some((target_key, edge_rel, from_key)) => {
885                    if !visited.contains(&target_key) {
886                        visited.insert(target_key.clone());
887                        rec_stack.insert(target_key.clone());
888                        let successors =
889                            self.cycle_successors(&target_key, rel_type, Some((&edge_rel, &from_key)));
890                        stack.push(Frame {
891                            key: target_key,
892                            successors,
893                            idx: 0,
894                        });
895                    } else if rec_stack.contains(&target_key) {
896                        return true;
897                    }
898                }
899                None => {
900                    let frame = stack.pop().unwrap();
901                    rec_stack.remove(&frame.key);
902                }
903            }
904        }
905
906        false
907    }
908
909    // =========================================================================
910    // Traversal Operations
911    // =========================================================================
912
913    /// Get neighboring nodes.
914    ///
915    /// Results are deduplicated while preserving first-occurrence order:
916    /// a node connected through multiple edges (e.g. the forward and
917    /// auto-reverse edges of an undirected graph with `Direction::Both`)
918    /// appears only once.
919    pub fn neighbors(
920        &self,
921        node_ref: &NodeRef,
922        rel_type: Option<&str>,
923        direction: Direction,
924    ) -> Vec<NodeId> {
925        let mut neighbors = Vec::new();
926        let mut seen: HashSet<String> = HashSet::new();
927        let node_key = format!("{}:{}", node_ref.0, node_ref.1);
928
929        if direction == Direction::Out || direction == Direction::Both {
930            if let Some(edges) = self.out_edges.get(&node_key) {
931                for edge in edges {
932                    if (rel_type.is_none() || rel_type == Some(&edge.rel_type))
933                        && seen.insert(edge.target.to_key())
934                    {
935                        neighbors.push(edge.target.clone());
936                    }
937                }
938            }
939        }
940
941        if direction == Direction::In || direction == Direction::Both {
942            if let Some(edges) = self.in_edges.get(&node_key) {
943                for edge in edges {
944                    if (rel_type.is_none() || rel_type == Some(&edge.rel_type))
945                        && seen.insert(edge.source.to_key())
946                    {
947                        neighbors.push(edge.source.clone());
948                    }
949                }
950            }
951        }
952
953        neighbors
954    }
955
956    /// Get nodes N hops away
957    pub fn multi_hop(
958        &self,
959        start: &NodeRef,
960        rel_type: Option<&str>,
961        hops: usize,
962        direction: Direction,
963    ) -> Vec<NodeId> {
964        if hops == 0 {
965            return vec![NodeId::new(start.0, start.1)];
966        }
967
968        let start_key = format!("{}:{}", start.0, start.1);
969        let mut current: HashSet<String> = HashSet::new();
970        current.insert(start_key.clone());
971
972        let mut visited: HashSet<String> = HashSet::new();
973        visited.insert(start_key);
974
975        let mut ref_map: HashMap<String, NodeId> = HashMap::new();
976        ref_map.insert(
977            format!("{}:{}", start.0, start.1),
978            NodeId::new(start.0, start.1),
979        );
980
981        for _ in 0..hops {
982            let mut next_level: HashSet<String> = HashSet::new();
983
984            for key in &current {
985                if let Some(node_id) = ref_map.get(key) {
986                    let neighbors = self.neighbors(&node_id.as_ref(), rel_type, direction);
987                    for neighbor in neighbors {
988                        let neighbor_key = neighbor.to_key();
989                        if !visited.contains(&neighbor_key) {
990                            next_level.insert(neighbor_key.clone());
991                            ref_map.insert(neighbor_key.clone(), neighbor);
992                        }
993                    }
994                }
995            }
996
997            for key in &next_level {
998                visited.insert(key.clone());
999            }
1000            current = next_level;
1001        }
1002
1003        current
1004            .iter()
1005            .filter_map(|key| ref_map.get(key).cloned())
1006            .collect()
1007    }
1008
1009    /// Get nodes within a range of hops
1010    pub fn multi_hop_range(
1011        &self,
1012        start: &NodeRef,
1013        rel_type: Option<&str>,
1014        min_hops: usize,
1015        max_hops: usize,
1016        direction: Direction,
1017    ) -> Vec<NodeId> {
1018        let start_key = format!("{}:{}", start.0, start.1);
1019        let mut result: HashSet<String> = HashSet::new();
1020        let mut current: HashSet<String> = HashSet::new();
1021        current.insert(start_key.clone());
1022
1023        let mut visited: HashSet<String> = HashSet::new();
1024        visited.insert(start_key);
1025
1026        let mut ref_map: HashMap<String, NodeId> = HashMap::new();
1027        ref_map.insert(
1028            format!("{}:{}", start.0, start.1),
1029            NodeId::new(start.0, start.1),
1030        );
1031
1032        for hop in 1..=max_hops {
1033            let mut next_level: HashSet<String> = HashSet::new();
1034
1035            for key in &current {
1036                if let Some(node_id) = ref_map.get(key) {
1037                    let neighbors = self.neighbors(&node_id.as_ref(), rel_type, direction);
1038                    for neighbor in neighbors {
1039                        let neighbor_key = neighbor.to_key();
1040                        if !visited.contains(&neighbor_key) {
1041                            next_level.insert(neighbor_key.clone());
1042                            ref_map.insert(neighbor_key.clone(), neighbor);
1043                            if hop >= min_hops {
1044                                result.insert(neighbor_key);
1045                            }
1046                        }
1047                    }
1048                }
1049            }
1050
1051            for key in &next_level {
1052                visited.insert(key.clone());
1053            }
1054            current = next_level;
1055
1056            if current.is_empty() {
1057                break;
1058            }
1059        }
1060
1061        result
1062            .iter()
1063            .filter_map(|key| ref_map.get(key).cloned())
1064            .collect()
1065    }
1066
1067    // =========================================================================
1068    // Path Finding
1069    // =========================================================================
1070
1071    /// Find shortest path between two nodes using BFS
1072    pub fn shortest_path(
1073        &self,
1074        start: &NodeRef,
1075        end: &NodeRef,
1076        rel_type: Option<&str>,
1077        max_hops: usize,
1078        direction: Direction,
1079    ) -> Option<Path> {
1080        let start_id = NodeId::new(start.0, start.1);
1081        let end_id = NodeId::new(end.0, end.1);
1082
1083        if start_id == end_id {
1084            return Some(Path::new(vec![start_id], vec![]));
1085        }
1086
1087        let end_key = end_id.to_key();
1088        let mut visited: HashSet<String> = HashSet::new();
1089        visited.insert(start_id.to_key());
1090
1091        let mut queue: VecDeque<(NodeId, Vec<NodeId>, Vec<Edge>)> = VecDeque::new();
1092        queue.push_back((start_id.clone(), vec![start_id], vec![]));
1093
1094        while let Some((current, path_nodes, path_edges)) = queue.pop_front() {
1095            if path_nodes.len() > max_hops.saturating_add(1) {
1096                continue;
1097            }
1098
1099            let current_key = current.to_key();
1100
1101            if direction != Direction::In {
1102                if let Some(edges) = self.out_edges.get(&current_key) {
1103                    for edge in edges {
1104                        if rel_type.is_some() && rel_type != Some(&edge.rel_type) {
1105                            continue;
1106                        }
1107
1108                        let target_key = edge.target.to_key();
1109                        if target_key == end_key {
1110                            let mut nodes = path_nodes.clone();
1111                            nodes.push(edge.target.clone());
1112                            let mut edges = path_edges.clone();
1113                            edges.push(edge.clone());
1114                            return Some(Path::new(nodes, edges));
1115                        }
1116
1117                        if !visited.contains(&target_key) {
1118                            visited.insert(target_key);
1119                            let mut nodes = path_nodes.clone();
1120                            nodes.push(edge.target.clone());
1121                            let mut edges = path_edges.clone();
1122                            edges.push(edge.clone());
1123                            queue.push_back((edge.target.clone(), nodes, edges));
1124                        }
1125                    }
1126                }
1127            }
1128
1129            if direction == Direction::In || direction == Direction::Both {
1130                if let Some(edges) = self.in_edges.get(&current_key) {
1131                    for edge in edges {
1132                        if rel_type.is_some() && rel_type != Some(&edge.rel_type) {
1133                            continue;
1134                        }
1135
1136                        let source_key = edge.source.to_key();
1137                        if source_key == end_key {
1138                            let mut nodes = path_nodes.clone();
1139                            nodes.push(edge.source.clone());
1140                            let mut edges = path_edges.clone();
1141                            edges.push(edge.clone());
1142                            return Some(Path::new(nodes, edges));
1143                        }
1144
1145                        if !visited.contains(&source_key) {
1146                            visited.insert(source_key);
1147                            let mut nodes = path_nodes.clone();
1148                            nodes.push(edge.source.clone());
1149                            let mut edges = path_edges.clone();
1150                            edges.push(edge.clone());
1151                            queue.push_back((edge.source.clone(), nodes, edges));
1152                        }
1153                    }
1154                }
1155            }
1156        }
1157
1158        None
1159    }
1160
1161    /// Check if a path exists between two nodes in the given direction
1162    pub fn path_exists(
1163        &self,
1164        start: &NodeRef,
1165        end: &NodeRef,
1166        rel_type: Option<&str>,
1167        max_hops: usize,
1168        direction: Direction,
1169    ) -> bool {
1170        self.shortest_path(start, end, rel_type, max_hops, direction)
1171            .is_some()
1172    }
1173
1174    // =========================================================================
1175    // Graph Analysis
1176    // =========================================================================
1177
1178    /// Count incoming edges for a node
1179    pub fn in_degree(&self, node_ref: &NodeRef) -> usize {
1180        let key = format!("{}:{}", node_ref.0, node_ref.1);
1181        self.in_edges.get(&key).map(|v| v.len()).unwrap_or(0)
1182    }
1183
1184    /// Count outgoing edges for a node
1185    pub fn out_degree(&self, node_ref: &NodeRef) -> usize {
1186        let key = format!("{}:{}", node_ref.0, node_ref.1);
1187        self.out_edges.get(&key).map(|v| v.len()).unwrap_or(0)
1188    }
1189
1190    /// Total degree for a node
1191    pub fn degree(&self, node_ref: &NodeRef) -> usize {
1192        self.in_degree(node_ref) + self.out_degree(node_ref)
1193    }
1194
1195    /// Check if graph is connected
1196    pub fn is_connected(&self) -> bool {
1197        let all_nodes: Vec<_> = self.nodes().collect();
1198        if all_nodes.is_empty() {
1199            return true;
1200        }
1201
1202        let start = &all_nodes[0];
1203        let start_key = start.to_key();
1204        let mut visited: HashSet<String> = HashSet::new();
1205        visited.insert(start_key.clone());
1206
1207        let mut queue: VecDeque<String> = VecDeque::new();
1208        queue.push_back(start_key);
1209
1210        while let Some(current_key) = queue.pop_front() {
1211            // Get node from key
1212            let parts: Vec<&str> = current_key.split(':').collect();
1213            if parts.len() == 2 {
1214                let neighbors = self.neighbors(&(parts[0], parts[1]), None, Direction::Both);
1215                for neighbor in neighbors {
1216                    let neighbor_key = neighbor.to_key();
1217                    if !visited.contains(&neighbor_key) {
1218                        visited.insert(neighbor_key.clone());
1219                        queue.push_back(neighbor_key);
1220                    }
1221                }
1222            }
1223        }
1224
1225        visited.len() == all_nodes.len()
1226    }
1227
1228    // =========================================================================
1229    // Serialization
1230    // =========================================================================
1231
1232    /// Serialize graph to ISON format.
1233    ///
1234    /// Serialization is canonical: node type blocks, node rows within a
1235    /// block, edge type blocks, and edge rows within a block are all sorted
1236    /// (ordinal string comparison), independent of insertion order. The
1237    /// same logical graph always serializes to the same bytes, regardless
1238    /// of construction history.
1239    /// Build the ISON Document this graph serializes to.
1240    ///
1241    /// ISONGraph decides *what* to emit - which blocks, which rows, which
1242    /// columns - and hands every byte-level decision to ison-rs's canonical
1243    /// writer: quoting, escaping, delimiters, column layout, and the final
1244    /// block and row order.
1245    ///
1246    /// This used to be hand-rolled here, which meant ISON syntax had two
1247    /// implementations per language that had to agree forever. They did not:
1248    /// the id column was written unquoted, so a node id containing a space
1249    /// produced output that would not reparse.
1250    fn document(&self) -> IsonDocument {
1251        let mut doc = IsonDocument::new();
1252
1253        let mut node_types: Vec<_> = self.nodes.keys().collect();
1254        node_types.sort();
1255        for node_type in node_types {
1256            let type_nodes = &self.nodes[node_type];
1257            if type_nodes.is_empty() {
1258                continue;
1259            }
1260
1261            let mut prop_keys: Vec<&String> = type_nodes
1262                .values()
1263                .flat_map(|n| n.properties.keys())
1264                .collect::<HashSet<_>>()
1265                .into_iter()
1266                .collect();
1267            prop_keys.sort();
1268
1269            let mut block = IsonBlock::new("nodes", node_type.as_str());
1270            block.fields = std::iter::once("id".to_string())
1271                .chain(prop_keys.iter().map(|k| (*k).clone()))
1272                .collect();
1273
1274            for node in type_nodes.values() {
1275                let mut row: HashMap<String, IsonValue> = HashMap::new();
1276                row.insert("id".to_string(), IsonValue::String(node.id.clone()));
1277                for key in &prop_keys {
1278                    let value = match node.properties.get(*key) {
1279                        Some(v) => v.clone(),
1280                        None => IsonValue::Null,
1281                    };
1282                    row.insert((*key).clone(), value);
1283                }
1284                block.rows.push(row);
1285            }
1286            doc.blocks.push(block);
1287        }
1288
1289        let mut edge_types: Vec<_> = self.edges.keys().collect();
1290        edge_types.sort();
1291        for rel_type in edge_types {
1292            let edges = &self.edges[rel_type];
1293            if edges.is_empty() {
1294                continue;
1295            }
1296
1297            let mut prop_keys: Vec<&String> = edges
1298                .iter()
1299                .flat_map(|e| e.properties.keys())
1300                .collect::<HashSet<_>>()
1301                .into_iter()
1302                .collect();
1303            prop_keys.sort();
1304
1305            let mut block = IsonBlock::new("edges", rel_type.as_str());
1306            block.fields = ["source".to_string(), "target".to_string()]
1307                .into_iter()
1308                .chain(prop_keys.iter().map(|k| (*k).clone()))
1309                .collect();
1310
1311            for edge in edges {
1312                let mut row: HashMap<String, IsonValue> = HashMap::new();
1313                row.insert(
1314                    "source".to_string(),
1315                    IsonValue::Reference(IsonReference::with_type(
1316                        edge.source.id.clone(),
1317                        edge.source.node_type.clone(),
1318                    )),
1319                );
1320                row.insert(
1321                    "target".to_string(),
1322                    IsonValue::Reference(IsonReference::with_type(
1323                        edge.target.id.clone(),
1324                        edge.target.node_type.clone(),
1325                    )),
1326                );
1327                for key in &prop_keys {
1328                    let value = match edge.properties.get(*key) {
1329                        Some(v) => v.clone(),
1330                        None => IsonValue::Null,
1331                    };
1332                    row.insert((*key).clone(), value);
1333                }
1334                block.rows.push(row);
1335            }
1336            doc.blocks.push(block);
1337        }
1338
1339        doc
1340    }
1341
1342    /// Serialize graph to canonical ISON (ISONCS).
1343    ///
1344    /// Output is canonical: the same logical graph always serializes to the
1345    /// same bytes regardless of construction order. Block, row and column
1346    /// order are the canonical writer's, not ISONGraph's.
1347    pub fn to_ison(&self) -> String {
1348        dumps_canonical(&self.document()).unwrap_or_default()
1349    }
1350
1351    /// Serialize graph to canonical ISONL. Row order matches [`to_ison`].
1352    pub fn to_isonl(&self) -> String {
1353        dumps_canonical_isonl(&self.document()).unwrap_or_default()
1354    }
1355
1356
1357    /// Node ids are identifiers rather than values, so they are always text.
1358    /// Property values keep whatever type the parser produced.
1359    fn id_text(value: &IsonValue) -> Option<String> {
1360        match value {
1361            IsonValue::Null => None,
1362            IsonValue::Bool(b) => Some(b.to_string()),
1363            IsonValue::Int(i) => Some(i.to_string()),
1364            IsonValue::Float(f) => Some(f.to_string()),
1365            IsonValue::String(s) => Some(s.clone()),
1366            IsonValue::Reference(r) => Some(r.to_ison()),
1367        }
1368    }
1369
1370    fn build_from_document(doc: &IsonDocument, name: &str) -> Result<Self> {
1371        let mut graph = ISONGraph::new(name);
1372
1373        for block in &doc.blocks {
1374            if block.kind != "nodes" && block.kind != "edges" {
1375                return Err(GraphError::ParseError(format!(
1376                    "unknown block kind {:?} (expected 'nodes' or 'edges')",
1377                    block.kind
1378                )));
1379            }
1380        }
1381
1382        // Nodes first regardless of block order - the canonical writer sorts
1383        // blocks by name, which puts 'edges' ahead of 'nodes'.
1384        for block in &doc.blocks {
1385            if block.kind != "nodes" {
1386                continue;
1387            }
1388            for row in &block.rows {
1389                // The id is an identifier, not a property, so it stays text;
1390                // everything else keeps the type the parser gave it.
1391                let id = row
1392                    .get("id")
1393                    .and_then(Self::id_text)
1394                    .ok_or_else(|| GraphError::ParseError("row has no id".into()))?;
1395                let props: Vec<(String, Value)> = row
1396                    .iter()
1397                    .filter(|(k, _)| k.as_str() != "id")
1398                    .map(|(k, v)| (k.clone(), v.clone()))
1399                    .collect();
1400                let borrowed: Vec<(&str, Value)> =
1401                    props.iter().map(|(k, v)| (k.as_str(), v.clone())).collect();
1402                graph.add_node(&block.name, &id, borrowed)?;
1403            }
1404        }
1405
1406        for block in &doc.blocks {
1407            if block.kind != "edges" {
1408                continue;
1409            }
1410            for row in &block.rows {
1411                let (source, target) = match (row.get("source"), row.get("target")) {
1412                    (Some(IsonValue::Reference(s)), Some(IsonValue::Reference(t))) => (
1413                        (s.ref_type.clone().unwrap_or_default(), s.id.clone()),
1414                        (t.ref_type.clone().unwrap_or_default(), t.id.clone()),
1415                    ),
1416                    _ => {
1417                        return Err(GraphError::ParseError(
1418                            "edge row is missing a source or target reference".into(),
1419                        ))
1420                    }
1421                };
1422                let props: Vec<(String, Value)> = row
1423                    .iter()
1424                    .filter(|(k, _)| k.as_str() != "source" && k.as_str() != "target")
1425                    .map(|(k, v)| (k.clone(), v.clone()))
1426                    .collect();
1427                let borrowed: Vec<(&str, Value)> =
1428                    props.iter().map(|(k, v)| (k.as_str(), v.clone())).collect();
1429                graph.add_edge(
1430                    &block.name,
1431                    (&source.0, &source.1),
1432                    (&target.0, &target.1),
1433                    borrowed,
1434                )?;
1435            }
1436        }
1437
1438        Ok(graph)
1439    }
1440
1441    /// Parse a graph from ISON.
1442    pub fn from_ison(text: &str, name: Option<&str>) -> Result<Self> {
1443        let doc = loads(text)
1444            .map_err(|e| GraphError::ParseError(format!("{}", e)))?;
1445        Self::build_from_document(&doc, name.unwrap_or("graph"))
1446    }
1447
1448    /// Parse a graph from ISONL.
1449    pub fn from_isonl(text: &str, name: Option<&str>) -> Result<Self> {
1450        let doc = loads_isonl(text)
1451            .map_err(|e| GraphError::ParseError(format!("{}", e)))?;
1452        Self::build_from_document(&doc, name.unwrap_or("graph"))
1453    }
1454
1455    pub fn save<P: AsRef<StdPath>>(&self, path: P, format: Option<&str>) -> Result<()> {
1456        let path = path.as_ref();
1457        let actual_format = format.unwrap_or_else(|| {
1458            if path.extension().map(|e| e == "isonl").unwrap_or(false) {
1459                "isonl"
1460            } else {
1461                "ison"
1462            }
1463        });
1464
1465        let content = if actual_format == "isonl" {
1466            self.to_isonl()
1467        } else {
1468            self.to_ison()
1469        };
1470
1471        fs::write(path, content).map_err(GraphError::Io)
1472    }
1473
1474    /// Load graph from file
1475    pub fn load<P: AsRef<StdPath>>(path: P, format: Option<&str>) -> Result<Self> {
1476        let path = path.as_ref();
1477        let content = fs::read_to_string(path).map_err(GraphError::Io)?;
1478
1479        let actual_format = format.unwrap_or_else(|| {
1480            if path.extension().map(|e| e == "isonl").unwrap_or(false) {
1481                "isonl"
1482            } else {
1483                "ison"
1484            }
1485        });
1486
1487        let graph_name = path.file_stem().and_then(|s| s.to_str()).unwrap_or("graph");
1488
1489        if actual_format == "isonl" {
1490            Self::from_isonl(&content, Some(graph_name))
1491        } else {
1492            Self::from_ison(&content, Some(graph_name))
1493        }
1494    }
1495
1496    // =========================================================================
1497    // Additional Edge Operations
1498    // =========================================================================
1499
1500    /// Get an edge by its components
1501    pub fn get_edge(&self, rel_type: &str, source: (&str, &str), target: (&str, &str)) -> Result<&Edge> {
1502        let source_id = NodeId::new(source.0, source.1);
1503        let target_id = NodeId::new(target.0, target.1);
1504
1505        if let Some(edges) = self.edges.get(rel_type) {
1506            for edge in edges {
1507                if edge.source == source_id && edge.target == target_id {
1508                    return Ok(edge);
1509                }
1510            }
1511        }
1512
1513        Err(GraphError::EdgeNotFound(
1514            format!("{}:{}", source.0, source.1),
1515            format!("{}:{}", target.0, target.1),
1516        ))
1517    }
1518
1519    // =========================================================================
1520    // Additional Graph Analysis
1521    // =========================================================================
1522
1523    /// Get all connected components
1524    pub fn connected_components(&self) -> Vec<HashSet<NodeId>> {
1525        let mut visited: HashSet<String> = HashSet::new();
1526        let mut components: Vec<HashSet<NodeId>> = Vec::new();
1527
1528        for node in self.nodes() {
1529            let node_key = node.to_key();
1530            if !visited.contains(&node_key) {
1531                let mut component: HashSet<NodeId> = HashSet::new();
1532                let mut queue: VecDeque<NodeId> = VecDeque::new();
1533                queue.push_back(node.node_id());
1534
1535                while let Some(current) = queue.pop_front() {
1536                    let current_key = current.to_key();
1537                    if visited.contains(&current_key) {
1538                        continue;
1539                    }
1540                    visited.insert(current_key);
1541                    component.insert(current.clone());
1542
1543                    // Get neighbors in both directions
1544                    let neighbors = self.neighbors(&current.as_ref(), None, Direction::Both);
1545                    for neighbor in neighbors {
1546                        if !visited.contains(&neighbor.to_key()) {
1547                            queue.push_back(neighbor);
1548                        }
1549                    }
1550                }
1551
1552                components.push(component);
1553            }
1554        }
1555
1556        components
1557    }
1558
1559    /// Edges to follow from a node for path enumeration
1560    fn edges_to_follow(
1561        &self,
1562        node: &NodeId,
1563        rel_type: Option<&str>,
1564        direction: Direction,
1565    ) -> Vec<(Edge, NodeId)> {
1566        let node_key = node.to_key();
1567        let mut edges_to_follow: Vec<(Edge, NodeId)> = Vec::new();
1568
1569        if direction == Direction::Out || direction == Direction::Both {
1570            if let Some(out_edges) = self.out_edges.get(&node_key) {
1571                for edge in out_edges {
1572                    if rel_type.is_none() || rel_type == Some(&edge.rel_type) {
1573                        edges_to_follow.push((edge.clone(), edge.target.clone()));
1574                    }
1575                }
1576            }
1577        }
1578
1579        if direction == Direction::In || direction == Direction::Both {
1580            if let Some(in_edges) = self.in_edges.get(&node_key) {
1581                for edge in in_edges {
1582                    if rel_type.is_none() || rel_type == Some(&edge.rel_type) {
1583                        edges_to_follow.push((edge.clone(), edge.source.clone()));
1584                    }
1585                }
1586            }
1587        }
1588
1589        edges_to_follow
1590    }
1591
1592    /// Find all paths between two nodes using iterative DFS
1593    pub fn all_paths(
1594        &self,
1595        start: &NodeRef,
1596        end: &NodeRef,
1597        rel_type: Option<&str>,
1598        max_hops: usize,
1599        direction: Direction,
1600    ) -> Vec<Path> {
1601        let start_id = NodeId::new(start.0, start.1);
1602        let end_id = NodeId::new(end.0, end.1);
1603        let mut paths: Vec<Path> = Vec::new();
1604
1605        let mut visited: HashSet<String> = HashSet::new();
1606        visited.insert(start_id.to_key());
1607        let mut path_nodes = vec![start_id.clone()];
1608        let mut path_edges: Vec<Edge> = Vec::new();
1609
1610        if start_id == end_id {
1611            paths.push(Path::new(path_nodes, path_edges));
1612            return paths;
1613        }
1614
1615        struct Frame {
1616            options: Vec<(Edge, NodeId)>,
1617            idx: usize,
1618        }
1619
1620        let mut stack = vec![Frame {
1621            options: self.edges_to_follow(&start_id, rel_type, direction),
1622            idx: 0,
1623        }];
1624
1625        while !stack.is_empty() {
1626            let next = {
1627                let frame = stack.last_mut().unwrap();
1628                if frame.idx < frame.options.len() {
1629                    let option = frame.options[frame.idx].clone();
1630                    frame.idx += 1;
1631                    Some(option)
1632                } else {
1633                    None
1634                }
1635            };
1636
1637            match next {
1638                Some((edge, next_node)) => {
1639                    let next_key = next_node.to_key();
1640                    if visited.contains(&next_key) {
1641                        continue;
1642                    }
1643
1644                    visited.insert(next_key.clone());
1645                    path_nodes.push(next_node.clone());
1646                    path_edges.push(edge);
1647
1648                    if path_nodes.len() > max_hops.saturating_add(1) {
1649                        // Too deep: backtrack immediately
1650                        path_nodes.pop();
1651                        path_edges.pop();
1652                        visited.remove(&next_key);
1653                        continue;
1654                    }
1655
1656                    if next_node == end_id {
1657                        paths.push(Path::new(path_nodes.clone(), path_edges.clone()));
1658                        path_nodes.pop();
1659                        path_edges.pop();
1660                        visited.remove(&next_key);
1661                        continue;
1662                    }
1663
1664                    stack.push(Frame {
1665                        options: self.edges_to_follow(&next_node, rel_type, direction),
1666                        idx: 0,
1667                    });
1668                }
1669                None => {
1670                    stack.pop();
1671                    // Backtrack the path entry owned by the popped frame
1672                    // (the root frame owns the start node, which stays).
1673                    if !stack.is_empty() {
1674                        if let Some(popped) = path_nodes.pop() {
1675                            path_edges.pop();
1676                            visited.remove(&popped.to_key());
1677                        }
1678                    }
1679                }
1680            }
1681        }
1682
1683        paths
1684    }
1685
1686    // =========================================================================
1687    // Pattern-based Traversal
1688    // =========================================================================
1689
1690    /// Traverse graph following a pattern of relationship types
1691    pub fn traverse(
1692        &self,
1693        start: &NodeRef,
1694        pattern: &[(String, Direction)],
1695        filter_fn: Option<&dyn Fn(&Node) -> bool>,
1696    ) -> Vec<NodeId> {
1697        let start_id = NodeId::new(start.0, start.1);
1698        let mut current: HashSet<String> = HashSet::new();
1699        current.insert(start_id.to_key());
1700
1701        let mut ref_map: HashMap<String, NodeId> = HashMap::new();
1702        ref_map.insert(start_id.to_key(), start_id);
1703
1704        for (rel_type, direction) in pattern {
1705            let mut next_level: HashSet<String> = HashSet::new();
1706
1707            for key in &current {
1708                if let Some(node_id) = ref_map.get(key) {
1709                    let neighbors = self.neighbors(&node_id.as_ref(), Some(rel_type), *direction);
1710                    for neighbor in neighbors {
1711                        let neighbor_key = neighbor.to_key();
1712
1713                        let should_include = match filter_fn {
1714                            None => true,
1715                            Some(f) => {
1716                                if let Ok(node) = self.get_node_by_id(&neighbor) {
1717                                    f(node)
1718                                } else {
1719                                    false
1720                                }
1721                            }
1722                        };
1723
1724                        if should_include {
1725                            next_level.insert(neighbor_key.clone());
1726                            ref_map.insert(neighbor_key, neighbor);
1727                        }
1728                    }
1729                }
1730            }
1731
1732            current = next_level;
1733            if current.is_empty() {
1734                break;
1735            }
1736        }
1737
1738        current
1739            .iter()
1740            .filter_map(|key| ref_map.get(key).cloned())
1741            .collect()
1742    }
1743
1744    // =========================================================================
1745    // Query Pattern Syntax
1746    // =========================================================================
1747
1748    /// Execute a simple pattern query
1749    ///
1750    /// Pattern syntax:
1751    ///   :type:id -[:REL]-> *           (single hop)
1752    ///   :type:id -[:REL*N]-> *         (N hops)
1753    ///   :type:id -[:REL*1..3]-> *      (1-3 hops range)
1754    pub fn query(&self, pattern: &str) -> Result<Vec<NodeId>> {
1755        static HOP_REGEX: OnceLock<Regex> = OnceLock::new();
1756        static RANGE_REGEX: OnceLock<Regex> = OnceLock::new();
1757        static SIMPLE_REGEX: OnceLock<Regex> = OnceLock::new();
1758
1759        let p = pattern.trim();
1760
1761        // Match: :type:id -[:REL*N]-> *
1762        let hop_regex = HOP_REGEX.get_or_init(|| {
1763            Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\*(\d+)\]->\s*\*$").unwrap()
1764        });
1765        if let Some(caps) = hop_regex.captures(p) {
1766            let node_type = caps.get(1).unwrap().as_str();
1767            let node_id = caps.get(2).unwrap().as_str();
1768            let rel_type = caps.get(3).unwrap().as_str();
1769            let hops: usize = caps.get(4).unwrap().as_str().parse().unwrap_or(1);
1770            return Ok(self.multi_hop(&(node_type, node_id), Some(rel_type), hops, Direction::Out));
1771        }
1772
1773        // Match: :type:id -[:REL*N..M]-> *
1774        let range_regex = RANGE_REGEX.get_or_init(|| {
1775            Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\*(\d+)\.\.(\d+)\]->\s*\*$").unwrap()
1776        });
1777        if let Some(caps) = range_regex.captures(p) {
1778            let node_type = caps.get(1).unwrap().as_str();
1779            let node_id = caps.get(2).unwrap().as_str();
1780            let rel_type = caps.get(3).unwrap().as_str();
1781            let min_hops: usize = caps.get(4).unwrap().as_str().parse().unwrap_or(1);
1782            let max_hops: usize = caps.get(5).unwrap().as_str().parse().unwrap_or(3);
1783            return Ok(self.multi_hop_range(
1784                &(node_type, node_id),
1785                Some(rel_type),
1786                min_hops,
1787                max_hops,
1788                Direction::Out,
1789            ));
1790        }
1791
1792        // Match: :type:id -[:REL]-> *
1793        let simple_regex = SIMPLE_REGEX
1794            .get_or_init(|| Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\]->\s*\*$").unwrap());
1795        if let Some(caps) = simple_regex.captures(p) {
1796            let node_type = caps.get(1).unwrap().as_str();
1797            let node_id = caps.get(2).unwrap().as_str();
1798            let rel_type = caps.get(3).unwrap().as_str();
1799            return Ok(self.neighbors(&(node_type, node_id), Some(rel_type), Direction::Out));
1800        }
1801
1802        Err(GraphError::ParseError(format!("Invalid query pattern: {}", pattern)))
1803    }
1804
1805    // =========================================================================
1806    // Fluent API Entry Point
1807    // =========================================================================
1808
1809    /// Start a fluent traversal from a node
1810    pub fn start(&self, node_ref: &NodeRef) -> GraphTraversal<'_> {
1811        GraphTraversal::new(self, NodeId::new(node_ref.0, node_ref.1))
1812    }
1813}
1814
1815// =============================================================================
1816// Fluent Traversal API
1817// =============================================================================
1818
1819/// Fluent API for graph traversal
1820pub struct GraphTraversal<'a> {
1821    graph: &'a ISONGraph,
1822    current: HashSet<String>,
1823    visited: HashSet<String>,
1824    ref_map: HashMap<String, NodeId>,
1825}
1826
1827impl<'a> GraphTraversal<'a> {
1828    pub fn new(graph: &'a ISONGraph, start: NodeId) -> Self {
1829        let start_key = start.to_key();
1830        let mut current = HashSet::new();
1831        current.insert(start_key.clone());
1832
1833        let mut visited = HashSet::new();
1834        visited.insert(start_key.clone());
1835
1836        let mut ref_map = HashMap::new();
1837        ref_map.insert(start_key, start);
1838
1839        Self {
1840            graph,
1841            current,
1842            visited,
1843            ref_map,
1844        }
1845    }
1846
1847    /// Traverse one hop following edges
1848    pub fn hop(mut self, rel_type: Option<&str>, direction: Direction) -> Self {
1849        let mut next_level: HashSet<String> = HashSet::new();
1850
1851        for key in &self.current {
1852            if let Some(node_id) = self.ref_map.get(key) {
1853                let neighbors = self.graph.neighbors(&node_id.as_ref(), rel_type, direction);
1854                for neighbor in neighbors {
1855                    let neighbor_key = neighbor.to_key();
1856                    if !self.visited.contains(&neighbor_key) {
1857                        next_level.insert(neighbor_key.clone());
1858                        self.ref_map.insert(neighbor_key, neighbor);
1859                    }
1860                }
1861            }
1862        }
1863
1864        for key in &next_level {
1865            self.visited.insert(key.clone());
1866        }
1867        self.current = next_level;
1868        self
1869    }
1870
1871    /// Traverse N hops
1872    pub fn hops(mut self, n: usize, rel_type: Option<&str>, direction: Direction) -> Self {
1873        for _ in 0..n {
1874            self = self.hop(rel_type, direction);
1875        }
1876        self
1877    }
1878
1879    /// Filter current nodes
1880    pub fn filter<F>(mut self, f: F) -> Self
1881    where
1882        F: Fn(&Node) -> bool,
1883    {
1884        let filtered: HashSet<String> = self
1885            .current
1886            .iter()
1887            .filter(|key| {
1888                if let Some(node_id) = self.ref_map.get(*key) {
1889                    if let Ok(node) = self.graph.get_node_by_id(node_id) {
1890                        return f(node);
1891                    }
1892                }
1893                false
1894            })
1895            .cloned()
1896            .collect();
1897        self.current = filtered;
1898        self
1899    }
1900
1901    /// Return current nodes as NodeId vector
1902    pub fn collect(self) -> Vec<NodeId> {
1903        self.current
1904            .iter()
1905            .filter_map(|key| self.ref_map.get(key).cloned())
1906            .collect()
1907    }
1908
1909    /// Return current nodes as Node objects
1910    pub fn collect_nodes(self) -> Vec<Node> {
1911        self.current
1912            .iter()
1913            .filter_map(|key| {
1914                self.ref_map
1915                    .get(key)
1916                    .and_then(|id| self.graph.get_node_by_id(id).ok().cloned())
1917            })
1918            .collect()
1919    }
1920
1921    /// Count current nodes
1922    pub fn count(&self) -> usize {
1923        self.current.len()
1924    }
1925
1926    /// Get first node or None
1927    pub fn first(&self) -> Option<NodeId> {
1928        self.current
1929            .iter()
1930            .next()
1931            .and_then(|key| self.ref_map.get(key).cloned())
1932    }
1933}
1934
1935// =============================================================================
1936// Tests
1937// =============================================================================
1938
1939#[cfg(test)]
1940mod tests {
1941    use super::*;
1942
1943    #[test]
1944    fn test_add_and_get_node() {
1945        let mut graph = ISONGraph::new("test");
1946        graph
1947            .add_node("person", "1", props![("name", "Alice"), ("age", "30")])
1948            .unwrap();
1949
1950        let node = graph.get_node("person", "1").unwrap();
1951        assert_eq!(node.node_type, "person");
1952        assert_eq!(node.id, "1");
1953        assert_eq!(crate::value_to_text(node.properties.get("name").unwrap()), "Alice");
1954    }
1955
1956    #[test]
1957    fn test_duplicate_node() {
1958        let mut graph = ISONGraph::new("test");
1959        graph.add_node("person", "1", props![]).unwrap();
1960        assert!(graph.add_node("person", "1", props![]).is_err());
1961    }
1962
1963    #[test]
1964    fn test_add_node_rejects_colon() {
1965        let mut graph = ISONGraph::new("test");
1966        assert!(matches!(
1967            graph.add_node("per:son", "1", props![]),
1968            Err(GraphError::InvalidIdentifier(_))
1969        ));
1970        assert!(matches!(
1971            graph.add_node("person", "1:2", props![]),
1972            Err(GraphError::InvalidIdentifier(_))
1973        ));
1974        assert_eq!(graph.node_count(), 0);
1975    }
1976
1977    // ':' and '|' are structurally significant to the wire format ('type:id'
1978    // references, ISONL columns); allowing them in a node type, node id, or
1979    // relationship type builds a graph that fails on to_ison()/to_isonl()
1980    // round-trip instead of failing loudly at construction.
1981    #[test]
1982    fn test_add_node_rejects_pipe() {
1983        let mut graph = ISONGraph::new("test");
1984        assert!(matches!(
1985            graph.add_node("per|son", "1", props![]),
1986            Err(GraphError::InvalidIdentifier(_))
1987        ));
1988        assert!(matches!(
1989            graph.add_node("person", "1|2", props![]),
1990            Err(GraphError::InvalidIdentifier(_))
1991        ));
1992        assert_eq!(graph.node_count(), 0);
1993    }
1994
1995    #[test]
1996    fn test_add_edge_rejects_colon_and_pipe_in_rel_type() {
1997        let mut graph = ISONGraph::new("test");
1998        graph.add_node("person", "1", props![]).unwrap();
1999        graph.add_node("person", "2", props![]).unwrap();
2000        assert!(matches!(
2001            graph.add_edge("KN:OWS", ("person", "1"), ("person", "2"), props![]),
2002            Err(GraphError::InvalidIdentifier(_))
2003        ));
2004        assert!(matches!(
2005            graph.add_edge("KN|OWS", ("person", "1"), ("person", "2"), props![]),
2006            Err(GraphError::InvalidIdentifier(_))
2007        ));
2008        assert_eq!(graph.edge_count(), 0);
2009    }
2010
2011    #[test]
2012    fn test_unrepresentable_identifiers_are_rejected() {
2013        // Whitespace and empty used to be accepted and then blow up on round
2014        // trip: ':a b:1' splits mid-reference, and an id column holding 'a b'
2015        // reparses as two values. Rejected at construction instead.
2016        for bad in ["a b", "a\tb", "a\nb", ""] {
2017            let mut graph = ISONGraph::new("test");
2018            assert!(graph.add_node(bad, "1", props![]).is_err(), "type {:?}", bad);
2019            assert!(graph.add_node("p", bad, props![]).is_err(), "id {:?}", bad);
2020        }
2021
2022        // ISONL cannot quote a block name, so types are stricter than ids.
2023        for bad in ["a\"b", "a\\b"] {
2024            let mut graph = ISONGraph::new("test");
2025            assert!(graph.add_node(bad, "1", props![]).is_err(), "type {:?}", bad);
2026            assert!(graph.add_node("p", bad, props![]).is_ok(), "id {:?}", bad);
2027        }
2028    }
2029
2030    #[test]
2031    fn test_valid_identifiers_still_allowed() {
2032        let mut graph = ISONGraph::new("test");
2033        graph.add_node("a-type", "an-id-1", props![]).unwrap();
2034        graph.add_node("b.c", "#2", props![]).unwrap();
2035        graph
2036            .add_edge("SHARES_BORDER_WITH", ("a-type", "an-id-1"), ("b.c", "#2"), props![])
2037            .unwrap();
2038        assert_eq!(graph.edge_count(), 1);
2039
2040        let restored = ISONGraph::from_ison(&graph.to_ison(), None).unwrap();
2041        assert_eq!(restored.node_count(), 2);
2042        assert_eq!(restored.edge_count(), 1);
2043    }
2044
2045    #[test]
2046    fn test_no_longer_crashes_on_ison_roundtrip() {
2047        // Previously: add_node("a:b", "1") succeeded, then to_ison() ->
2048        // from_ison() raised NodeNotFound - the actual bug this closes.
2049        let mut graph = ISONGraph::new("test");
2050        assert!(graph.add_node("a:b", "1", props![]).is_err());
2051    }
2052
2053    #[test]
2054    fn test_no_longer_crashes_on_isonl_roundtrip() {
2055        let mut graph = ISONGraph::new("test");
2056        assert!(graph.add_node("rel|type", "1", props![]).is_err());
2057    }
2058
2059    #[cfg(feature = "serde")]
2060    #[test]
2061    fn test_serde_deserialize_rejects_bad_identifiers() {
2062        // Deserialization bypasses add_node/add_edge entirely (it rebuilds
2063        // the index maps directly from the payload), so a crafted or
2064        // corrupted JSON blob could smuggle in a ':' or '|' identifier that
2065        // the public API would have rejected - verify the TryFrom impl
2066        // re-applies the same guard.
2067        let bad = r#"{"name":"t","directed":true,"nodes":{"a:b":{"1":{"node_type":"a:b","id":"1","properties":{}}}},"edges":{}}"#;
2068        let result: std::result::Result<ISONGraph, _> = serde_json::from_str(bad);
2069        assert!(result.is_err());
2070
2071        let good = r#"{"name":"t","directed":true,"nodes":{"a":{"1":{"node_type":"a","id":"1","properties":{}}}},"edges":{}}"#;
2072        let graph: ISONGraph = serde_json::from_str(good).unwrap();
2073        assert_eq!(graph.node_count(), 1);
2074    }
2075
2076    #[test]
2077    fn test_add_and_has_edge() {
2078        let mut graph = ISONGraph::new("test");
2079        graph.add_node("person", "1", props![]).unwrap();
2080        graph.add_node("person", "2", props![]).unwrap();
2081        graph
2082            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2083            .unwrap();
2084
2085        assert!(graph.has_edge("KNOWS", ("person", "1"), ("person", "2")));
2086        assert!(!graph.has_edge("KNOWS", ("person", "2"), ("person", "1")));
2087    }
2088
2089    #[test]
2090    fn test_neighbors() {
2091        let mut graph = ISONGraph::new("test");
2092        graph.add_node("person", "1", props![]).unwrap();
2093        graph.add_node("person", "2", props![]).unwrap();
2094        graph.add_node("person", "3", props![]).unwrap();
2095        graph
2096            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2097            .unwrap();
2098        graph
2099            .add_edge("KNOWS", ("person", "1"), ("person", "3"), props![])
2100            .unwrap();
2101
2102        let friends = graph.neighbors(&("person", "1"), Some("KNOWS"), Direction::Out);
2103        assert_eq!(friends.len(), 2);
2104    }
2105
2106    #[test]
2107    fn test_multi_hop() {
2108        let mut graph = ISONGraph::new("test");
2109        graph.add_node("person", "1", props![]).unwrap();
2110        graph.add_node("person", "2", props![]).unwrap();
2111        graph.add_node("person", "3", props![]).unwrap();
2112        graph
2113            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2114            .unwrap();
2115        graph
2116            .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2117            .unwrap();
2118
2119        let two_hops = graph.multi_hop(&("person", "1"), Some("KNOWS"), 2, Direction::Out);
2120        assert_eq!(two_hops.len(), 1);
2121        assert_eq!(two_hops[0].id, "3");
2122    }
2123
2124    #[test]
2125    fn test_shortest_path() {
2126        let mut graph = ISONGraph::new("test");
2127        graph.add_node("person", "1", props![]).unwrap();
2128        graph.add_node("person", "2", props![]).unwrap();
2129        graph.add_node("person", "3", props![]).unwrap();
2130        graph
2131            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2132            .unwrap();
2133        graph
2134            .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2135            .unwrap();
2136
2137        let path = graph
2138            .shortest_path(&("person", "1"), &("person", "3"), Some("KNOWS"), 10, Direction::Out)
2139            .unwrap();
2140        assert_eq!(path.length(), 2);
2141        assert_eq!(path.nodes.len(), 3);
2142    }
2143
2144    #[test]
2145    fn test_node_count() {
2146        let mut graph = ISONGraph::new("test");
2147        graph.add_node("person", "1", props![]).unwrap();
2148        graph.add_node("person", "2", props![]).unwrap();
2149        graph.add_node("company", "100", props![]).unwrap();
2150
2151        assert_eq!(graph.node_count(), 3);
2152        assert_eq!(graph.node_count_of_type("person"), 2);
2153        assert_eq!(graph.node_count_of_type("company"), 1);
2154    }
2155
2156    #[test]
2157    fn test_to_ison() {
2158        let mut graph = ISONGraph::new("test");
2159        graph
2160            .add_node("person", "1", props![("name", "Alice")])
2161            .unwrap();
2162        graph
2163            .add_node("person", "2", props![("name", "Bob")])
2164            .unwrap();
2165        graph
2166            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2167            .unwrap();
2168
2169        let ison = graph.to_ison();
2170        assert!(ison.contains("nodes.person"));
2171        assert!(ison.contains("edges.KNOWS"));
2172        assert!(ison.contains("Alice"));
2173    }
2174
2175    fn special_values_graph() -> ISONGraph {
2176        let mut graph = ISONGraph::new("test");
2177        graph
2178            .add_node(
2179                "person",
2180                "1",
2181                props![
2182                    ("name", "Alice Smith"),
2183                    ("bio", "a|b"),
2184                    ("note", "line1\nline2"),
2185                    ("empty", ""),
2186                ],
2187            )
2188            .unwrap();
2189        graph
2190            .add_node(
2191                "person",
2192                "2",
2193                props![
2194                    ("name", "Bob"),
2195                    ("bio", "he said \"hi\""),
2196                    ("note", "x"),
2197                    ("empty", "y"),
2198                ],
2199            )
2200            .unwrap();
2201        graph
2202            .add_edge(
2203                "KNOWS",
2204                ("person", "1"),
2205                ("person", "2"),
2206                props![("where", "New York"), ("tag", "")],
2207            )
2208            .unwrap();
2209        graph
2210    }
2211
2212    fn assert_special_values(restored: &ISONGraph) {
2213        assert_eq!(restored.node_count(), 2);
2214        assert_eq!(restored.edge_count(), 1);
2215        let n1 = restored.get_node("person", "1").unwrap();
2216        assert_eq!(crate::value_to_text(n1.properties.get("name").unwrap()), "Alice Smith");
2217        assert_eq!(crate::value_to_text(n1.properties.get("bio").unwrap()), "a|b");
2218        assert_eq!(crate::value_to_text(n1.properties.get("note").unwrap()), "line1\nline2");
2219        assert_eq!(crate::value_to_text(n1.properties.get("empty").unwrap()), "");
2220        let n2 = restored.get_node("person", "2").unwrap();
2221        assert_eq!(crate::value_to_text(n2.properties.get("bio").unwrap()), "he said \"hi\"");
2222        let e = restored
2223            .get_edge("KNOWS", ("person", "1"), ("person", "2"))
2224            .unwrap();
2225        assert_eq!(crate::value_to_text(e.properties.get("where").unwrap()), "New York");
2226        assert_eq!(crate::value_to_text(e.properties.get("tag").unwrap()), "");
2227    }
2228
2229    #[test]
2230    fn test_ison_round_trip_special_values() {
2231        let graph = special_values_graph();
2232        let restored = ISONGraph::from_ison(&graph.to_ison(), Some("test")).unwrap();
2233        assert_special_values(&restored);
2234    }
2235
2236    #[test]
2237    fn test_isonl_round_trip_special_values() {
2238        let graph = special_values_graph();
2239        let restored = ISONGraph::from_isonl(&graph.to_isonl(), Some("test")).unwrap();
2240        assert_special_values(&restored);
2241    }
2242
2243    #[test]
2244    fn test_is_connected() {
2245        let mut graph = ISONGraph::new("test");
2246        graph.add_node("person", "1", props![]).unwrap();
2247        graph.add_node("person", "2", props![]).unwrap();
2248        graph
2249            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2250            .unwrap();
2251
2252        assert!(graph.is_connected());
2253
2254        graph.add_node("person", "3", props![]).unwrap();
2255        assert!(!graph.is_connected());
2256    }
2257
2258    // =========================================================================
2259    // Deserialization Tests
2260    // =========================================================================
2261
2262    #[test]
2263    fn test_from_ison() {
2264        let ison_text = r#"
2265nodes.person
2266id name age
2267alice Alice 30
2268bob Bob 25
2269
2270edges.KNOWS
2271source target since
2272:person:alice :person:bob 2020
2273"#;
2274
2275        let graph = ISONGraph::from_ison(ison_text, Some("test")).unwrap();
2276        assert_eq!(graph.node_count(), 2);
2277        assert_eq!(graph.edge_count(), 1);
2278        assert!(graph.has_node("person", "alice"));
2279        assert!(graph.has_node("person", "bob"));
2280        assert!(graph.has_edge("KNOWS", ("person", "alice"), ("person", "bob")));
2281    }
2282
2283    #[test]
2284    fn test_from_isonl() {
2285        let isonl_text = "nodes.person|id name age|alice Alice 30\n\
2286            nodes.person|id name age|bob Bob 25\n\
2287            edges.KNOWS|source target since|:person:alice :person:bob 2020\n";
2288
2289        let graph = ISONGraph::from_isonl(isonl_text, Some("test")).unwrap();
2290        assert_eq!(graph.node_count(), 2);
2291        assert_eq!(graph.edge_count(), 1);
2292        assert!(graph.has_node("person", "alice"));
2293        assert!(graph.has_edge("KNOWS", ("person", "alice"), ("person", "bob")));
2294    }
2295
2296    #[test]
2297    fn test_from_ison_malformed_errors() {
2298        // Row with 3 values against 2 fields
2299        let bad_row = "nodes.person\nid name\nalice Alice Extra";
2300        assert!(matches!(
2301            ISONGraph::from_ison(bad_row, None),
2302            Err(GraphError::ParseError(_))
2303        ));
2304
2305        // Header without '.'
2306        let bad_header = "people\nid name\nalice Alice";
2307        assert!(matches!(
2308            ISONGraph::from_ison(bad_header, None),
2309            Err(GraphError::ParseError(_))
2310        ));
2311
2312        // Unknown block kind
2313        let bad_kind = "vertices.person\nid name\nalice Alice";
2314        assert!(matches!(
2315            ISONGraph::from_ison(bad_kind, None),
2316            Err(GraphError::ParseError(_))
2317        ));
2318    }
2319
2320    #[test]
2321    fn test_from_isonl_malformed_errors() {
2322        // Missing values section
2323        assert!(matches!(
2324            ISONGraph::from_isonl("nodes.person|id name", None),
2325            Err(GraphError::ParseError(_))
2326        ));
2327        // A short row is padded with null by the shared ISON parser rather
2328        // than rejected - every port behaves this way now that emission and
2329        // parsing both go through it, so this is no longer an error here.
2330        let padded = ISONGraph::from_isonl("nodes.person|id name|alice", None).unwrap();
2331        assert_eq!(padded.node_count(), 1);
2332        // Header without '.'
2333        assert!(matches!(
2334            ISONGraph::from_isonl("nodesperson|id|alice", None),
2335            Err(GraphError::ParseError(_))
2336        ));
2337    }
2338
2339    // =========================================================================
2340    // Additional Analysis Tests
2341    // =========================================================================
2342
2343    #[test]
2344    fn test_connected_components() {
2345        let mut graph = ISONGraph::new("test");
2346        graph.add_node("person", "1", props![]).unwrap();
2347        graph.add_node("person", "2", props![]).unwrap();
2348        graph.add_node("person", "3", props![]).unwrap();
2349        graph.add_node("person", "4", props![]).unwrap();
2350        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2351        graph.add_edge("KNOWS", ("person", "3"), ("person", "4"), props![]).unwrap();
2352
2353        let components = graph.connected_components();
2354        assert_eq!(components.len(), 2);
2355    }
2356
2357    #[test]
2358    fn test_all_paths() {
2359        let mut graph = ISONGraph::new("test");
2360        graph.add_node("person", "1", props![]).unwrap();
2361        graph.add_node("person", "2", props![]).unwrap();
2362        graph.add_node("person", "3", props![]).unwrap();
2363        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2364        graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2365        graph.add_edge("KNOWS", ("person", "1"), ("person", "3"), props![]).unwrap();
2366
2367        let paths = graph.all_paths(&("person", "1"), &("person", "3"), None, 5, Direction::Out);
2368        assert_eq!(paths.len(), 2); // Direct path and via person 2
2369    }
2370
2371    #[test]
2372    fn test_get_edge() {
2373        let mut graph = ISONGraph::new("test");
2374        graph.add_node("person", "1", props![]).unwrap();
2375        graph.add_node("person", "2", props![]).unwrap();
2376        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020")]).unwrap();
2377
2378        let edge = graph.get_edge("KNOWS", ("person", "1"), ("person", "2")).unwrap();
2379        assert_eq!(edge.rel_type, "KNOWS");
2380        assert_eq!(crate::value_to_text(edge.properties.get("since").unwrap()), "2020");
2381    }
2382
2383    // =========================================================================
2384    // Pattern Query Tests
2385    // =========================================================================
2386
2387    #[test]
2388    fn test_query_pattern() {
2389        let mut graph = ISONGraph::new("test");
2390        graph.add_node("person", "1", props![]).unwrap();
2391        graph.add_node("person", "2", props![]).unwrap();
2392        graph.add_node("person", "3", props![]).unwrap();
2393        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2394        graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2395
2396        let result = graph.query(":person:1 -[:KNOWS]-> *").unwrap();
2397        assert_eq!(result.len(), 1);
2398        assert_eq!(result[0].id, "2");
2399
2400        let result2 = graph.query(":person:1 -[:KNOWS*2]-> *").unwrap();
2401        assert_eq!(result2.len(), 1);
2402        assert_eq!(result2[0].id, "3");
2403    }
2404
2405    // =========================================================================
2406    // Fluent API Tests
2407    // =========================================================================
2408
2409    #[test]
2410    fn test_start_method() {
2411        let mut graph = ISONGraph::new("test");
2412        graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2413        graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2414        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2415
2416        let result = graph.start(&("person", "1"))
2417            .hop(Some("KNOWS"), Direction::Out)
2418            .collect();
2419
2420        assert_eq!(result.len(), 1);
2421        assert_eq!(result[0].id, "2");
2422    }
2423
2424    #[test]
2425    fn test_fluent_collect_nodes() {
2426        let mut graph = ISONGraph::new("test");
2427        graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2428        graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2429        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2430
2431        let nodes = graph.start(&("person", "1"))
2432            .hop(Some("KNOWS"), Direction::Out)
2433            .collect_nodes();
2434
2435        assert_eq!(nodes.len(), 1);
2436        assert_eq!(crate::value_to_text(nodes[0].properties.get("name").unwrap()), "Bob");
2437    }
2438
2439    #[test]
2440    fn test_fluent_filter() {
2441        let mut graph = ISONGraph::new("test");
2442        graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2443        graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2444        graph.add_node("person", "3", props![("name", "Charlie")]).unwrap();
2445        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2446        graph.add_edge("KNOWS", ("person", "1"), ("person", "3"), props![]).unwrap();
2447
2448        let result = graph.start(&("person", "1"))
2449            .hop(Some("KNOWS"), Direction::Out)
2450            .filter(|n| n.properties.get("name").map(|v| crate::value_to_text(v) == "Bob").unwrap_or(false))
2451            .collect();
2452
2453        assert_eq!(result.len(), 1);
2454        assert_eq!(result[0].id, "2");
2455    }
2456
2457    // =========================================================================
2458    // Cycle / Direction / Dedup Tests
2459    // =========================================================================
2460
2461    #[test]
2462    fn test_undirected_single_edge_no_cycle() {
2463        let mut graph = ISONGraph::undirected("test");
2464        graph.add_node("person", "1", props![]).unwrap();
2465        graph.add_node("person", "2", props![]).unwrap();
2466        graph
2467            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2468            .unwrap();
2469        // A single undirected edge must not be reported as a cycle
2470        assert!(!graph.has_cycle(None));
2471
2472        // A chain of two undirected edges is still acyclic
2473        graph.add_node("person", "3", props![]).unwrap();
2474        graph
2475            .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2476            .unwrap();
2477        assert!(!graph.has_cycle(None));
2478
2479        // Closing the triangle creates a real cycle
2480        graph
2481            .add_edge("KNOWS", ("person", "3"), ("person", "1"), props![])
2482            .unwrap();
2483        assert!(graph.has_cycle(None));
2484    }
2485
2486    #[test]
2487    fn test_directed_cycle_detection() {
2488        let mut graph = ISONGraph::new("test");
2489        graph.add_node("t", "a", props![]).unwrap();
2490        graph.add_node("t", "b", props![]).unwrap();
2491        graph.add_edge("R", ("t", "a"), ("t", "b"), props![]).unwrap();
2492        assert!(!graph.has_cycle(None));
2493        graph.add_edge("R", ("t", "b"), ("t", "a"), props![]).unwrap();
2494        assert!(graph.has_cycle(None));
2495        // Filtering on a rel type with no cycle
2496        assert!(!graph.has_cycle(Some("OTHER")));
2497    }
2498
2499    #[test]
2500    fn test_neighbors_both_undirected_dedup() {
2501        let mut graph = ISONGraph::undirected("test");
2502        graph.add_node("person", "1", props![]).unwrap();
2503        graph.add_node("person", "2", props![]).unwrap();
2504        graph
2505            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2506            .unwrap();
2507
2508        let neighbors = graph.neighbors(&("person", "1"), None, Direction::Both);
2509        assert_eq!(neighbors.len(), 1);
2510        assert_eq!(neighbors[0].id, "2");
2511    }
2512
2513    #[test]
2514    fn test_path_exists_direction() {
2515        let mut graph = ISONGraph::new("test");
2516        graph.add_node("person", "1", props![]).unwrap();
2517        graph.add_node("person", "2", props![]).unwrap();
2518        graph
2519            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2520            .unwrap();
2521
2522        assert!(graph.path_exists(&("person", "1"), &("person", "2"), None, 5, Direction::Out));
2523        assert!(!graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::Out));
2524        assert!(graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::In));
2525        assert!(graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::Both));
2526    }
2527
2528    #[test]
2529    fn test_max_hops_usize_max_no_overflow() {
2530        let mut graph = ISONGraph::new("test");
2531        graph.add_node("person", "1", props![]).unwrap();
2532        graph.add_node("person", "2", props![]).unwrap();
2533        graph
2534            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2535            .unwrap();
2536
2537        assert!(graph.path_exists(
2538            &("person", "1"),
2539            &("person", "2"),
2540            None,
2541            usize::MAX,
2542            Direction::Out
2543        ));
2544        let paths = graph.all_paths(&("person", "1"), &("person", "2"), None, usize::MAX, Direction::Out);
2545        assert_eq!(paths.len(), 1);
2546    }
2547
2548    #[test]
2549    fn test_all_paths_start_equals_end() {
2550        let mut graph = ISONGraph::new("test");
2551        graph.add_node("person", "1", props![]).unwrap();
2552        let paths = graph.all_paths(&("person", "1"), &("person", "1"), None, 5, Direction::Out);
2553        assert_eq!(paths.len(), 1);
2554        assert_eq!(paths[0].length(), 0);
2555    }
2556
2557    // =========================================================================
2558    // Serde Tests
2559    // =========================================================================
2560
2561    #[cfg(feature = "serde")]
2562    #[test]
2563    fn test_serde_round_trip() {
2564        let mut graph = ISONGraph::new("test");
2565        graph
2566            .add_node("person", "1", props![("name", "Alice")])
2567            .unwrap();
2568        graph
2569            .add_node("person", "2", props![("name", "Bob")])
2570            .unwrap();
2571        graph
2572            .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020")])
2573            .unwrap();
2574
2575        let json = serde_json::to_string(&graph).unwrap();
2576        // Internal indexes must not be serialized (every edge only once)
2577        assert!(!json.contains("out_edges"));
2578        assert!(!json.contains("in_edges"));
2579        assert!(!json.contains("edge_set"));
2580
2581        let restored: ISONGraph = serde_json::from_str(&json).unwrap();
2582        assert_eq!(restored.name, "test");
2583        assert_eq!(restored.node_count(), 2);
2584        assert_eq!(restored.edge_count(), 1);
2585        assert!(restored.has_edge("KNOWS", ("person", "1"), ("person", "2")));
2586
2587        // Indexes are rebuilt: traversal works on the deserialized graph
2588        let neighbors = restored.neighbors(&("person", "1"), Some("KNOWS"), Direction::Out);
2589        assert_eq!(neighbors.len(), 1);
2590        assert_eq!(neighbors[0].id, "2");
2591        assert_eq!(restored.in_degree(&("person", "2")), 1);
2592    }
2593
2594    #[test]
2595    fn test_fluent_hops() {
2596        let mut graph = ISONGraph::new("test");
2597        graph.add_node("person", "1", props![]).unwrap();
2598        graph.add_node("person", "2", props![]).unwrap();
2599        graph.add_node("person", "3", props![]).unwrap();
2600        graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2601        graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2602
2603        let count = graph.start(&("person", "1"))
2604            .hops(2, Some("KNOWS"), Direction::Out)
2605            .count();
2606
2607        assert_eq!(count, 1);
2608    }
2609
2610    // =========================================================================
2611    // Canonical Serialization
2612    //
2613    // to_ison()/to_isonl() must be byte-identical for the same logical graph
2614    // regardless of insertion order (node type blocks, node rows, edge type
2615    // blocks, and edge rows are all sorted, ordinal string comparison). The
2616    // golden fixture below is shared verbatim across every ISONGraph
2617    // language port's test suite (Python, JS, TS, Rust, C++, C#) as the
2618    // cross-language byte-identity contract - if it changes here, it must
2619    // change everywhere.
2620    // =========================================================================
2621
2622    const CANONICAL_GOLDEN_ISON: &str = r#"edges.KNOWS
2623since source target weight
2624"2020" :person:1 :person:2 1.75
2625"2021" :person:10 :person:1 0.5
2626
2627edges.WORKS_AT
2628role source target
2629"Lead Engineer" :person:1 :company:acme
2630
2631edges.WORKS_ON
2632hours source target
26333 :person:10 :project:p1
26345 :person:2 :project:p1
2635
2636nodes.company
2637id listed name staff
2638acme false "Acme Corp" 42
2639
2640nodes.person
2641id active age name score
2642"1" true "30" Alice 9.5
2643"10" false "22" Jax -2.25
2644"2" null "25" Bob null
2645
2646nodes.project
2647id budget name tag
2648p1 1250 Alpha a|b"#;
2649
2650    const CANONICAL_GOLDEN_ISONL: &str = r#"edges.KNOWS|since source target weight|"2020" :person:1 :person:2 1.75
2651edges.KNOWS|since source target weight|"2021" :person:10 :person:1 0.5
2652edges.WORKS_AT|role source target|"Lead Engineer" :person:1 :company:acme
2653edges.WORKS_ON|hours source target|3 :person:10 :project:p1
2654edges.WORKS_ON|hours source target|5 :person:2 :project:p1
2655nodes.company|id listed name staff|acme false "Acme Corp" 42
2656nodes.person|id active age name score|"1" true "30" Alice 9.5
2657nodes.person|id active age name score|"10" false "22" Jax -2.25
2658nodes.person|id active age name score|"2" null "25" Bob null
2659nodes.project|id budget name tag|p1 1250 Alpha "a\|b""#;
2660
2661    #[allow(clippy::type_complexity)]
2662    fn build_canonical_fixture(order: usize) -> ISONGraph {
2663        let mut g = ISONGraph::new("fixture");
2664        // Mixed types on purpose: the string ids and string ages pin that a
2665        // value which would reparse as a number stays quoted, while the int,
2666        // float and bool pin that a real number does not. No integral float
2667        // appears - JavaScript cannot originate one, so a shared fixture must
2668        // not ask for it.
2669        let nodes: Vec<(&str, &str, Vec<(&str, Value)>)> = vec![
2670            ("company", "acme", props![("name", "Acme Corp"), ("staff", 42i64), ("listed", false)]),
2671            ("person", "1", props![("name", "Alice"), ("age", "30"), ("score", 9.5f64), ("active", true)]),
2672            ("person", "10", props![("name", "Jax"), ("age", "22"), ("score", -2.25f64), ("active", false)]),
2673            ("person", "2", props![("name", "Bob"), ("age", "25")]),
2674            ("project", "p1", props![("name", "Alpha"), ("tag", "a|b"), ("budget", 1250i64)]),
2675        ];
2676        let edges: Vec<(&str, (&str, &str), (&str, &str), Vec<(&str, Value)>)> = vec![
2677            ("KNOWS", ("person", "10"), ("person", "1"), props![("since", "2021"), ("weight", 0.5f64)]),
2678            ("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020"), ("weight", 1.75f64)]),
2679            ("WORKS_AT", ("person", "1"), ("company", "acme"), props![("role", "Lead Engineer")]),
2680            ("WORKS_ON", ("person", "2"), ("project", "p1"), props![("hours", 5i64)]),
2681            ("WORKS_ON", ("person", "10"), ("project", "p1"), props![("hours", 3i64)]),
2682        ];
2683        let mut n = nodes;
2684        let mut e = edges;
2685        if order != 0 {
2686            n.reverse();
2687            e.reverse();
2688        }
2689        for (t, i, props) in n {
2690            g.add_node(t, i, props).unwrap();
2691        }
2692        for (rel, s, t, props) in e {
2693            g.add_edge(rel, s, t, props).unwrap();
2694        }
2695        g
2696    }
2697
2698    #[test]
2699    fn test_to_ison_independent_of_insertion_order() {
2700        assert_eq!(build_canonical_fixture(0).to_ison(), build_canonical_fixture(1).to_ison());
2701    }
2702
2703    #[test]
2704    fn test_to_isonl_independent_of_insertion_order() {
2705        assert_eq!(build_canonical_fixture(0).to_isonl(), build_canonical_fixture(1).to_isonl());
2706    }
2707
2708    #[test]
2709    fn test_to_ison_matches_golden_fixture() {
2710        assert_eq!(build_canonical_fixture(0).to_ison(), CANONICAL_GOLDEN_ISON);
2711        assert_eq!(build_canonical_fixture(1).to_ison(), CANONICAL_GOLDEN_ISON);
2712    }
2713
2714    #[test]
2715    fn test_to_isonl_matches_golden_fixture() {
2716        assert_eq!(build_canonical_fixture(0).to_isonl(), CANONICAL_GOLDEN_ISONL);
2717        assert_eq!(build_canonical_fixture(1).to_isonl(), CANONICAL_GOLDEN_ISONL);
2718    }
2719
2720    #[test]
2721    fn test_ordinal_not_numeric_sort() {
2722        // "1" < "10" < "2" ordinally.
2723        let ison = build_canonical_fixture(0).to_ison();
2724        let person_block = ison.split("nodes.person
2725").nth(1).unwrap().split("
2726
2727").next().unwrap();
2728        // Ids are quoted because the fixture uses string ids - the canonical
2729        // writer quotes a string that would otherwise reparse as a number, so
2730        // the round trip stays lossless. Strip that to read the order.
2731        let ids: Vec<&str> = person_block
2732            .lines()
2733            .skip(1)
2734            .map(|l| l.split(' ').next().unwrap().trim_matches('"'))
2735            .collect();
2736        assert_eq!(ids, vec!["1", "10", "2"]);
2737    }
2738
2739    #[test]
2740    fn test_roundtrip_preserves_canonical_form() {
2741        let g = build_canonical_fixture(0);
2742        let reloaded = ISONGraph::from_ison(&g.to_ison(), None).unwrap();
2743        assert_eq!(reloaded.to_ison(), g.to_ison());
2744    }
2745}