//! Floyd-Warshall algorithm.
use crate::result::FloydWarshallResult;
use safe_graph::{Graph, NodeTrait};
use num_traits::Num;
use std::clone::Clone;
use std::cmp::Ord;
use std::cmp::Ordering::{Greater, Less};
use std::cmp::PartialOrd;
/// A trait group for `FloydWarshall`'s weighted edges.
pub trait FloydWarshallTrait: Copy + Num + PartialOrd {}
/// Implement the `FloydWarshallTrait` for all types satisfying bounds.
impl<F> FloydWarshallTrait for F where F: Copy + Num + PartialOrd {}
/// Floyd-Warshall algorithm structure.
///
/// # `FloydWarshall` algorithm is parameterized over:
///
/// - Number type `F` giving a weights to edges.
pub struct FloydWarshall<F: FloydWarshallTrait> {
/// Operator to be used for weighted edges.
op: Box<Fn(F, F) -> F>,
/// Comparison to be used for weighted paths to determine if a newly tested path through `k`
/// should be added or not.
///
/// # Examples
///
/// ```
/// use std::cmp::Ordering::{Greater, Less};
/// use std::cmp::PartialOrd;
///
/// let cmp: Box<Fn(f32, f32) -> bool> = Box::new(|x: f32, y: f32| x.partial_cmp(&y)
/// .unwrap_or(Greater) == Less);
///
/// let new_weight = 4.2;
/// let old_weight = 10.1;
///
/// if cmp(new_weight, old_weight) {
/// // Use the new weight and path through `k`.
/// }
/// ```
cmp: Box<Fn(F, F) -> bool>,
/// Discard loops (e.g. edges starting and ending in the same node) from calculation.
discard_loops: bool,
}
impl<F: FloydWarshallTrait> FloydWarshall<F> {
/// Create a new instance of FloydWarshall structure with default settings.
///
/// # Examples
///
/// ```
/// use floyd_warshall_alg::FloydWarshall;
///
/// let alg: FloydWarshall<f32> = FloydWarshall::new();
/// ```
pub fn new() -> Self {
// Initialize defaults.
let add = Box::new(|x: F, y: F| x + y);
let sharp_less = Box::new(|x: F, y: F| x.partial_cmp(&y).unwrap_or(Greater) == Less);
Self {
op: add,
cmp: sharp_less,
discard_loops: true,
}
}
/// Create a new instance of FloydWarshall structure with customized settings.
///
/// You can set:
/// - the `op` (operator) to be used for weighted edges
/// - the `cmp` (comparison) to be used for weighted paths
///
/// # Examples
///
/// ```
/// use floyd_warshall_alg::FloydWarshall;
/// use std::cmp::Ordering::{Greater, Less};
///
/// let mul = Box::new(|x: f32, y: f32| x * y);
/// let sharp_greater = Box::new(|x: f32, y: f32| x.partial_cmp(&y).unwrap_or(Less) == Greater);
///
/// let alg: FloydWarshall<f32> = FloydWarshall::new_customized(mul, sharp_greater);
/// ```
pub fn new_customized(op: Box<Fn(F, F) -> F>, cmp: Box<Fn(F, F) -> bool>) -> Self {
Self::new_fully_customized(op, cmp, true)
}
/// Create a new instance of FloydWarshall structure with customized settings.
///
/// You can set:
/// - the `op` (operator) to be used for weighted edges
/// - the `cmp` (comparison) to be used for weighted paths
/// - the `discard_loops` to discard loops (e.g. edges starting and ending in the same node)
/// from calculation.
///
/// # Examples
///
/// ```
/// use floyd_warshall_alg::FloydWarshall;
/// use std::cmp::Ordering::{Greater, Less};
///
/// let mul = Box::new(|x: f32, y: f32| x * y);
/// let sharp_greater = Box::new(|x: f32, y: f32| x.partial_cmp(&y).unwrap_or(Less) == Greater);
/// let discard_loops = false;
///
/// let alg: FloydWarshall<f32> = FloydWarshall::new_customized(mul, sharp_greater);
pub fn new_fully_customized(
op: Box<Fn(F, F) -> F>,
cmp: Box<Fn(F, F) -> bool>,
discard_loops: bool,
) -> Self {
Self {
op,
cmp,
discard_loops,
}
}
/// Find all the shortest paths (or best rated paths based on algorithm customized settings).
///
/// The result of type FloydWarshallResult holds both:
/// - best rates for all possible paths
/// - next node on the best rated (shortest) path for each possible path
///
/// # Method is parameterized over:
///
/// - Node index / label `N`.
/// - Number type `E` giving a weight to edges.
pub fn find_paths<N>(&self, graph: &Graph<N, F>) -> FloydWarshallResult<N, F>
where
N: NodeTrait,
{
let mut path: Graph<N, F> = graph.clone();
let mut next: Graph<N, N> = Graph::with_capacity(graph.node_count(), graph.edge_count());
// Initialize next steps of each edge existing in `graph` with its end node.
for (a, b, _) in graph.all_edges() {
next.add_edge(a, b, b);
}
// `k` is the "intermediate" node which is currently considered.
for k in graph.nodes() {
// `i` is a starting node of the path we try to optimize.
for i in graph.nodes() {
// `j` is an end node of the path we try to optimize.
for j in graph.nodes() {
// Skip calculation for loops if requested.
if self.discard_loops && !Self::unique(vec![k, i, j]) {
continue;
}
// Calculation of a new weight of the path from `i` to `j` through `k`.
let left_operand = path.edge_weight(i, k);
let right_operand = path.edge_weight(k, j);
// There's nothing to calculate if the left `(i, k)` or right `(k, j)` path misses.
if left_operand.is_none() || right_operand.is_none() {
continue;
}
// It is safe to unwrap the operands now.
let left_operand = left_operand.unwrap();
let right_operand = right_operand.unwrap();
// Use the weight operator. It can be customized.
let new_weight = (self.op)(*left_operand, *right_operand);
// The `(i, j)` path already exists.
if let Some(&old_weight) = path.edge_weight(i, j) {
// Use the comparison. It can be customized.
if (self.cmp)(new_weight, old_weight) {
path.add_edge(i, j, new_weight);
// The algorithm invariants guarantee the edge exists.
let direction = next.edge_weight(i, k).unwrap();
next.add_edge(i, j, *direction);
}
} else {
// The path was missing so add a new one.
path.add_edge(i, j, new_weight);
// The algorithm invariants guarantee the edge exists.
let direction = next.edge_weight(i, k).unwrap();
next.add_edge(i, j, *direction);
}
}
}
}
FloydWarshallResult::new(path, next)
}
/// Are elements unique (no duplicates present).
fn unique<T: Ord>(mut elements: Vec<T>) -> bool {
let length = elements.len();
Self::dedup(&mut elements);
elements.len() == length
}
/// De-duplicate vector elements.
fn dedup<T: Ord>(elements: &mut Vec<T>) {
// `sort_unstable` may not preserve the order of equal elements, but it is faster and less
// memory consuming algorithm.
elements.sort();
elements.dedup();
}
}
#[cfg(test)]
mod tests {
use crate::floyd_warshall::FloydWarshall;
use safe_graph::Graph;
use std::cmp::Ordering::{Greater, Less};
#[test]
fn new() {
let _alg: FloydWarshall<f32> = FloydWarshall::new();
}
#[test]
fn new_customized() {
let mul = Box::new(|x: f32, y: f32| x * y);
let sharp_greater = Box::new(|x: f32, y: f32| x.partial_cmp(&y).unwrap_or(Less) == Greater);
let _alg: FloydWarshall<f32> = FloydWarshall::new_customized(mul, sharp_greater);
}
#[test]
fn new_fully_customized() {
let mul = Box::new(|x: f32, y: f32| x * y);
let sharp_less = Box::new(|x: f32, y: f32| x.partial_cmp(&y).unwrap_or(Greater) == Less);
let discard_loops = false;
let _alg: FloydWarshall<f32> =
FloydWarshall::new_fully_customized(mul, sharp_less, discard_loops);
}
#[test]
fn find_paths() {
let alg: FloydWarshall<f32> = FloydWarshall::new();
let w_a_b = 0.12;
let w_a_c = 1.99;
let w_b_c = 3.0;
let w_a_d = 2.1;
let w_a_e = 0.9;
let w_a_f = 4.44;
let w_a_g = 0.8;
let w_g_f = 0.6;
let w_a_h = 8.8;
let w_f_h = 1.0;
let graph = Graph::<_, _>::from_edges(&[
("a", "b", w_a_b),
("a", "c", w_a_c),
("b", "c", w_b_c),
("a", "d", w_a_d),
("a", "e", w_a_e),
("a", "f", w_a_f),
("a", "g", w_a_g),
("g", "f", w_g_f),
("a", "h", w_a_h),
("f", "h", w_f_h),
]);
let result = alg.find_paths(&graph);
let path = result.path;
let next = result.next;
// Test that the initial `(a, b)` edge is still the shortest path.
assert_eq!(path.edge_weight("a", "b"), Some(&w_a_b));
assert_eq!(next.edge_weight("a", "b"), Some(&"b"));
// Test that the initial `(a, c)` edge is still the shortest path.
assert_eq!(path.edge_weight("a", "c"), Some(&w_a_c));
assert_eq!(next.edge_weight("a", "c"), Some(&"c"));
// Test that a shorter path was found for the `(a, f)` and it is through `g`.
assert_eq!(path.edge_weight("a", "f"), Some(&(w_a_g + w_g_f)));
assert_eq!(next.edge_weight("a", "f"), Some(&"g"));
assert_eq!(next.edge_weight("g", "f"), Some(&"f"));
// Test that a shorter path was found for the `(a, f)` and it is through `g` and `f`.
assert_eq!(path.edge_weight("a", "h"), Some(&(w_a_g + w_g_f + w_f_h)));
assert_eq!(next.edge_weight("a", "h"), Some(&"g"));
assert_eq!(next.edge_weight("g", "h"), Some(&"f"));
assert_eq!(next.edge_weight("f", "h"), Some(&"h"));
}
}