tsplib/
lib.rs

1//! Parser for [TSPLIB](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) instances.
2//!
3//! # Example
4//!
5//! ```
6//! use tsplib::{EdgeWeightType, NodeCoord, Type};
7//! use std::io::Cursor;
8//!
9//! let data = br#"
10//! NAME : example
11//! COMMENT : this is
12//! COMMENT : a simple example
13//! TYPE : TSP
14//! DIMENSION : 3
15//! EDGE_WEIGHT_TYPE: EUC_2D
16//! NODE_COORD_SECTION
17//!   1 1.2 3.4
18//!   2 5.6 7.8
19//!   3 9.0 1.2
20//! EOF
21//! "#;
22//!
23//! let instance = tsplib::parse(Cursor::new(&data[..])).unwrap();
24//! assert_eq!("example", instance.name);
25//! assert_eq!(Some(Type::Tsp), instance.type_);
26//! assert_eq!(vec!["this is".to_owned(), "a simple example".to_owned()], instance.comment);
27//! assert_eq!(3, instance.dimension);
28//! assert_eq!(0, instance.capacity);
29//! assert_eq!(None, instance.edge_data);
30//! assert_eq!(None, instance.edge_weight);
31//! assert_eq!(Some(EdgeWeightType::Euc2d), instance.edge_weight_type);
32//! assert_eq!(None, instance.fixed_edges);
33//! assert_eq!(Some(NodeCoord::Two(vec![(1, 1.2, 3.4),
34//!                                     (2, 5.6, 7.8),
35//!                                     (3, 9.0, 1.2)])),
36//!            instance.node_coord);
37//! assert_eq!(None, instance.display_data);
38//! assert_eq!(None, instance.display_data_type);
39//! assert_eq!(None, instance.tour);
40//! ```
41
42use std::error::Error;
43use std::fs::File;
44use std::io::{self, BufReader, BufRead};
45use std::path::Path;
46use std::str::FromStr;
47
48macro_rules! err_invalid_data {
49    ($fmt:expr, $($v:ident),*) => (
50        Err(invalid_data(format!($fmt, $($v),*)))
51    )
52}
53
54/// An TSPLIB instance.
55#[derive(Default, Debug)]
56pub struct Instance {
57    pub name: String,
58    pub type_: Option<Type>,
59    pub comment: Vec<String>,
60    pub dimension: usize,
61    pub capacity: usize,
62    pub edge_data: Option<EdgeData>,
63    pub edge_weight: Option<EdgeWeight>,
64    pub edge_weight_type: Option<EdgeWeightType>,
65    pub fixed_edges: Option<Vec<(usize, usize)>>,
66    pub node_coord: Option<NodeCoord>,
67    pub display_data: Option<Vec<(usize, f64, f64)>>,
68    pub display_data_type: Option<DisplayDataType>,
69    pub tour: Option<Vec<usize>>,
70}
71
72#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
73pub enum EdgeData {
74    EdgeList(Vec<(usize, usize)>),
75    AdjList(Vec<Vec<usize>>),
76}
77
78/// Type of the instance.
79#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
80pub enum Type {
81    Tsp,
82    Atsp,
83    Sop,
84    Hcp,
85    Cvrp,
86    Tour,
87}
88
89#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
90pub enum EdgeWeightType {
91    Explicit,
92    Euc2d,
93    Euc3d,
94    Max2d,
95    Max3d,
96    Man2d,
97    Man3d,
98    Ceil2d,
99    Geo,
100    Att,
101    Xray1,
102    Xray2,
103    Special,
104}
105
106#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
107pub enum EdgeWeight {
108    Function,
109    FullMatrix(Vec<usize>),
110    UpperRow(Vec<usize>),
111    LowerRow(Vec<usize>),
112    UpperDiagRow(Vec<usize>),
113    LowerDiagRow(Vec<usize>),
114    UpperCol(Vec<usize>),
115    LowerCol(Vec<usize>),
116    UpperDiagCol(Vec<usize>),
117    LowerDiagCol(Vec<usize>),
118}
119
120#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
121pub enum DisplayDataType {
122    Coord,
123    TwoD,
124}
125
126#[derive(Debug, Clone, PartialEq, PartialOrd)]
127pub enum NodeCoord {
128    Two(Vec<(usize, f32, f32)>),
129    Three(Vec<(usize, f32, f32, f32)>),
130}
131
132/// Read a TSPLIB instance from `path`.
133///
134/// This funtions is implemented as
135///
136/// ```ignore
137/// parse(BufReader::new(File::open(path)?))
138/// ```
139///
140/// # Errors
141///
142/// This function will return an error if an IO error occurs or if the file cannot be parsed.
143pub fn read<P: AsRef<Path>>(path: P) -> io::Result<Instance> {
144    parse(BufReader::new(File::open(path)?))
145}
146
147/// Read a TSPLIB instance from `reader`.
148///
149/// # Errors
150///
151/// This function will return an error if an IO error occurs or if the file cannot be parsed.
152pub fn parse<R: BufRead>(mut reader: R) -> io::Result<Instance> {
153    let mut instance = Instance::default();
154    let mut line = String::new();
155    let mut keyword = String::new();
156    let mut value = String::new();
157
158    while reader.read_line(&mut line)? != 0 && line.trim() != EOF {
159        let r = {
160            let s = line.trim();
161            s.is_empty() || s == "-1"
162        };
163        if r {
164            line.clear();
165            continue;
166        }
167        let (keyword, value) = {
168            let (k, v) = split_colon(&line);
169            keyword.clear();
170            keyword.push_str(k);
171            value.clear();
172            value.push_str(v);
173            (keyword.as_str(), value.as_str())
174        };
175        match keyword {
176            NAME => {
177                instance.name = value.into();
178            }
179            COMMENT => {
180                instance.comment.push(value.into());
181            }
182            TYPE => {
183                instance.set_type(value)?;
184            }
185            DIMENSION => {
186                instance.dimension = parse_value(value)?;
187            }
188            CAPACITY => {
189                instance.capacity = parse_value(value)?;
190            }
191            EDGE_WEIGHT_TYPE => {
192                instance.set_edge_weight_type(value)?;
193            }
194            EDGE_WEIGHT_FORMAT => instance.set_edge_weight_format(value)?,
195            EDGE_DATA_FORMAT => {
196                instance.set_edge_data_format(value)?;
197            }
198            DISPLAY_DATA_TYPE => {
199                instance.set_display_data_type(value)?;
200            }
201            NODE_COORD_TYPE => instance.set_node_coord_type(value)?,
202            EDGE_DATA_SECTION => {
203                parse_edge_data_section(&mut instance, &mut reader)?;
204            }
205            NODE_COORD_SECTION => {
206                parse_node_coord_section(&mut instance, &mut reader)?;
207            }
208            EDGE_WEIGHT_SECTION => {
209                parse_edge_weight_section(&mut instance, &mut reader)?;
210            }
211            DISPLAY_DATA_SECTION => {
212                parse_display_data_section(&mut instance, &mut reader)?;
213            }
214            FIXED_EDGES_SECTION => {
215                parse_fixed_edges_section(&mut instance, &mut reader)?;
216            }
217            TOUR_SECTION => {
218                parse_tour_section(&mut instance, &mut reader)?;
219            }
220            DEPOT_SECTION | DEMAND_SECTION => {
221                return err_invalid_data!("not implemented: {}", keyword)
222            }
223            _ => return err_invalid_data!("invalid keyword: {}", keyword),
224        }
225        line.clear();
226    }
227
228    Ok(instance)
229}
230
231impl Instance {
232    fn num_edges(&self) -> Option<usize> {
233        let m = if let Some(ref edge_data) = self.edge_data {
234            use EdgeData::*;
235            match *edge_data {
236                EdgeList(ref v) => v.len(),
237                AdjList(ref v) => v.iter().map(Vec::len).sum::<usize>() - v.len(),
238            }
239        } else if let Some(ref edge_weight) = self.edge_weight {
240            use EdgeWeight::*;
241            let n = self.dimension;
242            match *edge_weight {
243                FullMatrix(_) => n * n,
244                UpperRow(_) | LowerRow(_) | UpperCol(_) | LowerCol(_) => (n * n - n) / 2,
245                UpperDiagRow(_) | LowerDiagRow(_) | UpperDiagCol(_) | LowerDiagCol(_) => {
246                    (n * n + n) / 2
247                }
248                _ => return None,
249            }
250        } else {
251            return None;
252        };
253        Some(m)
254    }
255
256    fn set_type(&mut self, value: &str) -> io::Result<()> {
257        use Type::*;
258        let type_ = match value {
259            ATSP => Atsp,
260            CVRP => Cvrp,
261            HCP => Hcp,
262            SOP => Sop,
263            TOUR => Tour,
264            TSP | "TSP (M.~Hofmeister)" => Tsp,
265            _ => return err_invalid_data!("invalid TYPE: {}", value),
266        };
267        self.type_ = Some(type_);
268        Ok(())
269    }
270
271    fn set_edge_weight_type(&mut self, value: &str) -> io::Result<()> {
272        use EdgeWeightType::*;
273        let edge_weight_type = match value {
274            EXPLICIT => Explicit,
275            EUC_2D => Euc2d,
276            EUC_3D => Euc3d,
277            MAX_2D => Max2d,
278            MAX_3D => Max3d,
279            MAN_2D => Man2d,
280            MAN_3D => Man3d,
281            CEIL_2D => Ceil2d,
282            GEO => Geo,
283            ATT => Att,
284            XRAY1 => Xray1,
285            XRAY2 => Xray2,
286            SPECIAL => Special,
287            _ => return err_invalid_data!("invalid EDGE_WEIGHT_TYPE: {}", value),
288        };
289        self.edge_weight_type = Some(edge_weight_type);
290        self.node_coord = match value {
291            EXPLICIT => None,
292            EUC_2D | MAX_2D | MAN_2D | CEIL_2D | GEO | ATT => Some(NodeCoord::Two(vec![])),
293            EUC_3D | MAX_3D | MAN_3D => Some(NodeCoord::Three(vec![])),
294            XRAY1 | XRAY2 | SPECIAL => return err_invalid_data!("not implemented: {}", value),
295            _ => return err_invalid_data!("invalid EDGE_WEIGHT_TYPE: {}", value),
296        };
297        Ok(())
298    }
299
300    fn set_edge_weight_format(&mut self, value: &str) -> io::Result<()> {
301        use EdgeWeight::*;
302        let v = vec![];
303        let edge_weight = match value {
304            FUNCTION => Function,
305            FULL_MATRIX => FullMatrix(v),
306            UPPER_ROW => UpperRow(v),
307            LOWER_ROW => LowerRow(v),
308            UPPER_DIAG_ROW => UpperDiagRow(v),
309            LOWER_DIAG_ROW => LowerDiagRow(v),
310            UPPER_COL => UpperCol(v),
311            LOWER_COL => LowerCol(v),
312            UPPER_DIAG_COL => UpperDiagCol(v),
313            LOWER_DIAG_COL => LowerDiagCol(v),
314            _ => return err_invalid_data!("invalid EDGE_WEIGHT_FORMAT: {}", value),
315        };
316        self.edge_weight = Some(edge_weight);
317        Ok(())
318    }
319
320    fn set_edge_data_format(&mut self, value: &str) -> io::Result<()> {
321        use EdgeData::*;
322        let edge_data = match value {
323            EDGE_LIST => EdgeList(vec![]),
324            ADJ_LIST => AdjList(vec![]),
325            _ => return err_invalid_data!("invalid EDGE_DATA_FORMAT: {}", value),
326        };
327        self.edge_data = Some(edge_data);
328        Ok(())
329    }
330
331    fn set_display_data_type(&mut self, value: &str) -> io::Result<()> {
332        use DisplayDataType::*;
333        self.display_data_type = match value {
334            COORD_DISPLAY => Some(Coord),
335            TWOD_DISPLAY => Some(TwoD),
336            NO_DISPLAY => None,
337            _ => return err_invalid_data!("invalid DISPLAY_DATA_TYPE: {}", value),
338        };
339        Ok(())
340    }
341
342    fn set_node_coord_type(&mut self, value: &str) -> io::Result<()> {
343        use NodeCoord::*;
344        self.node_coord = match value {
345            TWOD_COORDS => Some(Two(vec![])),
346            THREED_COORDS => Some(Three(vec![])),
347            NO_COORDS => None,
348            _ => return err_invalid_data!("invalid NODE_COORD_TYPE: {}", value),
349        };
350        Ok(())
351    }
352}
353
354
355fn parse_edge_data_section<R: BufRead>(instance: &mut Instance, reader: &mut R) -> io::Result<()> {
356    use EdgeData::*;
357    match instance.edge_data {
358        Some(EdgeList(ref mut v)) => {
359            parse_vec(reader, v)?;
360        }
361        Some(AdjList(ref mut v)) => {
362            parse_vecs(reader, v)?;
363        }
364        None => return Err(invalid_data("EDGE_DATA_SECTION without EDGE_DATA_FORMAT")),
365    }
366    Ok(())
367}
368
369fn parse_edge_weight_section<R: BufRead>(instance: &mut Instance,
370                                         reader: &mut R)
371                                         -> io::Result<()> {
372    use EdgeWeight::*;
373    let num_edges = instance.num_edges();
374    match instance.edge_weight {
375        Some(Function) => {
376            panic!();
377        }
378        Some(FullMatrix(ref mut v)) |
379        Some(UpperRow(ref mut v)) |
380        Some(LowerRow(ref mut v)) |
381        Some(UpperDiagRow(ref mut v)) |
382        Some(LowerDiagRow(ref mut v)) |
383        Some(UpperCol(ref mut v)) |
384        Some(LowerCol(ref mut v)) |
385        Some(UpperDiagCol(ref mut v)) |
386        Some(LowerDiagCol(ref mut v)) => parse_all(reader, v, num_edges)?,
387        None => return Err(invalid_data("EDGE_WEIGHT_FORMAT without EDGE_WEIGHT_SECTION")),
388    }
389    Ok(())
390}
391
392fn parse_node_coord_section<R: BufRead>(instance: &mut Instance, reader: &mut R) -> io::Result<()> {
393    use NodeCoord::*;
394    match instance.node_coord {
395        Some(Two(ref mut v)) => {
396            parse_vec(reader, v)?;
397        }
398        Some(Three(ref mut v)) => {
399            parse_vec(reader, v)?;
400        }
401        None => return Err(invalid_data("EDGE_DATA_SECTION without EDGE_DATA_FORMAT")),
402    }
403    Ok(())
404}
405
406fn parse_display_data_section<R: BufRead>(instance: &mut Instance,
407                                          reader: &mut R)
408                                          -> io::Result<()> {
409    if let Some(DisplayDataType::TwoD) = instance.display_data_type {
410        let mut v = vec![];
411        parse_vec(reader, &mut v)?;
412        instance.display_data = Some(v);
413    } else {
414        return Err(invalid_data("DISPLAY_DATA_SECTION without EDGE_DATA_TYPE : TWOD_DISPLAY"));
415    }
416    Ok(())
417}
418
419fn parse_fixed_edges_section<R: BufRead>(instance: &mut Instance,
420                                         reader: &mut R)
421                                         -> io::Result<()> {
422    let mut v = vec![];
423    parse_vec(reader, &mut v)?;
424    instance.fixed_edges = Some(v);
425    Ok(())
426}
427
428fn parse_tour_section<R: BufRead>(instance: &mut Instance, reader: &mut R) -> io::Result<()> {
429    let mut v = vec![];
430    let num = if instance.dimension == 0 {
431        None
432    } else {
433        Some(instance.dimension)
434    };
435    parse_all(reader, &mut v, num)?;
436    instance.tour = Some(v);
437    Ok(())
438}
439
440fn parse_value<T>(s: &str) -> io::Result<T>
441    where T: FromStr,
442          T::Err: Into<Box<Error + Send + Sync>>
443{
444    s.parse().map_err(invalid_data)
445}
446
447fn parse_vec<T, R: BufRead>(reader: &mut R, v: &mut Vec<T>) -> io::Result<()>
448    where T: MyFromStr
449{
450    let mut line = String::new();
451    while reader.read_line(&mut line)? != 0 && !is_eof(&line) {
452        match MyFromStr::from_str(&line) {
453            Ok(a) => {
454                v.push(a);
455            }
456            Err(a) => {
457                return Err(invalid_data(a));
458            }
459        }
460        line.clear();
461    }
462    Ok(())
463}
464
465fn parse_all<T, R: BufRead>(reader: &mut R, v: &mut Vec<T>, num: Option<usize>) -> io::Result<()>
466    where T: FromStr + Copy,
467          T::Err: Into<Box<Error + Send + Sync>>
468{
469    let mut line = String::new();
470    while Some(v.len()) != num && reader.read_line(&mut line)? != 0 && !is_eof(&line) {
471        let values: Result<Vec<T>, _> = line.split_whitespace().map(|s| s.parse::<T>()).collect();
472        v.extend(values.map_err(invalid_data)?);
473        line.clear();
474    }
475    if let Some(num) = num {
476        if v.len() < num {
477            return Err(invalid_data("too few values"));
478        } else if v.len() > num {
479            return Err(invalid_data("too many values"));
480        }
481    }
482    Ok(())
483}
484
485fn parse_vecs<T, R: BufRead>(reader: &mut R, v: &mut Vec<Vec<T>>) -> io::Result<()>
486    where T: FromStr + Copy,
487          T::Err: Into<Box<Error + Send + Sync>>
488{
489    let mut line = String::new();
490    while reader.read_line(&mut line)? != 0 && !is_eof(&line) {
491        let values: Result<Vec<T>, _> = line.split_whitespace().map(|s| s.parse::<T>()).collect();
492        v.push(values.map_err(invalid_data)?);
493        line.clear();
494    }
495    Ok(())
496}
497
498fn is_eof(s: &str) -> bool {
499    let s = s.trim();
500    s.is_empty() || s == "-1" || s == EOF
501}
502
503fn split_colon(line: &str) -> (&str, &str) {
504    if let Some(p) = line.find(':') {
505        (line[..p].trim(), line[p + 1..].trim())
506    } else {
507        (line.trim(), &line[..0])
508    }
509}
510
511fn invalid_data<E>(error: E) -> io::Error
512    where E: Into<Box<Error + Send + Sync>>
513{
514    io::Error::new(io::ErrorKind::InvalidData, error)
515}
516
517trait MyFromStr: Sized {
518    fn from_str(s: &str) -> Result<Self, Box<Error + Send + Sync>>;
519}
520
521macro_rules! impl_from_str {
522    ($($T:ident),*) => (
523        impl<$($T),*> MyFromStr for ($($T),*)
524            where $($T: FromStr, $T::Err: Into<Box<Error + Send + Sync>>),*
525        {
526            #[allow(non_snake_case)]
527            fn from_str(s: &str) -> Result<Self, Box<Error + Send + Sync>> {
528                let mut iter = s.split_whitespace();
529                $(
530                    let $T;
531                    if let Some(x) = iter.next() {
532                        $T = x.parse().map_err(invalid_data)?;
533                    } else {
534                        return Err(format!("too few values: {}", s).into());
535                    }
536                )*
537
538                if iter.next().is_some() {
539                    return Err(format!("too many values: {}", s).into());
540                }
541
542                Ok(($($T),*))
543            }
544        }
545    )
546}
547
548impl_from_str!(A, B);
549impl_from_str!(A, B, C);
550impl_from_str!(A, B, C, D);
551
552macro_rules! def_str_consts {
553    ($($name:ident),*) => (
554        $(const $name: &str = stringify!($name);)*
555    )
556}
557
558def_str_consts! {
559    NAME,
560    COMMENT,
561    TYPE,
562        TSP, ATSP, SOP, HCP, CVRP, TOUR,
563    DIMENSION,
564    CAPACITY,
565    EDGE_WEIGHT_TYPE,
566        EXPLICIT, EUC_2D, EUC_3D, MAX_2D, MAX_3D, MAN_2D, MAN_3D, CEIL_2D, GEO, ATT, XRAY1, XRAY2,
567        SPECIAL,
568    EDGE_WEIGHT_FORMAT,
569        FUNCTION, FULL_MATRIX, UPPER_ROW, LOWER_ROW, UPPER_DIAG_ROW, LOWER_DIAG_ROW, UPPER_COL,
570        LOWER_COL, UPPER_DIAG_COL, LOWER_DIAG_COL,
571    EDGE_DATA_FORMAT,
572        EDGE_LIST, ADJ_LIST,
573    NODE_COORD_TYPE,
574        TWOD_COORDS, THREED_COORDS, NO_COORDS,
575    DISPLAY_DATA_TYPE,
576        COORD_DISPLAY, TWOD_DISPLAY, NO_DISPLAY,
577    DEMAND_SECTION,
578    DEPOT_SECTION,
579    DISPLAY_DATA_SECTION,
580    EDGE_DATA_SECTION,
581    EDGE_WEIGHT_SECTION,
582    FIXED_EDGES_SECTION,
583    NODE_COORD_SECTION,
584    TOUR_SECTION,
585    EOF
586}
tsplib/lib.rs

tsplib/
lib.rs
