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 |
|
---|
22 | using System;
|
---|
23 | using System.Globalization;
|
---|
24 | using System.IO;
|
---|
25 |
|
---|
26 | namespace 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 | }
|
---|