problemreductions/models/graph/
shortest_weight_constrained_path.rs

1//! Shortest Weight-Constrained Path problem implementation.
2//!
3//! The Shortest Weight-Constrained Path problem finds a simple path from a
4//! source vertex to a target vertex that minimizes total length while keeping
5//! the total weight within a prescribed bound.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::{Min, WeightElement};
11use num_traits::Zero;
12use serde::{Deserialize, Serialize};
13use std::collections::VecDeque;
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "ShortestWeightConstrainedPath",
18        display_name: "Shortest Weight-Constrained Path",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
22            VariantDimension::new("weight", "i32", &["i32"]),
23        ],
24        module_path: module_path!(),
25        description: "Find a simple s-t path minimizing total length subject to a weight budget",
26        fields: &[
27            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
28            FieldInfo { name: "edge_lengths", type_name: "Vec<W>", description: "Edge lengths l: E -> ZZ_(> 0)" },
29            FieldInfo { name: "edge_weights", type_name: "Vec<W>", description: "Edge weights w: E -> ZZ_(> 0)" },
30            FieldInfo { name: "source_vertex", type_name: "usize", description: "Source vertex s" },
31            FieldInfo { name: "target_vertex", type_name: "usize", description: "Target vertex t" },
32            FieldInfo { name: "weight_bound", type_name: "W::Sum", description: "Upper bound W on total path weight" },
33        ],
34    }
35}
36
37/// The Shortest Weight-Constrained Path problem.
38///
39/// Given a graph G = (V, E) with positive edge lengths l(e) and edge weights
40/// w(e), designated vertices s and t, and a weight bound W, find a simple
41/// path from s to t that minimizes total length subject to total weight at
42/// most W.
43///
44/// # Representation
45///
46/// Each edge is assigned a binary variable:
47/// - 0: edge is not in the selected path
48/// - 1: edge is in the selected path
49///
50/// A valid configuration must:
51/// - form a single simple path from `source_vertex` to `target_vertex`
52/// - use only edges present in the graph
53/// - satisfy the weight bound
54///
55/// The objective value is the total length of the path (`Min<N::Sum>`).
56///
57/// # Type Parameters
58///
59/// * `G` - The graph type (e.g., `SimpleGraph`)
60/// * `N` - The edge length / weight type (e.g., `i32`, `f64`)
61#[derive(Debug, Clone, Serialize, Deserialize)]
62pub struct ShortestWeightConstrainedPath<G, N: WeightElement> {
63    /// The underlying graph.
64    graph: G,
65    /// Length for each edge in graph-edge order.
66    edge_lengths: Vec<N>,
67    /// Weight for each edge in graph-edge order.
68    edge_weights: Vec<N>,
69    /// Source vertex s.
70    source_vertex: usize,
71    /// Target vertex t.
72    target_vertex: usize,
73    /// Upper bound W on total path weight.
74    weight_bound: N::Sum,
75}
76
77impl<G: Graph, N: WeightElement> ShortestWeightConstrainedPath<G, N> {
78    fn assert_positive_edge_values(values: &[N], label: &str) {
79        let zero = N::Sum::zero();
80        assert!(
81            values.iter().all(|value| value.to_sum() > zero.clone()),
82            "All {label} must be positive (> 0)"
83        );
84    }
85
86    fn assert_positive_bound(bound: &N::Sum, label: &str) {
87        let zero = N::Sum::zero();
88        assert!(bound > &zero, "{label} must be positive (> 0)");
89    }
90
91    /// Create a new ShortestWeightConstrainedPath instance.
92    ///
93    /// # Panics
94    ///
95    /// Panics if either edge vector length does not match the graph's edge
96    /// count, or if the source / target vertices are out of bounds.
97    pub fn new(
98        graph: G,
99        edge_lengths: Vec<N>,
100        edge_weights: Vec<N>,
101        source_vertex: usize,
102        target_vertex: usize,
103        weight_bound: N::Sum,
104    ) -> Self {
105        assert_eq!(
106            edge_lengths.len(),
107            graph.num_edges(),
108            "edge_lengths length must match num_edges"
109        );
110        assert_eq!(
111            edge_weights.len(),
112            graph.num_edges(),
113            "edge_weights length must match num_edges"
114        );
115        Self::assert_positive_edge_values(&edge_lengths, "edge lengths");
116        Self::assert_positive_edge_values(&edge_weights, "edge weights");
117        assert!(
118            source_vertex < graph.num_vertices(),
119            "source_vertex {} out of bounds (graph has {} vertices)",
120            source_vertex,
121            graph.num_vertices()
122        );
123        assert!(
124            target_vertex < graph.num_vertices(),
125            "target_vertex {} out of bounds (graph has {} vertices)",
126            target_vertex,
127            graph.num_vertices()
128        );
129        Self::assert_positive_bound(&weight_bound, "weight_bound");
130        Self {
131            graph,
132            edge_lengths,
133            edge_weights,
134            source_vertex,
135            target_vertex,
136            weight_bound,
137        }
138    }
139
140    /// Get a reference to the underlying graph.
141    pub fn graph(&self) -> &G {
142        &self.graph
143    }
144
145    /// Get the edge lengths.
146    pub fn edge_lengths(&self) -> &[N] {
147        &self.edge_lengths
148    }
149
150    /// Get the edge weights.
151    pub fn edge_weights(&self) -> &[N] {
152        &self.edge_weights
153    }
154
155    /// Set new edge lengths.
156    pub fn set_lengths(&mut self, edge_lengths: Vec<N>) {
157        assert_eq!(
158            edge_lengths.len(),
159            self.graph.num_edges(),
160            "edge_lengths length must match num_edges"
161        );
162        Self::assert_positive_edge_values(&edge_lengths, "edge lengths");
163        self.edge_lengths = edge_lengths;
164    }
165
166    /// Set new edge weights.
167    pub fn set_weights(&mut self, edge_weights: Vec<N>) {
168        assert_eq!(
169            edge_weights.len(),
170            self.graph.num_edges(),
171            "edge_weights length must match num_edges"
172        );
173        Self::assert_positive_edge_values(&edge_weights, "edge weights");
174        self.edge_weights = edge_weights;
175    }
176
177    /// Get the source vertex.
178    pub fn source_vertex(&self) -> usize {
179        self.source_vertex
180    }
181
182    /// Get the target vertex.
183    pub fn target_vertex(&self) -> usize {
184        self.target_vertex
185    }
186
187    /// Get the weight bound.
188    pub fn weight_bound(&self) -> &N::Sum {
189        &self.weight_bound
190    }
191
192    /// Check whether this problem uses a non-unit weight type.
193    pub fn is_weighted(&self) -> bool {
194        !N::IS_UNIT
195    }
196
197    /// Get the number of vertices in the graph.
198    pub fn num_vertices(&self) -> usize {
199        self.graph.num_vertices()
200    }
201
202    /// Get the number of edges in the graph.
203    pub fn num_edges(&self) -> usize {
204        self.graph.num_edges()
205    }
206
207    /// Check if a configuration is a valid weight-constrained s-t path.
208    ///
209    /// Returns `Some(total_length)` for a valid simple s-t path whose total
210    /// weight is within the weight bound, or `None` otherwise.
211    pub fn is_valid_solution(&self, config: &[usize]) -> Option<N::Sum> {
212        if config.len() != self.graph.num_edges() || config.iter().any(|&value| value > 1) {
213            return None;
214        }
215
216        if self.source_vertex == self.target_vertex {
217            if config.contains(&1) {
218                return None;
219            }
220            return Some(N::Sum::zero());
221        }
222
223        let edges = self.graph.edges();
224        let mut degree = vec![0usize; self.graph.num_vertices()];
225        let mut adjacency = vec![Vec::new(); self.graph.num_vertices()];
226        let mut selected_edge_count = 0usize;
227        let mut total_length = N::Sum::zero();
228        let mut total_weight = N::Sum::zero();
229
230        for (idx, &selected) in config.iter().enumerate() {
231            if selected == 0 {
232                continue;
233            }
234            let (u, v) = edges[idx];
235            degree[u] += 1;
236            degree[v] += 1;
237            adjacency[u].push(v);
238            adjacency[v].push(u);
239            selected_edge_count += 1;
240            total_length += self.edge_lengths[idx].to_sum();
241            total_weight += self.edge_weights[idx].to_sum();
242        }
243
244        if selected_edge_count == 0 {
245            return None;
246        }
247
248        if total_weight > self.weight_bound.clone() {
249            return None;
250        }
251
252        if degree[self.source_vertex] != 1 || degree[self.target_vertex] != 1 {
253            return None;
254        }
255
256        for (vertex, &vertex_degree) in degree.iter().enumerate() {
257            if vertex == self.source_vertex || vertex == self.target_vertex {
258                continue;
259            }
260            if vertex_degree != 0 && vertex_degree != 2 {
261                return None;
262            }
263        }
264
265        let mut visited = vec![false; self.graph.num_vertices()];
266        let mut queue = VecDeque::new();
267        visited[self.source_vertex] = true;
268        queue.push_back(self.source_vertex);
269
270        while let Some(vertex) = queue.pop_front() {
271            for &neighbor in &adjacency[vertex] {
272                if !visited[neighbor] {
273                    visited[neighbor] = true;
274                    queue.push_back(neighbor);
275                }
276            }
277        }
278
279        if !visited[self.target_vertex] {
280            return None;
281        }
282
283        let used_vertex_count = degree
284            .iter()
285            .filter(|&&vertex_degree| vertex_degree > 0)
286            .count();
287        for (vertex, &vertex_degree) in degree.iter().enumerate() {
288            if vertex_degree > 0 && !visited[vertex] {
289                return None;
290            }
291        }
292
293        if used_vertex_count == selected_edge_count + 1 {
294            Some(total_length)
295        } else {
296            None
297        }
298    }
299}
300
301impl<G, N> Problem for ShortestWeightConstrainedPath<G, N>
302where
303    G: Graph + crate::variant::VariantParam,
304    N: WeightElement + crate::variant::VariantParam,
305{
306    const NAME: &'static str = "ShortestWeightConstrainedPath";
307    type Value = Min<N::Sum>;
308
309    fn variant() -> Vec<(&'static str, &'static str)> {
310        crate::variant_params![G, N]
311    }
312
313    fn dims(&self) -> Vec<usize> {
314        vec![2; self.graph.num_edges()]
315    }
316
317    fn evaluate(&self, config: &[usize]) -> Min<N::Sum> {
318        Min(self.is_valid_solution(config))
319    }
320}
321
322#[cfg(feature = "example-db")]
323pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
324    vec![crate::example_db::specs::ModelExampleSpec {
325        id: "shortest_weight_constrained_path_simplegraph_i32",
326        instance: Box::new(ShortestWeightConstrainedPath::new(
327            SimpleGraph::new(
328                6,
329                vec![
330                    (0, 1),
331                    (0, 2),
332                    (1, 3),
333                    (2, 3),
334                    (2, 4),
335                    (3, 5),
336                    (4, 5),
337                    (1, 4),
338                ],
339            ),
340            vec![2, 4, 3, 1, 5, 4, 2, 6],
341            vec![5, 1, 2, 3, 2, 3, 1, 1],
342            0,
343            5,
344            8,
345        )),
346        optimal_config: vec![0, 1, 0, 1, 0, 1, 0, 0],
347        optimal_value: serde_json::json!(9),
348    }]
349}
350
351crate::declare_variants! {
352    default ShortestWeightConstrainedPath<SimpleGraph, i32> => "2^num_edges",
353}
354
355#[cfg(test)]
356#[path = "../../unit_tests/models/graph/shortest_weight_constrained_path.rs"]
357mod tests;
problemreductions/models/graph/shortest_weight_constrained_path.rs

problemreductions/models/graph/
shortest_weight_constrained_path.rs
