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(try_from = "HamiltonianPathBetweenTwoVerticesData<G>")]
73#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
74pub struct HamiltonianPathBetweenTwoVertices<G> {
75    graph: G,
76    source_vertex: usize,
77    target_vertex: usize,
78}
79
80#[derive(Deserialize)]
81#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
82struct HamiltonianPathBetweenTwoVerticesData<G> {
83    graph: G,
84    source_vertex: usize,
85    target_vertex: usize,
86}
87
88impl<G> TryFrom<HamiltonianPathBetweenTwoVerticesData<G>> for HamiltonianPathBetweenTwoVertices<G>
89where
90    G: Graph,
91{
92    type Error = crate::registry::ConstructionError;
93
94    fn try_from(data: HamiltonianPathBetweenTwoVerticesData<G>) -> Result<Self, Self::Error> {
95        Self::try_new(data.graph, data.source_vertex, data.target_vertex)
96    }
97}
98
99#[derive(Debug, Deserialize, crate::CreateSpec)]
100struct HamiltonianPathBetweenTwoVerticesRandomSpec {
101    /// Number of graph vertices.
102    num_vertices: usize,
103    /// Independent edge probability (default: 0.5).
104    edge_prob: Option<f64>,
105    /// Seed for reproducible generation.
106    seed: Option<i64>,
107    /// Path start vertex (default: 0).
108    source_vertex: Option<usize>,
109    /// Path end vertex (default: the final vertex).
110    target_vertex: Option<usize>,
111}
112
113impl<G: Graph> HamiltonianPathBetweenTwoVertices<G> {
114    /// Create a new Hamiltonian Path Between Two Vertices problem.
115    ///
116    /// # Panics
117    ///
118    /// Panics if `source_vertex` or `target_vertex` is out of range, or if they are equal.
119    pub fn new(graph: G, source_vertex: usize, target_vertex: usize) -> Self {
120        Self::try_new(graph, source_vertex, target_vertex).unwrap_or_else(|error| panic!("{error}"))
121    }
122
123    fn try_new(
124        graph: G,
125        source_vertex: usize,
126        target_vertex: usize,
127    ) -> Result<Self, crate::registry::ConstructionError> {
128        let n = graph.num_vertices();
129        if source_vertex >= n {
130            return Err(format!(
131                "source_vertex {source_vertex} out of range for graph with {n} vertices"
132            )
133            .into());
134        }
135        if target_vertex >= n {
136            return Err(format!(
137                "target_vertex {target_vertex} out of range for graph with {n} vertices"
138            )
139            .into());
140        }
141        if source_vertex == target_vertex {
142            return Err("source_vertex and target_vertex must be distinct".into());
143        }
144        Ok(Self {
145            graph,
146            source_vertex,
147            target_vertex,
148        })
149    }
150
151    /// Get a reference to the underlying graph.
152    pub fn graph(&self) -> &G {
153        &self.graph
154    }
155
156    /// Get the source vertex s.
157    pub fn source_vertex(&self) -> usize {
158        self.source_vertex
159    }
160
161    /// Get the target vertex t.
162    pub fn target_vertex(&self) -> usize {
163        self.target_vertex
164    }
165
166    /// Get the number of vertices in the underlying graph.
167    pub fn num_vertices(&self) -> usize {
168        self.graph.num_vertices()
169    }
170
171    /// Get the number of edges in the underlying graph.
172    pub fn num_edges(&self) -> usize {
173        self.graph.num_edges()
174    }
175
176    /// Check if a configuration is a valid Hamiltonian s-t path.
177    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
178        is_valid_hamiltonian_st_path(&self.graph, config, self.source_vertex, self.target_vertex)
179    }
180}
181
182impl<G> Problem for HamiltonianPathBetweenTwoVertices<G>
183where
184    G: Graph + VariantParam,
185{
186    const NAME: &'static str = "HamiltonianPathBetweenTwoVertices";
187    type Solution = Vec<usize>;
188    type Value = crate::types::Or;
189
190    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
191
192    fn variant() -> Vec<(&'static str, &'static str)> {
193        crate::variant_params![G]
194    }
195
196    fn evaluate(
197        &self,
198        config: &Self::Solution,
199    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
200        let n = self.graph.num_vertices();
201        if config.len() != n {
202            return Err(crate::traits::EvaluationError::InvalidConfiguration(
203                "path ordering length does not match the graph vertices".into(),
204            ));
205        }
206        if config.iter().any(|&vertex| vertex >= n) {
207            return Err(crate::traits::EvaluationError::InvalidConfiguration(
208                "path ordering contains an out-of-range vertex".into(),
209            ));
210        }
211        Ok({
212            crate::types::Or(is_valid_hamiltonian_st_path(
213                &self.graph,
214                config,
215                self.source_vertex,
216                self.target_vertex,
217            ))
218        })
219    }
220}
221
222impl<G> crate::solvers::BruteForceProblem for HamiltonianPathBetweenTwoVertices<G>
223where
224    G: Graph + VariantParam,
225{
226    fn dimensions(&self) -> Vec<usize> {
227        let n = self.graph.num_vertices();
228        vec![n; n]
229    }
230}
231
232/// Check if a configuration represents a valid Hamiltonian s-t path in the graph.
233///
234/// A valid Hamiltonian s-t path is a permutation of all vertices such that:
235/// - The first element is `source`
236/// - The last element is `target`
237/// - Consecutive vertices in the permutation are adjacent in the graph
238pub(crate) fn is_valid_hamiltonian_st_path<G: Graph>(
239    graph: &G,
240    config: &[usize],
241    source: usize,
242    target: usize,
243) -> bool {
244    let n = graph.num_vertices();
245    if config.len() != n {
246        return false;
247    }
248
249    // Check that config is a valid permutation of 0..n
250    let mut seen = vec![false; n];
251    for &v in config {
252        if v >= n || seen[v] {
253            return false;
254        }
255        seen[v] = true;
256    }
257
258    // Check endpoint constraints
259    if config[0] != source || config[n - 1] != target {
260        return false;
261    }
262
263    // Check consecutive vertices are adjacent
264    for i in 0..n.saturating_sub(1) {
265        if !graph.has_edge(config[i], config[i + 1]) {
266            return false;
267        }
268    }
269
270    true
271}
272
273#[cfg(feature = "example-db")]
274pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
275    // Instance from issue #831: 6 vertices, s=0, t=5
276    // Hamiltonian s-t path: [0, 3, 2, 1, 4, 5]
277    vec![crate::example_db::specs::ModelExampleSpec {
278        id: "hamiltonian_path_between_two_vertices_simplegraph",
279        instance: Box::new(HamiltonianPathBetweenTwoVertices::new(
280            SimpleGraph::new(
281                6,
282                vec![
283                    (0, 1),
284                    (0, 3),
285                    (1, 2),
286                    (1, 4),
287                    (2, 5),
288                    (3, 4),
289                    (4, 5),
290                    (2, 3),
291                ],
292            ),
293            0,
294            5,
295        )),
296        optimal_config: serde_json::json!(vec![0, 3, 2, 1, 4, 5]),
297        optimal_value: serde_json::json!(true),
298    }]
299}
300
301// Use Bjorklund (2014) O*(1.657^n) as best known for general undirected graphs
302crate::impl_random_generate!(
303    HamiltonianPathBetweenTwoVertices<SimpleGraph>,
304    HamiltonianPathBetweenTwoVerticesRandomSpec,
305    |spec| {
306        if spec.num_vertices < 2 {
307            return Err("num_vertices must be at least 2".to_string().into());
308        }
309        let source = spec.source_vertex.unwrap_or(0);
310        let sink = spec.target_vertex.unwrap_or(spec.num_vertices - 1);
311        if source >= spec.num_vertices || sink >= spec.num_vertices || source == sink {
312            return Err(
313                "source_vertex and target_vertex must be distinct valid vertices"
314                    .to_string()
315                    .into(),
316            );
317        }
318        let graph = crate::random::SimpleGraphRandomSpec {
319            num_vertices: spec.num_vertices,
320            edge_prob: spec.edge_prob,
321            seed: spec.seed,
322        }
323        .graph()?;
324        Ok(HamiltonianPathBetweenTwoVertices::new(graph, source, sink))
325    }
326);
327
328crate::declare_variants! {
329    default HamiltonianPathBetweenTwoVertices<SimpleGraph> => "1.657^num_vertices" random,
330}
331
332crate::register_brute_force! {
333    HamiltonianPathBetweenTwoVertices<SimpleGraph>,
334}
335
336#[cfg(test)]
337#[path = "../../unit_tests/models/graph/hamiltonian_path_between_two_vertices.rs"]
338mod tests;
problemreductions/models/graph/hamiltonian_path_between_two_vertices.rs

problemreductions/models/graph/
hamiltonian_path_between_two_vertices.rs
