manifoldb_graph/traversal/
dijkstra.rs

1//! Dijkstra's algorithm for weighted shortest path finding.
2//!
3//! This module provides Dijkstra's algorithm for finding the shortest weighted
4//! path between two nodes in a graph. Unlike BFS-based shortest path which
5//! treats all edges as having weight 1, Dijkstra's algorithm considers edge
6//! weights stored as properties.
7//!
8//! # Edge Weights
9//!
10//! Weights are extracted from edge properties using a configurable weight
11//! function. The default behavior looks for a "weight" property, falling back
12//! to 1.0 if not present.
13//!
14//! # Negative Weights
15//!
16//! This implementation detects negative edge weights and returns an error.
17//! For graphs with negative weights, Bellman-Ford algorithm would be needed,
18//! which is not currently implemented.
19//!
20//! # Example
21//!
22//! ```ignore
23//! use manifoldb_graph::traversal::{Dijkstra, Direction, WeightedPathResult};
24//!
25//! // Find shortest weighted path between two locations
26//! let path = Dijkstra::new(city_a, city_b, Direction::Outgoing)
27//!     .with_weight_property("distance")
28//!     .find(&tx)?;
29//!
30//! if let Some(result) = path {
31//!     println!("Total distance: {}", result.total_weight);
32//!     println!("Path: {:?}", result.nodes);
33//! }
34//! ```
35
36use std::cmp::Ordering;
37use std::collections::{BinaryHeap, HashMap, HashSet};
38
39use manifoldb_core::{Edge, EdgeId, EdgeType, EntityId, Value};
40use manifoldb_storage::Transaction;
41
42use super::{Direction, TraversalFilter};
43use crate::index::AdjacencyIndex;
44use crate::store::{EdgeStore, GraphError, GraphResult};
45
46/// A weighted path through the graph.
47///
48/// Represents a sequence of nodes and edges from a source to a target,
49/// along with the total accumulated weight.
50#[derive(Debug, Clone, PartialEq)]
51pub struct WeightedPathResult {
52    /// The nodes in the path, from source to target.
53    pub nodes: Vec<EntityId>,
54    /// The edges connecting the nodes.
55    /// Length is `nodes.len() - 1`.
56    pub edges: Vec<EdgeId>,
57    /// The total weight of the path.
58    pub total_weight: f64,
59    /// The number of edges in the path.
60    pub length: usize,
61}
62
63impl WeightedPathResult {
64    /// Create a new weighted path result.
65    pub fn new(nodes: Vec<EntityId>, edges: Vec<EdgeId>, total_weight: f64) -> Self {
66        let length = edges.len();
67        Self { nodes, edges, total_weight, length }
68    }
69
70    /// Create a path for a single node (source == target).
71    pub fn single_node(node: EntityId) -> Self {
72        Self { nodes: vec![node], edges: Vec::new(), total_weight: 0.0, length: 0 }
73    }
74
75    /// Get the source node.
76    pub fn source(&self) -> EntityId {
77        self.nodes[0]
78    }
79
80    /// Get the target node.
81    ///
82    /// # Panics
83    /// Panics if the path is empty (should not happen with valid construction).
84    pub fn target(&self) -> EntityId {
85        *self.nodes.last().expect("path has at least one node")
86    }
87
88    /// Check if the path is empty (source == target).
89    pub const fn is_empty(&self) -> bool {
90        self.length == 0
91    }
92}
93
94/// Weight extraction configuration.
95///
96/// Defines how edge weights are extracted from edge properties.
97#[derive(Debug, Clone)]
98pub enum WeightConfig {
99    /// Use a specific property name as the weight.
100    /// Falls back to `default_weight` if the property is not found.
101    Property {
102        /// The name of the property to use as weight.
103        name: String,
104        /// The default weight if the property is not found.
105        default_weight: f64,
106    },
107    /// Use a constant weight for all edges.
108    Constant(f64),
109}
110
111impl Default for WeightConfig {
112    fn default() -> Self {
113        Self::Property { name: "weight".to_owned(), default_weight: 1.0 }
114    }
115}
116
117impl WeightConfig {
118    /// Create a weight config that uses a specific property.
119    pub fn property(name: impl Into<String>) -> Self {
120        Self::Property { name: name.into(), default_weight: 1.0 }
121    }
122
123    /// Create a weight config that uses a specific property with a default value.
124    pub fn property_with_default(name: impl Into<String>, default: f64) -> Self {
125        Self::Property { name: name.into(), default_weight: default }
126    }
127
128    /// Create a weight config that uses a constant weight.
129    pub const fn constant(weight: f64) -> Self {
130        Self::Constant(weight)
131    }
132
133    /// Extract the weight from an edge based on this configuration.
134    ///
135    /// # Returns
136    /// - `Ok(weight)` - The extracted weight
137    /// - `Err` - If the weight value is invalid (non-numeric)
138    pub fn extract_weight(&self, edge: &Edge) -> GraphResult<f64> {
139        match self {
140            Self::Constant(w) => Ok(*w),
141            Self::Property { name, default_weight } => match edge.get_property(name) {
142                Some(Value::Float(f)) => Ok(*f),
143                Some(Value::Int(i)) => Ok(*i as f64),
144                Some(other) => Err(GraphError::InvalidWeight {
145                    edge_id: edge.id,
146                    message: format!("non-numeric weight property '{}': {:?}", name, other),
147                }),
148                None => Ok(*default_weight),
149            },
150        }
151    }
152}
153
154/// Entry in the priority queue for Dijkstra's algorithm.
155///
156/// Ordered by distance (lower distance = higher priority).
157#[derive(Debug, Clone)]
158struct DijkstraEntry {
159    node: EntityId,
160    distance: f64,
161}
162
163impl PartialEq for DijkstraEntry {
164    fn eq(&self, other: &Self) -> bool {
165        self.distance == other.distance && self.node == other.node
166    }
167}
168
169impl Eq for DijkstraEntry {}
170
171impl PartialOrd for DijkstraEntry {
172    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
173        Some(self.cmp(other))
174    }
175}
176
177impl Ord for DijkstraEntry {
178    fn cmp(&self, other: &Self) -> Ordering {
179        // Reverse ordering for min-heap behavior
180        // Lower distance = higher priority
181        other
182            .distance
183            .partial_cmp(&self.distance)
184            .unwrap_or(Ordering::Equal)
185            .then_with(|| self.node.as_u64().cmp(&other.node.as_u64()))
186    }
187}
188
189/// Dijkstra's algorithm for weighted shortest path finding.
190///
191/// Finds the shortest weighted path between two nodes using Dijkstra's
192/// algorithm with a binary heap.
193///
194/// # Features
195///
196/// - Configurable edge weight extraction
197/// - Detects negative weights (returns error)
198/// - Configurable traversal direction
199/// - Optional edge type filtering
200/// - Optional maximum weight limit
201///
202/// # Example
203///
204/// ```ignore
205/// // Find shortest weighted path
206/// let path = Dijkstra::new(start, end, Direction::Outgoing)
207///     .with_weight_property("cost")
208///     .find(&tx)?;
209///
210/// // With maximum weight constraint
211/// let path = Dijkstra::new(start, end, Direction::Both)
212///     .with_max_weight(100.0)
213///     .find(&tx)?;
214/// ```
215pub struct Dijkstra {
216    /// Source node.
217    source: EntityId,
218    /// Target node.
219    target: EntityId,
220    /// Traversal direction.
221    direction: Direction,
222    /// Weight configuration.
223    weight_config: WeightConfig,
224    /// Maximum total weight to search (acts like a distance cutoff).
225    max_weight: Option<f64>,
226    /// Filter for traversal.
227    filter: TraversalFilter,
228}
229
230impl Dijkstra {
231    /// Create a new Dijkstra shortest path finder.
232    ///
233    /// # Arguments
234    ///
235    /// * `source` - The starting node
236    /// * `target` - The destination node
237    /// * `direction` - Which direction to traverse edges
238    pub fn new(source: EntityId, target: EntityId, direction: Direction) -> Self {
239        Self {
240            source,
241            target,
242            direction,
243            weight_config: WeightConfig::default(),
244            max_weight: None,
245            filter: TraversalFilter::new(),
246        }
247    }
248
249    /// Set the weight property name to use.
250    ///
251    /// The weight will be extracted from this edge property.
252    /// Defaults to "weight" with a fallback value of 1.0.
253    pub fn with_weight_property(mut self, property: impl Into<String>) -> Self {
254        self.weight_config = WeightConfig::property(property);
255        self
256    }
257
258    /// Set the weight property name with a custom default value.
259    pub fn with_weight_property_default(
260        mut self,
261        property: impl Into<String>,
262        default: f64,
263    ) -> Self {
264        self.weight_config = WeightConfig::property_with_default(property, default);
265        self
266    }
267
268    /// Use a constant weight for all edges.
269    ///
270    /// This effectively makes Dijkstra behave like BFS when weight is 1.0.
271    pub fn with_constant_weight(mut self, weight: f64) -> Self {
272        self.weight_config = WeightConfig::constant(weight);
273        self
274    }
275
276    /// Set a custom weight configuration.
277    pub fn with_weight_config(mut self, config: WeightConfig) -> Self {
278        self.weight_config = config;
279        self
280    }
281
282    /// Set the maximum total weight to search.
283    ///
284    /// Paths with total weight exceeding this value will not be considered.
285    pub fn with_max_weight(mut self, max_weight: f64) -> Self {
286        self.max_weight = Some(max_weight);
287        self
288    }
289
290    /// Filter to only traverse edges of the specified type.
291    pub fn with_edge_type(mut self, edge_type: impl Into<EdgeType>) -> Self {
292        self.filter = self.filter.with_edge_type(edge_type);
293        self
294    }
295
296    /// Filter to only traverse edges of the specified types.
297    pub fn with_edge_types(mut self, edge_types: impl IntoIterator<Item = EdgeType>) -> Self {
298        self.filter = self.filter.with_edge_types(edge_types);
299        self
300    }
301
302    /// Exclude specific nodes from the path.
303    pub fn exclude_nodes(mut self, nodes: impl IntoIterator<Item = EntityId>) -> Self {
304        self.filter = self.filter.exclude_nodes(nodes);
305        self
306    }
307
308    /// Find the shortest weighted path.
309    ///
310    /// # Returns
311    ///
312    /// - `Ok(Some(WeightedPathResult))` if a path exists
313    /// - `Ok(None)` if no path exists within the constraints
314    /// - `Err(GraphError)` if a negative weight is detected or other error occurs
315    pub fn find<T: Transaction>(self, tx: &T) -> GraphResult<Option<WeightedPathResult>> {
316        // Handle same source and target
317        if self.source == self.target {
318            return Ok(Some(WeightedPathResult::single_node(self.source)));
319        }
320
321        // Estimate initial capacity based on typical graph traversal patterns
322        // For shortest path, we typically visit O(sqrt(n)) to O(n) nodes
323        const INITIAL_CAPACITY: usize = 256;
324
325        // Distance from source to each node
326        let mut distances: HashMap<EntityId, f64> = HashMap::with_capacity(INITIAL_CAPACITY);
327        // Track parent and edge used to reach each node
328        let mut parent: HashMap<EntityId, (EntityId, EdgeId)> =
329            HashMap::with_capacity(INITIAL_CAPACITY);
330        // Nodes that have been finalized
331        let mut finalized: HashSet<EntityId> = HashSet::with_capacity(INITIAL_CAPACITY);
332        // Priority queue (min-heap by distance)
333        let mut heap: BinaryHeap<DijkstraEntry> = BinaryHeap::with_capacity(INITIAL_CAPACITY);
334
335        // Initialize source
336        distances.insert(self.source, 0.0);
337        heap.push(DijkstraEntry { node: self.source, distance: 0.0 });
338
339        while let Some(DijkstraEntry { node: current, distance: current_dist }) = heap.pop() {
340            // Skip if already finalized
341            if finalized.contains(&current) {
342                continue;
343            }
344
345            // Check if we've found the target
346            if current == self.target {
347                return Ok(Some(self.reconstruct_path(&parent, current_dist)));
348            }
349
350            // Mark as finalized
351            finalized.insert(current);
352
353            // Skip if we already have a better path to this node
354            // (can happen due to duplicate entries in heap)
355            if let Some(&known_dist) = distances.get(&current) {
356                if current_dist > known_dist {
357                    continue;
358                }
359            }
360
361            // Explore neighbors
362            let neighbors = self.get_neighbors_with_weights(tx, current)?;
363
364            for (neighbor, edge_id, weight) in neighbors {
365                // Check for negative weights
366                if weight < 0.0 {
367                    return Err(GraphError::InvalidWeight {
368                        edge_id,
369                        message: format!(
370                            "negative weight {} not supported by Dijkstra's algorithm",
371                            weight
372                        ),
373                    });
374                }
375
376                // Skip finalized nodes
377                if finalized.contains(&neighbor) {
378                    continue;
379                }
380
381                // Check node filter
382                if neighbor != self.target && !self.filter.should_include_node(neighbor) {
383                    continue;
384                }
385
386                let new_dist = current_dist + weight;
387
388                // Check max weight constraint
389                if let Some(max) = self.max_weight {
390                    if new_dist > max {
391                        continue;
392                    }
393                }
394
395                // Update if this is a better path
396                let is_better = match distances.get(&neighbor) {
397                    None => true,
398                    Some(&existing) => new_dist < existing,
399                };
400
401                if is_better {
402                    distances.insert(neighbor, new_dist);
403                    parent.insert(neighbor, (current, edge_id));
404                    heap.push(DijkstraEntry { node: neighbor, distance: new_dist });
405                }
406            }
407        }
408
409        Ok(None)
410    }
411
412    /// Get neighbors with their edge weights.
413    fn get_neighbors_with_weights<T: Transaction>(
414        &self,
415        tx: &T,
416        node: EntityId,
417    ) -> GraphResult<Vec<(EntityId, EdgeId, f64)>> {
418        let mut neighbors = Vec::new();
419
420        // Get outgoing neighbors
421        if self.direction.includes_outgoing() {
422            self.add_neighbors_outgoing(tx, node, &mut neighbors)?;
423        }
424
425        // Get incoming neighbors
426        if self.direction.includes_incoming() {
427            self.add_neighbors_incoming(tx, node, &mut neighbors)?;
428        }
429
430        Ok(neighbors)
431    }
432
433    fn add_neighbors_outgoing<T: Transaction>(
434        &self,
435        tx: &T,
436        node: EntityId,
437        neighbors: &mut Vec<(EntityId, EdgeId, f64)>,
438    ) -> GraphResult<()> {
439        match &self.filter.edge_types {
440            Some(types) => {
441                for edge_type in types {
442                    AdjacencyIndex::for_each_outgoing_by_type(tx, node, edge_type, |edge_id| {
443                        if let Some(edge) = EdgeStore::get(tx, edge_id)? {
444                            let weight = self.weight_config.extract_weight(&edge)?;
445                            neighbors.push((edge.target, edge_id, weight));
446                        }
447                        Ok(true)
448                    })?;
449                }
450            }
451            None => {
452                AdjacencyIndex::for_each_outgoing(tx, node, |edge_id| {
453                    if let Some(edge) = EdgeStore::get(tx, edge_id)? {
454                        let weight = self.weight_config.extract_weight(&edge)?;
455                        neighbors.push((edge.target, edge_id, weight));
456                    }
457                    Ok(true)
458                })?;
459            }
460        }
461        Ok(())
462    }
463
464    fn add_neighbors_incoming<T: Transaction>(
465        &self,
466        tx: &T,
467        node: EntityId,
468        neighbors: &mut Vec<(EntityId, EdgeId, f64)>,
469    ) -> GraphResult<()> {
470        match &self.filter.edge_types {
471            Some(types) => {
472                for edge_type in types {
473                    AdjacencyIndex::for_each_incoming_by_type(tx, node, edge_type, |edge_id| {
474                        if let Some(edge) = EdgeStore::get(tx, edge_id)? {
475                            let weight = self.weight_config.extract_weight(&edge)?;
476                            neighbors.push((edge.source, edge_id, weight));
477                        }
478                        Ok(true)
479                    })?;
480                }
481            }
482            None => {
483                AdjacencyIndex::for_each_incoming(tx, node, |edge_id| {
484                    if let Some(edge) = EdgeStore::get(tx, edge_id)? {
485                        let weight = self.weight_config.extract_weight(&edge)?;
486                        neighbors.push((edge.source, edge_id, weight));
487                    }
488                    Ok(true)
489                })?;
490            }
491        }
492        Ok(())
493    }
494
495    /// Reconstruct the path from source to target using the parent map.
496    fn reconstruct_path(
497        &self,
498        parent: &HashMap<EntityId, (EntityId, EdgeId)>,
499        total_weight: f64,
500    ) -> WeightedPathResult {
501        let mut nodes = Vec::new();
502        let mut edges = Vec::new();
503        let mut current = self.target;
504
505        // Trace back from target to source
506        while let Some(&(prev, edge_id)) = parent.get(&current) {
507            nodes.push(current);
508            edges.push(edge_id);
509            current = prev;
510        }
511
512        // Add source
513        nodes.push(self.source);
514
515        // Reverse to get source -> target order
516        nodes.reverse();
517        edges.reverse();
518
519        WeightedPathResult::new(nodes, edges, total_weight)
520    }
521
522    /// Convenience method: find shortest weighted path with default settings.
523    pub fn find_path<T: Transaction>(
524        tx: &T,
525        source: EntityId,
526        target: EntityId,
527        direction: Direction,
528    ) -> GraphResult<Option<WeightedPathResult>> {
529        Self::new(source, target, direction).find(tx)
530    }
531
532    /// Find the shortest distance (total weight) to the target.
533    ///
534    /// This is more efficient than `find()` when you only need the distance.
535    pub fn distance<T: Transaction>(self, tx: &T) -> GraphResult<Option<f64>> {
536        if self.source == self.target {
537            return Ok(Some(0.0));
538        }
539
540        // Estimate initial capacity based on typical graph traversal patterns
541        const INITIAL_CAPACITY: usize = 256;
542
543        let mut distances: HashMap<EntityId, f64> = HashMap::with_capacity(INITIAL_CAPACITY);
544        let mut finalized: HashSet<EntityId> = HashSet::with_capacity(INITIAL_CAPACITY);
545        let mut heap: BinaryHeap<DijkstraEntry> = BinaryHeap::with_capacity(INITIAL_CAPACITY);
546
547        distances.insert(self.source, 0.0);
548        heap.push(DijkstraEntry { node: self.source, distance: 0.0 });
549
550        while let Some(DijkstraEntry { node: current, distance: current_dist }) = heap.pop() {
551            if finalized.contains(&current) {
552                continue;
553            }
554
555            if current == self.target {
556                return Ok(Some(current_dist));
557            }
558
559            finalized.insert(current);
560
561            if let Some(&known_dist) = distances.get(&current) {
562                if current_dist > known_dist {
563                    continue;
564                }
565            }
566
567            let neighbors = self.get_neighbors_with_weights(tx, current)?;
568
569            for (neighbor, edge_id, weight) in neighbors {
570                if weight < 0.0 {
571                    return Err(GraphError::InvalidWeight {
572                        edge_id,
573                        message: format!(
574                            "negative weight {} not supported by Dijkstra's algorithm",
575                            weight
576                        ),
577                    });
578                }
579
580                if finalized.contains(&neighbor) {
581                    continue;
582                }
583
584                if neighbor != self.target && !self.filter.should_include_node(neighbor) {
585                    continue;
586                }
587
588                let new_dist = current_dist + weight;
589
590                if let Some(max) = self.max_weight {
591                    if new_dist > max {
592                        continue;
593                    }
594                }
595
596                let is_better = match distances.get(&neighbor) {
597                    None => true,
598                    Some(&existing) => new_dist < existing,
599                };
600
601                if is_better {
602                    distances.insert(neighbor, new_dist);
603                    heap.push(DijkstraEntry { node: neighbor, distance: new_dist });
604                }
605            }
606        }
607
608        Ok(None)
609    }
610
611    /// Check if a path exists within the weight constraints.
612    pub fn exists<T: Transaction>(self, tx: &T) -> GraphResult<bool> {
613        Ok(self.distance(tx)?.is_some())
614    }
615}
616
617/// Find single-source shortest paths to all reachable nodes.
618///
619/// This runs Dijkstra's algorithm from a single source and returns
620/// the shortest distance to all reachable nodes.
621pub struct SingleSourceDijkstra {
622    /// Source node.
623    source: EntityId,
624    /// Traversal direction.
625    direction: Direction,
626    /// Weight configuration.
627    weight_config: WeightConfig,
628    /// Maximum total weight to search.
629    max_weight: Option<f64>,
630    /// Filter for traversal.
631    filter: TraversalFilter,
632}
633
634impl SingleSourceDijkstra {
635    /// Create a new single-source Dijkstra finder.
636    pub fn new(source: EntityId, direction: Direction) -> Self {
637        Self {
638            source,
639            direction,
640            weight_config: WeightConfig::default(),
641            max_weight: None,
642            filter: TraversalFilter::new(),
643        }
644    }
645
646    /// Set the weight property name to use.
647    pub fn with_weight_property(mut self, property: impl Into<String>) -> Self {
648        self.weight_config = WeightConfig::property(property);
649        self
650    }
651
652    /// Set the maximum total weight to search.
653    pub fn with_max_weight(mut self, max_weight: f64) -> Self {
654        self.max_weight = Some(max_weight);
655        self
656    }
657
658    /// Filter to only traverse edges of the specified type.
659    pub fn with_edge_type(mut self, edge_type: impl Into<EdgeType>) -> Self {
660        self.filter = self.filter.with_edge_type(edge_type);
661        self
662    }
663
664    /// Compute shortest distances to all reachable nodes.
665    ///
666    /// # Returns
667    ///
668    /// A map from node ID to (distance, parent node, edge used).
669    /// The source node maps to (0.0, None).
670    pub fn compute<T: Transaction>(
671        self,
672        tx: &T,
673    ) -> GraphResult<HashMap<EntityId, (f64, Option<(EntityId, EdgeId)>)>> {
674        // Estimate initial capacity based on typical graph traversal patterns
675        const INITIAL_CAPACITY: usize = 256;
676
677        let mut results: HashMap<EntityId, (f64, Option<(EntityId, EdgeId)>)> =
678            HashMap::with_capacity(INITIAL_CAPACITY);
679        let mut finalized: HashSet<EntityId> = HashSet::with_capacity(INITIAL_CAPACITY);
680        let mut heap: BinaryHeap<DijkstraEntry> = BinaryHeap::with_capacity(INITIAL_CAPACITY);
681
682        // Initialize source
683        results.insert(self.source, (0.0, None));
684        heap.push(DijkstraEntry { node: self.source, distance: 0.0 });
685
686        while let Some(DijkstraEntry { node: current, distance: current_dist }) = heap.pop() {
687            if finalized.contains(&current) {
688                continue;
689            }
690
691            finalized.insert(current);
692
693            // Skip if we already have a better path
694            if let Some(&(known_dist, _)) = results.get(&current) {
695                if current_dist > known_dist {
696                    continue;
697                }
698            }
699
700            // Explore neighbors
701            let neighbors = self.get_neighbors_with_weights(tx, current)?;
702
703            for (neighbor, edge_id, weight) in neighbors {
704                if weight < 0.0 {
705                    return Err(GraphError::InvalidWeight {
706                        edge_id,
707                        message: format!(
708                            "negative weight {} not supported by Dijkstra's algorithm",
709                            weight
710                        ),
711                    });
712                }
713
714                if finalized.contains(&neighbor) {
715                    continue;
716                }
717
718                if !self.filter.should_include_node(neighbor) {
719                    continue;
720                }
721
722                let new_dist = current_dist + weight;
723
724                if let Some(max) = self.max_weight {
725                    if new_dist > max {
726                        continue;
727                    }
728                }
729
730                let is_better = match results.get(&neighbor) {
731                    None => true,
732                    Some((existing, _)) => new_dist < *existing,
733                };
734
735                if is_better {
736                    results.insert(neighbor, (new_dist, Some((current, edge_id))));
737                    heap.push(DijkstraEntry { node: neighbor, distance: new_dist });
738                }
739            }
740        }
741
742        Ok(results)
743    }
744
745    /// Get neighbors with their edge weights.
746    fn get_neighbors_with_weights<T: Transaction>(
747        &self,
748        tx: &T,
749        node: EntityId,
750    ) -> GraphResult<Vec<(EntityId, EdgeId, f64)>> {
751        let mut neighbors = Vec::new();
752
753        if self.direction.includes_outgoing() {
754            match &self.filter.edge_types {
755                Some(types) => {
756                    for edge_type in types {
757                        AdjacencyIndex::for_each_outgoing_by_type(
758                            tx,
759                            node,
760                            edge_type,
761                            |edge_id| {
762                                if let Some(edge) = EdgeStore::get(tx, edge_id)? {
763                                    let weight = self.weight_config.extract_weight(&edge)?;
764                                    neighbors.push((edge.target, edge_id, weight));
765                                }
766                                Ok(true)
767                            },
768                        )?;
769                    }
770                }
771                None => {
772                    AdjacencyIndex::for_each_outgoing(tx, node, |edge_id| {
773                        if let Some(edge) = EdgeStore::get(tx, edge_id)? {
774                            let weight = self.weight_config.extract_weight(&edge)?;
775                            neighbors.push((edge.target, edge_id, weight));
776                        }
777                        Ok(true)
778                    })?;
779                }
780            }
781        }
782
783        if self.direction.includes_incoming() {
784            match &self.filter.edge_types {
785                Some(types) => {
786                    for edge_type in types {
787                        AdjacencyIndex::for_each_incoming_by_type(
788                            tx,
789                            node,
790                            edge_type,
791                            |edge_id| {
792                                if let Some(edge) = EdgeStore::get(tx, edge_id)? {
793                                    let weight = self.weight_config.extract_weight(&edge)?;
794                                    neighbors.push((edge.source, edge_id, weight));
795                                }
796                                Ok(true)
797                            },
798                        )?;
799                    }
800                }
801                None => {
802                    AdjacencyIndex::for_each_incoming(tx, node, |edge_id| {
803                        if let Some(edge) = EdgeStore::get(tx, edge_id)? {
804                            let weight = self.weight_config.extract_weight(&edge)?;
805                            neighbors.push((edge.source, edge_id, weight));
806                        }
807                        Ok(true)
808                    })?;
809                }
810            }
811        }
812
813        Ok(neighbors)
814    }
815}
816
817#[cfg(test)]
818mod tests {
819    use super::*;
820
821    #[test]
822    fn weighted_path_result_single_node() {
823        let path = WeightedPathResult::single_node(EntityId::new(1));
824        assert_eq!(path.source(), EntityId::new(1));
825        assert_eq!(path.target(), EntityId::new(1));
826        assert_eq!(path.length, 0);
827        assert_eq!(path.total_weight, 0.0);
828        assert!(path.is_empty());
829    }
830
831    #[test]
832    fn weighted_path_result_multi_node() {
833        let nodes = vec![EntityId::new(1), EntityId::new(2), EntityId::new(3)];
834        let edges = vec![EdgeId::new(10), EdgeId::new(20)];
835        let path = WeightedPathResult::new(nodes, edges, 5.5);
836
837        assert_eq!(path.source(), EntityId::new(1));
838        assert_eq!(path.target(), EntityId::new(3));
839        assert_eq!(path.length, 2);
840        assert_eq!(path.total_weight, 5.5);
841        assert!(!path.is_empty());
842    }
843
844    #[test]
845    fn weight_config_default() {
846        let config = WeightConfig::default();
847        match config {
848            WeightConfig::Property { name, default_weight } => {
849                assert_eq!(name, "weight");
850                assert_eq!(default_weight, 1.0);
851            }
852            _ => panic!("expected Property variant"),
853        }
854    }
855
856    #[test]
857    fn weight_config_constant() {
858        let config = WeightConfig::constant(2.5);
859        let edge = Edge::new(EdgeId::new(1), EntityId::new(1), EntityId::new(2), "TEST");
860        assert_eq!(config.extract_weight(&edge).unwrap(), 2.5);
861    }
862
863    #[test]
864    fn weight_config_property_float() {
865        let config = WeightConfig::property("cost");
866        let edge = Edge::new(EdgeId::new(1), EntityId::new(1), EntityId::new(2), "TEST")
867            .with_property("cost", 3.5f64);
868        assert_eq!(config.extract_weight(&edge).unwrap(), 3.5);
869    }
870
871    #[test]
872    fn weight_config_property_int() {
873        let config = WeightConfig::property("cost");
874        let edge = Edge::new(EdgeId::new(1), EntityId::new(1), EntityId::new(2), "TEST")
875            .with_property("cost", 42i64);
876        assert_eq!(config.extract_weight(&edge).unwrap(), 42.0);
877    }
878
879    #[test]
880    fn weight_config_property_missing_uses_default() {
881        let config = WeightConfig::property_with_default("cost", 1.5);
882        let edge = Edge::new(EdgeId::new(1), EntityId::new(1), EntityId::new(2), "TEST");
883        assert_eq!(config.extract_weight(&edge).unwrap(), 1.5);
884    }
885
886    #[test]
887    fn weight_config_property_non_numeric_error() {
888        let config = WeightConfig::property("cost");
889        let edge = Edge::new(EdgeId::new(1), EntityId::new(1), EntityId::new(2), "TEST")
890            .with_property("cost", "not a number");
891        assert!(config.extract_weight(&edge).is_err());
892    }
893
894    #[test]
895    fn dijkstra_builder() {
896        let d = Dijkstra::new(EntityId::new(1), EntityId::new(10), Direction::Both)
897            .with_weight_property("distance")
898            .with_max_weight(100.0)
899            .with_edge_type("ROAD");
900
901        assert_eq!(d.source, EntityId::new(1));
902        assert_eq!(d.target, EntityId::new(10));
903        assert_eq!(d.direction, Direction::Both);
904        assert_eq!(d.max_weight, Some(100.0));
905    }
906
907    #[test]
908    fn dijkstra_entry_ordering() {
909        let entry1 = DijkstraEntry { node: EntityId::new(1), distance: 5.0 };
910        let entry2 = DijkstraEntry { node: EntityId::new(2), distance: 3.0 };
911        let entry3 = DijkstraEntry { node: EntityId::new(3), distance: 7.0 };
912
913        // Min-heap: smaller distance should have higher priority
914        assert!(entry2 > entry1); // 3.0 has higher priority than 5.0
915        assert!(entry1 > entry3); // 5.0 has higher priority than 7.0
916    }
917}
manifoldb_graph/traversal/dijkstra.rs

manifoldb_graph/traversal/
dijkstra.rs
