Free cookie consent management tool by TermsFeed Policy Generator

source: branches/histogram/HeuristicLab.Problems.TravelingSalesman/3.3/TSPLIBParser.cs @ 6055

Last change on this file since 6055 was 5445, checked in by swagner, 13 years ago

Updated year of copyrights (#1406)

File size: 8.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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.TravelingSalesman {
27  /// <summary>
28  /// Parses a *.tsp file in TSPLIB format and extracts its information about a TSP.
29  /// </summary>
30  public class TSPLIBParser {
31    #region Inner Enum TSPLIBEdgeWeightType
32    public enum TSPLIBEdgeWeightType {
33      UNDEFINED,
34      EUC_2D,
35      GEO
36    }
37    #endregion
38
39    private const int EOF = 0;
40    private const int NAME = 1;
41    private const int TYPE = 2;
42    private const int COMMENT = 3;
43    private const int DIM = 4;
44    private const int WEIGHTTYPE = 5;
45    private const int NODETYPE = 6;
46    private const int NODESECTION = 7;
47
48    private StreamReader source;
49
50    private string name;
51    /// <summary>
52    /// Gets the name of the parsed TSP.
53    /// </summary>
54    public string Name {
55      get { return name; }
56    }
57    private string comment;
58    /// <summary>
59    /// Gets the comment of the parsed TSP.
60    /// </summary>
61    public string Comment {
62      get { return comment; }
63    }
64    private double[,] vertices;
65    /// <summary>
66    /// Gets the vertices of the parsed TSP.
67    /// </summary>
68    public double[,] Vertices {
69      get { return vertices; }
70    }
71    private TSPLIBEdgeWeightType weightType;
72    /// <summary>
73    /// Gets the weight type of the parsed TSP.
74    /// </summary>
75    public TSPLIBEdgeWeightType WeightType {
76      get { return weightType; }
77    }
78
79    /// <summary>
80    /// Initializes a new instance of <see cref="TSPLIBParser"/> with the given <paramref name="path"/>.
81    /// </summary>
82    /// <exception cref="ArgumentException">Thrown if the input file is not a TSPLIB TSP file (*.tsp)
83    /// </exception>
84    /// <param name="path">The path where the TSP is stored.</param>
85    public TSPLIBParser(String path) {
86      if (!path.EndsWith(".tsp"))
87        throw new ArgumentException("Input file has to be a TSPLIB TSP file (*.tsp).");
88
89      source = new StreamReader(path);
90      name = path;
91      comment = string.Empty;
92      vertices = null;
93      weightType = TSPLIBEdgeWeightType.UNDEFINED;
94    }
95
96    /// <summary>
97    /// Reads the TSPLIB TSP file and parses the elements.
98    /// </summary>
99    /// <exception cref="InvalidDataException">Thrown if the file has an invalid format or contains invalid data.</exception>
100    public void Parse() {
101      int section = -1;
102      string str = null;
103      bool typeIsChecked = false;
104      bool weightTypeIsChecked = false;
105
106      do {
107        str = source.ReadLine();
108        section = GetSection(str);
109
110        if (section != -1) {
111          switch (section) {
112            case NAME:
113              ReadName(str);
114              break;
115            case TYPE:
116              CheckType(str);
117              typeIsChecked = true;
118              break;
119            case COMMENT:
120              ReadComment(str);
121              break;
122            case DIM:
123              InitVerticesArray(str);
124              break;
125            case WEIGHTTYPE:
126              ReadWeightType(str);
127              weightTypeIsChecked = true;
128              break;
129            case NODETYPE:
130              CheckNodeType(str);
131              break;
132            case NODESECTION:
133              ReadVertices();
134              break;
135          }
136        }
137      } while (!((section == EOF) || (str == null)));
138
139      if (!(typeIsChecked && weightTypeIsChecked))
140        throw new InvalidDataException("Input file does not contain type or edge weight type information.");
141    }
142
143    private int GetSection(string str) {
144      if (str == null)
145        return EOF;
146
147      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
148      if (tokens.Length == 0)
149        return -1;
150
151      string token = tokens[0].Trim();
152      if (token.Equals("eof", StringComparison.OrdinalIgnoreCase))
153        return EOF;
154      if (token.Equals("name", StringComparison.OrdinalIgnoreCase))
155        return NAME;
156      if (token.Equals("type", StringComparison.OrdinalIgnoreCase))
157        return TYPE;
158      if (token.Equals("comment", StringComparison.OrdinalIgnoreCase))
159        return COMMENT;
160      if (token.Equals("dimension", StringComparison.OrdinalIgnoreCase))
161        return DIM;
162      if (token.Equals("edge_weight_type", StringComparison.OrdinalIgnoreCase))
163        return WEIGHTTYPE;
164      if (token.Equals("node_coord_type", StringComparison.OrdinalIgnoreCase))
165        return NODETYPE;
166      if (token.Equals("node_coord_section", StringComparison.OrdinalIgnoreCase))
167        return NODESECTION;
168
169      return -1;
170    }
171
172    private void ReadName(string str) {
173      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
174      name = tokens[tokens.Length - 1].Trim();
175    }
176
177    private void CheckType(string str) {
178      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
179
180      string type = tokens[tokens.Length - 1].Trim();
181      if (!type.Equals("tsp", StringComparison.OrdinalIgnoreCase))
182        throw new InvalidDataException("Input file type is not \"TSP\"");
183    }
184
185    private void ReadComment(string str) {
186      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
187      comment = tokens[tokens.Length - 1].Trim();
188    }
189
190    private void InitVerticesArray(string str) {
191      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
192      string dimension = tokens[tokens.Length - 1].Trim();
193
194      int dim = Int32.Parse(dimension);
195      vertices = new double[dim, 2];
196    }
197
198    private void ReadWeightType(string str) {
199      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
200      string type = tokens[tokens.Length - 1].Trim();
201
202      if (type.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
203        weightType = TSPLIBEdgeWeightType.EUC_2D;
204      else if (type.Equals("geo", StringComparison.OrdinalIgnoreCase))
205        weightType = TSPLIBEdgeWeightType.GEO;
206      else
207        throw new InvalidDataException("Input file contains an unsupported edge weight type (only \"EUC_2D\" and \"GEO\" are supported).");
208    }
209
210    private void CheckNodeType(string str) {
211      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
212      string type = tokens[tokens.Length - 1].Trim();
213
214      if (!type.Equals("twod_coords", StringComparison.OrdinalIgnoreCase))
215        throw new InvalidDataException("Input file contains an unsupported node coordinates type (only \"TWOD_COORDS\" is supported).");
216    }
217
218    private void ReadVertices() {
219      if (vertices == null)
220        throw new InvalidDataException("Input file does not contain dimension information.");
221
222      for (int i = 0; i < (vertices.Length / 2); i++) {
223        string str = source.ReadLine();
224        string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
225
226        if (tokens.Length != 3)
227          throw new InvalidDataException("Input file contains invalid node coordinates.");
228
229        CultureInfo culture = new CultureInfo("en-US");
230        vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
231        vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
232      }
233    }
234  }
235}
Note: See TracBrowser for help on using the repository browser.