helix_graph_algorithms/algorithms/
traversal.rs

1use std::collections::{BTreeSet, VecDeque};
2
3use serde::{Deserialize, Serialize};
4
5use crate::{Edge, EdgeId, ExternalId, Graph, GraphError, NodeId};
6
7/// Direction used by local graph traversals.
8#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
9#[serde(rename_all = "snake_case")]
10pub enum TraversalDirection {
11    /// Follow stored source-to-target direction.
12    Out,
13    /// Follow stored target-to-source direction.
14    In,
15    /// Follow both directions.
16    Both,
17}
18
19/// Traversal algorithm.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
21#[serde(rename_all = "snake_case")]
22pub enum TraversalStrategy {
23    /// FIFO breadth-first traversal.
24    BreadthFirst,
25    /// Explicit-stack depth-first traversal.
26    DepthFirst,
27}
28
29/// Whether high-degree nodes may expand their adjacency.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
31#[serde(rename_all = "snake_case", tag = "kind")]
32pub enum HubExpansionPolicy {
33    /// Expand every visited node.
34    ExpandAll,
35    /// Include high-degree non-seeds but do not expand them.
36    StopNonSeedAtOrAbove {
37        /// Inclusive degree threshold.
38        degree: usize,
39    },
40}
41
42/// Complete Graphify-compatible traversal options.
43#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
44pub struct TraversalOptions {
45    /// BFS or DFS.
46    pub strategy: TraversalStrategy,
47    /// One or more external node IDs.
48    pub seeds: Vec<NodeId>,
49    /// Maximum emitted depth. Zero emits only seeds.
50    pub max_depth: usize,
51    /// Edge direction.
52    pub direction: TraversalDirection,
53    /// Allowed edge labels. Empty means every label.
54    pub allowed_labels: BTreeSet<String>,
55    /// Optional hub suppression.
56    pub hub_policy: HubExpansionPolicy,
57}
58
59impl TraversalOptions {
60    /// Construct breadth-first traversal options.
61    pub fn breadth_first<I>(seeds: impl IntoIterator<Item = I>, max_depth: usize) -> Self
62    where
63        I: Into<NodeId>,
64    {
65        Self {
66            strategy: TraversalStrategy::BreadthFirst,
67            seeds: seeds.into_iter().map(Into::into).collect(),
68            max_depth,
69            direction: TraversalDirection::Both,
70            allowed_labels: BTreeSet::new(),
71            hub_policy: HubExpansionPolicy::ExpandAll,
72        }
73    }
74
75    /// Construct depth-first traversal options.
76    pub fn depth_first<I>(seeds: impl IntoIterator<Item = I>, max_depth: usize) -> Self
77    where
78        I: Into<NodeId>,
79    {
80        Self {
81            strategy: TraversalStrategy::DepthFirst,
82            ..Self::breadth_first(seeds, max_depth)
83        }
84    }
85}
86
87/// One visited node.
88#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
89pub struct Visit {
90    /// External node identity.
91    pub node_id: NodeId,
92    /// Minimum BFS depth or DFS discovery depth.
93    pub depth: usize,
94    /// Stable zero-based discovery order.
95    pub discovery_order: usize,
96}
97
98/// Whether an edge was traversed with or against its stored orientation.
99#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
100#[serde(rename_all = "snake_case")]
101pub enum EdgeTraversalDirection {
102    /// Stored source to stored target.
103    Forward,
104    /// Stored target to stored source.
105    Reverse,
106}
107
108/// Edge responsible for one discovery.
109#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
110pub struct TraversedEdge {
111    /// Stable edge ID.
112    pub edge_id: EdgeId,
113    /// Optional Graphify key.
114    pub graphify_key: Option<ExternalId>,
115    /// Stored source identity.
116    pub source: NodeId,
117    /// Stored target identity.
118    pub target: NodeId,
119    /// Orientation used during traversal.
120    pub traversal_direction: EdgeTraversalDirection,
121    /// Optional edge label.
122    pub label: Option<String>,
123}
124
125/// Stable traversal output.
126#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
127pub struct TraversalResult {
128    /// Visited nodes in discovery order.
129    pub visits: Vec<Visit>,
130    /// One edge per non-seed discovery.
131    pub discovery_edges: Vec<TraversedEdge>,
132}
133
134/// Degree flavor.
135#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
136#[serde(rename_all = "snake_case")]
137pub enum DegreeKind {
138    /// Stored incoming edges.
139    In,
140    /// Stored outgoing edges.
141    Out,
142    /// Incoming plus outgoing. A self-loop contributes two.
143    Total,
144}
145
146/// One deterministic node degree record.
147#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
148pub struct NodeDegree {
149    /// External node identity.
150    pub node_id: NodeId,
151    /// Unweighted degree.
152    pub degree: usize,
153    /// Weighted degree, using one for edges without an explicit weight.
154    pub weighted_degree: f64,
155}
156
157/// One edge in a found path.
158#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
159pub struct PathEdge {
160    /// Stable edge ID.
161    pub edge_id: EdgeId,
162    /// Optional Graphify key.
163    pub graphify_key: Option<ExternalId>,
164    /// Stored source identity.
165    pub source: NodeId,
166    /// Stored target identity.
167    pub target: NodeId,
168    /// Orientation used along the path.
169    pub traversal_direction: EdgeTraversalDirection,
170    /// Optional label.
171    pub label: Option<String>,
172    /// Selected edge properties.
173    pub attributes: crate::Attributes,
174}
175
176/// Exhaustive local shortest-path result states.
177#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
178#[serde(rename_all = "snake_case", tag = "kind")]
179pub enum PathResult {
180    /// Source is absent from the loaded graph.
181    MissingSource,
182    /// Target is absent from the loaded graph.
183    MissingTarget,
184    /// Both endpoints exist but no allowed path exists.
185    NoPath,
186    /// Found shortest path.
187    Found {
188        /// Node sequence including both endpoints.
189        node_ids: Vec<NodeId>,
190        /// Edge sequence aligned between adjacent nodes.
191        edges: Vec<PathEdge>,
192    },
193}
194
195impl Graph {
196    /// Execute deterministic BFS or DFS over the loaded graph.
197    pub fn traverse(&self, options: &TraversalOptions) -> Result<TraversalResult, GraphError> {
198        if options.seeds.is_empty() {
199            return Err(GraphError::InvalidOption(
200                "traversal requires at least one seed".to_string(),
201            ));
202        }
203        let mut seed_indexes = Vec::new();
204        let mut seed_set = BTreeSet::new();
205        for seed in &options.seeds {
206            let index = self.node_index(seed)?;
207            if seed_set.insert(index) {
208                seed_indexes.push(index);
209            }
210        }
211        match options.strategy {
212            TraversalStrategy::BreadthFirst => self.breadth_first(options, &seed_indexes),
213            TraversalStrategy::DepthFirst => self.depth_first(options, &seed_indexes),
214        }
215    }
216
217    fn breadth_first(
218        &self,
219        options: &TraversalOptions,
220        seeds: &[usize],
221    ) -> Result<TraversalResult, GraphError> {
222        let mut visited = vec![false; self.node_count()];
223        let mut queue = VecDeque::new();
224        let mut visits = Vec::new();
225        for seed in seeds {
226            visited[*seed] = true;
227            queue.push_back((*seed, 0));
228            visits.push(Visit {
229                node_id: self.node_id(*seed).clone(),
230                depth: 0,
231                discovery_order: visits.len(),
232            });
233        }
234        let mut discovery_edges = Vec::new();
235        while let Some((node, depth)) = queue.pop_front() {
236            if depth >= options.max_depth
237                || (!seeds.contains(&node) && self.suppresses_hub(node, options))
238            {
239                continue;
240            }
241            for arc in self.arcs(node, options.direction) {
242                let edge = self.edge_at(arc.edge);
243                if !edge_label_allowed(edge, &options.allowed_labels) || visited[arc.neighbor] {
244                    continue;
245                }
246                visited[arc.neighbor] = true;
247                let next_depth = depth + 1;
248                queue.push_back((arc.neighbor, next_depth));
249                visits.push(Visit {
250                    node_id: self.node_id(arc.neighbor).clone(),
251                    depth: next_depth,
252                    discovery_order: visits.len(),
253                });
254                discovery_edges.push(traversed_edge(self, node, edge));
255            }
256        }
257        Ok(TraversalResult {
258            visits,
259            discovery_edges,
260        })
261    }
262
263    fn depth_first(
264        &self,
265        options: &TraversalOptions,
266        seeds: &[usize],
267    ) -> Result<TraversalResult, GraphError> {
268        let mut visited = vec![false; self.node_count()];
269        let mut stack = Vec::new();
270        let mut visits = Vec::new();
271        for seed in seeds.iter().rev() {
272            if !visited[*seed] {
273                visited[*seed] = true;
274                stack.push((*seed, 0, None));
275            }
276        }
277        let mut discovery_edges = Vec::new();
278        while let Some((node, depth, discovery)) = stack.pop() {
279            visits.push(Visit {
280                node_id: self.node_id(node).clone(),
281                depth,
282                discovery_order: visits.len(),
283            });
284            if let Some((previous, edge_index)) = discovery {
285                discovery_edges.push(traversed_edge(self, previous, self.edge_at(edge_index)));
286            }
287            if depth >= options.max_depth
288                || (!seeds.contains(&node) && self.suppresses_hub(node, options))
289            {
290                continue;
291            }
292            let mut discovered = BTreeSet::new();
293            let arcs = self
294                .arcs(node, options.direction)
295                .filter(|arc| {
296                    !visited[arc.neighbor]
297                        && edge_label_allowed(self.edge_at(arc.edge), &options.allowed_labels)
298                        && discovered.insert(arc.neighbor)
299                })
300                .collect::<Vec<_>>();
301            for arc in arcs.into_iter().rev() {
302                visited[arc.neighbor] = true;
303                stack.push((arc.neighbor, depth + 1, Some((node, arc.edge))));
304            }
305        }
306        Ok(TraversalResult {
307            visits,
308            discovery_edges,
309        })
310    }
311
312    fn suppresses_hub(&self, node: usize, options: &TraversalOptions) -> bool {
313        match options.hub_policy {
314            HubExpansionPolicy::ExpandAll => false,
315            HubExpansionPolicy::StopNonSeedAtOrAbove { degree } => {
316                self.unweighted_degree_at(node, DegreeKind::Total) >= degree
317            }
318        }
319    }
320
321    /// Compute one node degree.
322    pub fn degree(
323        &self,
324        node_id: impl Into<NodeId>,
325        kind: DegreeKind,
326    ) -> Result<NodeDegree, GraphError> {
327        let node_id = node_id.into();
328        let node = self.node_index(&node_id)?;
329        Ok(NodeDegree {
330            node_id,
331            degree: self.unweighted_degree_at(node, kind),
332            weighted_degree: self.weighted_degree_at(node, kind),
333        })
334    }
335
336    /// Compute degrees for all nodes in deterministic ID order.
337    pub fn degrees(&self, kind: DegreeKind) -> Vec<NodeDegree> {
338        (0..self.node_count())
339            .map(|node| NodeDegree {
340                node_id: self.node_id(node).clone(),
341                degree: self.unweighted_degree_at(node, kind),
342                weighted_degree: self.weighted_degree_at(node, kind),
343            })
344            .collect()
345    }
346
347    fn unweighted_degree_at(&self, node: usize, kind: DegreeKind) -> usize {
348        if !self.is_directed() {
349            return self.outgoing(node).len() + self.incoming(node).len();
350        }
351        match kind {
352            DegreeKind::In => self.incoming(node).len(),
353            DegreeKind::Out => self.outgoing(node).len(),
354            DegreeKind::Total => self.incoming(node).len() + self.outgoing(node).len(),
355        }
356    }
357
358    fn weighted_degree_at(&self, node: usize, kind: DegreeKind) -> f64 {
359        let sum = |arcs: &[crate::model::ArcRef]| {
360            arcs.iter()
361                .map(|arc| self.edge_at(arc.edge).weight.unwrap_or(1.0))
362                .sum::<f64>()
363        };
364        if !self.is_directed() {
365            return sum(self.outgoing(node)) + sum(self.incoming(node));
366        }
367        match kind {
368            DegreeKind::In => sum(self.incoming(node)),
369            DegreeKind::Out => sum(self.outgoing(node)),
370            DegreeKind::Total => sum(self.incoming(node)) + sum(self.outgoing(node)),
371        }
372    }
373
374    /// Find an unweighted shortest path in the loaded graph.
375    pub fn shortest_path(
376        &self,
377        source: impl Into<NodeId>,
378        target: impl Into<NodeId>,
379        direction: TraversalDirection,
380        allowed_labels: &BTreeSet<String>,
381        max_depth: Option<usize>,
382    ) -> PathResult {
383        let source = source.into();
384        let target = target.into();
385        let Ok(source_index) = self.node_index(&source) else {
386            return PathResult::MissingSource;
387        };
388        let Ok(target_index) = self.node_index(&target) else {
389            return PathResult::MissingTarget;
390        };
391        if source_index == target_index {
392            return PathResult::Found {
393                node_ids: vec![source],
394                edges: Vec::new(),
395            };
396        }
397        let mut visited = vec![false; self.node_count()];
398        let mut predecessor = vec![None::<(usize, usize)>; self.node_count()];
399        let mut queue = VecDeque::from([(source_index, 0)]);
400        visited[source_index] = true;
401        while let Some((node, depth)) = queue.pop_front() {
402            if max_depth.is_some_and(|bound| depth >= bound) {
403                continue;
404            }
405            for arc in self.arcs(node, direction) {
406                if visited[arc.neighbor]
407                    || !edge_label_allowed(self.edge_at(arc.edge), allowed_labels)
408                {
409                    continue;
410                }
411                visited[arc.neighbor] = true;
412                predecessor[arc.neighbor] = Some((node, arc.edge));
413                if arc.neighbor == target_index {
414                    return self.reconstruct_path(source_index, target_index, &predecessor);
415                }
416                queue.push_back((arc.neighbor, depth + 1));
417            }
418        }
419        PathResult::NoPath
420    }
421
422    fn reconstruct_path(
423        &self,
424        source: usize,
425        target: usize,
426        predecessor: &[Option<(usize, usize)>],
427    ) -> PathResult {
428        let mut nodes = vec![target];
429        let mut path_edges = Vec::new();
430        let mut current = target;
431        while current != source {
432            let Some((previous, edge_index)) = predecessor[current] else {
433                unreachable!("visited target has a complete predecessor chain")
434            };
435            let edge = self.edge_at(edge_index);
436            path_edges.push(PathEdge {
437                edge_id: edge.id.clone(),
438                graphify_key: edge.graphify_key.clone(),
439                source: edge.source.clone(),
440                target: edge.target.clone(),
441                traversal_direction: edge_direction(self, previous, edge),
442                label: edge.label.clone(),
443                attributes: edge.attributes.clone(),
444            });
445            nodes.push(previous);
446            current = previous;
447        }
448        nodes.reverse();
449        path_edges.reverse();
450        PathResult::Found {
451            node_ids: nodes
452                .into_iter()
453                .map(|node| self.node_id(node).clone())
454                .collect(),
455            edges: path_edges,
456        }
457    }
458
459    /// Deterministic neighboring node IDs.
460    pub fn neighbors(
461        &self,
462        node_id: impl Into<NodeId>,
463        direction: TraversalDirection,
464    ) -> Result<Vec<NodeId>, GraphError> {
465        let node = self.node_index(node_id)?;
466        let mut neighbors = self
467            .arcs(node, direction)
468            .map(|arc| self.node_id(arc.neighbor).clone())
469            .collect::<Vec<_>>();
470        neighbors.sort();
471        neighbors.dedup();
472        Ok(neighbors)
473    }
474
475    /// Deterministic successors under the graph's direction semantics.
476    pub fn successors(&self, node_id: impl Into<NodeId>) -> Result<Vec<NodeId>, GraphError> {
477        self.neighbors(node_id, TraversalDirection::Out)
478    }
479
480    /// Deterministic predecessors under the graph's direction semantics.
481    pub fn predecessors(&self, node_id: impl Into<NodeId>) -> Result<Vec<NodeId>, GraphError> {
482        self.neighbors(node_id, TraversalDirection::In)
483    }
484
485    /// Stable IDs of outgoing edges. Undirected graphs return every incident
486    /// edge exactly once.
487    pub fn out_edge_ids(&self, node_id: impl Into<NodeId>) -> Result<Vec<EdgeId>, GraphError> {
488        self.edge_ids_for(node_id, TraversalDirection::Out)
489    }
490
491    /// Stable IDs of incoming edges. Undirected graphs return every incident
492    /// edge exactly once.
493    pub fn in_edge_ids(&self, node_id: impl Into<NodeId>) -> Result<Vec<EdgeId>, GraphError> {
494        self.edge_ids_for(node_id, TraversalDirection::In)
495    }
496
497    /// Stable IDs of all incident edges, with self-loops returned once.
498    pub fn incident_edge_ids(&self, node_id: impl Into<NodeId>) -> Result<Vec<EdgeId>, GraphError> {
499        self.edge_ids_for(node_id, TraversalDirection::Both)
500    }
501
502    fn edge_ids_for(
503        &self,
504        node_id: impl Into<NodeId>,
505        direction: TraversalDirection,
506    ) -> Result<Vec<EdgeId>, GraphError> {
507        let node = self.node_index(node_id)?;
508        Ok(self
509            .arcs(node, direction)
510            .map(|arc| self.edge_at(arc.edge).id.clone())
511            .collect())
512    }
513
514    /// All stable edge IDs between two nodes under the selected direction.
515    pub fn edges_between(
516        &self,
517        source: impl Into<NodeId>,
518        target: impl Into<NodeId>,
519        direction: TraversalDirection,
520    ) -> Result<Vec<EdgeId>, GraphError> {
521        let source = self.node_index(source)?;
522        let target = self.node_index(target)?;
523        Ok(self
524            .arcs(source, direction)
525            .filter(|arc| arc.neighbor == target)
526            .map(|arc| self.edge_at(arc.edge).id.clone())
527            .collect())
528    }
529
530    /// Whether at least one edge connects an endpoint pair under the selected
531    /// traversal direction.
532    pub fn has_edge_between(
533        &self,
534        source: impl Into<NodeId>,
535        target: impl Into<NodeId>,
536        direction: TraversalDirection,
537    ) -> Result<bool, GraphError> {
538        let source = self.node_index(source)?;
539        let target = self.node_index(target)?;
540        Ok(self
541            .arcs(source, direction)
542            .any(|arc| arc.neighbor == target))
543    }
544}
545
546fn edge_label_allowed(edge: &Edge, allowed: &BTreeSet<String>) -> bool {
547    allowed.is_empty()
548        || edge
549            .label
550            .as_ref()
551            .is_some_and(|label| allowed.contains(label))
552}
553
554fn edge_direction(graph: &Graph, current: usize, edge: &Edge) -> EdgeTraversalDirection {
555    if graph.node_id(current) == &edge.source {
556        EdgeTraversalDirection::Forward
557    } else {
558        EdgeTraversalDirection::Reverse
559    }
560}
561
562fn traversed_edge(graph: &Graph, current: usize, edge: &Edge) -> TraversedEdge {
563    TraversedEdge {
564        edge_id: edge.id.clone(),
565        graphify_key: edge.graphify_key.clone(),
566        source: edge.source.clone(),
567        target: edge.target.clone(),
568        traversal_direction: edge_direction(graph, current, edge),
569        label: edge.label.clone(),
570    }
571}
572
573#[cfg(test)]
574mod tests {
575    use super::*;
576    use crate::{Edge, GraphKind, Node};
577
578    fn graph() -> Graph {
579        Graph::new(
580            GraphKind::Graph,
581            ["a", "b", "c", "hub", "leaf", "leaf2", "leaf3"]
582                .into_iter()
583                .map(Node::new),
584            [
585                Edge::new("ab", "a", "b").with_label("allowed"),
586                Edge::new("bc", "b", "c").with_label("allowed"),
587                Edge::new("bh", "b", "hub").with_label("allowed"),
588                Edge::new("hl", "hub", "leaf").with_label("allowed"),
589                Edge::new("hl2", "hub", "leaf2").with_label("allowed"),
590                Edge::new("hl3", "hub", "leaf3").with_label("allowed"),
591            ],
592        )
593        .unwrap()
594    }
595
596    #[test]
597    fn breadth_first_returns_depth_order_and_discovery_edges() {
598        let result = graph()
599            .traverse(&TraversalOptions::breadth_first(["a".to_string()], 2))
600            .unwrap();
601        assert_eq!(
602            result
603                .visits
604                .iter()
605                .map(|visit| (visit.node_id.clone(), visit.depth))
606                .collect::<Vec<_>>(),
607            [
608                (NodeId::from("a"), 0),
609                (NodeId::from("b"), 1),
610                (NodeId::from("c"), 2),
611                (NodeId::from("hub"), 2),
612            ]
613        );
614        assert_eq!(result.discovery_edges.len(), 3);
615    }
616
617    #[test]
618    fn traversal_includes_but_does_not_expand_non_seed_hubs() {
619        let mut options = TraversalOptions::breadth_first(["a".to_string()], 4);
620        options.hub_policy = HubExpansionPolicy::StopNonSeedAtOrAbove { degree: 4 };
621        let result = graph().traverse(&options).unwrap();
622        assert!(result.visits.iter().any(|visit| visit.node_id == "hub"));
623        assert!(!result.visits.iter().any(|visit| visit.node_id == "leaf"));
624    }
625
626    #[test]
627    fn shortest_path_distinguishes_result_states_and_returns_edges() {
628        let graph = graph();
629        assert_eq!(
630            graph.shortest_path(
631                "missing",
632                "a",
633                TraversalDirection::Both,
634                &BTreeSet::new(),
635                None
636            ),
637            PathResult::MissingSource
638        );
639        let PathResult::Found { node_ids, edges } =
640            graph.shortest_path("a", "c", TraversalDirection::Both, &BTreeSet::new(), None)
641        else {
642            panic!("path should exist")
643        };
644        assert_eq!(node_ids, ["a", "b", "c"]);
645        assert_eq!(edges.len(), 2);
646    }
647
648    #[test]
649    fn degree_counts_parallel_edges_and_self_loops() {
650        let graph = Graph::new(
651            GraphKind::MultiGraph,
652            [Node::new("a"), Node::new("b")],
653            [
654                Edge::new("aa", "a", "a"),
655                Edge::new("ab1", "a", "b"),
656                Edge::new("ab2", "a", "b"),
657            ],
658        )
659        .unwrap();
660        assert_eq!(graph.degree("a", DegreeKind::Total).unwrap().degree, 4);
661        assert_eq!(graph.degree("b", DegreeKind::Total).unwrap().degree, 2);
662    }
663
664    #[test]
665    fn depth_first_marks_nodes_when_scheduled_and_uses_stable_edges() {
666        let graph = Graph::new(
667            GraphKind::MultiDiGraph,
668            [
669                Node::new("a"),
670                Node::new("b"),
671                Node::new("c"),
672                Node::new("d"),
673            ],
674            [
675                Edge::new("ab-first", "a", "b"),
676                Edge::new("ab-second", "a", "b"),
677                Edge::new("ac", "a", "c"),
678                Edge::new("bd", "b", "d"),
679                Edge::new("cd", "c", "d"),
680            ],
681        )
682        .unwrap();
683        let mut options = TraversalOptions::depth_first(["a".to_string()], 3);
684        options.direction = TraversalDirection::Out;
685        let result = graph.traverse(&options).unwrap();
686        assert_eq!(
687            result
688                .visits
689                .iter()
690                .map(|visit| (visit.node_id.clone(), visit.depth))
691                .collect::<Vec<_>>(),
692            [
693                (NodeId::from("a"), 0),
694                (NodeId::from("b"), 1),
695                (NodeId::from("d"), 2),
696                (NodeId::from("c"), 1),
697            ]
698        );
699        assert_eq!(
700            result
701                .discovery_edges
702                .iter()
703                .map(|edge| edge.edge_id.stored_id())
704                .collect::<Vec<_>>(),
705            ["ab-first", "bd", "ac"]
706        );
707    }
708
709    #[test]
710    fn graph_object_accessors_cover_direction_edges_and_pair_existence() {
711        let directed = Graph::new(
712            GraphKind::MultiDiGraph,
713            ["a", "b", "c"].into_iter().map(Node::new),
714            [
715                Edge::new("ab1", "a", "b"),
716                Edge::new("ab2", "a", "b"),
717                Edge::new("ca", "c", "a"),
718                Edge::new("aa", "a", "a"),
719            ],
720        )
721        .unwrap();
722
723        assert_eq!(
724            directed.neighbors("a", TraversalDirection::Out).unwrap(),
725            ["a", "b"]
726        );
727        assert_eq!(directed.successors("a").unwrap(), ["a", "b"]);
728        assert_eq!(directed.predecessors("a").unwrap(), ["a", "c"]);
729        assert_eq!(
730            directed.out_edge_ids("a").unwrap(),
731            ["aa", "ab1", "ab2"].map(crate::EdgeId::from)
732        );
733        assert_eq!(
734            directed.in_edge_ids("a").unwrap(),
735            ["aa", "ca"].map(crate::EdgeId::from)
736        );
737        assert_eq!(
738            directed.incident_edge_ids("a").unwrap(),
739            ["aa", "ab1", "ab2", "ca"].map(crate::EdgeId::from)
740        );
741        assert_eq!(
742            directed
743                .edges_between("a", "b", TraversalDirection::Out)
744                .unwrap(),
745            ["ab1", "ab2"].map(crate::EdgeId::from)
746        );
747        assert!(directed
748            .has_edge_between("b", "a", TraversalDirection::In)
749            .unwrap());
750        assert!(!directed
751            .has_edge_between("b", "c", TraversalDirection::Both)
752            .unwrap());
753        assert!(matches!(
754            directed.neighbors("missing", TraversalDirection::Both),
755            Err(GraphError::UnknownNode(_))
756        ));
757    }
758
759    #[test]
760    fn directed_degrees_filters_bounds_and_invalid_traversals_are_explicit() {
761        let directed = Graph::new(
762            GraphKind::DiGraph,
763            ["a", "b", "c"].into_iter().map(Node::new),
764            [
765                Edge::new("ab", "a", "b")
766                    .with_label("allowed")
767                    .with_weight(2.0),
768                Edge::new("bc", "b", "c").with_label("blocked"),
769                Edge::new("aa", "a", "a").with_label("allowed"),
770            ],
771        )
772        .unwrap();
773
774        assert_eq!(directed.degree("a", DegreeKind::In).unwrap().degree, 1);
775        assert_eq!(
776            directed
777                .degree("a", DegreeKind::Out)
778                .unwrap()
779                .weighted_degree,
780            3.0
781        );
782        assert_eq!(directed.degrees(DegreeKind::Total).len(), 3);
783        assert!(matches!(
784            directed.degree("missing", DegreeKind::Total),
785            Err(GraphError::UnknownNode(_))
786        ));
787        assert!(matches!(
788            directed.traverse(&TraversalOptions::breadth_first(Vec::<NodeId>::new(), 1)),
789            Err(GraphError::InvalidOption(_))
790        ));
791        assert!(matches!(
792            directed.traverse(&TraversalOptions::breadth_first(["missing".to_string()], 1)),
793            Err(GraphError::UnknownNode(_))
794        ));
795
796        let allowed = BTreeSet::from(["allowed".to_string()]);
797        let filtered = directed
798            .traverse(&TraversalOptions {
799                direction: TraversalDirection::Out,
800                allowed_labels: allowed.clone(),
801                ..TraversalOptions::breadth_first(["a"], 3)
802            })
803            .unwrap();
804        assert_eq!(
805            filtered
806                .visits
807                .iter()
808                .map(|visit| visit.node_id.clone())
809                .collect::<Vec<_>>(),
810            ["a", "b"].map(NodeId::from)
811        );
812        assert!(filtered
813            .discovery_edges
814            .iter()
815            .all(|edge| edge.label.as_deref() == Some("allowed")));
816        assert!(matches!(
817            directed.shortest_path("a", "c", TraversalDirection::Out, &allowed, None),
818            PathResult::NoPath
819        ));
820        assert!(matches!(
821            directed.shortest_path("a", "c", TraversalDirection::Out, &BTreeSet::new(), Some(1)),
822            PathResult::NoPath
823        ));
824        assert!(matches!(
825            directed.shortest_path("a", "a", TraversalDirection::Out, &BTreeSet::new(), None),
826            PathResult::Found { node_ids, edges } if node_ids == ["a"] && edges.is_empty()
827        ));
828        assert!(matches!(
829            directed.shortest_path(
830                "a",
831                "missing",
832                TraversalDirection::Out,
833                &BTreeSet::new(),
834                None
835            ),
836            PathResult::MissingTarget
837        ));
838    }
839}
helix_graph_algorithms/algorithms/traversal.rs

helix_graph_algorithms/algorithms/
traversal.rs
