problemreductions/rules/
hamiltoniancircuit_stackercrane.rs

1//! Reduction from HamiltonianCircuit to StackerCrane.
2//!
3//! Based on the vertex-splitting construction of Frederickson, Hecht & Kim (1978).
4//! Each vertex v_i is split into v_i^in (= 2i) and v_i^out (= 2i+1). A mandatory
5//! directed arc (v_i^in → v_i^out) of length 1 is added for each vertex. For each
6//! undirected edge {v_i, v_j} in the source graph, two undirected connector edges
7//! {v_i^out, v_j^in} and {v_j^out, v_i^in} of length 1 are added.
8//!
9//! The source graph has a Hamiltonian circuit iff the optimal Stacker Crane tour
10//! cost equals 2n (n arcs of cost 1 plus n single-hop connectors of cost 1).
11//! Using connector length 1 (rather than 0) ensures that multi-hop connector
12//! paths cost strictly more than single-hop ones, so every optimal permutation
13//! corresponds to a valid Hamiltonian circuit.
14
15use crate::models::graph::HamiltonianCircuit;
16use crate::models::misc::StackerCrane;
17use crate::reduction;
18use crate::rules::traits::{ReduceTo, ReductionResult};
19use crate::topology::{Graph, SimpleGraph};
20
21/// Result of reducing HamiltonianCircuit to StackerCrane.
22#[derive(Debug, Clone)]
23pub struct ReductionHamiltonianCircuitToStackerCrane {
24    target: StackerCrane,
25}
26
27impl ReductionResult for ReductionHamiltonianCircuitToStackerCrane {
28    type Source = HamiltonianCircuit<SimpleGraph>;
29    type Target = StackerCrane;
30
31    fn target_problem(&self) -> &Self::Target {
32        &self.target
33    }
34
35    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
36        // The target config is a permutation of arc indices.
37        // Arc i corresponds to original vertex i (arc from 2i to 2i+1).
38        // The permutation order directly gives the Hamiltonian circuit vertex order.
39        target_solution.to_vec()
40    }
41}
42
43#[reduction(
44    overhead = {
45        num_vertices = "2 * num_vertices",
46        num_arcs = "num_vertices",
47        num_edges = "2 * num_edges",
48    }
49)]
50impl ReduceTo<StackerCrane> for HamiltonianCircuit<SimpleGraph> {
51    type Result = ReductionHamiltonianCircuitToStackerCrane;
52
53    fn reduce_to(&self) -> Self::Result {
54        let n = self.num_vertices();
55
56        // Each vertex i becomes two vertices: 2i (in) and 2i+1 (out).
57        let target_num_vertices = 2 * n;
58
59        // One mandatory arc per original vertex: (2i, 2i+1) with length 1.
60        let arcs: Vec<(usize, usize)> = (0..n).map(|i| (2 * i, 2 * i + 1)).collect();
61        let arc_lengths: Vec<i32> = vec![1; n];
62
63        // For each original edge {u, v}, add two undirected connector edges:
64        //   {u^out, v^in} = {2u+1, 2v}  with length 1
65        //   {v^out, u^in} = {2v+1, 2u}  with length 1
66        // Using length 1 (not 0) prevents multi-hop zero-cost shortcuts that
67        // would create optimal SC permutations not corresponding to valid HCs.
68        let mut edges = Vec::new();
69        let mut edge_lengths = Vec::new();
70        for (u, v) in self.graph().edges() {
71            edges.push((2 * u + 1, 2 * v));
72            edge_lengths.push(1);
73            edges.push((2 * v + 1, 2 * u));
74            edge_lengths.push(1);
75        }
76
77        let target = StackerCrane::new(target_num_vertices, arcs, edges, arc_lengths, edge_lengths);
78
79        ReductionHamiltonianCircuitToStackerCrane { target }
80    }
81}
82
83#[cfg(feature = "example-db")]
84pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
85    use crate::export::SolutionPair;
86
87    vec![crate::example_db::specs::RuleExampleSpec {
88        id: "hamiltoniancircuit_to_stackercrane",
89        build: || {
90            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
91            crate::example_db::specs::rule_example_with_witness::<_, StackerCrane>(
92                source,
93                SolutionPair {
94                    source_config: vec![0, 1, 2, 3],
95                    target_config: vec![0, 1, 2, 3],
96                },
97            )
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/hamiltoniancircuit_stackercrane.rs"]
104mod tests;
problemreductions/rules/hamiltoniancircuit_stackercrane.rs

problemreductions/rules/
hamiltoniancircuit_stackercrane.rs
