1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

use itertools::Itertools;
use petgraph::graphmap::DiGraphMap;
use std::collections::BTreeMap;
use std::string::String;

/// Similar to [Python's networkx Floyd Warshall implementation](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html#networkx.algorithms.shortest_paths.dense.floyd_warshall). Performs all-pairs shortest paths against a graph and returns a mapping of the shortest paths
pub fn floyd_warshall(graph: &DiGraphMap<i32, f64>) -> Result<BTreeMap<(i32, i32), f64>, String> {
    // TODO: would be neat to use generics instead
    let mut mappings = BTreeMap::new();

    // initialize distances to self to 0
    for node in graph.nodes() {
        mappings.insert((node, node), 0.);
    }

    // add existing edges
    for (source, target, weight) in graph.all_edges() {
        mappings.insert((source, target), *weight);
    }

    // get the smallest distances seen so far
    let triangles = graph.nodes().permutations(3);

    for triangle in triangles {
        let k = triangle[0];
        let i = triangle[1];
        let j = triangle[2];
        let position = (i, j);

        let d_ik = match mappings.get(&(i, k)) {
            Some(d) => d,
            None => &std::f64::MAX,
        };
        let d_kj = match mappings.get(&(k, j)) {
            Some(d) => d,
            None => &std::f64::MAX,
        };

        let d_current = {
            match mappings.get(&position) {
                Some(d) => d,
                None => &std::f64::MAX,
            }
        };

        let d_new = d_current.min(*d_ik + *d_kj);

        if i == j && d_new < 0. {
            let error_message = format!(
                "negative cycle found on node ID {}: {} + {} = {}",
                i, d_ik, d_kj, d_new
            );
            return Err(error_message);
        }

        mappings.insert(position, d_new);
    }

    Ok(mappings)
}