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

problemreductions/models/graph/
traveling_salesman.rs
