problemreductions/models/graph/
longest_circuit.rs

1//! Longest Circuit problem implementation.
2//!
3//! The Longest Circuit problem asks for a simple circuit in a graph
4//! that maximizes the total edge length.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Max, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12use std::collections::VecDeque;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "LongestCircuit",
17        display_name: "Longest Circuit",
18        aliases: &[],
19        dimensions: &[
20            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
21            VariantDimension::new("weight", "i64", &["i64"]),
22        ],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "Find a simple circuit in a graph that maximizes total edge length",
26        fields: LongestCircuitCreateSpec::FIELDS,
27    }
28}
29
30/// The Longest Circuit problem.
31///
32/// Given an undirected graph `G = (V, E)` with positive edge lengths `l(e)`,
33/// find a simple circuit in `G` that maximizes the total edge-length sum.
34///
35/// # Representation
36///
37/// Each edge is assigned a binary variable:
38/// - `0`: edge is not in the circuit
39/// - `1`: edge is in the circuit
40///
41/// A valid configuration must select edges that form exactly one connected
42/// simple circuit using only edges from `graph`.
43#[derive(Debug, Clone, Serialize, Deserialize)]
44pub struct LongestCircuit<G, W: WeightElement> {
45    graph: G,
46    edge_lengths: Vec<W>,
47}
48
49#[derive(Debug, Deserialize, crate::CreateSpec)]
50struct LongestCircuitCreateSpec {
51    #[create(codec = "edge-list")]
52    graph: Vec<(usize, usize)>,
53    num_vertices: Option<usize>,
54    #[create(codec = "comma-separated")]
55    edge_weights: Option<Vec<i64>>,
56}
57
58impl TryFrom<LongestCircuitCreateSpec> for LongestCircuit<SimpleGraph, i64> {
59    type Error = crate::registry::ConstructionError;
60
61    fn try_from(spec: LongestCircuitCreateSpec) -> Result<Self, Self::Error> {
62        let graph = simple_graph_from_create(spec.graph, spec.num_vertices)?;
63        let edge_lengths = spec
64            .edge_weights
65            .unwrap_or_else(|| vec![1; graph.num_edges()]);
66        if edge_lengths.len() != graph.num_edges() {
67            return Err(format!(
68                "edge_weights has length {}, expected {}",
69                edge_lengths.len(),
70                graph.num_edges()
71            )
72            .into());
73        }
74        if edge_lengths.iter().any(|&length| length <= 0) {
75            return Err("edge_weights must be positive".to_string().into());
76        }
77        Ok(Self::new(graph, edge_lengths))
78    }
79}
80
81fn simple_graph_from_create(
82    edges: Vec<(usize, usize)>,
83    num_vertices: Option<usize>,
84) -> Result<SimpleGraph, crate::registry::ConstructionError> {
85    if edges.is_empty() && num_vertices.is_none() {
86        return Err("num_vertices is required for an empty graph"
87            .to_string()
88            .into());
89    }
90    for (index, &(u, v)) in edges.iter().enumerate() {
91        if u == v {
92            return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
93        }
94    }
95    let inferred = edges
96        .iter()
97        .flat_map(|&(u, v)| [u, v])
98        .max()
99        .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
100        .transpose()?
101        .unwrap_or(0);
102    let num_vertices = num_vertices.unwrap_or(inferred);
103    if num_vertices < inferred {
104        return Err(format!(
105            "num_vertices {num_vertices} is too small for graph endpoints; need at least {inferred}"
106        )
107        .into());
108    }
109    Ok(SimpleGraph::new(num_vertices, edges))
110}
111
112impl<G: Graph, W: WeightElement> LongestCircuit<G, W> {
113    /// Create a new LongestCircuit instance.
114    ///
115    /// # Panics
116    ///
117    /// Panics if the number of edge lengths does not match the graph's edge
118    /// count, or if any edge length is non-positive.
119    pub fn new(graph: G, edge_lengths: Vec<W>) -> Self {
120        assert_eq!(
121            edge_lengths.len(),
122            graph.num_edges(),
123            "edge_lengths length must match num_edges"
124        );
125        let zero = W::Sum::zero();
126        assert!(
127            edge_lengths
128                .iter()
129                .all(|length| length.to_sum() > zero.clone()),
130            "All edge lengths must be positive (> 0)"
131        );
132        Self {
133            graph,
134            edge_lengths,
135        }
136    }
137
138    /// Get a reference to the underlying graph.
139    pub fn graph(&self) -> &G {
140        &self.graph
141    }
142
143    /// Get the edge lengths.
144    pub fn edge_lengths(&self) -> &[W] {
145        &self.edge_lengths
146    }
147
148    /// Replace the edge lengths.
149    pub fn set_lengths(&mut self, edge_lengths: Vec<W>) {
150        assert_eq!(
151            edge_lengths.len(),
152            self.graph.num_edges(),
153            "edge_lengths length must match num_edges"
154        );
155        let zero = W::Sum::zero();
156        assert!(
157            edge_lengths
158                .iter()
159                .all(|length| length.to_sum() > zero.clone()),
160            "All edge lengths must be positive (> 0)"
161        );
162        self.edge_lengths = edge_lengths;
163    }
164
165    /// Replace the edge lengths via the generic weight-management naming.
166    pub fn set_weights(&mut self, weights: Vec<W>) {
167        self.set_lengths(weights);
168    }
169
170    /// Get the edge lengths as a cloned vector.
171    pub fn weights(&self) -> Vec<W> {
172        self.edge_lengths.clone()
173    }
174
175    /// Get the number of vertices in the graph.
176    pub fn num_vertices(&self) -> usize {
177        self.graph.num_vertices()
178    }
179
180    /// Get the number of edges in the graph.
181    pub fn num_edges(&self) -> usize {
182        self.graph.num_edges()
183    }
184
185    /// Check if the problem uses a non-unit weight type.
186    pub fn is_weighted(&self) -> bool {
187        !W::IS_UNIT
188    }
189
190    /// Check whether a configuration is a valid simple circuit.
191    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
192        is_simple_circuit(&self.graph, config)
193    }
194}
195
196impl<G, W> Problem for LongestCircuit<G, W>
197where
198    G: Graph + crate::variant::VariantParam,
199    W: WeightElement + crate::variant::VariantParam,
200{
201    const NAME: &'static str = "LongestCircuit";
202    type Solution = Vec<bool>;
203    type Value = Max<W::Sum>;
204
205    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
206
207    fn variant() -> Vec<(&'static str, &'static str)> {
208        crate::variant_params![G, W]
209    }
210
211    fn evaluate(
212        &self,
213        config: &Self::Solution,
214    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
215        if config.len() != self.graph.num_edges() {
216            return Err(crate::traits::EvaluationError::InvalidConfiguration(
217                "edge-selection length does not match the graph".into(),
218            ));
219        }
220        Ok({
221            if !is_simple_circuit(&self.graph, config) {
222                return Ok(Max(None));
223            }
224            let mut total = W::Sum::zero();
225            for (idx, &selected) in config.iter().enumerate() {
226                if selected {
227                    total = W::checked_add_to_sum(
228                        total,
229                        self.edge_lengths[idx].to_sum(),
230                        "summing circuit edge lengths",
231                    )?;
232                }
233            }
234            Max(Some(total))
235        })
236    }
237}
238
239impl<G, W> crate::solvers::BruteForceProblem for LongestCircuit<G, W>
240where
241    G: Graph + crate::variant::VariantParam,
242    W: WeightElement + crate::variant::VariantParam,
243{
244    fn dimensions(&self) -> Vec<usize> {
245        vec![2; self.graph.num_edges()]
246    }
247}
248
249/// Check whether a binary edge-selection encodes exactly one simple circuit.
250pub(crate) fn is_simple_circuit<G: Graph>(graph: &G, config: &[bool]) -> bool {
251    if config.len() != graph.num_edges() {
252        return false;
253    }
254
255    let edges = graph.edges();
256    let n = graph.num_vertices();
257    let mut degree = vec![0usize; n];
258    let mut adjacency = vec![Vec::new(); n];
259    let mut selected_count = 0usize;
260    let mut start = None;
261
262    for (idx, &selected) in config.iter().enumerate() {
263        if !selected {
264            continue;
265        }
266        let (u, v) = edges[idx];
267        degree[u] += 1;
268        degree[v] += 1;
269        adjacency[u].push(v);
270        adjacency[v].push(u);
271        selected_count += 1;
272        if start.is_none() {
273            start = Some(u);
274        }
275    }
276
277    if selected_count < 3 {
278        return false;
279    }
280
281    let selected_vertices: Vec<usize> = degree
282        .iter()
283        .enumerate()
284        .filter_map(|(vertex, &deg)| (deg > 0).then_some(vertex))
285        .collect();
286
287    if selected_vertices.is_empty() || selected_vertices.iter().any(|&vertex| degree[vertex] != 2) {
288        return false;
289    }
290
291    let start = match start {
292        Some(vertex) => vertex,
293        None => return false,
294    };
295
296    let mut visited = vec![false; n];
297    let mut queue = VecDeque::new();
298    visited[start] = true;
299    queue.push_back(start);
300    let mut visited_selected_vertices = 0usize;
301
302    while let Some(vertex) = queue.pop_front() {
303        visited_selected_vertices += 1;
304        for &neighbor in &adjacency[vertex] {
305            if !visited[neighbor] {
306                visited[neighbor] = true;
307                queue.push_back(neighbor);
308            }
309        }
310    }
311
312    visited_selected_vertices == selected_vertices.len()
313}
314
315#[cfg(feature = "example-db")]
316pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
317    vec![crate::example_db::specs::ModelExampleSpec {
318        id: "longest_circuit_simplegraph",
319        instance: Box::new(LongestCircuit::new(
320            SimpleGraph::new(
321                6,
322                vec![
323                    (0, 1),
324                    (1, 2),
325                    (2, 3),
326                    (3, 4),
327                    (4, 5),
328                    (5, 0),
329                    (0, 3),
330                    (1, 4),
331                    (2, 5),
332                    (3, 5),
333                ],
334            ),
335            vec![3, 2, 4, 1, 5, 2, 3, 2, 1, 2],
336        )),
337        optimal_config: serde_json::json!(vec![
338            true, false, true, false, true, false, true, true, true, false
339        ]),
340        optimal_value: serde_json::json!(18),
341    }]
342}
343
344crate::impl_random_generate!(LongestCircuit<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
345    let graph = spec.graph()?;
346    let lengths = vec![1; graph.num_edges()];
347    Ok(LongestCircuit::new(graph, lengths))
348});
349
350crate::declare_variants! {
351    default LongestCircuit<SimpleGraph, i64> => "2^num_vertices * num_vertices^2" create LongestCircuitCreateSpec random,
352}
353
354crate::register_brute_force! {
355    LongestCircuit<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
356}
357
358#[cfg(test)]
359#[path = "../../unit_tests/models/graph/longest_circuit.rs"]
360mod tests;
problemreductions/models/graph/longest_circuit.rs

problemreductions/models/graph/
longest_circuit.rs
