source: branches/FitnessLandscapeAnalysis/VRPProblemAnalyzer/TSPLIBParser.cs @ 7231

Last change on this file since 7231 was 7231, checked in by svonolfe, 11 years ago

Added VRP problem analyzer (#1696)

File size: 13.5 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 VRPProblemAnalyzer {
27  /// <summary>
28  /// Parses a *.vrp file in TSPLIB format and extracts its information about a VRP.
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 WEIGHTFORMAT = 11;
46    private const int NODETYPE = 6;
47    private const int NODESECTION = 7;
48    private const int CAPACITY = 8;
49    private const int DISTANCE = 12;
50    private const int VEHICLES = 13;
51    private const int DEPOTSECTION = 9;
52    private const int DEMANDSECTION = 10;
53
54    private StreamReader source;
55    private bool alternateFormat;
56    CultureInfo culture = new CultureInfo("en-US");
57
58    private string name;
59    /// <summary>
60    /// Gets the name of the parsed VRP.
61    /// </summary>
62    public string Name {
63      get { return name; }
64    }
65    private string comment;
66    /// <summary>
67    /// Gets the comment of the parsed VRP.
68    /// </summary>
69    public string Comment {
70      get { return comment; }
71    }
72    private double[,] vertices;
73    /// <summary>
74    /// Gets the vertices of the parsed VRP.
75    /// </summary>
76    public double[,] Vertices {
77      get { return vertices; }
78    }
79    private TSPLIBEdgeWeightType weightType;
80    /// <summary>
81    /// Gets the weight format of the parsed VRP.
82    /// </summary>
83    public TSPLIBEdgeWeightType WeightType {
84      get { return weightType; }
85    }
86
87    private double capacity;
88    public double Capacity {
89      get {
90        return capacity;
91      }
92    }
93
94    private double distance;
95    public double Distance {
96      get {
97        return distance;
98      }
99    }
100
101    private int vehicles;
102    public int Vehicles {
103      get {
104        return vehicles;
105      }
106    }
107
108    private int depot;
109    public int Depot {
110      get {
111        return depot;
112      }
113    }
114
115    private double[] demands;
116    public double[] Demands {
117      get {
118        return demands;
119      }
120    }
121
122    /// <summary>
123    /// Initializes a new instance of <see cref="TSPLIBParser"/> with the given <paramref name="path"/>.
124    /// </summary>
125    /// <exception cref="ArgumentException">Thrown if the input file is not a TSPLIB TSP file (*.vrp)
126    /// </exception>
127    /// <param name="path">The path where the VRP is stored.</param>
128    public TSPLIBParser(String path) {
129      if (!path.EndsWith(".vrp"))
130        throw new ArgumentException("Input file has to be a TSPLIB CVRP file (*.vrp, *.txt).");
131
132      source = null;
133      name = path;
134      comment = string.Empty;
135      vertices = null;
136      weightType = TSPLIBEdgeWeightType.UNDEFINED;
137      capacity = -1;
138      distance = -1;
139      vehicles = -1;
140      depot = -1;
141      demands = null;
142      alternateFormat = false;
143    }
144
145    /// <summary>
146    /// Reads the TSPLIB VRP file and parses the elements.
147    /// </summary>
148    /// <exception cref="InvalidDataException">Thrown if the file has an invalid format or contains invalid data.</exception>
149    public void Parse() {
150      using (source = new StreamReader(name)) {
151        int section = -1;
152        string str = null;
153        bool typeIsChecked = false;
154        bool weightTypeIsChecked = false;
155        bool weightFormatIsChecked = false;
156
157        do {
158          str = source.ReadLine();
159          section = GetSection(str);
160
161          if (section != -1) {
162            switch (section) {
163              case NAME:
164                ReadName(str);
165                break;
166              case TYPE:
167                CheckType(str);
168                typeIsChecked = true;
169                break;
170              case COMMENT:
171                ReadComment(str);
172                break;
173              case DIM:
174                InitArrays(str);
175                break;
176              case WEIGHTTYPE:
177                ReadWeightType(str);
178                weightTypeIsChecked = true;
179                break;
180              case WEIGHTFORMAT:
181                ReadWeightFormat(str);
182                weightFormatIsChecked = true;
183                break;
184              case NODETYPE:
185                CheckNodeType(str);
186                break;
187              case NODESECTION:
188                ReadVertices();
189                break;
190              case CAPACITY:
191                ReadCapacity(str);
192                break;
193              case DISTANCE:
194                ReadDistance(str);
195                break;
196              case VEHICLES:
197                ReadVehicles(str);
198                break;
199              case DEPOTSECTION:
200                ReadDepot();
201                break;
202              case DEMANDSECTION:
203                ReadDemands();
204                break;
205            }
206          }
207        } while (!((section == EOF) || (str == null)));
208
209        if (!typeIsChecked || !weightTypeIsChecked ||
210          (alternateFormat && !weightFormatIsChecked) ||
211          weightType == TSPLIBEdgeWeightType.UNDEFINED)
212          throw new InvalidDataException("Input file does not contain format or edge weight format information.");
213      }
214      source = null;
215    }
216
217    private int GetSection(string str) {
218      if (str == null)
219        return EOF;
220
221      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
222      if (tokens.Length == 0)
223        return -1;
224
225      string token = tokens[0].Trim();
226      if (token.Equals("eof", StringComparison.OrdinalIgnoreCase))
227        return EOF;
228      if (token.Equals("name", StringComparison.OrdinalIgnoreCase))
229        return NAME;
230      if (token.Equals("type", StringComparison.OrdinalIgnoreCase))
231        return TYPE;
232      if (token.Equals("comment", StringComparison.OrdinalIgnoreCase))
233        return COMMENT;
234      if (token.Equals("dimension", StringComparison.OrdinalIgnoreCase))
235        return DIM;
236      if (token.Equals("edge_weight_type", StringComparison.OrdinalIgnoreCase))
237        return WEIGHTTYPE;
238      if (token.Equals("edge_weight_format", StringComparison.OrdinalIgnoreCase))
239        return WEIGHTFORMAT;
240      if (token.Equals("node_coord_type", StringComparison.OrdinalIgnoreCase))
241        return NODETYPE;
242      if (token.Equals("node_coord_section", StringComparison.OrdinalIgnoreCase))
243        return NODESECTION;
244      if (token.Equals("capacity", StringComparison.OrdinalIgnoreCase))
245        return CAPACITY;
246      if (token.Equals("distance", StringComparison.OrdinalIgnoreCase))
247        return DISTANCE;
248      if (token.Equals("vehicles", StringComparison.OrdinalIgnoreCase))
249        return VEHICLES;
250      if (token.Equals("depot_section", StringComparison.OrdinalIgnoreCase))
251        return DEPOTSECTION;
252      if (token.Equals("demand_section", StringComparison.OrdinalIgnoreCase))
253        return DEMANDSECTION;
254
255      return -1;
256    }
257
258    private void ReadName(string str) {
259      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
260      name = tokens[tokens.Length - 1].Trim();
261    }
262
263    private void CheckType(string str) {
264      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
265
266      string type = tokens[tokens.Length - 1].Trim();
267      if (!type.Equals("cvrp", StringComparison.OrdinalIgnoreCase))
268        throw new InvalidDataException("Input file format is not \"CVRP\"");
269    }
270
271    private void ReadComment(string str) {
272      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
273      comment = tokens[tokens.Length - 1].Trim();
274    }
275
276    private void InitArrays(string str) {
277      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
278      string dimension = tokens[tokens.Length - 1].Trim();
279
280      int dim = Int32.Parse(dimension);
281      vertices = new double[dim, 2];
282      demands = new double[dim];
283    }
284
285    private void ReadWeightType(string str) {
286      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
287      string type = tokens[tokens.Length - 1].Trim();
288
289      if (type.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
290        weightType = TSPLIBEdgeWeightType.EUC_2D;
291      else if (type.Equals("geo", StringComparison.OrdinalIgnoreCase))
292        weightType = TSPLIBEdgeWeightType.GEO;
293      else if (type.Equals("function", StringComparison.OrdinalIgnoreCase)) {
294        weightType = TSPLIBEdgeWeightType.UNDEFINED;
295        alternateFormat = true;
296      } else
297        throw new InvalidDataException("Input file contains an unsupported edge weight format (only \"EUC_2D\" and \"GEO\" are supported).");
298    }
299
300    private void ReadWeightFormat(string str) {
301      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
302      string format = tokens[tokens.Length - 1].Trim();
303
304      if (alternateFormat && format.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
305        weightType = TSPLIBEdgeWeightType.EUC_2D;
306      else if (format.Equals("geo", StringComparison.OrdinalIgnoreCase))
307        weightType = TSPLIBEdgeWeightType.GEO;
308      else
309        throw new InvalidDataException("Input file contains an unsupported edge weight format.");
310    }
311
312    private void CheckNodeType(string str) {
313      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
314      string type = tokens[tokens.Length - 1].Trim();
315
316      if (!type.Equals("twod_coords", StringComparison.OrdinalIgnoreCase))
317        throw new InvalidDataException("Input file contains an unsupported node coordinates format (only \"TWOD_COORDS\" is supported).");
318    }
319
320    private void ReadVertices() {
321      if (vertices == null)
322        throw new InvalidDataException("Input file does not contain dimension information.");
323
324      for (int i = 0; i < (vertices.Length / 2); i++) {
325        if (!(alternateFormat && i == 0)) {
326          string str = source.ReadLine();
327          string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
328
329          if (tokens.Length != 3)
330            throw new InvalidDataException("Input file contains invalid node coordinates.");
331
332          vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
333          vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
334        }
335      }
336    }
337
338    private void ReadCapacity(string str) {
339      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
340      capacity = double.Parse(tokens[tokens.Length - 1].Trim(), culture.NumberFormat);
341    }
342
343    private void ReadDistance(string str) {
344      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
345      distance = double.Parse(tokens[tokens.Length - 1].Trim(), culture.NumberFormat);
346    }
347
348    private void ReadVehicles(string str) {
349      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
350      vehicles = int.Parse(tokens[tokens.Length - 1].Trim());
351    }
352
353    private void ReadDepot() {
354      if (alternateFormat) {
355        string[] tokens;
356        do {
357          string str = source.ReadLine();
358          tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
359
360          if (tokens.Length == 2) {
361            vertices[0, 0] = double.Parse(tokens[0], culture.NumberFormat);
362            vertices[0, 1] = double.Parse(tokens[1], culture.NumberFormat);
363            depot = 1;
364          }
365        } while(tokens.Length == 2);
366      } else {
367        int read;
368        do {
369          string str = source.ReadLine();
370          read = int.Parse(str);
371          if (read != -1)
372            depot = read;
373        } while (read != -1);
374      }
375    }
376
377    private void ReadDemands() {
378      if (demands == null)
379        throw new InvalidDataException("Input file does not contain dimension information.");
380
381      for (int i = 0; i < demands.Length; i++) {
382        if (!(alternateFormat && i == 0)) {
383          string str = source.ReadLine();
384          string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
385
386          if (tokens.Length != 2)
387            throw new InvalidDataException("Input file contains invalid demands.");
388
389          int index = int.Parse(tokens[0]);
390          double value = double.Parse(tokens[1]);
391
392          if (alternateFormat)
393            demands[index] = value;
394          else
395            demands[index - 1] = value;
396        } else {
397          demands[0] = 0;
398        }
399      }
400    }
401  }
402}
Note: See TracBrowser for help on using the repository browser.