rustworkx_core/geometry/
greedy_routing.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13use std::hash::Hash;
14
15use petgraph::algo::Measure;
16use petgraph::visit::{
17    IntoEdges, IntoNodeIdentifiers, NodeCount, NodeIndexable, VisitMap, Visitable,
18};
19
20/// Error returned when a greedy routing fails.
21#[derive(Debug, PartialEq, Eq)]
22pub struct NodeNotReachedError;
23
24/// Returns the proportion of successful greedy routing paths between all pairs of nodes.
25///
26/// See [`greedy_routing`] for details on the greedy routing algorithm.
27///
28/// # Example
29/// ```rust
30///
31/// use rustworkx_core::petgraph;
32/// use rustworkx_core::geometry::{euclidean_distance, greedy_routing_success_rate};
33///
34/// let g = petgraph::graph::UnGraph::<i32, ()>::from_edges(&[
35///     (0, 1), (1, 2), (0, 3), (3, 4), (1, 4), (4, 5)
36/// ]);
37///
38/// fn distance2d<G>(graph: &G, positions: &Vec<[f64; 2]>, u: G::NodeId, v: G::NodeId) -> f64 where G: petgraph::visit::NodeIndexable {
39///     euclidean_distance(&positions[graph.to_index(u)], &positions[graph.to_index(v)]).unwrap()
40/// }
41///
42/// let positions = vec![[1., 0.] , [2., 3.], [3., 0.], [1., -1.], [2., -1.], [3., -1.]];
43/// let success_rate = greedy_routing_success_rate(&g, |u, v| {distance2d(&g, &positions, u, v)});
44/// assert!( (success_rate - 26./30.).abs() < 1e-15);
45/// ```
46pub fn greedy_routing_success_rate<G, F, K>(graph: G, distance: F) -> f64
47where
48    G: IntoEdges + NodeCount + NodeIndexable + IntoNodeIdentifiers + Visitable,
49    G::NodeId: Eq + Hash,
50    F: Fn(G::NodeId, G::NodeId) -> K,
51    K: Measure + Copy,
52{
53    let num_vertices = graph.node_count() as f64;
54    let num_successes = graph
55        .node_identifiers()
56        .flat_map(|u| graph.node_identifiers().map(move |v| (u, v)))
57        .map(|(u, v)| ((u != v) && greedy_routing(graph, u, v, &distance).is_ok()) as u32)
58        .sum::<u32>() as f64;
59    num_successes / (num_vertices * num_vertices - num_vertices)
60}
61
62/// Greedy routing shortest path algorithm.
63///
64/// Successively follows the neighbor closest to `destination` from `source` until `destination` is
65/// reached. The closest neighbor is the node that minimizes the `distance` function.
66///
67/// Returns the greedy path and the sum of the distances in the path. A [`NodeNotReachedError`] is
68/// returned if the greedy routing fails to reach `destination`.
69///
70/// # Example:
71/// ```rust
72///
73/// use rustworkx_core::petgraph;
74/// use rustworkx_core::geometry::{euclidean_distance, greedy_routing};
75///
76/// let g = petgraph::graph::UnGraph::<i32, ()>::from_edges(&[
77///     (0, 1), (1, 2), (2, 3), (1, 4), (4, 5), (2, 5), (5, 6)
78/// ]);
79///
80/// fn distance2d<G>(graph: &G, positions: &Vec<[f64; 2]>, u: G::NodeId, v: G::NodeId) -> f64 where G: petgraph::visit::NodeIndexable {
81///     euclidean_distance(&positions[graph.to_index(u)], &positions[graph.to_index(v)]).unwrap()
82/// }
83///
84/// let positions = vec![[0., 0.], [1., 0.] , [2., 0.], [2.5, 0.], [1., 1.], [2., 1.], [3., 1.]];
85/// let (path, dist) = greedy_routing(&g, 0.into(), 6.into(), |u, v| {distance2d(&g, &positions, u, v)}).unwrap();
86/// assert_eq!(path, vec![0.into(), 1.into(), 2.into(), 5.into(), 6.into()]);
87/// assert!( (dist - (1.+1.+1.+1.)).abs() < 1e-15 );
88/// ```
89///
90pub fn greedy_routing<G, F, K>(
91    graph: G,
92    source: G::NodeId,
93    destination: G::NodeId,
94    distance: F,
95) -> Result<(Vec<G::NodeId>, K), NodeNotReachedError>
96where
97    G: IntoEdges + NodeCount + NodeIndexable + Visitable,
98    G::NodeId: Eq + Hash,
99    F: Fn(G::NodeId, G::NodeId) -> K,
100    K: Measure + Copy,
101{
102    if source == destination {
103        return Ok((vec![source], distance(source, destination)));
104    }
105    let mut visitmap = graph.visit_map();
106    let mut path: Vec<G::NodeId> = vec![source];
107    let mut total_distance = K::default();
108
109    let mut current_vertex = source;
110    while current_vertex != destination {
111        if visitmap.is_visited(&current_vertex) {
112            return Err(NodeNotReachedError {});
113        }
114        visitmap.visit(current_vertex);
115
116        let mut min_distance = None;
117        let mut next = current_vertex;
118        for neighbor in graph.neighbors(current_vertex) {
119            let d = distance(neighbor, destination);
120            if min_distance.is_none() || d < min_distance.unwrap() {
121                next = neighbor;
122                min_distance = Some(d);
123            }
124        }
125        if min_distance.is_none() {
126            return Err(NodeNotReachedError {});
127        }
128        total_distance = total_distance + distance(current_vertex, next);
129        current_vertex = next;
130        path.push(current_vertex);
131    }
132    Ok((path, total_distance))
133}
134
135#[cfg(test)]
136mod tests {
137    use super::{NodeNotReachedError, greedy_routing, greedy_routing_success_rate};
138    use crate::geometry::distances;
139    use crate::petgraph::graph::UnGraph;
140    use petgraph::Graph;
141    use petgraph::visit::NodeIndexable;
142
143    fn distance1d<G>(graph: &G, positions: &[f64], u: G::NodeId, v: G::NodeId) -> f64
144    where
145        G: NodeIndexable,
146    {
147        distances::lp_distance(
148            &[positions[graph.to_index(u)]],
149            &[positions[graph.to_index(v)]],
150            1,
151        )
152        .unwrap()
153    }
154    fn distance2d<G>(graph: &G, positions: &[[f64; 2]], u: G::NodeId, v: G::NodeId) -> f64
155    where
156        G: NodeIndexable,
157    {
158        distances::euclidean_distance(&positions[graph.to_index(u)], &positions[graph.to_index(v)])
159            .unwrap()
160    }
161
162    #[test]
163    fn test_unreachable_destination_error() {
164        // Disconnected graph
165        let mut graph: UnGraph<(), ()> = Graph::with_capacity(4, 2);
166
167        let a = graph.add_node(());
168        let b = graph.add_node(());
169
170        let positions = vec![1., 2.];
171        assert_eq!(
172            greedy_routing(&graph, a, b, |u, v| distance1d(&graph, &positions, u, v)),
173            Err(NodeNotReachedError {})
174        )
175    }
176
177    #[test]
178    fn test_greedy_loop_error() {
179        // a -- b -- c -- d
180        let mut graph: UnGraph<(), ()> = Graph::with_capacity(4, 2);
181
182        let a = graph.add_node(());
183        let b = graph.add_node(());
184        let c = graph.add_node(());
185        let d = graph.add_node(());
186
187        graph.extend_with_edges([(a, b), (b, c), (c, d)]);
188
189        let positions = vec![[0., 0.], [1., 0.], [10., 0.], [4., 0.]];
190        assert_eq!(
191            greedy_routing(&graph, a, d, |u, v| distance2d(&graph, &positions, u, v)),
192            Err(NodeNotReachedError {})
193        )
194    }
195
196    #[test]
197    fn test_correct_greedy_path() {
198        // a -- b -- c -- d
199        //      |    |
200        //      e -- f -- g
201        let mut graph: UnGraph<(), ()> = Graph::with_capacity(7, 7);
202
203        let a = graph.add_node(());
204        let b = graph.add_node(());
205        let c = graph.add_node(());
206        let d = graph.add_node(());
207        let e = graph.add_node(());
208        let f = graph.add_node(());
209        let g = graph.add_node(());
210
211        graph.extend_with_edges([(a, b), (b, c), (c, d), (b, e), (e, f), (c, f), (f, g)]);
212
213        let positions = vec![
214            [0., 0.],
215            [1., 0.],
216            [2., 0.],
217            [2.5, 0.],
218            [1., 1.],
219            [2., 1.],
220            [3., 1.],
221        ];
222        let (path, dist) =
223            greedy_routing(&graph, a, d, |u, v| distance2d(&graph, &positions, u, v)).unwrap();
224        assert_eq!(path, vec![a, b, c, d]);
225        assert!((dist - (1. + 1. + 0.5)).abs() < 1e-15);
226
227        let (path, dist) =
228            greedy_routing(&graph, a, g, |u, v| distance2d(&graph, &positions, u, v)).unwrap();
229        assert_eq!(path, vec![a, b, c, f, g]);
230        assert!((dist - (1. + 1. + 1. + 1.)).abs() < 1e-15);
231    }
232
233    #[test]
234    fn test_correct_greedy_success_rate() {
235        // b -- c -- d
236        // |    |
237        // e -- f -- g
238        let mut graph: UnGraph<(), ()> = Graph::with_capacity(6, 6);
239
240        let b = graph.add_node(());
241        let c = graph.add_node(());
242        let d = graph.add_node(());
243        let e = graph.add_node(());
244        let f = graph.add_node(());
245        let g = graph.add_node(());
246
247        graph.extend_with_edges([(b, c), (c, d), (b, e), (e, f), (c, f), (f, g)]);
248
249        let positions = vec![
250            [1., 0.],
251            [2., 3.],
252            [3., 0.],
253            [1., -1.],
254            [2., -1.],
255            [3., -1.],
256        ];
257        let success_rate =
258            greedy_routing_success_rate(&graph, |u, v| distance2d(&graph, &positions, u, v));
259        // Greedy paths b -> d, e->d, f->d and g->d fail.
260        assert!((success_rate - 26. / 30.).abs() < 1e-15);
261    }
262}
rustworkx_core/geometry/greedy_routing.rs

rustworkx_core/geometry/
greedy_routing.rs
