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::{FieldInfo, 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", "i32", &["i32"]),
21        ],
22        module_path: module_path!(),
23        description: "Find minimum weight Hamiltonian cycle in a graph (Traveling Salesman Problem)",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "edge_weights", type_name: "Vec<W>", description: "Edge weights w: E -> R" },
27        ],
28    }
29}
30
31/// The Traveling Salesman problem.
32///
33/// Given a weighted graph G = (V, E) with edge weights w_e,
34/// find a cycle that visits every vertex exactly once and
35/// minimizes the total edge weight.
36///
37/// # Representation
38///
39/// Each edge is assigned a binary variable:
40/// - 0: edge is not in the cycle
41/// - 1: edge is in the cycle
42///
43/// A valid Hamiltonian cycle requires:
44/// - Exactly 2 selected edges incident to each vertex (degree constraint)
45/// - Selected edges form a single connected cycle (no subtours)
46/// - Exactly |V| edges are selected
47///
48/// # Type Parameters
49///
50/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`)
51/// * `W` - The weight type for edges (e.g., `i32`, `f64`)
52#[derive(Debug, Clone, Serialize, Deserialize)]
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
60impl<G: Graph, W: Clone + Default> TravelingSalesman<G, W> {
61    /// Create a TravelingSalesman problem from a graph with given edge weights.
62    pub fn new(graph: G, edge_weights: Vec<W>) -> Self {
63        assert_eq!(
64            edge_weights.len(),
65            graph.num_edges(),
66            "edge_weights length must match num_edges"
67        );
68        Self {
69            graph,
70            edge_weights,
71        }
72    }
73
74    /// Create a TravelingSalesman problem with unit weights.
75    pub fn unit_weights(graph: G) -> Self
76    where
77        W: From<i32>,
78    {
79        let edge_weights = vec![W::from(1); graph.num_edges()];
80        Self {
81            graph,
82            edge_weights,
83        }
84    }
85
86    /// Get a reference to the underlying graph.
87    pub fn graph(&self) -> &G {
88        &self.graph
89    }
90
91    /// Get all edges with their weights.
92    pub fn edges(&self) -> Vec<(usize, usize, W)> {
93        self.graph
94            .edges()
95            .into_iter()
96            .zip(self.edge_weights.iter().cloned())
97            .map(|((u, v), w)| (u, v, w))
98            .collect()
99    }
100
101    /// Set new weights for the problem.
102    pub fn set_weights(&mut self, weights: Vec<W>) {
103        assert_eq!(weights.len(), self.graph.num_edges());
104        self.edge_weights = weights;
105    }
106
107    /// Get the weights for the problem.
108    pub fn weights(&self) -> Vec<W> {
109        self.edge_weights.clone()
110    }
111
112    /// Check if the problem uses a non-unit weight type.
113    pub fn is_weighted(&self) -> bool
114    where
115        W: WeightElement,
116    {
117        !W::IS_UNIT
118    }
119
120    /// Check if a configuration is a valid Hamiltonian cycle.
121    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
122        self.is_valid_hamiltonian_cycle(config)
123    }
124
125    /// Check if a configuration forms a valid Hamiltonian cycle.
126    fn is_valid_hamiltonian_cycle(&self, config: &[usize]) -> bool {
127        if config.len() != self.graph.num_edges() {
128            return false;
129        }
130        let selected: Vec<bool> = config.iter().map(|&s| s == 1).collect();
131        is_hamiltonian_cycle(&self.graph, &selected)
132    }
133}
134
135impl<G: Graph, W: WeightElement> TravelingSalesman<G, W> {
136    /// Get the number of vertices in the underlying graph.
137    pub fn num_vertices(&self) -> usize {
138        self.graph().num_vertices()
139    }
140
141    /// Get the number of edges in the underlying graph.
142    pub fn num_edges(&self) -> usize {
143        self.graph().num_edges()
144    }
145}
146
147impl<G, W> Problem for TravelingSalesman<G, W>
148where
149    G: Graph + crate::variant::VariantParam,
150    W: WeightElement + crate::variant::VariantParam,
151{
152    const NAME: &'static str = "TravelingSalesman";
153    type Value = Min<W::Sum>;
154
155    fn variant() -> Vec<(&'static str, &'static str)> {
156        crate::variant_params![G, W]
157    }
158
159    fn dims(&self) -> Vec<usize> {
160        vec![2; self.graph.num_edges()]
161    }
162
163    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
164        if !self.is_valid_hamiltonian_cycle(config) {
165            return Min(None);
166        }
167        let mut total = W::Sum::zero();
168        for (idx, &selected) in config.iter().enumerate() {
169            if selected == 1 {
170                if let Some(w) = self.edge_weights.get(idx) {
171                    total += w.to_sum();
172                }
173            }
174        }
175        Min(Some(total))
176    }
177}
178
179/// Check if a selection of edges forms a valid Hamiltonian cycle.
180///
181/// # Panics
182/// Panics if `selected.len() != graph.num_edges()`.
183pub(crate) fn is_hamiltonian_cycle<G: Graph>(graph: &G, selected: &[bool]) -> bool {
184    assert_eq!(
185        selected.len(),
186        graph.num_edges(),
187        "selected length must match num_edges"
188    );
189
190    let n = graph.num_vertices();
191    let edges = graph.edges();
192    let mut degree = vec![0usize; n];
193    let mut selected_count = 0;
194    let mut first_vertex = None;
195
196    for (idx, &sel) in selected.iter().enumerate() {
197        if sel {
198            let (u, v) = edges[idx];
199            degree[u] += 1;
200            degree[v] += 1;
201            selected_count += 1;
202            if first_vertex.is_none() {
203                first_vertex = Some(u);
204            }
205        }
206    }
207
208    if selected_count != n {
209        return false;
210    }
211
212    if degree.iter().any(|&d| d != 2) {
213        return false;
214    }
215
216    let first = match first_vertex {
217        Some(v) => v,
218        None => return false,
219    };
220
221    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
222    for (idx, &sel) in selected.iter().enumerate() {
223        if sel {
224            let (u, v) = edges[idx];
225            adj[u].push(v);
226            adj[v].push(u);
227        }
228    }
229
230    let mut visited = vec![false; n];
231    let mut queue = std::collections::VecDeque::new();
232    visited[first] = true;
233    queue.push_back(first);
234    let mut visit_count = 1;
235
236    while let Some(node) = queue.pop_front() {
237        for &neighbor in &adj[node] {
238            if !visited[neighbor] {
239                visited[neighbor] = true;
240                visit_count += 1;
241                queue.push_back(neighbor);
242            }
243        }
244    }
245
246    visit_count == n
247}
248
249#[cfg(feature = "example-db")]
250pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
251    vec![crate::example_db::specs::ModelExampleSpec {
252        id: "traveling_salesman_simplegraph_i32",
253        instance: Box::new(TravelingSalesman::new(
254            SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
255            vec![1, 3, 2, 2, 3, 1],
256        )),
257        optimal_config: vec![1, 0, 1, 1, 0, 1],
258        optimal_value: serde_json::json!(6),
259    }]
260}
261
262crate::declare_variants! {
263    default TravelingSalesman<SimpleGraph, i32> => "2^num_vertices",
264}
265
266#[cfg(test)]
267#[path = "../../unit_tests/models/graph/traveling_salesman.rs"]
268mod tests;
problemreductions/models/graph/traveling_salesman.rs

problemreductions/models/graph/
traveling_salesman.rs
