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