problemreductions/models/graph/
directed_hamiltonian_path.rs

1//! Directed Hamiltonian Path problem implementation.
2//!
3//! The Directed Hamiltonian Path problem asks whether a directed graph contains
4//! a simple directed path that visits every vertex exactly once.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::topology::DirectedGraph;
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "DirectedHamiltonianPath",
14        display_name: "Directed Hamiltonian Path",
15        aliases: &["DHP"],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Graph,
18        module_path: module_path!(),
19        description: "Does the directed graph contain a Hamiltonian path?",
20        fields: &[
21            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "The directed graph G=(V,A)" },
22        ],
23    }
24}
25
26/// The Directed Hamiltonian Path problem.
27///
28/// Given a directed graph G = (V, A), determine whether G contains a Hamiltonian path,
29/// i.e., a simple directed path that visits every vertex exactly once following arc
30/// directions.
31///
32/// # Representation
33///
34/// A configuration encodes a permutation using the Lehmer code:
35/// `dims() = [n, n-1, ..., 2, 1]`, yielding `n!` reachable configurations.
36/// Each configuration is decoded to a permutation of `0..n`, and a solution is
37/// valid when every consecutive pair `(path[i], path[i+1])` is an arc in the
38/// directed graph.
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::graph::DirectedHamiltonianPath;
44/// use problemreductions::topology::DirectedGraph;
45/// use problemreductions::{Problem, BruteForce};
46///
47/// // Simple directed path: 0->1->2->3
48/// let graph = DirectedGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
49/// let problem = DirectedHamiltonianPath::new(graph);
50///
51/// let solver = BruteForce::new();
52/// let solution = solver.solve(&problem).unwrap();
53/// assert!(solution.is_some());
54/// ```
55#[derive(Debug, Clone, Serialize, Deserialize)]
56pub struct DirectedHamiltonianPath {
57    graph: DirectedGraph,
58}
59
60impl DirectedHamiltonianPath {
61    /// Create a new Directed Hamiltonian Path problem from a directed graph.
62    pub fn new(graph: DirectedGraph) -> Self {
63        Self { graph }
64    }
65
66    /// Get a reference to the underlying directed graph.
67    pub fn graph(&self) -> &DirectedGraph {
68        &self.graph
69    }
70
71    /// Get the number of vertices in the directed graph.
72    pub fn num_vertices(&self) -> usize {
73        self.graph.num_vertices()
74    }
75
76    /// Get the number of arcs in the directed graph.
77    pub fn num_arcs(&self) -> usize {
78        self.graph.num_arcs()
79    }
80
81    /// Check if a permutation is a valid directed Hamiltonian path.
82    pub fn is_valid_solution(&self, solution: &[usize]) -> bool {
83        is_valid_directed_hamiltonian_path(&self.graph, solution)
84    }
85}
86
87impl Problem for DirectedHamiltonianPath {
88    const NAME: &'static str = "DirectedHamiltonianPath";
89    type Solution = Vec<usize>;
90    type Value = crate::types::Or;
91
92    crate::problem_parameters![("num_arcs", num_arcs), ("num_vertices", num_vertices),];
93
94    fn variant() -> Vec<(&'static str, &'static str)> {
95        crate::variant_params![]
96    }
97
98    fn evaluate(
99        &self,
100        solution: &Self::Solution,
101    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
102        let n = self.graph.num_vertices();
103        if solution.len() != n {
104            return Err(crate::traits::EvaluationError::InvalidConfiguration(
105                "path ordering length does not match the graph vertices".into(),
106            ));
107        }
108        if solution.iter().any(|&vertex| vertex >= n) {
109            return Err(crate::traits::EvaluationError::InvalidConfiguration(
110                "path ordering contains an out-of-range vertex".into(),
111            ));
112        }
113        Ok(crate::types::Or(is_valid_directed_hamiltonian_path(
114            &self.graph,
115            solution,
116        )))
117    }
118}
119
120impl crate::solvers::BruteForceProblem for DirectedHamiltonianPath {
121    fn dimensions(&self) -> Vec<usize> {
122        lehmer_dims(self.graph.num_vertices())
123    }
124}
125
126/// Returns the Lehmer code dimension vector for `n` items: `[n, n-1, ..., 2, 1]`.
127pub(crate) fn lehmer_dims(n: usize) -> Vec<usize> {
128    (1..=n).rev().collect()
129}
130
131/// Decode a Lehmer code into a permutation.
132///
133/// Given a configuration `code` where `code[i] < n - i`, returns the
134/// corresponding permutation of `0..n`.
135pub(crate) fn decode_lehmer(code: &[usize]) -> Vec<usize> {
136    let n = code.len();
137    let mut available: Vec<usize> = (0..n).collect();
138    let mut perm = Vec::with_capacity(n);
139    for &idx in code {
140        let idx = idx.min(available.len().saturating_sub(1));
141        perm.push(available.remove(idx));
142    }
143    perm
144}
145
146/// Check if a permutation is a valid directed Hamiltonian path.
147///
148/// A valid directed Hamiltonian path visits every vertex exactly once and
149/// every consecutive pair `(perm[i], perm[i+1])` must be an arc in the graph.
150pub(crate) fn is_valid_directed_hamiltonian_path(graph: &DirectedGraph, perm: &[usize]) -> bool {
151    let n = graph.num_vertices();
152    if perm.len() != n {
153        return false;
154    }
155
156    // Check that perm is a valid permutation of 0..n
157    let mut seen = vec![false; n];
158    for &v in perm {
159        if v >= n || seen[v] {
160            return false;
161        }
162        seen[v] = true;
163    }
164
165    // Check that consecutive pairs are directed arcs
166    for i in 0..n.saturating_sub(1) {
167        if !graph.has_arc(perm[i], perm[i + 1]) {
168            return false;
169        }
170    }
171
172    true
173}
174
175#[cfg(feature = "example-db")]
176pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
177    // 6 vertices, arcs from issue #813
178    // Hamiltonian path: [0, 1, 3, 2, 4, 5]
179    let graph = DirectedGraph::new(
180        6,
181        vec![
182            (0, 1),
183            (0, 3),
184            (1, 3),
185            (1, 4),
186            (2, 0),
187            (2, 4),
188            (3, 2),
189            (3, 5),
190            (4, 5),
191            (5, 1),
192        ],
193    );
194    let optimal_perm = vec![0usize, 1, 3, 2, 4, 5];
195    vec![crate::example_db::specs::ModelExampleSpec {
196        id: "directed_hamiltonian_path",
197        instance: Box::new(DirectedHamiltonianPath::new(graph)),
198        optimal_config: serde_json::to_value(optimal_perm)
199            .expect("solution serialization must succeed"),
200        optimal_value: serde_json::json!(true),
201    }]
202}
203
204crate::declare_variants! {
205    default DirectedHamiltonianPath => "num_vertices^2 * 2^num_vertices",
206}
207
208crate::register_brute_force! {
209    DirectedHamiltonianPath decode |_problem: &DirectedHamiltonianPath, indices: Vec<usize>| decode_lehmer(&indices),
210}
211
212#[cfg(test)]
213#[path = "../../unit_tests/models/graph/directed_hamiltonian_path.rs"]
214mod tests;
problemreductions/models/graph/directed_hamiltonian_path.rs

problemreductions/models/graph/
directed_hamiltonian_path.rs
