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::{FieldInfo, 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", "i32", &["i32"]),
22        ],
23        module_path: module_path!(),
24        description: "Find a simple circuit in a graph that maximizes 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 -> Z_(> 0)" },
28        ],
29    }
30}
31
32/// The Longest Circuit problem.
33///
34/// Given an undirected graph `G = (V, E)` with positive edge lengths `l(e)`,
35/// find a simple circuit in `G` that maximizes the total edge-length sum.
36///
37/// # Representation
38///
39/// Each edge is assigned a binary variable:
40/// - `0`: edge is not in the circuit
41/// - `1`: edge is in the circuit
42///
43/// A valid configuration must select edges that form exactly one connected
44/// simple circuit using only edges from `graph`.
45#[derive(Debug, Clone, Serialize, Deserialize)]
46pub struct LongestCircuit<G, W: WeightElement> {
47    graph: G,
48    edge_lengths: Vec<W>,
49}
50
51impl<G: Graph, W: WeightElement> LongestCircuit<G, W> {
52    /// Create a new LongestCircuit instance.
53    ///
54    /// # Panics
55    ///
56    /// Panics if the number of edge lengths does not match the graph's edge
57    /// count, or if any edge length is non-positive.
58    pub fn new(graph: G, edge_lengths: Vec<W>) -> Self {
59        assert_eq!(
60            edge_lengths.len(),
61            graph.num_edges(),
62            "edge_lengths length must match num_edges"
63        );
64        let zero = W::Sum::zero();
65        assert!(
66            edge_lengths
67                .iter()
68                .all(|length| length.to_sum() > zero.clone()),
69            "All edge lengths must be positive (> 0)"
70        );
71        Self {
72            graph,
73            edge_lengths,
74        }
75    }
76
77    /// Get a reference to the underlying graph.
78    pub fn graph(&self) -> &G {
79        &self.graph
80    }
81
82    /// Get the edge lengths.
83    pub fn edge_lengths(&self) -> &[W] {
84        &self.edge_lengths
85    }
86
87    /// Replace the edge lengths.
88    pub fn set_lengths(&mut self, edge_lengths: Vec<W>) {
89        assert_eq!(
90            edge_lengths.len(),
91            self.graph.num_edges(),
92            "edge_lengths length must match num_edges"
93        );
94        let zero = W::Sum::zero();
95        assert!(
96            edge_lengths
97                .iter()
98                .all(|length| length.to_sum() > zero.clone()),
99            "All edge lengths must be positive (> 0)"
100        );
101        self.edge_lengths = edge_lengths;
102    }
103
104    /// Replace the edge lengths via the generic weight-management naming.
105    pub fn set_weights(&mut self, weights: Vec<W>) {
106        self.set_lengths(weights);
107    }
108
109    /// Get the edge lengths as a cloned vector.
110    pub fn weights(&self) -> Vec<W> {
111        self.edge_lengths.clone()
112    }
113
114    /// Get the number of vertices in the graph.
115    pub fn num_vertices(&self) -> usize {
116        self.graph.num_vertices()
117    }
118
119    /// Get the number of edges in the graph.
120    pub fn num_edges(&self) -> usize {
121        self.graph.num_edges()
122    }
123
124    /// Check if the problem uses a non-unit weight type.
125    pub fn is_weighted(&self) -> bool {
126        !W::IS_UNIT
127    }
128
129    /// Check whether a configuration is a valid simple circuit.
130    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
131        is_simple_circuit(&self.graph, config)
132    }
133}
134
135impl<G, W> Problem for LongestCircuit<G, W>
136where
137    G: Graph + crate::variant::VariantParam,
138    W: WeightElement + crate::variant::VariantParam,
139{
140    const NAME: &'static str = "LongestCircuit";
141    type Value = Max<W::Sum>;
142
143    fn variant() -> Vec<(&'static str, &'static str)> {
144        crate::variant_params![G, W]
145    }
146
147    fn dims(&self) -> Vec<usize> {
148        vec![2; self.graph.num_edges()]
149    }
150
151    fn evaluate(&self, config: &[usize]) -> Max<W::Sum> {
152        if !is_simple_circuit(&self.graph, config) {
153            return Max(None);
154        }
155        let mut total = W::Sum::zero();
156        for (idx, &selected) in config.iter().enumerate() {
157            if selected == 1 {
158                total += self.edge_lengths[idx].to_sum();
159            }
160        }
161        Max(Some(total))
162    }
163}
164
165/// Check whether a binary edge-selection encodes exactly one simple circuit.
166pub(crate) fn is_simple_circuit<G: Graph>(graph: &G, config: &[usize]) -> bool {
167    if config.len() != graph.num_edges() || config.iter().any(|&value| value > 1) {
168        return false;
169    }
170
171    let edges = graph.edges();
172    let n = graph.num_vertices();
173    let mut degree = vec![0usize; n];
174    let mut adjacency = vec![Vec::new(); n];
175    let mut selected_count = 0usize;
176    let mut start = None;
177
178    for (idx, &selected) in config.iter().enumerate() {
179        if selected == 0 {
180            continue;
181        }
182        let (u, v) = edges[idx];
183        degree[u] += 1;
184        degree[v] += 1;
185        adjacency[u].push(v);
186        adjacency[v].push(u);
187        selected_count += 1;
188        if start.is_none() {
189            start = Some(u);
190        }
191    }
192
193    if selected_count < 3 {
194        return false;
195    }
196
197    let selected_vertices: Vec<usize> = degree
198        .iter()
199        .enumerate()
200        .filter_map(|(vertex, &deg)| (deg > 0).then_some(vertex))
201        .collect();
202
203    if selected_vertices.is_empty() || selected_vertices.iter().any(|&vertex| degree[vertex] != 2) {
204        return false;
205    }
206
207    let start = match start {
208        Some(vertex) => vertex,
209        None => return false,
210    };
211
212    let mut visited = vec![false; n];
213    let mut queue = VecDeque::new();
214    visited[start] = true;
215    queue.push_back(start);
216    let mut visited_selected_vertices = 0usize;
217
218    while let Some(vertex) = queue.pop_front() {
219        visited_selected_vertices += 1;
220        for &neighbor in &adjacency[vertex] {
221            if !visited[neighbor] {
222                visited[neighbor] = true;
223                queue.push_back(neighbor);
224            }
225        }
226    }
227
228    visited_selected_vertices == selected_vertices.len()
229}
230
231#[cfg(feature = "example-db")]
232pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
233    vec![crate::example_db::specs::ModelExampleSpec {
234        id: "longest_circuit_simplegraph_i32",
235        instance: Box::new(LongestCircuit::new(
236            SimpleGraph::new(
237                6,
238                vec![
239                    (0, 1),
240                    (1, 2),
241                    (2, 3),
242                    (3, 4),
243                    (4, 5),
244                    (5, 0),
245                    (0, 3),
246                    (1, 4),
247                    (2, 5),
248                    (3, 5),
249                ],
250            ),
251            vec![3, 2, 4, 1, 5, 2, 3, 2, 1, 2],
252        )),
253        optimal_config: vec![1, 0, 1, 0, 1, 0, 1, 1, 1, 0],
254        optimal_value: serde_json::json!(18),
255    }]
256}
257
258crate::declare_variants! {
259    default LongestCircuit<SimpleGraph, i32> => "2^num_vertices * num_vertices^2",
260}
261
262#[cfg(test)]
263#[path = "../../unit_tests/models/graph/longest_circuit.rs"]
264mod tests;
problemreductions/models/graph/longest_circuit.rs

problemreductions/models/graph/
longest_circuit.rs
