1use 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
31pub 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#[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
75pub 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
89pub 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
101pub const VERSION: &str = env!("CARGO_PKG_VERSION");
103
104pub mod query;
106
107pub mod schema;
109
110pub type NodeRef<'a> = (&'a str, &'a str);
116
117#[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#[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#[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#[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#[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 pub fn length(&self) -> usize {
251 self.edges.len()
252 }
253
254 pub fn start(&self) -> Option<&NodeId> {
256 self.nodes.first()
257 }
258
259 pub fn end(&self) -> Option<&NodeId> {
261 self.nodes.last()
262 }
263}
264
265#[derive(Error, Debug)]
270pub enum GraphError {
271 #[error("Node not found: :{0}:{1}")]
272 NodeNotFound(String, String),
273
274 #[error("Edge not found: {0} -> {1}")]
275 EdgeNotFound(String, String),
276
277 #[error("Duplicate node: :{0}:{1}")]
278 DuplicateNode(String, String),
279
280 #[error("Duplicate edge: {0}")]
281 DuplicateEdge(String),
282
283 #[error("Parse error: {0}")]
284 ParseError(String),
285
286 #[error("{0}")]
287 InvalidIdentifier(String),
288
289 #[error("I/O error: {0}")]
290 Io(#[from] std::io::Error),
291}
292
293pub type Result<T> = std::result::Result<T, GraphError>;
294
295#[derive(Debug)]
310#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
311#[cfg_attr(feature = "serde", serde(try_from = "GraphData"))]
312pub struct ISONGraph {
313 pub name: String,
315
316 pub directed: bool,
318
319 nodes: HashMap<String, HashMap<String, Node>>,
321
322 edges: HashMap<String, Vec<Edge>>,
324
325 #[cfg_attr(feature = "serde", serde(skip))]
328 out_edges: HashMap<String, Vec<Edge>>,
329
330 #[cfg_attr(feature = "serde", serde(skip))]
333 in_edges: HashMap<String, Vec<Edge>>,
334
335 #[cfg_attr(feature = "serde", serde(skip))]
338 edge_set: HashSet<String>,
339}
340
341#[cfg(feature = "serde")]
344#[derive(Deserialize)]
345struct GraphData {
346 name: String,
347 directed: bool,
348 nodes: HashMap<String, HashMap<String, Node>>,
349 edges: HashMap<String, Vec<Edge>>,
350}
351
352#[cfg(feature = "serde")]
353impl TryFrom<GraphData> for ISONGraph {
354 type Error = GraphError;
355
356 fn try_from(data: GraphData) -> Result<Self> {
363 for (node_type, type_nodes) in &data.nodes {
364 ISONGraph::check_identifier("Node type", node_type)?;
365 for node_id in type_nodes.keys() {
366 ISONGraph::check_identifier("Node id", node_id)?;
367 }
368 }
369 for (rel_type, edges) in &data.edges {
370 ISONGraph::check_identifier("Relationship type", rel_type)?;
371 for edge in edges {
372 ISONGraph::check_identifier("Node type", &edge.source.node_type)?;
373 ISONGraph::check_identifier("Node id", &edge.source.id)?;
374 ISONGraph::check_identifier("Node type", &edge.target.node_type)?;
375 ISONGraph::check_identifier("Node id", &edge.target.id)?;
376 }
377 }
378
379 let mut graph = ISONGraph {
380 name: data.name,
381 directed: data.directed,
382 nodes: data.nodes,
383 edges: data.edges,
384 out_edges: HashMap::new(),
385 in_edges: HashMap::new(),
386 edge_set: HashSet::new(),
387 };
388 graph.rebuild_indexes();
389 Ok(graph)
390 }
391}
392
393impl Default for ISONGraph {
394 fn default() -> Self {
395 Self::new("graph")
396 }
397}
398
399impl ISONGraph {
400 pub fn new(name: impl Into<String>) -> Self {
402 Self {
403 name: name.into(),
404 directed: true,
405 nodes: HashMap::new(),
406 edges: HashMap::new(),
407 out_edges: HashMap::new(),
408 in_edges: HashMap::new(),
409 edge_set: HashSet::new(),
410 }
411 }
412
413 pub fn undirected(name: impl Into<String>) -> Self {
415 let mut graph = Self::new(name);
416 graph.directed = false;
417 graph
418 }
419
420 #[cfg(feature = "serde")]
423 fn rebuild_indexes(&mut self) {
424 self.out_edges.clear();
425 self.in_edges.clear();
426 self.edge_set.clear();
427
428 for edges in self.edges.values() {
429 for edge in edges {
430 let edge_key = edge.to_key();
431 if !self.edge_set.insert(edge_key) {
432 continue;
433 }
434 self.out_edges
435 .entry(edge.source.to_key())
436 .or_default()
437 .push(edge.clone());
438 self.in_edges
439 .entry(edge.target.to_key())
440 .or_default()
441 .push(edge.clone());
442 }
443 }
444 }
445
446 fn check_identifier(kind: &str, value: &str) -> Result<()> {
460 let is_type = kind.to_lowercase().contains("type");
463 let bad = value.is_empty()
464 || value.chars().any(|ch| {
465 ch.is_whitespace()
466 || ch == ':'
467 || ch == '|'
468 || (is_type && (ch == '"' || ch == '\\'))
469 });
470 if bad {
471 return Err(GraphError::InvalidIdentifier(format!(
472 "{} {:?} is not representable: it must not be empty or contain \
473 whitespace, ':' or '|'{}",
474 kind,
475 value,
476 if is_type { ", '\"' or '\\'" } else { "" }
477 )));
478 }
479 Ok(())
480 }
481
482 fn check_property_names<'a, I>(kind: &str, names: I) -> Result<()>
489 where
490 I: IntoIterator<Item = &'a str>,
491 {
492 for name in names {
493 let bad = name.is_empty()
494 || name.starts_with('#')
495 || name.chars().any(|ch| {
496 ch.is_whitespace()
497 || ch == ':'
498 || ch == '|'
499 || ch == '"'
500 || ch == '\\'
501 || ch == '.'
502 });
503 if bad {
504 return Err(GraphError::InvalidIdentifier(format!(
505 "{} name {:?} cannot be encoded: property names must not be \
506 empty, start with '#', or contain whitespace, ':', '|', \
507 '\"', '\\' or '.'",
508 kind, name
509 )));
510 }
511 }
512 Ok(())
513 }
514
515 pub fn add_node(
516 &mut self,
517 node_type: &str,
518 node_id: &str,
519 properties: Vec<(&str, Value)>,
520 ) -> Result<&Node> {
521 Self::check_identifier("Node type", node_type)?;
522 Self::check_identifier("Node id", node_id)?;
523 Self::check_property_names("Node property", properties.iter().map(|(k, _)| *k))?;
524
525 let type_nodes = self.nodes.entry(node_type.to_string()).or_default();
526
527 if type_nodes.contains_key(node_id) {
528 return Err(GraphError::DuplicateNode(
529 node_type.to_string(),
530 node_id.to_string(),
531 ));
532 }
533
534 let node = Node::new(node_type, node_id).with_properties(properties);
535 type_nodes.insert(node_id.to_string(), node);
536 Ok(type_nodes.get(node_id).unwrap())
537 }
538
539 pub fn get_node(&self, node_type: &str, node_id: &str) -> Result<&Node> {
541 self.nodes
542 .get(node_type)
543 .and_then(|m| m.get(node_id))
544 .ok_or_else(|| GraphError::NodeNotFound(node_type.to_string(), node_id.to_string()))
545 }
546
547 pub fn get_node_by_id(&self, node_id: &NodeId) -> Result<&Node> {
549 self.get_node(&node_id.node_type, &node_id.id)
550 }
551
552 pub fn has_node(&self, node_type: &str, node_id: &str) -> bool {
554 self.nodes
555 .get(node_type)
556 .map(|m| m.contains_key(node_id))
557 .unwrap_or(false)
558 }
559
560 pub fn remove_node(&mut self, node_type: &str, node_id: &str) -> Result<()> {
562 if !self.has_node(node_type, node_id) {
563 return Err(GraphError::NodeNotFound(
564 node_type.to_string(),
565 node_id.to_string(),
566 ));
567 }
568
569 let node_key = format!("{}:{}", node_type, node_id);
570
571 let out_edges: Vec<Edge> = self.out_edges.get(&node_key).cloned().unwrap_or_default();
573 let in_edges: Vec<Edge> = self.in_edges.get(&node_key).cloned().unwrap_or_default();
574
575 for edge in out_edges.iter().chain(in_edges.iter()) {
576 self.remove_edge_internal(edge);
577 }
578
579 if let Some(type_nodes) = self.nodes.get_mut(node_type) {
581 type_nodes.remove(node_id);
582 if type_nodes.is_empty() {
583 self.nodes.remove(node_type);
584 }
585 }
586
587 Ok(())
588 }
589
590 pub fn update_node(
592 &mut self,
593 node_type: &str,
594 node_id: &str,
595 properties: Vec<(&str, Value)>,
596 ) -> Result<()> {
597 let node = self
598 .nodes
599 .get_mut(node_type)
600 .and_then(|m| m.get_mut(node_id))
601 .ok_or_else(|| GraphError::NodeNotFound(node_type.to_string(), node_id.to_string()))?;
602
603 for (k, v) in properties {
604 node.properties.insert(k.to_string(), v);
605 }
606 Ok(())
607 }
608
609 pub fn nodes(&self) -> impl Iterator<Item = &Node> {
611 self.nodes.values().flat_map(|m| m.values())
612 }
613
614 pub fn nodes_of_type(&self, node_type: &str) -> impl Iterator<Item = &Node> {
616 self.nodes
617 .get(node_type)
618 .into_iter()
619 .flat_map(|m| m.values())
620 }
621
622 pub fn node_count(&self) -> usize {
624 self.nodes.values().map(|m| m.len()).sum()
625 }
626
627 pub fn node_count_of_type(&self, node_type: &str) -> usize {
629 self.nodes.get(node_type).map(|m| m.len()).unwrap_or(0)
630 }
631
632 pub fn node_types(&self) -> Vec<&String> {
634 self.nodes.keys().collect()
635 }
636
637 pub fn add_edge(
643 &mut self,
644 rel_type: &str,
645 source: (&str, &str),
646 target: (&str, &str),
647 properties: Vec<(&str, Value)>,
648 ) -> Result<()> {
649 Self::check_identifier("Relationship type", rel_type)?;
650 Self::check_property_names("Edge property", properties.iter().map(|(k, _)| *k))?;
651
652 if !self.has_node(source.0, source.1) {
654 return Err(GraphError::NodeNotFound(
655 source.0.to_string(),
656 source.1.to_string(),
657 ));
658 }
659 if !self.has_node(target.0, target.1) {
660 return Err(GraphError::NodeNotFound(
661 target.0.to_string(),
662 target.1.to_string(),
663 ));
664 }
665
666 let source_id = NodeId::new(source.0, source.1);
667 let target_id = NodeId::new(target.0, target.1);
668 let edge = Edge::new(rel_type, source_id.clone(), target_id.clone()).with_properties(properties.clone());
669 let edge_key = edge.to_key();
670
671 if self.edge_set.contains(&edge_key) {
672 return Err(GraphError::DuplicateEdge(edge_key));
673 }
674
675 self.edges
677 .entry(rel_type.to_string())
678 .or_default()
679 .push(edge.clone());
680
681 let source_key = source_id.to_key();
682 let target_key = target_id.to_key();
683
684 self.out_edges
685 .entry(source_key.clone())
686 .or_default()
687 .push(edge.clone());
688 self.in_edges
689 .entry(target_key.clone())
690 .or_default()
691 .push(edge.clone());
692
693 self.edge_set.insert(edge_key);
694
695 if !self.directed {
697 let reverse_edge = Edge::new(rel_type, target_id.clone(), source_id.clone())
698 .with_properties(properties);
699 let reverse_key = reverse_edge.to_key();
700
701 if !self.edge_set.contains(&reverse_key) {
702 self.edges
703 .entry(rel_type.to_string())
704 .or_default()
705 .push(reverse_edge.clone());
706 self.out_edges
707 .entry(target_key)
708 .or_default()
709 .push(reverse_edge.clone());
710 self.in_edges
711 .entry(source_key)
712 .or_default()
713 .push(reverse_edge);
714 self.edge_set.insert(reverse_key);
715 }
716 }
717
718 Ok(())
719 }
720
721 fn remove_edge_internal(&mut self, edge: &Edge) {
722 let edge_key = edge.to_key();
723 if !self.edge_set.contains(&edge_key) {
724 return;
725 }
726
727 self.edge_set.remove(&edge_key);
728
729 if let Some(rel_edges) = self.edges.get_mut(&edge.rel_type) {
731 rel_edges.retain(|e| e.to_key() != edge_key);
732 }
733
734 let source_key = edge.source.to_key();
736 if let Some(out) = self.out_edges.get_mut(&source_key) {
737 out.retain(|e| e.to_key() != edge_key);
738 }
739
740 let target_key = edge.target.to_key();
742 if let Some(in_e) = self.in_edges.get_mut(&target_key) {
743 in_e.retain(|e| e.to_key() != edge_key);
744 }
745 }
746
747 pub fn remove_edge(
749 &mut self,
750 rel_type: &str,
751 source: (&str, &str),
752 target: (&str, &str),
753 ) -> Result<()> {
754 let source_id = NodeId::new(source.0, source.1);
755 let target_id = NodeId::new(target.0, target.1);
756 let edge = Edge::new(rel_type, source_id, target_id);
757 let edge_key = edge.to_key();
758
759 if !self.edge_set.contains(&edge_key) {
760 return Err(GraphError::EdgeNotFound(
761 format!("{}:{}", source.0, source.1),
762 format!("{}:{}", target.0, target.1),
763 ));
764 }
765
766 self.remove_edge_internal(&edge);
767 Ok(())
768 }
769
770 pub fn has_edge(&self, rel_type: &str, source: (&str, &str), target: (&str, &str)) -> bool {
772 let source_id = NodeId::new(source.0, source.1);
773 let target_id = NodeId::new(target.0, target.1);
774 let edge = Edge::new(rel_type, source_id, target_id);
775 self.edge_set.contains(&edge.to_key())
776 }
777
778 pub fn edge_count(&self) -> usize {
780 self.edge_set.len()
781 }
782
783 pub fn edge_count_of_type(&self, rel_type: &str) -> usize {
785 self.edges.get(rel_type).map(|v| v.len()).unwrap_or(0)
786 }
787
788 pub fn edge_types(&self) -> Vec<&String> {
790 self.edges.keys().collect()
791 }
792
793 pub fn edges_of_type(&self, rel_type: &str) -> impl Iterator<Item = &Edge> {
795 self.edges.get(rel_type).into_iter().flatten()
796 }
797
798 pub fn has_cycle(&self, rel_type: Option<&str>) -> bool {
800 let mut visited = HashSet::new();
802
803 for node_types in self.nodes.values() {
804 for node in node_types.values() {
805 let node_key = format!("{}:{}", node.node_type, node.id);
806 if !visited.contains(&node_key)
807 && self.has_cycle_from(&node_key, &mut visited, rel_type)
808 {
809 return true;
810 }
811 }
812 }
813 false
814 }
815
816 fn cycle_successors(
823 &self,
824 node_key: &str,
825 rel_type: Option<&str>,
826 skip: Option<(&str, &str)>,
827 ) -> Vec<(String, String)> {
828 let mut result = Vec::new();
829 let mut skip_remaining = if self.directed { None } else { skip };
830
831 if let Some(edges) = self.out_edges.get(node_key) {
832 for edge in edges {
833 if rel_type.is_some() && rel_type != Some(edge.rel_type.as_str()) {
834 continue;
835 }
836 let target_key = edge.target.to_key();
837 if let Some((skip_rel, skip_key)) = skip_remaining {
838 if edge.rel_type == skip_rel && target_key == skip_key {
839 skip_remaining = None;
840 continue;
841 }
842 }
843 result.push((target_key, edge.rel_type.clone()));
844 }
845 }
846 result
847 }
848
849 fn has_cycle_from(
850 &self,
851 start_key: &str,
852 visited: &mut HashSet<String>,
853 rel_type: Option<&str>,
854 ) -> bool {
855 struct Frame {
856 key: String,
857 successors: Vec<(String, String)>,
858 idx: usize,
859 }
860
861 let mut rec_stack: HashSet<String> = HashSet::new();
862 visited.insert(start_key.to_string());
863 rec_stack.insert(start_key.to_string());
864
865 let mut stack = vec![Frame {
866 key: start_key.to_string(),
867 successors: self.cycle_successors(start_key, rel_type, None),
868 idx: 0,
869 }];
870
871 while !stack.is_empty() {
872 let next = {
873 let frame = stack.last_mut().unwrap();
874 if frame.idx < frame.successors.len() {
875 let (target_key, edge_rel) = frame.successors[frame.idx].clone();
876 frame.idx += 1;
877 Some((target_key, edge_rel, frame.key.clone()))
878 } else {
879 None
880 }
881 };
882
883 match next {
884 Some((target_key, edge_rel, from_key)) => {
885 if !visited.contains(&target_key) {
886 visited.insert(target_key.clone());
887 rec_stack.insert(target_key.clone());
888 let successors =
889 self.cycle_successors(&target_key, rel_type, Some((&edge_rel, &from_key)));
890 stack.push(Frame {
891 key: target_key,
892 successors,
893 idx: 0,
894 });
895 } else if rec_stack.contains(&target_key) {
896 return true;
897 }
898 }
899 None => {
900 let frame = stack.pop().unwrap();
901 rec_stack.remove(&frame.key);
902 }
903 }
904 }
905
906 false
907 }
908
909 pub fn neighbors(
920 &self,
921 node_ref: &NodeRef,
922 rel_type: Option<&str>,
923 direction: Direction,
924 ) -> Vec<NodeId> {
925 let mut neighbors = Vec::new();
926 let mut seen: HashSet<String> = HashSet::new();
927 let node_key = format!("{}:{}", node_ref.0, node_ref.1);
928
929 if direction == Direction::Out || direction == Direction::Both {
930 if let Some(edges) = self.out_edges.get(&node_key) {
931 for edge in edges {
932 if (rel_type.is_none() || rel_type == Some(&edge.rel_type))
933 && seen.insert(edge.target.to_key())
934 {
935 neighbors.push(edge.target.clone());
936 }
937 }
938 }
939 }
940
941 if direction == Direction::In || direction == Direction::Both {
942 if let Some(edges) = self.in_edges.get(&node_key) {
943 for edge in edges {
944 if (rel_type.is_none() || rel_type == Some(&edge.rel_type))
945 && seen.insert(edge.source.to_key())
946 {
947 neighbors.push(edge.source.clone());
948 }
949 }
950 }
951 }
952
953 neighbors
954 }
955
956 pub fn multi_hop(
958 &self,
959 start: &NodeRef,
960 rel_type: Option<&str>,
961 hops: usize,
962 direction: Direction,
963 ) -> Vec<NodeId> {
964 if hops == 0 {
965 return vec![NodeId::new(start.0, start.1)];
966 }
967
968 let start_key = format!("{}:{}", start.0, start.1);
969 let mut current: HashSet<String> = HashSet::new();
970 current.insert(start_key.clone());
971
972 let mut visited: HashSet<String> = HashSet::new();
973 visited.insert(start_key);
974
975 let mut ref_map: HashMap<String, NodeId> = HashMap::new();
976 ref_map.insert(
977 format!("{}:{}", start.0, start.1),
978 NodeId::new(start.0, start.1),
979 );
980
981 for _ in 0..hops {
982 let mut next_level: HashSet<String> = HashSet::new();
983
984 for key in ¤t {
985 if let Some(node_id) = ref_map.get(key) {
986 let neighbors = self.neighbors(&node_id.as_ref(), rel_type, direction);
987 for neighbor in neighbors {
988 let neighbor_key = neighbor.to_key();
989 if !visited.contains(&neighbor_key) {
990 next_level.insert(neighbor_key.clone());
991 ref_map.insert(neighbor_key.clone(), neighbor);
992 }
993 }
994 }
995 }
996
997 for key in &next_level {
998 visited.insert(key.clone());
999 }
1000 current = next_level;
1001 }
1002
1003 current
1004 .iter()
1005 .filter_map(|key| ref_map.get(key).cloned())
1006 .collect()
1007 }
1008
1009 pub fn multi_hop_range(
1011 &self,
1012 start: &NodeRef,
1013 rel_type: Option<&str>,
1014 min_hops: usize,
1015 max_hops: usize,
1016 direction: Direction,
1017 ) -> Vec<NodeId> {
1018 let start_key = format!("{}:{}", start.0, start.1);
1019 let mut result: HashSet<String> = HashSet::new();
1020 let mut current: HashSet<String> = HashSet::new();
1021 current.insert(start_key.clone());
1022
1023 let mut visited: HashSet<String> = HashSet::new();
1024 visited.insert(start_key);
1025
1026 let mut ref_map: HashMap<String, NodeId> = HashMap::new();
1027 ref_map.insert(
1028 format!("{}:{}", start.0, start.1),
1029 NodeId::new(start.0, start.1),
1030 );
1031
1032 for hop in 1..=max_hops {
1033 let mut next_level: HashSet<String> = HashSet::new();
1034
1035 for key in ¤t {
1036 if let Some(node_id) = ref_map.get(key) {
1037 let neighbors = self.neighbors(&node_id.as_ref(), rel_type, direction);
1038 for neighbor in neighbors {
1039 let neighbor_key = neighbor.to_key();
1040 if !visited.contains(&neighbor_key) {
1041 next_level.insert(neighbor_key.clone());
1042 ref_map.insert(neighbor_key.clone(), neighbor);
1043 if hop >= min_hops {
1044 result.insert(neighbor_key);
1045 }
1046 }
1047 }
1048 }
1049 }
1050
1051 for key in &next_level {
1052 visited.insert(key.clone());
1053 }
1054 current = next_level;
1055
1056 if current.is_empty() {
1057 break;
1058 }
1059 }
1060
1061 result
1062 .iter()
1063 .filter_map(|key| ref_map.get(key).cloned())
1064 .collect()
1065 }
1066
1067 pub fn shortest_path(
1073 &self,
1074 start: &NodeRef,
1075 end: &NodeRef,
1076 rel_type: Option<&str>,
1077 max_hops: usize,
1078 direction: Direction,
1079 ) -> Option<Path> {
1080 let start_id = NodeId::new(start.0, start.1);
1081 let end_id = NodeId::new(end.0, end.1);
1082
1083 if start_id == end_id {
1084 return Some(Path::new(vec![start_id], vec![]));
1085 }
1086
1087 let end_key = end_id.to_key();
1088 let mut visited: HashSet<String> = HashSet::new();
1089 visited.insert(start_id.to_key());
1090
1091 let mut queue: VecDeque<(NodeId, Vec<NodeId>, Vec<Edge>)> = VecDeque::new();
1092 queue.push_back((start_id.clone(), vec![start_id], vec![]));
1093
1094 while let Some((current, path_nodes, path_edges)) = queue.pop_front() {
1095 if path_nodes.len() > max_hops.saturating_add(1) {
1096 continue;
1097 }
1098
1099 let current_key = current.to_key();
1100
1101 if direction != Direction::In {
1102 if let Some(edges) = self.out_edges.get(¤t_key) {
1103 for edge in edges {
1104 if rel_type.is_some() && rel_type != Some(&edge.rel_type) {
1105 continue;
1106 }
1107
1108 let target_key = edge.target.to_key();
1109 if target_key == end_key {
1110 let mut nodes = path_nodes.clone();
1111 nodes.push(edge.target.clone());
1112 let mut edges = path_edges.clone();
1113 edges.push(edge.clone());
1114 return Some(Path::new(nodes, edges));
1115 }
1116
1117 if !visited.contains(&target_key) {
1118 visited.insert(target_key);
1119 let mut nodes = path_nodes.clone();
1120 nodes.push(edge.target.clone());
1121 let mut edges = path_edges.clone();
1122 edges.push(edge.clone());
1123 queue.push_back((edge.target.clone(), nodes, edges));
1124 }
1125 }
1126 }
1127 }
1128
1129 if direction == Direction::In || direction == Direction::Both {
1130 if let Some(edges) = self.in_edges.get(¤t_key) {
1131 for edge in edges {
1132 if rel_type.is_some() && rel_type != Some(&edge.rel_type) {
1133 continue;
1134 }
1135
1136 let source_key = edge.source.to_key();
1137 if source_key == end_key {
1138 let mut nodes = path_nodes.clone();
1139 nodes.push(edge.source.clone());
1140 let mut edges = path_edges.clone();
1141 edges.push(edge.clone());
1142 return Some(Path::new(nodes, edges));
1143 }
1144
1145 if !visited.contains(&source_key) {
1146 visited.insert(source_key);
1147 let mut nodes = path_nodes.clone();
1148 nodes.push(edge.source.clone());
1149 let mut edges = path_edges.clone();
1150 edges.push(edge.clone());
1151 queue.push_back((edge.source.clone(), nodes, edges));
1152 }
1153 }
1154 }
1155 }
1156 }
1157
1158 None
1159 }
1160
1161 pub fn path_exists(
1163 &self,
1164 start: &NodeRef,
1165 end: &NodeRef,
1166 rel_type: Option<&str>,
1167 max_hops: usize,
1168 direction: Direction,
1169 ) -> bool {
1170 self.shortest_path(start, end, rel_type, max_hops, direction)
1171 .is_some()
1172 }
1173
1174 pub fn in_degree(&self, node_ref: &NodeRef) -> usize {
1180 let key = format!("{}:{}", node_ref.0, node_ref.1);
1181 self.in_edges.get(&key).map(|v| v.len()).unwrap_or(0)
1182 }
1183
1184 pub fn out_degree(&self, node_ref: &NodeRef) -> usize {
1186 let key = format!("{}:{}", node_ref.0, node_ref.1);
1187 self.out_edges.get(&key).map(|v| v.len()).unwrap_or(0)
1188 }
1189
1190 pub fn degree(&self, node_ref: &NodeRef) -> usize {
1192 self.in_degree(node_ref) + self.out_degree(node_ref)
1193 }
1194
1195 pub fn is_connected(&self) -> bool {
1197 let all_nodes: Vec<_> = self.nodes().collect();
1198 if all_nodes.is_empty() {
1199 return true;
1200 }
1201
1202 let start = &all_nodes[0];
1203 let start_key = start.to_key();
1204 let mut visited: HashSet<String> = HashSet::new();
1205 visited.insert(start_key.clone());
1206
1207 let mut queue: VecDeque<String> = VecDeque::new();
1208 queue.push_back(start_key);
1209
1210 while let Some(current_key) = queue.pop_front() {
1211 let parts: Vec<&str> = current_key.split(':').collect();
1213 if parts.len() == 2 {
1214 let neighbors = self.neighbors(&(parts[0], parts[1]), None, Direction::Both);
1215 for neighbor in neighbors {
1216 let neighbor_key = neighbor.to_key();
1217 if !visited.contains(&neighbor_key) {
1218 visited.insert(neighbor_key.clone());
1219 queue.push_back(neighbor_key);
1220 }
1221 }
1222 }
1223 }
1224
1225 visited.len() == all_nodes.len()
1226 }
1227
1228 fn document(&self) -> IsonDocument {
1251 let mut doc = IsonDocument::new();
1252
1253 let mut node_types: Vec<_> = self.nodes.keys().collect();
1254 node_types.sort();
1255 for node_type in node_types {
1256 let type_nodes = &self.nodes[node_type];
1257 if type_nodes.is_empty() {
1258 continue;
1259 }
1260
1261 let mut prop_keys: Vec<&String> = type_nodes
1262 .values()
1263 .flat_map(|n| n.properties.keys())
1264 .collect::<HashSet<_>>()
1265 .into_iter()
1266 .collect();
1267 prop_keys.sort();
1268
1269 let mut block = IsonBlock::new("nodes", node_type.as_str());
1270 block.fields = std::iter::once("id".to_string())
1271 .chain(prop_keys.iter().map(|k| (*k).clone()))
1272 .collect();
1273
1274 for node in type_nodes.values() {
1275 let mut row: HashMap<String, IsonValue> = HashMap::new();
1276 row.insert("id".to_string(), IsonValue::String(node.id.clone()));
1277 for key in &prop_keys {
1278 let value = match node.properties.get(*key) {
1279 Some(v) => v.clone(),
1280 None => IsonValue::Null,
1281 };
1282 row.insert((*key).clone(), value);
1283 }
1284 block.rows.push(row);
1285 }
1286 doc.blocks.push(block);
1287 }
1288
1289 let mut edge_types: Vec<_> = self.edges.keys().collect();
1290 edge_types.sort();
1291 for rel_type in edge_types {
1292 let edges = &self.edges[rel_type];
1293 if edges.is_empty() {
1294 continue;
1295 }
1296
1297 let mut prop_keys: Vec<&String> = edges
1298 .iter()
1299 .flat_map(|e| e.properties.keys())
1300 .collect::<HashSet<_>>()
1301 .into_iter()
1302 .collect();
1303 prop_keys.sort();
1304
1305 let mut block = IsonBlock::new("edges", rel_type.as_str());
1306 block.fields = ["source".to_string(), "target".to_string()]
1307 .into_iter()
1308 .chain(prop_keys.iter().map(|k| (*k).clone()))
1309 .collect();
1310
1311 for edge in edges {
1312 let mut row: HashMap<String, IsonValue> = HashMap::new();
1313 row.insert(
1314 "source".to_string(),
1315 IsonValue::Reference(IsonReference::with_type(
1316 edge.source.id.clone(),
1317 edge.source.node_type.clone(),
1318 )),
1319 );
1320 row.insert(
1321 "target".to_string(),
1322 IsonValue::Reference(IsonReference::with_type(
1323 edge.target.id.clone(),
1324 edge.target.node_type.clone(),
1325 )),
1326 );
1327 for key in &prop_keys {
1328 let value = match edge.properties.get(*key) {
1329 Some(v) => v.clone(),
1330 None => IsonValue::Null,
1331 };
1332 row.insert((*key).clone(), value);
1333 }
1334 block.rows.push(row);
1335 }
1336 doc.blocks.push(block);
1337 }
1338
1339 doc
1340 }
1341
1342 pub fn to_ison(&self) -> String {
1348 dumps_canonical(&self.document()).unwrap_or_default()
1349 }
1350
1351 pub fn to_isonl(&self) -> String {
1353 dumps_canonical_isonl(&self.document()).unwrap_or_default()
1354 }
1355
1356
1357 fn id_text(value: &IsonValue) -> Option<String> {
1360 match value {
1361 IsonValue::Null => None,
1362 IsonValue::Bool(b) => Some(b.to_string()),
1363 IsonValue::Int(i) => Some(i.to_string()),
1364 IsonValue::Float(f) => Some(f.to_string()),
1365 IsonValue::String(s) => Some(s.clone()),
1366 IsonValue::Reference(r) => Some(r.to_ison()),
1367 }
1368 }
1369
1370 fn build_from_document(doc: &IsonDocument, name: &str) -> Result<Self> {
1371 let mut graph = ISONGraph::new(name);
1372
1373 for block in &doc.blocks {
1374 if block.kind != "nodes" && block.kind != "edges" {
1375 return Err(GraphError::ParseError(format!(
1376 "unknown block kind {:?} (expected 'nodes' or 'edges')",
1377 block.kind
1378 )));
1379 }
1380 }
1381
1382 for block in &doc.blocks {
1385 if block.kind != "nodes" {
1386 continue;
1387 }
1388 for row in &block.rows {
1389 let id = row
1392 .get("id")
1393 .and_then(Self::id_text)
1394 .ok_or_else(|| GraphError::ParseError("row has no id".into()))?;
1395 let props: Vec<(String, Value)> = row
1396 .iter()
1397 .filter(|(k, _)| k.as_str() != "id")
1398 .map(|(k, v)| (k.clone(), v.clone()))
1399 .collect();
1400 let borrowed: Vec<(&str, Value)> =
1401 props.iter().map(|(k, v)| (k.as_str(), v.clone())).collect();
1402 graph.add_node(&block.name, &id, borrowed)?;
1403 }
1404 }
1405
1406 for block in &doc.blocks {
1407 if block.kind != "edges" {
1408 continue;
1409 }
1410 for row in &block.rows {
1411 let (source, target) = match (row.get("source"), row.get("target")) {
1412 (Some(IsonValue::Reference(s)), Some(IsonValue::Reference(t))) => (
1413 (s.ref_type.clone().unwrap_or_default(), s.id.clone()),
1414 (t.ref_type.clone().unwrap_or_default(), t.id.clone()),
1415 ),
1416 _ => {
1417 return Err(GraphError::ParseError(
1418 "edge row is missing a source or target reference".into(),
1419 ))
1420 }
1421 };
1422 let props: Vec<(String, Value)> = row
1423 .iter()
1424 .filter(|(k, _)| k.as_str() != "source" && k.as_str() != "target")
1425 .map(|(k, v)| (k.clone(), v.clone()))
1426 .collect();
1427 let borrowed: Vec<(&str, Value)> =
1428 props.iter().map(|(k, v)| (k.as_str(), v.clone())).collect();
1429 graph.add_edge(
1430 &block.name,
1431 (&source.0, &source.1),
1432 (&target.0, &target.1),
1433 borrowed,
1434 )?;
1435 }
1436 }
1437
1438 Ok(graph)
1439 }
1440
1441 pub fn from_ison(text: &str, name: Option<&str>) -> Result<Self> {
1443 let doc = loads(text)
1444 .map_err(|e| GraphError::ParseError(format!("{}", e)))?;
1445 Self::build_from_document(&doc, name.unwrap_or("graph"))
1446 }
1447
1448 pub fn from_isonl(text: &str, name: Option<&str>) -> Result<Self> {
1450 let doc = loads_isonl(text)
1451 .map_err(|e| GraphError::ParseError(format!("{}", e)))?;
1452 Self::build_from_document(&doc, name.unwrap_or("graph"))
1453 }
1454
1455 pub fn save<P: AsRef<StdPath>>(&self, path: P, format: Option<&str>) -> Result<()> {
1456 let path = path.as_ref();
1457 let actual_format = format.unwrap_or_else(|| {
1458 if path.extension().map(|e| e == "isonl").unwrap_or(false) {
1459 "isonl"
1460 } else {
1461 "ison"
1462 }
1463 });
1464
1465 let content = if actual_format == "isonl" {
1466 self.to_isonl()
1467 } else {
1468 self.to_ison()
1469 };
1470
1471 fs::write(path, content).map_err(GraphError::Io)
1472 }
1473
1474 pub fn load<P: AsRef<StdPath>>(path: P, format: Option<&str>) -> Result<Self> {
1476 let path = path.as_ref();
1477 let content = fs::read_to_string(path).map_err(GraphError::Io)?;
1478
1479 let actual_format = format.unwrap_or_else(|| {
1480 if path.extension().map(|e| e == "isonl").unwrap_or(false) {
1481 "isonl"
1482 } else {
1483 "ison"
1484 }
1485 });
1486
1487 let graph_name = path.file_stem().and_then(|s| s.to_str()).unwrap_or("graph");
1488
1489 if actual_format == "isonl" {
1490 Self::from_isonl(&content, Some(graph_name))
1491 } else {
1492 Self::from_ison(&content, Some(graph_name))
1493 }
1494 }
1495
1496 pub fn get_edge(&self, rel_type: &str, source: (&str, &str), target: (&str, &str)) -> Result<&Edge> {
1502 let source_id = NodeId::new(source.0, source.1);
1503 let target_id = NodeId::new(target.0, target.1);
1504
1505 if let Some(edges) = self.edges.get(rel_type) {
1506 for edge in edges {
1507 if edge.source == source_id && edge.target == target_id {
1508 return Ok(edge);
1509 }
1510 }
1511 }
1512
1513 Err(GraphError::EdgeNotFound(
1514 format!("{}:{}", source.0, source.1),
1515 format!("{}:{}", target.0, target.1),
1516 ))
1517 }
1518
1519 pub fn connected_components(&self) -> Vec<HashSet<NodeId>> {
1525 let mut visited: HashSet<String> = HashSet::new();
1526 let mut components: Vec<HashSet<NodeId>> = Vec::new();
1527
1528 for node in self.nodes() {
1529 let node_key = node.to_key();
1530 if !visited.contains(&node_key) {
1531 let mut component: HashSet<NodeId> = HashSet::new();
1532 let mut queue: VecDeque<NodeId> = VecDeque::new();
1533 queue.push_back(node.node_id());
1534
1535 while let Some(current) = queue.pop_front() {
1536 let current_key = current.to_key();
1537 if visited.contains(¤t_key) {
1538 continue;
1539 }
1540 visited.insert(current_key);
1541 component.insert(current.clone());
1542
1543 let neighbors = self.neighbors(¤t.as_ref(), None, Direction::Both);
1545 for neighbor in neighbors {
1546 if !visited.contains(&neighbor.to_key()) {
1547 queue.push_back(neighbor);
1548 }
1549 }
1550 }
1551
1552 components.push(component);
1553 }
1554 }
1555
1556 components
1557 }
1558
1559 fn edges_to_follow(
1561 &self,
1562 node: &NodeId,
1563 rel_type: Option<&str>,
1564 direction: Direction,
1565 ) -> Vec<(Edge, NodeId)> {
1566 let node_key = node.to_key();
1567 let mut edges_to_follow: Vec<(Edge, NodeId)> = Vec::new();
1568
1569 if direction == Direction::Out || direction == Direction::Both {
1570 if let Some(out_edges) = self.out_edges.get(&node_key) {
1571 for edge in out_edges {
1572 if rel_type.is_none() || rel_type == Some(&edge.rel_type) {
1573 edges_to_follow.push((edge.clone(), edge.target.clone()));
1574 }
1575 }
1576 }
1577 }
1578
1579 if direction == Direction::In || direction == Direction::Both {
1580 if let Some(in_edges) = self.in_edges.get(&node_key) {
1581 for edge in in_edges {
1582 if rel_type.is_none() || rel_type == Some(&edge.rel_type) {
1583 edges_to_follow.push((edge.clone(), edge.source.clone()));
1584 }
1585 }
1586 }
1587 }
1588
1589 edges_to_follow
1590 }
1591
1592 pub fn all_paths(
1594 &self,
1595 start: &NodeRef,
1596 end: &NodeRef,
1597 rel_type: Option<&str>,
1598 max_hops: usize,
1599 direction: Direction,
1600 ) -> Vec<Path> {
1601 let start_id = NodeId::new(start.0, start.1);
1602 let end_id = NodeId::new(end.0, end.1);
1603 let mut paths: Vec<Path> = Vec::new();
1604
1605 let mut visited: HashSet<String> = HashSet::new();
1606 visited.insert(start_id.to_key());
1607 let mut path_nodes = vec![start_id.clone()];
1608 let mut path_edges: Vec<Edge> = Vec::new();
1609
1610 if start_id == end_id {
1611 paths.push(Path::new(path_nodes, path_edges));
1612 return paths;
1613 }
1614
1615 struct Frame {
1616 options: Vec<(Edge, NodeId)>,
1617 idx: usize,
1618 }
1619
1620 let mut stack = vec![Frame {
1621 options: self.edges_to_follow(&start_id, rel_type, direction),
1622 idx: 0,
1623 }];
1624
1625 while !stack.is_empty() {
1626 let next = {
1627 let frame = stack.last_mut().unwrap();
1628 if frame.idx < frame.options.len() {
1629 let option = frame.options[frame.idx].clone();
1630 frame.idx += 1;
1631 Some(option)
1632 } else {
1633 None
1634 }
1635 };
1636
1637 match next {
1638 Some((edge, next_node)) => {
1639 let next_key = next_node.to_key();
1640 if visited.contains(&next_key) {
1641 continue;
1642 }
1643
1644 visited.insert(next_key.clone());
1645 path_nodes.push(next_node.clone());
1646 path_edges.push(edge);
1647
1648 if path_nodes.len() > max_hops.saturating_add(1) {
1649 path_nodes.pop();
1651 path_edges.pop();
1652 visited.remove(&next_key);
1653 continue;
1654 }
1655
1656 if next_node == end_id {
1657 paths.push(Path::new(path_nodes.clone(), path_edges.clone()));
1658 path_nodes.pop();
1659 path_edges.pop();
1660 visited.remove(&next_key);
1661 continue;
1662 }
1663
1664 stack.push(Frame {
1665 options: self.edges_to_follow(&next_node, rel_type, direction),
1666 idx: 0,
1667 });
1668 }
1669 None => {
1670 stack.pop();
1671 if !stack.is_empty() {
1674 if let Some(popped) = path_nodes.pop() {
1675 path_edges.pop();
1676 visited.remove(&popped.to_key());
1677 }
1678 }
1679 }
1680 }
1681 }
1682
1683 paths
1684 }
1685
1686 pub fn traverse(
1692 &self,
1693 start: &NodeRef,
1694 pattern: &[(String, Direction)],
1695 filter_fn: Option<&dyn Fn(&Node) -> bool>,
1696 ) -> Vec<NodeId> {
1697 let start_id = NodeId::new(start.0, start.1);
1698 let mut current: HashSet<String> = HashSet::new();
1699 current.insert(start_id.to_key());
1700
1701 let mut ref_map: HashMap<String, NodeId> = HashMap::new();
1702 ref_map.insert(start_id.to_key(), start_id);
1703
1704 for (rel_type, direction) in pattern {
1705 let mut next_level: HashSet<String> = HashSet::new();
1706
1707 for key in ¤t {
1708 if let Some(node_id) = ref_map.get(key) {
1709 let neighbors = self.neighbors(&node_id.as_ref(), Some(rel_type), *direction);
1710 for neighbor in neighbors {
1711 let neighbor_key = neighbor.to_key();
1712
1713 let should_include = match filter_fn {
1714 None => true,
1715 Some(f) => {
1716 if let Ok(node) = self.get_node_by_id(&neighbor) {
1717 f(node)
1718 } else {
1719 false
1720 }
1721 }
1722 };
1723
1724 if should_include {
1725 next_level.insert(neighbor_key.clone());
1726 ref_map.insert(neighbor_key, neighbor);
1727 }
1728 }
1729 }
1730 }
1731
1732 current = next_level;
1733 if current.is_empty() {
1734 break;
1735 }
1736 }
1737
1738 current
1739 .iter()
1740 .filter_map(|key| ref_map.get(key).cloned())
1741 .collect()
1742 }
1743
1744 pub fn query(&self, pattern: &str) -> Result<Vec<NodeId>> {
1755 static HOP_REGEX: OnceLock<Regex> = OnceLock::new();
1756 static RANGE_REGEX: OnceLock<Regex> = OnceLock::new();
1757 static SIMPLE_REGEX: OnceLock<Regex> = OnceLock::new();
1758
1759 let p = pattern.trim();
1760
1761 let hop_regex = HOP_REGEX.get_or_init(|| {
1763 Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\*(\d+)\]->\s*\*$").unwrap()
1764 });
1765 if let Some(caps) = hop_regex.captures(p) {
1766 let node_type = caps.get(1).unwrap().as_str();
1767 let node_id = caps.get(2).unwrap().as_str();
1768 let rel_type = caps.get(3).unwrap().as_str();
1769 let hops: usize = caps.get(4).unwrap().as_str().parse().unwrap_or(1);
1770 return Ok(self.multi_hop(&(node_type, node_id), Some(rel_type), hops, Direction::Out));
1771 }
1772
1773 let range_regex = RANGE_REGEX.get_or_init(|| {
1775 Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\*(\d+)\.\.(\d+)\]->\s*\*$").unwrap()
1776 });
1777 if let Some(caps) = range_regex.captures(p) {
1778 let node_type = caps.get(1).unwrap().as_str();
1779 let node_id = caps.get(2).unwrap().as_str();
1780 let rel_type = caps.get(3).unwrap().as_str();
1781 let min_hops: usize = caps.get(4).unwrap().as_str().parse().unwrap_or(1);
1782 let max_hops: usize = caps.get(5).unwrap().as_str().parse().unwrap_or(3);
1783 return Ok(self.multi_hop_range(
1784 &(node_type, node_id),
1785 Some(rel_type),
1786 min_hops,
1787 max_hops,
1788 Direction::Out,
1789 ));
1790 }
1791
1792 let simple_regex = SIMPLE_REGEX
1794 .get_or_init(|| Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\]->\s*\*$").unwrap());
1795 if let Some(caps) = simple_regex.captures(p) {
1796 let node_type = caps.get(1).unwrap().as_str();
1797 let node_id = caps.get(2).unwrap().as_str();
1798 let rel_type = caps.get(3).unwrap().as_str();
1799 return Ok(self.neighbors(&(node_type, node_id), Some(rel_type), Direction::Out));
1800 }
1801
1802 Err(GraphError::ParseError(format!("Invalid query pattern: {}", pattern)))
1803 }
1804
1805 pub fn start(&self, node_ref: &NodeRef) -> GraphTraversal<'_> {
1811 GraphTraversal::new(self, NodeId::new(node_ref.0, node_ref.1))
1812 }
1813}
1814
1815pub struct GraphTraversal<'a> {
1821 graph: &'a ISONGraph,
1822 current: HashSet<String>,
1823 visited: HashSet<String>,
1824 ref_map: HashMap<String, NodeId>,
1825}
1826
1827impl<'a> GraphTraversal<'a> {
1828 pub fn new(graph: &'a ISONGraph, start: NodeId) -> Self {
1829 let start_key = start.to_key();
1830 let mut current = HashSet::new();
1831 current.insert(start_key.clone());
1832
1833 let mut visited = HashSet::new();
1834 visited.insert(start_key.clone());
1835
1836 let mut ref_map = HashMap::new();
1837 ref_map.insert(start_key, start);
1838
1839 Self {
1840 graph,
1841 current,
1842 visited,
1843 ref_map,
1844 }
1845 }
1846
1847 pub fn hop(mut self, rel_type: Option<&str>, direction: Direction) -> Self {
1849 let mut next_level: HashSet<String> = HashSet::new();
1850
1851 for key in &self.current {
1852 if let Some(node_id) = self.ref_map.get(key) {
1853 let neighbors = self.graph.neighbors(&node_id.as_ref(), rel_type, direction);
1854 for neighbor in neighbors {
1855 let neighbor_key = neighbor.to_key();
1856 if !self.visited.contains(&neighbor_key) {
1857 next_level.insert(neighbor_key.clone());
1858 self.ref_map.insert(neighbor_key, neighbor);
1859 }
1860 }
1861 }
1862 }
1863
1864 for key in &next_level {
1865 self.visited.insert(key.clone());
1866 }
1867 self.current = next_level;
1868 self
1869 }
1870
1871 pub fn hops(mut self, n: usize, rel_type: Option<&str>, direction: Direction) -> Self {
1873 for _ in 0..n {
1874 self = self.hop(rel_type, direction);
1875 }
1876 self
1877 }
1878
1879 pub fn filter<F>(mut self, f: F) -> Self
1881 where
1882 F: Fn(&Node) -> bool,
1883 {
1884 let filtered: HashSet<String> = self
1885 .current
1886 .iter()
1887 .filter(|key| {
1888 if let Some(node_id) = self.ref_map.get(*key) {
1889 if let Ok(node) = self.graph.get_node_by_id(node_id) {
1890 return f(node);
1891 }
1892 }
1893 false
1894 })
1895 .cloned()
1896 .collect();
1897 self.current = filtered;
1898 self
1899 }
1900
1901 pub fn collect(self) -> Vec<NodeId> {
1903 self.current
1904 .iter()
1905 .filter_map(|key| self.ref_map.get(key).cloned())
1906 .collect()
1907 }
1908
1909 pub fn collect_nodes(self) -> Vec<Node> {
1911 self.current
1912 .iter()
1913 .filter_map(|key| {
1914 self.ref_map
1915 .get(key)
1916 .and_then(|id| self.graph.get_node_by_id(id).ok().cloned())
1917 })
1918 .collect()
1919 }
1920
1921 pub fn count(&self) -> usize {
1923 self.current.len()
1924 }
1925
1926 pub fn first(&self) -> Option<NodeId> {
1928 self.current
1929 .iter()
1930 .next()
1931 .and_then(|key| self.ref_map.get(key).cloned())
1932 }
1933}
1934
1935#[cfg(test)]
1940mod tests {
1941 use super::*;
1942
1943 #[test]
1944 fn test_add_and_get_node() {
1945 let mut graph = ISONGraph::new("test");
1946 graph
1947 .add_node("person", "1", props![("name", "Alice"), ("age", "30")])
1948 .unwrap();
1949
1950 let node = graph.get_node("person", "1").unwrap();
1951 assert_eq!(node.node_type, "person");
1952 assert_eq!(node.id, "1");
1953 assert_eq!(crate::value_to_text(node.properties.get("name").unwrap()), "Alice");
1954 }
1955
1956 #[test]
1957 fn test_duplicate_node() {
1958 let mut graph = ISONGraph::new("test");
1959 graph.add_node("person", "1", props![]).unwrap();
1960 assert!(graph.add_node("person", "1", props![]).is_err());
1961 }
1962
1963 #[test]
1964 fn test_add_node_rejects_colon() {
1965 let mut graph = ISONGraph::new("test");
1966 assert!(matches!(
1967 graph.add_node("per:son", "1", props![]),
1968 Err(GraphError::InvalidIdentifier(_))
1969 ));
1970 assert!(matches!(
1971 graph.add_node("person", "1:2", props![]),
1972 Err(GraphError::InvalidIdentifier(_))
1973 ));
1974 assert_eq!(graph.node_count(), 0);
1975 }
1976
1977 #[test]
1982 fn test_add_node_rejects_pipe() {
1983 let mut graph = ISONGraph::new("test");
1984 assert!(matches!(
1985 graph.add_node("per|son", "1", props![]),
1986 Err(GraphError::InvalidIdentifier(_))
1987 ));
1988 assert!(matches!(
1989 graph.add_node("person", "1|2", props![]),
1990 Err(GraphError::InvalidIdentifier(_))
1991 ));
1992 assert_eq!(graph.node_count(), 0);
1993 }
1994
1995 #[test]
1996 fn test_add_edge_rejects_colon_and_pipe_in_rel_type() {
1997 let mut graph = ISONGraph::new("test");
1998 graph.add_node("person", "1", props![]).unwrap();
1999 graph.add_node("person", "2", props![]).unwrap();
2000 assert!(matches!(
2001 graph.add_edge("KN:OWS", ("person", "1"), ("person", "2"), props![]),
2002 Err(GraphError::InvalidIdentifier(_))
2003 ));
2004 assert!(matches!(
2005 graph.add_edge("KN|OWS", ("person", "1"), ("person", "2"), props![]),
2006 Err(GraphError::InvalidIdentifier(_))
2007 ));
2008 assert_eq!(graph.edge_count(), 0);
2009 }
2010
2011 #[test]
2012 fn test_unrepresentable_identifiers_are_rejected() {
2013 for bad in ["a b", "a\tb", "a\nb", ""] {
2017 let mut graph = ISONGraph::new("test");
2018 assert!(graph.add_node(bad, "1", props![]).is_err(), "type {:?}", bad);
2019 assert!(graph.add_node("p", bad, props![]).is_err(), "id {:?}", bad);
2020 }
2021
2022 for bad in ["a\"b", "a\\b"] {
2024 let mut graph = ISONGraph::new("test");
2025 assert!(graph.add_node(bad, "1", props![]).is_err(), "type {:?}", bad);
2026 assert!(graph.add_node("p", bad, props![]).is_ok(), "id {:?}", bad);
2027 }
2028 }
2029
2030 #[test]
2031 fn test_valid_identifiers_still_allowed() {
2032 let mut graph = ISONGraph::new("test");
2033 graph.add_node("a-type", "an-id-1", props![]).unwrap();
2034 graph.add_node("b.c", "#2", props![]).unwrap();
2035 graph
2036 .add_edge("SHARES_BORDER_WITH", ("a-type", "an-id-1"), ("b.c", "#2"), props![])
2037 .unwrap();
2038 assert_eq!(graph.edge_count(), 1);
2039
2040 let restored = ISONGraph::from_ison(&graph.to_ison(), None).unwrap();
2041 assert_eq!(restored.node_count(), 2);
2042 assert_eq!(restored.edge_count(), 1);
2043 }
2044
2045 #[test]
2046 fn test_no_longer_crashes_on_ison_roundtrip() {
2047 let mut graph = ISONGraph::new("test");
2050 assert!(graph.add_node("a:b", "1", props![]).is_err());
2051 }
2052
2053 #[test]
2054 fn test_no_longer_crashes_on_isonl_roundtrip() {
2055 let mut graph = ISONGraph::new("test");
2056 assert!(graph.add_node("rel|type", "1", props![]).is_err());
2057 }
2058
2059 #[cfg(feature = "serde")]
2060 #[test]
2061 fn test_serde_deserialize_rejects_bad_identifiers() {
2062 let bad = r#"{"name":"t","directed":true,"nodes":{"a:b":{"1":{"node_type":"a:b","id":"1","properties":{}}}},"edges":{}}"#;
2068 let result: std::result::Result<ISONGraph, _> = serde_json::from_str(bad);
2069 assert!(result.is_err());
2070
2071 let good = r#"{"name":"t","directed":true,"nodes":{"a":{"1":{"node_type":"a","id":"1","properties":{}}}},"edges":{}}"#;
2072 let graph: ISONGraph = serde_json::from_str(good).unwrap();
2073 assert_eq!(graph.node_count(), 1);
2074 }
2075
2076 #[test]
2077 fn test_add_and_has_edge() {
2078 let mut graph = ISONGraph::new("test");
2079 graph.add_node("person", "1", props![]).unwrap();
2080 graph.add_node("person", "2", props![]).unwrap();
2081 graph
2082 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2083 .unwrap();
2084
2085 assert!(graph.has_edge("KNOWS", ("person", "1"), ("person", "2")));
2086 assert!(!graph.has_edge("KNOWS", ("person", "2"), ("person", "1")));
2087 }
2088
2089 #[test]
2090 fn test_neighbors() {
2091 let mut graph = ISONGraph::new("test");
2092 graph.add_node("person", "1", props![]).unwrap();
2093 graph.add_node("person", "2", props![]).unwrap();
2094 graph.add_node("person", "3", props![]).unwrap();
2095 graph
2096 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2097 .unwrap();
2098 graph
2099 .add_edge("KNOWS", ("person", "1"), ("person", "3"), props![])
2100 .unwrap();
2101
2102 let friends = graph.neighbors(&("person", "1"), Some("KNOWS"), Direction::Out);
2103 assert_eq!(friends.len(), 2);
2104 }
2105
2106 #[test]
2107 fn test_multi_hop() {
2108 let mut graph = ISONGraph::new("test");
2109 graph.add_node("person", "1", props![]).unwrap();
2110 graph.add_node("person", "2", props![]).unwrap();
2111 graph.add_node("person", "3", props![]).unwrap();
2112 graph
2113 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2114 .unwrap();
2115 graph
2116 .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2117 .unwrap();
2118
2119 let two_hops = graph.multi_hop(&("person", "1"), Some("KNOWS"), 2, Direction::Out);
2120 assert_eq!(two_hops.len(), 1);
2121 assert_eq!(two_hops[0].id, "3");
2122 }
2123
2124 #[test]
2125 fn test_shortest_path() {
2126 let mut graph = ISONGraph::new("test");
2127 graph.add_node("person", "1", props![]).unwrap();
2128 graph.add_node("person", "2", props![]).unwrap();
2129 graph.add_node("person", "3", props![]).unwrap();
2130 graph
2131 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2132 .unwrap();
2133 graph
2134 .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2135 .unwrap();
2136
2137 let path = graph
2138 .shortest_path(&("person", "1"), &("person", "3"), Some("KNOWS"), 10, Direction::Out)
2139 .unwrap();
2140 assert_eq!(path.length(), 2);
2141 assert_eq!(path.nodes.len(), 3);
2142 }
2143
2144 #[test]
2145 fn test_node_count() {
2146 let mut graph = ISONGraph::new("test");
2147 graph.add_node("person", "1", props![]).unwrap();
2148 graph.add_node("person", "2", props![]).unwrap();
2149 graph.add_node("company", "100", props![]).unwrap();
2150
2151 assert_eq!(graph.node_count(), 3);
2152 assert_eq!(graph.node_count_of_type("person"), 2);
2153 assert_eq!(graph.node_count_of_type("company"), 1);
2154 }
2155
2156 #[test]
2157 fn test_to_ison() {
2158 let mut graph = ISONGraph::new("test");
2159 graph
2160 .add_node("person", "1", props![("name", "Alice")])
2161 .unwrap();
2162 graph
2163 .add_node("person", "2", props![("name", "Bob")])
2164 .unwrap();
2165 graph
2166 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2167 .unwrap();
2168
2169 let ison = graph.to_ison();
2170 assert!(ison.contains("nodes.person"));
2171 assert!(ison.contains("edges.KNOWS"));
2172 assert!(ison.contains("Alice"));
2173 }
2174
2175 fn special_values_graph() -> ISONGraph {
2176 let mut graph = ISONGraph::new("test");
2177 graph
2178 .add_node(
2179 "person",
2180 "1",
2181 props![
2182 ("name", "Alice Smith"),
2183 ("bio", "a|b"),
2184 ("note", "line1\nline2"),
2185 ("empty", ""),
2186 ],
2187 )
2188 .unwrap();
2189 graph
2190 .add_node(
2191 "person",
2192 "2",
2193 props![
2194 ("name", "Bob"),
2195 ("bio", "he said \"hi\""),
2196 ("note", "x"),
2197 ("empty", "y"),
2198 ],
2199 )
2200 .unwrap();
2201 graph
2202 .add_edge(
2203 "KNOWS",
2204 ("person", "1"),
2205 ("person", "2"),
2206 props![("where", "New York"), ("tag", "")],
2207 )
2208 .unwrap();
2209 graph
2210 }
2211
2212 fn assert_special_values(restored: &ISONGraph) {
2213 assert_eq!(restored.node_count(), 2);
2214 assert_eq!(restored.edge_count(), 1);
2215 let n1 = restored.get_node("person", "1").unwrap();
2216 assert_eq!(crate::value_to_text(n1.properties.get("name").unwrap()), "Alice Smith");
2217 assert_eq!(crate::value_to_text(n1.properties.get("bio").unwrap()), "a|b");
2218 assert_eq!(crate::value_to_text(n1.properties.get("note").unwrap()), "line1\nline2");
2219 assert_eq!(crate::value_to_text(n1.properties.get("empty").unwrap()), "");
2220 let n2 = restored.get_node("person", "2").unwrap();
2221 assert_eq!(crate::value_to_text(n2.properties.get("bio").unwrap()), "he said \"hi\"");
2222 let e = restored
2223 .get_edge("KNOWS", ("person", "1"), ("person", "2"))
2224 .unwrap();
2225 assert_eq!(crate::value_to_text(e.properties.get("where").unwrap()), "New York");
2226 assert_eq!(crate::value_to_text(e.properties.get("tag").unwrap()), "");
2227 }
2228
2229 #[test]
2230 fn test_ison_round_trip_special_values() {
2231 let graph = special_values_graph();
2232 let restored = ISONGraph::from_ison(&graph.to_ison(), Some("test")).unwrap();
2233 assert_special_values(&restored);
2234 }
2235
2236 #[test]
2237 fn test_isonl_round_trip_special_values() {
2238 let graph = special_values_graph();
2239 let restored = ISONGraph::from_isonl(&graph.to_isonl(), Some("test")).unwrap();
2240 assert_special_values(&restored);
2241 }
2242
2243 #[test]
2244 fn test_is_connected() {
2245 let mut graph = ISONGraph::new("test");
2246 graph.add_node("person", "1", props![]).unwrap();
2247 graph.add_node("person", "2", props![]).unwrap();
2248 graph
2249 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2250 .unwrap();
2251
2252 assert!(graph.is_connected());
2253
2254 graph.add_node("person", "3", props![]).unwrap();
2255 assert!(!graph.is_connected());
2256 }
2257
2258 #[test]
2263 fn test_from_ison() {
2264 let ison_text = r#"
2265nodes.person
2266id name age
2267alice Alice 30
2268bob Bob 25
2269
2270edges.KNOWS
2271source target since
2272:person:alice :person:bob 2020
2273"#;
2274
2275 let graph = ISONGraph::from_ison(ison_text, Some("test")).unwrap();
2276 assert_eq!(graph.node_count(), 2);
2277 assert_eq!(graph.edge_count(), 1);
2278 assert!(graph.has_node("person", "alice"));
2279 assert!(graph.has_node("person", "bob"));
2280 assert!(graph.has_edge("KNOWS", ("person", "alice"), ("person", "bob")));
2281 }
2282
2283 #[test]
2284 fn test_from_isonl() {
2285 let isonl_text = "nodes.person|id name age|alice Alice 30\n\
2286 nodes.person|id name age|bob Bob 25\n\
2287 edges.KNOWS|source target since|:person:alice :person:bob 2020\n";
2288
2289 let graph = ISONGraph::from_isonl(isonl_text, Some("test")).unwrap();
2290 assert_eq!(graph.node_count(), 2);
2291 assert_eq!(graph.edge_count(), 1);
2292 assert!(graph.has_node("person", "alice"));
2293 assert!(graph.has_edge("KNOWS", ("person", "alice"), ("person", "bob")));
2294 }
2295
2296 #[test]
2297 fn test_from_ison_malformed_errors() {
2298 let bad_row = "nodes.person\nid name\nalice Alice Extra";
2300 assert!(matches!(
2301 ISONGraph::from_ison(bad_row, None),
2302 Err(GraphError::ParseError(_))
2303 ));
2304
2305 let bad_header = "people\nid name\nalice Alice";
2307 assert!(matches!(
2308 ISONGraph::from_ison(bad_header, None),
2309 Err(GraphError::ParseError(_))
2310 ));
2311
2312 let bad_kind = "vertices.person\nid name\nalice Alice";
2314 assert!(matches!(
2315 ISONGraph::from_ison(bad_kind, None),
2316 Err(GraphError::ParseError(_))
2317 ));
2318 }
2319
2320 #[test]
2321 fn test_from_isonl_malformed_errors() {
2322 assert!(matches!(
2324 ISONGraph::from_isonl("nodes.person|id name", None),
2325 Err(GraphError::ParseError(_))
2326 ));
2327 let padded = ISONGraph::from_isonl("nodes.person|id name|alice", None).unwrap();
2331 assert_eq!(padded.node_count(), 1);
2332 assert!(matches!(
2334 ISONGraph::from_isonl("nodesperson|id|alice", None),
2335 Err(GraphError::ParseError(_))
2336 ));
2337 }
2338
2339 #[test]
2344 fn test_connected_components() {
2345 let mut graph = ISONGraph::new("test");
2346 graph.add_node("person", "1", props![]).unwrap();
2347 graph.add_node("person", "2", props![]).unwrap();
2348 graph.add_node("person", "3", props![]).unwrap();
2349 graph.add_node("person", "4", props![]).unwrap();
2350 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2351 graph.add_edge("KNOWS", ("person", "3"), ("person", "4"), props![]).unwrap();
2352
2353 let components = graph.connected_components();
2354 assert_eq!(components.len(), 2);
2355 }
2356
2357 #[test]
2358 fn test_all_paths() {
2359 let mut graph = ISONGraph::new("test");
2360 graph.add_node("person", "1", props![]).unwrap();
2361 graph.add_node("person", "2", props![]).unwrap();
2362 graph.add_node("person", "3", props![]).unwrap();
2363 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2364 graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2365 graph.add_edge("KNOWS", ("person", "1"), ("person", "3"), props![]).unwrap();
2366
2367 let paths = graph.all_paths(&("person", "1"), &("person", "3"), None, 5, Direction::Out);
2368 assert_eq!(paths.len(), 2); }
2370
2371 #[test]
2372 fn test_get_edge() {
2373 let mut graph = ISONGraph::new("test");
2374 graph.add_node("person", "1", props![]).unwrap();
2375 graph.add_node("person", "2", props![]).unwrap();
2376 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020")]).unwrap();
2377
2378 let edge = graph.get_edge("KNOWS", ("person", "1"), ("person", "2")).unwrap();
2379 assert_eq!(edge.rel_type, "KNOWS");
2380 assert_eq!(crate::value_to_text(edge.properties.get("since").unwrap()), "2020");
2381 }
2382
2383 #[test]
2388 fn test_query_pattern() {
2389 let mut graph = ISONGraph::new("test");
2390 graph.add_node("person", "1", props![]).unwrap();
2391 graph.add_node("person", "2", props![]).unwrap();
2392 graph.add_node("person", "3", props![]).unwrap();
2393 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2394 graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2395
2396 let result = graph.query(":person:1 -[:KNOWS]-> *").unwrap();
2397 assert_eq!(result.len(), 1);
2398 assert_eq!(result[0].id, "2");
2399
2400 let result2 = graph.query(":person:1 -[:KNOWS*2]-> *").unwrap();
2401 assert_eq!(result2.len(), 1);
2402 assert_eq!(result2[0].id, "3");
2403 }
2404
2405 #[test]
2410 fn test_start_method() {
2411 let mut graph = ISONGraph::new("test");
2412 graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2413 graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2414 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2415
2416 let result = graph.start(&("person", "1"))
2417 .hop(Some("KNOWS"), Direction::Out)
2418 .collect();
2419
2420 assert_eq!(result.len(), 1);
2421 assert_eq!(result[0].id, "2");
2422 }
2423
2424 #[test]
2425 fn test_fluent_collect_nodes() {
2426 let mut graph = ISONGraph::new("test");
2427 graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2428 graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2429 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2430
2431 let nodes = graph.start(&("person", "1"))
2432 .hop(Some("KNOWS"), Direction::Out)
2433 .collect_nodes();
2434
2435 assert_eq!(nodes.len(), 1);
2436 assert_eq!(crate::value_to_text(nodes[0].properties.get("name").unwrap()), "Bob");
2437 }
2438
2439 #[test]
2440 fn test_fluent_filter() {
2441 let mut graph = ISONGraph::new("test");
2442 graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2443 graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2444 graph.add_node("person", "3", props![("name", "Charlie")]).unwrap();
2445 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2446 graph.add_edge("KNOWS", ("person", "1"), ("person", "3"), props![]).unwrap();
2447
2448 let result = graph.start(&("person", "1"))
2449 .hop(Some("KNOWS"), Direction::Out)
2450 .filter(|n| n.properties.get("name").map(|v| crate::value_to_text(v) == "Bob").unwrap_or(false))
2451 .collect();
2452
2453 assert_eq!(result.len(), 1);
2454 assert_eq!(result[0].id, "2");
2455 }
2456
2457 #[test]
2462 fn test_undirected_single_edge_no_cycle() {
2463 let mut graph = ISONGraph::undirected("test");
2464 graph.add_node("person", "1", props![]).unwrap();
2465 graph.add_node("person", "2", props![]).unwrap();
2466 graph
2467 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2468 .unwrap();
2469 assert!(!graph.has_cycle(None));
2471
2472 graph.add_node("person", "3", props![]).unwrap();
2474 graph
2475 .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2476 .unwrap();
2477 assert!(!graph.has_cycle(None));
2478
2479 graph
2481 .add_edge("KNOWS", ("person", "3"), ("person", "1"), props![])
2482 .unwrap();
2483 assert!(graph.has_cycle(None));
2484 }
2485
2486 #[test]
2487 fn test_directed_cycle_detection() {
2488 let mut graph = ISONGraph::new("test");
2489 graph.add_node("t", "a", props![]).unwrap();
2490 graph.add_node("t", "b", props![]).unwrap();
2491 graph.add_edge("R", ("t", "a"), ("t", "b"), props![]).unwrap();
2492 assert!(!graph.has_cycle(None));
2493 graph.add_edge("R", ("t", "b"), ("t", "a"), props![]).unwrap();
2494 assert!(graph.has_cycle(None));
2495 assert!(!graph.has_cycle(Some("OTHER")));
2497 }
2498
2499 #[test]
2500 fn test_neighbors_both_undirected_dedup() {
2501 let mut graph = ISONGraph::undirected("test");
2502 graph.add_node("person", "1", props![]).unwrap();
2503 graph.add_node("person", "2", props![]).unwrap();
2504 graph
2505 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2506 .unwrap();
2507
2508 let neighbors = graph.neighbors(&("person", "1"), None, Direction::Both);
2509 assert_eq!(neighbors.len(), 1);
2510 assert_eq!(neighbors[0].id, "2");
2511 }
2512
2513 #[test]
2514 fn test_path_exists_direction() {
2515 let mut graph = ISONGraph::new("test");
2516 graph.add_node("person", "1", props![]).unwrap();
2517 graph.add_node("person", "2", props![]).unwrap();
2518 graph
2519 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2520 .unwrap();
2521
2522 assert!(graph.path_exists(&("person", "1"), &("person", "2"), None, 5, Direction::Out));
2523 assert!(!graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::Out));
2524 assert!(graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::In));
2525 assert!(graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::Both));
2526 }
2527
2528 #[test]
2529 fn test_max_hops_usize_max_no_overflow() {
2530 let mut graph = ISONGraph::new("test");
2531 graph.add_node("person", "1", props![]).unwrap();
2532 graph.add_node("person", "2", props![]).unwrap();
2533 graph
2534 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2535 .unwrap();
2536
2537 assert!(graph.path_exists(
2538 &("person", "1"),
2539 &("person", "2"),
2540 None,
2541 usize::MAX,
2542 Direction::Out
2543 ));
2544 let paths = graph.all_paths(&("person", "1"), &("person", "2"), None, usize::MAX, Direction::Out);
2545 assert_eq!(paths.len(), 1);
2546 }
2547
2548 #[test]
2549 fn test_all_paths_start_equals_end() {
2550 let mut graph = ISONGraph::new("test");
2551 graph.add_node("person", "1", props![]).unwrap();
2552 let paths = graph.all_paths(&("person", "1"), &("person", "1"), None, 5, Direction::Out);
2553 assert_eq!(paths.len(), 1);
2554 assert_eq!(paths[0].length(), 0);
2555 }
2556
2557 #[cfg(feature = "serde")]
2562 #[test]
2563 fn test_serde_round_trip() {
2564 let mut graph = ISONGraph::new("test");
2565 graph
2566 .add_node("person", "1", props![("name", "Alice")])
2567 .unwrap();
2568 graph
2569 .add_node("person", "2", props![("name", "Bob")])
2570 .unwrap();
2571 graph
2572 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020")])
2573 .unwrap();
2574
2575 let json = serde_json::to_string(&graph).unwrap();
2576 assert!(!json.contains("out_edges"));
2578 assert!(!json.contains("in_edges"));
2579 assert!(!json.contains("edge_set"));
2580
2581 let restored: ISONGraph = serde_json::from_str(&json).unwrap();
2582 assert_eq!(restored.name, "test");
2583 assert_eq!(restored.node_count(), 2);
2584 assert_eq!(restored.edge_count(), 1);
2585 assert!(restored.has_edge("KNOWS", ("person", "1"), ("person", "2")));
2586
2587 let neighbors = restored.neighbors(&("person", "1"), Some("KNOWS"), Direction::Out);
2589 assert_eq!(neighbors.len(), 1);
2590 assert_eq!(neighbors[0].id, "2");
2591 assert_eq!(restored.in_degree(&("person", "2")), 1);
2592 }
2593
2594 #[test]
2595 fn test_fluent_hops() {
2596 let mut graph = ISONGraph::new("test");
2597 graph.add_node("person", "1", props![]).unwrap();
2598 graph.add_node("person", "2", props![]).unwrap();
2599 graph.add_node("person", "3", props![]).unwrap();
2600 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2601 graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2602
2603 let count = graph.start(&("person", "1"))
2604 .hops(2, Some("KNOWS"), Direction::Out)
2605 .count();
2606
2607 assert_eq!(count, 1);
2608 }
2609
2610 const CANONICAL_GOLDEN_ISON: &str = r#"edges.KNOWS
2623since source target weight
2624"2020" :person:1 :person:2 1.75
2625"2021" :person:10 :person:1 0.5
2626
2627edges.WORKS_AT
2628role source target
2629"Lead Engineer" :person:1 :company:acme
2630
2631edges.WORKS_ON
2632hours source target
26333 :person:10 :project:p1
26345 :person:2 :project:p1
2635
2636nodes.company
2637id listed name staff
2638acme false "Acme Corp" 42
2639
2640nodes.person
2641id active age name score
2642"1" true "30" Alice 9.5
2643"10" false "22" Jax -2.25
2644"2" null "25" Bob null
2645
2646nodes.project
2647id budget name tag
2648p1 1250 Alpha a|b"#;
2649
2650 const CANONICAL_GOLDEN_ISONL: &str = r#"edges.KNOWS|since source target weight|"2020" :person:1 :person:2 1.75
2651edges.KNOWS|since source target weight|"2021" :person:10 :person:1 0.5
2652edges.WORKS_AT|role source target|"Lead Engineer" :person:1 :company:acme
2653edges.WORKS_ON|hours source target|3 :person:10 :project:p1
2654edges.WORKS_ON|hours source target|5 :person:2 :project:p1
2655nodes.company|id listed name staff|acme false "Acme Corp" 42
2656nodes.person|id active age name score|"1" true "30" Alice 9.5
2657nodes.person|id active age name score|"10" false "22" Jax -2.25
2658nodes.person|id active age name score|"2" null "25" Bob null
2659nodes.project|id budget name tag|p1 1250 Alpha "a\|b""#;
2660
2661 #[allow(clippy::type_complexity)]
2662 fn build_canonical_fixture(order: usize) -> ISONGraph {
2663 let mut g = ISONGraph::new("fixture");
2664 let nodes: Vec<(&str, &str, Vec<(&str, Value)>)> = vec![
2670 ("company", "acme", props![("name", "Acme Corp"), ("staff", 42i64), ("listed", false)]),
2671 ("person", "1", props![("name", "Alice"), ("age", "30"), ("score", 9.5f64), ("active", true)]),
2672 ("person", "10", props![("name", "Jax"), ("age", "22"), ("score", -2.25f64), ("active", false)]),
2673 ("person", "2", props![("name", "Bob"), ("age", "25")]),
2674 ("project", "p1", props![("name", "Alpha"), ("tag", "a|b"), ("budget", 1250i64)]),
2675 ];
2676 let edges: Vec<(&str, (&str, &str), (&str, &str), Vec<(&str, Value)>)> = vec![
2677 ("KNOWS", ("person", "10"), ("person", "1"), props![("since", "2021"), ("weight", 0.5f64)]),
2678 ("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020"), ("weight", 1.75f64)]),
2679 ("WORKS_AT", ("person", "1"), ("company", "acme"), props![("role", "Lead Engineer")]),
2680 ("WORKS_ON", ("person", "2"), ("project", "p1"), props![("hours", 5i64)]),
2681 ("WORKS_ON", ("person", "10"), ("project", "p1"), props![("hours", 3i64)]),
2682 ];
2683 let mut n = nodes;
2684 let mut e = edges;
2685 if order != 0 {
2686 n.reverse();
2687 e.reverse();
2688 }
2689 for (t, i, props) in n {
2690 g.add_node(t, i, props).unwrap();
2691 }
2692 for (rel, s, t, props) in e {
2693 g.add_edge(rel, s, t, props).unwrap();
2694 }
2695 g
2696 }
2697
2698 #[test]
2699 fn test_to_ison_independent_of_insertion_order() {
2700 assert_eq!(build_canonical_fixture(0).to_ison(), build_canonical_fixture(1).to_ison());
2701 }
2702
2703 #[test]
2704 fn test_to_isonl_independent_of_insertion_order() {
2705 assert_eq!(build_canonical_fixture(0).to_isonl(), build_canonical_fixture(1).to_isonl());
2706 }
2707
2708 #[test]
2709 fn test_to_ison_matches_golden_fixture() {
2710 assert_eq!(build_canonical_fixture(0).to_ison(), CANONICAL_GOLDEN_ISON);
2711 assert_eq!(build_canonical_fixture(1).to_ison(), CANONICAL_GOLDEN_ISON);
2712 }
2713
2714 #[test]
2715 fn test_to_isonl_matches_golden_fixture() {
2716 assert_eq!(build_canonical_fixture(0).to_isonl(), CANONICAL_GOLDEN_ISONL);
2717 assert_eq!(build_canonical_fixture(1).to_isonl(), CANONICAL_GOLDEN_ISONL);
2718 }
2719
2720 #[test]
2721 fn test_ordinal_not_numeric_sort() {
2722 let ison = build_canonical_fixture(0).to_ison();
2724 let person_block = ison.split("nodes.person
2725").nth(1).unwrap().split("
2726
2727").next().unwrap();
2728 let ids: Vec<&str> = person_block
2732 .lines()
2733 .skip(1)
2734 .map(|l| l.split(' ').next().unwrap().trim_matches('"'))
2735 .collect();
2736 assert_eq!(ids, vec!["1", "10", "2"]);
2737 }
2738
2739 #[test]
2740 fn test_roundtrip_preserves_canonical_form() {
2741 let g = build_canonical_fixture(0);
2742 let reloaded = ISONGraph::from_ison(&g.to_ison(), None).unwrap();
2743 assert_eq!(reloaded.to_ison(), g.to_ison());
2744 }
2745}