algorithms_edu/problems/network_flow/
mice_and_owls.rs

1use crate::algo::geometry::Point2D;
2use crate::algo::graph::network_flow::{MaxFlowSolver, NetworkFlowAdjacencyList};
3
4#[allow(clippy::many_single_char_names)]
5#[allow(clippy::needless_range_loop)]
6pub fn mice_and_owls<S: MaxFlowSolver>(mice: &[Mouse], holes: &[Hole], radius: f64) -> i32 {
7    let m = mice.len();
8    let h = holes.len();
9    let n = m + h + 2;
10
11    let mut g = NetworkFlowAdjacencyList::with_size(n);
12    let s = g.source;
13    let t = g.sink;
14
15    for mouse in 0..m {
16        g.add_edge(s, mouse, 1);
17    }
18
19    // Hook up each mouse with the holes they are able to reach
20    for (mouse_id, mouse) in mice.iter().enumerate() {
21        for (j, hole) in holes.iter().enumerate() {
22            let hole_id = m + j;
23            if mouse.position.distance_to_point(&hole.position) <= radius {
24                g.add_edge(mouse_id, hole_id, 1);
25            }
26        }
27    }
28
29    for i in 0..h {
30        g.add_edge(m + i, t, holes[i].capacity);
31    }
32
33    S::max_flow(&mut g)
34}
35
36pub struct Mouse {
37    position: Point2D,
38}
39
40impl Mouse {
41    pub fn new(x: f64, y: f64) -> Self {
42        Self {
43            position: Point2D { x, y },
44        }
45    }
46}
47
48pub struct Hole {
49    position: Point2D,
50    capacity: i32,
51}
52
53impl Hole {
54    pub fn new(x: f64, y: f64, capacity: i32) -> Self {
55        Self {
56            position: Point2D { x, y },
57            capacity,
58        }
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65    use crate::algo::graph::network_flow::EdmondsKarpSolver;
66    #[test]
67    fn test_mice_and_owls() {
68        let mice = &[
69            Mouse::new(1., 0.),
70            Mouse::new(8., 1.),
71            Mouse::new(12., 0.),
72            Mouse::new(12., 4.),
73            Mouse::new(15., 5.),
74        ];
75        let holes = &[
76            Hole::new(1., 1., 1),
77            Hole::new(10., 2., 2),
78            Hole::new(14., 5., 1),
79        ];
80
81        let res = mice_and_owls::<EdmondsKarpSolver>(mice, holes, 3.);
82        assert_eq!(res, 4)
83    }
84}
algorithms_edu/problems/network_flow/mice_and_owls.rs

algorithms_edu/problems/network_flow/
mice_and_owls.rs
