problemreductions/rules/
hamiltoniancircuit_bottlenecktravelingsalesman.rs

1//! Reduction from HamiltonianCircuit to BottleneckTravelingSalesman.
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 optimal bottleneck tour equals 1 iff the source graph contains a Hamiltonian circuit.
6
7use crate::models::graph::{BottleneckTravelingSalesman, HamiltonianCircuit};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11
12/// Result of reducing HamiltonianCircuit to BottleneckTravelingSalesman.
13#[derive(Debug, Clone)]
14pub struct ReductionHamiltonianCircuitToBottleneckTravelingSalesman {
15    target: BottleneckTravelingSalesman,
16}
17
18impl ReductionResult for ReductionHamiltonianCircuitToBottleneckTravelingSalesman {
19    type Source = HamiltonianCircuit<SimpleGraph>;
20    type Target = BottleneckTravelingSalesman;
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
43    for ReductionHamiltonianCircuitToBottleneckTravelingSalesman
44{
45    type Source = HamiltonianCircuit<SimpleGraph>;
46    type Target = BottleneckTravelingSalesman;
47
48    fn target_problem(&self) -> &Self::Target {
49        &self.target
50    }
51
52    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
53        crate::types::Or(value.0 == Some(1))
54    }
55}
56
57#[reduction(
58    transform = exact {
59        num_vertices = "num_vertices",
60        num_edges = "num_vertices * (num_vertices - 1) / 2",
61    }
62)]
63impl ReduceTo<BottleneckTravelingSalesman> for HamiltonianCircuit<SimpleGraph> {
64    type Result = ReductionHamiltonianCircuitToBottleneckTravelingSalesman;
65
66    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
67        let num_vertices = self.num_vertices();
68        let target_graph = SimpleGraph::complete(num_vertices);
69        let weights = target_graph
70            .edges()
71            .into_iter()
72            .map(|(u, v)| if self.graph().has_edge(u, v) { 1 } else { 2 })
73            .collect();
74        let target = BottleneckTravelingSalesman::new(target_graph, weights);
75
76        Ok(ReductionHamiltonianCircuitToBottleneckTravelingSalesman { target })
77    }
78}
79
80#[cfg(feature = "example-db")]
81pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
82    use crate::export::SolutionPair;
83
84    vec![crate::example_db::specs::RuleExampleSpec {
85        id: "hamiltoniancircuit_to_bottlenecktravelingsalesman",
86        build: || {
87            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
88            crate::example_db::specs::rule_example_with_witness::<_, BottleneckTravelingSalesman>(
89                source,
90                SolutionPair {
91                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
92                    target_config: serde_json::json!(vec![true, false, true, true, false, true]),
93                },
94            )
95        },
96    }]
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/hamiltoniancircuit_bottlenecktravelingsalesman.rs"]
101mod tests;
problemreductions/rules/hamiltoniancircuit_bottlenecktravelingsalesman.rs

problemreductions/rules/
hamiltoniancircuit_bottlenecktravelingsalesman.rs
