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

problemreductions/models/graph/
steiner_tree.rs
