problemreductions/models/graph/
bounded_component_spanning_forest.rs

1//! Bounded Component Spanning Forest problem implementation.
2//!
3//! The Bounded Component Spanning Forest problem asks whether the vertices of a
4//! weighted graph can be partitioned into at most `K` connected components, each
5//! of total weight at most `B`.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::WeightElement;
11use num_traits::Zero;
12use serde::{Deserialize, Serialize};
13use std::collections::VecDeque;
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "BoundedComponentSpanningForest",
18        display_name: "Bounded Component Spanning Forest",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
22            VariantDimension::new("weight", "i64", &["i64"]),
23        ],
24        category: crate::registry::ProblemCategory::Graph,
25        module_path: module_path!(),
26        description: "Partition vertices into at most K connected components, each of total weight at most B",
27        fields: BoundedComponentSpanningForestCreateSpec::FIELDS,
28    }
29}
30
31/// The Bounded Component Spanning Forest problem.
32///
33/// Given a graph `G = (V, E)`, a nonnegative weight `w(v)` for each vertex, an
34/// integer `K`, and a bound `B`, determine whether the vertices can be
35/// partitioned into at most `K` non-empty sets such that every set induces a
36/// connected subgraph and the total weight of each set is at most `B`.
37#[derive(Debug, Clone, Serialize, Deserialize)]
38pub struct BoundedComponentSpanningForest<G, W: WeightElement> {
39    /// The underlying graph.
40    graph: G,
41    /// Weights for each vertex.
42    weights: Vec<W>,
43    /// Upper bound on the number of connected components.
44    max_components: usize,
45    /// Upper bound on the total weight of every component.
46    max_weight: W::Sum,
47}
48
49#[derive(Debug, Deserialize, crate::CreateSpec)]
50struct BoundedComponentSpanningForestCreateSpec {
51    /// The underlying graph G=(V,E).
52    graph: SimpleGraph,
53    /// Vertex weights w(v) for each vertex v in V.
54    weights: Vec<i64>,
55    /// Upper bound K on the number of connected components.
56    k: usize,
57    /// Upper bound B on the total weight of each component.
58    max_weight: i64,
59}
60
61impl TryFrom<BoundedComponentSpanningForestCreateSpec>
62    for BoundedComponentSpanningForest<SimpleGraph, i64>
63{
64    type Error = crate::registry::ConstructionError;
65
66    fn try_from(spec: BoundedComponentSpanningForestCreateSpec) -> Result<Self, Self::Error> {
67        if spec.weights.len() != spec.graph.num_vertices() {
68            return Err(format!(
69                "weights has {} entries, expected {}",
70                spec.weights.len(),
71                spec.graph.num_vertices()
72            )
73            .into());
74        }
75        if spec.weights.iter().any(|&weight| weight < 0) {
76            return Err("weights must be nonnegative".to_string().into());
77        }
78        if spec.k == 0 {
79            return Err("k must be at least 1".to_string().into());
80        }
81        if spec.max_weight <= 0 {
82            return Err("max_weight must be positive".to_string().into());
83        }
84        Ok(Self::new(spec.graph, spec.weights, spec.k, spec.max_weight))
85    }
86}
87
88impl<G: Graph, W: WeightElement> BoundedComponentSpanningForest<G, W> {
89    /// Create a new bounded-component spanning forest instance.
90    pub fn new(graph: G, weights: Vec<W>, max_components: usize, max_weight: W::Sum) -> Self {
91        assert_eq!(
92            weights.len(),
93            graph.num_vertices(),
94            "weights length must match graph num_vertices"
95        );
96        assert!(
97            weights
98                .iter()
99                .all(|weight| weight.to_sum() >= W::Sum::zero()),
100            "weights must be nonnegative"
101        );
102        assert!(max_components >= 1, "max_components must be at least 1");
103        assert!(max_weight > W::Sum::zero(), "max_weight must be positive");
104        Self {
105            graph,
106            weights,
107            max_components,
108            max_weight,
109        }
110    }
111
112    /// Get a reference to the underlying graph.
113    pub fn graph(&self) -> &G {
114        &self.graph
115    }
116
117    /// Get the vertex weights.
118    pub fn weights(&self) -> &[W] {
119        &self.weights
120    }
121
122    /// Get the maximum number of components.
123    pub fn max_components(&self) -> usize {
124        self.max_components
125    }
126
127    /// Get the maximum allowed component weight.
128    pub fn max_weight(&self) -> &W::Sum {
129        &self.max_weight
130    }
131
132    /// Get the number of vertices in the underlying graph.
133    pub fn num_vertices(&self) -> usize {
134        self.graph.num_vertices()
135    }
136
137    /// Get the number of edges in the underlying graph.
138    pub fn num_edges(&self) -> usize {
139        self.graph.num_edges()
140    }
141
142    /// Check if the problem uses a non-unit weight type.
143    pub fn is_weighted(&self) -> bool {
144        !W::IS_UNIT
145    }
146
147    /// Check if a configuration is a valid bounded-component partition.
148    pub fn is_valid_solution(
149        &self,
150        config: &[usize],
151    ) -> Result<bool, crate::traits::EvaluationError> {
152        let num_vertices = self.graph.num_vertices();
153        if config.len() != num_vertices {
154            return Ok(false);
155        }
156
157        let mut component_weights = vec![W::Sum::zero(); self.max_components];
158        let mut component_sizes = vec![0usize; self.max_components];
159        let mut component_starts = vec![usize::MAX; self.max_components];
160        let mut used_components = Vec::with_capacity(self.max_components);
161
162        for (vertex, &component) in config.iter().enumerate() {
163            if component >= self.max_components {
164                return Ok(false);
165            }
166
167            if component_sizes[component] == 0 {
168                component_starts[component] = vertex;
169                used_components.push(component);
170            }
171
172            component_sizes[component] += 1;
173            component_weights[component] = W::checked_add_to_sum(
174                component_weights[component].clone(),
175                self.weights[vertex].to_sum(),
176                "summing bounded forest component weights",
177            )?;
178            if component_weights[component] > self.max_weight {
179                return Ok(false);
180            }
181        }
182
183        if used_components
184            .iter()
185            .all(|&component| component_sizes[component] <= 1)
186        {
187            return Ok(true);
188        }
189
190        let mut visited_marks = vec![0usize; num_vertices];
191        let mut queue = VecDeque::with_capacity(num_vertices);
192
193        for (mark, component) in used_components.into_iter().enumerate() {
194            let component_size = component_sizes[component];
195            if component_size <= 1 {
196                continue;
197            }
198
199            let start = component_starts[component];
200            queue.clear();
201            queue.push_back(start);
202            visited_marks[start] = mark + 1;
203            let mut visited_count = 0usize;
204
205            while let Some(vertex) = queue.pop_front() {
206                visited_count += 1;
207                for neighbor in self.graph.neighbors(vertex) {
208                    if config[neighbor] == component && visited_marks[neighbor] != mark + 1 {
209                        visited_marks[neighbor] = mark + 1;
210                        queue.push_back(neighbor);
211                    }
212                }
213            }
214
215            if visited_count != component_size {
216                return Ok(false);
217            }
218        }
219
220        Ok(true)
221    }
222}
223
224impl<G, W> Problem for BoundedComponentSpanningForest<G, W>
225where
226    G: Graph + crate::variant::VariantParam,
227    W: WeightElement + crate::variant::VariantParam,
228{
229    const NAME: &'static str = "BoundedComponentSpanningForest";
230    type Solution = Vec<usize>;
231    type Value = crate::types::Or;
232
233    crate::problem_parameters![
234        ("max_components", max_components),
235        ("num_edges", num_edges),
236        ("num_vertices", num_vertices),
237    ];
238
239    fn variant() -> Vec<(&'static str, &'static str)> {
240        crate::variant_params![G, W]
241    }
242
243    fn evaluate(
244        &self,
245        config: &Self::Solution,
246    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
247        if config.len() != self.graph.num_vertices() {
248            return Err(crate::traits::EvaluationError::InvalidConfiguration(
249                "component assignment length does not match the graph vertices".into(),
250            ));
251        }
252        Ok(crate::types::Or(self.is_valid_solution(config)?))
253    }
254}
255
256impl<G, W> crate::solvers::BruteForceProblem for BoundedComponentSpanningForest<G, W>
257where
258    G: Graph + crate::variant::VariantParam,
259    W: WeightElement + crate::variant::VariantParam,
260{
261    fn dimensions(&self) -> Vec<usize> {
262        vec![self.max_components; self.graph.num_vertices()]
263    }
264}
265
266#[cfg(feature = "example-db")]
267pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
268    vec![crate::example_db::specs::ModelExampleSpec {
269        id: "bounded_component_spanning_forest_simplegraph",
270        instance: Box::new(BoundedComponentSpanningForest::new(
271            SimpleGraph::new(
272                8,
273                vec![
274                    (0, 1),
275                    (1, 2),
276                    (2, 3),
277                    (3, 4),
278                    (4, 5),
279                    (5, 6),
280                    (6, 7),
281                    (0, 7),
282                    (1, 5),
283                    (2, 6),
284                ],
285            ),
286            vec![2, 3, 1, 2, 3, 1, 2, 1],
287            3,
288            6,
289        )),
290        optimal_config: serde_json::json!(vec![0, 0, 1, 1, 1, 2, 2, 0]),
291        optimal_value: serde_json::json!(true),
292    }]
293}
294
295crate::declare_variants! {
296    default BoundedComponentSpanningForest<SimpleGraph, i64> => "3^num_vertices" create BoundedComponentSpanningForestCreateSpec,
297}
298
299crate::register_brute_force! {
300    BoundedComponentSpanningForest<SimpleGraph, i64>,
301}
302
303#[cfg(test)]
304#[path = "../../unit_tests/models/graph/bounded_component_spanning_forest.rs"]
305mod tests;
problemreductions/models/graph/bounded_component_spanning_forest.rs

problemreductions/models/graph/
bounded_component_spanning_forest.rs
