aprender_tsp/instance/
mod.rs

1//! TSP instance representation and parsers.
2//!
3//! Supports multiple formats:
4//! - TSPLIB (standard benchmark format)
5//! - CSV (simple coordinate format)
6//! - Distance matrix (JSON)
7
8mod tsplib;
9
10pub use tsplib::TsplibParser;
11
12use crate::error::{TspError, TspResult};
13use std::path::Path;
14
15/// Edge weight computation method
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub enum EdgeWeightType {
18    /// Euclidean 2D distance
19    Euc2d,
20    /// Euclidean 3D distance
21    Euc3d,
22    /// Ceiling of Euclidean 2D
23    Ceil2d,
24    /// Geographical distance
25    Geo,
26    /// Explicit distance matrix
27    Explicit,
28    /// Pseudo-Euclidean (ATSP)
29    Att,
30}
31
32/// A TSP problem instance
33#[derive(Debug, Clone)]
34pub struct TspInstance {
35    /// Instance name
36    pub name: String,
37    /// Number of cities
38    pub dimension: usize,
39    /// Optional comment
40    pub comment: Option<String>,
41    /// Edge weight type
42    pub edge_weight_type: EdgeWeightType,
43    /// City coordinates (if available)
44    pub coords: Option<Vec<(f64, f64)>>,
45    /// Distance matrix (computed or explicit)
46    pub distances: Vec<Vec<f64>>,
47    /// Best known solution length (if available)
48    pub best_known: Option<f64>,
49}
50
51impl TspInstance {
52    /// Create a new TSP instance from coordinates
53    pub fn from_coords(name: &str, coords: Vec<(f64, f64)>) -> TspResult<Self> {
54        if coords.is_empty() {
55            return Err(TspError::InvalidInstance {
56                message: "Instance must have at least one city".into(),
57            });
58        }
59
60        let dimension = coords.len();
61        let distances = Self::compute_distance_matrix(&coords);
62
63        Ok(Self {
64            name: name.to_string(),
65            dimension,
66            comment: None,
67            edge_weight_type: EdgeWeightType::Euc2d,
68            coords: Some(coords),
69            distances,
70            best_known: None,
71        })
72    }
73
74    /// Create a new TSP instance from a distance matrix
75    pub fn from_matrix(name: &str, distances: Vec<Vec<f64>>) -> TspResult<Self> {
76        if distances.is_empty() {
77            return Err(TspError::InvalidInstance {
78                message: "Distance matrix cannot be empty".into(),
79            });
80        }
81
82        let dimension = distances.len();
83
84        // Validate matrix is square
85        for (i, row) in distances.iter().enumerate() {
86            if row.len() != dimension {
87                return Err(TspError::InvalidInstance {
88                    message: format!(
89                        "Distance matrix row {i} has {} elements, expected {dimension}",
90                        row.len()
91                    ),
92                });
93            }
94        }
95
96        Ok(Self {
97            name: name.to_string(),
98            dimension,
99            comment: None,
100            edge_weight_type: EdgeWeightType::Explicit,
101            coords: None,
102            distances,
103            best_known: None,
104        })
105    }
106
107    /// Load instance from file (auto-detects format)
108    pub fn load(path: &Path) -> TspResult<Self> {
109        let extension = path.extension().and_then(|e| e.to_str()).unwrap_or("");
110
111        match extension.to_lowercase().as_str() {
112            "tsp" => TsplibParser::parse_file(path),
113            "csv" => Self::load_csv(path),
114            _ => Err(TspError::ParseError {
115                file: path.to_path_buf(),
116                line: None,
117                cause: format!("Unknown file extension: {extension}"),
118            }),
119        }
120    }
121
122    /// Load from CSV format (id,x,y)
123    fn load_csv(path: &Path) -> TspResult<Self> {
124        let content = std::fs::read_to_string(path)?;
125        let mut coords = Vec::new();
126
127        for (line_num, line) in content.lines().enumerate() {
128            let line = line.trim();
129            if line.is_empty() || line.starts_with('#') {
130                continue;
131            }
132
133            let parts: Vec<&str> = line.split(',').collect();
134            if parts.len() < 3 {
135                return Err(TspError::ParseError {
136                    file: path.to_path_buf(),
137                    line: Some(line_num + 1),
138                    cause: "Expected at least 3 columns: id,x,y".into(),
139                });
140            }
141
142            let x: f64 = parts[1].trim().parse().map_err(|_| TspError::ParseError {
143                file: path.to_path_buf(),
144                line: Some(line_num + 1),
145                cause: format!("Invalid x coordinate: {}", parts[1]),
146            })?;
147
148            let y: f64 = parts[2].trim().parse().map_err(|_| TspError::ParseError {
149                file: path.to_path_buf(),
150                line: Some(line_num + 1),
151                cause: format!("Invalid y coordinate: {}", parts[2]),
152            })?;
153
154            coords.push((x, y));
155        }
156
157        let name = path
158            .file_stem()
159            .and_then(|s| s.to_str())
160            .unwrap_or("unnamed")
161            .to_string();
162
163        Self::from_coords(&name, coords)
164    }
165
166    /// Compute Euclidean distance matrix from coordinates
167    fn compute_distance_matrix(coords: &[(f64, f64)]) -> Vec<Vec<f64>> {
168        let n = coords.len();
169        let mut matrix = vec![vec![0.0; n]; n];
170
171        for i in 0..n {
172            for j in i + 1..n {
173                let dx = coords[i].0 - coords[j].0;
174                let dy = coords[i].1 - coords[j].1;
175                let dist = (dx * dx + dy * dy).sqrt();
176                matrix[i][j] = dist;
177                matrix[j][i] = dist;
178            }
179        }
180
181        matrix
182    }
183
184    /// Get number of cities
185    #[inline]
186    pub fn num_cities(&self) -> usize {
187        self.dimension
188    }
189
190    /// Get distance between two cities
191    #[inline]
192    pub fn distance(&self, i: usize, j: usize) -> f64 {
193        self.distances[i][j]
194    }
195
196    /// Calculate tour length
197    pub fn tour_length(&self, tour: &[usize]) -> f64 {
198        if tour.is_empty() {
199            return 0.0;
200        }
201
202        let mut length = 0.0;
203        for window in tour.windows(2) {
204            length += self.distance(window[0], window[1]);
205        }
206        // Return to start
207        length += self.distance(tour[tour.len() - 1], tour[0]);
208        length
209    }
210
211    /// Validate a tour
212    pub fn validate_tour(&self, tour: &[usize]) -> TspResult<()> {
213        if tour.len() != self.dimension {
214            return Err(TspError::InvalidInstance {
215                message: format!(
216                    "Tour has {} cities, expected {}",
217                    tour.len(),
218                    self.dimension
219                ),
220            });
221        }
222
223        let mut visited = vec![false; self.dimension];
224        for &city in tour {
225            if city >= self.dimension {
226                return Err(TspError::InvalidInstance {
227                    message: format!("City {city} out of range [0, {})", self.dimension),
228                });
229            }
230            if visited[city] {
231                return Err(TspError::InvalidInstance {
232                    message: format!("City {city} visited multiple times"),
233                });
234            }
235            visited[city] = true;
236        }
237
238        Ok(())
239    }
240
241    /// Get nearest neighbor rank of city j from city i
242    pub fn nearest_neighbor_rank(&self, i: usize, j: usize) -> usize {
243        let mut neighbors: Vec<(usize, f64)> = (0..self.dimension)
244            .filter(|&k| k != i)
245            .map(|k| (k, self.distance(i, k)))
246            .collect();
247        neighbors.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
248
249        neighbors
250            .iter()
251            .position(|&(k, _)| k == j)
252            .map_or(self.dimension, |p| p + 1)
253    }
254}
255
256#[cfg(test)]
257mod tests {
258    use super::*;
259
260    #[test]
261    fn test_from_coords_creates_instance() {
262        let coords = vec![(0.0, 0.0), (3.0, 0.0), (3.0, 4.0)];
263        let instance = TspInstance::from_coords("test", coords).expect("should create instance");
264
265        assert_eq!(instance.name, "test");
266        assert_eq!(instance.dimension, 3);
267        assert_eq!(instance.num_cities(), 3);
268    }
269
270    #[test]
271    fn test_from_coords_computes_distances() {
272        // 3-4-5 right triangle
273        let coords = vec![(0.0, 0.0), (3.0, 0.0), (3.0, 4.0)];
274        let instance = TspInstance::from_coords("test", coords).expect("should create instance");
275
276        assert!((instance.distance(0, 1) - 3.0).abs() < 1e-10);
277        assert!((instance.distance(1, 2) - 4.0).abs() < 1e-10);
278        assert!((instance.distance(0, 2) - 5.0).abs() < 1e-10);
279    }
280
281    #[test]
282    fn test_from_coords_empty_fails() {
283        let result = TspInstance::from_coords("test", vec![]);
284        assert!(result.is_err());
285    }
286
287    #[test]
288    fn test_from_matrix_creates_instance() {
289        let matrix = vec![
290            vec![0.0, 10.0, 15.0],
291            vec![10.0, 0.0, 20.0],
292            vec![15.0, 20.0, 0.0],
293        ];
294        let instance = TspInstance::from_matrix("test", matrix).expect("should create instance");
295
296        assert_eq!(instance.dimension, 3);
297        assert!((instance.distance(0, 1) - 10.0).abs() < 1e-10);
298    }
299
300    #[test]
301    fn test_from_matrix_non_square_fails() {
302        let matrix = vec![vec![0.0, 10.0], vec![10.0, 0.0, 5.0]];
303        let result = TspInstance::from_matrix("test", matrix);
304        assert!(result.is_err());
305    }
306
307    #[test]
308    fn test_tour_length_calculation() {
309        let coords = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)];
310        let instance = TspInstance::from_coords("square", coords).expect("should create");
311
312        // Tour around the square: 0->1->2->3->0 = 1+1+1+1 = 4
313        let tour = vec![0, 1, 2, 3];
314        let length = instance.tour_length(&tour);
315        assert!((length - 4.0).abs() < 1e-10);
316    }
317
318    #[test]
319    fn test_validate_tour_correct() {
320        let coords = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)];
321        let instance = TspInstance::from_coords("test", coords).expect("should create");
322
323        let tour = vec![0, 1, 2];
324        assert!(instance.validate_tour(&tour).is_ok());
325    }
326
327    #[test]
328    fn test_validate_tour_wrong_length() {
329        let coords = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)];
330        let instance = TspInstance::from_coords("test", coords).expect("should create");
331
332        let tour = vec![0, 1];
333        assert!(instance.validate_tour(&tour).is_err());
334    }
335
336    #[test]
337    fn test_validate_tour_duplicate_city() {
338        let coords = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)];
339        let instance = TspInstance::from_coords("test", coords).expect("should create");
340
341        let tour = vec![0, 1, 1];
342        assert!(instance.validate_tour(&tour).is_err());
343    }
344
345    #[test]
346    fn test_validate_tour_out_of_range() {
347        let coords = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)];
348        let instance = TspInstance::from_coords("test", coords).expect("should create");
349
350        let tour = vec![0, 1, 5];
351        assert!(instance.validate_tour(&tour).is_err());
352    }
353
354    #[test]
355    fn test_nearest_neighbor_rank() {
356        // Cities: A(0,0), B(1,0), C(3,0)
357        // From A: B is nearest (rank 1), C is 2nd (rank 2)
358        let coords = vec![(0.0, 0.0), (1.0, 0.0), (3.0, 0.0)];
359        let instance = TspInstance::from_coords("test", coords).expect("should create");
360
361        assert_eq!(instance.nearest_neighbor_rank(0, 1), 1); // B is nearest to A
362        assert_eq!(instance.nearest_neighbor_rank(0, 2), 2); // C is 2nd nearest to A
363    }
364
365    #[test]
366    fn test_empty_tour_length() {
367        let coords = vec![(0.0, 0.0), (1.0, 0.0)];
368        let instance = TspInstance::from_coords("test", coords).expect("should create");
369
370        assert!((instance.tour_length(&[]) - 0.0).abs() < 1e-10);
371    }
372}
aprender_tsp/instance/mod.rs

aprender_tsp/instance/
mod.rs
