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<i32>,
19    n: usize,
20}
21
22impl ReductionResult for ReductionHamiltonianCircuitToStrongConnectivityAugmentation {
23    type Source = HamiltonianCircuit<SimpleGraph>;
24    type Target = StrongConnectivityAugmentation<i32>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
31        let n = self.n;
32        if n == 0 {
33            return vec![];
34        }
35
36        // Build directed adjacency from selected arcs.
37        let candidate_arcs = self.target.candidate_arcs();
38        let mut successors = vec![Vec::new(); n];
39        for (idx, &selected) in target_solution.iter().enumerate() {
40            if selected == 1 {
41                let (u, v, _) = candidate_arcs[idx];
42                successors[u].push(v);
43            }
44        }
45
46        // Walk the directed cycle starting from vertex 0.
47        let mut order = Vec::with_capacity(n);
48        let mut current = 0;
49        let mut visited = vec![false; n];
50        for _ in 0..n {
51            if visited[current] {
52                // Not a valid Hamiltonian cycle; return fallback.
53                return vec![0; n];
54            }
55            visited[current] = true;
56            order.push(current);
57            if successors[current].len() != 1 {
58                return vec![0; n];
59            }
60            current = successors[current][0];
61        }
62
63        order
64    }
65}
66
67#[reduction(
68    overhead = {
69        num_vertices = "num_vertices",
70        num_arcs = "0",
71        num_potential_arcs = "num_vertices * (num_vertices - 1)",
72    }
73)]
74impl ReduceTo<StrongConnectivityAugmentation<i32>> for HamiltonianCircuit<SimpleGraph> {
75    type Result = ReductionHamiltonianCircuitToStrongConnectivityAugmentation;
76
77    fn reduce_to(&self) -> Self::Result {
78        let n = self.num_vertices();
79        let graph = DirectedGraph::empty(n);
80
81        // Generate all ordered pairs (u, v) with u != v as candidate arcs.
82        let mut candidate_arcs = Vec::with_capacity(n * (n - 1));
83        for u in 0..n {
84            for v in 0..n {
85                if u != v {
86                    let weight = if self.graph().has_edge(u, v) { 1 } else { 2 };
87                    candidate_arcs.push((u, v, weight));
88                }
89            }
90        }
91
92        let bound = n as i32;
93        let target = StrongConnectivityAugmentation::new(graph, candidate_arcs, bound);
94
95        ReductionHamiltonianCircuitToStrongConnectivityAugmentation { target, n }
96    }
97}
98
99#[cfg(feature = "example-db")]
100pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
101    use crate::export::SolutionPair;
102
103    vec![crate::example_db::specs::RuleExampleSpec {
104        id: "hamiltoniancircuit_to_strongconnectivityaugmentation",
105        build: || {
106            // 4-cycle: 0-1-2-3-0
107            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
108            let reduction = ReduceTo::<StrongConnectivityAugmentation<i32>>::reduce_to(&source);
109            let target = reduction.target_problem();
110
111            // The HC permutation [0, 1, 2, 3] corresponds to the directed cycle
112            // 0->1->2->3->0. We need to find the indices of these arcs in the
113            // candidate list. Candidate arcs are ordered: for each u in 0..n,
114            // for each v in 0..n where u!=v, so arc (u,v) is at index
115            // u*(n-1) + (if v > u then v-1 else v).
116            let n = 4;
117            let mut target_config = vec![0usize; n * (n - 1)];
118            let cycle_arcs = [(0, 1), (1, 2), (2, 3), (3, 0)];
119            for (u, v) in cycle_arcs {
120                let idx = u * (n - 1) + if v > u { v - 1 } else { v };
121                target_config[idx] = 1;
122            }
123
124            // Verify the target config is valid
125            assert!(
126                target.is_valid_solution(&target_config),
127                "canonical target config must be a valid SCA solution"
128            );
129
130            crate::example_db::specs::assemble_rule_example(
131                &source,
132                target,
133                vec![SolutionPair {
134                    source_config: vec![0, 1, 2, 3],
135                    target_config,
136                }],
137            )
138        },
139    }]
140}
141
142#[cfg(test)]
143#[path = "../unit_tests/rules/hamiltoniancircuit_strongconnectivityaugmentation.rs"]
144mod tests;
problemreductions/rules/hamiltoniancircuit_strongconnectivityaugmentation.rs

problemreductions/rules/
hamiltoniancircuit_strongconnectivityaugmentation.rs
