problemreductions/rules/
hamiltoniancircuit_strongconnectivityaugmentation.rs

1//! Reduction from HamiltonianCircuit to StrongConnectivityAugmentation.
2//!
3//! Based on the Eswaran & Tarjan (1976) construction: start with an arc-less
4//! digraph on n vertices. For each ordered pair (u, v), create a candidate arc
5//! with weight 1 if {u, v} is an edge in the source graph, and weight 2
6//! otherwise. Set the budget B = n. A Hamiltonian circuit exists in the source
7//! graph if and only if a cost-n strong connectivity augmentation exists using
8//! only weight-1 arcs.
9
10use crate::models::graph::{HamiltonianCircuit, StrongConnectivityAugmentation};
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{DirectedGraph, Graph, SimpleGraph};
14
15/// Result of reducing HamiltonianCircuit to StrongConnectivityAugmentation.
16#[derive(Debug, Clone)]
17pub struct ReductionHamiltonianCircuitToStrongConnectivityAugmentation {
18    target: StrongConnectivityAugmentation<i64>,
19    n: usize,
20}
21
22impl ReductionResult for ReductionHamiltonianCircuitToStrongConnectivityAugmentation {
23    type Source = HamiltonianCircuit<SimpleGraph>;
24    type Target = StrongConnectivityAugmentation<i64>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    fn extract_solution(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        crate::rules::traits::validate_target_witness(
35            self.target_problem(),
36            target_solution,
37            |value| value.0,
38            "target witness is not satisfying",
39        )?;
40
41        Ok({
42            let n = self.n;
43            if n == 0 {
44                return Ok(vec![]);
45            }
46
47            // Build directed adjacency from selected arcs.
48            let candidate_arcs = self.target.candidate_arcs();
49            let mut successors = vec![Vec::new(); n];
50            for (idx, &selected) in target_solution.iter().enumerate() {
51                if selected {
52                    let (u, v, _) = candidate_arcs[idx];
53                    successors[u].push(v);
54                }
55            }
56
57            // Walk the directed cycle starting from vertex 0.
58            let mut order = Vec::with_capacity(n);
59            let mut current = 0;
60            let mut visited = vec![false; n];
61            for _ in 0..n {
62                if visited[current] {
63                    return Err(crate::rules::ExtractionError::invalid(
64                        "selected arcs revisit a source vertex",
65                    ));
66                }
67                visited[current] = true;
68                order.push(current);
69                if successors[current].len() != 1 {
70                    return Err(crate::rules::ExtractionError::invalid(
71                        "selected arcs do not provide one successor for every source vertex",
72                    ));
73                }
74                current = successors[current][0];
75            }
76
77            order
78        })
79    }
80}
81
82#[crate::aggregate_reduction(identity)]
83impl crate::rules::AggregateReductionResult
84    for ReductionHamiltonianCircuitToStrongConnectivityAugmentation
85{
86}
87
88#[reduction(
89    transform = upper_bound {
90        max_numeric_magnitude_bits = "num_vertices + 1",
91        num_vertices = "num_vertices + 2",
92        num_arcs = "0",
93        num_potential_arcs = "num_vertices * (num_vertices - 1)",
94    }
95)]
96impl ReduceTo<StrongConnectivityAugmentation<i64>> for HamiltonianCircuit<SimpleGraph> {
97    type Result = ReductionHamiltonianCircuitToStrongConnectivityAugmentation;
98
99    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
100        let n = self.num_vertices();
101        if n < 3 {
102            return Ok(
103                ReductionHamiltonianCircuitToStrongConnectivityAugmentation {
104                    target: StrongConnectivityAugmentation::new(DirectedGraph::empty(2), vec![], 0),
105                    n,
106                },
107            );
108        }
109        let graph = DirectedGraph::empty(n);
110
111        // Generate all ordered pairs (u, v) with u != v as candidate arcs.
112        let mut candidate_arcs = Vec::with_capacity(n * (n - 1));
113        for u in 0..n {
114            for v in 0..n {
115                if u != v {
116                    let weight = if self.graph().has_edge(u, v) { 1 } else { 2 };
117                    candidate_arcs.push((u, v, weight));
118                }
119            }
120        }
121
122        let bound = i64::try_from(n).map_err(|_| {
123            crate::rules::ReductionError::integer_overflow::<
124                HamiltonianCircuit<SimpleGraph>,
125                StrongConnectivityAugmentation<i64>,
126            >("converting the vertex count to the target bound")
127        })?;
128        let target = StrongConnectivityAugmentation::new(graph, candidate_arcs, bound);
129
130        Ok(ReductionHamiltonianCircuitToStrongConnectivityAugmentation { target, n })
131    }
132}
133
134#[cfg(feature = "example-db")]
135pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
136    use crate::export::SolutionPair;
137
138    vec![crate::example_db::specs::RuleExampleSpec {
139        id: "hamiltoniancircuit_to_strongconnectivityaugmentation",
140        build: || {
141            // 4-cycle: 0-1-2-3-0
142            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
143            let reduction = ReduceTo::<StrongConnectivityAugmentation<i64>>::reduce_to(&source)
144                .expect("reduction should succeed");
145            let target = reduction.target_problem();
146
147            // The HC permutation [0, 1, 2, 3] corresponds to the directed cycle
148            // 0->1->2->3->0. We need to find the indices of these arcs in the
149            // candidate list. Candidate arcs are ordered: for each u in 0..n,
150            // for each v in 0..n where u!=v, so arc (u,v) is at index
151            // u*(n-1) + (if v > u then v-1 else v).
152            let n = 4;
153            let mut target_config = vec![false; n * (n - 1)];
154            let cycle_arcs = [(0, 1), (1, 2), (2, 3), (3, 0)];
155            for (u, v) in cycle_arcs {
156                let idx = u * (n - 1) + if v > u { v - 1 } else { v };
157                target_config[idx] = true;
158            }
159
160            // Verify the target config is valid
161            assert!(
162                target.is_valid_solution(&target_config).unwrap(),
163                "canonical target config must be a valid SCA solution"
164            );
165
166            crate::example_db::specs::assemble_rule_example(
167                &source,
168                target,
169                vec![SolutionPair {
170                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
171                    target_config: serde_json::to_value(target_config)
172                        .expect("solution serialization must succeed"),
173                }],
174            )
175        },
176    }]
177}
178
179#[cfg(test)]
180#[path = "../unit_tests/rules/hamiltoniancircuit_strongconnectivityaugmentation.rs"]
181mod tests;
problemreductions/rules/hamiltoniancircuit_strongconnectivityaugmentation.rs

problemreductions/rules/
hamiltoniancircuit_strongconnectivityaugmentation.rs
