problemreductions/models/graph/
steiner_tree.rs

1//! Steiner Tree problem implementation.
2//!
3//! Given a weighted graph and a set of terminal vertices, find a minimum-weight
4//! tree that connects all terminals.
5
6use std::collections::BTreeSet;
7
8use num_traits::Zero;
9use serde::{Deserialize, Serialize};
10
11use crate::{
12    registry::{CreateSpec, ProblemSchemaEntry, VariantDimension},
13    topology::{Graph, SimpleGraph},
14    traits::Problem,
15    types::{Min, One, WeightElement},
16};
17
18inventory::submit! {
19    ProblemSchemaEntry {
20        name: "SteinerTree",
21        display_name: "Steiner Tree",
22        aliases: &[],
23        dimensions: &[
24            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
25            VariantDimension::new("weight", "i64", &["One", "i64"]),
26        ],
27        category: crate::registry::ProblemCategory::Graph,
28        module_path: module_path!(),
29        description: "Find minimum weight tree connecting terminal vertices",
30        fields: SteinerTreeCreateSpec::<i64>::FIELDS,
31    }
32}
33
34/// The Steiner Tree problem.
35///
36/// Given a weighted graph G = (V, E) with edge weights w_e and a set
37/// of terminal vertices T, find a tree S in G such that T is a subset
38/// of V(S), minimizing the total edge weight of S.
39///
40/// # Representation
41///
42/// Each edge is assigned a binary variable:
43/// - 0: edge is not in the Steiner tree
44/// - 1: edge is in the Steiner tree
45///
46/// A valid Steiner tree requires:
47/// - Selected edges form a tree (connected + acyclic)
48/// - All terminal vertices are included
49///
50/// # Type Parameters
51///
52/// * `G` - The graph type (e.g., `SimpleGraph`)
53/// * `W` - The weight type for edges (e.g., `i64`, `f64`)
54#[derive(Debug, Clone, Serialize)]
55pub struct SteinerTree<G, W> {
56    /// The underlying graph.
57    graph: G,
58    /// Weights for each edge (in edge index order).
59    edge_weights: Vec<W>,
60    /// Terminal vertices that must be connected.
61    terminals: Vec<usize>,
62}
63
64impl<'de, G, W> Deserialize<'de> for SteinerTree<G, W>
65where
66    G: Graph + Deserialize<'de>,
67    W: Clone + Default + Deserialize<'de>,
68{
69    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
70    where
71        D: serde::Deserializer<'de>,
72    {
73        #[derive(Deserialize)]
74        struct Fields<G, W> {
75            graph: G,
76            edge_weights: Vec<W>,
77            terminals: Vec<usize>,
78        }
79
80        let fields = Fields::deserialize(deserializer)?;
81        Self::try_new(fields.graph, fields.edge_weights, fields.terminals)
82            .map_err(serde::de::Error::custom)
83    }
84}
85
86#[derive(Debug, Deserialize, crate::CreateSpec)]
87struct SteinerTreeCreateSpec<W> {
88    /// The underlying graph G=(V,E).
89    graph: SimpleGraph,
90    /// Edge weights w: E -> R.
91    edge_weights: Vec<W>,
92    /// Terminal vertices T that must be connected.
93    terminals: Vec<usize>,
94}
95
96impl<W: Clone + Default> TryFrom<SteinerTreeCreateSpec<W>> for SteinerTree<SimpleGraph, W> {
97    type Error = crate::registry::ConstructionError;
98    fn try_from(spec: SteinerTreeCreateSpec<W>) -> Result<Self, Self::Error> {
99        Self::try_new(spec.graph, spec.edge_weights, spec.terminals).map_err(Into::into)
100    }
101}
102
103impl<G: Graph, W: Clone + Default> SteinerTree<G, W> {
104    fn try_new(graph: G, edge_weights: Vec<W>, terminals: Vec<usize>) -> Result<Self, String> {
105        if edge_weights.len() != graph.num_edges() {
106            return Err("edge_weights length must match num_edges".into());
107        }
108        if terminals.len() < 2 {
109            return Err("at least 2 terminals required".into());
110        }
111        let distinct_terminals: BTreeSet<_> = terminals.iter().copied().collect();
112        if distinct_terminals.len() != terminals.len() {
113            return Err("terminals must be distinct".into());
114        }
115        let n = graph.num_vertices();
116        if let Some(&terminal) = terminals.iter().find(|&&terminal| terminal >= n) {
117            return Err(format!(
118                "terminal {terminal} out of range (num_vertices = {n})"
119            ));
120        }
121        Ok(Self {
122            graph,
123            edge_weights,
124            terminals,
125        })
126    }
127
128    /// Create a SteinerTree problem from a graph, edge weights, and terminals.
129    pub fn new(graph: G, edge_weights: Vec<W>, terminals: Vec<usize>) -> Self {
130        Self::try_new(graph, edge_weights, terminals).unwrap_or_else(|error| panic!("{error}"))
131    }
132
133    /// Create a SteinerTree problem with unit edge weights.
134    pub fn unit_weights(graph: G, terminals: Vec<usize>) -> Self
135    where
136        W: WeightElement,
137    {
138        let edge_weights = vec![W::unit(); graph.num_edges()];
139        Self::new(graph, edge_weights, terminals)
140    }
141
142    /// Get a reference to the underlying graph.
143    pub fn graph(&self) -> &G {
144        &self.graph
145    }
146
147    /// Get a reference to the edge weights.
148    pub fn edge_weights(&self) -> &[W] {
149        &self.edge_weights
150    }
151
152    /// Set new edge weights.
153    pub fn set_weights(&mut self, weights: Vec<W>) {
154        assert_eq!(weights.len(), self.graph.num_edges());
155        self.edge_weights = weights;
156    }
157
158    /// Get the edge weights as a Vec.
159    pub fn weights(&self) -> Vec<W> {
160        self.edge_weights.clone()
161    }
162
163    /// Get the terminal vertices.
164    pub fn terminals(&self) -> &[usize] {
165        &self.terminals
166    }
167
168    /// Check if the problem uses a non-unit weight type.
169    pub fn is_weighted(&self) -> bool
170    where
171        W: WeightElement,
172    {
173        !W::IS_UNIT
174    }
175
176    /// Check if a configuration is a valid Steiner tree.
177    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
178        is_valid_steiner_tree(&self.graph, &self.terminals, config)
179    }
180}
181
182impl<G: Graph, W: WeightElement> SteinerTree<G, W> {
183    /// Get the number of vertices in the underlying graph.
184    pub fn num_vertices(&self) -> usize {
185        self.graph.num_vertices()
186    }
187
188    /// Get the number of edges in the underlying graph.
189    pub fn num_edges(&self) -> usize {
190        self.graph.num_edges()
191    }
192
193    /// Get the number of terminal vertices.
194    pub fn num_terminals(&self) -> usize {
195        self.terminals.len()
196    }
197}
198
199/// Check if a configuration forms a valid Steiner tree:
200/// 1. Selected edges form a connected subgraph containing all terminals
201/// 2. Selected edges are acyclic (tree property)
202fn is_valid_steiner_tree<G: Graph>(graph: &G, terminals: &[usize], config: &[bool]) -> bool {
203    let n = graph.num_vertices();
204    let edges = graph.edges();
205    if config.len() != edges.len() {
206        return false;
207    }
208
209    // Build adjacency list from selected edges
210    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
211    let mut selected_count = 0usize;
212    let mut involved = vec![false; n];
213    for (idx, &sel) in config.iter().enumerate() {
214        if sel {
215            let (u, v) = edges[idx];
216            adj[u].push(v);
217            adj[v].push(u);
218            involved[u] = true;
219            involved[v] = true;
220            selected_count += 1;
221        }
222    }
223
224    if selected_count == 0 {
225        return false;
226    }
227
228    // BFS from first terminal to check connectivity
229    let start = terminals[0];
230    let mut visited = vec![false; n];
231    let mut queue = std::collections::VecDeque::new();
232    visited[start] = true;
233    queue.push_back(start);
234    while let Some(v) = queue.pop_front() {
235        for &u in &adj[v] {
236            if !visited[u] {
237                visited[u] = true;
238                queue.push_back(u);
239            }
240        }
241    }
242
243    // All terminals must be reachable
244    if !terminals.iter().all(|&t| visited[t]) {
245        return false;
246    }
247
248    // All involved vertices must be in one connected component
249    if (0..n).any(|i| involved[i] && !visited[i]) {
250        return false;
251    }
252
253    // Tree property: #edges == #involved_vertices - 1
254    let involved_count = involved.iter().filter(|&&x| x).count();
255    selected_count == involved_count - 1
256}
257
258impl<G, W> Problem for SteinerTree<G, W>
259where
260    G: Graph + crate::variant::VariantParam,
261    W: WeightElement + crate::variant::VariantParam,
262{
263    const NAME: &'static str = "SteinerTree";
264    type Solution = Vec<bool>;
265    type Value = Min<W::Sum>;
266
267    crate::problem_parameters![
268        ("num_edges", num_edges),
269        ("num_terminals", num_terminals),
270        ("num_vertices", num_vertices),
271    ];
272
273    fn variant() -> Vec<(&'static str, &'static str)> {
274        crate::variant_params![G, W]
275    }
276
277    fn evaluate(
278        &self,
279        config: &Self::Solution,
280    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
281        if config.len() != self.graph.num_edges() {
282            return Err(crate::traits::EvaluationError::InvalidConfiguration(
283                "edge-selection length does not match the graph".into(),
284            ));
285        }
286        Ok({
287            if !is_valid_steiner_tree(&self.graph, &self.terminals, config) {
288                return Ok(Min(None));
289            }
290            let mut total = W::Sum::zero();
291            for (idx, &selected) in config.iter().enumerate() {
292                if selected {
293                    if let Some(w) = self.edge_weights.get(idx) {
294                        total = W::checked_add_to_sum(
295                            total,
296                            w.to_sum(),
297                            "summing Steiner tree edge weights",
298                        )?;
299                    }
300                }
301            }
302            Min(Some(total))
303        })
304    }
305}
306
307impl<G, W> crate::solvers::BruteForceProblem for SteinerTree<G, W>
308where
309    G: Graph + crate::variant::VariantParam,
310    W: WeightElement + crate::variant::VariantParam,
311{
312    fn dimensions(&self) -> Vec<usize> {
313        vec![2; self.graph.num_edges()]
314    }
315}
316
317crate::impl_random_generate!(SteinerTree<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
318    if spec.num_vertices < 2 {
319        return Err("num_vertices must be at least 2".to_string().into());
320    }
321    let mut state = crate::random::lcg_init(crate::random::seed_to_u64(spec.seed)?);
322    let graph = spec.graph()?;
323    for _ in 0..spec.num_vertices * spec.num_vertices {
324        crate::random::lcg_step(&mut state);
325    }
326    let weights = (0..graph.num_edges()).map(|_| (crate::random::lcg_step(&mut state) * 9.0) as i64 + 1).collect();
327    let count = std::cmp::max(2, spec.num_vertices * 2 / 5);
328    let terminals = crate::random::lcg_choose(&mut state, spec.num_vertices, count)
329        .map_err(|error| error.to_string())?;
330    Ok(SteinerTree::new(graph, weights, terminals))
331});
332
333#[derive(Debug, Deserialize, crate::CreateSpec)]
334struct SteinerTreeOneCreateSpec {
335    /// The underlying graph.
336    graph: SimpleGraph,
337    terminals: Vec<usize>,
338}
339
340impl TryFrom<SteinerTreeOneCreateSpec> for SteinerTree<SimpleGraph, One> {
341    type Error = crate::registry::ConstructionError;
342    fn try_from(spec: SteinerTreeOneCreateSpec) -> Result<Self, Self::Error> {
343        let weights = vec![One; spec.graph.num_edges()];
344        Self::try_new(spec.graph, weights, spec.terminals).map_err(Into::into)
345    }
346}
347
348crate::declare_variants! {
349    default SteinerTree<SimpleGraph, i64> => "3^num_terminals * num_vertices + 2^num_terminals * num_vertices^2" create SteinerTreeCreateSpec<i64> random,
350    SteinerTree<SimpleGraph, One> => "3^num_terminals * num_vertices + 2^num_terminals * num_vertices^2" create SteinerTreeOneCreateSpec,
351}
352
353crate::register_brute_force! {
354    SteinerTree<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
355    SteinerTree<SimpleGraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
356}
357
358#[cfg(feature = "example-db")]
359pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
360    vec![crate::example_db::specs::ModelExampleSpec {
361        id: "steiner_tree_simplegraph",
362        instance: Box::new(SteinerTree::new(
363            SimpleGraph::new(
364                5,
365                vec![(0, 1), (0, 3), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
366            ),
367            vec![2, 5, 2, 1, 5, 6, 1],
368            vec![0, 2, 4],
369        )),
370        optimal_config: serde_json::json!(vec![true, false, true, true, false, false, true]),
371        optimal_value: serde_json::json!(6),
372    }]
373}
374
375#[cfg(test)]
376#[path = "../../unit_tests/models/graph/steiner_tree.rs"]
377mod tests;
problemreductions/models/graph/steiner_tree.rs

problemreductions/models/graph/
steiner_tree.rs
