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::{FieldInfo, 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", "i32", &["i32"]),
23        ],
24        module_path: module_path!(),
25        description: "Partition vertices into at most K connected components, each of total weight at most B",
26        fields: &[
27            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
28            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w(v) for each vertex v in V" },
29            FieldInfo { name: "max_components", type_name: "usize", description: "Upper bound K on the number of connected components" },
30            FieldInfo { name: "max_weight", type_name: "W::Sum", description: "Upper bound B on the total weight of each component" },
31        ],
32    }
33}
34
35/// The Bounded Component Spanning Forest problem.
36///
37/// Given a graph `G = (V, E)`, a nonnegative weight `w(v)` for each vertex, an
38/// integer `K`, and a bound `B`, determine whether the vertices can be
39/// partitioned into at most `K` non-empty sets such that every set induces a
40/// connected subgraph and the total weight of each set is at most `B`.
41#[derive(Debug, Clone, Serialize, Deserialize)]
42pub struct BoundedComponentSpanningForest<G, W: WeightElement> {
43    /// The underlying graph.
44    graph: G,
45    /// Weights for each vertex.
46    weights: Vec<W>,
47    /// Upper bound on the number of connected components.
48    max_components: usize,
49    /// Upper bound on the total weight of every component.
50    max_weight: W::Sum,
51}
52
53impl<G: Graph, W: WeightElement> BoundedComponentSpanningForest<G, W> {
54    /// Create a new bounded-component spanning forest instance.
55    pub fn new(graph: G, weights: Vec<W>, max_components: usize, max_weight: W::Sum) -> Self {
56        assert_eq!(
57            weights.len(),
58            graph.num_vertices(),
59            "weights length must match graph num_vertices"
60        );
61        assert!(
62            weights
63                .iter()
64                .all(|weight| weight.to_sum() >= W::Sum::zero()),
65            "weights must be nonnegative"
66        );
67        assert!(max_components >= 1, "max_components must be at least 1");
68        assert!(max_weight > W::Sum::zero(), "max_weight must be positive");
69        Self {
70            graph,
71            weights,
72            max_components,
73            max_weight,
74        }
75    }
76
77    /// Get a reference to the underlying graph.
78    pub fn graph(&self) -> &G {
79        &self.graph
80    }
81
82    /// Get the vertex weights.
83    pub fn weights(&self) -> &[W] {
84        &self.weights
85    }
86
87    /// Get the maximum number of components.
88    pub fn max_components(&self) -> usize {
89        self.max_components
90    }
91
92    /// Get the maximum allowed component weight.
93    pub fn max_weight(&self) -> &W::Sum {
94        &self.max_weight
95    }
96
97    /// Get the number of vertices in the underlying graph.
98    pub fn num_vertices(&self) -> usize {
99        self.graph.num_vertices()
100    }
101
102    /// Get the number of edges in the underlying graph.
103    pub fn num_edges(&self) -> usize {
104        self.graph.num_edges()
105    }
106
107    /// Check if the problem uses a non-unit weight type.
108    pub fn is_weighted(&self) -> bool {
109        !W::IS_UNIT
110    }
111
112    /// Check if a configuration is a valid bounded-component partition.
113    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
114        let num_vertices = self.graph.num_vertices();
115        if config.len() != num_vertices {
116            return false;
117        }
118
119        let mut component_weights = vec![W::Sum::zero(); self.max_components];
120        let mut component_sizes = vec![0usize; self.max_components];
121        let mut component_starts = vec![usize::MAX; self.max_components];
122        let mut used_components = Vec::with_capacity(self.max_components);
123
124        for (vertex, &component) in config.iter().enumerate() {
125            if component >= self.max_components {
126                return false;
127            }
128
129            if component_sizes[component] == 0 {
130                component_starts[component] = vertex;
131                used_components.push(component);
132            }
133
134            component_sizes[component] += 1;
135            component_weights[component] += self.weights[vertex].to_sum();
136            if component_weights[component] > self.max_weight {
137                return false;
138            }
139        }
140
141        if used_components
142            .iter()
143            .all(|&component| component_sizes[component] <= 1)
144        {
145            return true;
146        }
147
148        let mut visited_marks = vec![0usize; num_vertices];
149        let mut queue = VecDeque::with_capacity(num_vertices);
150
151        for (mark, component) in used_components.into_iter().enumerate() {
152            let component_size = component_sizes[component];
153            if component_size <= 1 {
154                continue;
155            }
156
157            let start = component_starts[component];
158            queue.clear();
159            queue.push_back(start);
160            visited_marks[start] = mark + 1;
161            let mut visited_count = 0usize;
162
163            while let Some(vertex) = queue.pop_front() {
164                visited_count += 1;
165                for neighbor in self.graph.neighbors(vertex) {
166                    if config[neighbor] == component && visited_marks[neighbor] != mark + 1 {
167                        visited_marks[neighbor] = mark + 1;
168                        queue.push_back(neighbor);
169                    }
170                }
171            }
172
173            if visited_count != component_size {
174                return false;
175            }
176        }
177
178        true
179    }
180}
181
182impl<G, W> Problem for BoundedComponentSpanningForest<G, W>
183where
184    G: Graph + crate::variant::VariantParam,
185    W: WeightElement + crate::variant::VariantParam,
186{
187    const NAME: &'static str = "BoundedComponentSpanningForest";
188    type Value = crate::types::Or;
189
190    fn variant() -> Vec<(&'static str, &'static str)> {
191        crate::variant_params![G, W]
192    }
193
194    fn dims(&self) -> Vec<usize> {
195        vec![self.max_components; self.graph.num_vertices()]
196    }
197
198    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
199        crate::types::Or(self.is_valid_solution(config))
200    }
201}
202
203#[cfg(feature = "example-db")]
204pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
205    vec![crate::example_db::specs::ModelExampleSpec {
206        id: "bounded_component_spanning_forest_simplegraph_i32",
207        instance: Box::new(BoundedComponentSpanningForest::new(
208            SimpleGraph::new(
209                8,
210                vec![
211                    (0, 1),
212                    (1, 2),
213                    (2, 3),
214                    (3, 4),
215                    (4, 5),
216                    (5, 6),
217                    (6, 7),
218                    (0, 7),
219                    (1, 5),
220                    (2, 6),
221                ],
222            ),
223            vec![2, 3, 1, 2, 3, 1, 2, 1],
224            3,
225            6,
226        )),
227        optimal_config: vec![0, 0, 1, 1, 1, 2, 2, 0],
228        optimal_value: serde_json::json!(true),
229    }]
230}
231
232crate::declare_variants! {
233    default BoundedComponentSpanningForest<SimpleGraph, i32> => "3^num_vertices",
234}
235
236#[cfg(test)]
237#[path = "../../unit_tests/models/graph/bounded_component_spanning_forest.rs"]
238mod tests;
problemreductions/models/graph/bounded_component_spanning_forest.rs

problemreductions/models/graph/
bounded_component_spanning_forest.rs
