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

problemreductions/models/graph/
length_bounded_disjoint_paths.rs
