problemreductions/rules/
hamiltoniancircuit_longestcircuit.rs

1//! Reduction from HamiltonianCircuit to LongestCircuit.
2//!
3//! Given an HC instance G = (V, E), construct an LC instance on the same graph
4//! with unit edge weights. A Hamiltonian circuit exists iff the optimal circuit
5//! length equals |V|.
6
7use crate::models::graph::{HamiltonianCircuit, LongestCircuit};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11
12/// Result of reducing HamiltonianCircuit to LongestCircuit.
13#[derive(Debug, Clone)]
14pub struct ReductionHamiltonianCircuitToLongestCircuit {
15    target: LongestCircuit<SimpleGraph, i64>,
16}
17
18impl ReductionResult for ReductionHamiltonianCircuitToLongestCircuit {
19    type Source = HamiltonianCircuit<SimpleGraph>;
20    type Target = LongestCircuit<SimpleGraph, i64>;
21
22    fn target_problem(&self) -> &Self::Target {
23        &self.target
24    }
25
26    fn extract_solution(
27        &self,
28        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
29    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
30        let value =
31            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
32        if !crate::rules::AggregateReductionResult::extract_value(self, value).0 {
33            return Err(crate::rules::ExtractionError::invalid(
34                "target circuit does not certify a Hamiltonian circuit",
35            ));
36        }
37
38        crate::rules::graph_helpers::edges_to_cycle_order(self.target.graph(), target_solution)
39    }
40}
41
42impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToLongestCircuit {
43    type Source = HamiltonianCircuit<SimpleGraph>;
44    type Target = LongestCircuit<SimpleGraph, i64>;
45
46    fn target_problem(&self) -> &Self::Target {
47        &self.target
48    }
49
50    fn extract_value(&self, target_value: crate::types::Max<i64>) -> crate::types::Or {
51        crate::types::Or(
52            target_value
53                .0
54                .is_some_and(|length| usize::try_from(length) == Ok(self.target.num_vertices())),
55        )
56    }
57}
58
59#[reduction(
60    aggregate = custom,
61    transform = exact {
62        num_vertices = "num_vertices",
63        num_edges = "num_edges",
64    }
65)]
66impl ReduceTo<LongestCircuit<SimpleGraph, i64>> for HamiltonianCircuit<SimpleGraph> {
67    type Result = ReductionHamiltonianCircuitToLongestCircuit;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let n = self.num_vertices();
71        let edges = self.graph().edges();
72        let target = LongestCircuit::new(SimpleGraph::new(n, edges), vec![1i64; self.num_edges()]);
73        Ok(ReductionHamiltonianCircuitToLongestCircuit { target })
74    }
75}
76
77#[cfg(feature = "example-db")]
78pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
79    use crate::export::SolutionPair;
80
81    vec![crate::example_db::specs::RuleExampleSpec {
82        id: "hamiltoniancircuit_to_longestcircuit",
83        build: || {
84            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
85            crate::example_db::specs::rule_example_with_witness::<_, LongestCircuit<SimpleGraph, i64>>(
86                source,
87                SolutionPair {
88                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
89                    target_config: serde_json::json!(vec![true, true, true, true]),
90                },
91            )
92        },
93    }]
94}
95
96#[cfg(test)]
97#[path = "../unit_tests/rules/hamiltoniancircuit_longestcircuit.rs"]
98mod tests;
problemreductions/rules/hamiltoniancircuit_longestcircuit.rs

problemreductions/rules/
hamiltoniancircuit_longestcircuit.rs
