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 SSSP algorithm.
678static SSSP_PARAMS: OnceLock<Vec<ParameterDef>> = OnceLock::new();
679
680fn sssp_params() -> &'static [ParameterDef] {
681    SSSP_PARAMS.get_or_init(|| {
682        vec![
683            ParameterDef {
684                name: "source".to_string(),
685                description: "Source node name (string) or ID (integer as string)".to_string(),
686                param_type: ParameterType::String,
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/// SSSP (Single-Source Shortest Paths) algorithm for LDBC Graphanalytics compatibility.
702///
703/// Wraps Dijkstra's algorithm with string-based node name resolution.
704/// The source parameter is a string node name (looked up via "name" property)
705/// or falls back to integer ID parsing.
706pub struct SsspAlgorithm;
707
708impl GraphAlgorithm for SsspAlgorithm {
709    fn name(&self) -> &str {
710        "sssp"
711    }
712
713    fn description(&self) -> &str {
714        "Single-source shortest paths (Dijkstra) with string node name support"
715    }
716
717    fn parameters(&self) -> &[ParameterDef] {
718        sssp_params()
719    }
720
721    fn execute(&self, store: &LpgStore, params: &Parameters) -> Result<AlgorithmResult> {
722        let source_str = params
723            .get_string("source")
724            .ok_or_else(|| Error::InvalidValue("source parameter required".to_string()))?;
725
726        // Resolve source: try integer parse first, then name property lookup
727        let source = if let Ok(id) = source_str.parse::<u64>() {
728            NodeId::new(id)
729        } else {
730            let candidates = store.find_nodes_by_property("name", &Value::from(source_str));
731            match candidates.len() {
732                0 => {
733                    return Err(Error::InvalidValue(format!(
734                        "No node found with name '{source_str}'"
735                    )));
736                }
737                1 => candidates[0],
738                _ => {
739                    return Err(Error::InvalidValue(format!(
740                        "Multiple nodes found with name '{source_str}', use node ID instead"
741                    )));
742                }
743            }
744        };
745
746        let weight_prop = params.get_string("weight");
747        let dijkstra_result = dijkstra(store, source, weight_prop);
748
749        let mut result = AlgorithmResult::new(vec!["node_id".to_string(), "distance".to_string()]);
750
751        for (node, distance) in dijkstra_result.distances {
752            result.add_row(vec![Value::Int64(node.0 as i64), Value::Float64(distance)]);
753        }
754
755        Ok(result)
756    }
757}
758
759/// Static parameter definitions for Bellman-Ford algorithm.
760static BELLMAN_FORD_PARAMS: OnceLock<Vec<ParameterDef>> = OnceLock::new();
761
762fn bellman_ford_params() -> &'static [ParameterDef] {
763    BELLMAN_FORD_PARAMS.get_or_init(|| {
764        vec![
765            ParameterDef {
766                name: "source".to_string(),
767                description: "Source node ID".to_string(),
768                param_type: ParameterType::NodeId,
769                required: true,
770                default: None,
771            },
772            ParameterDef {
773                name: "weight".to_string(),
774                description: "Edge property name for weights (default: 1.0)".to_string(),
775                param_type: ParameterType::String,
776                required: false,
777                default: None,
778            },
779        ]
780    })
781}
782
783/// Bellman-Ford algorithm wrapper for the plugin registry.
784pub struct BellmanFordAlgorithm;
785
786impl GraphAlgorithm for BellmanFordAlgorithm {
787    fn name(&self) -> &str {
788        "bellman_ford"
789    }
790
791    fn description(&self) -> &str {
792        "Bellman-Ford shortest path algorithm (handles negative weights)"
793    }
794
795    fn parameters(&self) -> &[ParameterDef] {
796        bellman_ford_params()
797    }
798
799    fn execute(&self, store: &LpgStore, params: &Parameters) -> Result<AlgorithmResult> {
800        let source_id = params
801            .get_int("source")
802            .ok_or_else(|| Error::InvalidValue("source parameter required".to_string()))?;
803
804        let source = NodeId::new(source_id as u64);
805        let weight_prop = params.get_string("weight");
806
807        let bf_result = bellman_ford(store, source, weight_prop.as_deref());
808
809        let mut result = AlgorithmResult::new(vec![
810            "node_id".to_string(),
811            "distance".to_string(),
812            "has_negative_cycle".to_string(),
813        ]);
814
815        for (node, distance) in bf_result.distances {
816            result.add_row(vec![
817                Value::Int64(node.0 as i64),
818                Value::Float64(distance),
819                Value::Bool(bf_result.has_negative_cycle),
820            ]);
821        }
822
823        Ok(result)
824    }
825}
826
827/// Static parameter definitions for Floyd-Warshall algorithm.
828static FLOYD_WARSHALL_PARAMS: OnceLock<Vec<ParameterDef>> = OnceLock::new();
829
830fn floyd_warshall_params() -> &'static [ParameterDef] {
831    FLOYD_WARSHALL_PARAMS.get_or_init(|| {
832        vec![ParameterDef {
833            name: "weight".to_string(),
834            description: "Edge property name for weights (default: 1.0)".to_string(),
835            param_type: ParameterType::String,
836            required: false,
837            default: None,
838        }]
839    })
840}
841
842/// Floyd-Warshall algorithm wrapper for the plugin registry.
843pub struct FloydWarshallAlgorithm;
844
845impl GraphAlgorithm for FloydWarshallAlgorithm {
846    fn name(&self) -> &str {
847        "floyd_warshall"
848    }
849
850    fn description(&self) -> &str {
851        "Floyd-Warshall all-pairs shortest paths algorithm"
852    }
853
854    fn parameters(&self) -> &[ParameterDef] {
855        floyd_warshall_params()
856    }
857
858    fn execute(&self, store: &LpgStore, params: &Parameters) -> Result<AlgorithmResult> {
859        let weight_prop = params.get_string("weight");
860
861        let fw_result = floyd_warshall(store, weight_prop.as_deref());
862
863        let mut result = AlgorithmResult::new(vec![
864            "source".to_string(),
865            "target".to_string(),
866            "distance".to_string(),
867        ]);
868
869        // Output all pairs with finite distances
870        for (i, &from_node) in fw_result.index_to_node.iter().enumerate() {
871            for (j, &to_node) in fw_result.index_to_node.iter().enumerate() {
872                let dist = fw_result.distances[i][j];
873                if dist < f64::INFINITY {
874                    result.add_row(vec![
875                        Value::Int64(from_node.0 as i64),
876                        Value::Int64(to_node.0 as i64),
877                        Value::Float64(dist),
878                    ]);
879                }
880            }
881        }
882
883        Ok(result)
884    }
885}
886
887// ============================================================================
888// Tests
889// ============================================================================
890
891#[cfg(test)]
892mod tests {
893    use super::*;
894
895    fn create_weighted_graph() -> LpgStore {
896        let store = LpgStore::new();
897
898        // Create a weighted graph:
899        //   0 --2--> 1 --3--> 2
900        //   |        ^        |
901        //   4        1        1
902        //   v        |        v
903        //   3 -------+        4
904        //
905        // Shortest path from 0 to 2: 0 -> 3 -> 1 -> 2 (cost: 4+1+3 = 8)
906        // vs direct: 0 -> 1 -> 2 (cost: 2+3 = 5)
907        let n0 = store.create_node(&["Node"]);
908        let n1 = store.create_node(&["Node"]);
909        let n2 = store.create_node(&["Node"]);
910        let n3 = store.create_node(&["Node"]);
911        let n4 = store.create_node(&["Node"]);
912
913        // Create edges with weights
914        store.create_edge_with_props(n0, n1, "EDGE", [("weight", Value::Float64(2.0))]);
915        store.create_edge_with_props(n1, n2, "EDGE", [("weight", Value::Float64(3.0))]);
916        store.create_edge_with_props(n0, n3, "EDGE", [("weight", Value::Float64(4.0))]);
917        store.create_edge_with_props(n3, n1, "EDGE", [("weight", Value::Float64(1.0))]);
918        store.create_edge_with_props(n2, n4, "EDGE", [("weight", Value::Float64(1.0))]);
919
920        store
921    }
922
923    #[test]
924    fn test_dijkstra_basic() {
925        let store = create_weighted_graph();
926        let result = dijkstra(&store, NodeId::new(0), Some("weight"));
927
928        assert!(result.distances.contains_key(&NodeId::new(0)));
929        assert_eq!(result.distance_to(NodeId::new(0)), Some(0.0));
930        assert!(result.distances.contains_key(&NodeId::new(1)));
931        assert!(result.distances.contains_key(&NodeId::new(2)));
932    }
933
934    #[test]
935    fn test_dijkstra_path() {
936        let store = create_weighted_graph();
937        let result = dijkstra(&store, NodeId::new(0), Some("weight"));
938
939        let path = result.path_to(NodeId::new(0), NodeId::new(2));
940        assert!(path.is_some());
941
942        let path = path.unwrap();
943        assert_eq!(path[0], NodeId::new(0)); // Start
944        assert_eq!(*path.last().unwrap(), NodeId::new(2)); // End
945    }
946
947    #[test]
948    fn test_dijkstra_single_pair() {
949        let store = create_weighted_graph();
950        let result = dijkstra_path(&store, NodeId::new(0), NodeId::new(4), Some("weight"));
951
952        assert!(result.is_some());
953        let (distance, path) = result.unwrap();
954        assert!(distance > 0.0);
955        assert_eq!(path[0], NodeId::new(0));
956        assert_eq!(*path.last().unwrap(), NodeId::new(4));
957    }
958
959    #[test]
960    fn test_dijkstra_unreachable() {
961        let store = LpgStore::new();
962        let n0 = store.create_node(&["Node"]);
963        let _n1 = store.create_node(&["Node"]); // Disconnected
964
965        let result = dijkstra_path(&store, n0, NodeId::new(1), None);
966        assert!(result.is_none());
967    }
968
969    #[test]
970    fn test_bellman_ford_basic() {
971        let store = create_weighted_graph();
972        let result = bellman_ford(&store, NodeId::new(0), Some("weight"));
973
974        assert!(!result.has_negative_cycle);
975        assert!(result.distances.contains_key(&NodeId::new(0)));
976        assert_eq!(*result.distances.get(&NodeId::new(0)).unwrap(), 0.0);
977    }
978
979    #[test]
980    fn test_floyd_warshall_basic() {
981        let store = create_weighted_graph();
982        let result = floyd_warshall(&store, Some("weight"));
983
984        // Self-distances should be 0
985        assert_eq!(result.distance(NodeId::new(0), NodeId::new(0)), Some(0.0));
986        assert_eq!(result.distance(NodeId::new(1), NodeId::new(1)), Some(0.0));
987
988        // Check some paths exist
989        assert!(result.distance(NodeId::new(0), NodeId::new(2)).is_some());
990    }
991
992    #[test]
993    fn test_floyd_warshall_path_reconstruction() {
994        let store = create_weighted_graph();
995        let result = floyd_warshall(&store, Some("weight"));
996
997        let path = result.path(NodeId::new(0), NodeId::new(2));
998        assert!(path.is_some());
999
1000        let path = path.unwrap();
1001        assert_eq!(path[0], NodeId::new(0));
1002        assert_eq!(*path.last().unwrap(), NodeId::new(2));
1003    }
1004
1005    #[test]
1006    fn test_astar_basic() {
1007        let store = create_weighted_graph();
1008
1009        // Simple heuristic: always return 0 (degenerates to Dijkstra)
1010        let heuristic = |_: NodeId| 0.0;
1011
1012        let result = astar(
1013            &store,
1014            NodeId::new(0),
1015            NodeId::new(4),
1016            Some("weight"),
1017            heuristic,
1018        );
1019        assert!(result.is_some());
1020
1021        let (distance, path) = result.unwrap();
1022        assert!(distance > 0.0);
1023        assert_eq!(path[0], NodeId::new(0));
1024        assert_eq!(*path.last().unwrap(), NodeId::new(4));
1025    }
1026
1027    #[test]
1028    fn test_dijkstra_nonexistent_source() {
1029        let store = LpgStore::new();
1030        let result = dijkstra(&store, NodeId::new(999), None);
1031        assert!(result.distances.is_empty());
1032    }
1033
1034    #[test]
1035    fn test_unweighted_defaults() {
1036        let store = LpgStore::new();
1037        let n0 = store.create_node(&["Node"]);
1038        let n1 = store.create_node(&["Node"]);
1039        let n2 = store.create_node(&["Node"]);
1040        store.create_edge(n0, n1, "EDGE");
1041        store.create_edge(n1, n2, "EDGE");
1042
1043        // Without weight property, should default to 1.0 per edge
1044        let result = dijkstra(&store, n0, None);
1045        assert_eq!(result.distance_to(n1), Some(1.0));
1046        assert_eq!(result.distance_to(n2), Some(2.0));
1047    }
1048
1049    #[test]
1050    fn test_sssp_with_named_nodes() {
1051        let store = LpgStore::new();
1052        let n0 = store.create_node(&["Node"]);
1053        let n1 = store.create_node(&["Node"]);
1054        let n2 = store.create_node(&["Node"]);
1055        store.set_node_property(n0, "name", Value::from("alice"));
1056        store.set_node_property(n1, "name", Value::from("bob"));
1057        store.set_node_property(n2, "name", Value::from("carol"));
1058        store.create_edge_with_props(n0, n1, "KNOWS", [("weight", Value::Float64(1.0))]);
1059        store.create_edge_with_props(n1, n2, "KNOWS", [("weight", Value::Float64(2.0))]);
1060
1061        let mut params = Parameters::new();
1062        params.set_string("source", "alice");
1063        params.set_string("weight", "weight");
1064
1065        let result = SsspAlgorithm.execute(&store, &params).unwrap();
1066        assert_eq!(result.columns, vec!["node_id", "distance"]);
1067        assert_eq!(result.row_count(), 3); // alice, bob, carol
1068    }
1069
1070    #[test]
1071    fn test_sssp_with_numeric_source() {
1072        let store = LpgStore::new();
1073        let n0 = store.create_node(&["Node"]);
1074        let n1 = store.create_node(&["Node"]);
1075        store.create_edge(n0, n1, "EDGE");
1076
1077        let mut params = Parameters::new();
1078        params.set_string("source", n0.0.to_string());
1079
1080        let result = SsspAlgorithm.execute(&store, &params).unwrap();
1081        assert_eq!(result.row_count(), 2);
1082    }
1083
1084    #[test]
1085    fn test_sssp_nonexistent_name() {
1086        let store = LpgStore::new();
1087        let _n0 = store.create_node(&["Node"]);
1088
1089        let mut params = Parameters::new();
1090        params.set_string("source", "nonexistent");
1091
1092        let result = SsspAlgorithm.execute(&store, &params);
1093        assert!(result.is_err());
1094    }
1095}
grafeo_adapters/plugins/algorithms/shortest_path.rs

grafeo_adapters/plugins/algorithms/
shortest_path.rs
