use std::collections::HashMap;
use std::hash::Hash;
use crate::algo::{BoundedMeasure, NegativeCycle};
use crate::visit::{
EdgeRef, GraphProp, IntoEdgeReferences, IntoNodeIdentifiers, NodeCompactIndexable,
};
#[allow(clippy::type_complexity, clippy::needless_range_loop)]
pub fn floyd_warshall<G, F, K>(
graph: G,
mut edge_cost: F,
) -> Result<HashMap<(G::NodeId, G::NodeId), K>, NegativeCycle>
where
G: NodeCompactIndexable + IntoEdgeReferences + IntoNodeIdentifiers + GraphProp,
G::NodeId: Eq + Hash,
F: FnMut(G::EdgeRef) -> K,
K: BoundedMeasure + Copy,
{
let num_of_nodes = graph.node_count();
let mut dist = vec![vec![K::max(); num_of_nodes]; num_of_nodes];
for edge in graph.edge_references() {
dist[graph.to_index(edge.source())][graph.to_index(edge.target())] = edge_cost(edge);
if !graph.is_directed() {
dist[graph.to_index(edge.target())][graph.to_index(edge.source())] = edge_cost(edge);
}
}
for node in graph.node_identifiers() {
dist[graph.to_index(node)][graph.to_index(node)] = K::default();
}
for k in 0..num_of_nodes {
for i in 0..num_of_nodes {
for j in 0..num_of_nodes {
let (result, overflow) = dist[i][k].overflowing_add(dist[k][j]);
if !overflow && dist[i][j] > result {
dist[i][j] = result;
}
}
}
}
for i in 0..num_of_nodes {
if dist[i][i] < K::default() {
return Err(NegativeCycle(()));
}
}
let mut distance_map: HashMap<(G::NodeId, G::NodeId), K> =
HashMap::with_capacity(num_of_nodes * num_of_nodes);
for i in 0..num_of_nodes {
for j in 0..num_of_nodes {
distance_map.insert((graph.from_index(i), graph.from_index(j)), dist[i][j]);
}
}
Ok(distance_map)
}