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

aprender_tsp/instance/
mod.rs
