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