problemreductions/models/graph/
hamiltonian_path.rs

1//! Hamiltonian Path problem implementation.
2//!
3//! The Hamiltonian Path problem asks whether a graph contains a simple path
4//! that visits every vertex exactly once.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::variant::VariantParam;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "HamiltonianPath",
15        display_name: "Hamiltonian Path",
16        aliases: &[],
17        dimensions: &[
18            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
19        ],
20        module_path: module_path!(),
21        description: "Find a Hamiltonian path in a graph",
22        fields: &[
23            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
24        ],
25    }
26}
27
28/// The Hamiltonian Path problem.
29///
30/// Given a graph G = (V, E), determine whether G contains a Hamiltonian path,
31/// i.e., a simple path that visits every vertex exactly once.
32///
33/// # Representation
34///
35/// A configuration is a sequence of `n` vertex indices representing a vertex
36/// ordering (permutation). Each position `i` in the configuration holds the
37/// vertex visited at step `i`. A valid solution must be a permutation of
38/// `0..n` where consecutive entries are adjacent in the graph.
39///
40/// The search space has `dims() = [n; n]` (each position can hold any of `n`
41/// vertices), so brute-force enumerates `n^n` configurations. Only `n!`
42/// permutations can satisfy the constraints, but the encoding avoids complex
43/// variable-domain schemes and matches the problem's natural formulation.
44///
45/// # Type Parameters
46///
47/// * `G` - Graph type (e.g., SimpleGraph)
48///
49/// # Example
50///
51/// ```
52/// use problemreductions::models::graph::HamiltonianPath;
53/// use problemreductions::topology::SimpleGraph;
54/// use problemreductions::{Problem, Solver, BruteForce};
55///
56/// // Path graph: 0-1-2-3
57/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
58/// let problem = HamiltonianPath::new(graph);
59///
60/// let solver = BruteForce::new();
61/// let solution = solver.find_witness(&problem);
62/// assert!(solution.is_some());
63/// ```
64#[derive(Debug, Clone, Serialize, Deserialize)]
65#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
66pub struct HamiltonianPath<G> {
67    graph: G,
68}
69
70impl<G: Graph> HamiltonianPath<G> {
71    /// Create a new Hamiltonian Path problem from a graph.
72    pub fn new(graph: G) -> Self {
73        Self { graph }
74    }
75
76    /// Get a reference to the underlying graph.
77    pub fn graph(&self) -> &G {
78        &self.graph
79    }
80
81    /// Get the number of vertices in the underlying graph.
82    pub fn num_vertices(&self) -> usize {
83        self.graph.num_vertices()
84    }
85
86    /// Get the number of edges in the underlying graph.
87    pub fn num_edges(&self) -> usize {
88        self.graph.num_edges()
89    }
90
91    /// Check if a configuration is a valid Hamiltonian path.
92    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
93        is_valid_hamiltonian_path(&self.graph, config)
94    }
95}
96
97impl<G> Problem for HamiltonianPath<G>
98where
99    G: Graph + VariantParam,
100{
101    const NAME: &'static str = "HamiltonianPath";
102    type Value = crate::types::Or;
103
104    fn variant() -> Vec<(&'static str, &'static str)> {
105        crate::variant_params![G]
106    }
107
108    fn dims(&self) -> Vec<usize> {
109        let n = self.graph.num_vertices();
110        vec![n; n]
111    }
112
113    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
114        crate::types::Or(is_valid_hamiltonian_path(&self.graph, config))
115    }
116}
117
118/// Check if a configuration represents a valid Hamiltonian path in the graph.
119///
120/// A valid Hamiltonian path is a permutation of the vertices such that
121/// consecutive vertices in the permutation are adjacent in the graph.
122pub(crate) fn is_valid_hamiltonian_path<G: Graph>(graph: &G, config: &[usize]) -> bool {
123    let n = graph.num_vertices();
124    if config.len() != n {
125        return false;
126    }
127
128    // Check that config is a valid permutation of 0..n
129    let mut seen = vec![false; n];
130    for &v in config {
131        if v >= n || seen[v] {
132            return false;
133        }
134        seen[v] = true;
135    }
136
137    // Check consecutive vertices are adjacent
138    for i in 0..n.saturating_sub(1) {
139        if !graph.has_edge(config[i], config[i + 1]) {
140            return false;
141        }
142    }
143
144    true
145}
146
147#[cfg(feature = "example-db")]
148pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
149    vec![crate::example_db::specs::ModelExampleSpec {
150        id: "hamiltonian_path_simplegraph",
151        instance: Box::new(HamiltonianPath::new(SimpleGraph::new(
152            6,
153            vec![
154                (0, 1),
155                (0, 2),
156                (1, 3),
157                (2, 3),
158                (3, 4),
159                (3, 5),
160                (4, 2),
161                (5, 1),
162            ],
163        ))),
164        optimal_config: vec![0, 2, 4, 3, 1, 5],
165        optimal_value: serde_json::json!(true),
166    }]
167}
168
169// Use Bjorklund (2014) O*(1.657^n) as best known for general undirected graphs
170crate::declare_variants! {
171    default HamiltonianPath<SimpleGraph> => "1.657^num_vertices",
172}
173
174#[cfg(test)]
175#[path = "../../unit_tests/models/graph/hamiltonian_path.rs"]
176mod tests;
problemreductions/models/graph/hamiltonian_path.rs

problemreductions/models/graph/
hamiltonian_path.rs
