toolbox_rs/
tsplib.rs

1use log::debug;
2
3use crate::{geometry::IPoint2D, io::read_lines};
4use std::str::FromStr;
5
6/// A site in a TSP problem, consisting of an ID and integer coordinates
7#[derive(Debug, Clone)]
8pub struct TspSite {
9    pub id: usize,
10    pub coordinate: IPoint2D,
11}
12
13#[derive(Debug)]
14pub enum TspError {
15    IoError(std::io::Error),
16    ParseError(String),
17}
18
19impl From<std::io::Error> for TspError {
20    fn from(error: std::io::Error) -> Self {
21        TspError::IoError(error)
22    }
23}
24
25/// Parse a TSP file containing site coordinates.
26///
27/// Format specification:
28/// - Header section with metadata (NAME, COMMENT, TYPE, DIMENSION, EDGE_WEIGHT_TYPE)
29/// - NODE_COORD_SECTION marker
30/// - List of nodes with format: <id> <x> <y>
31///
32/// # Arguments
33/// * `filename` - Path to the TSP file
34///
35/// # Returns
36/// A vector of TspSite objects containing the parsed coordinates
37pub fn read_tsp_file(filename: &str) -> Result<Vec<TspSite>, TspError> {
38    let mut sites = Vec::new();
39    let mut in_coord_section = false;
40    let mut dimension: Option<usize> = None;
41
42    for line in read_lines(filename)? {
43        let line = line?;
44        let line = line.trim();
45
46        if line.is_empty() || line == "EOF" {
47            continue;
48        }
49
50        if line == "NODE_COORD_SECTION" {
51            in_coord_section = true;
52            continue;
53        }
54
55        if !in_coord_section {
56            // Parse header section
57            if line.starts_with("DIMENSION") {
58                if let Some(dim_str) = line.split(':').nth(1) {
59                    dimension = Some(dim_str.trim().parse().map_err(|_| {
60                        TspError::ParseError("Invalid DIMENSION value".to_string())
61                    })?);
62                }
63            }
64            continue;
65        }
66
67        // Parse coordinate section
68        let parts: Vec<&str> = line.split_whitespace().collect();
69        if parts.len() != 3 {
70            return Err(TspError::ParseError(format!(
71                "Invalid coordinate line: {line}"
72            )));
73        }
74
75        let id = parts[0]
76            .parse()
77            .map_err(|_| TspError::ParseError(format!("Invalid id: {}", parts[0])))?;
78        let x = f64::from_str(parts[1])
79            .map_err(|_| TspError::ParseError(format!("Invalid x coordinate: {}", parts[1])))?
80            as i32;
81        let y = f64::from_str(parts[2])
82            .map_err(|_| TspError::ParseError(format!("Invalid y coordinate: {}", parts[2])))?
83            as i32;
84
85        debug!("Parsed site: id={}, x={}, y={}", id, x, y);
86
87        sites.push(TspSite {
88            id,
89            coordinate: IPoint2D::new(x, y),
90        });
91    }
92
93    // Verify we read the expected number of sites
94    if let Some(dim) = dimension {
95        if sites.len() != dim {
96            return Err(TspError::ParseError(format!(
97                "Expected {} sites but found {}",
98                dim,
99                sites.len()
100            )));
101        }
102    }
103
104    Ok(sites)
105}
106
107/// Calculate the Euclidean distance between two TSP sites
108pub fn euclidean_distance(a: &TspSite, b: &TspSite) -> i32 {
109    a.coordinate.distance_to(&b.coordinate)
110}
111
112#[cfg(test)]
113mod tests {
114    use super::*;
115    use std::io::{Error, ErrorKind, Write};
116    use tempfile::NamedTempFile;
117
118    fn create_test_tsp_file() -> NamedTempFile {
119        let mut file = NamedTempFile::new().unwrap();
120        write!(
121            file,
122            "NAME : test_problem
123COMMENT : A small 4-city TSP instance for testing
124TYPE : TSP
125DIMENSION : 4
126EDGE_WEIGHT_TYPE : EUC_2D
127NODE_COORD_SECTION
1281 0 0
1292 3 0
1303 0 4
1314 3 4
132EOF"
133        )
134        .unwrap();
135        file
136    }
137
138    #[test]
139    fn test_euclidean_distance() {
140        let site1 = TspSite {
141            id: 1,
142            coordinate: IPoint2D::new(0, 0),
143        };
144        let site2 = TspSite {
145            id: 2,
146            coordinate: IPoint2D::new(3, 4),
147        };
148
149        let distance = euclidean_distance(&site1, &site2);
150        assert_eq!(distance, 5);
151    }
152
153    #[test]
154    fn test_parse_tsp_file() {
155        let file = create_test_tsp_file();
156        let sites = read_tsp_file(file.path().to_str().unwrap()).unwrap();
157
158        assert_eq!(sites.len(), 4, "Should parse exactly 4 sites");
159
160        // Check first site coordinates
161        assert_eq!(sites[0].coordinate.x, 0);
162        assert_eq!(sites[0].coordinate.y, 0);
163        assert_eq!(sites[0].id, 1);
164
165        // Verify distances
166        let d12 = euclidean_distance(&sites[0], &sites[1]); // horizontal distance
167        let d13 = euclidean_distance(&sites[0], &sites[2]); // vertical distance
168        let d14 = euclidean_distance(&sites[0], &sites[3]); // diagonal distance
169
170        assert_eq!(d12, 3, "Distance between sites 1 and 2 should be 3");
171        assert_eq!(d13, 4, "Distance between sites 1 and 3 should be 4");
172        assert_eq!(d14, 5, "Distance between sites 1 and 4 should be 5");
173    }
174
175    #[test]
176    fn test_parse_invalid_dimension() {
177        let mut file = NamedTempFile::new().unwrap();
178        write!(
179            file,
180            "NAME : invalid_problem
181DIMENSION : not_a_number
182NODE_COORD_SECTION
1831 0 0
184EOF"
185        )
186        .unwrap();
187
188        let result = read_tsp_file(file.path().to_str().unwrap());
189        assert!(matches!(result, Err(TspError::ParseError(_))));
190    }
191
192    #[test]
193    fn test_parse_wrong_dimension() {
194        let mut file = NamedTempFile::new().unwrap();
195        write!(
196            file,
197            "NAME : wrong_dimension
198DIMENSION : 2
199NODE_COORD_SECTION
2001 0 0
2012 1 1
2023 2 2
203EOF"
204        )
205        .unwrap();
206
207        let result = read_tsp_file(file.path().to_str().unwrap());
208        assert!(matches!(result, Err(TspError::ParseError(_))));
209    }
210
211    #[test]
212    fn test_parse_invalid_coordinates() {
213        let mut file = NamedTempFile::new().unwrap();
214        write!(
215            file,
216            "NAME : invalid_coords
217DIMENSION : 1
218NODE_COORD_SECTION
2191 not_a_number 0
220EOF"
221        )
222        .unwrap();
223
224        let result = read_tsp_file(file.path().to_str().unwrap());
225        assert!(matches!(result, Err(TspError::ParseError(_))));
226    }
227
228    #[test]
229    fn test_parse_invalid_line_format() {
230        let mut file = NamedTempFile::new().unwrap();
231        write!(
232            file,
233            "NAME : invalid_format
234DIMENSION : 1
235NODE_COORD_SECTION
2361 0    # missing y coordinate
237EOF"
238        )
239        .unwrap();
240
241        let result = read_tsp_file(file.path().to_str().unwrap());
242        assert!(
243            matches!(result, Err(TspError::ParseError(msg)) if msg.contains("Invalid coordinate line"))
244        );
245    }
246
247    #[test]
248    fn test_io_error_conversion() {
249        let io_error = Error::new(ErrorKind::NotFound, "file not found");
250        let tsp_error = TspError::from(io_error);
251
252        assert!(matches!(tsp_error, TspError::IoError(_)));
253        if let TspError::IoError(err) = tsp_error {
254            assert_eq!(err.kind(), ErrorKind::NotFound);
255        } else {
256            panic!("Expected IoError variant");
257        }
258    }
259
260    #[test]
261    fn test_parse_missing_node_coord_section() {
262        let mut file = NamedTempFile::new().unwrap();
263        write!(
264            file,
265            "NAME : missing_section
266DIMENSION : 1
2671 0 0
268EOF"
269        )
270        .unwrap();
271
272        let result = read_tsp_file(file.path().to_str().unwrap());
273        // Since we never saw NODE_COORD_SECTION, no coordinates should be parsed
274        assert!(
275            matches!(result, Err(TspError::ParseError(msg)) if msg.contains("Expected 1 sites but found 0"))
276        );
277    }
278
279    #[test]
280    fn test_parse_empty_file() {
281        let file = NamedTempFile::new().unwrap();
282        let result = read_tsp_file(file.path().to_str().unwrap());
283        assert!(matches!(result, Ok(sites) if sites.is_empty()));
284    }
285
286    #[test]
287    fn test_parse_header_only() {
288        let mut file = NamedTempFile::new().unwrap();
289        write!(
290            file,
291            "NAME : header_only
292DIMENSION : 2
293TYPE : TSP
294EDGE_WEIGHT_TYPE : EUC_2D
295NODE_COORD_SECTION
296EOF"
297        )
298        .unwrap();
299
300        let result = read_tsp_file(file.path().to_str().unwrap());
301        assert!(
302            matches!(result, Err(TspError::ParseError(msg)) if msg.contains("Expected 2 sites but found 0"))
303        );
304    }
305
306    #[test]
307    fn test_parse_non_sequential_ids() {
308        let mut file = NamedTempFile::new().unwrap();
309        write!(
310            file,
311            "NAME : non_sequential
312DIMENSION : 2
313NODE_COORD_SECTION
3141 0 0
3153 1 1
316EOF"
317        )
318        .unwrap();
319
320        let result = read_tsp_file(file.path().to_str().unwrap());
321        match result {
322            Ok(sites) => {
323                assert_eq!(sites.len(), 2, "Should have 2 sites");
324                assert_eq!(sites[1].id, 3, "Second site should have id 3");
325            }
326            Err(e) => panic!("Expected Ok result, got error: {:?}", e),
327        }
328    }
329
330    #[test]
331    fn test_parse_duplicate_ids() {
332        let mut file = NamedTempFile::new().unwrap();
333        write!(
334            file,
335            "NAME : duplicate_ids
336DIMENSION : 2
337NODE_COORD_SECTION
3381 0 0
3391 1 1
340EOF"
341        )
342        .unwrap();
343
344        let result = read_tsp_file(file.path().to_str().unwrap());
345        match result {
346            Ok(sites) => {
347                assert_eq!(sites.len(), 2, "Should have 2 sites");
348                assert_eq!(sites[0].id, 1, "First site should have id 1");
349                assert_eq!(sites[1].id, 1, "Second site should have id 1");
350            }
351            Err(e) => panic!("Expected Ok result, got error: {:?}", e),
352        }
353    }
354}
toolbox_rs/tsplib.rs

toolbox_rs/
tsplib.rs
