Skip to main content

ison_graph/
lib.rs

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