graph_advanced/
hamiltonian.rs

1use graph_core::{Graph, NodeId};
2use std::collections::HashSet;
3
4/// Finds a **Hamiltonian path** starting from `start` using backtracking.
5///
6/// A Hamiltonian path visits every node **exactly once**. Unlike an Euler
7/// path (which covers every *edge*), a Hamiltonian path covers every *node*.
8///
9/// # Algorithm
10///
11/// Depth-first backtracking: at each step, extend the current path to any
12/// unvisited neighbour. Backtrack if no extension is possible. The search
13/// terminates as soon as a complete path (visiting all `V` nodes) is found.
14///
15/// This is an exact algorithm — it finds a solution if one exists and
16/// reports `None` otherwise. The worst-case time is O(V!), so this is
17/// only practical for small graphs (V ≲ 20).
18///
19/// # Returns
20///
21/// `Some(Vec<NodeId>)` — a Hamiltonian path starting at `start`, listing
22/// nodes in visit order.  
23/// `None` — no Hamiltonian path from `start` exists.
24///
25/// # Complexity
26///
27/// O(V!) worst case.
28///
29/// # Examples
30///
31/// ```
32/// use graph_core::{AdjacencyList, Graph};
33/// use graph_advanced::hamiltonian_path;
34///
35/// // Path graph: 0-1-2-3 — Hamiltonian path obviously exists.
36/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
37/// let n: Vec<_> = (0..4).map(|_| g.add_node(())).collect();
38/// g.add_edge(n[0], n[1], 1.0).unwrap();
39/// g.add_edge(n[1], n[2], 1.0).unwrap();
40/// g.add_edge(n[2], n[3], 1.0).unwrap();
41///
42/// let path = hamiltonian_path(&g, n[0]).unwrap();
43/// assert_eq!(path.len(), 4);
44/// assert_eq!(path[0], n[0]);
45/// ```
46pub fn hamiltonian_path<G>(graph: &G, start: NodeId) -> Option<Vec<NodeId>>
47where
48    G: Graph<Weight = f64>,
49{
50    let total_nodes = graph.node_count();
51    if total_nodes == 0 {
52        return None;
53    }
54
55    let mut path = vec![start];
56    let mut visited: HashSet<NodeId> = HashSet::new();
57    visited.insert(start);
58
59    if backtrack(graph, &mut path, &mut visited, total_nodes) {
60        Some(path)
61    } else {
62        None
63    }
64}
65
66/// Recursive backtracking helper.
67///
68/// Returns `true` when a complete Hamiltonian path has been found in `path`.
69fn backtrack<G>(
70    graph: &G,
71    path: &mut Vec<NodeId>,
72    visited: &mut HashSet<NodeId>,
73    total_nodes: usize,
74) -> bool
75where
76    G: Graph<Weight = f64>,
77{
78    if path.len() == total_nodes {
79        return true; // All nodes visited — path is complete.
80    }
81
82    let current = *path.last().unwrap();
83
84    // Collect neighbours first to avoid holding a borrow while mutating path.
85    let neighbours: Vec<NodeId> = graph.neighbors(current).map(|(v, _)| v).collect();
86
87    for next in neighbours {
88        if !visited.contains(&next) {
89            path.push(next);
90            visited.insert(next);
91
92            if backtrack(graph, path, visited, total_nodes) {
93                return true;
94            }
95
96            // Backtrack.
97            path.pop();
98            visited.remove(&next);
99        }
100    }
101
102    false
103}
graph_advanced/hamiltonian.rs

graph_advanced/
hamiltonian.rs
