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("{0}")]
293 InvalidPropertyValue(String),
294
295 #[error("I/O error: {0}")]
296 Io(#[from] std::io::Error),
297}
298
299pub type Result<T> = std::result::Result<T, GraphError>;
300
301pub const MULTIGRAPH_FORMAT: &str = "ison-graph-multigraph-v1";
305
306#[derive(Debug)]
321#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
322#[cfg_attr(feature = "serde", serde(try_from = "GraphData"))]
323pub struct ISONGraph {
324 pub name: String,
326
327 pub directed: bool,
329
330 nodes: HashMap<String, HashMap<String, Node>>,
332
333 edges: HashMap<String, Vec<Edge>>,
335
336 #[cfg_attr(feature = "serde", serde(skip))]
339 out_edges: HashMap<String, Vec<Edge>>,
340
341 #[cfg_attr(feature = "serde", serde(skip))]
344 in_edges: HashMap<String, Vec<Edge>>,
345
346 #[cfg_attr(feature = "serde", serde(skip))]
349 edge_set: HashSet<String>,
350}
351
352#[cfg(feature = "serde")]
355#[derive(Deserialize)]
356struct GraphData {
357 name: String,
358 directed: bool,
359 nodes: HashMap<String, HashMap<String, Node>>,
360 edges: HashMap<String, Vec<Edge>>,
361}
362
363#[cfg(feature = "serde")]
364impl TryFrom<GraphData> for ISONGraph {
365 type Error = GraphError;
366
367 fn try_from(data: GraphData) -> Result<Self> {
374 for (node_type, type_nodes) in &data.nodes {
375 ISONGraph::check_identifier("Node type", node_type)?;
376 for node_id in type_nodes.keys() {
377 ISONGraph::check_identifier("Node id", node_id)?;
378 }
379 }
380 for (rel_type, edges) in &data.edges {
381 ISONGraph::check_identifier("Relationship type", rel_type)?;
382 for edge in edges {
383 ISONGraph::check_identifier("Node type", &edge.source.node_type)?;
384 ISONGraph::check_identifier("Node id", &edge.source.id)?;
385 ISONGraph::check_identifier("Node type", &edge.target.node_type)?;
386 ISONGraph::check_identifier("Node id", &edge.target.id)?;
387 }
388 }
389
390 let mut graph = ISONGraph {
391 name: data.name,
392 directed: data.directed,
393 nodes: data.nodes,
394 edges: data.edges,
395 out_edges: HashMap::new(),
396 in_edges: HashMap::new(),
397 edge_set: HashSet::new(),
398 };
399 graph.rebuild_indexes();
400 Ok(graph)
401 }
402}
403
404impl Default for ISONGraph {
405 fn default() -> Self {
406 Self::new("graph")
407 }
408}
409
410impl ISONGraph {
411 pub fn new(name: impl Into<String>) -> Self {
413 Self {
414 name: name.into(),
415 directed: true,
416 nodes: HashMap::new(),
417 edges: HashMap::new(),
418 out_edges: HashMap::new(),
419 in_edges: HashMap::new(),
420 edge_set: HashSet::new(),
421 }
422 }
423
424 pub fn undirected(name: impl Into<String>) -> Self {
426 let mut graph = Self::new(name);
427 graph.directed = false;
428 graph
429 }
430
431 #[cfg(feature = "serde")]
434 fn rebuild_indexes(&mut self) {
435 self.out_edges.clear();
436 self.in_edges.clear();
437 self.edge_set.clear();
438
439 for edges in self.edges.values() {
440 for edge in edges {
441 let edge_key = edge.to_key();
442 if !self.edge_set.insert(edge_key) {
443 continue;
444 }
445 self.out_edges
446 .entry(edge.source.to_key())
447 .or_default()
448 .push(edge.clone());
449 self.in_edges
450 .entry(edge.target.to_key())
451 .or_default()
452 .push(edge.clone());
453 }
454 }
455 }
456
457 fn check_identifier(kind: &str, value: &str) -> Result<()> {
471 let is_type = kind.to_lowercase().contains("type");
474 let bad = value.is_empty()
475 || value.chars().any(|ch| {
476 ch.is_whitespace()
477 || ch == ':'
478 || ch == '|'
479 || (is_type && (ch == '"' || ch == '\\'))
480 });
481 if bad {
482 return Err(GraphError::InvalidIdentifier(format!(
483 "{} {:?} is not representable: it must not be empty or contain \
484 whitespace, ':' or '|'{}",
485 kind,
486 value,
487 if is_type { ", '\"' or '\\'" } else { "" }
488 )));
489 }
490 Ok(())
491 }
492
493 fn check_property_names<'a, I>(kind: &str, names: I) -> Result<()>
500 where
501 I: IntoIterator<Item = &'a str>,
502 {
503 for name in names {
504 let bad = name.is_empty()
505 || name.starts_with('#')
506 || name.chars().any(|ch| {
507 ch.is_whitespace()
508 || ch == ':'
509 || ch == '|'
510 || ch == '"'
511 || ch == '\\'
512 || ch == '.'
513 });
514 if bad {
515 return Err(GraphError::InvalidIdentifier(format!(
516 "{} name {:?} cannot be encoded: property names must not be \
517 empty, start with '#', or contain whitespace, ':', '|', \
518 '\"', '\\' or '.'",
519 kind, name
520 )));
521 }
522 }
523 Ok(())
524 }
525
526 fn check_property_values<'a>(
529 kind: &str,
530 properties: impl Iterator<Item = (&'a str, &'a Value)>,
531 ) -> Result<()> {
532 for (name, value) in properties {
533 if let Value::Float(f) = value {
534 if !f.is_finite() {
535 return Err(GraphError::InvalidPropertyValue(format!(
536 "{} {:?} = {} cannot be encoded: a float must be finite \
537 (NaN and infinity are read back as strings).",
538 kind, name, f
539 )));
540 }
541 }
542 }
543 Ok(())
544 }
545
546 pub fn add_node(
547 &mut self,
548 node_type: &str,
549 node_id: &str,
550 properties: Vec<(&str, Value)>,
551 ) -> Result<&Node> {
552 Self::check_identifier("Node type", node_type)?;
553 Self::check_identifier("Node id", node_id)?;
554 Self::check_property_names("Node property", properties.iter().map(|(k, _)| *k))?;
555 Self::check_property_values("Node property", properties.iter().map(|(k, v)| (*k, v)))?;
556
557 let type_nodes = self.nodes.entry(node_type.to_string()).or_default();
558
559 if type_nodes.contains_key(node_id) {
560 return Err(GraphError::DuplicateNode(
561 node_type.to_string(),
562 node_id.to_string(),
563 ));
564 }
565
566 let node = Node::new(node_type, node_id).with_properties(properties);
567 type_nodes.insert(node_id.to_string(), node);
568 Ok(type_nodes.get(node_id).unwrap())
569 }
570
571 pub fn get_node(&self, node_type: &str, node_id: &str) -> Result<&Node> {
573 self.nodes
574 .get(node_type)
575 .and_then(|m| m.get(node_id))
576 .ok_or_else(|| GraphError::NodeNotFound(node_type.to_string(), node_id.to_string()))
577 }
578
579 pub fn get_node_by_id(&self, node_id: &NodeId) -> Result<&Node> {
581 self.get_node(&node_id.node_type, &node_id.id)
582 }
583
584 pub fn has_node(&self, node_type: &str, node_id: &str) -> bool {
586 self.nodes
587 .get(node_type)
588 .map(|m| m.contains_key(node_id))
589 .unwrap_or(false)
590 }
591
592 pub fn remove_node(&mut self, node_type: &str, node_id: &str) -> Result<()> {
594 if !self.has_node(node_type, node_id) {
595 return Err(GraphError::NodeNotFound(
596 node_type.to_string(),
597 node_id.to_string(),
598 ));
599 }
600
601 let node_key = format!("{}:{}", node_type, node_id);
602
603 let out_edges: Vec<Edge> = self.out_edges.get(&node_key).cloned().unwrap_or_default();
605 let in_edges: Vec<Edge> = self.in_edges.get(&node_key).cloned().unwrap_or_default();
606
607 for edge in out_edges.iter().chain(in_edges.iter()) {
608 self.remove_edge_internal(edge);
609 }
610
611 if let Some(type_nodes) = self.nodes.get_mut(node_type) {
613 type_nodes.remove(node_id);
614 if type_nodes.is_empty() {
615 self.nodes.remove(node_type);
616 }
617 }
618
619 Ok(())
620 }
621
622 pub fn update_node(
624 &mut self,
625 node_type: &str,
626 node_id: &str,
627 properties: Vec<(&str, Value)>,
628 ) -> Result<()> {
629 Self::check_property_names("Node property", properties.iter().map(|(k, _)| *k))?;
630 Self::check_property_values("Node property", properties.iter().map(|(k, v)| (*k, v)))?;
631 let node = self
632 .nodes
633 .get_mut(node_type)
634 .and_then(|m| m.get_mut(node_id))
635 .ok_or_else(|| GraphError::NodeNotFound(node_type.to_string(), node_id.to_string()))?;
636
637 for (k, v) in properties {
638 node.properties.insert(k.to_string(), v);
639 }
640 Ok(())
641 }
642
643 pub fn nodes(&self) -> impl Iterator<Item = &Node> {
645 self.nodes.values().flat_map(|m| m.values())
646 }
647
648 pub fn nodes_of_type(&self, node_type: &str) -> impl Iterator<Item = &Node> {
650 self.nodes
651 .get(node_type)
652 .into_iter()
653 .flat_map(|m| m.values())
654 }
655
656 pub fn node_count(&self) -> usize {
658 self.nodes.values().map(|m| m.len()).sum()
659 }
660
661 pub fn node_count_of_type(&self, node_type: &str) -> usize {
663 self.nodes.get(node_type).map(|m| m.len()).unwrap_or(0)
664 }
665
666 pub fn node_types(&self) -> Vec<&String> {
668 self.nodes.keys().collect()
669 }
670
671 pub fn add_edge(
677 &mut self,
678 rel_type: &str,
679 source: (&str, &str),
680 target: (&str, &str),
681 properties: Vec<(&str, Value)>,
682 ) -> Result<()> {
683 Self::check_identifier("Relationship type", rel_type)?;
684 Self::check_property_names("Edge property", properties.iter().map(|(k, _)| *k))?;
685 Self::check_property_values("Edge property", properties.iter().map(|(k, v)| (*k, v)))?;
686
687 if !self.has_node(source.0, source.1) {
689 return Err(GraphError::NodeNotFound(
690 source.0.to_string(),
691 source.1.to_string(),
692 ));
693 }
694 if !self.has_node(target.0, target.1) {
695 return Err(GraphError::NodeNotFound(
696 target.0.to_string(),
697 target.1.to_string(),
698 ));
699 }
700
701 let source_id = NodeId::new(source.0, source.1);
702 let target_id = NodeId::new(target.0, target.1);
703 let edge = Edge::new(rel_type, source_id.clone(), target_id.clone()).with_properties(properties.clone());
704 let edge_key = edge.to_key();
705
706 if self.edge_set.contains(&edge_key) {
707 return Err(GraphError::DuplicateEdge(edge_key));
708 }
709
710 self.edges
712 .entry(rel_type.to_string())
713 .or_default()
714 .push(edge.clone());
715
716 let source_key = source_id.to_key();
717 let target_key = target_id.to_key();
718
719 self.out_edges
720 .entry(source_key.clone())
721 .or_default()
722 .push(edge.clone());
723 self.in_edges
724 .entry(target_key.clone())
725 .or_default()
726 .push(edge.clone());
727
728 self.edge_set.insert(edge_key);
729
730 if !self.directed {
732 let reverse_edge = Edge::new(rel_type, target_id.clone(), source_id.clone())
733 .with_properties(properties);
734 let reverse_key = reverse_edge.to_key();
735
736 if !self.edge_set.contains(&reverse_key) {
737 self.edges
738 .entry(rel_type.to_string())
739 .or_default()
740 .push(reverse_edge.clone());
741 self.out_edges
742 .entry(target_key)
743 .or_default()
744 .push(reverse_edge.clone());
745 self.in_edges
746 .entry(source_key)
747 .or_default()
748 .push(reverse_edge);
749 self.edge_set.insert(reverse_key);
750 }
751 }
752
753 Ok(())
754 }
755
756 fn remove_edge_internal(&mut self, edge: &Edge) {
757 let edge_key = edge.to_key();
758 if !self.edge_set.contains(&edge_key) {
759 return;
760 }
761
762 self.edge_set.remove(&edge_key);
763
764 if let Some(rel_edges) = self.edges.get_mut(&edge.rel_type) {
766 rel_edges.retain(|e| e.to_key() != edge_key);
767 }
768
769 let source_key = edge.source.to_key();
771 if let Some(out) = self.out_edges.get_mut(&source_key) {
772 out.retain(|e| e.to_key() != edge_key);
773 }
774
775 let target_key = edge.target.to_key();
777 if let Some(in_e) = self.in_edges.get_mut(&target_key) {
778 in_e.retain(|e| e.to_key() != edge_key);
779 }
780 }
781
782 pub fn remove_edge(
784 &mut self,
785 rel_type: &str,
786 source: (&str, &str),
787 target: (&str, &str),
788 ) -> Result<()> {
789 let source_id = NodeId::new(source.0, source.1);
790 let target_id = NodeId::new(target.0, target.1);
791 let edge = Edge::new(rel_type, source_id, target_id);
792 let edge_key = edge.to_key();
793
794 if !self.edge_set.contains(&edge_key) {
795 return Err(GraphError::EdgeNotFound(
796 format!("{}:{}", source.0, source.1),
797 format!("{}:{}", target.0, target.1),
798 ));
799 }
800
801 self.remove_edge_internal(&edge);
802 Ok(())
803 }
804
805 pub fn has_edge(&self, rel_type: &str, source: (&str, &str), target: (&str, &str)) -> bool {
807 let source_id = NodeId::new(source.0, source.1);
808 let target_id = NodeId::new(target.0, target.1);
809 let edge = Edge::new(rel_type, source_id, target_id);
810 self.edge_set.contains(&edge.to_key())
811 }
812
813 pub fn edge_count(&self) -> usize {
815 self.edge_set.len()
816 }
817
818 pub fn edge_count_of_type(&self, rel_type: &str) -> usize {
820 self.edges.get(rel_type).map(|v| v.len()).unwrap_or(0)
821 }
822
823 pub fn edge_types(&self) -> Vec<&String> {
825 self.edges.keys().collect()
826 }
827
828 pub fn edges_of_type(&self, rel_type: &str) -> impl Iterator<Item = &Edge> {
830 self.edges.get(rel_type).into_iter().flatten()
831 }
832
833 pub fn has_cycle(&self, rel_type: Option<&str>) -> bool {
835 let mut visited = HashSet::new();
837
838 for node_types in self.nodes.values() {
839 for node in node_types.values() {
840 let node_key = format!("{}:{}", node.node_type, node.id);
841 if !visited.contains(&node_key)
842 && self.has_cycle_from(&node_key, &mut visited, rel_type)
843 {
844 return true;
845 }
846 }
847 }
848 false
849 }
850
851 fn cycle_successors(
858 &self,
859 node_key: &str,
860 rel_type: Option<&str>,
861 skip: Option<(&str, &str)>,
862 ) -> Vec<(String, String)> {
863 let mut result = Vec::new();
864 let mut skip_remaining = if self.directed { None } else { skip };
865
866 if let Some(edges) = self.out_edges.get(node_key) {
867 for edge in edges {
868 if rel_type.is_some() && rel_type != Some(edge.rel_type.as_str()) {
869 continue;
870 }
871 let target_key = edge.target.to_key();
872 if let Some((skip_rel, skip_key)) = skip_remaining {
873 if edge.rel_type == skip_rel && target_key == skip_key {
874 skip_remaining = None;
875 continue;
876 }
877 }
878 result.push((target_key, edge.rel_type.clone()));
879 }
880 }
881 result
882 }
883
884 fn has_cycle_from(
885 &self,
886 start_key: &str,
887 visited: &mut HashSet<String>,
888 rel_type: Option<&str>,
889 ) -> bool {
890 struct Frame {
891 key: String,
892 successors: Vec<(String, String)>,
893 idx: usize,
894 }
895
896 let mut rec_stack: HashSet<String> = HashSet::new();
897 visited.insert(start_key.to_string());
898 rec_stack.insert(start_key.to_string());
899
900 let mut stack = vec![Frame {
901 key: start_key.to_string(),
902 successors: self.cycle_successors(start_key, rel_type, None),
903 idx: 0,
904 }];
905
906 while !stack.is_empty() {
907 let next = {
908 let frame = stack.last_mut().unwrap();
909 if frame.idx < frame.successors.len() {
910 let (target_key, edge_rel) = frame.successors[frame.idx].clone();
911 frame.idx += 1;
912 Some((target_key, edge_rel, frame.key.clone()))
913 } else {
914 None
915 }
916 };
917
918 match next {
919 Some((target_key, edge_rel, from_key)) => {
920 if !visited.contains(&target_key) {
921 visited.insert(target_key.clone());
922 rec_stack.insert(target_key.clone());
923 let successors =
924 self.cycle_successors(&target_key, rel_type, Some((&edge_rel, &from_key)));
925 stack.push(Frame {
926 key: target_key,
927 successors,
928 idx: 0,
929 });
930 } else if rec_stack.contains(&target_key) {
931 return true;
932 }
933 }
934 None => {
935 let frame = stack.pop().unwrap();
936 rec_stack.remove(&frame.key);
937 }
938 }
939 }
940
941 false
942 }
943
944 pub fn neighbors(
955 &self,
956 node_ref: &NodeRef,
957 rel_type: Option<&str>,
958 direction: Direction,
959 ) -> Vec<NodeId> {
960 let mut neighbors = Vec::new();
961 let mut seen: HashSet<String> = HashSet::new();
962 let node_key = format!("{}:{}", node_ref.0, node_ref.1);
963
964 if direction == Direction::Out || direction == Direction::Both {
965 if let Some(edges) = self.out_edges.get(&node_key) {
966 for edge in edges {
967 if (rel_type.is_none() || rel_type == Some(&edge.rel_type))
968 && seen.insert(edge.target.to_key())
969 {
970 neighbors.push(edge.target.clone());
971 }
972 }
973 }
974 }
975
976 if direction == Direction::In || direction == Direction::Both {
977 if let Some(edges) = self.in_edges.get(&node_key) {
978 for edge in edges {
979 if (rel_type.is_none() || rel_type == Some(&edge.rel_type))
980 && seen.insert(edge.source.to_key())
981 {
982 neighbors.push(edge.source.clone());
983 }
984 }
985 }
986 }
987
988 neighbors
989 }
990
991 pub fn multi_hop(
993 &self,
994 start: &NodeRef,
995 rel_type: Option<&str>,
996 hops: usize,
997 direction: Direction,
998 ) -> Vec<NodeId> {
999 if hops == 0 {
1000 return vec![NodeId::new(start.0, start.1)];
1001 }
1002
1003 let start_key = format!("{}:{}", start.0, start.1);
1004 let mut current: HashSet<String> = HashSet::new();
1005 current.insert(start_key.clone());
1006
1007 let mut visited: HashSet<String> = HashSet::new();
1008 visited.insert(start_key);
1009
1010 let mut ref_map: HashMap<String, NodeId> = HashMap::new();
1011 ref_map.insert(
1012 format!("{}:{}", start.0, start.1),
1013 NodeId::new(start.0, start.1),
1014 );
1015
1016 for _ in 0..hops {
1017 let mut next_level: HashSet<String> = HashSet::new();
1018
1019 for key in ¤t {
1020 if let Some(node_id) = ref_map.get(key) {
1021 let neighbors = self.neighbors(&node_id.as_ref(), rel_type, direction);
1022 for neighbor in neighbors {
1023 let neighbor_key = neighbor.to_key();
1024 if !visited.contains(&neighbor_key) {
1025 next_level.insert(neighbor_key.clone());
1026 ref_map.insert(neighbor_key.clone(), neighbor);
1027 }
1028 }
1029 }
1030 }
1031
1032 for key in &next_level {
1033 visited.insert(key.clone());
1034 }
1035 current = next_level;
1036 }
1037
1038 current
1039 .iter()
1040 .filter_map(|key| ref_map.get(key).cloned())
1041 .collect()
1042 }
1043
1044 pub fn multi_hop_range(
1046 &self,
1047 start: &NodeRef,
1048 rel_type: Option<&str>,
1049 min_hops: usize,
1050 max_hops: usize,
1051 direction: Direction,
1052 ) -> Vec<NodeId> {
1053 let start_key = format!("{}:{}", start.0, start.1);
1054 let mut result: HashSet<String> = HashSet::new();
1055 let mut current: HashSet<String> = HashSet::new();
1056 current.insert(start_key.clone());
1057
1058 let mut visited: HashSet<String> = HashSet::new();
1059 visited.insert(start_key);
1060
1061 let mut ref_map: HashMap<String, NodeId> = HashMap::new();
1062 ref_map.insert(
1063 format!("{}:{}", start.0, start.1),
1064 NodeId::new(start.0, start.1),
1065 );
1066
1067 for hop in 1..=max_hops {
1068 let mut next_level: HashSet<String> = HashSet::new();
1069
1070 for key in ¤t {
1071 if let Some(node_id) = ref_map.get(key) {
1072 let neighbors = self.neighbors(&node_id.as_ref(), rel_type, direction);
1073 for neighbor in neighbors {
1074 let neighbor_key = neighbor.to_key();
1075 if !visited.contains(&neighbor_key) {
1076 next_level.insert(neighbor_key.clone());
1077 ref_map.insert(neighbor_key.clone(), neighbor);
1078 if hop >= min_hops {
1079 result.insert(neighbor_key);
1080 }
1081 }
1082 }
1083 }
1084 }
1085
1086 for key in &next_level {
1087 visited.insert(key.clone());
1088 }
1089 current = next_level;
1090
1091 if current.is_empty() {
1092 break;
1093 }
1094 }
1095
1096 result
1097 .iter()
1098 .filter_map(|key| ref_map.get(key).cloned())
1099 .collect()
1100 }
1101
1102 pub fn shortest_path(
1108 &self,
1109 start: &NodeRef,
1110 end: &NodeRef,
1111 rel_type: Option<&str>,
1112 max_hops: usize,
1113 direction: Direction,
1114 ) -> Option<Path> {
1115 let start_id = NodeId::new(start.0, start.1);
1116 let end_id = NodeId::new(end.0, end.1);
1117
1118 if start_id == end_id {
1119 return Some(Path::new(vec![start_id], vec![]));
1120 }
1121
1122 let end_key = end_id.to_key();
1123 let mut visited: HashSet<String> = HashSet::new();
1124 visited.insert(start_id.to_key());
1125
1126 let mut queue: VecDeque<(NodeId, Vec<NodeId>, Vec<Edge>)> = VecDeque::new();
1127 queue.push_back((start_id.clone(), vec![start_id], vec![]));
1128
1129 while let Some((current, path_nodes, path_edges)) = queue.pop_front() {
1130 if path_nodes.len() > max_hops.saturating_add(1) {
1131 continue;
1132 }
1133
1134 let current_key = current.to_key();
1135
1136 if direction != Direction::In {
1137 if let Some(edges) = self.out_edges.get(¤t_key) {
1138 for edge in edges {
1139 if rel_type.is_some() && rel_type != Some(&edge.rel_type) {
1140 continue;
1141 }
1142
1143 let target_key = edge.target.to_key();
1144 if target_key == end_key {
1145 let mut nodes = path_nodes.clone();
1146 nodes.push(edge.target.clone());
1147 let mut edges = path_edges.clone();
1148 edges.push(edge.clone());
1149 return Some(Path::new(nodes, edges));
1150 }
1151
1152 if !visited.contains(&target_key) {
1153 visited.insert(target_key);
1154 let mut nodes = path_nodes.clone();
1155 nodes.push(edge.target.clone());
1156 let mut edges = path_edges.clone();
1157 edges.push(edge.clone());
1158 queue.push_back((edge.target.clone(), nodes, edges));
1159 }
1160 }
1161 }
1162 }
1163
1164 if direction == Direction::In || direction == Direction::Both {
1165 if let Some(edges) = self.in_edges.get(¤t_key) {
1166 for edge in edges {
1167 if rel_type.is_some() && rel_type != Some(&edge.rel_type) {
1168 continue;
1169 }
1170
1171 let source_key = edge.source.to_key();
1172 if source_key == end_key {
1173 let mut nodes = path_nodes.clone();
1174 nodes.push(edge.source.clone());
1175 let mut edges = path_edges.clone();
1176 edges.push(edge.clone());
1177 return Some(Path::new(nodes, edges));
1178 }
1179
1180 if !visited.contains(&source_key) {
1181 visited.insert(source_key);
1182 let mut nodes = path_nodes.clone();
1183 nodes.push(edge.source.clone());
1184 let mut edges = path_edges.clone();
1185 edges.push(edge.clone());
1186 queue.push_back((edge.source.clone(), nodes, edges));
1187 }
1188 }
1189 }
1190 }
1191 }
1192
1193 None
1194 }
1195
1196 pub fn path_exists(
1198 &self,
1199 start: &NodeRef,
1200 end: &NodeRef,
1201 rel_type: Option<&str>,
1202 max_hops: usize,
1203 direction: Direction,
1204 ) -> bool {
1205 self.shortest_path(start, end, rel_type, max_hops, direction)
1206 .is_some()
1207 }
1208
1209 pub fn in_degree(&self, node_ref: &NodeRef) -> usize {
1215 let key = format!("{}:{}", node_ref.0, node_ref.1);
1216 self.in_edges.get(&key).map(|v| v.len()).unwrap_or(0)
1217 }
1218
1219 pub fn out_degree(&self, node_ref: &NodeRef) -> usize {
1221 let key = format!("{}:{}", node_ref.0, node_ref.1);
1222 self.out_edges.get(&key).map(|v| v.len()).unwrap_or(0)
1223 }
1224
1225 pub fn degree(&self, node_ref: &NodeRef) -> usize {
1227 self.in_degree(node_ref) + self.out_degree(node_ref)
1228 }
1229
1230 pub fn is_connected(&self) -> bool {
1232 let all_nodes: Vec<_> = self.nodes().collect();
1233 if all_nodes.is_empty() {
1234 return true;
1235 }
1236
1237 let start = &all_nodes[0];
1238 let start_key = start.to_key();
1239 let mut visited: HashSet<String> = HashSet::new();
1240 visited.insert(start_key.clone());
1241
1242 let mut queue: VecDeque<String> = VecDeque::new();
1243 queue.push_back(start_key);
1244
1245 while let Some(current_key) = queue.pop_front() {
1246 let parts: Vec<&str> = current_key.split(':').collect();
1248 if parts.len() == 2 {
1249 let neighbors = self.neighbors(&(parts[0], parts[1]), None, Direction::Both);
1250 for neighbor in neighbors {
1251 let neighbor_key = neighbor.to_key();
1252 if !visited.contains(&neighbor_key) {
1253 visited.insert(neighbor_key.clone());
1254 queue.push_back(neighbor_key);
1255 }
1256 }
1257 }
1258 }
1259
1260 visited.len() == all_nodes.len()
1261 }
1262
1263 fn document(&self) -> IsonDocument {
1286 let mut doc = IsonDocument::new();
1287
1288 if !self.directed {
1294 let mut block = IsonBlock::new("meta", "graph");
1295 block.fields = vec!["directed".to_string()];
1296 let mut row: HashMap<String, IsonValue> = HashMap::new();
1297 row.insert("directed".to_string(), IsonValue::Bool(false));
1298 block.rows.push(row);
1299 doc.blocks.push(block);
1300 }
1301
1302 let mut node_types: Vec<_> = self.nodes.keys().collect();
1303 node_types.sort();
1304 for node_type in node_types {
1305 let type_nodes = &self.nodes[node_type];
1306 if type_nodes.is_empty() {
1307 continue;
1308 }
1309
1310 let mut prop_keys: Vec<&String> = type_nodes
1311 .values()
1312 .flat_map(|n| n.properties.keys())
1313 .collect::<HashSet<_>>()
1314 .into_iter()
1315 .collect();
1316 prop_keys.sort();
1317
1318 let mut block = IsonBlock::new("nodes", node_type.as_str());
1319 block.fields = std::iter::once("id".to_string())
1320 .chain(prop_keys.iter().map(|k| (*k).clone()))
1321 .collect();
1322
1323 for node in type_nodes.values() {
1324 let mut row: HashMap<String, IsonValue> = HashMap::new();
1325 row.insert("id".to_string(), IsonValue::String(node.id.clone()));
1326 for key in &prop_keys {
1327 let value = match node.properties.get(*key) {
1328 Some(v) => v.clone(),
1329 None => IsonValue::Null,
1330 };
1331 row.insert((*key).clone(), value);
1332 }
1333 block.rows.push(row);
1334 }
1335 doc.blocks.push(block);
1336 }
1337
1338 let mut edge_types: Vec<_> = self.edges.keys().collect();
1339 edge_types.sort();
1340 for rel_type in edge_types {
1341 let edges = &self.edges[rel_type];
1342 if edges.is_empty() {
1343 continue;
1344 }
1345
1346 let mut prop_keys: Vec<&String> = edges
1347 .iter()
1348 .flat_map(|e| e.properties.keys())
1349 .collect::<HashSet<_>>()
1350 .into_iter()
1351 .collect();
1352 prop_keys.sort();
1353
1354 let mut block = IsonBlock::new("edges", rel_type.as_str());
1355 block.fields = ["source".to_string(), "target".to_string()]
1356 .into_iter()
1357 .chain(prop_keys.iter().map(|k| (*k).clone()))
1358 .collect();
1359
1360 for edge in edges {
1361 let mut row: HashMap<String, IsonValue> = HashMap::new();
1362 row.insert(
1363 "source".to_string(),
1364 IsonValue::Reference(IsonReference::with_type(
1365 edge.source.id.clone(),
1366 edge.source.node_type.clone(),
1367 )),
1368 );
1369 row.insert(
1370 "target".to_string(),
1371 IsonValue::Reference(IsonReference::with_type(
1372 edge.target.id.clone(),
1373 edge.target.node_type.clone(),
1374 )),
1375 );
1376 for key in &prop_keys {
1377 let value = match edge.properties.get(*key) {
1378 Some(v) => v.clone(),
1379 None => IsonValue::Null,
1380 };
1381 row.insert((*key).clone(), value);
1382 }
1383 block.rows.push(row);
1384 }
1385 doc.blocks.push(block);
1386 }
1387
1388 doc
1389 }
1390
1391 pub fn to_ison(&self) -> String {
1397 dumps_canonical(&self.document()).unwrap_or_default()
1398 }
1399
1400 pub fn to_isonl(&self) -> String {
1402 dumps_canonical_isonl(&self.document()).unwrap_or_default()
1403 }
1404
1405
1406 fn id_text(value: &IsonValue) -> Option<String> {
1409 match value {
1410 IsonValue::Null => None,
1411 IsonValue::Bool(b) => Some(b.to_string()),
1412 IsonValue::Int(i) => Some(i.to_string()),
1413 IsonValue::Float(f) => Some(f.to_string()),
1414 IsonValue::String(s) => Some(s.clone()),
1415 IsonValue::Reference(r) => Some(r.to_ison()),
1416 }
1417 }
1418
1419 fn build_from_document(doc: &IsonDocument, name: &str) -> Result<Self> {
1420 let mut directed = true;
1424 for block in &doc.blocks {
1425 match block.kind.as_str() {
1426 "nodes" | "edges" => {}
1427 "meta" if block.name == "graph" => {
1428 for row in &block.rows {
1429 if let Some(IsonValue::String(format)) = row.get("format") {
1430 if format == MULTIGRAPH_FORMAT {
1431 return Err(GraphError::ParseError(format!(
1432 "This is a {} document, which may contain multiple \
1433 edges per (rel_type, source, target) triple; this \
1434 port has no MultiGraph and would silently drop them.",
1435 MULTIGRAPH_FORMAT
1436 )));
1437 }
1438 }
1439 if let Some(IsonValue::Bool(b)) = row.get("directed") {
1440 directed = *b;
1441 }
1442 }
1443 }
1444 other => {
1445 return Err(GraphError::ParseError(format!(
1446 "unknown block kind {:?} (expected 'nodes', 'edges' or 'meta')",
1447 other
1448 )))
1449 }
1450 }
1451 }
1452
1453 let mut graph = ISONGraph::new(name);
1454 graph.directed = directed;
1455
1456 for block in &doc.blocks {
1459 if block.kind != "nodes" {
1460 continue;
1461 }
1462 for row in &block.rows {
1463 let id = row
1466 .get("id")
1467 .and_then(Self::id_text)
1468 .ok_or_else(|| GraphError::ParseError("row has no id".into()))?;
1469 let props: Vec<(String, Value)> = row
1470 .iter()
1471 .filter(|(k, _)| k.as_str() != "id")
1472 .map(|(k, v)| (k.clone(), v.clone()))
1473 .collect();
1474 let borrowed: Vec<(&str, Value)> =
1475 props.iter().map(|(k, v)| (k.as_str(), v.clone())).collect();
1476 graph.add_node(&block.name, &id, borrowed)?;
1477 }
1478 }
1479
1480 for block in &doc.blocks {
1481 if block.kind != "edges" {
1482 continue;
1483 }
1484 for row in &block.rows {
1485 let (source, target) = match (row.get("source"), row.get("target")) {
1486 (Some(IsonValue::Reference(s)), Some(IsonValue::Reference(t))) => (
1487 (s.ref_type.clone().unwrap_or_default(), s.id.clone()),
1488 (t.ref_type.clone().unwrap_or_default(), t.id.clone()),
1489 ),
1490 _ => {
1491 return Err(GraphError::ParseError(
1492 "edge row is missing a source or target reference".into(),
1493 ))
1494 }
1495 };
1496 let props: Vec<(String, Value)> = row
1497 .iter()
1498 .filter(|(k, _)| k.as_str() != "source" && k.as_str() != "target")
1499 .map(|(k, v)| (k.clone(), v.clone()))
1500 .collect();
1501 let borrowed: Vec<(&str, Value)> =
1502 props.iter().map(|(k, v)| (k.as_str(), v.clone())).collect();
1503 if !graph.directed
1508 && graph.has_edge(&block.name, (&source.0, &source.1), (&target.0, &target.1))
1509 {
1510 continue;
1511 }
1512 graph.add_edge(
1513 &block.name,
1514 (&source.0, &source.1),
1515 (&target.0, &target.1),
1516 borrowed,
1517 )?;
1518 }
1519 }
1520
1521 Ok(graph)
1522 }
1523
1524 pub fn from_ison(text: &str, name: Option<&str>) -> Result<Self> {
1526 let doc = loads(text)
1527 .map_err(|e| GraphError::ParseError(format!("{}", e)))?;
1528 Self::build_from_document(&doc, name.unwrap_or("graph"))
1529 }
1530
1531 pub fn from_isonl(text: &str, name: Option<&str>) -> Result<Self> {
1533 let doc = loads_isonl(text)
1534 .map_err(|e| GraphError::ParseError(format!("{}", e)))?;
1535 Self::build_from_document(&doc, name.unwrap_or("graph"))
1536 }
1537
1538 pub fn save<P: AsRef<StdPath>>(&self, path: P, format: Option<&str>) -> Result<()> {
1539 let path = path.as_ref();
1540 let actual_format = format.unwrap_or_else(|| {
1541 if path.extension().map(|e| e == "isonl").unwrap_or(false) {
1542 "isonl"
1543 } else {
1544 "ison"
1545 }
1546 });
1547
1548 let content = if actual_format == "isonl" {
1549 self.to_isonl()
1550 } else {
1551 self.to_ison()
1552 };
1553
1554 fs::write(path, content).map_err(GraphError::Io)
1555 }
1556
1557 pub fn load<P: AsRef<StdPath>>(path: P, format: Option<&str>) -> Result<Self> {
1559 let path = path.as_ref();
1560 let content = fs::read_to_string(path).map_err(GraphError::Io)?;
1561
1562 let actual_format = format.unwrap_or_else(|| {
1563 if path.extension().map(|e| e == "isonl").unwrap_or(false) {
1564 "isonl"
1565 } else {
1566 "ison"
1567 }
1568 });
1569
1570 let graph_name = path.file_stem().and_then(|s| s.to_str()).unwrap_or("graph");
1571
1572 if actual_format == "isonl" {
1573 Self::from_isonl(&content, Some(graph_name))
1574 } else {
1575 Self::from_ison(&content, Some(graph_name))
1576 }
1577 }
1578
1579 pub fn get_edge(&self, rel_type: &str, source: (&str, &str), target: (&str, &str)) -> Result<&Edge> {
1585 let source_id = NodeId::new(source.0, source.1);
1586 let target_id = NodeId::new(target.0, target.1);
1587
1588 if let Some(edges) = self.edges.get(rel_type) {
1589 for edge in edges {
1590 if edge.source == source_id && edge.target == target_id {
1591 return Ok(edge);
1592 }
1593 }
1594 }
1595
1596 Err(GraphError::EdgeNotFound(
1597 format!("{}:{}", source.0, source.1),
1598 format!("{}:{}", target.0, target.1),
1599 ))
1600 }
1601
1602 pub fn connected_components(&self) -> Vec<HashSet<NodeId>> {
1608 let mut visited: HashSet<String> = HashSet::new();
1609 let mut components: Vec<HashSet<NodeId>> = Vec::new();
1610
1611 for node in self.nodes() {
1612 let node_key = node.to_key();
1613 if !visited.contains(&node_key) {
1614 let mut component: HashSet<NodeId> = HashSet::new();
1615 let mut queue: VecDeque<NodeId> = VecDeque::new();
1616 queue.push_back(node.node_id());
1617
1618 while let Some(current) = queue.pop_front() {
1619 let current_key = current.to_key();
1620 if visited.contains(¤t_key) {
1621 continue;
1622 }
1623 visited.insert(current_key);
1624 component.insert(current.clone());
1625
1626 let neighbors = self.neighbors(¤t.as_ref(), None, Direction::Both);
1628 for neighbor in neighbors {
1629 if !visited.contains(&neighbor.to_key()) {
1630 queue.push_back(neighbor);
1631 }
1632 }
1633 }
1634
1635 components.push(component);
1636 }
1637 }
1638
1639 components
1640 }
1641
1642 fn edges_to_follow(
1644 &self,
1645 node: &NodeId,
1646 rel_type: Option<&str>,
1647 direction: Direction,
1648 ) -> Vec<(Edge, NodeId)> {
1649 let node_key = node.to_key();
1650 let mut edges_to_follow: Vec<(Edge, NodeId)> = Vec::new();
1651
1652 if direction == Direction::Out || direction == Direction::Both {
1653 if let Some(out_edges) = self.out_edges.get(&node_key) {
1654 for edge in out_edges {
1655 if rel_type.is_none() || rel_type == Some(&edge.rel_type) {
1656 edges_to_follow.push((edge.clone(), edge.target.clone()));
1657 }
1658 }
1659 }
1660 }
1661
1662 if direction == Direction::In || direction == Direction::Both {
1663 if let Some(in_edges) = self.in_edges.get(&node_key) {
1664 for edge in in_edges {
1665 if rel_type.is_none() || rel_type == Some(&edge.rel_type) {
1666 edges_to_follow.push((edge.clone(), edge.source.clone()));
1667 }
1668 }
1669 }
1670 }
1671
1672 edges_to_follow
1673 }
1674
1675 pub fn all_paths(
1677 &self,
1678 start: &NodeRef,
1679 end: &NodeRef,
1680 rel_type: Option<&str>,
1681 max_hops: usize,
1682 direction: Direction,
1683 ) -> Vec<Path> {
1684 let start_id = NodeId::new(start.0, start.1);
1685 let end_id = NodeId::new(end.0, end.1);
1686 let mut paths: Vec<Path> = Vec::new();
1687
1688 let mut visited: HashSet<String> = HashSet::new();
1689 visited.insert(start_id.to_key());
1690 let mut path_nodes = vec![start_id.clone()];
1691 let mut path_edges: Vec<Edge> = Vec::new();
1692
1693 if start_id == end_id {
1694 paths.push(Path::new(path_nodes, path_edges));
1695 return paths;
1696 }
1697
1698 struct Frame {
1699 options: Vec<(Edge, NodeId)>,
1700 idx: usize,
1701 }
1702
1703 let mut stack = vec![Frame {
1704 options: self.edges_to_follow(&start_id, rel_type, direction),
1705 idx: 0,
1706 }];
1707
1708 while !stack.is_empty() {
1709 let next = {
1710 let frame = stack.last_mut().unwrap();
1711 if frame.idx < frame.options.len() {
1712 let option = frame.options[frame.idx].clone();
1713 frame.idx += 1;
1714 Some(option)
1715 } else {
1716 None
1717 }
1718 };
1719
1720 match next {
1721 Some((edge, next_node)) => {
1722 let next_key = next_node.to_key();
1723 if visited.contains(&next_key) {
1724 continue;
1725 }
1726
1727 visited.insert(next_key.clone());
1728 path_nodes.push(next_node.clone());
1729 path_edges.push(edge);
1730
1731 if path_nodes.len() > max_hops.saturating_add(1) {
1732 path_nodes.pop();
1734 path_edges.pop();
1735 visited.remove(&next_key);
1736 continue;
1737 }
1738
1739 if next_node == end_id {
1740 paths.push(Path::new(path_nodes.clone(), path_edges.clone()));
1741 path_nodes.pop();
1742 path_edges.pop();
1743 visited.remove(&next_key);
1744 continue;
1745 }
1746
1747 stack.push(Frame {
1748 options: self.edges_to_follow(&next_node, rel_type, direction),
1749 idx: 0,
1750 });
1751 }
1752 None => {
1753 stack.pop();
1754 if !stack.is_empty() {
1757 if let Some(popped) = path_nodes.pop() {
1758 path_edges.pop();
1759 visited.remove(&popped.to_key());
1760 }
1761 }
1762 }
1763 }
1764 }
1765
1766 paths
1767 }
1768
1769 pub fn traverse(
1775 &self,
1776 start: &NodeRef,
1777 pattern: &[(String, Direction)],
1778 filter_fn: Option<&dyn Fn(&Node) -> bool>,
1779 ) -> Vec<NodeId> {
1780 let start_id = NodeId::new(start.0, start.1);
1781 let mut current: HashSet<String> = HashSet::new();
1782 current.insert(start_id.to_key());
1783
1784 let mut ref_map: HashMap<String, NodeId> = HashMap::new();
1785 ref_map.insert(start_id.to_key(), start_id);
1786
1787 for (rel_type, direction) in pattern {
1788 let mut next_level: HashSet<String> = HashSet::new();
1789
1790 for key in ¤t {
1791 if let Some(node_id) = ref_map.get(key) {
1792 let neighbors = self.neighbors(&node_id.as_ref(), Some(rel_type), *direction);
1793 for neighbor in neighbors {
1794 let neighbor_key = neighbor.to_key();
1795
1796 let should_include = match filter_fn {
1797 None => true,
1798 Some(f) => {
1799 if let Ok(node) = self.get_node_by_id(&neighbor) {
1800 f(node)
1801 } else {
1802 false
1803 }
1804 }
1805 };
1806
1807 if should_include {
1808 next_level.insert(neighbor_key.clone());
1809 ref_map.insert(neighbor_key, neighbor);
1810 }
1811 }
1812 }
1813 }
1814
1815 current = next_level;
1816 if current.is_empty() {
1817 break;
1818 }
1819 }
1820
1821 current
1822 .iter()
1823 .filter_map(|key| ref_map.get(key).cloned())
1824 .collect()
1825 }
1826
1827 pub fn query(&self, pattern: &str) -> Result<Vec<NodeId>> {
1838 static HOP_REGEX: OnceLock<Regex> = OnceLock::new();
1839 static RANGE_REGEX: OnceLock<Regex> = OnceLock::new();
1840 static SIMPLE_REGEX: OnceLock<Regex> = OnceLock::new();
1841
1842 let p = pattern.trim();
1843
1844 let hop_regex = HOP_REGEX.get_or_init(|| {
1846 Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\*(\d+)\]->\s*\*$").unwrap()
1847 });
1848 if let Some(caps) = hop_regex.captures(p) {
1849 let node_type = caps.get(1).unwrap().as_str();
1850 let node_id = caps.get(2).unwrap().as_str();
1851 let rel_type = caps.get(3).unwrap().as_str();
1852 let hops: usize = caps.get(4).unwrap().as_str().parse().unwrap_or(1);
1853 return Ok(self.multi_hop(&(node_type, node_id), Some(rel_type), hops, Direction::Out));
1854 }
1855
1856 let range_regex = RANGE_REGEX.get_or_init(|| {
1858 Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\*(\d+)\.\.(\d+)\]->\s*\*$").unwrap()
1859 });
1860 if let Some(caps) = range_regex.captures(p) {
1861 let node_type = caps.get(1).unwrap().as_str();
1862 let node_id = caps.get(2).unwrap().as_str();
1863 let rel_type = caps.get(3).unwrap().as_str();
1864 let min_hops: usize = caps.get(4).unwrap().as_str().parse().unwrap_or(1);
1865 let max_hops: usize = caps.get(5).unwrap().as_str().parse().unwrap_or(3);
1866 return Ok(self.multi_hop_range(
1867 &(node_type, node_id),
1868 Some(rel_type),
1869 min_hops,
1870 max_hops,
1871 Direction::Out,
1872 ));
1873 }
1874
1875 let simple_regex = SIMPLE_REGEX
1877 .get_or_init(|| Regex::new(r"^:(\w+):(\w+)\s*-\[:(\w+)\]->\s*\*$").unwrap());
1878 if let Some(caps) = simple_regex.captures(p) {
1879 let node_type = caps.get(1).unwrap().as_str();
1880 let node_id = caps.get(2).unwrap().as_str();
1881 let rel_type = caps.get(3).unwrap().as_str();
1882 return Ok(self.neighbors(&(node_type, node_id), Some(rel_type), Direction::Out));
1883 }
1884
1885 Err(GraphError::ParseError(format!("Invalid query pattern: {}", pattern)))
1886 }
1887
1888 pub fn start(&self, node_ref: &NodeRef) -> GraphTraversal<'_> {
1894 GraphTraversal::new(self, NodeId::new(node_ref.0, node_ref.1))
1895 }
1896}
1897
1898pub struct GraphTraversal<'a> {
1904 graph: &'a ISONGraph,
1905 current: HashSet<String>,
1906 visited: HashSet<String>,
1907 ref_map: HashMap<String, NodeId>,
1908}
1909
1910impl<'a> GraphTraversal<'a> {
1911 pub fn new(graph: &'a ISONGraph, start: NodeId) -> Self {
1912 let start_key = start.to_key();
1913 let mut current = HashSet::new();
1914 current.insert(start_key.clone());
1915
1916 let mut visited = HashSet::new();
1917 visited.insert(start_key.clone());
1918
1919 let mut ref_map = HashMap::new();
1920 ref_map.insert(start_key, start);
1921
1922 Self {
1923 graph,
1924 current,
1925 visited,
1926 ref_map,
1927 }
1928 }
1929
1930 pub fn hop(mut self, rel_type: Option<&str>, direction: Direction) -> Self {
1932 let mut next_level: HashSet<String> = HashSet::new();
1933
1934 for key in &self.current {
1935 if let Some(node_id) = self.ref_map.get(key) {
1936 let neighbors = self.graph.neighbors(&node_id.as_ref(), rel_type, direction);
1937 for neighbor in neighbors {
1938 let neighbor_key = neighbor.to_key();
1939 if !self.visited.contains(&neighbor_key) {
1940 next_level.insert(neighbor_key.clone());
1941 self.ref_map.insert(neighbor_key, neighbor);
1942 }
1943 }
1944 }
1945 }
1946
1947 for key in &next_level {
1948 self.visited.insert(key.clone());
1949 }
1950 self.current = next_level;
1951 self
1952 }
1953
1954 pub fn hops(mut self, n: usize, rel_type: Option<&str>, direction: Direction) -> Self {
1956 for _ in 0..n {
1957 self = self.hop(rel_type, direction);
1958 }
1959 self
1960 }
1961
1962 pub fn filter<F>(mut self, f: F) -> Self
1964 where
1965 F: Fn(&Node) -> bool,
1966 {
1967 let filtered: HashSet<String> = self
1968 .current
1969 .iter()
1970 .filter(|key| {
1971 if let Some(node_id) = self.ref_map.get(*key) {
1972 if let Ok(node) = self.graph.get_node_by_id(node_id) {
1973 return f(node);
1974 }
1975 }
1976 false
1977 })
1978 .cloned()
1979 .collect();
1980 self.current = filtered;
1981 self
1982 }
1983
1984 pub fn collect(self) -> Vec<NodeId> {
1986 self.current
1987 .iter()
1988 .filter_map(|key| self.ref_map.get(key).cloned())
1989 .collect()
1990 }
1991
1992 pub fn collect_nodes(self) -> Vec<Node> {
1994 self.current
1995 .iter()
1996 .filter_map(|key| {
1997 self.ref_map
1998 .get(key)
1999 .and_then(|id| self.graph.get_node_by_id(id).ok().cloned())
2000 })
2001 .collect()
2002 }
2003
2004 pub fn count(&self) -> usize {
2006 self.current.len()
2007 }
2008
2009 pub fn first(&self) -> Option<NodeId> {
2011 self.current
2012 .iter()
2013 .next()
2014 .and_then(|key| self.ref_map.get(key).cloned())
2015 }
2016}
2017
2018#[cfg(test)]
2023mod tests {
2024 use super::*;
2025
2026 #[test]
2027 fn test_add_and_get_node() {
2028 let mut graph = ISONGraph::new("test");
2029 graph
2030 .add_node("person", "1", props![("name", "Alice"), ("age", "30")])
2031 .unwrap();
2032
2033 let node = graph.get_node("person", "1").unwrap();
2034 assert_eq!(node.node_type, "person");
2035 assert_eq!(node.id, "1");
2036 assert_eq!(crate::value_to_text(node.properties.get("name").unwrap()), "Alice");
2037 }
2038
2039 #[test]
2040 fn test_duplicate_node() {
2041 let mut graph = ISONGraph::new("test");
2042 graph.add_node("person", "1", props![]).unwrap();
2043 assert!(graph.add_node("person", "1", props![]).is_err());
2044 }
2045
2046 #[test]
2047 fn test_add_node_rejects_colon() {
2048 let mut graph = ISONGraph::new("test");
2049 assert!(matches!(
2050 graph.add_node("per:son", "1", props![]),
2051 Err(GraphError::InvalidIdentifier(_))
2052 ));
2053 assert!(matches!(
2054 graph.add_node("person", "1:2", props![]),
2055 Err(GraphError::InvalidIdentifier(_))
2056 ));
2057 assert_eq!(graph.node_count(), 0);
2058 }
2059
2060 #[test]
2065 fn test_add_node_rejects_pipe() {
2066 let mut graph = ISONGraph::new("test");
2067 assert!(matches!(
2068 graph.add_node("per|son", "1", props![]),
2069 Err(GraphError::InvalidIdentifier(_))
2070 ));
2071 assert!(matches!(
2072 graph.add_node("person", "1|2", props![]),
2073 Err(GraphError::InvalidIdentifier(_))
2074 ));
2075 assert_eq!(graph.node_count(), 0);
2076 }
2077
2078 #[test]
2079 fn test_add_edge_rejects_colon_and_pipe_in_rel_type() {
2080 let mut graph = ISONGraph::new("test");
2081 graph.add_node("person", "1", props![]).unwrap();
2082 graph.add_node("person", "2", props![]).unwrap();
2083 assert!(matches!(
2084 graph.add_edge("KN:OWS", ("person", "1"), ("person", "2"), props![]),
2085 Err(GraphError::InvalidIdentifier(_))
2086 ));
2087 assert!(matches!(
2088 graph.add_edge("KN|OWS", ("person", "1"), ("person", "2"), props![]),
2089 Err(GraphError::InvalidIdentifier(_))
2090 ));
2091 assert_eq!(graph.edge_count(), 0);
2092 }
2093
2094 #[test]
2095 fn test_unrepresentable_identifiers_are_rejected() {
2096 for bad in ["a b", "a\tb", "a\nb", ""] {
2100 let mut graph = ISONGraph::new("test");
2101 assert!(graph.add_node(bad, "1", props![]).is_err(), "type {:?}", bad);
2102 assert!(graph.add_node("p", bad, props![]).is_err(), "id {:?}", bad);
2103 }
2104
2105 for bad in ["a\"b", "a\\b"] {
2107 let mut graph = ISONGraph::new("test");
2108 assert!(graph.add_node(bad, "1", props![]).is_err(), "type {:?}", bad);
2109 assert!(graph.add_node("p", bad, props![]).is_ok(), "id {:?}", bad);
2110 }
2111 }
2112
2113 #[test]
2114 fn test_valid_identifiers_still_allowed() {
2115 let mut graph = ISONGraph::new("test");
2116 graph.add_node("a-type", "an-id-1", props![]).unwrap();
2117 graph.add_node("b.c", "#2", props![]).unwrap();
2118 graph
2119 .add_edge("SHARES_BORDER_WITH", ("a-type", "an-id-1"), ("b.c", "#2"), props![])
2120 .unwrap();
2121 assert_eq!(graph.edge_count(), 1);
2122
2123 let restored = ISONGraph::from_ison(&graph.to_ison(), None).unwrap();
2124 assert_eq!(restored.node_count(), 2);
2125 assert_eq!(restored.edge_count(), 1);
2126 }
2127
2128 #[test]
2129 fn test_no_longer_crashes_on_ison_roundtrip() {
2130 let mut graph = ISONGraph::new("test");
2133 assert!(graph.add_node("a:b", "1", props![]).is_err());
2134 }
2135
2136 #[test]
2137 fn test_no_longer_crashes_on_isonl_roundtrip() {
2138 let mut graph = ISONGraph::new("test");
2139 assert!(graph.add_node("rel|type", "1", props![]).is_err());
2140 }
2141
2142 #[cfg(feature = "serde")]
2143 #[test]
2144 fn test_serde_deserialize_rejects_bad_identifiers() {
2145 let bad = r#"{"name":"t","directed":true,"nodes":{"a:b":{"1":{"node_type":"a:b","id":"1","properties":{}}}},"edges":{}}"#;
2151 let result: std::result::Result<ISONGraph, _> = serde_json::from_str(bad);
2152 assert!(result.is_err());
2153
2154 let good = r#"{"name":"t","directed":true,"nodes":{"a":{"1":{"node_type":"a","id":"1","properties":{}}}},"edges":{}}"#;
2155 let graph: ISONGraph = serde_json::from_str(good).unwrap();
2156 assert_eq!(graph.node_count(), 1);
2157 }
2158
2159 #[test]
2160 fn test_add_and_has_edge() {
2161 let mut graph = ISONGraph::new("test");
2162 graph.add_node("person", "1", props![]).unwrap();
2163 graph.add_node("person", "2", props![]).unwrap();
2164 graph
2165 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2166 .unwrap();
2167
2168 assert!(graph.has_edge("KNOWS", ("person", "1"), ("person", "2")));
2169 assert!(!graph.has_edge("KNOWS", ("person", "2"), ("person", "1")));
2170 }
2171
2172 #[test]
2173 fn test_neighbors() {
2174 let mut graph = ISONGraph::new("test");
2175 graph.add_node("person", "1", props![]).unwrap();
2176 graph.add_node("person", "2", props![]).unwrap();
2177 graph.add_node("person", "3", props![]).unwrap();
2178 graph
2179 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2180 .unwrap();
2181 graph
2182 .add_edge("KNOWS", ("person", "1"), ("person", "3"), props![])
2183 .unwrap();
2184
2185 let friends = graph.neighbors(&("person", "1"), Some("KNOWS"), Direction::Out);
2186 assert_eq!(friends.len(), 2);
2187 }
2188
2189 #[test]
2190 fn test_multi_hop() {
2191 let mut graph = ISONGraph::new("test");
2192 graph.add_node("person", "1", props![]).unwrap();
2193 graph.add_node("person", "2", props![]).unwrap();
2194 graph.add_node("person", "3", props![]).unwrap();
2195 graph
2196 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2197 .unwrap();
2198 graph
2199 .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2200 .unwrap();
2201
2202 let two_hops = graph.multi_hop(&("person", "1"), Some("KNOWS"), 2, Direction::Out);
2203 assert_eq!(two_hops.len(), 1);
2204 assert_eq!(two_hops[0].id, "3");
2205 }
2206
2207 #[test]
2208 fn test_shortest_path() {
2209 let mut graph = ISONGraph::new("test");
2210 graph.add_node("person", "1", props![]).unwrap();
2211 graph.add_node("person", "2", props![]).unwrap();
2212 graph.add_node("person", "3", props![]).unwrap();
2213 graph
2214 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2215 .unwrap();
2216 graph
2217 .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2218 .unwrap();
2219
2220 let path = graph
2221 .shortest_path(&("person", "1"), &("person", "3"), Some("KNOWS"), 10, Direction::Out)
2222 .unwrap();
2223 assert_eq!(path.length(), 2);
2224 assert_eq!(path.nodes.len(), 3);
2225 }
2226
2227 #[test]
2228 fn test_node_count() {
2229 let mut graph = ISONGraph::new("test");
2230 graph.add_node("person", "1", props![]).unwrap();
2231 graph.add_node("person", "2", props![]).unwrap();
2232 graph.add_node("company", "100", props![]).unwrap();
2233
2234 assert_eq!(graph.node_count(), 3);
2235 assert_eq!(graph.node_count_of_type("person"), 2);
2236 assert_eq!(graph.node_count_of_type("company"), 1);
2237 }
2238
2239 #[test]
2240 fn test_to_ison() {
2241 let mut graph = ISONGraph::new("test");
2242 graph
2243 .add_node("person", "1", props![("name", "Alice")])
2244 .unwrap();
2245 graph
2246 .add_node("person", "2", props![("name", "Bob")])
2247 .unwrap();
2248 graph
2249 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2250 .unwrap();
2251
2252 let ison = graph.to_ison();
2253 assert!(ison.contains("nodes.person"));
2254 assert!(ison.contains("edges.KNOWS"));
2255 assert!(ison.contains("Alice"));
2256 }
2257
2258 fn special_values_graph() -> ISONGraph {
2259 let mut graph = ISONGraph::new("test");
2260 graph
2261 .add_node(
2262 "person",
2263 "1",
2264 props![
2265 ("name", "Alice Smith"),
2266 ("bio", "a|b"),
2267 ("note", "line1\nline2"),
2268 ("empty", ""),
2269 ],
2270 )
2271 .unwrap();
2272 graph
2273 .add_node(
2274 "person",
2275 "2",
2276 props![
2277 ("name", "Bob"),
2278 ("bio", "he said \"hi\""),
2279 ("note", "x"),
2280 ("empty", "y"),
2281 ],
2282 )
2283 .unwrap();
2284 graph
2285 .add_edge(
2286 "KNOWS",
2287 ("person", "1"),
2288 ("person", "2"),
2289 props![("where", "New York"), ("tag", "")],
2290 )
2291 .unwrap();
2292 graph
2293 }
2294
2295 fn assert_special_values(restored: &ISONGraph) {
2296 assert_eq!(restored.node_count(), 2);
2297 assert_eq!(restored.edge_count(), 1);
2298 let n1 = restored.get_node("person", "1").unwrap();
2299 assert_eq!(crate::value_to_text(n1.properties.get("name").unwrap()), "Alice Smith");
2300 assert_eq!(crate::value_to_text(n1.properties.get("bio").unwrap()), "a|b");
2301 assert_eq!(crate::value_to_text(n1.properties.get("note").unwrap()), "line1\nline2");
2302 assert_eq!(crate::value_to_text(n1.properties.get("empty").unwrap()), "");
2303 let n2 = restored.get_node("person", "2").unwrap();
2304 assert_eq!(crate::value_to_text(n2.properties.get("bio").unwrap()), "he said \"hi\"");
2305 let e = restored
2306 .get_edge("KNOWS", ("person", "1"), ("person", "2"))
2307 .unwrap();
2308 assert_eq!(crate::value_to_text(e.properties.get("where").unwrap()), "New York");
2309 assert_eq!(crate::value_to_text(e.properties.get("tag").unwrap()), "");
2310 }
2311
2312 #[test]
2313 fn test_ison_round_trip_special_values() {
2314 let graph = special_values_graph();
2315 let restored = ISONGraph::from_ison(&graph.to_ison(), Some("test")).unwrap();
2316 assert_special_values(&restored);
2317 }
2318
2319 #[test]
2320 fn test_isonl_round_trip_special_values() {
2321 let graph = special_values_graph();
2322 let restored = ISONGraph::from_isonl(&graph.to_isonl(), Some("test")).unwrap();
2323 assert_special_values(&restored);
2324 }
2325
2326 #[test]
2327 fn test_is_connected() {
2328 let mut graph = ISONGraph::new("test");
2329 graph.add_node("person", "1", props![]).unwrap();
2330 graph.add_node("person", "2", props![]).unwrap();
2331 graph
2332 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2333 .unwrap();
2334
2335 assert!(graph.is_connected());
2336
2337 graph.add_node("person", "3", props![]).unwrap();
2338 assert!(!graph.is_connected());
2339 }
2340
2341 #[test]
2346 fn test_from_ison() {
2347 let ison_text = r#"
2348nodes.person
2349id name age
2350alice Alice 30
2351bob Bob 25
2352
2353edges.KNOWS
2354source target since
2355:person:alice :person:bob 2020
2356"#;
2357
2358 let graph = ISONGraph::from_ison(ison_text, Some("test")).unwrap();
2359 assert_eq!(graph.node_count(), 2);
2360 assert_eq!(graph.edge_count(), 1);
2361 assert!(graph.has_node("person", "alice"));
2362 assert!(graph.has_node("person", "bob"));
2363 assert!(graph.has_edge("KNOWS", ("person", "alice"), ("person", "bob")));
2364 }
2365
2366 #[test]
2367 fn test_from_isonl() {
2368 let isonl_text = "nodes.person|id name age|alice Alice 30\n\
2369 nodes.person|id name age|bob Bob 25\n\
2370 edges.KNOWS|source target since|:person:alice :person:bob 2020\n";
2371
2372 let graph = ISONGraph::from_isonl(isonl_text, Some("test")).unwrap();
2373 assert_eq!(graph.node_count(), 2);
2374 assert_eq!(graph.edge_count(), 1);
2375 assert!(graph.has_node("person", "alice"));
2376 assert!(graph.has_edge("KNOWS", ("person", "alice"), ("person", "bob")));
2377 }
2378
2379 #[test]
2380 fn test_from_ison_malformed_errors() {
2381 let bad_row = "nodes.person\nid name\nalice Alice Extra";
2383 assert!(matches!(
2384 ISONGraph::from_ison(bad_row, None),
2385 Err(GraphError::ParseError(_))
2386 ));
2387
2388 let bad_header = "people\nid name\nalice Alice";
2390 assert!(matches!(
2391 ISONGraph::from_ison(bad_header, None),
2392 Err(GraphError::ParseError(_))
2393 ));
2394
2395 let bad_kind = "vertices.person\nid name\nalice Alice";
2397 assert!(matches!(
2398 ISONGraph::from_ison(bad_kind, None),
2399 Err(GraphError::ParseError(_))
2400 ));
2401 }
2402
2403 #[test]
2404 fn test_from_isonl_malformed_errors() {
2405 assert!(matches!(
2407 ISONGraph::from_isonl("nodes.person|id name", None),
2408 Err(GraphError::ParseError(_))
2409 ));
2410 let padded = ISONGraph::from_isonl("nodes.person|id name|alice", None).unwrap();
2414 assert_eq!(padded.node_count(), 1);
2415 assert!(matches!(
2417 ISONGraph::from_isonl("nodesperson|id|alice", None),
2418 Err(GraphError::ParseError(_))
2419 ));
2420 }
2421
2422 #[test]
2427 fn test_connected_components() {
2428 let mut graph = ISONGraph::new("test");
2429 graph.add_node("person", "1", props![]).unwrap();
2430 graph.add_node("person", "2", props![]).unwrap();
2431 graph.add_node("person", "3", props![]).unwrap();
2432 graph.add_node("person", "4", props![]).unwrap();
2433 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2434 graph.add_edge("KNOWS", ("person", "3"), ("person", "4"), props![]).unwrap();
2435
2436 let components = graph.connected_components();
2437 assert_eq!(components.len(), 2);
2438 }
2439
2440 #[test]
2441 fn test_all_paths() {
2442 let mut graph = ISONGraph::new("test");
2443 graph.add_node("person", "1", props![]).unwrap();
2444 graph.add_node("person", "2", props![]).unwrap();
2445 graph.add_node("person", "3", props![]).unwrap();
2446 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2447 graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2448 graph.add_edge("KNOWS", ("person", "1"), ("person", "3"), props![]).unwrap();
2449
2450 let paths = graph.all_paths(&("person", "1"), &("person", "3"), None, 5, Direction::Out);
2451 assert_eq!(paths.len(), 2); }
2453
2454 #[test]
2455 fn test_get_edge() {
2456 let mut graph = ISONGraph::new("test");
2457 graph.add_node("person", "1", props![]).unwrap();
2458 graph.add_node("person", "2", props![]).unwrap();
2459 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020")]).unwrap();
2460
2461 let edge = graph.get_edge("KNOWS", ("person", "1"), ("person", "2")).unwrap();
2462 assert_eq!(edge.rel_type, "KNOWS");
2463 assert_eq!(crate::value_to_text(edge.properties.get("since").unwrap()), "2020");
2464 }
2465
2466 #[test]
2471 fn test_query_pattern() {
2472 let mut graph = ISONGraph::new("test");
2473 graph.add_node("person", "1", props![]).unwrap();
2474 graph.add_node("person", "2", props![]).unwrap();
2475 graph.add_node("person", "3", props![]).unwrap();
2476 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2477 graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2478
2479 let result = graph.query(":person:1 -[:KNOWS]-> *").unwrap();
2480 assert_eq!(result.len(), 1);
2481 assert_eq!(result[0].id, "2");
2482
2483 let result2 = graph.query(":person:1 -[:KNOWS*2]-> *").unwrap();
2484 assert_eq!(result2.len(), 1);
2485 assert_eq!(result2[0].id, "3");
2486 }
2487
2488 #[test]
2493 fn test_start_method() {
2494 let mut graph = ISONGraph::new("test");
2495 graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2496 graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2497 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2498
2499 let result = graph.start(&("person", "1"))
2500 .hop(Some("KNOWS"), Direction::Out)
2501 .collect();
2502
2503 assert_eq!(result.len(), 1);
2504 assert_eq!(result[0].id, "2");
2505 }
2506
2507 #[test]
2508 fn test_fluent_collect_nodes() {
2509 let mut graph = ISONGraph::new("test");
2510 graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2511 graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2512 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2513
2514 let nodes = graph.start(&("person", "1"))
2515 .hop(Some("KNOWS"), Direction::Out)
2516 .collect_nodes();
2517
2518 assert_eq!(nodes.len(), 1);
2519 assert_eq!(crate::value_to_text(nodes[0].properties.get("name").unwrap()), "Bob");
2520 }
2521
2522 #[test]
2523 fn test_fluent_filter() {
2524 let mut graph = ISONGraph::new("test");
2525 graph.add_node("person", "1", props![("name", "Alice")]).unwrap();
2526 graph.add_node("person", "2", props![("name", "Bob")]).unwrap();
2527 graph.add_node("person", "3", props![("name", "Charlie")]).unwrap();
2528 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2529 graph.add_edge("KNOWS", ("person", "1"), ("person", "3"), props![]).unwrap();
2530
2531 let result = graph.start(&("person", "1"))
2532 .hop(Some("KNOWS"), Direction::Out)
2533 .filter(|n| n.properties.get("name").map(|v| crate::value_to_text(v) == "Bob").unwrap_or(false))
2534 .collect();
2535
2536 assert_eq!(result.len(), 1);
2537 assert_eq!(result[0].id, "2");
2538 }
2539
2540 #[test]
2545 fn test_undirected_single_edge_no_cycle() {
2546 let mut graph = ISONGraph::undirected("test");
2547 graph.add_node("person", "1", props![]).unwrap();
2548 graph.add_node("person", "2", props![]).unwrap();
2549 graph
2550 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2551 .unwrap();
2552 assert!(!graph.has_cycle(None));
2554
2555 graph.add_node("person", "3", props![]).unwrap();
2557 graph
2558 .add_edge("KNOWS", ("person", "2"), ("person", "3"), props![])
2559 .unwrap();
2560 assert!(!graph.has_cycle(None));
2561
2562 graph
2564 .add_edge("KNOWS", ("person", "3"), ("person", "1"), props![])
2565 .unwrap();
2566 assert!(graph.has_cycle(None));
2567 }
2568
2569 #[test]
2570 fn test_directed_cycle_detection() {
2571 let mut graph = ISONGraph::new("test");
2572 graph.add_node("t", "a", props![]).unwrap();
2573 graph.add_node("t", "b", props![]).unwrap();
2574 graph.add_edge("R", ("t", "a"), ("t", "b"), props![]).unwrap();
2575 assert!(!graph.has_cycle(None));
2576 graph.add_edge("R", ("t", "b"), ("t", "a"), props![]).unwrap();
2577 assert!(graph.has_cycle(None));
2578 assert!(!graph.has_cycle(Some("OTHER")));
2580 }
2581
2582 #[test]
2583 fn test_neighbors_both_undirected_dedup() {
2584 let mut graph = ISONGraph::undirected("test");
2585 graph.add_node("person", "1", props![]).unwrap();
2586 graph.add_node("person", "2", props![]).unwrap();
2587 graph
2588 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2589 .unwrap();
2590
2591 let neighbors = graph.neighbors(&("person", "1"), None, Direction::Both);
2592 assert_eq!(neighbors.len(), 1);
2593 assert_eq!(neighbors[0].id, "2");
2594 }
2595
2596 #[test]
2597 fn test_path_exists_direction() {
2598 let mut graph = ISONGraph::new("test");
2599 graph.add_node("person", "1", props![]).unwrap();
2600 graph.add_node("person", "2", props![]).unwrap();
2601 graph
2602 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2603 .unwrap();
2604
2605 assert!(graph.path_exists(&("person", "1"), &("person", "2"), None, 5, Direction::Out));
2606 assert!(!graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::Out));
2607 assert!(graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::In));
2608 assert!(graph.path_exists(&("person", "2"), &("person", "1"), None, 5, Direction::Both));
2609 }
2610
2611 #[test]
2612 fn test_max_hops_usize_max_no_overflow() {
2613 let mut graph = ISONGraph::new("test");
2614 graph.add_node("person", "1", props![]).unwrap();
2615 graph.add_node("person", "2", props![]).unwrap();
2616 graph
2617 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![])
2618 .unwrap();
2619
2620 assert!(graph.path_exists(
2621 &("person", "1"),
2622 &("person", "2"),
2623 None,
2624 usize::MAX,
2625 Direction::Out
2626 ));
2627 let paths = graph.all_paths(&("person", "1"), &("person", "2"), None, usize::MAX, Direction::Out);
2628 assert_eq!(paths.len(), 1);
2629 }
2630
2631 #[test]
2632 fn test_all_paths_start_equals_end() {
2633 let mut graph = ISONGraph::new("test");
2634 graph.add_node("person", "1", props![]).unwrap();
2635 let paths = graph.all_paths(&("person", "1"), &("person", "1"), None, 5, Direction::Out);
2636 assert_eq!(paths.len(), 1);
2637 assert_eq!(paths[0].length(), 0);
2638 }
2639
2640 #[cfg(feature = "serde")]
2645 #[test]
2646 fn test_serde_round_trip() {
2647 let mut graph = ISONGraph::new("test");
2648 graph
2649 .add_node("person", "1", props![("name", "Alice")])
2650 .unwrap();
2651 graph
2652 .add_node("person", "2", props![("name", "Bob")])
2653 .unwrap();
2654 graph
2655 .add_edge("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020")])
2656 .unwrap();
2657
2658 let json = serde_json::to_string(&graph).unwrap();
2659 assert!(!json.contains("out_edges"));
2661 assert!(!json.contains("in_edges"));
2662 assert!(!json.contains("edge_set"));
2663
2664 let restored: ISONGraph = serde_json::from_str(&json).unwrap();
2665 assert_eq!(restored.name, "test");
2666 assert_eq!(restored.node_count(), 2);
2667 assert_eq!(restored.edge_count(), 1);
2668 assert!(restored.has_edge("KNOWS", ("person", "1"), ("person", "2")));
2669
2670 let neighbors = restored.neighbors(&("person", "1"), Some("KNOWS"), Direction::Out);
2672 assert_eq!(neighbors.len(), 1);
2673 assert_eq!(neighbors[0].id, "2");
2674 assert_eq!(restored.in_degree(&("person", "2")), 1);
2675 }
2676
2677 #[test]
2678 fn test_fluent_hops() {
2679 let mut graph = ISONGraph::new("test");
2680 graph.add_node("person", "1", props![]).unwrap();
2681 graph.add_node("person", "2", props![]).unwrap();
2682 graph.add_node("person", "3", props![]).unwrap();
2683 graph.add_edge("KNOWS", ("person", "1"), ("person", "2"), props![]).unwrap();
2684 graph.add_edge("KNOWS", ("person", "2"), ("person", "3"), props![]).unwrap();
2685
2686 let count = graph.start(&("person", "1"))
2687 .hops(2, Some("KNOWS"), Direction::Out)
2688 .count();
2689
2690 assert_eq!(count, 1);
2691 }
2692
2693 const CANONICAL_GOLDEN_ISON: &str = r#"edges.KNOWS
2706since source target weight
2707"2020" :person:1 :person:2 1.75
2708"2021" :person:10 :person:1 0.5
2709
2710edges.WORKS_AT
2711role source target
2712"Lead Engineer" :person:1 :company:acme
2713
2714edges.WORKS_ON
2715hours source target
27163 :person:10 :project:p1
27175 :person:2 :project:p1
2718
2719nodes.company
2720id listed name staff
2721acme false "Acme Corp" 42
2722
2723nodes.person
2724id active age name score
2725"1" true "30" Alice 9.5
2726"10" false "22" Jax -2.25
2727"2" null "25" Bob null
2728
2729nodes.project
2730id budget name tag
2731p1 1250 Alpha a|b"#;
2732
2733 const CANONICAL_GOLDEN_ISONL: &str = r#"edges.KNOWS|since source target weight|"2020" :person:1 :person:2 1.75
2734edges.KNOWS|since source target weight|"2021" :person:10 :person:1 0.5
2735edges.WORKS_AT|role source target|"Lead Engineer" :person:1 :company:acme
2736edges.WORKS_ON|hours source target|3 :person:10 :project:p1
2737edges.WORKS_ON|hours source target|5 :person:2 :project:p1
2738nodes.company|id listed name staff|acme false "Acme Corp" 42
2739nodes.person|id active age name score|"1" true "30" Alice 9.5
2740nodes.person|id active age name score|"10" false "22" Jax -2.25
2741nodes.person|id active age name score|"2" null "25" Bob null
2742nodes.project|id budget name tag|p1 1250 Alpha "a\|b""#;
2743
2744 #[allow(clippy::type_complexity)]
2745 fn build_canonical_fixture(order: usize) -> ISONGraph {
2746 let mut g = ISONGraph::new("fixture");
2747 let nodes: Vec<(&str, &str, Vec<(&str, Value)>)> = vec![
2753 ("company", "acme", props![("name", "Acme Corp"), ("staff", 42i64), ("listed", false)]),
2754 ("person", "1", props![("name", "Alice"), ("age", "30"), ("score", 9.5f64), ("active", true)]),
2755 ("person", "10", props![("name", "Jax"), ("age", "22"), ("score", -2.25f64), ("active", false)]),
2756 ("person", "2", props![("name", "Bob"), ("age", "25")]),
2757 ("project", "p1", props![("name", "Alpha"), ("tag", "a|b"), ("budget", 1250i64)]),
2758 ];
2759 let edges: Vec<(&str, (&str, &str), (&str, &str), Vec<(&str, Value)>)> = vec![
2760 ("KNOWS", ("person", "10"), ("person", "1"), props![("since", "2021"), ("weight", 0.5f64)]),
2761 ("KNOWS", ("person", "1"), ("person", "2"), props![("since", "2020"), ("weight", 1.75f64)]),
2762 ("WORKS_AT", ("person", "1"), ("company", "acme"), props![("role", "Lead Engineer")]),
2763 ("WORKS_ON", ("person", "2"), ("project", "p1"), props![("hours", 5i64)]),
2764 ("WORKS_ON", ("person", "10"), ("project", "p1"), props![("hours", 3i64)]),
2765 ];
2766 let mut n = nodes;
2767 let mut e = edges;
2768 if order != 0 {
2769 n.reverse();
2770 e.reverse();
2771 }
2772 for (t, i, props) in n {
2773 g.add_node(t, i, props).unwrap();
2774 }
2775 for (rel, s, t, props) in e {
2776 g.add_edge(rel, s, t, props).unwrap();
2777 }
2778 g
2779 }
2780
2781 #[test]
2782 fn test_to_ison_independent_of_insertion_order() {
2783 assert_eq!(build_canonical_fixture(0).to_ison(), build_canonical_fixture(1).to_ison());
2784 }
2785
2786 #[test]
2787 fn test_to_isonl_independent_of_insertion_order() {
2788 assert_eq!(build_canonical_fixture(0).to_isonl(), build_canonical_fixture(1).to_isonl());
2789 }
2790
2791 #[test]
2792 fn test_to_ison_matches_golden_fixture() {
2793 assert_eq!(build_canonical_fixture(0).to_ison(), CANONICAL_GOLDEN_ISON);
2794 assert_eq!(build_canonical_fixture(1).to_ison(), CANONICAL_GOLDEN_ISON);
2795 }
2796
2797 #[test]
2798 fn test_to_isonl_matches_golden_fixture() {
2799 assert_eq!(build_canonical_fixture(0).to_isonl(), CANONICAL_GOLDEN_ISONL);
2800 assert_eq!(build_canonical_fixture(1).to_isonl(), CANONICAL_GOLDEN_ISONL);
2801 }
2802
2803 #[test]
2804 fn test_ordinal_not_numeric_sort() {
2805 let ison = build_canonical_fixture(0).to_ison();
2807 let person_block = ison.split("nodes.person
2808").nth(1).unwrap().split("
2809
2810").next().unwrap();
2811 let ids: Vec<&str> = person_block
2815 .lines()
2816 .skip(1)
2817 .map(|l| l.split(' ').next().unwrap().trim_matches('"'))
2818 .collect();
2819 assert_eq!(ids, vec!["1", "10", "2"]);
2820 }
2821
2822 #[test]
2823 fn test_roundtrip_preserves_canonical_form() {
2824 let g = build_canonical_fixture(0);
2825 let reloaded = ISONGraph::from_ison(&g.to_ison(), None).unwrap();
2826 assert_eq!(reloaded.to_ison(), g.to_ison());
2827 }
2828
2829 const UNDIRECTED_FIXTURE: &str = "edges.R\nsource target w\n:p:1 :p:2 1\n:p:2 :p:1 1\n\n\
2838 meta.graph\ndirected\nfalse\n\n\
2839 nodes.p\nid name\n\"1\" A\n\"2\" null";
2840
2841 fn build_undirected() -> ISONGraph {
2842 let mut g = ISONGraph::undirected("u");
2843 g.add_node("p", "1", props![("name", "A")]).unwrap();
2844 g.add_node("p", "2", props![]).unwrap();
2845 g.add_edge("R", ("p", "1"), ("p", "2"), props![("w", 1i64)]).unwrap();
2846 g
2847 }
2848
2849 #[test]
2850 fn test_undirected_writes_meta_and_matches_python_bytes() {
2851 assert_eq!(build_undirected().to_ison(), UNDIRECTED_FIXTURE);
2852 }
2853
2854 #[test]
2855 fn test_directed_output_has_no_meta_block() {
2856 assert!(!build_canonical_fixture(0).to_ison().contains("meta.graph"));
2857 assert!(!build_canonical_fixture(0).to_isonl().contains("meta.graph"));
2858 }
2859
2860 #[test]
2861 fn test_undirected_roundtrip() {
2862 let g = build_undirected();
2863 let r = ISONGraph::from_ison(&g.to_ison(), None).unwrap();
2864 assert!(!r.directed);
2865 assert_eq!(r.edge_count(), g.edge_count());
2866 assert!(r.has_edge("R", ("p", "1"), ("p", "2")));
2867 assert!(r.has_edge("R", ("p", "2"), ("p", "1")));
2868 assert_eq!(r.to_ison(), g.to_ison());
2869
2870 let rl = ISONGraph::from_isonl(&g.to_isonl(), None).unwrap();
2871 assert!(!rl.directed);
2872 assert_eq!(rl.to_isonl(), g.to_isonl());
2873 }
2874
2875 #[test]
2876 fn test_directed_duplicate_row_still_fails() {
2877 let text = "edges.R\nsource target\n:p:1 :p:2\n:p:1 :p:2\n\nnodes.p\nid\n\"1\"\n\"2\"";
2878 assert!(matches!(
2879 ISONGraph::from_ison(text, None),
2880 Err(GraphError::DuplicateEdge(_))
2881 ));
2882 }
2883
2884 #[test]
2885 fn test_explicit_directed_true_is_honoured() {
2886 let g = ISONGraph::from_ison("meta.graph\ndirected\ntrue\n\nnodes.p\nid\n\"1\"", None).unwrap();
2887 assert!(g.directed);
2888 }
2889
2890 #[test]
2891 fn test_multigraph_document_is_refused() {
2892 let text = "meta.graph\ndirected format version\ntrue ison-graph-multigraph-v1 1\n\n\
2893 nodes.p\nid\n\"1\"";
2894 match ISONGraph::from_ison(text, None) {
2895 Err(GraphError::ParseError(msg)) => assert!(msg.contains("MultiGraph"), "{}", msg),
2896 other => panic!("expected ParseError, got {:?}", other.map(|_| ())),
2897 }
2898 }
2899
2900 #[test]
2901 fn test_non_finite_float_properties_are_refused() {
2902 let mut g = ISONGraph::new("t");
2903 assert!(matches!(
2904 g.add_node("p", "1", props![("x", f64::NAN)]),
2905 Err(GraphError::InvalidPropertyValue(_))
2906 ));
2907 g.add_node("p", "1", props![]).unwrap();
2908 g.add_node("p", "2", props![]).unwrap();
2909 assert!(matches!(
2910 g.update_node("p", "1", props![("x", f64::INFINITY)]),
2911 Err(GraphError::InvalidPropertyValue(_))
2912 ));
2913 assert!(g.get_node("p", "1").unwrap().properties.is_empty());
2914 assert!(matches!(
2915 g.add_edge("R", ("p", "1"), ("p", "2"), props![("w", f64::NEG_INFINITY)]),
2916 Err(GraphError::InvalidPropertyValue(_))
2917 ));
2918 assert_eq!(g.edge_count(), 0);
2919 g.add_edge("R", ("p", "1"), ("p", "2"), props![("w", 1.5f64)]).unwrap();
2921 }
2922}