source: trunk/sources/HeuristicLab.Problems.TSP/3.3/TSPLIBParser.cs @ 3151

Last change on this file since 3151 was 3151, checked in by swagner, 12 years ago

Implemented import of optimal TSP solutions (#924).

File size: 7.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Globalization;
24using System.IO;
25
26namespace HeuristicLab.Problems.TSP {
27  /// <summary>
28  /// Parses a *.tsp file in TSPLIB format and extracts its information about a TSP.
29  /// </summary>
30  public class TSPLIBParser {
31    private const int EOF = 0;
32    private const int NAME = 1;
33    private const int TYPE = 2;
34    private const int COMMENT = 3;
35    private const int DIM = 4;
36    private const int WEIGHTTYPE = 5;
37    private const int NODETYPE = 6;
38    private const int NODESECTION = 7;
39
40    private StreamReader source;
41
42    private string name;
43    /// <summary>
44    /// Gets the name of the parsed TSP.
45    /// </summary>
46    public string Name {
47      get { return name; }
48    }
49    private string comment;
50    /// <summary>
51    /// Gets the comment of the parsed TSP.
52    /// </summary>
53    public string Comment {
54      get { return comment; }
55    }
56    private double[,] vertices;
57    /// <summary>
58    /// Gets the vertices of the parsed TSP.
59    /// </summary>
60    public double[,] Vertices {
61      get { return vertices; }
62    }
63    private int weightType;
64    /// <summary>
65    /// Gets the weight type of the parsed TSP.
66    /// </summary>
67    public int WeightType {
68      get { return weightType; }
69    }
70
71    /// <summary>
72    /// Initializes a new instance of <see cref="TSPLIBParser"/> with the given <paramref name="path"/>.
73    /// </summary>
74    /// <exception cref="ArgumentException">Thrown if the input file is not a TSPLIB TSP file (*.tsp)
75    /// </exception>
76    /// <param name="path">The path where the TSP is stored.</param>
77    public TSPLIBParser(String path) {
78      if (!path.EndsWith(".tsp"))
79        throw new ArgumentException("Input file has to be a TSPLIB TSP file (*.tsp).");
80
81      source = new StreamReader(path);
82      name = path;
83      comment = string.Empty;
84      vertices = null;
85      weightType = -1;
86    }
87
88    /// <summary>
89    /// Reads the TSPLIB TSP file and parses the elements.
90    /// </summary>
91    /// <exception cref="InvalidDataException">Thrown if the file has an invalid format or contains invalid data.</exception>
92    public void Parse() {
93      int section = -1;
94      string str = null;
95      bool typeIsChecked = false;
96      bool weightTypeIsChecked = false;
97
98      do {
99        str = source.ReadLine();
100        section = GetSection(str);
101
102        if (section != -1) {
103          switch (section) {
104            case NAME:
105              ReadName(str);
106              break;
107            case TYPE:
108              CheckType(str);
109              typeIsChecked = true;
110              break;
111            case COMMENT:
112              ReadComment(str);
113              break;
114            case DIM:
115              InitVerticesArray(str);
116              break;
117            case WEIGHTTYPE:
118              ReadWeightType(str);
119              weightTypeIsChecked = true;
120              break;
121            case NODETYPE:
122              CheckNodeType(str);
123              break;
124            case NODESECTION:
125              ReadVertices();
126              break;
127          }
128        }
129      } while (!((section == EOF) || (str == null)));
130
131      if (!(typeIsChecked && weightTypeIsChecked))
132        throw new InvalidDataException("Input file does not contain type or edge weight type information.");
133    }
134
135    private int GetSection(string str) {
136      if (str == null)
137        return EOF;
138
139      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
140      if (tokens.Length == 0)
141        return -1;
142
143      string token = tokens[0].Trim();
144      if (token.Equals("eof", StringComparison.OrdinalIgnoreCase))
145        return EOF;
146      if (token.Equals("name", StringComparison.OrdinalIgnoreCase))
147        return NAME;
148      if (token.Equals("type", StringComparison.OrdinalIgnoreCase))
149        return TYPE;
150      if (token.Equals("comment", StringComparison.OrdinalIgnoreCase))
151        return COMMENT;
152      if (token.Equals("dimension", StringComparison.OrdinalIgnoreCase))
153        return DIM;
154      if (token.Equals("edge_weight_type", StringComparison.OrdinalIgnoreCase))
155        return WEIGHTTYPE;
156      if (token.Equals("node_coord_type", StringComparison.OrdinalIgnoreCase))
157        return NODETYPE;
158      if (token.Equals("node_coord_section", StringComparison.OrdinalIgnoreCase))
159        return NODESECTION;
160
161      return -1;
162    }
163
164    private void ReadName(string str) {
165      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
166      name = tokens[tokens.Length - 1].Trim();
167    }
168
169    private void CheckType(string str) {
170      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
171
172      string type = tokens[tokens.Length - 1].Trim();
173      if (!type.Equals("tsp", StringComparison.OrdinalIgnoreCase))
174        throw new InvalidDataException("Input file type is not \"TSP\"");
175    }
176
177    private void ReadComment(string str) {
178      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
179      comment = tokens[tokens.Length - 1].Trim();
180    }
181
182    private void InitVerticesArray(string str) {
183      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
184      string dimension = tokens[tokens.Length - 1].Trim();
185
186      int dim = Int32.Parse(dimension);
187      vertices = new double[dim, 2];
188    }
189
190    private void ReadWeightType(string str) {
191      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
192      string type = tokens[tokens.Length - 1].Trim();
193
194      if (type.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
195        weightType = 0;
196      else if (type.Equals("geo", StringComparison.OrdinalIgnoreCase))
197        weightType = 1;
198      else
199        throw new InvalidDataException("Input file contains an unsupported edge weight type (only \"EUC_2D\" and \"GEO\" are supported).");
200    }
201
202    private void CheckNodeType(string str) {
203      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
204      string type = tokens[tokens.Length - 1].Trim();
205
206      if (!type.Equals("twod_coords", StringComparison.OrdinalIgnoreCase))
207        throw new InvalidDataException("Input file contains an unsupported node coordinates type (only \"TWOD_COORDS\" is supported).");
208    }
209
210    private void ReadVertices() {
211      if (vertices == null)
212        throw new InvalidDataException("Input file does not contain dimension information.");
213
214      for (int i = 0; i < (vertices.Length / 2); i++) {
215        string str = source.ReadLine();
216        string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
217
218        if (tokens.Length != 3)
219          throw new InvalidDataException("Input file contains invalid node coordinates.");
220
221        CultureInfo culture = new CultureInfo("en-US");
222        vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
223        vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
224      }
225    }
226  }
227}
Note: See TracBrowser for help on using the repository browser.