problemreductions/models/graph/
prize_collecting_steiner_forest.rs

1//! Prize-Collecting Steiner Forest problem implementation.
2//!
3//! Given an undirected network `G = (V, E)` with nonnegative vertex prizes
4//! `p: V -> R_{>=0}`, nonnegative edge costs `c: E -> R_{>=0}`, and
5//! nonnegative tradeoff parameters `beta` and `omega`, find a forest
6//! `F = (V_F, E_F)` -- a subgraph that is a disjoint union of trees,
7//! including singleton-vertex trees -- minimizing
8//!
9//! ```text
10//! beta * sum_{v in V \ V_F} p(v) + sum_{e in E_F} c(e) + omega * kappa(F),
11//! ```
12//!
13//! where `kappa(F)` is the number of (tree) components of `F`. Singleton
14//! selected vertices are allowed and count as one-vertex tree components;
15//! unselected vertices are not part of any component.
16//!
17//! Reference:
18//! - Nurcan Tuncbag, Alfredo Braunstein, Andrea Pagnani, Shao-Shan Carol
19//!   Huang, Jennifer Chayes, Christian Borgs, Riccardo Zecchina, and Ernest
20//!   Fraenkel. "Simultaneous Reconstruction of Multiple Signaling Pathways
21//!   via the Prize-Collecting Steiner Forest Problem." Journal of
22//!   Computational Biology 20(2):124--136, 2013.
23//!   <https://doi.org/10.1089/cmb.2012.0092>
24//! - Earlier conference version, RECOMB 2012, LNBI 7262, pp. 287--301.
25//!   <https://doi.org/10.1007/978-3-642-29627-7_31>
26
27use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry, VariantDimension};
28use crate::topology::{Graph, SimpleGraph};
29use crate::traits::Problem;
30use crate::types::{Min, WeightElement};
31use crate::variant::VariantParam;
32use num_traits::Zero;
33use serde::{Deserialize, Serialize};
34use std::collections::VecDeque;
35
36inventory::submit! {
37    ProblemSchemaEntry {
38        name: "PrizeCollectingSteinerForest",
39        display_name: "Prize-Collecting Steiner Forest",
40        aliases: &[],
41        dimensions: &[
42            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
43            VariantDimension::new("weight", "i32", &["i32", "f64"]),
44        ],
45        module_path: module_path!(),
46        description: "Find a forest minimizing omitted-prize plus edge-cost plus omega times the number of tree components",
47        fields: &[
48            FieldInfo { name: "graph", type_name: "G", description: "The underlying network G=(V,E)" },
49            FieldInfo { name: "vertex_prizes", type_name: "Vec<W>", description: "Nonnegative vertex prizes p: V -> R_{>=0}" },
50            FieldInfo { name: "edge_costs", type_name: "Vec<W>", description: "Nonnegative edge costs c: E -> R_{>=0} in graph.edges() order" },
51            FieldInfo { name: "beta", type_name: "W", description: "Tradeoff coefficient beta >= 0 on the omitted-prize term" },
52            FieldInfo { name: "omega", type_name: "W", description: "Per-component penalty omega >= 0 on the number of tree components" },
53        ],
54    }
55}
56
57inventory::submit! {
58    ProblemSizeFieldEntry {
59        name: "PrizeCollectingSteinerForest",
60        fields: &["num_vertices", "num_edges", "num_vertices_with_prize"],
61    }
62}
63
64/// The Prize-Collecting Steiner Forest problem (biology-paper variant).
65///
66/// Configuration layout (length `num_vertices + num_edges`):
67/// - the first `num_vertices` bits are vertex selectors `x_v` (1 iff
68///   `v in V_F`),
69/// - the next `num_edges` bits are edge selectors `y_e` (1 iff `e in E_F`),
70///   in `graph.edges()` order.
71///
72/// A configuration is feasible iff every selected edge has both endpoints
73/// selected and the resulting subgraph is acyclic. Singleton selected
74/// vertices are allowed.
75///
76/// # Type Parameters
77///
78/// * `G` - Graph type (currently `SimpleGraph`).
79/// * `W` - Weight / cost type (e.g., `i32`, `f64`).
80///
81/// # Example
82///
83/// ```
84/// use problemreductions::models::graph::PrizeCollectingSteinerForest;
85/// use problemreductions::topology::SimpleGraph;
86/// use problemreductions::types::Min;
87/// use problemreductions::{BruteForce, Problem, Solver};
88///
89/// // Path 0 - 1 - 2 with edge costs c(0,1)=1, c(1,2)=6 and vertex prizes
90/// // p = (5, 2, 5), beta = 1, omega = 2.
91/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
92/// let problem =
93///     PrizeCollectingSteinerForest::<_, i32>::new(graph, vec![5, 2, 5], vec![1, 6], 1, 2);
94/// // V_F = {0,1,2}, E_F = {(0,1)} gives two components {0,1} and {2}:
95/// // objective = 0 + 1 + 2*2 = 5.
96/// assert_eq!(BruteForce::new().solve(&problem), Min(Some(5)));
97/// ```
98#[derive(Debug, Clone, Serialize, Deserialize)]
99#[serde(bound(deserialize = "G: serde::Deserialize<'de>, W: serde::Deserialize<'de>"))]
100pub struct PrizeCollectingSteinerForest<G, W> {
101    /// The underlying network.
102    graph: G,
103    /// Vertex prizes `p: V -> R_{>=0}` (in vertex-index order).
104    vertex_prizes: Vec<W>,
105    /// Edge costs `c: E -> R_{>=0}` (in `graph.edges()` order).
106    edge_costs: Vec<W>,
107    /// Tradeoff coefficient on the omitted-prize term.
108    beta: W,
109    /// Per-component penalty.
110    omega: W,
111}
112
113impl<G: Graph, W: Clone + Default> PrizeCollectingSteinerForest<G, W> {
114    /// Create a new Prize-Collecting Steiner Forest instance.
115    ///
116    /// # Panics
117    /// Panics if `vertex_prizes.len() != graph.num_vertices()` or
118    /// `edge_costs.len() != graph.num_edges()`.
119    pub fn new(graph: G, vertex_prizes: Vec<W>, edge_costs: Vec<W>, beta: W, omega: W) -> Self {
120        assert_eq!(
121            vertex_prizes.len(),
122            graph.num_vertices(),
123            "vertex_prizes length must match graph num_vertices"
124        );
125        assert_eq!(
126            edge_costs.len(),
127            graph.num_edges(),
128            "edge_costs length must match graph num_edges"
129        );
130        Self {
131            graph,
132            vertex_prizes,
133            edge_costs,
134            beta,
135            omega,
136        }
137    }
138
139    /// Reference to the underlying graph.
140    pub fn graph(&self) -> &G {
141        &self.graph
142    }
143
144    /// Vertex prizes in vertex-index order.
145    pub fn vertex_prizes(&self) -> &[W] {
146        &self.vertex_prizes
147    }
148
149    /// Edge costs in `graph.edges()` order.
150    pub fn edge_costs(&self) -> &[W] {
151        &self.edge_costs
152    }
153
154    /// Tradeoff coefficient on the omitted-prize term.
155    pub fn beta(&self) -> &W {
156        &self.beta
157    }
158
159    /// Per-component penalty.
160    pub fn omega(&self) -> &W {
161        &self.omega
162    }
163}
164
165impl<G: Graph, W: WeightElement> PrizeCollectingSteinerForest<G, W> {
166    /// Number of vertices in the underlying graph.
167    pub fn num_vertices(&self) -> usize {
168        self.graph.num_vertices()
169    }
170
171    /// Number of edges in the underlying graph.
172    pub fn num_edges(&self) -> usize {
173        self.graph.num_edges()
174    }
175
176    /// Number of vertices with a strictly positive prize, i.e.
177    /// `|{ v in V : p(v) > 0 }|`.
178    pub fn num_vertices_with_prize(&self) -> usize {
179        let zero = <W::Sum as Zero>::zero();
180        self.vertex_prizes
181            .iter()
182            .filter(|prize| prize.to_sum() > zero)
183            .count()
184    }
185
186    /// Whether this configuration is a feasible forest (selected edges only
187    /// touch selected vertices and induce an acyclic subgraph).
188    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
189        forest_components(&self.graph, config).is_some()
190    }
191}
192
193impl<G, W> Problem for PrizeCollectingSteinerForest<G, W>
194where
195    G: Graph + VariantParam,
196    W: WeightElement + VariantParam,
197{
198    const NAME: &'static str = "PrizeCollectingSteinerForest";
199    type Value = Min<W::Sum>;
200
201    fn variant() -> Vec<(&'static str, &'static str)> {
202        crate::variant_params![G, W]
203    }
204
205    fn dims(&self) -> Vec<usize> {
206        vec![2; self.graph.num_vertices() + self.graph.num_edges()]
207    }
208
209    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
210        let n = self.graph.num_vertices();
211        let kappa = match forest_components(&self.graph, config) {
212            Some(kappa) => kappa,
213            None => return Min(None),
214        };
215
216        // Objective: beta * sum_{v notin V_F} p(v)
217        //          + sum_{e in E_F} c(e)
218        //          + omega * kappa(F).
219        //
220        // `W::Sum: Num` (via `NumericSize`) gives us `Mul`, so we form the
221        // products `beta * (omitted prize sum)` and `omega * kappa` directly.
222        let mut omitted_prizes = W::Sum::zero();
223        for (v, prize) in self.vertex_prizes.iter().enumerate() {
224            if config[v] == 0 {
225                omitted_prizes += prize.to_sum();
226            }
227        }
228        let omitted_term = self.beta.to_sum() * omitted_prizes;
229
230        let mut edge_term = W::Sum::zero();
231        for (i, cost) in self.edge_costs.iter().enumerate() {
232            if config[n + i] == 1 {
233                edge_term += cost.to_sum();
234            }
235        }
236
237        // Represent `kappa` in `W::Sum` by summing `omega` `kappa` times.
238        // `NumericSize` does not require a `From<usize>` conversion, so we
239        // accumulate additively rather than casting.
240        let omega_sum = self.omega.to_sum();
241        let mut kappa_sum = W::Sum::zero();
242        for _ in 0..kappa {
243            kappa_sum += omega_sum.clone();
244        }
245
246        let mut total = W::Sum::zero();
247        total += omitted_term;
248        total += edge_term;
249        total += kappa_sum;
250        Min(Some(total))
251    }
252}
253
254/// Validate a `(V_F, E_F)` configuration and, if feasible, return the number of
255/// tree components `kappa(F)` among the selected vertices. Feasible means every
256/// selected edge is incident only to selected vertices and the selected
257/// subgraph is acyclic. Returns `None` for any infeasible configuration.
258fn forest_components<G: Graph>(graph: &G, config: &[usize]) -> Option<usize> {
259    let n = graph.num_vertices();
260    let m = graph.num_edges();
261    if config.len() != n + m {
262        return None;
263    }
264    let edges = graph.edges();
265    let mut adj: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n];
266    for (i, &(u, v)) in edges.iter().enumerate() {
267        let y_e = config[n + i];
268        if y_e == 0 {
269            continue;
270        }
271        if y_e != 1 {
272            return None;
273        }
274        if config[u] != 1 || config[v] != 1 {
275            return None;
276        }
277        adj[u].push((v, i));
278        adj[v].push((u, i));
279    }
280    let mut visited = vec![false; n];
281    let mut kappa: usize = 0;
282    for start in 0..n {
283        if config[start] != 1 || visited[start] {
284            continue;
285        }
286        kappa += 1;
287        visited[start] = true;
288        let mut parent_edge: Vec<Option<usize>> = vec![None; n];
289        let mut queue: VecDeque<usize> = VecDeque::new();
290        queue.push_back(start);
291        while let Some(u) = queue.pop_front() {
292            for &(w, edge_idx) in &adj[u] {
293                if parent_edge[u] == Some(edge_idx) {
294                    continue;
295                }
296                if visited[w] {
297                    return None; // back-edge inside the component => cycle
298                }
299                visited[w] = true;
300                parent_edge[w] = Some(edge_idx);
301                queue.push_back(w);
302            }
303        }
304    }
305    Some(kappa)
306}
307
308crate::declare_variants! {
309    default PrizeCollectingSteinerForest<SimpleGraph, i32> => "2^(num_vertices + num_edges)",
310    PrizeCollectingSteinerForest<SimpleGraph, f64> => "2^(num_vertices + num_edges)",
311}
312
313#[cfg(feature = "example-db")]
314pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
315    // Issue #1026 canonical instance: path 0 - 1 - 2 with edge costs
316    // c(0,1)=1, c(1,2)=6, vertex prizes p = (5, 2, 5), beta = 1, omega = 2.
317    // Optimum: V_F = {0,1,2}, E_F = {(0,1)} (two components {0,1} and {2}),
318    // objective = 0 + 1 + 2*2 = 5.
319    vec![crate::example_db::specs::ModelExampleSpec {
320        id: "prize_collecting_steiner_forest_simplegraph_i32",
321        instance: Box::new(PrizeCollectingSteinerForest::<SimpleGraph, i32>::new(
322            SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
323            vec![5, 2, 5],
324            vec![1, 6],
325            1,
326            2,
327        )),
328        // 3 vertex bits + 2 edge bits = 5-bit configuration.
329        optimal_config: vec![1, 1, 1, 1, 0],
330        optimal_value: serde_json::json!(5),
331    }]
332}
333
334#[cfg(test)]
335#[path = "../../unit_tests/models/graph/prize_collecting_steiner_forest.rs"]
336mod tests;
problemreductions/models/graph/prize_collecting_steiner_forest.rs

problemreductions/models/graph/
prize_collecting_steiner_forest.rs
