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

problemreductions/models/graph/
traveling_salesman.rs
