Context Navigation

← Previous Change
Next Change →

Changeset 7465 for branches

Timestamp:

02/10/12 23:11:59 (13 years ago)

Author:

abeham

Message:

#1614

Added TSPLIB instances (TSP, ATSP, CVRP)
Improved parser for TSPLIB file format
Added ProblemInstanceProvider as an abstract base class which handles the feeding of consumers

Location:

branches/GeneralizedQAP

Files:

: 195 added
: 4 edited
: 1 copied

Legend:

: Unmodified
: Added
: Removed

branches/GeneralizedQAP/GeneralizedQAP.sln

-                      r7444
+                      r7465
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Instances.ElloumiCTAP-3.3", "HeuristicLab.Problems.Instances.ElloumiCTAP\3.3\HeuristicLab.Problems.Instances.ElloumiCTAP-3.3.csproj", "{CCF61DA0-B226-4C0F-8052-29ACC6BDE6EE}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Instances.TSPLIB-3.3", "HeuristicLab.Problems.Instances.TSPLIB\3.3\HeuristicLab.Problems.Instances.TSPLIB-3.3.csproj", "{CE0F99D6-1C56-48A9-9B68-3E5B833703EF}"
 EndProject
 Global
 …
     {CCF61DA0-B226-4C0F-8052-29ACC6BDE6EE}.Release|x64.ActiveCfg = Release|Any CPU
     {CCF61DA0-B226-4C0F-8052-29ACC6BDE6EE}.Release|x86.ActiveCfg = Release|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|Any CPU.Build.0 = Debug|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|x64.ActiveCfg = Debug|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|x86.ActiveCfg = Debug|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|Any CPU.ActiveCfg = Release|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|Any CPU.Build.0 = Release|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|x64.ActiveCfg = Release|Any CPU
+    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|x86.ActiveCfg = Release|Any CPU
   EndGlobalSection
   GlobalSection(SolutionProperties) = preSolution

branches/GeneralizedQAP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBParser.cs

-                      r7453
+                      r7465
 using System;
+using System.Collections.Generic;
 using System.Globalization;
 using System.IO;
+namespace HeuristicLab.Problems.TravelingSalesman {
+  /// <summary>
+  /// Parses a *.tsp file in TSPLIB format and extracts its information about a TSP.
+  /// </summary>
+using System.Linq;
+namespace HeuristicLab.Problems.Instances.TSPLIB {
+  #region Public Enums
+  public enum TSPLIBTypes {
+    UNKNOWN = 0,
+    TSP = 1,
+    ATSP = 2,
+    SOP = 3,
+    HCP = 4,
+    CVRP = 5,
+    TOUR = 6
+  }
+  public enum TSPLIBEdgeWeightTypes {
+    UNKNOWN = 0,
+    EXPLICIT = 1,
+    EUC_2D = 2,
+    EUC_3D = 3,
+    MAX_2D = 4,
+    MAX_3D = 5,
+    MAN_2D = 6,
+    MAN_3D = 7,
+    CEIL_2D = 8,
+    GEO = 9,
+    ATT = 10,
+    XRAY1 = 11,
+    XRAY2 = 12,
+    SPECIAL = 13
+  }
+  public enum TSPLIBDisplayDataTypes {
+    UNKNOWN = 0,
+    COORD_DISPLAY = 1,
+    TWOD_DISPLAY = 2,
+    NO_DISPLAY = 3
+  }
+  #endregion
   public class TSPLIBParser {
+    #region Inner Enum TSPLIBEdgeWeightType
+    public enum TSPLIBEdgeWeightType {
+      UNDEFINED,
+      EUC_2D,
+      GEO
+    public string Name { get; private set; }
+    public TSPLIBTypes Type { get; private set; }
+    public string Comment { get; private set; }
+    public int Dimension { get; private set; }
+    public double? Capacity { get; private set; }
+    public TSPLIBEdgeWeightTypes EdgeWeightType { get; private set; }
+    public TSPLIBDisplayDataTypes DisplayDataType { get; private set; }
+    public double[,] Vertices { get; private set; }
+    public double[,] DisplayVertices { get; private set; }
+    public double[,] Distances { get; private set; }
+    public int[,] FixedEdges { get; private set; }
+    public int[] Depots { get; private set; }
+    public double[] Demands { get; private set; }
+    public int[][] Tour { get; private set; }
+    private static readonly char sectionSeparator = ':';
+    private static readonly char[] itemSeparator = new char[] { ' ', '\t' };
+    #region Private Enums
+    private enum TSPLIBSections {
+      UNKNOWN = 0,
+      EOF = 1,
+      NAME = 2,
+      TYPE = 3,
+      COMMENT = 4,
+      DIMENSION = 5,
+      CAPACITY = 6,
+      EDGE_WEIGHT_TYPE = 7,
+      EDGE_WEIGHT_FORMAT = 8,
+      EDGE_DATA_FORMAT = 9,
+      NODE_COORD_TYPE = 10,
+      DISPLAY_DATA_TYPE = 11,
+      NODE_COORD_SECTION = 12,
+      DEPOT_SECTION = 13,
+      DEMAND_SECTION = 14,
+      EDGE_DATA_SECTION = 15,
+      FIXED_EDGES_SECTION = 16,
+      DISPLAY_DATA_SECTION = 17,
+      TOUR_SECTION = 18,
+      EDGE_WEIGHT_SECTION = 19
+    }
+    private enum TSPLIBEdgeWeightFormats {
+      UNKNWON = 0,
+      FUNCTION = 1,
+      FULL_MATRIX = 2,
+      UPPER_ROW = 3,
+      LOWER_ROW = 4,
+      UPPER_DIAG_ROW = 5,
+      LOWER_DIAG_ROW = 6,
+      UPPER_COL = 7,
+      LOWER_COL = 8,
+      UPPER_DIAG_COL = 9,
+      LOWER_DIAG_COL = 10
+    }
+    private enum TSPLIBEdgeWeightDataFormats {
+      UNKNOWN = 0,
+      EDGE_LIST = 1,
+      ADJ_LIST = 2
+    }
+    private enum TSLPLIBNodeCoordTypes {
+      UNKNOWN = 0,
+      TWOD_COORDS = 1,
+      THREED_COORDS = 2,
+      NO_COORDS = 3
+    }
     #endregion
-    private const int EOF = 0;
-    private const int NAME = 1;
-    private const int TYPE = 2;
-    private const int COMMENT = 3;
-    private const int DIM = 4;
-    private const int WEIGHTTYPE = 5;
-    private const int NODETYPE = 6;
-    private const int NODESECTION = 7;
     private StreamReader source;
+    private string name;
+    private int currentLineNumber;
+    private TSPLIBEdgeWeightFormats edgeWeightFormat;
+    private TSPLIBEdgeWeightDataFormats edgeWeightDataFormat;
+    private TSLPLIBNodeCoordTypes nodeCoordType;
+    private TSPLIBDisplayDataTypes displayDataType;
+    private TSPLIBParser() {
+      Name = String.Empty;
+      Comment = String.Empty;
+      Type = TSPLIBTypes.UNKNOWN;
+      EdgeWeightType = TSPLIBEdgeWeightTypes.UNKNOWN;
+      edgeWeightFormat = TSPLIBEdgeWeightFormats.UNKNWON;
+      edgeWeightDataFormat = TSPLIBEdgeWeightDataFormats.UNKNOWN;
+      nodeCoordType = TSLPLIBNodeCoordTypes.UNKNOWN;
+      displayDataType = TSPLIBDisplayDataTypes.UNKNOWN;
+    }
+    public TSPLIBParser(String path)
+      : this() {
+      source = new StreamReader(path);
+    }
+    public TSPLIBParser(Stream stream)
+      : this() {
+      source = new StreamReader(stream);
+    }
     /// <summary>
+    /// Gets the name of the parsed TSP.
+    /// </summary>
+    public string Name {
+      get { return name; }
+    }
+    private string comment;
+    /// <summary>
+    /// Gets the comment of the parsed TSP.
+    /// </summary>
+    public string Comment {
+      get { return comment; }
+    }
+    private double[,] vertices;
+    /// <summary>
+    /// Gets the vertices of the parsed TSP.
+    /// </summary>
+    public double[,] Vertices {
+      get { return vertices; }
+    }
+    private TSPLIBEdgeWeightType weightType;
+    /// <summary>
+    /// Gets the weight type of the parsed TSP.
+    /// </summary>
+    public TSPLIBEdgeWeightType WeightType {
+      get { return weightType; }
+    }
+    /// <summary>
+    /// Initializes a new instance of <see cref="TSPLIBParser"/> with the given <paramref name="path"/>.
+    /// </summary>
+    /// <exception cref="ArgumentException">Thrown if the input file is not a TSPLIB TSP file (*.tsp)
+    /// </exception>
+    /// <param name="path">The path where the TSP is stored.</param>
+    public TSPLIBParser(String path) {
+      if (!path.EndsWith(".tsp"))
+        throw new ArgumentException("Input file has to be a TSPLIB TSP file (*.tsp).");
+      source = new StreamReader(path);
+      name = path;
+      comment = string.Empty;
+      vertices = null;
+      weightType = TSPLIBEdgeWeightType.UNDEFINED;
+    }
+    /// <summary>
+    /// Reads the TSPLIB TSP file and parses the elements.
+    /// Reads the TSPLIB file and parses the elements.
     /// </summary>
     /// <exception cref="InvalidDataException">Thrown if the file has an invalid format or contains invalid data.</exception>
     public void Parse() {
+      int section = -1;
+      string str = null;
+      bool typeIsChecked = false;
+      bool weightTypeIsChecked = false;
+      TSPLIBSections section;
+      string line;
+      currentLineNumber = 0;
+      try {
+        do {
+          line = NextLine();
+          string value;
+          section = GetSection(line, out value);
+          switch (section) {
+            case TSPLIBSections.UNKNOWN:
+              break;
+            case TSPLIBSections.NAME:
+              ReadName(value);
+              break;
+            case TSPLIBSections.TYPE:
+              ReadType(value);
+              break;
+            case TSPLIBSections.COMMENT:
+              ReadComment(value);
+              break;
+            case TSPLIBSections.DIMENSION:
+              ReadDimension(value);
+              break;
+            case TSPLIBSections.CAPACITY:
+              ReadCapacity(value);
+              break;
+            case TSPLIBSections.EDGE_WEIGHT_TYPE:
+              ReadEdgeWeightType(value);
+              break;
+            case TSPLIBSections.EDGE_WEIGHT_FORMAT:
+              ReadEdgeWeightFormat(value);
+              break;
+            case TSPLIBSections.EDGE_DATA_FORMAT:
+              ReadEdgeWeightDataFormat(value);
+              break;
+            case TSPLIBSections.NODE_COORD_TYPE:
+              ReadNodeCoordType(value);
+              break;
+            case TSPLIBSections.DISPLAY_DATA_TYPE:
+              ReadDisplayDataType(value);
+              break;
+            case TSPLIBSections.NODE_COORD_SECTION:
+              ReadNodeCoordsSection();
+              break;
+            case TSPLIBSections.DEPOT_SECTION:
+              ReadDepotSection();
+              break;
+            case TSPLIBSections.DEMAND_SECTION:
+              ReadDemandSection();
+              break;
+            case TSPLIBSections.EDGE_DATA_SECTION:
+              ReadEdgeDataSection();
+              break;
+            case TSPLIBSections.FIXED_EDGES_SECTION:
+              ReadFixedEdgesSection();
+              break;
+            case TSPLIBSections.DISPLAY_DATA_SECTION:
+              ReadDisplayDataSection();
+              break;
+            case TSPLIBSections.TOUR_SECTION:
+              ReadTourSection();
+              break;
+            case TSPLIBSections.EDGE_WEIGHT_SECTION:
+              ReadEdgeWeightSection();
+              break;
+            case TSPLIBSections.EOF:
+              break;
+            default:
+              throw new InvalidDataException("Input file contains unknown or unsupported section (" + line + ") in line " + currentLineNumber.ToString());
+          }
+        } while (!(section == TSPLIBSections.EOF || source.EndOfStream));
+      } finally {
+        source.Close();
+      }
+    }
+    private string NextLine() {
+      currentLineNumber++;
+      return source.ReadLine();
+    }
+    private TSPLIBSections GetSection(string line, out string value) {
+      value = String.Empty;
+      if (line == null)
+        return TSPLIBSections.UNKNOWN;
+      int sectionNameEnd = line.IndexOf(sectionSeparator);
+      if (sectionNameEnd == -1) sectionNameEnd = line.Length;
+      string sectionName = line.Substring(0, sectionNameEnd).Trim();
+      if (sectionNameEnd + 1 < line.Length)
+        value = line.Substring(sectionNameEnd + 1);
+      TSPLIBSections section;
+      if (Enum.TryParse(sectionName, out section)) {
+        return section;
+      } else return TSPLIBSections.UNKNOWN;
+    }
+    private void ReadName(string value) {
+      Name += value.Trim();
+    }
+    private void ReadType(string value) {
+      TSPLIBTypes t;
+      if (Enum.TryParse(value.Trim().ToUpper(), out t))
+        Type = t;
+      else Type = TSPLIBTypes.UNKNOWN;
+    }
+    private void ReadComment(string value) {
+      Comment += value.Trim() + Environment.NewLine;
+    }
+    private void ReadCapacity(string value) {
+      double c;
+      if (double.TryParse(value.Trim(), NumberStyles.Any, CultureInfo.InvariantCulture.NumberFormat, out c))
+        Capacity = c;
+      else throw new InvalidDataException("Parsing the capacity in line " + currentLineNumber + " failed. It is not recognized as double value.");
+    }
+    private void ReadDimension(string value) {
+      int dimension;
+      if (int.TryParse(value.Trim(), out dimension))
+        Dimension = dimension;
+      else throw new InvalidDataException("Parsing the dimension in line " + currentLineNumber + " failed. It is not recognized as an integer number.");
+    }
+    private void ReadEdgeWeightType(string value) {
+      TSPLIBEdgeWeightTypes e;
+      if (Enum.TryParse(value.Trim().ToUpper(), out e))
+        EdgeWeightType = e;
+      else throw new InvalidDataException("Input file contains an unsupported edge weight type (" + value + ") in line " + currentLineNumber + ".");
+    }
+    private void ReadEdgeWeightFormat(string value) {
+      TSPLIBEdgeWeightFormats e;
+      if (Enum.TryParse(value.Trim().ToUpper(), out e))
+        edgeWeightFormat = e;
+      else throw new InvalidDataException("Input file contains an unsupported edge weight format (" + value + ") in line " + currentLineNumber + ".");
+    }
+    private void ReadEdgeWeightDataFormat(string value) {
+      TSPLIBEdgeWeightDataFormats e;
+      if (Enum.TryParse(value.Trim().ToUpper(), out e))
+        edgeWeightDataFormat = e;
+      else throw new InvalidDataException("Input file contains an unsupported edge weight data format (" + value + ") in line " + currentLineNumber + ".");
+    }
+    private void ReadNodeCoordType(string value) {
+      TSLPLIBNodeCoordTypes n;
+      if (Enum.TryParse(value.Trim().ToUpper(), out n))
+        nodeCoordType = n;
+      else throw new InvalidDataException("Input file contains an unsupported node coordinates type (" + value + ") in line " + currentLineNumber + ".");
+    }
+    private void ReadDisplayDataType(string value) {
+      TSPLIBDisplayDataTypes d;
+      if (Enum.TryParse(value.Trim().ToUpper(), out d))
+        displayDataType = d;
+      else throw new InvalidDataException("Input file contains an unsupported display data type (" + value + ") in line " + currentLineNumber + ".");
+    }
+    private void ReadNodeCoordsSection() {
+      if (Dimension == 0)
+        throw new InvalidDataException("Input file does not contain dimension information.");
+      switch (nodeCoordType) {
+        case TSLPLIBNodeCoordTypes.NO_COORDS:
+          return;
+        case TSLPLIBNodeCoordTypes.UNKNOWN: // It's a pity that there is a documented standard which is ignored in most files.
+        case TSLPLIBNodeCoordTypes.TWOD_COORDS:
+          Vertices = new double[Dimension, 2];
+          break;
+        case TSLPLIBNodeCoordTypes.THREED_COORDS:
+          Vertices = new double[Dimension, 3];
+          break;
+        default:
+          throw new InvalidDataException("Input files does not specify a valid node coord type.");
+      }
+      for (int i = 0; i < Dimension; i++) {
+        string line = NextLine();
+        string[] tokens = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
+        if (tokens.Length != Vertices.GetLength(1) + 1)
+          throw new InvalidDataException("Input file contains invalid number of node coordinates in line " + currentLineNumber + ".");
+        int node;
+        if (int.TryParse(tokens[0], out node)) {
+          for (int j = 0; j < Vertices.GetLength(1); j++)
+            Vertices[node - 1, j] = double.Parse(tokens[j + 1], CultureInfo.InvariantCulture.NumberFormat);
+        } else throw new InvalidDataException("Input file does not specify a valid node in line " + currentLineNumber + ".");
+      }
+    }
+    private void ReadDepotSection() {
+      var depots = new List<int>();
       do {
+        str = source.ReadLine();
+        section = GetSection(str);
+        if (section != -1) {
+          switch (section) {
+            case NAME:
+              ReadName(str);
+              break;
+            case TYPE:
+              CheckType(str);
+              typeIsChecked = true;
+              break;
+            case COMMENT:
+              ReadComment(str);
+              break;
+            case DIM:
+              InitVerticesArray(str);
+              break;
+            case WEIGHTTYPE:
+              ReadWeightType(str);
+              weightTypeIsChecked = true;
+              break;
+            case NODETYPE:
+              CheckNodeType(str);
+              break;
+            case NODESECTION:
+              ReadVertices();
+              break;
+        string line = NextLine();
+        int node;
+        if (!int.TryParse(line, out node))
+          throw new InvalidDataException("Input file contains an unknown depot entry at line " + currentLineNumber + ".");
+        if (node == -1) break;
+        depots.Add(node);
+      } while (true);
+      Depots = depots.ToArray();
+    }
+    private void ReadDemandSection() {
+      if (Dimension == 0)
+        throw new InvalidDataException("Input file does not contain dimension information.");
+      Demands = new double[Dimension];
+      for (int i = 0; i < Dimension; i++) {
+        string[] tokens = NextLine().Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
+        int node;
+        if (int.TryParse(tokens[0], out node)) {
+          double demand;
+          if (double.TryParse(tokens[1], NumberStyles.Any, CultureInfo.InvariantCulture.NumberFormat, out demand))
+            Demands[node - 1] = demand;
+          else throw new InvalidDataException("Input file contains invalid demand information in line " + currentLineNumber + ".");
+        } else throw new InvalidDataException("Input file contains invalid node information in line " + currentLineNumber + ".");
+      }
+    }
+    private void ReadEdgeDataSection() {
+      throw new NotSupportedException("Files with an edge data section are not supported.");
+    }
+    private void ReadFixedEdgesSection() {
+      var edges = new List<Tuple<int, int>>();
+      bool finished = false;
+      while (!finished) {
+        string line = NextLine();
+        string[] tokens = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
+        if (tokens.Length == 1) {
+          int number;
+          if (!int.TryParse(tokens[0], NumberStyles.Integer, CultureInfo.InvariantCulture.NumberFormat, out number))
+            throw new InvalidDataException("Input file does not end the fixed edges section with \"-1\" in line " + currentLineNumber + ".");
+          if (number != -1)
+            throw new InvalidDataException("Input file must end the fixed edges section with a -1 in line " + currentLineNumber + ".");
+          finished = true;
+        } else {
+          if (tokens.Length != 2)
+            throw new InvalidDataException("Input file contains an error in line " + currentLineNumber + ", exactly two nodes need to be given in each line.");
+          int node1 = int.Parse(tokens[0], CultureInfo.InvariantCulture.NumberFormat) - 1;
+          int node2 = int.Parse(tokens[1], CultureInfo.InvariantCulture.NumberFormat) - 1;
+          edges.Add(Tuple.Create(node1, node2));
+        }
+      }
+      FixedEdges = new int[edges.Count, 2];
+      for (int i = 0; i < edges.Count; i++) {
+        FixedEdges[i, 0] = edges[i].Item1;
+        FixedEdges[i, 1] = edges[i].Item2;
+      }
+    }
+    private void ReadDisplayDataSection() {
+      if (Dimension == 0)
+        throw new InvalidDataException("Input file does not contain dimension information.");
+      switch (displayDataType) {
+        case TSPLIBDisplayDataTypes.NO_DISPLAY:
+        case TSPLIBDisplayDataTypes.COORD_DISPLAY:
+          return;
+        case TSPLIBDisplayDataTypes.TWOD_DISPLAY:
+          DisplayVertices = new double[Dimension, 2];
+          break;
+        default:
+          throw new InvalidDataException("Input files does not specify a valid node coord type.");
+      }
+      for (int i = 0; i < Dimension; i++) {
+        string line = NextLine();
+        string[] tokens = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
+        if (tokens.Length != DisplayVertices.GetLength(1) + 1)
+          throw new InvalidDataException("Input file contains invalid number of display data coordinates in line " + currentLineNumber + ".");
+        int node;
+        if (int.TryParse(tokens[0], out node)) {
+          for (int j = 0; j < DisplayVertices.GetLength(1); j++)
+            DisplayVertices[node - 1, j] = double.Parse(tokens[j + 1], CultureInfo.InvariantCulture.NumberFormat);
+        } else throw new InvalidDataException("Input file does not specify a valid node in line " + currentLineNumber + ".");
+      }
+    }
+    /// <summary>
+    /// Parses the tour section.
+    /// </summary>
+    /// <remarks>
+    /// Unfortunately, none of the given files for the TSP follow the description
+    /// in the TSPLIB documentation.
+    /// The faulty files use only one -1 to terminate the section as well as the tour
+    /// whereas the documentation says that one -1 terminates the tour and another -1
+    /// terminates the section.
+    /// So the parser peeks at the next character after a -1. If the next character
+    /// is an E as in EOF or the stream ends, the parser breaks. Otherwise it will
+    /// continue to read tours until a -1 is followed by a -1.
+    /// </remarks>
+    private void ReadTourSection() {
+      if (Dimension == 0)
+        throw new InvalidDataException("Input file does not contain dimension information.");
+      var tours = new List<List<int>>();
+      do {
+        string[] nodes = NextLine().Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
+        if (!nodes.Any()) break;
+        bool finished = false;
+        foreach (var nodeString in nodes) {
+          int node = int.Parse(nodeString, CultureInfo.InvariantCulture.NumberFormat);
+          if (node == -1) {
+            finished = (tours.Any() && tours.Last().Count == 0) // -1 followed by -1
+              || (source.BaseStream.CanSeek && source.Peek() == -1)
+              || source.Peek() == (int)'E';
+            if (finished) break;
+            tours.Add(new List<int>());
+          } else {
+            if (!tours.Any()) tours.Add(new List<int>());
+            tours.Last().Add(node - 1);
+          }
+        }
+      } while (!((section == EOF) || (str == null)));
+      if (!(typeIsChecked && weightTypeIsChecked))
+        throw new InvalidDataException("Input file does not contain type or edge weight type information.");
+    }
+    private int GetSection(string str) {
+      if (str == null)
+        return EOF;
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      if (tokens.Length == 0)
+        return -1;
+      string token = tokens[0].Trim();
+      if (token.Equals("eof", StringComparison.OrdinalIgnoreCase))
+        return EOF;
+      if (token.Equals("name", StringComparison.OrdinalIgnoreCase))
+        return NAME;
+      if (token.Equals("type", StringComparison.OrdinalIgnoreCase))
+        return TYPE;
+      if (token.Equals("comment", StringComparison.OrdinalIgnoreCase))
+        return COMMENT;
+      if (token.Equals("dimension", StringComparison.OrdinalIgnoreCase))
+        return DIM;
+      if (token.Equals("edge_weight_type", StringComparison.OrdinalIgnoreCase))
+        return WEIGHTTYPE;
+      if (token.Equals("node_coord_type", StringComparison.OrdinalIgnoreCase))
+        return NODETYPE;
+      if (token.Equals("node_coord_section", StringComparison.OrdinalIgnoreCase))
+        return NODESECTION;
+      return -1;
+    }
+    private void ReadName(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      name = tokens[tokens.Length - 1].Trim();
+    }
+    private void CheckType(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      string type = tokens[tokens.Length - 1].Trim();
+      if (!type.Equals("tsp", StringComparison.OrdinalIgnoreCase))
+        throw new InvalidDataException("Input file type is not \"TSP\"");
+    }
+    private void ReadComment(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      comment = tokens[tokens.Length - 1].Trim();
+    }
+    private void InitVerticesArray(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      string dimension = tokens[tokens.Length - 1].Trim();
+      int dim = Int32.Parse(dimension);
+      vertices = new double[dim, 2];
+    }
+    private void ReadWeightType(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      string type = tokens[tokens.Length - 1].Trim();
+      if (type.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
+        weightType = TSPLIBEdgeWeightType.EUC_2D;
+      else if (type.Equals("geo", StringComparison.OrdinalIgnoreCase))
+        weightType = TSPLIBEdgeWeightType.GEO;
+      else
+        throw new InvalidDataException("Input file contains an unsupported edge weight type (only \"EUC_2D\" and \"GEO\" are supported).");
+    }
+    private void CheckNodeType(string str) {
+      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
+      string type = tokens[tokens.Length - 1].Trim();
+      if (!type.Equals("twod_coords", StringComparison.OrdinalIgnoreCase))
+        throw new InvalidDataException("Input file contains an unsupported node coordinates type (only \"TWOD_COORDS\" is supported).");
+    }
+    private void ReadVertices() {
+      if (vertices == null)
+        if (finished) break;
+      } while (true);
+      if (tours.Last().Count == 0) tours.RemoveAt(tours.Count - 1);
+      Tour = tours.Select(x => x.ToArray()).ToArray();
+    }
+    private void ReadEdgeWeightSection() {
+      if (Dimension == 0)
         throw new InvalidDataException("Input file does not contain dimension information.");
+      for (int i = 0; i < (vertices.Length / 2); i++) {
+        string str = source.ReadLine();
+        string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
+        if (tokens.Length != 3)
+          throw new InvalidDataException("Input file contains invalid node coordinates.");
+        CultureInfo culture = new CultureInfo("en-US");
+        vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
+        vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
+      }
+    }
+      if (edgeWeightFormat == TSPLIBEdgeWeightFormats.UNKNWON)
+        throw new InvalidDataException("Input file does not specify an edge weight format.");
+      if (edgeWeightFormat == TSPLIBEdgeWeightFormats.FUNCTION)
+        return;
+      Distances = new double[Dimension, Dimension];
+      bool triangular = edgeWeightFormat != TSPLIBEdgeWeightFormats.FULL_MATRIX;
+      bool upperTriangular = edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_COL
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_COL
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_ROW
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_ROW;
+      bool diagonal = edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_DIAG_COL
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_DIAG_ROW
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_COL
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_ROW;
+      bool rowWise = edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_DIAG_ROW
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_ROW
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_ROW
+        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_ROW;
+      int dim1 = !upperTriangular ? (diagonal ? 0 : 1) : 0;
+      int dim2 = upperTriangular ? (diagonal ? 0 : 1) : 0;
+      bool finished = false;
+      while (!finished) {
+        string line = NextLine();
+        string[] weights = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
+        foreach (var weightString in weights) {
+          double weight;
+          if (!double.TryParse(weightString, NumberStyles.Any, CultureInfo.InvariantCulture.NumberFormat, out weight))
+            throw new InvalidDataException("Input file contains unreadable weight information (" + weightString + ") in line " + currentLineNumber + ".");
+          if (triangular) {
+            Distances[dim1, dim2] = weight;
+            Distances[dim2, dim1] = weight;
+            if (upperTriangular) {
+              if (rowWise) {
+                dim2++;
+                if (dim2 == Dimension) {
+                  dim1++;
+                  if (diagonal) dim2 = dim1;
+                  else dim2 = dim1 + 1;
+                }
+              } else { // column-wise
+                dim1++;
+                if (diagonal && dim1 == dim2 + 1
+                  || !diagonal && dim1 == dim2) {
+                  dim2++;
+                  dim1 = 0;
+                }
+              }
+            } else { // lower-triangular
+              if (rowWise) {
+                dim2++;
+                if (diagonal && dim2 == dim1 + 1
+                  || !diagonal && dim2 == dim1) {
+                  dim1++;
+                  dim2 = 0;
+                }
+              } else { // column-wise
+                dim1++;
+                if (dim1 == Dimension) {
+                  dim2++;
+                  if (diagonal) dim1 = dim2;
+                  else dim1 = dim2 + 1;
+                }
+              }
+            }
+          } else { // full-matrix
+            Distances[dim1, dim2] = weight;
+            dim2++;
+            if (dim2 == Dimension) {
+              dim1++;
+              dim2 = 0;
+            }
+          }
+        }
+        finished = dim1 == Dimension || dim2 == Dimension;
+      }
+    }
+  }
+}

branches/GeneralizedQAP/HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj

-                      r7448
+                      r7465
     <Compile Include="IInstanceDescriptor.cs" />
     <Compile Include="Instances\IQAPInstance.cs" />
+    <Compile Include="Instances\ITSPInstance.cs" />
     <Compile Include="IProblemInstanceConsumer.cs" />
     <Compile Include="IProblemInstanceProvider.cs" />
     <Compile Include="Plugin.cs" />
+    <Compile Include="ProblemInstanceProvider.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <None Include="Properties\AssemblyInfo.cs.frame" />

branches/GeneralizedQAP/HeuristicLab.Problems.Instances/3.3/Plugin.cs

r7448	r7465
23	23
24	24	namespace HeuristicLab.Problems.Instances {
25		[Plugin("HeuristicLab.Problems.Instances", "3.3.6.7445")]
	25	[Plugin("HeuristicLab.Problems.Instances", "3.3.6.7448")]
26	26	[PluginFile("HeuristicLab.Problems.Instances-3.3.dll", PluginFileType.Assembly)]
27	27	public class HeuristicLabProblemsInstancesPlugin : PluginBase {

branches/GeneralizedQAP/UnitTests/UnitTests.csproj

-                      r7412
+                      r7465
     <Compile Include="GQAPNMoveEvaluatorTest.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="TSPLIBInstanceProviderTest.cs" />
   </ItemGroup>
   <ItemGroup>
 …
       <Project>{C739E6D2-5680-4804-A810-8017DA0C238F}</Project>
       <Name>HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.Instances.TSPLIB\3.3\HeuristicLab.Problems.Instances.TSPLIB-3.3.csproj">
+      <Project>{CE0F99D6-1C56-48A9-9B68-3E5B833703EF}</Project>
+      <Name>HeuristicLab.Problems.Instances.TSPLIB-3.3</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
+      <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
+      <Name>HeuristicLab.Problems.Instances-3.3</Name>
     </ProjectReference>
   </ItemGroup>

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 7465 for branches

Legend:

branches/GeneralizedQAP/GeneralizedQAP.sln

branches/GeneralizedQAP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBParser.cs

branches/GeneralizedQAP/HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj

branches/GeneralizedQAP/HeuristicLab.Problems.Instances/3.3/Plugin.cs

branches/GeneralizedQAP/UnitTests/UnitTests.csproj

Download in other formats: