problemreductions/models/graph/
longest_path.rs

1//! Longest Path problem implementation.
2//!
3//! The Longest Path problem asks for a simple path between two distinguished
4//! vertices that maximizes the total edge length.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Max, One, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12use std::collections::VecDeque;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "LongestPath",
17        display_name: "Longest Path",
18        aliases: &[],
19        dimensions: &[
20            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
21            VariantDimension::new("weight", "i32", &["i32", "One"]),
22        ],
23        module_path: module_path!(),
24        description: "Find a simple s-t path of maximum total edge length",
25        fields: &[
26            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
27            FieldInfo { name: "edge_lengths", type_name: "Vec<W>", description: "Positive edge lengths l: E -> ZZ_(> 0)" },
28            FieldInfo { name: "source_vertex", type_name: "usize", description: "Source vertex s" },
29            FieldInfo { name: "target_vertex", type_name: "usize", description: "Target vertex t" },
30        ],
31    }
32}
33
34/// The Longest Path problem.
35///
36/// Given a graph `G = (V, E)` with positive edge lengths `l(e)` and
37/// distinguished vertices `s` and `t`, find a simple path from `s` to `t`
38/// maximizing the total length of its selected edges.
39///
40/// # Representation
41///
42/// Each edge is assigned a binary variable:
43/// - `0`: the edge is not selected
44/// - `1`: the edge is selected
45///
46/// A valid configuration must select exactly the edges of one simple
47/// undirected path from `source_vertex` to `target_vertex`.
48#[derive(Debug, Clone, Serialize, Deserialize)]
49pub struct LongestPath<G, W: WeightElement> {
50    graph: G,
51    edge_lengths: Vec<W>,
52    source_vertex: usize,
53    target_vertex: usize,
54}
55
56impl<G: Graph, W: WeightElement> LongestPath<G, W> {
57    fn assert_positive_edge_lengths(edge_lengths: &[W]) {
58        let zero = W::Sum::zero();
59        assert!(
60            edge_lengths
61                .iter()
62                .all(|length| length.to_sum() > zero.clone()),
63            "All edge lengths must be positive (> 0)"
64        );
65    }
66
67    /// Create a new LongestPath instance.
68    pub fn new(graph: G, edge_lengths: Vec<W>, source_vertex: usize, target_vertex: usize) -> Self {
69        assert_eq!(
70            edge_lengths.len(),
71            graph.num_edges(),
72            "edge_lengths length must match num_edges"
73        );
74        Self::assert_positive_edge_lengths(&edge_lengths);
75        assert!(
76            source_vertex < graph.num_vertices(),
77            "source_vertex {} out of bounds (graph has {} vertices)",
78            source_vertex,
79            graph.num_vertices()
80        );
81        assert!(
82            target_vertex < graph.num_vertices(),
83            "target_vertex {} out of bounds (graph has {} vertices)",
84            target_vertex,
85            graph.num_vertices()
86        );
87        Self {
88            graph,
89            edge_lengths,
90            source_vertex,
91            target_vertex,
92        }
93    }
94
95    /// Get a reference to the underlying graph.
96    pub fn graph(&self) -> &G {
97        &self.graph
98    }
99
100    /// Get the edge lengths.
101    pub fn edge_lengths(&self) -> &[W] {
102        &self.edge_lengths
103    }
104
105    /// Replace the edge lengths with a new vector.
106    pub fn set_lengths(&mut self, edge_lengths: Vec<W>) {
107        assert_eq!(
108            edge_lengths.len(),
109            self.graph.num_edges(),
110            "edge_lengths length must match num_edges"
111        );
112        Self::assert_positive_edge_lengths(&edge_lengths);
113        self.edge_lengths = edge_lengths;
114    }
115
116    /// Get the source vertex.
117    pub fn source_vertex(&self) -> usize {
118        self.source_vertex
119    }
120
121    /// Get the target vertex.
122    pub fn target_vertex(&self) -> usize {
123        self.target_vertex
124    }
125
126    /// Check whether this problem uses non-unit edge lengths.
127    pub fn is_weighted(&self) -> bool {
128        !W::IS_UNIT
129    }
130
131    /// Get the number of vertices in the graph.
132    pub fn num_vertices(&self) -> usize {
133        self.graph.num_vertices()
134    }
135
136    /// Get the number of edges in the graph.
137    pub fn num_edges(&self) -> usize {
138        self.graph.num_edges()
139    }
140
141    /// Check if a configuration encodes a valid simple source-target path.
142    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
143        is_simple_st_path(&self.graph, self.source_vertex, self.target_vertex, config)
144    }
145}
146
147impl<G, W> Problem for LongestPath<G, W>
148where
149    G: Graph + crate::variant::VariantParam,
150    W: WeightElement + crate::variant::VariantParam,
151{
152    const NAME: &'static str = "LongestPath";
153    type Value = Max<W::Sum>;
154
155    fn variant() -> Vec<(&'static str, &'static str)> {
156        crate::variant_params![G, W]
157    }
158
159    fn dims(&self) -> Vec<usize> {
160        vec![2; self.graph.num_edges()]
161    }
162
163    fn evaluate(&self, config: &[usize]) -> Max<W::Sum> {
164        if !self.is_valid_solution(config) {
165            return Max(None);
166        }
167
168        let mut total = W::Sum::zero();
169        for (idx, &selected) in config.iter().enumerate() {
170            if selected == 1 {
171                total += self.edge_lengths[idx].to_sum();
172            }
173        }
174        Max(Some(total))
175    }
176}
177
178fn is_simple_st_path<G: Graph>(
179    graph: &G,
180    source_vertex: usize,
181    target_vertex: usize,
182    config: &[usize],
183) -> bool {
184    if config.len() != graph.num_edges() || config.iter().any(|&value| value > 1) {
185        return false;
186    }
187
188    if source_vertex == target_vertex {
189        return config.iter().all(|&value| value == 0);
190    }
191
192    let edges = graph.edges();
193    let mut degree = vec![0usize; graph.num_vertices()];
194    let mut adjacency = vec![Vec::new(); graph.num_vertices()];
195    let mut selected_edge_count = 0usize;
196
197    for (idx, &selected) in config.iter().enumerate() {
198        if selected == 0 {
199            continue;
200        }
201        let (u, v) = edges[idx];
202        degree[u] += 1;
203        degree[v] += 1;
204        if degree[u] > 2 || degree[v] > 2 {
205            return false;
206        }
207        adjacency[u].push(v);
208        adjacency[v].push(u);
209        selected_edge_count += 1;
210    }
211
212    if selected_edge_count == 0 {
213        return false;
214    }
215    if degree[source_vertex] != 1 || degree[target_vertex] != 1 {
216        return false;
217    }
218
219    let mut selected_vertex_count = 0usize;
220    for (vertex, &vertex_degree) in degree.iter().enumerate() {
221        if vertex_degree == 0 {
222            continue;
223        }
224        selected_vertex_count += 1;
225        if vertex != source_vertex && vertex != target_vertex && vertex_degree != 2 {
226            return false;
227        }
228    }
229
230    if selected_edge_count != selected_vertex_count.saturating_sub(1) {
231        return false;
232    }
233
234    let mut visited = vec![false; graph.num_vertices()];
235    let mut queue = VecDeque::new();
236    visited[source_vertex] = true;
237    queue.push_back(source_vertex);
238
239    while let Some(vertex) = queue.pop_front() {
240        for &neighbor in &adjacency[vertex] {
241            if !visited[neighbor] {
242                visited[neighbor] = true;
243                queue.push_back(neighbor);
244            }
245        }
246    }
247
248    visited[target_vertex]
249        && degree
250            .iter()
251            .enumerate()
252            .all(|(vertex, &vertex_degree)| vertex_degree == 0 || visited[vertex])
253}
254
255crate::declare_variants! {
256    default LongestPath<SimpleGraph, i32> => "num_vertices * 2^num_vertices",
257    LongestPath<SimpleGraph, One> => "num_vertices * 2^num_vertices",
258}
259
260#[cfg(feature = "example-db")]
261pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
262    vec![crate::example_db::specs::ModelExampleSpec {
263        id: "longest_path_simplegraph_i32",
264        instance: Box::new(LongestPath::new(
265            SimpleGraph::new(
266                7,
267                vec![
268                    (0, 1),
269                    (0, 2),
270                    (1, 3),
271                    (2, 3),
272                    (2, 4),
273                    (3, 5),
274                    (4, 5),
275                    (4, 6),
276                    (5, 6),
277                    (1, 6),
278                ],
279            ),
280            vec![3, 2, 4, 1, 5, 2, 3, 2, 4, 1],
281            0,
282            6,
283        )),
284        optimal_config: vec![1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
285        optimal_value: serde_json::json!(20),
286    }]
287}
288
289#[cfg(test)]
290#[path = "../../unit_tests/models/graph/longest_path.rs"]
291mod tests;
problemreductions/models/graph/longest_path.rs

problemreductions/models/graph/
longest_path.rs
