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

graphos_adapters/plugins/algorithms/
shortest_path.rs
