floyd_warshall/
lib.rs

1//! This crate contains an implementation of the Floyd-Warshall algorithm to solve the all-pairs-shortest-paths problem in undirected graphs.
2
3#![deny(missing_docs)]
4#![feature(conservative_impl_trait)]
5
6extern crate petgraph;
7
8#[cfg(test)]
9extern crate rand;
10
11#[cfg(test)]
12#[macro_use]
13extern crate text_io;
14
15#[cfg(test)]
16mod tests;
17
18mod matrices;
19pub use matrices::*;
20
21use petgraph::graph::NodeIndex;
22use petgraph::visit::NodeRef;
23use petgraph::visit::Data;
24use petgraph::visit::GraphBase;
25use petgraph::visit::NodeCount;
26use petgraph::visit::IntoNodeIdentifiers;
27use petgraph::visit::IntoNodeReferences;
28use petgraph::visit::IntoEdgeReferences;
29use petgraph::visit::EdgeRef;
30use petgraph::visit::GraphProp;
31
32/// This function computes a distance matrix containing the shortest paths between every two nodes in the graph.
33/// By using the Floyd-Warshall algorithm, this is computed in **O(V^(3))** runtime.
34pub fn floyd_warshall<G>(g: G) -> PathMatrix<G::NodeWeight>
35where
36    G: Data
37        + GraphBase<NodeId = NodeIndex>
38        + NodeCount
39        + IntoNodeIdentifiers<NodeId = NodeIndex>
40        + IntoNodeReferences
41        + IntoEdgeReferences
42        + GraphProp,
43    G::NodeWeight: Clone,
44    G::EdgeWeight: Clone + Into<usize>,
45{
46    // We currently only support directed graphs.
47    assert!(!g.is_directed());
48
49    let mut m = PathMatrix::new(g.node_count());
50
51    // Each node has a distance of 0 to itself.
52    // Note, that this sets the distance of every node to itself to 0, due to the matrix representation.
53    m.set_path_len(0, 0, 0);
54
55    // Update the matrix to represent the actual edges in the graph.
56    for e in g.edge_references() {
57        let n1 = e.source().index();
58        let n2 = e.target().index();
59        let w: G::EdgeWeight = e.weight().clone();
60        let w: usize = w.into();
61        m.set_path_len(n1, n2, w);
62    }
63
64    // k is the "intermediate" node which is currently considered.
65    for k in g.node_references() {
66        let kw = k.weight();
67        let k = k.id().index();
68
69        // For every pair (n1, n2) of two disjunct nodes in the graph check, if the path over k is shorter than the previously found one.
70        for n1 in g.node_identifiers() {
71            let n1 = n1.index();
72
73            for n2 in g.node_identifiers() {
74                let n2 = n2.index();
75
76                // No need to do this for identical nodes.
77                if n1 == n2 {
78                    continue;
79                }
80
81                // No need to do this for both triangles in the matrix.
82                if n1 > n2 {
83                    continue;
84                }
85
86                // No need to do this for k == n1 or k == n2
87                if n1 == k || n2 == k {
88                    continue;
89                }
90
91                // These are the two options in this round to reach from node 1 to node 2:
92                // - v1, which is (if it exists) the saved path from n1 to n2, which is eiter a direct edge or a path using any intermediate nodes less than k.
93                let mut v1 = None;
94                if m.does_path_exist(n1, n2) {
95                    v1 = Some(m.get_path_len(n1, n2));
96                }
97
98                // - v2, which is the path from node 1 to node k to node 2 (if such a path exists, which means, that k is reachable from n1 and n2 is reachable from k).
99                let v2_exists = m.does_path_exist(n1, k);
100                let v2_exists = v2_exists && m.does_path_exist(k, n2);
101
102                let mut v2 = None;
103                if v2_exists {
104                    let part1 = m.get_path_len(n1, k);
105                    let part2 = m.get_path_len(k, n2);
106
107                    // .saturating_add is a relict of a time, when a path was usize::MAX as a sign for "there is no path here".
108                    // But as any other .add doesn't make any more sense, it will stay.
109                    v2 = Some(part1.saturating_add(part2));
110                }
111
112                // Whichever of these is minimal, can be used to reach from node 1 to node 2.
113                if v2.is_some() && (v1.is_none() || v2.unwrap() < v1.unwrap()) {
114                    let v2 = v2.unwrap();
115
116                    // Update the matrix to the minimum of these two.
117                    m.set_path_len(n1, n2, v2);
118
119                    // TODO: reuse vector here.
120                    let mut v: Vec<G::NodeWeight> = Vec::new();
121
122                    // Reverse path, if n1 < k or k < n2 not fulfilled:
123                    if n1 <= k {
124                        v.extend(m.get_path_iter(n1, k).cloned());
125                    } else {
126                        v.extend(m.get_path_iter(n1, k).rev().cloned());
127                    }
128
129                    // Push k in the middle of the path here.
130                    v.push(kw.clone());
131
132                    if k <= n2 {
133                        v.extend(m.get_path_iter(k, n2).cloned());
134                    } else {
135                        v.extend(m.get_path_iter(k, n2).rev().cloned());
136                    }
137
138                    // Save the path as new optimal path from node 1 to node 2.
139                    m.get_path_mut(n1, n2).set_vector(v);
140                }
141            }
142        }
143    }
144
145    m
146}
floyd_warshall/lib.rs

floyd_warshall/
lib.rs
