petgraph/algo/
floyd_warshall.rs

1use alloc::{vec, vec::Vec};
2use core::hash::Hash;
3
4use hashbrown::HashMap;
5
6use crate::algo::{BoundedMeasure, NegativeCycle};
7use crate::visit::{
8    EdgeRef, GraphProp, IntoEdgeReferences, IntoNodeIdentifiers, NodeCompactIndexable,
9};
10
11#[allow(clippy::type_complexity, clippy::needless_range_loop)]
12/// \[Generic\] [Floyd–Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) is an algorithm for all pairs shortest path problem
13///
14/// Compute the length of each shortest path in a weighted graph with positive or negative edge weights (but with no negative cycles).
15///
16/// # Arguments
17/// * `graph`: graph with no negative cycle.
18/// * `edge_cost`: closure that returns cost of a particular edge.
19///
20/// # Returns
21/// * `Ok`: (if graph contains no negative cycle) a [`struct@hashbrown::HashMap`] containing all pairs shortest paths.
22/// * `Err`: if graph contains negative cycle.
23///
24/// # Complexity
25/// * Time complexity: **O(|V|³)**.
26/// * Auxiliary space: **O(|V|²)**.
27///
28/// where **|V|** is the number of nodes.
29///
30/// **Note**: If the graph is sparse (the number of edges is quite small),
31/// consider using [`johnson`](fn@crate::algo::johnson)'s algorithm, which is likely to show better performance in such cases.
32///
33/// # Examples
34/// ```rust
35/// use petgraph::{prelude::*, Graph, Directed};
36/// use petgraph::algo::floyd_warshall;
37/// use hashbrown::HashMap;
38///
39/// let mut graph: Graph<(), (), Directed> = Graph::new();
40/// let a = graph.add_node(());
41/// let b = graph.add_node(());
42/// let c = graph.add_node(());
43/// let d = graph.add_node(());
44///
45/// graph.extend_with_edges(&[
46///    (a, b),
47///    (a, c),
48///    (a, d),
49///    (b, c),
50///    (b, d),
51///    (c, d)
52/// ]);
53///
54/// let weight_map: HashMap<(NodeIndex, NodeIndex), i32> = [
55///    ((a, a), 0), ((a, b), 1), ((a, c), 4), ((a, d), 10),
56///    ((b, b), 0), ((b, c), 2), ((b, d), 2),
57///    ((c, c), 0), ((c, d), 2)
58/// ].iter().cloned().collect();
59/// //     ----- b --------
60/// //    |      ^         | 2
61/// //    |    1 |    4    v
62/// //  2 |      a ------> c
63/// //    |   10 |         | 2
64/// //    |      v         v
65/// //     --->  d <-------
66///
67/// let inf = core::i32::MAX;
68/// let expected_res: HashMap<(NodeIndex, NodeIndex), i32> = [
69///    ((a, a), 0), ((a, b), 1), ((a, c), 3), ((a, d), 3),
70///    ((b, a), inf), ((b, b), 0), ((b, c), 2), ((b, d), 2),
71///    ((c, a), inf), ((c, b), inf), ((c, c), 0), ((c, d), 2),
72///    ((d, a), inf), ((d, b), inf), ((d, c), inf), ((d, d), 0),
73/// ].iter().cloned().collect();
74///
75///
76/// let res = floyd_warshall(&graph, |edge| {
77///     if let Some(weight) = weight_map.get(&(edge.source(), edge.target())) {
78///         *weight
79///     } else {
80///         inf
81///     }
82/// }).unwrap();
83///
84/// let nodes = [a, b, c, d];
85/// for node1 in &nodes {
86///     for node2 in &nodes {
87///         assert_eq!(res.get(&(*node1, *node2)).unwrap(), expected_res.get(&(*node1, *node2)).unwrap());
88///     }
89/// }
90/// ```
91pub fn floyd_warshall<G, F, K>(
92    graph: G,
93    edge_cost: F,
94) -> Result<HashMap<(G::NodeId, G::NodeId), K>, NegativeCycle>
95where
96    G: NodeCompactIndexable + IntoEdgeReferences + IntoNodeIdentifiers + GraphProp,
97    G::NodeId: Eq + Hash,
98    F: FnMut(G::EdgeRef) -> K,
99    K: BoundedMeasure + Copy,
100{
101    let num_of_nodes = graph.node_count();
102
103    // |V|x|V| matrix
104    let mut m_dist = Some(vec![vec![K::max(); num_of_nodes]; num_of_nodes]);
105
106    _floyd_warshall_path(graph, edge_cost, &mut m_dist, &mut None)?;
107
108    let mut distance_map: HashMap<(G::NodeId, G::NodeId), K> =
109        HashMap::with_capacity(num_of_nodes * num_of_nodes);
110
111    if let Some(dist) = m_dist {
112        for i in 0..num_of_nodes {
113            for j in 0..num_of_nodes {
114                distance_map.insert((graph.from_index(i), graph.from_index(j)), dist[i][j]);
115            }
116        }
117    }
118
119    Ok(distance_map)
120}
121
122#[allow(clippy::type_complexity, clippy::needless_range_loop)]
123/// \[Generic\] [Floyd–Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) is an algorithm for all pairs shortest path problem
124///
125/// Compute all pairs shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
126/// Returns HashMap of shortest path lengths. Additionally, returns HashMap of intermediate nodes along shortest path for indicated edges.
127///
128/// # Arguments
129/// * `graph`: graph with no negative cycle
130/// * `edge_cost`: closure that returns cost of a particular edge
131///
132/// # Returns
133/// * `Ok`: (if graph contains no negative cycle) a hashmap containing all pairs shortest path distances and a hashmap for all pairs shortest paths
134/// * `Err`: if graph contains negative cycle.
135///
136/// # Complexity
137/// * Time complexity: **O(|V|³)**
138/// * Auxiliary space: **O(|V|²)**
139///
140/// # Examples
141/// ```rust
142/// use petgraph::{prelude::*, Graph, Directed};
143/// use petgraph::algo::floyd_warshall::floyd_warshall_path;
144/// use std::collections::HashMap;
145///
146/// let mut graph: Graph<(), (), Directed> = Graph::new();
147/// let a = graph.add_node(());
148/// let b = graph.add_node(());
149/// let c = graph.add_node(());
150/// let d = graph.add_node(());
151///
152/// graph.extend_with_edges(&[
153///    (a, b),
154///    (a, c),
155///    (a, d),
156///    (b, c),
157///    (b, d),
158///    (c, d)
159/// ]);
160///
161/// let weight_map: HashMap<(NodeIndex, NodeIndex), i32> = [
162///    ((a, a), 0), ((a, b), 1), ((a, c), 4), ((a, d), 10),
163///    ((b, b), 0), ((b, c), 2), ((b, d), 2),
164///    ((c, c), 0), ((c, d), 2)
165/// ].iter().cloned().collect();
166/// //     ----- b --------
167/// //    |      ^         | 2
168/// //    |    1 |    4    v
169/// //  2 |      a ------> c
170/// //    |   10 |         | 2
171/// //    |      v         v
172/// //     --->  d <-------
173///
174/// let inf = std::i32::MAX;
175/// let expected_res: HashMap<(NodeIndex, NodeIndex), i32> = [
176///    ((a, a), 0), ((a, b), 1), ((a, c), 3), ((a, d), 3),
177///    ((b, a), inf), ((b, b), 0), ((b, c), 2), ((b, d), 2),
178///    ((c, a), inf), ((c, b), inf), ((c, c), 0), ((c, d), 2),
179///    ((d, a), inf), ((d, b), inf), ((d, c), inf), ((d, d), 0),
180/// ].iter().cloned().collect();
181///
182///
183/// let (res, prev) = floyd_warshall_path(&graph, |edge| {
184///     if let Some(weight) = weight_map.get(&(edge.source(), edge.target())) {
185///         *weight
186///     } else {
187///         inf
188///     }
189/// }).unwrap();
190///
191/// assert_eq!(prev[0][2], Some(1));
192///
193/// let nodes = [a, b, c, d];
194/// for node1 in &nodes {
195///     for node2 in &nodes {
196///         assert_eq!(res.get(&(*node1, *node2)).unwrap(), expected_res.get(&(*node1, *node2)).unwrap());
197///     }
198/// }
199///
200/// ```
201pub fn floyd_warshall_path<G, F, K>(
202    graph: G,
203    edge_cost: F,
204) -> Result<(HashMap<(G::NodeId, G::NodeId), K>, Vec<Vec<Option<usize>>>), NegativeCycle>
205where
206    G: NodeCompactIndexable + IntoEdgeReferences + IntoNodeIdentifiers + GraphProp,
207    G::NodeId: Eq + Hash,
208    F: FnMut(G::EdgeRef) -> K,
209    K: BoundedMeasure + Copy,
210{
211    let num_of_nodes = graph.node_count();
212
213    // |V|x|V| matrix
214    let mut m_dist = Some(vec![vec![K::max(); num_of_nodes]; num_of_nodes]);
215    // `prev[source][target]` holds the penultimate vertex on path from `source` to `target`, except `prev[source][source]`, which always stores `source`.
216    let mut m_prev = Some(vec![vec![None; num_of_nodes]; num_of_nodes]);
217
218    _floyd_warshall_path(graph, edge_cost, &mut m_dist, &mut m_prev)?;
219
220    let mut distance_map = HashMap::with_capacity(num_of_nodes * num_of_nodes);
221
222    if let Some(dist) = m_dist {
223        for i in 0..num_of_nodes {
224            for j in 0..num_of_nodes {
225                distance_map.insert((graph.from_index(i), graph.from_index(j)), dist[i][j]);
226            }
227        }
228    }
229
230    Ok((distance_map, m_prev.unwrap()))
231}
232
233/// Helper function to copy a value to a 2D array
234fn set_object<K: Clone>(m_dist: &mut Option<Vec<Vec<K>>>, i: usize, j: usize, value: K) {
235    if let Some(dist) = m_dist {
236        dist[i][j] = value;
237    }
238}
239
240/// Helper to check if the distance map is greater then a specific value
241fn is_greater<K: PartialOrd>(
242    m_dist: &mut Option<Vec<Vec<K>>>,
243    i: usize,
244    j: usize,
245    value: K,
246) -> bool {
247    if let Some(dist) = m_dist {
248        return dist[i][j] > value;
249    }
250    false
251}
252
253/// Helper that implements the floyd warshall routine, but paths are optional for memory overhead.
254fn _floyd_warshall_path<G, F, K>(
255    graph: G,
256    mut edge_cost: F,
257    m_dist: &mut Option<Vec<Vec<K>>>,
258    m_prev: &mut Option<Vec<Vec<Option<usize>>>>,
259) -> Result<(), NegativeCycle>
260where
261    G: NodeCompactIndexable + IntoEdgeReferences + IntoNodeIdentifiers + GraphProp,
262    G::NodeId: Eq + Hash,
263    F: FnMut(G::EdgeRef) -> K,
264    K: BoundedMeasure + Copy,
265{
266    let num_of_nodes = graph.node_count();
267
268    // Initialize distances and predecessors for edges
269    for edge in graph.edge_references() {
270        let source = graph.to_index(edge.source());
271        let target = graph.to_index(edge.target());
272        let cost = edge_cost(edge);
273        if is_greater(m_dist, source, target, cost) {
274            set_object(m_dist, source, target, cost);
275            set_object(m_prev, source, target, Some(source));
276
277            if !graph.is_directed() {
278                set_object(m_dist, target, source, cost);
279                set_object(m_prev, target, source, Some(target));
280            }
281        }
282    }
283
284    // Distance of each node to itself is the default value
285    for node in graph.node_identifiers() {
286        let index = graph.to_index(node);
287        set_object(m_dist, index, index, K::default());
288        set_object(m_prev, index, index, Some(index));
289    }
290
291    // Perform the Floyd-Warshall algorithm
292    for k in 0..num_of_nodes {
293        for i in 0..num_of_nodes {
294            for j in 0..num_of_nodes {
295                if let Some(dist) = m_dist {
296                    let (result, overflow) = dist[i][k].overflowing_add(dist[k][j]);
297                    if !overflow && dist[i][j] > result {
298                        dist[i][j] = result;
299                        if let Some(prev) = m_prev {
300                            prev[i][j] = prev[k][j];
301                        }
302                    }
303                }
304            }
305        }
306    }
307
308    // value less than 0(default value) indicates a negative cycle
309    for i in 0..num_of_nodes {
310        if let Some(dist) = m_dist {
311            if dist[i][i] < K::default() {
312                return Err(NegativeCycle(()));
313            }
314        }
315    }
316    Ok(())
317}
petgraph/algo/floyd_warshall.rs

petgraph/algo/
floyd_warshall.rs
