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

problemreductions/models/graph/
hamiltonian_path.rs
