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

problemreductions/models/graph/
longest_path.rs
