grafeo_adapters/plugins/algorithms/
shortest_path.rs

1//! Shortest path algorithms: Dijkstra, A*, Bellman-Ford, Floyd-Warshall.
2//!
3//! These algorithms find optimal paths in weighted graphs, supporting
4//! both single-source and all-pairs variants.
5
6use std::collections::BinaryHeap;
7use std::sync::OnceLock;
8
9use grafeo_common::types::{NodeId, Value};
10use grafeo_common::utils::error::{Error, Result};
11use grafeo_common::utils::hash::FxHashMap;
12use grafeo_core::graph::Direction;
13use grafeo_core::graph::lpg::LpgStore;
14
15use super::super::{AlgorithmResult, ParameterDef, ParameterType, Parameters};
16use super::traits::{GraphAlgorithm, MinScored};
17
18// ============================================================================
19// Edge Weight Extraction
20// ============================================================================
21
22/// Extracts edge weight from a property value.
23///
24/// Supports Int64 and Float64 values, defaulting to 1.0 if no weight property.
25fn extract_weight(
26    store: &LpgStore,
27    edge_id: grafeo_common::types::EdgeId,
28    weight_prop: Option<&str>,
29) -> f64 {
30    if let Some(prop_name) = weight_prop
31        && let Some(edge) = store.get_edge(edge_id)
32        && let Some(value) = edge.get_property(prop_name)
33    {
34        return match value {
35            Value::Int64(i) => *i as f64,
36            Value::Float64(f) => *f,
37            _ => 1.0,
38        };
39    }
40    1.0
41}
42
43// ============================================================================
44// Dijkstra's Algorithm
45// ============================================================================
46
47/// Result of Dijkstra's algorithm.
48#[derive(Debug, Clone)]
49pub struct DijkstraResult {
50    /// Distances from source to each reachable node.
51    pub distances: FxHashMap<NodeId, f64>,
52    /// Predecessor map for path reconstruction.
53    pub predecessors: FxHashMap<NodeId, NodeId>,
54}
55
56impl DijkstraResult {
57    /// Reconstructs the path from source to target.
58    ///
59    /// Returns `None` if target is unreachable.
60    pub fn path_to(&self, source: NodeId, target: NodeId) -> Option<Vec<NodeId>> {
61        if !self.distances.contains_key(&target) {
62            return None;
63        }
64
65        let mut path = Vec::new();
66        let mut current = target;
67
68        while current != source {
69            path.push(current);
70            current = *self.predecessors.get(&current)?;
71        }
72        path.push(source);
73        path.reverse();
74
75        Some(path)
76    }
77
78    /// Returns the distance to a target node.
79    pub fn distance_to(&self, target: NodeId) -> Option<f64> {
80        self.distances.get(&target).copied()
81    }
82}
83
84/// Runs Dijkstra's algorithm from a source node.
85///
86/// # Arguments
87///
88/// * `store` - The graph store
89/// * `source` - Starting node ID
90/// * `weight_property` - Optional property name for edge weights (defaults to 1.0)
91///
92/// # Returns
93///
94/// Distances and predecessors for all reachable nodes.
95///
96/// # Complexity
97///
98/// O((V + E) log V) using a binary heap.
99pub fn dijkstra(store: &LpgStore, source: NodeId, weight_property: Option<&str>) -> DijkstraResult {
100    let mut distances: FxHashMap<NodeId, f64> = FxHashMap::default();
101    let mut predecessors: FxHashMap<NodeId, NodeId> = FxHashMap::default();
102    let mut heap: BinaryHeap<MinScored<f64, NodeId>> = BinaryHeap::new();
103
104    // Check if source exists
105    if store.get_node(source).is_none() {
106        return DijkstraResult {
107            distances,
108            predecessors,
109        };
110    }
111
112    distances.insert(source, 0.0);
113    heap.push(MinScored::new(0.0, source));
114
115    while let Some(MinScored(dist, node)) = heap.pop() {
116        // Skip if we've found a better path
117        if let Some(&best) = distances.get(&node)
118            && dist > best
119        {
120            continue;
121        }
122
123        // Explore neighbors
124        for (neighbor, edge_id) in store.edges_from(node, Direction::Outgoing) {
125            let weight = extract_weight(store, edge_id, weight_property);
126            let new_dist = dist + weight;
127
128            let is_better = distances
129                .get(&neighbor)
130                .map_or(true, |&current| new_dist < current);
131
132            if is_better {
133                distances.insert(neighbor, new_dist);
134                predecessors.insert(neighbor, node);
135                heap.push(MinScored::new(new_dist, neighbor));
136            }
137        }
138    }
139
140    DijkstraResult {
141        distances,
142        predecessors,
143    }
144}
145
146/// Runs Dijkstra's algorithm to find shortest path to a specific target.
147///
148/// Early terminates when target is reached.
149pub fn dijkstra_path(
150    store: &LpgStore,
151    source: NodeId,
152    target: NodeId,
153    weight_property: Option<&str>,
154) -> Option<(f64, Vec<NodeId>)> {
155    let mut distances: FxHashMap<NodeId, f64> = FxHashMap::default();
156    let mut predecessors: FxHashMap<NodeId, NodeId> = FxHashMap::default();
157    let mut heap: BinaryHeap<MinScored<f64, NodeId>> = BinaryHeap::new();
158
159    // Check if source and target exist
160    if store.get_node(source).is_none() || store.get_node(target).is_none() {
161        return None;
162    }
163
164    distances.insert(source, 0.0);
165    heap.push(MinScored::new(0.0, source));
166
167    while let Some(MinScored(dist, node)) = heap.pop() {
168        // Early termination if we've reached target
169        if node == target {
170            // Reconstruct path
171            let mut path = Vec::new();
172            let mut current = target;
173            while current != source {
174                path.push(current);
175                current = *predecessors.get(&current)?;
176            }
177            path.push(source);
178            path.reverse();
179            return Some((dist, path));
180        }
181
182        // Skip if we've found a better path
183        if let Some(&best) = distances.get(&node)
184            && dist > best
185        {
186            continue;
187        }
188
189        // Explore neighbors
190        for (neighbor, edge_id) in store.edges_from(node, Direction::Outgoing) {
191            let weight = extract_weight(store, edge_id, weight_property);
192            let new_dist = dist + weight;
193
194            let is_better = distances
195                .get(&neighbor)
196                .map_or(true, |&current| new_dist < current);
197
198            if is_better {
199                distances.insert(neighbor, new_dist);
200                predecessors.insert(neighbor, node);
201                heap.push(MinScored::new(new_dist, neighbor));
202            }
203        }
204    }
205
206    None // Target not reachable
207}
208
209// ============================================================================
210// A* Algorithm
211// ============================================================================
212
213/// Runs A* algorithm with a heuristic function.
214///
215/// # Arguments
216///
217/// * `store` - The graph store
218/// * `source` - Starting node ID
219/// * `target` - Target node ID
220/// * `weight_property` - Optional property name for edge weights
221/// * `heuristic` - Function estimating cost from node to target (must be admissible)
222///
223/// # Returns
224///
225/// The shortest path distance and path, or `None` if unreachable.
226///
227/// # Complexity
228///
229/// O(E) in the best case with a good heuristic, O((V + E) log V) in the worst case.
230pub fn astar<H>(
231    store: &LpgStore,
232    source: NodeId,
233    target: NodeId,
234    weight_property: Option<&str>,
235    heuristic: H,
236) -> Option<(f64, Vec<NodeId>)>
237where
238    H: Fn(NodeId) -> f64,
239{
240    let mut g_score: FxHashMap<NodeId, f64> = FxHashMap::default();
241    let mut predecessors: FxHashMap<NodeId, NodeId> = FxHashMap::default();
242    let mut heap: BinaryHeap<MinScored<f64, NodeId>> = BinaryHeap::new();
243
244    // Check if source and target exist
245    if store.get_node(source).is_none() || store.get_node(target).is_none() {
246        return None;
247    }
248
249    g_score.insert(source, 0.0);
250    let f_score = heuristic(source);
251    heap.push(MinScored::new(f_score, source));
252
253    while let Some(MinScored(_, node)) = heap.pop() {
254        if node == target {
255            // Reconstruct path
256            let mut path = Vec::new();
257            let mut current = target;
258            while current != source {
259                path.push(current);
260                current = *predecessors.get(&current)?;
261            }
262            path.push(source);
263            path.reverse();
264            return Some((*g_score.get(&target)?, path));
265        }
266
267        let current_g = *g_score.get(&node).unwrap_or(&f64::INFINITY);
268
269        // Explore neighbors
270        for (neighbor, edge_id) in store.edges_from(node, Direction::Outgoing) {
271            let weight = extract_weight(store, edge_id, weight_property);
272            let tentative_g = current_g + weight;
273
274            let is_better = g_score
275                .get(&neighbor)
276                .map_or(true, |&current| tentative_g < current);
277
278            if is_better {
279                predecessors.insert(neighbor, node);
280                g_score.insert(neighbor, tentative_g);
281                let f = tentative_g + heuristic(neighbor);
282                heap.push(MinScored::new(f, neighbor));
283            }
284        }
285    }
286
287    None // Target not reachable
288}
289
290// ============================================================================
291// Bellman-Ford Algorithm
292// ============================================================================
293
294/// Result of Bellman-Ford algorithm.
295#[derive(Debug, Clone)]
296pub struct BellmanFordResult {
297    /// Distances from source to each reachable node.
298    pub distances: FxHashMap<NodeId, f64>,
299    /// Predecessor map for path reconstruction.
300    pub predecessors: FxHashMap<NodeId, NodeId>,
301    /// Whether a negative cycle was detected.
302    pub has_negative_cycle: bool,
303    /// The source node used for path reconstruction.
304    source: NodeId,
305}
306
307impl BellmanFordResult {
308    /// Reconstructs the path from source to target.
309    pub fn path_to(&self, target: NodeId) -> Option<Vec<NodeId>> {
310        if !self.distances.contains_key(&target) {
311            return None;
312        }
313
314        let mut path = vec![target];
315        let mut current = target;
316
317        while current != self.source {
318            let pred = self.predecessors.get(&current)?;
319            path.push(*pred);
320            current = *pred;
321        }
322
323        path.reverse();
324        Some(path)
325    }
326}
327
328/// Runs Bellman-Ford algorithm from a source node.
329///
330/// Unlike Dijkstra, this algorithm handles negative edge weights
331/// and detects negative cycles.
332///
333/// # Arguments
334///
335/// * `store` - The graph store
336/// * `source` - Starting node ID
337/// * `weight_property` - Optional property name for edge weights
338///
339/// # Returns
340///
341/// Distances, predecessors, and negative cycle detection flag.
342///
343/// # Complexity
344///
345/// O(V × E)
346pub fn bellman_ford(
347    store: &LpgStore,
348    source: NodeId,
349    weight_property: Option<&str>,
350) -> BellmanFordResult {
351    let mut distances: FxHashMap<NodeId, f64> = FxHashMap::default();
352    let mut predecessors: FxHashMap<NodeId, NodeId> = FxHashMap::default();
353
354    // Check if source exists
355    if store.get_node(source).is_none() {
356        return BellmanFordResult {
357            distances,
358            predecessors,
359            has_negative_cycle: false,
360            source,
361        };
362    }
363
364    // Collect all nodes and edges
365    let nodes: Vec<NodeId> = store.node_ids();
366    let edges: Vec<(NodeId, NodeId, grafeo_common::types::EdgeId)> = nodes
367        .iter()
368        .flat_map(|&node| {
369            store
370                .edges_from(node, Direction::Outgoing)
371                .map(move |(neighbor, edge_id)| (node, neighbor, edge_id))
372        })
373        .collect();
374
375    let n = nodes.len();
376
377    // Initialize distances
378    distances.insert(source, 0.0);
379
380    // Relax edges V-1 times
381    for _ in 0..n.saturating_sub(1) {
382        let mut changed = false;
383        for &(u, v, edge_id) in &edges {
384            if let Some(&dist_u) = distances.get(&u) {
385                let weight = extract_weight(store, edge_id, weight_property);
386                let new_dist = dist_u + weight;
387
388                let is_better = distances
389                    .get(&v)
390                    .map_or(true, |&current| new_dist < current);
391
392                if is_better {
393                    distances.insert(v, new_dist);
394                    predecessors.insert(v, u);
395                    changed = true;
396                }
397            }
398        }
399        if !changed {
400            break; // Early termination
401        }
402    }
403
404    // Check for negative cycles
405    let mut has_negative_cycle = false;
406    for &(u, v, edge_id) in &edges {
407        if let Some(&dist_u) = distances.get(&u) {
408            let weight = extract_weight(store, edge_id, weight_property);
409            if let Some(&dist_v) = distances.get(&v)
410                && dist_u + weight < dist_v
411            {
412                has_negative_cycle = true;
413                break;
414            }
415        }
416    }
417
418    BellmanFordResult {
419        distances,
420        predecessors,
421        has_negative_cycle,
422        source,
423    }
424}
425
426// ============================================================================
427// Floyd-Warshall Algorithm
428// ============================================================================
429
430/// Result of Floyd-Warshall algorithm.
431#[derive(Debug, Clone)]
432pub struct FloydWarshallResult {
433    /// Distance matrix: distances[i][j] is the shortest distance from node i to node j.
434    distances: Vec<Vec<f64>>,
435    /// Next-hop matrix for path reconstruction.
436    next: Vec<Vec<Option<usize>>>,
437    /// Mapping from NodeId to matrix index.
438    node_to_index: FxHashMap<NodeId, usize>,
439    /// Mapping from matrix index to NodeId.
440    index_to_node: Vec<NodeId>,
441}
442
443impl FloydWarshallResult {
444    /// Returns the shortest distance between two nodes.
445    pub fn distance(&self, from: NodeId, to: NodeId) -> Option<f64> {
446        let i = *self.node_to_index.get(&from)?;
447        let j = *self.node_to_index.get(&to)?;
448        let dist = self.distances[i][j];
449        if dist == f64::INFINITY {
450            None
451        } else {
452            Some(dist)
453        }
454    }
455
456    /// Reconstructs the shortest path between two nodes.
457    pub fn path(&self, from: NodeId, to: NodeId) -> Option<Vec<NodeId>> {
458        let i = *self.node_to_index.get(&from)?;
459        let j = *self.node_to_index.get(&to)?;
460
461        if self.distances[i][j] == f64::INFINITY {
462            return None;
463        }
464
465        let mut path = vec![from];
466        let mut current = i;
467
468        while current != j {
469            current = self.next[current][j]?;
470            path.push(self.index_to_node[current]);
471        }
472
473        Some(path)
474    }
475
476    /// Checks if the graph has a negative cycle.
477    pub fn has_negative_cycle(&self) -> bool {
478        for i in 0..self.distances.len() {
479            if self.distances[i][i] < 0.0 {
480                return true;
481            }
482        }
483        false
484    }
485
486    /// Returns all nodes in the graph.
487    pub fn nodes(&self) -> &[NodeId] {
488        &self.index_to_node
489    }
490}
491
492/// Runs Floyd-Warshall algorithm for all-pairs shortest paths.
493///
494/// # Arguments
495///
496/// * `store` - The graph store
497/// * `weight_property` - Optional property name for edge weights
498///
499/// # Returns
500///
501/// All-pairs shortest path distances and path reconstruction data.
502///
503/// # Complexity
504///
505/// O(V³)
506pub fn floyd_warshall(store: &LpgStore, weight_property: Option<&str>) -> FloydWarshallResult {
507    let nodes: Vec<NodeId> = store.node_ids();
508    let n = nodes.len();
509
510    // Build node index mappings
511    let mut node_to_index: FxHashMap<NodeId, usize> = FxHashMap::default();
512    for (idx, &node) in nodes.iter().enumerate() {
513        node_to_index.insert(node, idx);
514    }
515
516    // Initialize distance matrix
517    let mut distances = vec![vec![f64::INFINITY; n]; n];
518    let mut next: Vec<Vec<Option<usize>>> = vec![vec![None; n]; n];
519
520    // Set diagonal to 0
521    for i in 0..n {
522        distances[i][i] = 0.0;
523    }
524
525    // Initialize with direct edges
526    for (idx, &node) in nodes.iter().enumerate() {
527        for (neighbor, edge_id) in store.edges_from(node, Direction::Outgoing) {
528            if let Some(&neighbor_idx) = node_to_index.get(&neighbor) {
529                let weight = extract_weight(store, edge_id, weight_property);
530                if weight < distances[idx][neighbor_idx] {
531                    distances[idx][neighbor_idx] = weight;
532                    next[idx][neighbor_idx] = Some(neighbor_idx);
533                }
534            }
535        }
536    }
537
538    // Floyd-Warshall main loop
539    for k in 0..n {
540        for i in 0..n {
541            for j in 0..n {
542                let through_k = distances[i][k] + distances[k][j];
543                if through_k < distances[i][j] {
544                    distances[i][j] = through_k;
545                    next[i][j] = next[i][k];
546                }
547            }
548        }
549    }
550
551    FloydWarshallResult {
552        distances,
553        next,
554        node_to_index,
555        index_to_node: nodes,
556    }
557}
558
559// ============================================================================
560// Algorithm Wrappers for Plugin Registry
561// ============================================================================
562
563/// Static parameter definitions for Dijkstra algorithm.
564static DIJKSTRA_PARAMS: OnceLock<Vec<ParameterDef>> = OnceLock::new();
565
566fn dijkstra_params() -> &'static [ParameterDef] {
567    DIJKSTRA_PARAMS.get_or_init(|| {
568        vec![
569            ParameterDef {
570                name: "source".to_string(),
571                description: "Source node ID".to_string(),
572                param_type: ParameterType::NodeId,
573                required: true,
574                default: None,
575            },
576            ParameterDef {
577                name: "target".to_string(),
578                description: "Target node ID (optional, for single-pair shortest path)".to_string(),
579                param_type: ParameterType::NodeId,
580                required: false,
581                default: None,
582            },
583            ParameterDef {
584                name: "weight".to_string(),
585                description: "Edge property name for weights (default: 1.0)".to_string(),
586                param_type: ParameterType::String,
587                required: false,
588                default: None,
589            },
590        ]
591    })
592}
593
594/// Dijkstra algorithm wrapper for the plugin registry.
595pub struct DijkstraAlgorithm;
596
597impl GraphAlgorithm for DijkstraAlgorithm {
598    fn name(&self) -> &str {
599        "dijkstra"
600    }
601
602    fn description(&self) -> &str {
603        "Dijkstra's shortest path algorithm"
604    }
605
606    fn parameters(&self) -> &[ParameterDef] {
607        dijkstra_params()
608    }
609
610    fn execute(&self, store: &LpgStore, params: &Parameters) -> Result<AlgorithmResult> {
611        let source_id = params
612            .get_int("source")
613            .ok_or_else(|| Error::InvalidValue("source parameter required".to_string()))?;
614
615        let source = NodeId::new(source_id as u64);
616        let weight_prop = params.get_string("weight");
617
618        if let Some(target_id) = params.get_int("target") {
619            // Single-pair shortest path
620            let target = NodeId::new(target_id as u64);
621            match dijkstra_path(store, source, target, weight_prop.as_deref()) {
622                Some((distance, path)) => {
623                    let mut result = AlgorithmResult::new(vec![
624                        "source".to_string(),
625                        "target".to_string(),
626                        "distance".to_string(),
627                        "path".to_string(),
628                    ]);
629
630                    let path_str: String = path
631                        .iter()
632                        .map(|n| n.0.to_string())
633                        .collect::<Vec<_>>()
634                        .join(" -> ");
635
636                    result.add_row(vec![
637                        Value::Int64(source.0 as i64),
638                        Value::Int64(target.0 as i64),
639                        Value::Float64(distance),
640                        Value::String(path_str.into()),
641                    ]);
642
643                    Ok(result)
644                }
645                None => {
646                    let mut result = AlgorithmResult::new(vec![
647                        "source".to_string(),
648                        "target".to_string(),
649                        "distance".to_string(),
650                        "path".to_string(),
651                    ]);
652                    result.add_row(vec![
653                        Value::Int64(source.0 as i64),
654                        Value::Int64(target_id),
655                        Value::Null,
656                        Value::String("unreachable".into()),
657                    ]);
658                    Ok(result)
659                }
660            }
661        } else {
662            // Single-source shortest paths
663            let dijkstra_result = dijkstra(store, source, weight_prop.as_deref());
664
665            let mut result =
666                AlgorithmResult::new(vec!["node_id".to_string(), "distance".to_string()]);
667
668            for (node, distance) in dijkstra_result.distances {
669                result.add_row(vec![Value::Int64(node.0 as i64), Value::Float64(distance)]);
670            }
671
672            Ok(result)
673        }
674    }
675}
676
677/// Static parameter definitions for Bellman-Ford algorithm.
678static BELLMAN_FORD_PARAMS: OnceLock<Vec<ParameterDef>> = OnceLock::new();
679
680fn bellman_ford_params() -> &'static [ParameterDef] {
681    BELLMAN_FORD_PARAMS.get_or_init(|| {
682        vec![
683            ParameterDef {
684                name: "source".to_string(),
685                description: "Source node ID".to_string(),
686                param_type: ParameterType::NodeId,
687                required: true,
688                default: None,
689            },
690            ParameterDef {
691                name: "weight".to_string(),
692                description: "Edge property name for weights (default: 1.0)".to_string(),
693                param_type: ParameterType::String,
694                required: false,
695                default: None,
696            },
697        ]
698    })
699}
700
701/// Bellman-Ford algorithm wrapper for the plugin registry.
702pub struct BellmanFordAlgorithm;
703
704impl GraphAlgorithm for BellmanFordAlgorithm {
705    fn name(&self) -> &str {
706        "bellman_ford"
707    }
708
709    fn description(&self) -> &str {
710        "Bellman-Ford shortest path algorithm (handles negative weights)"
711    }
712
713    fn parameters(&self) -> &[ParameterDef] {
714        bellman_ford_params()
715    }
716
717    fn execute(&self, store: &LpgStore, params: &Parameters) -> Result<AlgorithmResult> {
718        let source_id = params
719            .get_int("source")
720            .ok_or_else(|| Error::InvalidValue("source parameter required".to_string()))?;
721
722        let source = NodeId::new(source_id as u64);
723        let weight_prop = params.get_string("weight");
724
725        let bf_result = bellman_ford(store, source, weight_prop.as_deref());
726
727        let mut result = AlgorithmResult::new(vec![
728            "node_id".to_string(),
729            "distance".to_string(),
730            "has_negative_cycle".to_string(),
731        ]);
732
733        for (node, distance) in bf_result.distances {
734            result.add_row(vec![
735                Value::Int64(node.0 as i64),
736                Value::Float64(distance),
737                Value::Bool(bf_result.has_negative_cycle),
738            ]);
739        }
740
741        Ok(result)
742    }
743}
744
745/// Static parameter definitions for Floyd-Warshall algorithm.
746static FLOYD_WARSHALL_PARAMS: OnceLock<Vec<ParameterDef>> = OnceLock::new();
747
748fn floyd_warshall_params() -> &'static [ParameterDef] {
749    FLOYD_WARSHALL_PARAMS.get_or_init(|| {
750        vec![ParameterDef {
751            name: "weight".to_string(),
752            description: "Edge property name for weights (default: 1.0)".to_string(),
753            param_type: ParameterType::String,
754            required: false,
755            default: None,
756        }]
757    })
758}
759
760/// Floyd-Warshall algorithm wrapper for the plugin registry.
761pub struct FloydWarshallAlgorithm;
762
763impl GraphAlgorithm for FloydWarshallAlgorithm {
764    fn name(&self) -> &str {
765        "floyd_warshall"
766    }
767
768    fn description(&self) -> &str {
769        "Floyd-Warshall all-pairs shortest paths algorithm"
770    }
771
772    fn parameters(&self) -> &[ParameterDef] {
773        floyd_warshall_params()
774    }
775
776    fn execute(&self, store: &LpgStore, params: &Parameters) -> Result<AlgorithmResult> {
777        let weight_prop = params.get_string("weight");
778
779        let fw_result = floyd_warshall(store, weight_prop.as_deref());
780
781        let mut result = AlgorithmResult::new(vec![
782            "source".to_string(),
783            "target".to_string(),
784            "distance".to_string(),
785        ]);
786
787        // Output all pairs with finite distances
788        for (i, &from_node) in fw_result.index_to_node.iter().enumerate() {
789            for (j, &to_node) in fw_result.index_to_node.iter().enumerate() {
790                let dist = fw_result.distances[i][j];
791                if dist < f64::INFINITY {
792                    result.add_row(vec![
793                        Value::Int64(from_node.0 as i64),
794                        Value::Int64(to_node.0 as i64),
795                        Value::Float64(dist),
796                    ]);
797                }
798            }
799        }
800
801        Ok(result)
802    }
803}
804
805// ============================================================================
806// Tests
807// ============================================================================
808
809#[cfg(test)]
810mod tests {
811    use super::*;
812
813    fn create_weighted_graph() -> LpgStore {
814        let store = LpgStore::new();
815
816        // Create a weighted graph:
817        //   0 --2--> 1 --3--> 2
818        //   |        ^        |
819        //   4        1        1
820        //   v        |        v
821        //   3 -------+        4
822        //
823        // Shortest path from 0 to 2: 0 -> 3 -> 1 -> 2 (cost: 4+1+3 = 8)
824        // vs direct: 0 -> 1 -> 2 (cost: 2+3 = 5)
825        let n0 = store.create_node(&["Node"]);
826        let n1 = store.create_node(&["Node"]);
827        let n2 = store.create_node(&["Node"]);
828        let n3 = store.create_node(&["Node"]);
829        let n4 = store.create_node(&["Node"]);
830
831        // Create edges with weights
832        store.create_edge_with_props(n0, n1, "EDGE", [("weight", Value::Float64(2.0))]);
833        store.create_edge_with_props(n1, n2, "EDGE", [("weight", Value::Float64(3.0))]);
834        store.create_edge_with_props(n0, n3, "EDGE", [("weight", Value::Float64(4.0))]);
835        store.create_edge_with_props(n3, n1, "EDGE", [("weight", Value::Float64(1.0))]);
836        store.create_edge_with_props(n2, n4, "EDGE", [("weight", Value::Float64(1.0))]);
837
838        store
839    }
840
841    #[test]
842    fn test_dijkstra_basic() {
843        let store = create_weighted_graph();
844        let result = dijkstra(&store, NodeId::new(0), Some("weight"));
845
846        assert!(result.distances.contains_key(&NodeId::new(0)));
847        assert_eq!(result.distance_to(NodeId::new(0)), Some(0.0));
848        assert!(result.distances.contains_key(&NodeId::new(1)));
849        assert!(result.distances.contains_key(&NodeId::new(2)));
850    }
851
852    #[test]
853    fn test_dijkstra_path() {
854        let store = create_weighted_graph();
855        let result = dijkstra(&store, NodeId::new(0), Some("weight"));
856
857        let path = result.path_to(NodeId::new(0), NodeId::new(2));
858        assert!(path.is_some());
859
860        let path = path.unwrap();
861        assert_eq!(path[0], NodeId::new(0)); // Start
862        assert_eq!(*path.last().unwrap(), NodeId::new(2)); // End
863    }
864
865    #[test]
866    fn test_dijkstra_single_pair() {
867        let store = create_weighted_graph();
868        let result = dijkstra_path(&store, NodeId::new(0), NodeId::new(4), Some("weight"));
869
870        assert!(result.is_some());
871        let (distance, path) = result.unwrap();
872        assert!(distance > 0.0);
873        assert_eq!(path[0], NodeId::new(0));
874        assert_eq!(*path.last().unwrap(), NodeId::new(4));
875    }
876
877    #[test]
878    fn test_dijkstra_unreachable() {
879        let store = LpgStore::new();
880        let n0 = store.create_node(&["Node"]);
881        let _n1 = store.create_node(&["Node"]); // Disconnected
882
883        let result = dijkstra_path(&store, n0, NodeId::new(1), None);
884        assert!(result.is_none());
885    }
886
887    #[test]
888    fn test_bellman_ford_basic() {
889        let store = create_weighted_graph();
890        let result = bellman_ford(&store, NodeId::new(0), Some("weight"));
891
892        assert!(!result.has_negative_cycle);
893        assert!(result.distances.contains_key(&NodeId::new(0)));
894        assert_eq!(*result.distances.get(&NodeId::new(0)).unwrap(), 0.0);
895    }
896
897    #[test]
898    fn test_floyd_warshall_basic() {
899        let store = create_weighted_graph();
900        let result = floyd_warshall(&store, Some("weight"));
901
902        // Self-distances should be 0
903        assert_eq!(result.distance(NodeId::new(0), NodeId::new(0)), Some(0.0));
904        assert_eq!(result.distance(NodeId::new(1), NodeId::new(1)), Some(0.0));
905
906        // Check some paths exist
907        assert!(result.distance(NodeId::new(0), NodeId::new(2)).is_some());
908    }
909
910    #[test]
911    fn test_floyd_warshall_path_reconstruction() {
912        let store = create_weighted_graph();
913        let result = floyd_warshall(&store, Some("weight"));
914
915        let path = result.path(NodeId::new(0), NodeId::new(2));
916        assert!(path.is_some());
917
918        let path = path.unwrap();
919        assert_eq!(path[0], NodeId::new(0));
920        assert_eq!(*path.last().unwrap(), NodeId::new(2));
921    }
922
923    #[test]
924    fn test_astar_basic() {
925        let store = create_weighted_graph();
926
927        // Simple heuristic: always return 0 (degenerates to Dijkstra)
928        let heuristic = |_: NodeId| 0.0;
929
930        let result = astar(
931            &store,
932            NodeId::new(0),
933            NodeId::new(4),
934            Some("weight"),
935            heuristic,
936        );
937        assert!(result.is_some());
938
939        let (distance, path) = result.unwrap();
940        assert!(distance > 0.0);
941        assert_eq!(path[0], NodeId::new(0));
942        assert_eq!(*path.last().unwrap(), NodeId::new(4));
943    }
944
945    #[test]
946    fn test_dijkstra_nonexistent_source() {
947        let store = LpgStore::new();
948        let result = dijkstra(&store, NodeId::new(999), None);
949        assert!(result.distances.is_empty());
950    }
951
952    #[test]
953    fn test_unweighted_defaults() {
954        let store = LpgStore::new();
955        let n0 = store.create_node(&["Node"]);
956        let n1 = store.create_node(&["Node"]);
957        let n2 = store.create_node(&["Node"]);
958        store.create_edge(n0, n1, "EDGE");
959        store.create_edge(n1, n2, "EDGE");
960
961        // Without weight property, should default to 1.0 per edge
962        let result = dijkstra(&store, n0, None);
963        assert_eq!(result.distance_to(n1), Some(1.0));
964        assert_eq!(result.distance_to(n2), Some(2.0));
965    }
966}
grafeo_adapters/plugins/algorithms/shortest_path.rs

grafeo_adapters/plugins/algorithms/
shortest_path.rs
