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