problemreductions/models/graph/
minimum_geometric_connected_dominating_set.rs

1//! Minimum Geometric Connected Dominating Set.
2//!
3//! Given a set of points P in the plane and a distance threshold B > 0,
4//! find a minimum subset P' ⊆ P such that:
5//! 1. Every point in P \ P' is within Euclidean distance B of some point in P' (domination).
6//! 2. The subgraph induced on P' (edges between points within distance B) is connected.
7
8use crate::registry::{ConstructionError, FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12use std::collections::VecDeque;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "MinimumGeometricConnectedDominatingSet",
17        display_name: "Minimum Geometric Connected Dominating Set",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Graph,
21        module_path: module_path!(),
22        description: "Find minimum connected dominating set in a geometric point set",
23        fields: &[
24            FieldInfo {
25                name: "points",
26                type_name: "Vec<(f64, f64)>",
27                description: "The set of points P in the plane",
28            },
29            FieldInfo {
30                name: "radius",
31                type_name: "f64",
32                description: "The distance threshold B",
33            },
34        ],
35    }
36}
37
38/// Minimum Geometric Connected Dominating Set.
39///
40/// Given points P in the plane and distance threshold B > 0,
41/// find a minimum subset P' ⊆ P such that every point in P \ P'
42/// is within distance B of some point in P', and the subgraph
43/// induced on P' (edges between points within distance B) is connected.
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::graph::MinimumGeometricConnectedDominatingSet;
49/// use problemreductions::{Problem, BruteForce};
50///
51/// // Four collinear points with spacing 3 and radius 3.5:
52/// // each point reaches its immediate neighbor but not two steps away.
53/// let points = vec![(0.0, 0.0), (3.0, 0.0), (6.0, 0.0), (9.0, 0.0)];
54/// let problem = MinimumGeometricConnectedDominatingSet::new(points, 3.5).unwrap();
55///
56/// let solver = BruteForce::new();
57/// let witness = solver.solve(&problem).unwrap().unwrap();
58/// let value = problem.evaluate(&witness).unwrap().unwrap();
59/// assert_eq!(value, 2); // Two interior points dominate all and form a connected pair
60/// ```
61#[derive(Debug, Clone, Serialize)]
62pub struct MinimumGeometricConnectedDominatingSet {
63    /// The set of points in the plane.
64    points: Vec<(f64, f64)>,
65    /// The distance threshold B.
66    radius: f64,
67}
68
69impl MinimumGeometricConnectedDominatingSet {
70    /// Create a new instance.
71    ///
72    pub fn new(points: Vec<(f64, f64)>, radius: f64) -> Result<Self, ConstructionError> {
73        if points.is_empty() {
74            return Err(ConstructionError::Conversion(
75                "points must be non-empty".into(),
76            ));
77        }
78        if !radius.is_finite() || radius <= 0.0 {
79            if !radius.is_finite() {
80                return Err(ConstructionError::NonFiniteFloat(
81                    "radius must be finite".into(),
82                ));
83            }
84            return Err(ConstructionError::Conversion(
85                "radius must be positive".into(),
86            ));
87        }
88        for (index, &(x, y)) in points.iter().enumerate() {
89            if !x.is_finite() || !y.is_finite() {
90                return Err(ConstructionError::NonFiniteFloat(format!(
91                    "point at index {index} must have finite coordinates"
92                )));
93            }
94        }
95        Ok(Self { points, radius })
96    }
97
98    /// Get the number of points.
99    pub fn num_points(&self) -> usize {
100        self.points.len()
101    }
102
103    /// Get the distance threshold.
104    pub fn radius(&self) -> f64 {
105        self.radius
106    }
107
108    /// Get a reference to the points.
109    pub fn points(&self) -> &[(f64, f64)] {
110        &self.points
111    }
112
113    /// Squared Euclidean distance between two points.
114    fn dist_sq(a: (f64, f64), b: (f64, f64)) -> Result<f64, crate::traits::EvaluationError> {
115        let dx = a.0 - b.0;
116        let dy = a.1 - b.1;
117        let distance = dx * dx + dy * dy;
118        distance.is_finite().then_some(distance).ok_or_else(|| {
119            crate::traits::EvaluationError::NonFiniteResult(
120                "computing geometric squared distance".into(),
121            )
122        })
123    }
124
125    /// Check if two points are within distance B.
126    fn within_radius(
127        &self,
128        i: usize,
129        j: usize,
130        radius_squared: f64,
131    ) -> Result<bool, crate::traits::EvaluationError> {
132        Ok(Self::dist_sq(self.points[i], self.points[j])? <= radius_squared)
133    }
134
135    /// Check if a configuration is a valid connected dominating set.
136    pub fn is_valid_solution(
137        &self,
138        config: &[bool],
139    ) -> Result<bool, crate::traits::EvaluationError> {
140        if config.len() != self.points.len() {
141            return Err(crate::traits::EvaluationError::InvalidConfiguration(
142                "geometric connected dominating set expects one Boolean value per point".into(),
143            ));
144        }
145        let radius_squared = self.radius * self.radius;
146        if !radius_squared.is_finite() {
147            return Err(crate::traits::EvaluationError::NonFiniteResult(
148                "squaring the geometric radius".into(),
149            ));
150        }
151        let selected: Vec<usize> = config
152            .iter()
153            .enumerate()
154            .filter(|(_, &v)| v)
155            .map(|(i, _)| i)
156            .collect();
157
158        if selected.is_empty() {
159            return Ok(false);
160        }
161
162        // Check domination: every unselected point must be within distance B
163        // of some selected point.
164        for (i, &v) in config.iter().enumerate() {
165            if !v {
166                let mut dominated = false;
167                for &s in &selected {
168                    if self.within_radius(i, s, radius_squared)? {
169                        dominated = true;
170                        break;
171                    }
172                }
173                if !dominated {
174                    return Ok(false);
175                }
176            }
177        }
178
179        // Check connectivity: BFS on selected points using distance-B edges.
180        if selected.len() == 1 {
181            return Ok(true);
182        }
183        let mut visited = vec![false; selected.len()];
184        let mut queue = VecDeque::new();
185        visited[0] = true;
186        queue.push_back(0);
187        while let Some(u) = queue.pop_front() {
188            for (vi, &vj) in selected.iter().enumerate() {
189                if !visited[vi] && self.within_radius(selected[u], vj, radius_squared)? {
190                    visited[vi] = true;
191                    queue.push_back(vi);
192                }
193            }
194        }
195        Ok(visited.iter().all(|&v| v))
196    }
197}
198
199impl<'de> Deserialize<'de> for MinimumGeometricConnectedDominatingSet {
200    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
201    where
202        D: serde::Deserializer<'de>,
203    {
204        #[derive(Deserialize)]
205        struct Raw {
206            points: Vec<(f64, f64)>,
207            radius: f64,
208        }
209
210        let raw = Raw::deserialize(deserializer)?;
211        Self::new(raw.points, raw.radius).map_err(serde::de::Error::custom)
212    }
213}
214
215impl Problem for MinimumGeometricConnectedDominatingSet {
216    const NAME: &'static str = "MinimumGeometricConnectedDominatingSet";
217    type Solution = Vec<bool>;
218    type Value = Min<i64>;
219
220    crate::problem_parameters![("num_points", num_points),];
221
222    fn variant() -> Vec<(&'static str, &'static str)> {
223        crate::variant_params![]
224    }
225
226    fn evaluate(
227        &self,
228        config: &Self::Solution,
229    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
230        Ok({
231            if !self.is_valid_solution(config)? {
232                return Ok(Min(None));
233            }
234            let count = config.iter().filter(|&&v| v).count();
235            Min(Some(i64::try_from(count).map_err(|_| {
236                crate::traits::EvaluationError::IntegerOverflow(
237                    "converting dominating-set cardinality to i64".into(),
238                )
239            })?))
240        })
241    }
242}
243
244impl crate::solvers::BruteForceProblem for MinimumGeometricConnectedDominatingSet {
245    fn dimensions(&self) -> Vec<usize> {
246        vec![2; self.num_points()]
247    }
248}
249
250crate::declare_variants! {
251    default MinimumGeometricConnectedDominatingSet => "2^num_points",
252}
253
254crate::register_brute_force! {
255    MinimumGeometricConnectedDominatingSet decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
256}
257
258#[cfg(feature = "example-db")]
259pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
260    vec![crate::example_db::specs::ModelExampleSpec {
261        id: "minimum_geometric_connected_dominating_set",
262        instance: Box::new(
263            MinimumGeometricConnectedDominatingSet::new(
264                vec![
265                    (0.0, 0.0),
266                    (3.0, 0.0),
267                    (6.0, 0.0),
268                    (9.0, 0.0),
269                    (0.0, 3.0),
270                    (3.0, 3.0),
271                    (6.0, 3.0),
272                    (9.0, 3.0),
273                ],
274                3.5,
275            )
276            .expect("canonical geometric connected-dominating-set instance must be valid"),
277        ),
278        optimal_config: serde_json::json!(vec![true, true, true, true, false, false, false, false]),
279        optimal_value: serde_json::json!(4),
280    }]
281}
282
283#[cfg(test)]
284#[path = "../../unit_tests/models/graph/minimum_geometric_connected_dominating_set.rs"]
285mod tests;
problemreductions/models/graph/minimum_geometric_connected_dominating_set.rs

problemreductions/models/graph/
minimum_geometric_connected_dominating_set.rs
