problemreductions/models/graph/
hamiltonian_circuit.rs

1//! Hamiltonian Circuit problem implementation.
2//!
3//! The Hamiltonian Circuit problem asks whether a graph contains a cycle
4//! that visits every vertex exactly once and returns to the starting vertex.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::{Problem, SatisfactionProblem};
9use crate::variant::VariantParam;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "HamiltonianCircuit",
15        display_name: "Hamiltonian Circuit",
16        aliases: &["HC"],
17        dimensions: &[
18            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
19        ],
20        module_path: module_path!(),
21        description: "Does the graph contain a Hamiltonian circuit?",
22        fields: &[
23            FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
24        ],
25    }
26}
27
28/// The Hamiltonian Circuit problem.
29///
30/// Given a graph G = (V, E), determine whether there exists a cycle that
31/// visits every vertex exactly once and returns to the starting vertex.
32///
33/// # Type Parameters
34///
35/// * `G` - Graph type (e.g., SimpleGraph)
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::graph::HamiltonianCircuit;
41/// use problemreductions::topology::SimpleGraph;
42/// use problemreductions::{Problem, Solver, BruteForce};
43///
44/// // Square graph (4-cycle) has a Hamiltonian circuit
45/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (0, 3)]);
46/// let problem = HamiltonianCircuit::new(graph);
47///
48/// let solver = BruteForce::new();
49/// let solutions = solver.find_all_satisfying(&problem);
50///
51/// // Verify all solutions are valid Hamiltonian circuits
52/// for sol in &solutions {
53///     assert!(problem.evaluate(sol));
54/// }
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
58pub struct HamiltonianCircuit<G> {
59    /// The underlying graph.
60    graph: G,
61}
62
63impl<G: Graph> HamiltonianCircuit<G> {
64    /// Create a new Hamiltonian Circuit problem from a graph.
65    pub fn new(graph: G) -> Self {
66        Self { graph }
67    }
68
69    /// Get a reference to the underlying graph.
70    pub fn graph(&self) -> &G {
71        &self.graph
72    }
73
74    /// Get the number of vertices in the underlying graph.
75    pub fn num_vertices(&self) -> usize {
76        self.graph().num_vertices()
77    }
78
79    /// Get the number of edges in the underlying graph.
80    pub fn num_edges(&self) -> usize {
81        self.graph().num_edges()
82    }
83
84    /// Check if a configuration is a valid Hamiltonian circuit.
85    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
86        is_valid_hamiltonian_circuit(&self.graph, config)
87    }
88}
89
90impl<G> Problem for HamiltonianCircuit<G>
91where
92    G: Graph + VariantParam,
93{
94    const NAME: &'static str = "HamiltonianCircuit";
95    type Metric = bool;
96
97    fn variant() -> Vec<(&'static str, &'static str)> {
98        crate::variant_params![G]
99    }
100
101    fn dims(&self) -> Vec<usize> {
102        let n = self.graph.num_vertices();
103        vec![n; n]
104    }
105
106    fn evaluate(&self, config: &[usize]) -> bool {
107        is_valid_hamiltonian_circuit(&self.graph, config)
108    }
109}
110
111/// Check if a configuration represents a valid Hamiltonian circuit in the graph.
112///
113/// A valid Hamiltonian circuit is a permutation of the vertices such that
114/// consecutive vertices in the permutation are adjacent in the graph,
115/// including a closing edge from the last vertex back to the first.
116pub(crate) fn is_valid_hamiltonian_circuit<G: Graph>(graph: &G, config: &[usize]) -> bool {
117    let n = graph.num_vertices();
118    if n < 3 || config.len() != n {
119        return false;
120    }
121
122    // Check that config is a valid permutation of 0..n
123    let mut seen = vec![false; n];
124    for &v in config {
125        if v >= n || seen[v] {
126            return false;
127        }
128        seen[v] = true;
129    }
130
131    // Check that consecutive vertices (including wrap-around) are connected by edges
132    for i in 0..n {
133        let u = config[i];
134        let v = config[(i + 1) % n];
135        if !graph.has_edge(u, v) {
136            return false;
137        }
138    }
139
140    true
141}
142
143impl<G: Graph + VariantParam> SatisfactionProblem for HamiltonianCircuit<G> {}
144
145#[cfg(feature = "example-db")]
146pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
147    vec![crate::example_db::specs::ModelExampleSpec {
148        id: "hamiltonian_circuit_simplegraph",
149        // Prism graph (triangular prism): 6 vertices, 9 edges
150        instance: Box::new(HamiltonianCircuit::new(SimpleGraph::new(
151            6,
152            vec![
153                (0, 1),
154                (1, 2),
155                (2, 0),
156                (3, 4),
157                (4, 5),
158                (5, 3),
159                (0, 3),
160                (1, 4),
161                (2, 5),
162            ],
163        ))),
164        optimal_config: vec![0, 1, 2, 5, 4, 3],
165        optimal_value: serde_json::json!(true),
166    }]
167}
168
169crate::declare_variants! {
170    default sat HamiltonianCircuit<SimpleGraph> => "1.657^num_vertices",
171}
172
173#[cfg(test)]
174#[path = "../../unit_tests/models/graph/hamiltonian_circuit.rs"]
175mod tests;
problemreductions/models/graph/hamiltonian_circuit.rs

problemreductions/models/graph/
hamiltonian_circuit.rs
