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_solution(self.target_problem(), target_solution)?;
35
36        Ok({
37            let n = self.n;
38            if n == 0 {
39                return Ok(vec![]);
40            }
41
42            // Build directed adjacency from selected arcs.
43            let candidate_arcs = self.target.candidate_arcs();
44            let mut successors = vec![Vec::new(); n];
45            for (idx, &selected) in target_solution.iter().enumerate() {
46                if selected {
47                    let (u, v, _) = candidate_arcs[idx];
48                    successors[u].push(v);
49                }
50            }
51
52            // Walk the directed cycle starting from vertex 0.
53            let mut order = Vec::with_capacity(n);
54            let mut current = 0;
55            let mut visited = vec![false; n];
56            for _ in 0..n {
57                if visited[current] {
58                    return Err(crate::rules::ExtractionError::invalid(
59                        "selected arcs revisit a source vertex",
60                    ));
61                }
62                visited[current] = true;
63                order.push(current);
64                if successors[current].len() != 1 {
65                    return Err(crate::rules::ExtractionError::invalid(
66                        "selected arcs do not provide one successor for every source vertex",
67                    ));
68                }
69                current = successors[current][0];
70            }
71
72            order
73        })
74    }
75}
76
77#[reduction(
78    transform = exact {
79        num_vertices = "num_vertices",
80        num_arcs = "0",
81        num_potential_arcs = "num_vertices * (num_vertices - 1)",
82    }
83)]
84impl ReduceTo<StrongConnectivityAugmentation<i64>> for HamiltonianCircuit<SimpleGraph> {
85    type Result = ReductionHamiltonianCircuitToStrongConnectivityAugmentation;
86
87    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
88        let n = self.num_vertices();
89        let graph = DirectedGraph::empty(n);
90
91        // Generate all ordered pairs (u, v) with u != v as candidate arcs.
92        let mut candidate_arcs = Vec::with_capacity(n * (n - 1));
93        for u in 0..n {
94            for v in 0..n {
95                if u != v {
96                    let weight = if self.graph().has_edge(u, v) { 1 } else { 2 };
97                    candidate_arcs.push((u, v, weight));
98                }
99            }
100        }
101
102        let bound = i64::try_from(n).map_err(|_| {
103            crate::rules::ReductionError::integer_overflow::<
104                HamiltonianCircuit<SimpleGraph>,
105                StrongConnectivityAugmentation<i64>,
106            >("converting the vertex count to the target bound")
107        })?;
108        let target = StrongConnectivityAugmentation::new(graph, candidate_arcs, bound);
109
110        Ok(ReductionHamiltonianCircuitToStrongConnectivityAugmentation { target, n })
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    use crate::export::SolutionPair;
117
118    vec![crate::example_db::specs::RuleExampleSpec {
119        id: "hamiltoniancircuit_to_strongconnectivityaugmentation",
120        build: || {
121            // 4-cycle: 0-1-2-3-0
122            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
123            let reduction = ReduceTo::<StrongConnectivityAugmentation<i64>>::reduce_to(&source)
124                .expect("reduction should succeed");
125            let target = reduction.target_problem();
126
127            // The HC permutation [0, 1, 2, 3] corresponds to the directed cycle
128            // 0->1->2->3->0. We need to find the indices of these arcs in the
129            // candidate list. Candidate arcs are ordered: for each u in 0..n,
130            // for each v in 0..n where u!=v, so arc (u,v) is at index
131            // u*(n-1) + (if v > u then v-1 else v).
132            let n = 4;
133            let mut target_config = vec![false; n * (n - 1)];
134            let cycle_arcs = [(0, 1), (1, 2), (2, 3), (3, 0)];
135            for (u, v) in cycle_arcs {
136                let idx = u * (n - 1) + if v > u { v - 1 } else { v };
137                target_config[idx] = true;
138            }
139
140            // Verify the target config is valid
141            assert!(
142                target.is_valid_solution(&target_config).unwrap(),
143                "canonical target config must be a valid SCA solution"
144            );
145
146            crate::example_db::specs::assemble_rule_example(
147                &source,
148                target,
149                vec![SolutionPair {
150                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
151                    target_config: serde_json::to_value(target_config)
152                        .expect("solution serialization must succeed"),
153                }],
154            )
155        },
156    }]
157}
158
159#[cfg(test)]
160#[path = "../unit_tests/rules/hamiltoniancircuit_strongconnectivityaugmentation.rs"]
161mod tests;
problemreductions/rules/hamiltoniancircuit_strongconnectivityaugmentation.rs

problemreductions/rules/
hamiltoniancircuit_strongconnectivityaugmentation.rs
