problemreductions/models/graph/
length_bounded_disjoint_paths.rs

1//! Length-Bounded Disjoint Paths problem implementation.
2//!
3//! The problem maximizes the number of internally vertex-disjoint `s-t` paths,
4//! each using at most `K` edges, over up to `max_paths` path slots.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{is_simple_st_path, Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Max;
10use crate::variant::VariantParam;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "LengthBoundedDisjointPaths",
16        display_name: "Length-Bounded Disjoint Paths",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Maximize the number of internally vertex-disjoint s-t paths of length at most K",
24        fields: LengthBoundedDisjointPathsCreateSpec::FIELDS,
25    }
26}
27
28/// Length-Bounded Disjoint Paths on an undirected graph.
29///
30/// A configuration uses `max_paths * |E|` binary choices. For each path slot
31/// `j` and edge `e` in `graph.edges()` order, `x_{j,e} = 1` means that the
32/// path uses that edge. Each non-empty slot must form a simple `s-t` path, and the internal
33/// vertices of different slots must be disjoint. Empty slots (all zeros) are
34/// unused and do not count toward the objective. The objective is to maximize
35/// the number of non-empty valid path slots.
36#[derive(Debug, Clone, Serialize, Deserialize)]
37#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
38pub struct LengthBoundedDisjointPaths<G> {
39    graph: G,
40    source: usize,
41    sink: usize,
42    max_paths: usize,
43    max_length: usize,
44}
45
46#[derive(Debug, Deserialize, crate::CreateSpec)]
47struct LengthBoundedDisjointPathsCreateSpec {
48    /// Undirected graph edges.
49    #[create(codec = "edge-list")]
50    graph: Vec<(usize, usize)>,
51    /// Vertex count, needed to preserve isolated vertices.
52    num_vertices: Option<usize>,
53    /// Shared source vertex.
54    source: usize,
55    /// Shared sink vertex.
56    sink: usize,
57    /// Maximum path length in edges.
58    max_length: usize,
59}
60
61#[derive(Debug, Deserialize, crate::CreateSpec)]
62struct LengthBoundedDisjointPathsRandomSpec {
63    /// Number of graph vertices.
64    num_vertices: usize,
65    /// Independent edge probability (default: 0.5).
66    edge_prob: Option<f64>,
67    /// Seed for reproducible generation.
68    seed: Option<i64>,
69    /// Source vertex (default: 0).
70    source: Option<usize>,
71    /// Sink vertex (default: the final vertex).
72    sink: Option<usize>,
73    /// Maximum path length (default: num_vertices - 1).
74    max_length: Option<usize>,
75}
76
77impl TryFrom<LengthBoundedDisjointPathsCreateSpec> for LengthBoundedDisjointPaths<SimpleGraph> {
78    type Error = crate::registry::ConstructionError;
79
80    fn try_from(spec: LengthBoundedDisjointPathsCreateSpec) -> Result<Self, Self::Error> {
81        if spec.graph.is_empty() && spec.num_vertices.is_none() {
82            return Err("num_vertices is required for an empty graph"
83                .to_string()
84                .into());
85        }
86        for (index, &(u, v)) in spec.graph.iter().enumerate() {
87            if u == v {
88                return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
89            }
90        }
91        let inferred = spec
92            .graph
93            .iter()
94            .flat_map(|&(u, v)| [u, v])
95            .max()
96            .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
97            .transpose()?
98            .unwrap_or(0);
99        let num_vertices = spec.num_vertices.unwrap_or(inferred);
100        if num_vertices < inferred {
101            return Err(format!(
102                "num_vertices {num_vertices} is too small for graph endpoints; need at least {inferred}"
103            ).into());
104        }
105        if spec.source >= num_vertices || spec.sink >= num_vertices {
106            return Err("source and sink must be valid graph vertices"
107                .to_string()
108                .into());
109        }
110        if spec.source == spec.sink {
111            return Err("source and sink must be distinct".to_string().into());
112        }
113        if spec.max_length == 0 {
114            return Err("max_length must be positive".to_string().into());
115        }
116
117        let graph = SimpleGraph::new(num_vertices, spec.graph);
118        let max_paths = graph
119            .neighbors(spec.source)
120            .len()
121            .min(graph.neighbors(spec.sink).len());
122        Ok(Self {
123            graph,
124            source: spec.source,
125            sink: spec.sink,
126            max_paths,
127            max_length: spec.max_length,
128        })
129    }
130}
131
132impl<G: Graph> LengthBoundedDisjointPaths<G> {
133    /// Create a new Length-Bounded Disjoint Paths instance.
134    ///
135    /// The `max_paths` upper bound is computed automatically as
136    /// `min(deg(source), deg(sink))`.
137    ///
138    /// # Panics
139    ///
140    /// Panics if `source` or `sink` is not a valid graph vertex, if `source ==
141    /// sink`, or if `max_length == 0`.
142    pub fn new(graph: G, source: usize, sink: usize, max_length: usize) -> Self {
143        assert!(
144            source < graph.num_vertices(),
145            "source must be a valid graph vertex"
146        );
147        assert!(
148            sink < graph.num_vertices(),
149            "sink must be a valid graph vertex"
150        );
151        assert_ne!(source, sink, "source and sink must be distinct");
152        assert!(max_length > 0, "max_length must be positive");
153        let deg_s = graph.neighbors(source).len();
154        let deg_t = graph.neighbors(sink).len();
155        let max_paths = deg_s.min(deg_t);
156        Self {
157            graph,
158            source,
159            sink,
160            max_paths,
161            max_length,
162        }
163    }
164
165    /// Get a reference to the underlying graph.
166    pub fn graph(&self) -> &G {
167        &self.graph
168    }
169
170    /// Get the shared source vertex.
171    pub fn source(&self) -> usize {
172        self.source
173    }
174
175    /// Get the shared sink vertex.
176    pub fn sink(&self) -> usize {
177        self.sink
178    }
179
180    /// Get the upper bound on the number of path slots.
181    pub fn max_paths(&self) -> usize {
182        self.max_paths
183    }
184
185    /// Get the maximum permitted path length in edges.
186    pub fn max_length(&self) -> usize {
187        self.max_length
188    }
189
190    /// Get the number of vertices in the graph.
191    pub fn num_vertices(&self) -> usize {
192        self.graph.num_vertices()
193    }
194
195    /// Get the number of edges in the graph.
196    pub fn num_edges(&self) -> usize {
197        self.graph.num_edges()
198    }
199}
200
201impl<G> Problem for LengthBoundedDisjointPaths<G>
202where
203    G: Graph + VariantParam,
204{
205    const NAME: &'static str = "LengthBoundedDisjointPaths";
206    type Solution = Vec<Vec<bool>>;
207    type Value = Max<i64>;
208
209    crate::problem_parameters![
210        ("max_paths", max_paths),
211        ("num_edges", num_edges),
212        ("num_vertices", num_vertices),
213    ];
214
215    fn variant() -> Vec<(&'static str, &'static str)> {
216        crate::variant_params![G]
217    }
218
219    fn evaluate(
220        &self,
221        solution: &Self::Solution,
222    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
223        if solution.len() != self.max_paths
224            || solution
225                .iter()
226                .any(|path| path.len() != self.graph.num_edges())
227        {
228            return Err(crate::traits::EvaluationError::InvalidConfiguration(
229                "path collection dimensions do not match the instance".into(),
230            ));
231        }
232        validate_path_collection(
233            &self.graph,
234            self.source,
235            self.sink,
236            self.max_length,
237            solution,
238        )
239    }
240}
241
242impl<G> crate::solvers::BruteForceProblem for LengthBoundedDisjointPaths<G>
243where
244    G: Graph + VariantParam,
245{
246    fn dimensions(&self) -> Vec<usize> {
247        vec![2; self.max_paths * self.graph.num_edges()]
248    }
249}
250
251/// Validate a path collection and return the number of valid non-empty paths,
252/// or `None` if any non-empty slot is structurally invalid.
253fn validate_path_collection<G: Graph>(
254    graph: &G,
255    source: usize,
256    sink: usize,
257    max_length: usize,
258    solution: &[Vec<bool>],
259) -> Result<Max<i64>, crate::traits::EvaluationError> {
260    let edges = graph.edges();
261    let mut internal_owner = vec![None; graph.num_vertices()];
262    let mut used_direct_path = false;
263    let mut count = 0_i64;
264    for (path_index, slot) in solution.iter().enumerate() {
265        let edge_count = slot.iter().filter(|&&selected| selected).count();
266        if edge_count == 0 {
267            continue;
268        }
269        if edge_count > max_length
270            || !is_simple_st_path(graph.num_vertices(), &edges, source, sink, slot)
271        {
272            return Ok(Max(None));
273        }
274        if edge_count == 1 {
275            if used_direct_path {
276                return Ok(Max(None));
277            }
278            used_direct_path = true;
279        }
280        for (&selected, &(u, v)) in slot.iter().zip(&edges) {
281            if !selected {
282                continue;
283            }
284            for vertex in [u, v] {
285                if vertex == source || vertex == sink {
286                    continue;
287                }
288                if internal_owner[vertex].is_some_and(|owner| owner != path_index) {
289                    return Ok(Max(None));
290                }
291                internal_owner[vertex] = Some(path_index);
292            }
293        }
294        count = count.checked_add(1).ok_or_else(|| {
295            crate::traits::EvaluationError::IntegerOverflow("counting disjoint paths".to_string())
296        })?;
297    }
298    Ok(Max(Some(count)))
299}
300
301#[cfg(any(test, feature = "example-db"))]
302fn encode_paths(num_edges: usize, max_paths: usize, slots: &[&[usize]]) -> Vec<Vec<bool>> {
303    let mut paths = vec![vec![false; num_edges]; max_paths];
304    for (slot_index, slot_edges) in slots.iter().enumerate() {
305        for &edge in *slot_edges {
306            paths[slot_index][edge] = true;
307        }
308    }
309    paths
310}
311
312#[cfg(feature = "example-db")]
313pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
314    let graph = SimpleGraph::new(5, vec![(0, 1), (1, 4), (0, 2), (2, 4), (0, 3), (3, 4)]);
315    // max_paths = min(deg(0), deg(4)) = min(3, 3) = 3
316    // Three edge-selection rows over six edges.
317    // Optimal: 3 disjoint paths [0,1,4], [0,2,4], [0,3,4]
318    vec![crate::example_db::specs::ModelExampleSpec {
319        id: "length_bounded_disjoint_paths_simplegraph",
320        instance: Box::new(LengthBoundedDisjointPaths::new(graph, 0, 4, 3)),
321        optimal_config: serde_json::json!(encode_paths(6, 3, &[&[0, 1], &[2, 3], &[4, 5]])),
322        optimal_value: serde_json::json!(3),
323    }]
324}
325
326crate::impl_random_generate!(
327    LengthBoundedDisjointPaths<SimpleGraph>,
328    LengthBoundedDisjointPathsRandomSpec,
329    |spec| {
330        let endpoints = crate::random::EndpointRandomSpec {
331            num_vertices: spec.num_vertices,
332            edge_prob: spec.edge_prob,
333            seed: spec.seed,
334            source: spec.source,
335            sink: spec.sink,
336        };
337        let (source, sink) = endpoints.endpoints()?;
338        let max_length = spec.max_length.unwrap_or(spec.num_vertices - 1);
339        if max_length == 0 {
340            return Err("max_length must be positive".to_string().into());
341        }
342        Ok(LengthBoundedDisjointPaths::new(
343            endpoints.graph()?,
344            source,
345            sink,
346            max_length,
347        ))
348    }
349);
350
351crate::declare_variants! {
352    default LengthBoundedDisjointPaths<SimpleGraph> => "2^(max_paths * num_edges)" create LengthBoundedDisjointPathsCreateSpec random,
353}
354
355crate::register_brute_force! {
356    LengthBoundedDisjointPaths<SimpleGraph> decode |problem: &LengthBoundedDisjointPaths<SimpleGraph>, indices: Vec<usize>| {
357        let m = problem.num_edges();
358        (0..problem.max_paths())
359            .map(|slot| crate::config::config_to_bits(&indices[slot * m..(slot + 1) * m]))
360            .collect()
361    },
362}
363
364#[cfg(test)]
365#[path = "../../unit_tests/models/graph/length_bounded_disjoint_paths.rs"]
366mod tests;
problemreductions/models/graph/length_bounded_disjoint_paths.rs

problemreductions/models/graph/
length_bounded_disjoint_paths.rs
