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::decision::Decision;
8use crate::models::graph::{HamiltonianCircuit, LongestCircuit};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12
13/// Result of reducing HamiltonianCircuit to LongestCircuit.
14#[derive(Debug, Clone)]
15pub struct ReductionHamiltonianCircuitToLongestCircuit {
16    target: Decision<LongestCircuit<SimpleGraph, i64>>,
17}
18
19impl ReductionResult for ReductionHamiltonianCircuitToLongestCircuit {
20    type Source = HamiltonianCircuit<SimpleGraph>;
21    type Target = Decision<LongestCircuit<SimpleGraph, i64>>;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    fn extract_solution(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_witness(
32            self.target_problem(),
33            target_solution,
34            |value| value.0,
35            "target circuit does not certify a Hamiltonian circuit",
36        )?;
37
38        crate::rules::graph_helpers::edges_to_cycle_order(
39            self.target.inner().graph(),
40            target_solution,
41        )
42    }
43}
44
45#[crate::aggregate_reduction(identity)]
46impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToLongestCircuit {}
47
48#[reduction(
49    transform = exact {
50        max_length_bits = "1",
51        num_vertices = "num_vertices",
52        num_edges = "num_edges",
53    }
54)]
55impl ReduceTo<Decision<LongestCircuit<SimpleGraph, i64>>> for HamiltonianCircuit<SimpleGraph> {
56    type Result = ReductionHamiltonianCircuitToLongestCircuit;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let n = self.num_vertices();
60        let edges = self.graph().edges();
61        let target = LongestCircuit::new(SimpleGraph::new(n, edges), vec![1i64; self.num_edges()]);
62        Ok(ReductionHamiltonianCircuitToLongestCircuit {
63            target: Decision::new(
64                target,
65                <Self as ReduceTo<Decision<LongestCircuit<SimpleGraph, i64>>>>::exact_i64(
66                    n,
67                    "encoding the circuit bound",
68                )?,
69            ),
70        })
71    }
72}
73
74#[cfg(feature = "example-db")]
75pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
76    use crate::export::SolutionPair;
77
78    vec![crate::example_db::specs::RuleExampleSpec {
79        id: "hamiltoniancircuit_to_longestcircuit",
80        build: || {
81            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
82            crate::example_db::specs::rule_example_with_witness::<
83                _,
84                Decision<LongestCircuit<SimpleGraph, i64>>,
85            >(
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
