problemreductions/models/graph/
traveling_salesman.rs

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

problemreductions/models/graph/
traveling_salesman.rs
