utils/
graph.rs

1//! Graph helpers.
2
3use crate::bit::BitIterator;
4use crate::number::UnsignedInteger;
5use std::marker::PhantomData;
6
7/// Explore all hamiltonian paths/cycles in a graph.
8///
9/// # Panics
10/// This function panics if the number of vertices exceeds the maximum supported, currently 32.
11///
12/// # Examples
13///
14/// Shortest hamiltonian path and cycle starting at vertex 0:
15/// ```
16/// # use utils::graph::explore_hamiltonian_paths;
17/// # use std::ops::Add;
18/// let distance_matrix = vec![
19///     0, 7, 2, 8, 6,
20///     7, 0, 1, 3, 5,
21///     2, 1, 0, 9, 4,
22///     8, 3, 9, 0, 9,
23///     6, 5, 4, 9, 0,
24/// ];
25///
26/// let mut min_hamiltonian_path = u32::MAX;
27/// let mut min_hamiltonian_cycle = u32::MAX;
28/// explore_hamiltonian_paths(
29///     5,                                                              // Number of vertices
30///     0,                                                              // Start vertex
31///     0,                                                              // Initial path cost
32///     |a, b| distance_matrix[a as usize * 5 + b as usize],            // Distance function
33///     u32::add,                                                       // Accumulate function
34///     |path, loop_edge| {                                             // Callback function
35///         min_hamiltonian_path = min_hamiltonian_path.min(path);
36///         min_hamiltonian_cycle = min_hamiltonian_cycle.min(path + loop_edge);
37///     }
38/// );
39///
40/// assert_eq!(min_hamiltonian_path, 14);  // 0 =[6]=> 4 =[4]=> 2 =[1]=> 1 =[3]=> 3
41/// assert_eq!(min_hamiltonian_cycle, 21); // 0 =[2]=> 2 =[1]=> 1 =[3]=> 3 =[9]=> 4 =[6]=> 0
42/// ```
43///
44/// Shortest and longest hamilton paths starting at any vertex:
45/// ```
46/// # use utils::graph::explore_hamiltonian_paths;
47/// let distance_matrix = vec![
48///     0, 7, 2, 8, 6,
49///     7, 0, 1, 3, 5,
50///     2, 1, 0, 9, 4,
51///     8, 3, 9, 0, 9,
52///     6, 5, 4, 9, 0,
53/// ];
54///
55/// let mut min_path = u32::MAX;
56/// let mut max_path = 0;
57/// explore_hamiltonian_paths(
58///     5,                                                              // Number of vertices
59///     0,                                                              // Start vertex
60///     (0, u32::MAX, 0),                                               // Initial path cost
61///     |a, b| distance_matrix[a as usize * 5 + b as usize],            // Distance function
62///     |(total, min_edge, max_edge), edge| {                           // Accumulate function
63///         (total + edge, min_edge.min(edge), max_edge.max(edge))
64///     },
65///     |(total, min_edge, max_edge), loop_edge| {                      // Callback function
66///         let loop_total = total + loop_edge;
67///         min_path = min_path.min(loop_total - max_edge.max(loop_edge));
68///         max_path = max_path.max(loop_total - min_edge.min(loop_edge));
69///     }
70/// );
71///
72/// assert_eq!(min_path, 12); // 3 =[3]=> 1 =[1]=> 2 =[2]=> 0 =[6]=> 4
73/// assert_eq!(max_path, 31); // 1 =[7]=> 0 =[6]=> 4 =[9]=> 3 =[9]=> 2
74/// ```
75#[inline]
76pub fn explore_hamiltonian_paths<E, P: Copy>(
77    vertices: u32,
78    start_vertex: u32,
79    initial_path: P,
80    distance_fn: impl Fn(u32, u32) -> E,
81    accumulate_fn: impl Fn(P, E) -> P,
82    callback_fn: impl FnMut(P, E),
83) {
84    // Rust doesn't allow recursive FnMut closures, so move state into struct
85    struct Visitor<P, F, G, H> {
86        start_vertex: u32,
87        phantom: PhantomData<P>,
88        distance_fn: F,
89        accumulate_fn: G,
90        callback_fn: H,
91    }
92
93    impl<E, P: Copy, F: Fn(u32, u32) -> E, G: Fn(P, E) -> P, H: FnMut(P, E)> Visitor<P, F, G, H> {
94        #[inline]
95        fn visit<V: UnsignedInteger>(&mut self, current_vertex: u32, visited: V, path: P) {
96            if visited == V::MAX {
97                let loop_edge = (self.distance_fn)(current_vertex, self.start_vertex);
98                (self.callback_fn)(path, loop_edge);
99                return;
100            }
101
102            for (next_vertex, next_bit) in BitIterator::zeroes(visited) {
103                let new_edge = (self.distance_fn)(current_vertex, next_vertex);
104                let new_path = (self.accumulate_fn)(path, new_edge);
105                self.visit(next_vertex, visited | next_bit, new_path);
106            }
107        }
108    }
109
110    // visit can take any unsigned integer type as a bitmask, so the code could switch the
111    // implementation based on the number of vertices. However, it seems unlikely that an AoC
112    // problem would require this as generating that many permutations would be very slow, so for
113    // now assume u32 is fine.
114    assert!(vertices <= 32, "too many vertices");
115
116    let mut visitor = Visitor {
117        start_vertex,
118        distance_fn,
119        accumulate_fn,
120        callback_fn,
121        phantom: PhantomData,
122    };
123    visitor.visit(
124        start_vertex,
125        !(u32::MAX >> (u32::BITS - vertices)) | (1 << start_vertex),
126        initial_path,
127    );
128}
utils/graph.rs

utils/
graph.rs
