rust_igraph/algorithms/properties/
hamiltonian.rs

1//! Hamiltonian path and cycle detection (ALGO-TR-031).
2//!
3//! A **Hamiltonian path** visits every vertex exactly once.
4//! A **Hamiltonian cycle** visits every vertex exactly once and returns
5//! to the start.
6//!
7//! Detection is NP-complete, so we use backtracking with pruning.
8//! Suitable for small graphs (≤ ~20 vertices).
9
10#![allow(
11    clippy::cast_possible_truncation,
12    clippy::cast_precision_loss,
13    clippy::many_single_char_names,
14    clippy::needless_range_loop,
15    clippy::too_many_lines
16)]
17
18use crate::core::{Graph, IgraphResult};
19
20/// Check whether a sequence of vertices forms a valid Hamiltonian path.
21///
22/// A valid Hamiltonian path visits every vertex exactly once and each
23/// consecutive pair is connected by an edge.
24///
25/// # Examples
26///
27/// ```
28/// use rust_igraph::{Graph, is_hamiltonian_path};
29///
30/// let g = Graph::from_edges(&[(0,1),(1,2),(2,3)], false, Some(4)).unwrap();
31/// assert!(is_hamiltonian_path(&g, &[0, 1, 2, 3]).unwrap());
32/// assert!(!is_hamiltonian_path(&g, &[0, 2, 1, 3]).unwrap());
33/// ```
34pub fn is_hamiltonian_path(graph: &Graph, path: &[u32]) -> IgraphResult<bool> {
35    let n = graph.vcount() as usize;
36    if path.len() != n {
37        return Ok(false);
38    }
39
40    let mut visited = vec![false; n];
41    for &v in path {
42        let vi = v as usize;
43        if vi >= n || visited[vi] {
44            return Ok(false);
45        }
46        visited[vi] = true;
47    }
48
49    for i in 0..path.len() - 1 {
50        let nbrs = graph.neighbors(path[i])?;
51        if !nbrs.contains(&path[i + 1]) {
52            return Ok(false);
53        }
54    }
55
56    Ok(true)
57}
58
59/// Check whether a sequence of vertices forms a valid Hamiltonian cycle.
60///
61/// A valid Hamiltonian cycle visits every vertex exactly once and the
62/// last vertex is adjacent to the first.
63///
64/// # Examples
65///
66/// ```
67/// use rust_igraph::{Graph, is_hamiltonian_cycle};
68///
69/// let g = Graph::from_edges(
70///     &[(0,1),(1,2),(2,3),(3,0)], false, Some(4)
71/// ).unwrap();
72/// assert!(is_hamiltonian_cycle(&g, &[0, 1, 2, 3]).unwrap());
73/// ```
74pub fn is_hamiltonian_cycle(graph: &Graph, cycle: &[u32]) -> IgraphResult<bool> {
75    let n = graph.vcount() as usize;
76    if n < 3 || cycle.len() != n {
77        return Ok(false);
78    }
79
80    if !is_hamiltonian_path(graph, cycle)? {
81        return Ok(false);
82    }
83
84    let last = cycle[cycle.len() - 1];
85    let first = cycle[0];
86    let nbrs = graph.neighbors(last)?;
87    Ok(nbrs.contains(&first))
88}
89
90/// Find a Hamiltonian path using backtracking.
91///
92/// Returns `Some(path)` if one exists, `None` otherwise.
93/// Only feasible for small graphs.
94///
95/// # Examples
96///
97/// ```
98/// use rust_igraph::{Graph, hamiltonian_path, is_hamiltonian_path};
99///
100/// let g = Graph::from_edges(&[(0,1),(1,2),(2,3)], false, Some(4)).unwrap();
101/// let p = hamiltonian_path(&g).unwrap();
102/// assert!(p.is_some());
103/// assert!(is_hamiltonian_path(&g, &p.unwrap()).unwrap());
104/// ```
105pub fn hamiltonian_path(graph: &Graph) -> IgraphResult<Option<Vec<u32>>> {
106    let n = graph.vcount() as usize;
107    if n == 0 {
108        return Ok(Some(Vec::new()));
109    }
110    if n == 1 {
111        return Ok(Some(vec![0]));
112    }
113
114    let adj = build_adj(graph, n);
115    let mut visited = vec![false; n];
116    let mut path = Vec::with_capacity(n);
117
118    for start in 0..n {
119        visited[start] = true;
120        path.push(start as u32);
121        if ham_path_bt(&adj, n, &mut visited, &mut path) {
122            return Ok(Some(path));
123        }
124        path.pop();
125        visited[start] = false;
126    }
127
128    Ok(None)
129}
130
131/// Find a Hamiltonian cycle using backtracking.
132///
133/// Returns `Some(cycle)` if one exists, `None` otherwise.
134/// Only feasible for small graphs.
135///
136/// # Examples
137///
138/// ```
139/// use rust_igraph::{Graph, hamiltonian_cycle, is_hamiltonian_cycle};
140///
141/// let g = Graph::from_edges(
142///     &[(0,1),(1,2),(2,3),(3,0)], false, Some(4)
143/// ).unwrap();
144/// let c = hamiltonian_cycle(&g).unwrap();
145/// assert!(c.is_some());
146/// assert!(is_hamiltonian_cycle(&g, &c.unwrap()).unwrap());
147/// ```
148pub fn hamiltonian_cycle(graph: &Graph) -> IgraphResult<Option<Vec<u32>>> {
149    let n = graph.vcount() as usize;
150    if n < 3 {
151        return Ok(None);
152    }
153
154    let adj = build_adj(graph, n);
155    let mut visited = vec![false; n];
156    let mut path = Vec::with_capacity(n);
157
158    visited[0] = true;
159    path.push(0_u32);
160    let result = ham_cycle_bt(&adj, n, &mut visited, &mut path);
161
162    if result { Ok(Some(path)) } else { Ok(None) }
163}
164
165/// Check whether a graph has a Hamiltonian path.
166///
167/// # Examples
168///
169/// ```
170/// use rust_igraph::{Graph, has_hamiltonian_path};
171///
172/// let g = Graph::from_edges(&[(0,1),(1,2),(2,3)], false, Some(4)).unwrap();
173/// assert!(has_hamiltonian_path(&g).unwrap());
174/// ```
175pub fn has_hamiltonian_path(graph: &Graph) -> IgraphResult<bool> {
176    Ok(hamiltonian_path(graph)?.is_some())
177}
178
179/// Check whether a graph has a Hamiltonian cycle.
180///
181/// # Examples
182///
183/// ```
184/// use rust_igraph::{Graph, has_hamiltonian_cycle};
185///
186/// let g = Graph::from_edges(
187///     &[(0,1),(1,2),(2,3),(3,0)], false, Some(4)
188/// ).unwrap();
189/// assert!(has_hamiltonian_cycle(&g).unwrap());
190/// ```
191pub fn has_hamiltonian_cycle(graph: &Graph) -> IgraphResult<bool> {
192    Ok(hamiltonian_cycle(graph)?.is_some())
193}
194
195fn build_adj(graph: &Graph, n: usize) -> Vec<bool> {
196    let mut adj = vec![false; n * n];
197    for (u, v) in graph.edges() {
198        let ui = u as usize;
199        let vi = v as usize;
200        adj[ui * n + vi] = true;
201        if !graph.is_directed() {
202            adj[vi * n + ui] = true;
203        }
204    }
205    adj
206}
207
208fn ham_path_bt(adj: &[bool], n: usize, visited: &mut Vec<bool>, path: &mut Vec<u32>) -> bool {
209    if path.len() == n {
210        return true;
211    }
212
213    let last = path[path.len() - 1] as usize;
214
215    let unvisited_count = visited.iter().filter(|&&v| !v).count();
216    if unvisited_count == 0 {
217        return false;
218    }
219
220    for next in 0..n {
221        if !visited[next] && adj[last * n + next] {
222            if unvisited_count > 1 {
223                let reachable = count_reachable_unvisited(adj, n, next, visited);
224                if reachable < unvisited_count - 1 {
225                    continue;
226                }
227            }
228
229            visited[next] = true;
230            path.push(next as u32);
231            if ham_path_bt(adj, n, visited, path) {
232                return true;
233            }
234            path.pop();
235            visited[next] = false;
236        }
237    }
238
239    false
240}
241
242fn ham_cycle_bt(adj: &[bool], n: usize, visited: &mut Vec<bool>, path: &mut Vec<u32>) -> bool {
243    if path.len() == n {
244        let last = path[path.len() - 1] as usize;
245        return adj[last * n]; // check edge back to vertex 0
246    }
247
248    let last = path[path.len() - 1] as usize;
249
250    for next in 0..n {
251        if !visited[next] && adj[last * n + next] {
252            visited[next] = true;
253            path.push(next as u32);
254            if ham_cycle_bt(adj, n, visited, path) {
255                return true;
256            }
257            path.pop();
258            visited[next] = false;
259        }
260    }
261
262    false
263}
264
265fn count_reachable_unvisited(adj: &[bool], n: usize, start: usize, visited: &[bool]) -> usize {
266    let mut seen = vec![false; n];
267    seen[start] = true;
268    let mut stack = vec![start];
269    let mut count: usize = 0;
270
271    while let Some(v) = stack.pop() {
272        for u in 0..n {
273            if !seen[u] && !visited[u] && adj[v * n + u] {
274                seen[u] = true;
275                count = count.saturating_add(1);
276                stack.push(u);
277            }
278        }
279    }
280
281    count
282}
283
284#[cfg(test)]
285mod tests {
286    use super::*;
287
288    fn path4() -> Graph {
289        Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false, Some(4)).unwrap()
290    }
291
292    fn cycle4() -> Graph {
293        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap()
294    }
295
296    fn cycle5() -> Graph {
297        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], false, Some(5)).unwrap()
298    }
299
300    fn k4() -> Graph {
301        Graph::from_edges(
302            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
303            false,
304            Some(4),
305        )
306        .unwrap()
307    }
308
309    fn k3() -> Graph {
310        Graph::from_edges(&[(0, 1), (1, 2), (0, 2)], false, Some(3)).unwrap()
311    }
312
313    fn star5() -> Graph {
314        Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], false, Some(5)).unwrap()
315    }
316
317    fn disconnected() -> Graph {
318        Graph::from_edges(&[(0, 1), (2, 3)], false, Some(4)).unwrap()
319    }
320
321    fn petersen() -> Graph {
322        Graph::from_edges(
323            &[
324                (0, 1),
325                (1, 2),
326                (2, 3),
327                (3, 4),
328                (4, 0),
329                (0, 5),
330                (1, 6),
331                (2, 7),
332                (3, 8),
333                (4, 9),
334                (5, 7),
335                (7, 9),
336                (9, 6),
337                (6, 8),
338                (8, 5),
339            ],
340            false,
341            Some(10),
342        )
343        .unwrap()
344    }
345
346    // --- is_hamiltonian_path ---
347
348    #[test]
349    fn ihp_valid() {
350        let g = path4();
351        assert!(is_hamiltonian_path(&g, &[0, 1, 2, 3]).unwrap());
352    }
353
354    #[test]
355    fn ihp_reversed() {
356        let g = path4();
357        assert!(is_hamiltonian_path(&g, &[3, 2, 1, 0]).unwrap());
358    }
359
360    #[test]
361    fn ihp_invalid_no_edge() {
362        let g = path4();
363        assert!(!is_hamiltonian_path(&g, &[0, 2, 1, 3]).unwrap());
364    }
365
366    #[test]
367    fn ihp_wrong_length() {
368        let g = path4();
369        assert!(!is_hamiltonian_path(&g, &[0, 1, 2]).unwrap());
370    }
371
372    #[test]
373    fn ihp_duplicate_vertex() {
374        let g = path4();
375        assert!(!is_hamiltonian_path(&g, &[0, 1, 1, 3]).unwrap());
376    }
377
378    #[test]
379    fn ihp_out_of_range() {
380        let g = path4();
381        assert!(!is_hamiltonian_path(&g, &[0, 1, 2, 10]).unwrap());
382    }
383
384    // --- is_hamiltonian_cycle ---
385
386    #[test]
387    fn ihc_valid() {
388        let g = cycle4();
389        assert!(is_hamiltonian_cycle(&g, &[0, 1, 2, 3]).unwrap());
390    }
391
392    #[test]
393    fn ihc_path_not_cycle() {
394        let g = path4();
395        assert!(!is_hamiltonian_cycle(&g, &[0, 1, 2, 3]).unwrap());
396    }
397
398    #[test]
399    fn ihc_too_small() {
400        let g = Graph::from_edges(&[(0, 1)], false, Some(2)).unwrap();
401        assert!(!is_hamiltonian_cycle(&g, &[0, 1]).unwrap());
402    }
403
404    #[test]
405    fn ihc_k3() {
406        let g = k3();
407        assert!(is_hamiltonian_cycle(&g, &[0, 1, 2]).unwrap());
408    }
409
410    // --- hamiltonian_path ---
411
412    #[test]
413    fn hp_empty() {
414        let g = Graph::with_vertices(0);
415        let p = hamiltonian_path(&g).unwrap();
416        assert!(p.is_some());
417        assert!(p.unwrap().is_empty());
418    }
419
420    #[test]
421    fn hp_single() {
422        let g = Graph::with_vertices(1);
423        let p = hamiltonian_path(&g).unwrap();
424        assert_eq!(p.unwrap(), vec![0]);
425    }
426
427    #[test]
428    fn hp_path4() {
429        let g = path4();
430        let p = hamiltonian_path(&g).unwrap().unwrap();
431        assert!(is_hamiltonian_path(&g, &p).unwrap());
432    }
433
434    #[test]
435    fn hp_cycle4() {
436        let g = cycle4();
437        let p = hamiltonian_path(&g).unwrap().unwrap();
438        assert!(is_hamiltonian_path(&g, &p).unwrap());
439    }
440
441    #[test]
442    fn hp_k4() {
443        let g = k4();
444        let p = hamiltonian_path(&g).unwrap().unwrap();
445        assert!(is_hamiltonian_path(&g, &p).unwrap());
446    }
447
448    #[test]
449    fn hp_star5() {
450        let g = star5();
451        assert!(hamiltonian_path(&g).unwrap().is_none());
452    }
453
454    #[test]
455    fn hp_disconnected() {
456        let g = disconnected();
457        assert!(hamiltonian_path(&g).unwrap().is_none());
458    }
459
460    #[test]
461    fn hp_cycle5() {
462        let g = cycle5();
463        let p = hamiltonian_path(&g).unwrap().unwrap();
464        assert!(is_hamiltonian_path(&g, &p).unwrap());
465    }
466
467    // --- hamiltonian_cycle ---
468
469    #[test]
470    fn hc_cycle4() {
471        let g = cycle4();
472        let c = hamiltonian_cycle(&g).unwrap().unwrap();
473        assert!(is_hamiltonian_cycle(&g, &c).unwrap());
474    }
475
476    #[test]
477    fn hc_cycle5() {
478        let g = cycle5();
479        let c = hamiltonian_cycle(&g).unwrap().unwrap();
480        assert!(is_hamiltonian_cycle(&g, &c).unwrap());
481    }
482
483    #[test]
484    fn hc_k4() {
485        let g = k4();
486        let c = hamiltonian_cycle(&g).unwrap().unwrap();
487        assert!(is_hamiltonian_cycle(&g, &c).unwrap());
488    }
489
490    #[test]
491    fn hc_k3() {
492        let g = k3();
493        let c = hamiltonian_cycle(&g).unwrap().unwrap();
494        assert!(is_hamiltonian_cycle(&g, &c).unwrap());
495    }
496
497    #[test]
498    fn hc_path4_no_cycle() {
499        let g = path4();
500        assert!(hamiltonian_cycle(&g).unwrap().is_none());
501    }
502
503    #[test]
504    fn hc_star5_no_cycle() {
505        let g = star5();
506        assert!(hamiltonian_cycle(&g).unwrap().is_none());
507    }
508
509    #[test]
510    fn hc_disconnected_no_cycle() {
511        let g = disconnected();
512        assert!(hamiltonian_cycle(&g).unwrap().is_none());
513    }
514
515    #[test]
516    fn hc_too_small() {
517        let g = Graph::from_edges(&[(0, 1)], false, Some(2)).unwrap();
518        assert!(hamiltonian_cycle(&g).unwrap().is_none());
519    }
520
521    // --- has_hamiltonian_path / has_hamiltonian_cycle ---
522
523    #[test]
524    fn hhp_path4() {
525        assert!(has_hamiltonian_path(&path4()).unwrap());
526    }
527
528    #[test]
529    fn hhp_star5() {
530        assert!(!has_hamiltonian_path(&star5()).unwrap());
531    }
532
533    #[test]
534    fn hhc_cycle4() {
535        assert!(has_hamiltonian_cycle(&cycle4()).unwrap());
536    }
537
538    #[test]
539    fn hhc_path4() {
540        assert!(!has_hamiltonian_cycle(&path4()).unwrap());
541    }
542
543    // --- petersen graph ---
544
545    #[test]
546    fn petersen_has_path() {
547        let g = petersen();
548        let p = hamiltonian_path(&g).unwrap().unwrap();
549        assert!(is_hamiltonian_path(&g, &p).unwrap());
550    }
551
552    #[test]
553    fn petersen_no_cycle() {
554        let g = petersen();
555        assert!(hamiltonian_cycle(&g).unwrap().is_none());
556    }
557
558    // --- cross-consistency ---
559
560    #[test]
561    fn cycle_implies_path() {
562        for g in &[cycle4(), cycle5(), k3(), k4()] {
563            if has_hamiltonian_cycle(g).unwrap() {
564                assert!(has_hamiltonian_path(g).unwrap());
565            }
566        }
567    }
568
569    #[test]
570    fn isolated_vertices() {
571        let g = Graph::with_vertices(3);
572        assert!(!has_hamiltonian_path(&g).unwrap());
573        assert!(!has_hamiltonian_cycle(&g).unwrap());
574    }
575}
rust_igraph/algorithms/properties/hamiltonian.rs

rust_igraph/algorithms/properties/
hamiltonian.rs
