problemreductions/models/graph/
hamiltonian_path_between_two_vertices.rs

1//! Hamiltonian Path Between Two Vertices problem implementation.
2//!
3//! The Hamiltonian Path Between Two Vertices problem asks whether a graph contains a
4//! simple path that starts at a specified source vertex, ends at a specified target
5//! vertex, and visits every other vertex exactly once.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::variant::VariantParam;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "HamiltonianPathBetweenTwoVertices",
16        display_name: "Hamiltonian Path Between Two Vertices",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Find a Hamiltonian path between two specified vertices in a graph",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "source_vertex", type_name: "usize", description: "Source vertex s" },
27            FieldInfo { name: "target_vertex", type_name: "usize", description: "Target vertex t" },
28        ],
29    }
30}
31
32/// The Hamiltonian Path Between Two Vertices problem.
33///
34/// Given a graph G = (V, E) and two distinguished vertices s, t in V,
35/// determine whether G contains a Hamiltonian path from s to t, i.e.,
36/// a simple path that begins at s, ends at t, and visits every vertex
37/// exactly once.
38///
39/// # Representation
40///
41/// A configuration is a sequence of `n` vertex indices representing a vertex
42/// ordering (permutation). Each position `i` in the configuration holds the
43/// vertex visited at step `i`. A valid solution must be a permutation of
44/// `0..n` where:
45/// - The first element equals `source_vertex`
46/// - The last element equals `target_vertex`
47/// - Consecutive entries are adjacent in the graph
48///
49/// The search space has `dims() = [n; n]` (each position can hold any of `n`
50/// vertices), so brute-force enumerates `n^n` configurations.
51///
52/// # Type Parameters
53///
54/// * `G` - Graph type (e.g., SimpleGraph)
55///
56/// # Example
57///
58/// ```
59/// use problemreductions::models::graph::HamiltonianPathBetweenTwoVertices;
60/// use problemreductions::topology::SimpleGraph;
61/// use problemreductions::{Problem, BruteForce};
62///
63/// // Path graph: 0-1-2-3, source=0, target=3
64/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
65/// let problem = HamiltonianPathBetweenTwoVertices::new(graph, 0, 3);
66///
67/// let solver = BruteForce::new();
68/// let solution = solver.solve(&problem).unwrap();
69/// assert!(solution.is_some());
70/// ```
71#[derive(Debug, Clone, Serialize, Deserialize)]
72#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
73pub struct HamiltonianPathBetweenTwoVertices<G> {
74    graph: G,
75    source_vertex: usize,
76    target_vertex: usize,
77}
78
79#[derive(Debug, Deserialize, crate::CreateSpec)]
80struct HamiltonianPathBetweenTwoVerticesRandomSpec {
81    /// Number of graph vertices.
82    num_vertices: usize,
83    /// Independent edge probability (default: 0.5).
84    edge_prob: Option<f64>,
85    /// Seed for reproducible generation.
86    seed: Option<i64>,
87    /// Path start vertex (default: 0).
88    source_vertex: Option<usize>,
89    /// Path end vertex (default: the final vertex).
90    target_vertex: Option<usize>,
91}
92
93impl<G: Graph> HamiltonianPathBetweenTwoVertices<G> {
94    /// Create a new Hamiltonian Path Between Two Vertices problem.
95    ///
96    /// # Panics
97    ///
98    /// Panics if `source_vertex` or `target_vertex` is out of range, or if they are equal.
99    pub fn new(graph: G, source_vertex: usize, target_vertex: usize) -> Self {
100        let n = graph.num_vertices();
101        assert!(
102            source_vertex < n,
103            "source_vertex {source_vertex} out of range for graph with {n} vertices"
104        );
105        assert!(
106            target_vertex < n,
107            "target_vertex {target_vertex} out of range for graph with {n} vertices"
108        );
109        assert_ne!(
110            source_vertex, target_vertex,
111            "source_vertex and target_vertex must be distinct"
112        );
113        Self {
114            graph,
115            source_vertex,
116            target_vertex,
117        }
118    }
119
120    /// Get a reference to the underlying graph.
121    pub fn graph(&self) -> &G {
122        &self.graph
123    }
124
125    /// Get the source vertex s.
126    pub fn source_vertex(&self) -> usize {
127        self.source_vertex
128    }
129
130    /// Get the target vertex t.
131    pub fn target_vertex(&self) -> usize {
132        self.target_vertex
133    }
134
135    /// Get the number of vertices in the underlying graph.
136    pub fn num_vertices(&self) -> usize {
137        self.graph.num_vertices()
138    }
139
140    /// Get the number of edges in the underlying graph.
141    pub fn num_edges(&self) -> usize {
142        self.graph.num_edges()
143    }
144
145    /// Check if a configuration is a valid Hamiltonian s-t path.
146    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
147        is_valid_hamiltonian_st_path(&self.graph, config, self.source_vertex, self.target_vertex)
148    }
149}
150
151impl<G> Problem for HamiltonianPathBetweenTwoVertices<G>
152where
153    G: Graph + VariantParam,
154{
155    const NAME: &'static str = "HamiltonianPathBetweenTwoVertices";
156    type Solution = Vec<usize>;
157    type Value = crate::types::Or;
158
159    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
160
161    fn variant() -> Vec<(&'static str, &'static str)> {
162        crate::variant_params![G]
163    }
164
165    fn evaluate(
166        &self,
167        config: &Self::Solution,
168    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
169        let n = self.graph.num_vertices();
170        if config.len() != n {
171            return Err(crate::traits::EvaluationError::InvalidConfiguration(
172                "path ordering length does not match the graph vertices".into(),
173            ));
174        }
175        if config.iter().any(|&vertex| vertex >= n) {
176            return Err(crate::traits::EvaluationError::InvalidConfiguration(
177                "path ordering contains an out-of-range vertex".into(),
178            ));
179        }
180        Ok({
181            crate::types::Or(is_valid_hamiltonian_st_path(
182                &self.graph,
183                config,
184                self.source_vertex,
185                self.target_vertex,
186            ))
187        })
188    }
189}
190
191impl<G> crate::solvers::BruteForceProblem for HamiltonianPathBetweenTwoVertices<G>
192where
193    G: Graph + VariantParam,
194{
195    fn dimensions(&self) -> Vec<usize> {
196        let n = self.graph.num_vertices();
197        vec![n; n]
198    }
199}
200
201/// Check if a configuration represents a valid Hamiltonian s-t path in the graph.
202///
203/// A valid Hamiltonian s-t path is a permutation of all vertices such that:
204/// - The first element is `source`
205/// - The last element is `target`
206/// - Consecutive vertices in the permutation are adjacent in the graph
207pub(crate) fn is_valid_hamiltonian_st_path<G: Graph>(
208    graph: &G,
209    config: &[usize],
210    source: usize,
211    target: usize,
212) -> bool {
213    let n = graph.num_vertices();
214    if config.len() != n {
215        return false;
216    }
217
218    // Check that config is a valid permutation of 0..n
219    let mut seen = vec![false; n];
220    for &v in config {
221        if v >= n || seen[v] {
222            return false;
223        }
224        seen[v] = true;
225    }
226
227    // Check endpoint constraints
228    if config[0] != source || config[n - 1] != target {
229        return false;
230    }
231
232    // Check consecutive vertices are adjacent
233    for i in 0..n.saturating_sub(1) {
234        if !graph.has_edge(config[i], config[i + 1]) {
235            return false;
236        }
237    }
238
239    true
240}
241
242#[cfg(feature = "example-db")]
243pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
244    // Instance from issue #831: 6 vertices, s=0, t=5
245    // Hamiltonian s-t path: [0, 3, 2, 1, 4, 5]
246    vec![crate::example_db::specs::ModelExampleSpec {
247        id: "hamiltonian_path_between_two_vertices_simplegraph",
248        instance: Box::new(HamiltonianPathBetweenTwoVertices::new(
249            SimpleGraph::new(
250                6,
251                vec![
252                    (0, 1),
253                    (0, 3),
254                    (1, 2),
255                    (1, 4),
256                    (2, 5),
257                    (3, 4),
258                    (4, 5),
259                    (2, 3),
260                ],
261            ),
262            0,
263            5,
264        )),
265        optimal_config: serde_json::json!(vec![0, 3, 2, 1, 4, 5]),
266        optimal_value: serde_json::json!(true),
267    }]
268}
269
270// Use Bjorklund (2014) O*(1.657^n) as best known for general undirected graphs
271crate::impl_random_generate!(
272    HamiltonianPathBetweenTwoVertices<SimpleGraph>,
273    HamiltonianPathBetweenTwoVerticesRandomSpec,
274    |spec| {
275        if spec.num_vertices < 2 {
276            return Err("num_vertices must be at least 2".to_string().into());
277        }
278        let source = spec.source_vertex.unwrap_or(0);
279        let sink = spec.target_vertex.unwrap_or(spec.num_vertices - 1);
280        if source >= spec.num_vertices || sink >= spec.num_vertices || source == sink {
281            return Err(
282                "source_vertex and target_vertex must be distinct valid vertices"
283                    .to_string()
284                    .into(),
285            );
286        }
287        let graph = crate::random::SimpleGraphRandomSpec {
288            num_vertices: spec.num_vertices,
289            edge_prob: spec.edge_prob,
290            seed: spec.seed,
291        }
292        .graph()?;
293        Ok(HamiltonianPathBetweenTwoVertices::new(graph, source, sink))
294    }
295);
296
297crate::declare_variants! {
298    default HamiltonianPathBetweenTwoVertices<SimpleGraph> => "1.657^num_vertices" random,
299}
300
301crate::register_brute_force! {
302    HamiltonianPathBetweenTwoVertices<SimpleGraph>,
303}
304
305#[cfg(test)]
306#[path = "../../unit_tests/models/graph/hamiltonian_path_between_two_vertices.rs"]
307mod tests;
problemreductions/models/graph/hamiltonian_path_between_two_vertices.rs

problemreductions/models/graph/
hamiltonian_path_between_two_vertices.rs
