problemreductions/models/graph/
strong_connectivity_augmentation.rs

1//! Strong Connectivity Augmentation problem implementation.
2//!
3//! The Strong Connectivity Augmentation problem asks whether adding a bounded
4//! set of weighted candidate arcs can make a directed graph strongly connected.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::DirectedGraph;
8use crate::traits::Problem;
9use crate::types::WeightElement;
10use num_traits::Zero;
11use serde::{Deserialize, Deserializer, Serialize};
12use std::cmp::Ordering;
13use std::collections::BTreeSet;
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "StrongConnectivityAugmentation",
18        display_name: "Strong Connectivity Augmentation",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("weight", "i32", &["i32"]),
22        ],
23        module_path: module_path!(),
24        description: "Add a bounded set of weighted candidate arcs to make a digraph strongly connected",
25        fields: &[
26            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "The initial directed graph G=(V,A)" },
27            FieldInfo { name: "candidate_arcs", type_name: "Vec<(usize, usize, W)>", description: "Candidate augmenting arcs (u, v, w(u,v)) not already present in G" },
28            FieldInfo { name: "bound", type_name: "W::Sum", description: "Upper bound B on the total added weight" },
29        ],
30    }
31}
32
33/// Strong Connectivity Augmentation.
34///
35/// Given a directed graph `G = (V, A)`, weighted candidate arcs not already in
36/// `A`, and a bound `B`, determine whether some subset of the candidate arcs
37/// has total weight at most `B` and makes the augmented digraph strongly
38/// connected.
39#[derive(Debug, Clone, Serialize)]
40pub struct StrongConnectivityAugmentation<W: WeightElement> {
41    graph: DirectedGraph,
42    candidate_arcs: Vec<(usize, usize, W)>,
43    bound: W::Sum,
44}
45
46impl<W: WeightElement> StrongConnectivityAugmentation<W> {
47    /// Fallible constructor used by CLI validation and deserialization.
48    pub fn try_new(
49        graph: DirectedGraph,
50        candidate_arcs: Vec<(usize, usize, W)>,
51        bound: W::Sum,
52    ) -> Result<Self, String> {
53        if !matches!(
54            bound.partial_cmp(&W::Sum::zero()),
55            Some(Ordering::Equal | Ordering::Greater)
56        ) {
57            return Err("bound must be nonnegative".to_string());
58        }
59
60        let num_vertices = graph.num_vertices();
61        let mut seen_pairs = BTreeSet::new();
62
63        for (u, v, weight) in &candidate_arcs {
64            if *u >= num_vertices || *v >= num_vertices {
65                return Err(format!(
66                    "candidate arc ({}, {}) references vertex >= num_vertices ({})",
67                    u, v, num_vertices
68                ));
69            }
70            if !matches!(
71                weight.to_sum().partial_cmp(&W::Sum::zero()),
72                Some(Ordering::Greater)
73            ) {
74                return Err(format!(
75                    "candidate arc ({}, {}) weight must be positive",
76                    u, v
77                ));
78            }
79            if graph.has_arc(*u, *v) {
80                return Err(format!(
81                    "candidate arc ({}, {}) already exists in the base graph",
82                    u, v
83                ));
84            }
85            if !seen_pairs.insert((*u, *v)) {
86                return Err(format!("duplicate candidate arc ({}, {})", u, v));
87            }
88        }
89
90        Ok(Self {
91            graph,
92            candidate_arcs,
93            bound,
94        })
95    }
96
97    /// Create a new strong connectivity augmentation instance.
98    ///
99    /// # Panics
100    ///
101    /// Panics if a candidate arc endpoint is out of range, if a candidate arc
102    /// already exists in the base graph, or if candidate arcs contain
103    /// duplicates.
104    pub fn new(
105        graph: DirectedGraph,
106        candidate_arcs: Vec<(usize, usize, W)>,
107        bound: W::Sum,
108    ) -> Self {
109        Self::try_new(graph, candidate_arcs, bound).unwrap_or_else(|msg| panic!("{msg}"))
110    }
111
112    /// Get the base directed graph.
113    pub fn graph(&self) -> &DirectedGraph {
114        &self.graph
115    }
116
117    /// Get the candidate augmenting arcs.
118    pub fn candidate_arcs(&self) -> &[(usize, usize, W)] {
119        &self.candidate_arcs
120    }
121
122    /// Get the upper bound on the total added weight.
123    pub fn bound(&self) -> &W::Sum {
124        &self.bound
125    }
126
127    /// Get the number of vertices in the base graph.
128    pub fn num_vertices(&self) -> usize {
129        self.graph.num_vertices()
130    }
131
132    /// Get the number of arcs in the base graph.
133    pub fn num_arcs(&self) -> usize {
134        self.graph.num_arcs()
135    }
136
137    /// Get the number of potential augmenting arcs.
138    pub fn num_potential_arcs(&self) -> usize {
139        self.candidate_arcs.len()
140    }
141
142    /// Check whether the problem uses non-unit weights.
143    pub fn is_weighted(&self) -> bool {
144        !W::IS_UNIT
145    }
146
147    /// Check whether a configuration is a satisfying augmentation.
148    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
149        self.evaluate_config(config)
150    }
151
152    fn evaluate_config(&self, config: &[usize]) -> bool {
153        if config.len() != self.candidate_arcs.len() {
154            return false;
155        }
156
157        let mut total = W::Sum::zero();
158        let mut augmented_arcs = self.graph.arcs();
159
160        for ((u, v, weight), &selected) in self.candidate_arcs.iter().zip(config.iter()) {
161            if selected > 1 {
162                return false;
163            }
164            if selected == 1 {
165                total += weight.to_sum();
166                if total > self.bound {
167                    return false;
168                }
169                augmented_arcs.push((*u, *v));
170            }
171        }
172
173        DirectedGraph::new(self.graph.num_vertices(), augmented_arcs).is_strongly_connected()
174    }
175}
176
177impl<W> Problem for StrongConnectivityAugmentation<W>
178where
179    W: WeightElement + crate::variant::VariantParam,
180{
181    const NAME: &'static str = "StrongConnectivityAugmentation";
182    type Value = crate::types::Or;
183
184    fn variant() -> Vec<(&'static str, &'static str)> {
185        crate::variant_params![W]
186    }
187
188    fn dims(&self) -> Vec<usize> {
189        vec![2; self.candidate_arcs.len()]
190    }
191
192    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
193        crate::types::Or(self.evaluate_config(config))
194    }
195}
196
197crate::declare_variants! {
198    default StrongConnectivityAugmentation<i32> => "2^num_potential_arcs",
199}
200
201#[derive(Deserialize)]
202struct StrongConnectivityAugmentationData<W: WeightElement> {
203    graph: DirectedGraph,
204    candidate_arcs: Vec<(usize, usize, W)>,
205    bound: W::Sum,
206}
207
208impl<'de, W> Deserialize<'de> for StrongConnectivityAugmentation<W>
209where
210    W: WeightElement + Deserialize<'de>,
211    W::Sum: Deserialize<'de>,
212{
213    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
214    where
215        D: Deserializer<'de>,
216    {
217        let data = StrongConnectivityAugmentationData::<W>::deserialize(deserializer)?;
218        Self::try_new(data.graph, data.candidate_arcs, data.bound).map_err(serde::de::Error::custom)
219    }
220}
221
222#[cfg(feature = "example-db")]
223pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
224    vec![crate::example_db::specs::ModelExampleSpec {
225        id: "strong_connectivity_augmentation_i32",
226        // Path digraph 0→1→2→3→4 (not strongly connected — no back-edges).
227        // Nine candidate arcs are all individually affordable, but only the
228        // pair (4→1, w=3) + (1→0, w=5) = 8 = B achieves strong connectivity.
229        instance: Box::new(StrongConnectivityAugmentation::new(
230            DirectedGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
231            vec![
232                (4, 0, 10), // direct fix, too expensive
233                (4, 3, 3),  // 4-escape to dead end
234                (4, 2, 3),  // 4-escape to dead end
235                (4, 1, 3),  // correct 4-escape
236                (3, 0, 7),  // too expensive to combine
237                (3, 1, 3),  // dead-end intermediate
238                (2, 0, 7),  // too expensive to combine
239                (2, 1, 3),  // dead-end intermediate
240                (1, 0, 5),  // the closing arc
241            ],
242            8,
243        )),
244        optimal_config: vec![0, 0, 0, 1, 0, 0, 0, 0, 1],
245        optimal_value: serde_json::json!(true),
246    }]
247}
248
249#[cfg(test)]
250#[path = "../../unit_tests/models/graph/strong_connectivity_augmentation.rs"]
251mod tests;
problemreductions/models/graph/strong_connectivity_augmentation.rs

problemreductions/models/graph/
strong_connectivity_augmentation.rs
