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, i32>,
16}
17
18impl ReductionResult for ReductionHamiltonianCircuitToTravelingSalesman {
19    type Source = HamiltonianCircuit<SimpleGraph>;
20    type Target = TravelingSalesman<SimpleGraph, i32>;
21
22    fn target_problem(&self) -> &Self::Target {
23        &self.target
24    }
25
26    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
27        crate::rules::graph_helpers::edges_to_cycle_order(self.target.graph(), target_solution)
28    }
29}
30
31#[reduction(
32    overhead = {
33        num_vertices = "num_vertices",
34        num_edges = "num_vertices * (num_vertices - 1) / 2",
35    }
36)]
37impl ReduceTo<TravelingSalesman<SimpleGraph, i32>> for HamiltonianCircuit<SimpleGraph> {
38    type Result = ReductionHamiltonianCircuitToTravelingSalesman;
39
40    fn reduce_to(&self) -> Self::Result {
41        let num_vertices = self.num_vertices();
42        let target_graph = SimpleGraph::complete(num_vertices);
43        let weights = target_graph
44            .edges()
45            .into_iter()
46            .map(|(u, v)| if self.graph().has_edge(u, v) { 1 } else { 2 })
47            .collect();
48        let target = TravelingSalesman::new(target_graph, weights);
49
50        ReductionHamiltonianCircuitToTravelingSalesman { target }
51    }
52}
53
54#[cfg(feature = "example-db")]
55pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
56    use crate::export::SolutionPair;
57
58    vec![crate::example_db::specs::RuleExampleSpec {
59        id: "hamiltoniancircuit_to_travelingsalesman",
60        build: || {
61            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
62            crate::example_db::specs::rule_example_with_witness::<
63                _,
64                TravelingSalesman<SimpleGraph, i32>,
65            >(
66                source,
67                SolutionPair {
68                    source_config: vec![0, 1, 2, 3],
69                    target_config: vec![1, 0, 1, 1, 0, 1],
70                },
71            )
72        },
73    }]
74}
75
76#[cfg(test)]
77#[path = "../unit_tests/rules/hamiltoniancircuit_travelingsalesman.rs"]
78mod tests;
problemreductions/rules/hamiltoniancircuit_travelingsalesman.rs

problemreductions/rules/
hamiltoniancircuit_travelingsalesman.rs
