problemreductions/models/graph/
minimum_capacitated_spanning_tree.rs

1//! Minimum Capacitated Spanning Tree problem implementation.
2//!
3//! Given a weighted graph with a designated root vertex, vertex requirements,
4//! and a capacity bound, find a minimum-weight spanning tree rooted at the root
5//! such that for each edge, the sum of requirements in its subtree (on the
6//! non-root side) does not exceed the capacity.
7
8use num_traits::Zero;
9use serde::{Deserialize, Serialize};
10
11use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
12use crate::topology::{Graph, SimpleGraph};
13use crate::traits::Problem;
14use crate::types::{Min, WeightElement};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "MinimumCapacitatedSpanningTree",
19        display_name: "Minimum Capacitated Spanning Tree",
20        aliases: &["MCST"],
21        dimensions: &[
22            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
23            VariantDimension::new("weight", "i64", &["i64"]),
24        ],
25        category: crate::registry::ProblemCategory::Graph,
26        module_path: module_path!(),
27        description: "Find minimum weight spanning tree with subtree capacity constraints",
28        fields: MinimumCapacitatedSpanningTreeCreateSpec::FIELDS,
29    }
30}
31
32/// The Minimum Capacitated Spanning Tree problem.
33///
34/// Given a weighted graph G = (V, E), edge weights w_e, a root vertex v0,
35/// vertex requirements r_v (with r_{v0} = 0), and a capacity C, find a
36/// spanning tree T rooted at v0 such that:
37/// - For each edge e in T, the sum of requirements of all vertices in the
38///   subtree on the non-root side of e is at most C.
39/// - The total weight of T is minimized.
40///
41/// # Representation
42///
43/// Each edge is assigned a binary variable:
44/// - 0: edge is not in the spanning tree
45/// - 1: edge is in the spanning tree
46///
47/// # Type Parameters
48///
49/// * `G` - The graph type (e.g., `SimpleGraph`)
50/// * `W` - The weight type for edges and requirements (e.g., `i64`)
51#[derive(Debug, Clone, Serialize, Deserialize)]
52#[serde(try_from = "MinimumCapacitatedSpanningTreeData<G, W>")]
53#[serde(bound(
54    deserialize = "G: Graph + Deserialize<'de>, W: WeightElement + Deserialize<'de>, W::Sum: Deserialize<'de>"
55))]
56pub struct MinimumCapacitatedSpanningTree<G, W: WeightElement> {
57    /// The underlying graph.
58    graph: G,
59    /// Weights for each edge (in edge index order).
60    weights: Vec<W>,
61    /// Root vertex index.
62    root: usize,
63    /// Vertex requirements (root has requirement 0).
64    requirements: Vec<W>,
65    /// Subtree capacity bound.
66    capacity: W::Sum,
67}
68
69#[derive(Deserialize)]
70#[serde(bound(
71    deserialize = "G: Graph + Deserialize<'de>, W: WeightElement + Deserialize<'de>, W::Sum: Deserialize<'de>"
72))]
73struct MinimumCapacitatedSpanningTreeData<G, W: WeightElement> {
74    graph: G,
75    weights: Vec<W>,
76    root: usize,
77    requirements: Vec<W>,
78    capacity: W::Sum,
79}
80
81impl<G, W> TryFrom<MinimumCapacitatedSpanningTreeData<G, W>>
82    for MinimumCapacitatedSpanningTree<G, W>
83where
84    G: Graph,
85    W: WeightElement,
86{
87    type Error = crate::registry::ConstructionError;
88
89    fn try_from(data: MinimumCapacitatedSpanningTreeData<G, W>) -> Result<Self, Self::Error> {
90        Self::try_new(
91            data.graph,
92            data.weights,
93            data.root,
94            data.requirements,
95            data.capacity,
96        )
97    }
98}
99
100#[derive(Debug, Deserialize, crate::CreateSpec)]
101struct MinimumCapacitatedSpanningTreeCreateSpec {
102    /// The underlying graph.
103    graph: SimpleGraph,
104    /// Edge weights; defaults to one per edge.
105    weights: Option<Vec<i64>>,
106    /// Root vertex.
107    root: usize,
108    /// Vertex requirements.
109    requirements: Vec<i64>,
110    /// Subtree capacity bound.
111    capacity: i64,
112}
113impl TryFrom<MinimumCapacitatedSpanningTreeCreateSpec>
114    for MinimumCapacitatedSpanningTree<SimpleGraph, i64>
115{
116    type Error = crate::registry::ConstructionError;
117    fn try_from(spec: MinimumCapacitatedSpanningTreeCreateSpec) -> Result<Self, Self::Error> {
118        let edges = spec.graph.num_edges();
119        let weights = spec.weights.unwrap_or_else(|| vec![1; edges]);
120        Self::try_new(
121            spec.graph,
122            weights,
123            spec.root,
124            spec.requirements,
125            spec.capacity,
126        )
127    }
128}
129
130impl<G: Graph, W: WeightElement> MinimumCapacitatedSpanningTree<G, W> {
131    /// Create a MinimumCapacitatedSpanningTree problem.
132    ///
133    /// # Panics
134    /// - If `weights.len() != graph.num_edges()`
135    /// - If `requirements.len() != graph.num_vertices()`
136    /// - If `root >= graph.num_vertices()`
137    /// - If `graph.num_vertices() < 2`
138    pub fn new(
139        graph: G,
140        weights: Vec<W>,
141        root: usize,
142        requirements: Vec<W>,
143        capacity: W::Sum,
144    ) -> Self {
145        Self::try_new(graph, weights, root, requirements, capacity)
146            .unwrap_or_else(|error| panic!("{error}"))
147    }
148
149    fn try_new(
150        graph: G,
151        weights: Vec<W>,
152        root: usize,
153        requirements: Vec<W>,
154        capacity: W::Sum,
155    ) -> Result<Self, crate::registry::ConstructionError> {
156        Self::check_weights(&graph, &weights)?;
157        if requirements.len() != graph.num_vertices() {
158            return Err(crate::registry::ConstructionError::length_mismatch(
159                "requirements",
160                requirements.len(),
161                graph.num_vertices(),
162            ));
163        }
164        if root >= graph.num_vertices() {
165            return Err(format!(
166                "root {root} out of range (num_vertices = {})",
167                graph.num_vertices()
168            )
169            .into());
170        }
171        if graph.num_vertices() < 2 {
172            return Err("graph must have at least 2 vertices".into());
173        }
174        Ok(Self {
175            graph,
176            weights,
177            root,
178            requirements,
179            capacity,
180        })
181    }
182
183    /// Get a reference to the underlying graph.
184    pub fn graph(&self) -> &G {
185        &self.graph
186    }
187
188    /// Get the edge weights.
189    pub fn weights(&self) -> &[W] {
190        &self.weights
191    }
192
193    /// Set new edge weights.
194    pub fn set_weights(&mut self, weights: Vec<W>) {
195        Self::check_weights(&self.graph, &weights).unwrap_or_else(|error| panic!("{error}"));
196        self.weights = weights;
197    }
198
199    fn check_weights(graph: &G, weights: &[W]) -> Result<(), crate::registry::ConstructionError> {
200        if weights.len() != graph.num_edges() {
201            return Err(crate::registry::ConstructionError::length_mismatch(
202                "weights",
203                weights.len(),
204                graph.num_edges(),
205            ));
206        }
207        Ok(())
208    }
209
210    /// Check if the problem uses a non-unit weight type.
211    pub fn is_weighted(&self) -> bool {
212        !W::IS_UNIT
213    }
214
215    /// Get the root vertex.
216    pub fn root(&self) -> usize {
217        self.root
218    }
219
220    /// Get the vertex requirements.
221    pub fn requirements(&self) -> &[W] {
222        &self.requirements
223    }
224
225    /// Get the capacity bound.
226    pub fn capacity(&self) -> &W::Sum {
227        &self.capacity
228    }
229
230    /// Smallest h >= 1 bounding vertex requirements and capacity in magnitude strictly by 2^h.
231    pub fn max_requirement_bits(&self) -> u64 {
232        crate::types::max_numeric_magnitude_bits(
233            self.requirements
234                .iter()
235                .map(|value| value.to_sum())
236                .chain(std::iter::once(self.capacity.clone())),
237        )
238    }
239
240    /// Get the number of vertices in the underlying graph.
241    pub fn num_vertices(&self) -> usize {
242        self.graph.num_vertices()
243    }
244
245    /// Get the number of edges in the underlying graph.
246    pub fn num_edges(&self) -> usize {
247        self.graph.num_edges()
248    }
249
250    /// Check if a configuration is a valid capacitated spanning tree.
251    pub fn is_valid_solution(
252        &self,
253        config: &[bool],
254    ) -> Result<bool, crate::traits::EvaluationError> {
255        is_valid_capacitated_spanning_tree(
256            &self.graph,
257            &self.requirements,
258            self.root,
259            &self.capacity,
260            config,
261        )
262    }
263}
264
265/// Check if a configuration forms a valid spanning tree:
266/// 1. Exactly n-1 edges selected
267/// 2. Selected edges form a connected subgraph
268fn is_spanning_tree<G: Graph>(graph: &G, config: &[bool]) -> bool {
269    let n = graph.num_vertices();
270    let edges = graph.edges();
271    if config.len() != edges.len() {
272        return false;
273    }
274
275    let selected_count = config.iter().filter(|&&selected| selected).count();
276    if selected_count != n - 1 {
277        return false;
278    }
279
280    // Build adjacency and BFS from vertex 0
281    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
282    for (idx, &sel) in config.iter().enumerate() {
283        if sel {
284            let (u, v) = edges[idx];
285            adj[u].push(v);
286            adj[v].push(u);
287        }
288    }
289
290    let mut visited = vec![false; n];
291    let mut queue = std::collections::VecDeque::new();
292    visited[0] = true;
293    queue.push_back(0);
294    while let Some(v) = queue.pop_front() {
295        for &u in &adj[v] {
296            if !visited[u] {
297                visited[u] = true;
298                queue.push_back(u);
299            }
300        }
301    }
302
303    visited.iter().all(|&v| v)
304}
305
306/// Compute the subtree requirement sum for each edge in the tree rooted at `root`.
307/// Returns None if the tree is invalid, otherwise returns the max subtree sum.
308fn check_capacity<G: Graph, W: WeightElement>(
309    graph: &G,
310    requirements: &[W],
311    root: usize,
312    capacity: &W::Sum,
313    config: &[bool],
314) -> Result<bool, crate::traits::EvaluationError> {
315    let n = graph.num_vertices();
316    let edges = graph.edges();
317
318    // Build adjacency list with edge indices
319    let mut adj: Vec<Vec<(usize, usize)>> = vec![vec![]; n]; // (neighbor, edge_idx)
320    for (idx, &sel) in config.iter().enumerate() {
321        if sel {
322            let (u, v) = edges[idx];
323            adj[u].push((v, idx));
324            adj[v].push((u, idx));
325        }
326    }
327
328    // Root the tree using BFS from root
329    let mut parent = vec![usize::MAX; n];
330    let mut order = Vec::with_capacity(n);
331    let mut visited = vec![false; n];
332    let mut queue = std::collections::VecDeque::new();
333    visited[root] = true;
334    parent[root] = root;
335    queue.push_back(root);
336    while let Some(v) = queue.pop_front() {
337        order.push(v);
338        for &(u, _) in &adj[v] {
339            if !visited[u] {
340                visited[u] = true;
341                parent[u] = v;
342                queue.push_back(u);
343            }
344        }
345    }
346
347    // Compute subtree sums bottom-up
348    let mut subtree_sum: Vec<W::Sum> = requirements.iter().map(|r| r.to_sum()).collect();
349    for &v in order.iter().rev() {
350        if v != root {
351            let p = parent[v];
352            let sv = subtree_sum[v].clone();
353            subtree_sum[p] = W::checked_add_to_sum(
354                subtree_sum[p].clone(),
355                sv,
356                "summing capacitated spanning tree requirements",
357            )?;
358        }
359    }
360
361    // Check capacity for each non-root vertex (its subtree sum is the flow on its parent edge)
362    for (v, sum) in subtree_sum.iter().enumerate() {
363        if v != root && *sum > *capacity {
364            return Ok(false);
365        }
366    }
367
368    Ok(true)
369}
370
371/// Check if a configuration forms a valid capacitated spanning tree.
372fn is_valid_capacitated_spanning_tree<G: Graph, W: WeightElement>(
373    graph: &G,
374    requirements: &[W],
375    root: usize,
376    capacity: &W::Sum,
377    config: &[bool],
378) -> Result<bool, crate::traits::EvaluationError> {
379    if !is_spanning_tree(graph, config) {
380        return Ok(false);
381    }
382    check_capacity(graph, requirements, root, capacity, config)
383}
384
385impl<G, W> Problem for MinimumCapacitatedSpanningTree<G, W>
386where
387    G: Graph + crate::variant::VariantParam,
388    W: WeightElement + crate::variant::VariantParam,
389{
390    const NAME: &'static str = "MinimumCapacitatedSpanningTree";
391    type Solution = Vec<bool>;
392    type Value = Min<W::Sum>;
393
394    crate::problem_parameters![
395        ("max_requirement_bits", max_requirement_bits),
396        ("num_edges", num_edges),
397        ("num_vertices", num_vertices),
398    ];
399
400    fn variant() -> Vec<(&'static str, &'static str)> {
401        crate::variant_params![G, W]
402    }
403
404    fn evaluate(
405        &self,
406        config: &Self::Solution,
407    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
408        if config.len() != self.graph.num_edges() {
409            return Err(crate::traits::EvaluationError::InvalidConfiguration(
410                "edge-selection length does not match the graph".into(),
411            ));
412        }
413        Ok({
414            if !is_valid_capacitated_spanning_tree(
415                &self.graph,
416                &self.requirements,
417                self.root,
418                &self.capacity,
419                config,
420            )? {
421                return Ok(Min(None));
422            }
423            let mut total = W::Sum::zero();
424            for (idx, &selected) in config.iter().enumerate() {
425                if selected {
426                    if let Some(w) = self.weights.get(idx) {
427                        total = W::checked_add_to_sum(
428                            total,
429                            w.to_sum(),
430                            "summing capacitated spanning tree edge weights",
431                        )?;
432                    }
433                }
434            }
435            Min(Some(total))
436        })
437    }
438}
439
440impl<G, W> crate::solvers::BruteForceProblem for MinimumCapacitatedSpanningTree<G, W>
441where
442    G: Graph + crate::variant::VariantParam,
443    W: WeightElement + crate::variant::VariantParam,
444{
445    fn dimensions(&self) -> Vec<usize> {
446        vec![2; self.graph.num_edges()]
447    }
448}
449
450crate::declare_variants! {
451    default MinimumCapacitatedSpanningTree<SimpleGraph, i64> => "2^num_edges" create MinimumCapacitatedSpanningTreeCreateSpec,
452}
453
454crate::register_brute_force! {
455    MinimumCapacitatedSpanningTree<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
456}
457
458#[cfg(feature = "example-db")]
459pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
460    vec![crate::example_db::specs::ModelExampleSpec {
461        id: "minimum_capacitated_spanning_tree_simplegraph",
462        instance: Box::new(MinimumCapacitatedSpanningTree::new(
463            SimpleGraph::new(
464                5,
465                vec![
466                    (0, 1),
467                    (0, 2),
468                    (0, 3),
469                    (1, 2),
470                    (1, 4),
471                    (2, 3),
472                    (2, 4),
473                    (3, 4),
474                ],
475            ),
476            vec![2, 1, 4, 3, 1, 2, 3, 1], // edge weights
477            0,                            // root
478            vec![0, 1, 1, 1, 1],          // requirements (root=0)
479            3,                            // capacity
480        )),
481        // Optimal: edges {(0,1),(0,2),(1,4),(3,4)} = indices {0,1,4,7}
482        // Weight = 2+1+1+1 = 5
483        // Subtree sums: subtree(1)={1,4}->req=2<=3, subtree(2)={2}->req=1<=3,
484        //   subtree(4)={4}->req=1<=3, subtree(3)={3}->req=1<=3
485        optimal_config: serde_json::json!(vec![true, true, false, false, true, false, false, true]),
486        optimal_value: serde_json::json!(5),
487    }]
488}
489
490#[cfg(test)]
491#[path = "../../unit_tests/models/graph/minimum_capacitated_spanning_tree.rs"]
492mod tests;
problemreductions/models/graph/minimum_capacitated_spanning_tree.rs

problemreductions/models/graph/
minimum_capacitated_spanning_tree.rs
