problemreductions/rules/
hamiltoniancircuit_stackercrane.rs

1//! Reduction from HamiltonianCircuit to StackerCrane.
2//!
3//! Vertex splitting into the mixed routing formulation of StackerCrane.
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 and n >= 3 (n service arcs and n unit-cost connectors).
11//! Using connector length 1 (rather than 0) ensures that multi-hop connector
12//! paths cost strictly more than single-hop ones. Only permutations attaining
13//! this lower bound certify a Hamiltonian circuit.
14
15use crate::models::decision::Decision;
16use crate::models::graph::HamiltonianCircuit;
17use crate::models::misc::StackerCrane;
18use crate::reduction;
19use crate::rules::traits::{ReduceTo, ReductionResult};
20use crate::topology::{Graph, SimpleGraph};
21
22/// Result of reducing HamiltonianCircuit to StackerCrane.
23#[derive(Debug, Clone)]
24pub struct ReductionHamiltonianCircuitToStackerCrane {
25    target: Decision<StackerCrane>,
26}
27
28impl ReductionResult for ReductionHamiltonianCircuitToStackerCrane {
29    type Source = HamiltonianCircuit<SimpleGraph>;
30    type Target = Decision<StackerCrane>;
31
32    fn target_problem(&self) -> &Self::Target {
33        &self.target
34    }
35
36    fn extract_solution(
37        &self,
38        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
39    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
40        crate::rules::traits::validate_target_witness(
41            self.target_problem(),
42            target_solution,
43            |value| value.0,
44            "target tour does not certify a Hamiltonian circuit",
45        )?;
46        // Service arc i corresponds to source vertex i.
47        Ok(target_solution.to_vec())
48    }
49}
50
51#[crate::aggregate_reduction(identity)]
52impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToStackerCrane {}
53
54#[reduction(
55    transform = exact {
56        num_vertices = "2 * num_vertices",
57        num_arcs = "num_vertices",
58        num_edges = "2 * num_edges",
59    }
60)]
61impl ReduceTo<Decision<StackerCrane>> for HamiltonianCircuit<SimpleGraph> {
62    type Result = ReductionHamiltonianCircuitToStackerCrane;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.num_vertices();
66
67        // Each vertex i becomes two vertices: 2i (in) and 2i+1 (out).
68        let (target_num_vertices, target_num_edges) = split_graph_dimensions(n, self.num_edges())?;
69
70        // One mandatory arc per original vertex: (2i, 2i+1) with length 1.
71        let arcs: Vec<(usize, usize)> = (0..n).map(|i| (2 * i, 2 * i + 1)).collect();
72        let arc_lengths: Vec<i64> = vec![1; n];
73
74        // For each original edge {u, v}, add two undirected connector edges:
75        //   {u^out, v^in} = {2u+1, 2v}  with length 1
76        //   {v^out, u^in} = {2v+1, 2u}  with length 1
77        // Using length 1 (not 0) prevents multi-hop zero-cost shortcuts that
78        // would create optimal SC permutations not corresponding to valid HCs.
79        let mut edges = Vec::with_capacity(target_num_edges);
80        let mut edge_lengths = Vec::with_capacity(target_num_edges);
81        for (u, v) in self.graph().edges() {
82            edges.push((2 * u + 1, 2 * v));
83            edge_lengths.push(1);
84            edges.push((2 * v + 1, 2 * u));
85            edge_lengths.push(1);
86        }
87
88        let target =
89            StackerCrane::try_new(target_num_vertices, arcs, edges, arc_lengths, edge_lengths)
90                .map_err(<Self as ReduceTo<Decision<StackerCrane>>>::target_construction)?;
91
92        Ok(ReductionHamiltonianCircuitToStackerCrane {
93            target: Decision::new(
94                target,
95                if n < 3 {
96                    -1
97                } else {
98                    <Self as ReduceTo<Decision<StackerCrane>>>::exact_i64(
99                        target_num_vertices,
100                        "encoding the route bound",
101                    )?
102                },
103            ),
104        })
105    }
106}
107
108/// Check split indices and every finite service-order cost before allocation.
109fn split_graph_dimensions(
110    n: usize,
111    m: usize,
112) -> Result<(usize, usize), crate::rules::ReductionError> {
113    type Source = HamiltonianCircuit<SimpleGraph>;
114    let overflow = || {
115        crate::rules::ReductionError::integer_overflow::<Source, Decision<StackerCrane>>(
116            "encoding split graph dimensions and route costs",
117        )
118    };
119    let vertices = n.checked_mul(2).ok_or_else(overflow)?;
120    let edges = m.checked_mul(2).ok_or_else(overflow)?;
121    // A shortest connector is simple and has at most 2n-1 unit steps.
122    // The n services therefore cost at most n * (1 + (2n-1)).
123    let cost_bound = n.checked_mul(vertices).ok_or_else(overflow)?;
124    <Source as ReduceTo<Decision<StackerCrane>>>::exact_i64(
125        cost_bound,
126        "bounding split graph route costs",
127    )?;
128    Ok((vertices, edges))
129}
130
131#[cfg(feature = "example-db")]
132pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
133    use crate::export::SolutionPair;
134
135    vec![crate::example_db::specs::RuleExampleSpec {
136        id: "hamiltoniancircuit_to_stackercrane",
137        build: || {
138            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
139            crate::example_db::specs::rule_example_with_witness::<_, Decision<StackerCrane>>(
140                source,
141                SolutionPair {
142                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
143                    target_config: serde_json::json!(vec![0, 1, 2, 3]),
144                },
145            )
146        },
147    }]
148}
149
150#[cfg(test)]
151#[path = "../unit_tests/rules/hamiltoniancircuit_stackercrane.rs"]
152mod tests;
problemreductions/rules/hamiltoniancircuit_stackercrane.rs

problemreductions/rules/
hamiltoniancircuit_stackercrane.rs
