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_solution(self.target_problem(), target_solution)?;
31
32        crate::rules::graph_helpers::edges_to_cycle_order(self.target.graph(), target_solution)
33    }
34}
35
36#[reduction(
37    transform = exact {
38        num_vertices = "num_vertices",
39        num_edges = "num_vertices * (num_vertices - 1) / 2",
40    }
41)]
42impl ReduceTo<BottleneckTravelingSalesman> for HamiltonianCircuit<SimpleGraph> {
43    type Result = ReductionHamiltonianCircuitToBottleneckTravelingSalesman;
44
45    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
46        let num_vertices = self.num_vertices();
47        let target_graph = SimpleGraph::complete(num_vertices);
48        let weights = target_graph
49            .edges()
50            .into_iter()
51            .map(|(u, v)| if self.graph().has_edge(u, v) { 1 } else { 2 })
52            .collect();
53        let target = BottleneckTravelingSalesman::new(target_graph, weights);
54
55        Ok(ReductionHamiltonianCircuitToBottleneckTravelingSalesman { target })
56    }
57}
58
59#[cfg(feature = "example-db")]
60pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
61    use crate::export::SolutionPair;
62
63    vec![crate::example_db::specs::RuleExampleSpec {
64        id: "hamiltoniancircuit_to_bottlenecktravelingsalesman",
65        build: || {
66            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
67            crate::example_db::specs::rule_example_with_witness::<_, BottleneckTravelingSalesman>(
68                source,
69                SolutionPair {
70                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
71                    target_config: serde_json::json!(vec![true, false, true, true, false, true]),
72                },
73            )
74        },
75    }]
76}
77
78#[cfg(test)]
79#[path = "../unit_tests/rules/hamiltoniancircuit_bottlenecktravelingsalesman.rs"]
80mod tests;
problemreductions/rules/hamiltoniancircuit_bottlenecktravelingsalesman.rs

problemreductions/rules/
hamiltoniancircuit_bottlenecktravelingsalesman.rs
