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::graph::{HamiltonianCircuit, LongestCircuit};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11
12/// Result of reducing HamiltonianCircuit to LongestCircuit.
13#[derive(Debug, Clone)]
14pub struct ReductionHamiltonianCircuitToLongestCircuit {
15    target: LongestCircuit<SimpleGraph, i32>,
16}
17
18impl ReductionResult for ReductionHamiltonianCircuitToLongestCircuit {
19    type Source = HamiltonianCircuit<SimpleGraph>;
20    type Target = LongestCircuit<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_edges",
35    }
36)]
37impl ReduceTo<LongestCircuit<SimpleGraph, i32>> for HamiltonianCircuit<SimpleGraph> {
38    type Result = ReductionHamiltonianCircuitToLongestCircuit;
39
40    fn reduce_to(&self) -> Self::Result {
41        let n = self.num_vertices();
42        let edges = self.graph().edges();
43        let target = LongestCircuit::new(SimpleGraph::new(n, edges), vec![1i32; self.num_edges()]);
44        ReductionHamiltonianCircuitToLongestCircuit { target }
45    }
46}
47
48#[cfg(feature = "example-db")]
49pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
50    use crate::export::SolutionPair;
51
52    vec![crate::example_db::specs::RuleExampleSpec {
53        id: "hamiltoniancircuit_to_longestcircuit",
54        build: || {
55            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
56            crate::example_db::specs::rule_example_with_witness::<_, LongestCircuit<SimpleGraph, i32>>(
57                source,
58                SolutionPair {
59                    source_config: vec![0, 1, 2, 3],
60                    target_config: vec![1, 1, 1, 1],
61                },
62            )
63        },
64    }]
65}
66
67#[cfg(test)]
68#[path = "../unit_tests/rules/hamiltoniancircuit_longestcircuit.rs"]
69mod tests;
problemreductions/rules/hamiltoniancircuit_longestcircuit.rs

problemreductions/rules/
hamiltoniancircuit_longestcircuit.rs
