weavatrix_graph/algo/
auto.rs

1use super::{AllPairsShortestPaths, floyd_warshall_filtered, johnson_all_pairs_filtered};
2use crate::{IndexGraphView, Result};
3
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub enum AllPairsStrategy {
6    FloydWarshall,
7    Johnson,
8}
9
10#[derive(Debug, Clone)]
11pub struct AutoAllPairs<Node> {
12    strategy: AllPairsStrategy,
13    paths: AllPairsShortestPaths<Node>,
14}
15
16impl<Node> AutoAllPairs<Node> {
17    #[must_use]
18    pub const fn strategy(&self) -> AllPairsStrategy {
19        self.strategy
20    }
21
22    #[must_use]
23    pub const fn paths(&self) -> &AllPairsShortestPaths<Node> {
24        &self.paths
25    }
26
27    #[must_use]
28    pub fn into_paths(self) -> AllPairsShortestPaths<Node> {
29        self.paths
30    }
31}
32
33/// Selects Floyd-Warshall for small/dense graphs and Johnson for sparse graphs.
34///
35/// The weight callback is evaluated exactly once for every edge.
36///
37/// # Errors
38///
39/// Returns an error for arithmetic overflow or any selected negative cycle.
40pub fn all_pairs_auto<G, F>(graph: &G, edge_cost: F) -> Result<AutoAllPairs<G::Node>>
41where
42    G: IndexGraphView,
43    F: Fn(G::Edge) -> i64,
44{
45    all_pairs_auto_filtered(graph, |edge| Some(edge_cost(edge)))
46}
47
48/// Automatically selects an all-pairs algorithm over a filtered edge set.
49///
50/// The selected strategy is exposed in the result. Filtered weights are
51/// snapshotted once before selection.
52///
53/// # Errors
54///
55/// Returns an error for arithmetic overflow or any selected negative cycle.
56pub fn all_pairs_auto_filtered<G, F>(graph: &G, edge_cost: F) -> Result<AutoAllPairs<G::Node>>
57where
58    G: IndexGraphView,
59    F: Fn(G::Edge) -> Option<i64>,
60{
61    let mut weights = vec![None; graph.edge_bound()];
62    let mut selected_edges = 0_usize;
63    for edge in graph.edge_indices() {
64        let weight = edge_cost(edge);
65        selected_edges += usize::from(weight.is_some());
66        weights[G::edge_slot(edge)] = weight;
67    }
68    let strategy = select_strategy(graph.node_count(), selected_edges);
69    let paths = match strategy {
70        AllPairsStrategy::FloydWarshall => {
71            floyd_warshall_filtered(graph, |edge| weights[G::edge_slot(edge)])?
72        }
73        AllPairsStrategy::Johnson => {
74            johnson_all_pairs_filtered(graph, |edge| weights[G::edge_slot(edge)])?
75        }
76    };
77    Ok(AutoAllPairs { strategy, paths })
78}
79
80fn select_strategy(node_count: usize, edge_count: usize) -> AllPairsStrategy {
81    if node_count <= 64 {
82        return AllPairsStrategy::FloydWarshall;
83    }
84    let dense_threshold = node_count
85        .checked_mul(node_count)
86        .map_or(usize::MAX, |cells| cells / 8);
87    if edge_count >= dense_threshold {
88        AllPairsStrategy::FloydWarshall
89    } else {
90        AllPairsStrategy::Johnson
91    }
92}
weavatrix_graph/algo/auto.rs

weavatrix_graph/algo/
auto.rs
