Function bevy_internal::utils::petgraph::algo::floyd_warshall

pub fn floyd_warshall<G, F, K>(
    graph: G,
    edge_cost: F
) -> Result<HashMap<(<G as GraphBase>::NodeId, <G as GraphBase>::NodeId), K>, NegativeCycle>
where
    G: NodeCompactIndexable + IntoEdgeReferences + IntoNodeIdentifiers + GraphProp,
    <G as GraphBase>::NodeId: Eq + Hash,
    F: FnMut(<G as IntoEdgeReferences>::EdgeRef) -> K,
    K: BoundedMeasure + Copy,

[Generic] Floyd–Warshall algorithm is an algorithm for all pairs shortest path problem

Compute shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles)

Arguments

• graph: graph with no negative cycle
• edge_cost: closure that returns cost of a particular edge

Returns

• Ok: (if graph contains no negative cycle) a hashmap containing all pairs shortest paths
• Err: if graph contains negative cycle.

Examples

use petgraph::{prelude::*, Graph, Directed};
use petgraph::algo::floyd_warshall;
use std::collections::HashMap;

let mut graph: Graph<(), (), Directed> = Graph::new();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());

graph.extend_with_edges(&[
   (a, b),
   (a, c),
   (a, d),
   (b, c),
   (b, d),
   (c, d)
]);

let weight_map: HashMap<(NodeIndex, NodeIndex), i32> = [
   ((a, a), 0), ((a, b), 1), ((a, c), 4), ((a, d), 10),
   ((b, b), 0), ((b, c), 2), ((b, d), 2),
   ((c, c), 0), ((c, d), 2)
].iter().cloned().collect();
//     ----- b --------
//    |      ^         | 2
//    |    1 |    4    v
//  2 |      a ------> c
//    |   10 |         | 2
//    |      v         v
//     --->  d <-------

let inf = std::i32::MAX;
let expected_res: HashMap<(NodeIndex, NodeIndex), i32> = [
   ((a, a), 0), ((a, b), 1), ((a, c), 3), ((a, d), 3),
   ((b, a), inf), ((b, b), 0), ((b, c), 2), ((b, d), 2),
   ((c, a), inf), ((c, b), inf), ((c, c), 0), ((c, d), 2),
   ((d, a), inf), ((d, b), inf), ((d, c), inf), ((d, d), 0),
].iter().cloned().collect();


let res = floyd_warshall(&graph, |edge| {
    if let Some(weight) = weight_map.get(&(edge.source(), edge.target())) {
        *weight
    } else {
        inf
    }
}).unwrap();

let nodes = [a, b, c, d];
for node1 in &nodes {
    for node2 in &nodes {
        assert_eq!(res.get(&(*node1, *node2)).unwrap(), expected_res.get(&(*node1, *node2)).unwrap());
    }
}