problemreductions/rules/
hamiltoniancircuit_travelingsalesman.rs

1//! Reduction from HamiltonianCircuit to TravelingSalesman.
2//!
3//! The standard construction embeds the source graph into the complete graph on the
4//! same vertex set, assigning weight 1 to source edges and weight 2 to non-edges.
5//! The target optimum is exactly n iff the source graph contains a Hamiltonian circuit.
6
7use crate::models::graph::{HamiltonianCircuit, TravelingSalesman};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11
12/// Result of reducing HamiltonianCircuit to TravelingSalesman.
13#[derive(Debug, Clone)]
14pub struct ReductionHamiltonianCircuitToTravelingSalesman {
15    target: TravelingSalesman<SimpleGraph, i64>,
16}
17
18impl ReductionResult for ReductionHamiltonianCircuitToTravelingSalesman {
19    type Source = HamiltonianCircuit<SimpleGraph>;
20    type Target = TravelingSalesman<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        crate::rules::traits::validate_target_witness(
31            self.target_problem(),
32            target_solution,
33            |value| crate::rules::AggregateReductionResult::extract_value(self, value).0,
34            "target witness does not certify a YES answer for the source",
35        )?;
36
37        crate::rules::graph_helpers::edges_to_cycle_order(self.target.graph(), target_solution)
38    }
39}
40
41#[crate::aggregate_reduction]
42impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToTravelingSalesman {
43    type Source = HamiltonianCircuit<SimpleGraph>;
44    type Target = TravelingSalesman<SimpleGraph, i64>;
45
46    fn target_problem(&self) -> &Self::Target {
47        &self.target
48    }
49
50    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
51        crate::types::Or(
52            value
53                .0
54                .is_some_and(|cost| i128::from(cost) == self.target.num_vertices() as i128),
55        )
56    }
57}
58
59#[reduction(
60    transform = exact {
61        num_vertices = "num_vertices",
62        num_edges = "num_vertices * (num_vertices - 1) / 2",
63    }
64)]
65impl ReduceTo<TravelingSalesman<SimpleGraph, i64>> for HamiltonianCircuit<SimpleGraph> {
66    type Result = ReductionHamiltonianCircuitToTravelingSalesman;
67
68    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
69        let num_vertices = self.num_vertices();
70        let target_graph = SimpleGraph::complete(num_vertices);
71        let weights = target_graph
72            .edges()
73            .into_iter()
74            .map(|(u, v)| if self.graph().has_edge(u, v) { 1 } else { 2 })
75            .collect();
76        let target = TravelingSalesman::new(target_graph, weights);
77
78        Ok(ReductionHamiltonianCircuitToTravelingSalesman { target })
79    }
80}
81
82#[cfg(feature = "example-db")]
83pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
84    use crate::export::SolutionPair;
85
86    vec![crate::example_db::specs::RuleExampleSpec {
87        id: "hamiltoniancircuit_to_travelingsalesman",
88        build: || {
89            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
90            crate::example_db::specs::rule_example_with_witness::<
91                _,
92                TravelingSalesman<SimpleGraph, i64>,
93            >(
94                source,
95                SolutionPair {
96                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
97                    target_config: serde_json::json!(vec![true, false, true, true, false, true]),
98                },
99            )
100        },
101    }]
102}
103
104#[cfg(test)]
105#[path = "../unit_tests/rules/hamiltoniancircuit_travelingsalesman.rs"]
106mod tests;
problemreductions/rules/hamiltoniancircuit_travelingsalesman.rs

problemreductions/rules/
hamiltoniancircuit_travelingsalesman.rs
