Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/10/12 23:11:59 (12 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/HeuristicLab.Problems.Instances.TSPLIB
Files:
2 added
1 copied

Legend:

Unmodified
Added
Removed

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

    r7453 r7465  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Globalization;
    2425using System.IO;
    25 
    26 namespace HeuristicLab.Problems.TravelingSalesman {
    27   /// <summary>
    28   /// Parses a *.tsp file in TSPLIB format and extracts its information about a TSP.
    29   /// </summary>
     26using System.Linq;
     27
     28namespace HeuristicLab.Problems.Instances.TSPLIB {
     29
     30  #region Public Enums
     31  public enum TSPLIBTypes {
     32    UNKNOWN = 0,
     33    TSP = 1,
     34    ATSP = 2,
     35    SOP = 3,
     36    HCP = 4,
     37    CVRP = 5,
     38    TOUR = 6
     39  }
     40
     41  public enum TSPLIBEdgeWeightTypes {
     42    UNKNOWN = 0,
     43    EXPLICIT = 1,
     44    EUC_2D = 2,
     45    EUC_3D = 3,
     46    MAX_2D = 4,
     47    MAX_3D = 5,
     48    MAN_2D = 6,
     49    MAN_3D = 7,
     50    CEIL_2D = 8,
     51    GEO = 9,
     52    ATT = 10,
     53    XRAY1 = 11,
     54    XRAY2 = 12,
     55    SPECIAL = 13
     56  }
     57
     58  public enum TSPLIBDisplayDataTypes {
     59    UNKNOWN = 0,
     60    COORD_DISPLAY = 1,
     61    TWOD_DISPLAY = 2,
     62    NO_DISPLAY = 3
     63  }
     64  #endregion
     65
    3066  public class TSPLIBParser {
    31     #region Inner Enum TSPLIBEdgeWeightType
    32     public enum TSPLIBEdgeWeightType {
    33       UNDEFINED,
    34       EUC_2D,
    35       GEO
     67
     68    public string Name { get; private set; }
     69    public TSPLIBTypes Type { get; private set; }
     70    public string Comment { get; private set; }
     71    public int Dimension { get; private set; }
     72    public double? Capacity { get; private set; }
     73    public TSPLIBEdgeWeightTypes EdgeWeightType { get; private set; }
     74    public TSPLIBDisplayDataTypes DisplayDataType { get; private set; }
     75    public double[,] Vertices { get; private set; }
     76    public double[,] DisplayVertices { get; private set; }
     77    public double[,] Distances { get; private set; }
     78    public int[,] FixedEdges { get; private set; }
     79    public int[] Depots { get; private set; }
     80    public double[] Demands { get; private set; }
     81    public int[][] Tour { get; private set; }
     82
     83    private static readonly char sectionSeparator = ':';
     84    private static readonly char[] itemSeparator = new char[] { ' ', '\t' };
     85
     86    #region Private Enums
     87    private enum TSPLIBSections {
     88      UNKNOWN = 0,
     89      EOF = 1,
     90      NAME = 2,
     91      TYPE = 3,
     92      COMMENT = 4,
     93      DIMENSION = 5,
     94      CAPACITY = 6,
     95      EDGE_WEIGHT_TYPE = 7,
     96      EDGE_WEIGHT_FORMAT = 8,
     97      EDGE_DATA_FORMAT = 9,
     98      NODE_COORD_TYPE = 10,
     99      DISPLAY_DATA_TYPE = 11,
     100      NODE_COORD_SECTION = 12,
     101      DEPOT_SECTION = 13,
     102      DEMAND_SECTION = 14,
     103      EDGE_DATA_SECTION = 15,
     104      FIXED_EDGES_SECTION = 16,
     105      DISPLAY_DATA_SECTION = 17,
     106      TOUR_SECTION = 18,
     107      EDGE_WEIGHT_SECTION = 19
     108    }
     109    private enum TSPLIBEdgeWeightFormats {
     110      UNKNWON = 0,
     111      FUNCTION = 1,
     112      FULL_MATRIX = 2,
     113      UPPER_ROW = 3,
     114      LOWER_ROW = 4,
     115      UPPER_DIAG_ROW = 5,
     116      LOWER_DIAG_ROW = 6,
     117      UPPER_COL = 7,
     118      LOWER_COL = 8,
     119      UPPER_DIAG_COL = 9,
     120      LOWER_DIAG_COL = 10
     121    }
     122    private enum TSPLIBEdgeWeightDataFormats {
     123      UNKNOWN = 0,
     124      EDGE_LIST = 1,
     125      ADJ_LIST = 2
     126    }
     127    private enum TSLPLIBNodeCoordTypes {
     128      UNKNOWN = 0,
     129      TWOD_COORDS = 1,
     130      THREED_COORDS = 2,
     131      NO_COORDS = 3
    36132    }
    37133    #endregion
    38134
    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 
    48135    private StreamReader source;
    49 
    50     private string name;
     136    private int currentLineNumber;
     137
     138    private TSPLIBEdgeWeightFormats edgeWeightFormat;
     139    private TSPLIBEdgeWeightDataFormats edgeWeightDataFormat;
     140    private TSLPLIBNodeCoordTypes nodeCoordType;
     141    private TSPLIBDisplayDataTypes displayDataType;
     142
     143    private TSPLIBParser() {
     144      Name = String.Empty;
     145      Comment = String.Empty;
     146      Type = TSPLIBTypes.UNKNOWN;
     147      EdgeWeightType = TSPLIBEdgeWeightTypes.UNKNOWN;
     148
     149      edgeWeightFormat = TSPLIBEdgeWeightFormats.UNKNWON;
     150      edgeWeightDataFormat = TSPLIBEdgeWeightDataFormats.UNKNOWN;
     151      nodeCoordType = TSLPLIBNodeCoordTypes.UNKNOWN;
     152      displayDataType = TSPLIBDisplayDataTypes.UNKNOWN;
     153    }
     154
     155    public TSPLIBParser(String path)
     156      : this() {
     157      source = new StreamReader(path);
     158    }
     159
     160    public TSPLIBParser(Stream stream)
     161      : this() {
     162      source = new StreamReader(stream);
     163    }
     164
    51165    /// <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.
     166    /// Reads the TSPLIB file and parses the elements.
    98167    /// </summary>
    99168    /// <exception cref="InvalidDataException">Thrown if the file has an invalid format or contains invalid data.</exception>
    100169    public void Parse() {
    101       int section = -1;
    102       string str = null;
    103       bool typeIsChecked = false;
    104       bool weightTypeIsChecked = false;
    105 
     170      TSPLIBSections section;
     171      string line;
     172      currentLineNumber = 0;
     173
     174      try {
     175        do {
     176          line = NextLine();
     177          string value;
     178          section = GetSection(line, out value);
     179
     180          switch (section) {
     181            case TSPLIBSections.UNKNOWN:
     182              break;
     183            case TSPLIBSections.NAME:
     184              ReadName(value);
     185              break;
     186            case TSPLIBSections.TYPE:
     187              ReadType(value);
     188              break;
     189            case TSPLIBSections.COMMENT:
     190              ReadComment(value);
     191              break;
     192            case TSPLIBSections.DIMENSION:
     193              ReadDimension(value);
     194              break;
     195            case TSPLIBSections.CAPACITY:
     196              ReadCapacity(value);
     197              break;
     198            case TSPLIBSections.EDGE_WEIGHT_TYPE:
     199              ReadEdgeWeightType(value);
     200              break;
     201            case TSPLIBSections.EDGE_WEIGHT_FORMAT:
     202              ReadEdgeWeightFormat(value);
     203              break;
     204            case TSPLIBSections.EDGE_DATA_FORMAT:
     205              ReadEdgeWeightDataFormat(value);
     206              break;
     207            case TSPLIBSections.NODE_COORD_TYPE:
     208              ReadNodeCoordType(value);
     209              break;
     210            case TSPLIBSections.DISPLAY_DATA_TYPE:
     211              ReadDisplayDataType(value);
     212              break;
     213            case TSPLIBSections.NODE_COORD_SECTION:
     214              ReadNodeCoordsSection();
     215              break;
     216            case TSPLIBSections.DEPOT_SECTION:
     217              ReadDepotSection();
     218              break;
     219            case TSPLIBSections.DEMAND_SECTION:
     220              ReadDemandSection();
     221              break;
     222            case TSPLIBSections.EDGE_DATA_SECTION:
     223              ReadEdgeDataSection();
     224              break;
     225            case TSPLIBSections.FIXED_EDGES_SECTION:
     226              ReadFixedEdgesSection();
     227              break;
     228            case TSPLIBSections.DISPLAY_DATA_SECTION:
     229              ReadDisplayDataSection();
     230              break;
     231            case TSPLIBSections.TOUR_SECTION:
     232              ReadTourSection();
     233              break;
     234            case TSPLIBSections.EDGE_WEIGHT_SECTION:
     235              ReadEdgeWeightSection();
     236              break;
     237            case TSPLIBSections.EOF:
     238              break;
     239            default:
     240              throw new InvalidDataException("Input file contains unknown or unsupported section (" + line + ") in line " + currentLineNumber.ToString());
     241          }
     242        } while (!(section == TSPLIBSections.EOF || source.EndOfStream));
     243      } finally {
     244        source.Close();
     245      }
     246    }
     247
     248    private string NextLine() {
     249      currentLineNumber++;
     250      return source.ReadLine();
     251    }
     252
     253    private TSPLIBSections GetSection(string line, out string value) {
     254      value = String.Empty;
     255
     256      if (line == null)
     257        return TSPLIBSections.UNKNOWN;
     258
     259      int sectionNameEnd = line.IndexOf(sectionSeparator);
     260      if (sectionNameEnd == -1) sectionNameEnd = line.Length;
     261
     262      string sectionName = line.Substring(0, sectionNameEnd).Trim();
     263      if (sectionNameEnd + 1 < line.Length)
     264        value = line.Substring(sectionNameEnd + 1);
     265
     266      TSPLIBSections section;
     267      if (Enum.TryParse(sectionName, out section)) {
     268        return section;
     269      } else return TSPLIBSections.UNKNOWN;
     270    }
     271
     272    private void ReadName(string value) {
     273      Name += value.Trim();
     274    }
     275
     276    private void ReadType(string value) {
     277      TSPLIBTypes t;
     278      if (Enum.TryParse(value.Trim().ToUpper(), out t))
     279        Type = t;
     280      else Type = TSPLIBTypes.UNKNOWN;
     281    }
     282
     283    private void ReadComment(string value) {
     284      Comment += value.Trim() + Environment.NewLine;
     285    }
     286
     287    private void ReadCapacity(string value) {
     288      double c;
     289      if (double.TryParse(value.Trim(), NumberStyles.Any, CultureInfo.InvariantCulture.NumberFormat, out c))
     290        Capacity = c;
     291      else throw new InvalidDataException("Parsing the capacity in line " + currentLineNumber + " failed. It is not recognized as double value.");
     292    }
     293
     294    private void ReadDimension(string value) {
     295      int dimension;
     296      if (int.TryParse(value.Trim(), out dimension))
     297        Dimension = dimension;
     298      else throw new InvalidDataException("Parsing the dimension in line " + currentLineNumber + " failed. It is not recognized as an integer number.");
     299    }
     300
     301    private void ReadEdgeWeightType(string value) {
     302      TSPLIBEdgeWeightTypes e;
     303      if (Enum.TryParse(value.Trim().ToUpper(), out e))
     304        EdgeWeightType = e;
     305      else throw new InvalidDataException("Input file contains an unsupported edge weight type (" + value + ") in line " + currentLineNumber + ".");
     306    }
     307
     308    private void ReadEdgeWeightFormat(string value) {
     309      TSPLIBEdgeWeightFormats e;
     310      if (Enum.TryParse(value.Trim().ToUpper(), out e))
     311        edgeWeightFormat = e;
     312      else throw new InvalidDataException("Input file contains an unsupported edge weight format (" + value + ") in line " + currentLineNumber + ".");
     313    }
     314
     315    private void ReadEdgeWeightDataFormat(string value) {
     316      TSPLIBEdgeWeightDataFormats e;
     317      if (Enum.TryParse(value.Trim().ToUpper(), out e))
     318        edgeWeightDataFormat = e;
     319      else throw new InvalidDataException("Input file contains an unsupported edge weight data format (" + value + ") in line " + currentLineNumber + ".");
     320    }
     321
     322    private void ReadNodeCoordType(string value) {
     323      TSLPLIBNodeCoordTypes n;
     324      if (Enum.TryParse(value.Trim().ToUpper(), out n))
     325        nodeCoordType = n;
     326      else throw new InvalidDataException("Input file contains an unsupported node coordinates type (" + value + ") in line " + currentLineNumber + ".");
     327    }
     328
     329    private void ReadDisplayDataType(string value) {
     330      TSPLIBDisplayDataTypes d;
     331      if (Enum.TryParse(value.Trim().ToUpper(), out d))
     332        displayDataType = d;
     333      else throw new InvalidDataException("Input file contains an unsupported display data type (" + value + ") in line " + currentLineNumber + ".");
     334    }
     335
     336    private void ReadNodeCoordsSection() {
     337      if (Dimension == 0)
     338        throw new InvalidDataException("Input file does not contain dimension information.");
     339      switch (nodeCoordType) {
     340        case TSLPLIBNodeCoordTypes.NO_COORDS:
     341          return;
     342        case TSLPLIBNodeCoordTypes.UNKNOWN: // It's a pity that there is a documented standard which is ignored in most files.
     343        case TSLPLIBNodeCoordTypes.TWOD_COORDS:
     344          Vertices = new double[Dimension, 2];
     345          break;
     346        case TSLPLIBNodeCoordTypes.THREED_COORDS:
     347          Vertices = new double[Dimension, 3];
     348          break;
     349        default:
     350          throw new InvalidDataException("Input files does not specify a valid node coord type.");
     351      }
     352
     353      for (int i = 0; i < Dimension; i++) {
     354        string line = NextLine();
     355        string[] tokens = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
     356
     357        if (tokens.Length != Vertices.GetLength(1) + 1)
     358          throw new InvalidDataException("Input file contains invalid number of node coordinates in line " + currentLineNumber + ".");
     359
     360        int node;
     361        if (int.TryParse(tokens[0], out node)) {
     362          for (int j = 0; j < Vertices.GetLength(1); j++)
     363            Vertices[node - 1, j] = double.Parse(tokens[j + 1], CultureInfo.InvariantCulture.NumberFormat);
     364        } else throw new InvalidDataException("Input file does not specify a valid node in line " + currentLineNumber + ".");
     365      }
     366    }
     367
     368    private void ReadDepotSection() {
     369      var depots = new List<int>();
    106370      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;
     371        string line = NextLine();
     372        int node;
     373        if (!int.TryParse(line, out node))
     374          throw new InvalidDataException("Input file contains an unknown depot entry at line " + currentLineNumber + ".");
     375        if (node == -1) break;
     376        depots.Add(node);
     377      } while (true);
     378      Depots = depots.ToArray();
     379    }
     380
     381    private void ReadDemandSection() {
     382      if (Dimension == 0)
     383        throw new InvalidDataException("Input file does not contain dimension information.");
     384      Demands = new double[Dimension];
     385      for (int i = 0; i < Dimension; i++) {
     386        string[] tokens = NextLine().Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
     387        int node;
     388        if (int.TryParse(tokens[0], out node)) {
     389          double demand;
     390          if (double.TryParse(tokens[1], NumberStyles.Any, CultureInfo.InvariantCulture.NumberFormat, out demand))
     391            Demands[node - 1] = demand;
     392          else throw new InvalidDataException("Input file contains invalid demand information in line " + currentLineNumber + ".");
     393        } else throw new InvalidDataException("Input file contains invalid node information in line " + currentLineNumber + ".");
     394      }
     395    }
     396
     397    private void ReadEdgeDataSection() {
     398      throw new NotSupportedException("Files with an edge data section are not supported.");
     399    }
     400
     401    private void ReadFixedEdgesSection() {
     402      var edges = new List<Tuple<int, int>>();
     403      bool finished = false;
     404      while (!finished) {
     405        string line = NextLine();
     406        string[] tokens = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
     407        if (tokens.Length == 1) {
     408          int number;
     409          if (!int.TryParse(tokens[0], NumberStyles.Integer, CultureInfo.InvariantCulture.NumberFormat, out number))
     410            throw new InvalidDataException("Input file does not end the fixed edges section with \"-1\" in line " + currentLineNumber + ".");
     411          if (number != -1)
     412            throw new InvalidDataException("Input file must end the fixed edges section with a -1 in line " + currentLineNumber + ".");
     413          finished = true;
     414        } else {
     415          if (tokens.Length != 2)
     416            throw new InvalidDataException("Input file contains an error in line " + currentLineNumber + ", exactly two nodes need to be given in each line.");
     417          int node1 = int.Parse(tokens[0], CultureInfo.InvariantCulture.NumberFormat) - 1;
     418          int node2 = int.Parse(tokens[1], CultureInfo.InvariantCulture.NumberFormat) - 1;
     419          edges.Add(Tuple.Create(node1, node2));
     420        }
     421      }
     422      FixedEdges = new int[edges.Count, 2];
     423      for (int i = 0; i < edges.Count; i++) {
     424        FixedEdges[i, 0] = edges[i].Item1;
     425        FixedEdges[i, 1] = edges[i].Item2;
     426      }
     427    }
     428
     429    private void ReadDisplayDataSection() {
     430      if (Dimension == 0)
     431        throw new InvalidDataException("Input file does not contain dimension information.");
     432
     433      switch (displayDataType) {
     434        case TSPLIBDisplayDataTypes.NO_DISPLAY:
     435        case TSPLIBDisplayDataTypes.COORD_DISPLAY:
     436          return;
     437        case TSPLIBDisplayDataTypes.TWOD_DISPLAY:
     438          DisplayVertices = new double[Dimension, 2];
     439          break;
     440        default:
     441          throw new InvalidDataException("Input files does not specify a valid node coord type.");
     442      }
     443
     444      for (int i = 0; i < Dimension; i++) {
     445        string line = NextLine();
     446        string[] tokens = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
     447
     448        if (tokens.Length != DisplayVertices.GetLength(1) + 1)
     449          throw new InvalidDataException("Input file contains invalid number of display data coordinates in line " + currentLineNumber + ".");
     450
     451        int node;
     452        if (int.TryParse(tokens[0], out node)) {
     453          for (int j = 0; j < DisplayVertices.GetLength(1); j++)
     454            DisplayVertices[node - 1, j] = double.Parse(tokens[j + 1], CultureInfo.InvariantCulture.NumberFormat);
     455        } else throw new InvalidDataException("Input file does not specify a valid node in line " + currentLineNumber + ".");
     456      }
     457    }
     458
     459    /// <summary>
     460    /// Parses the tour section.
     461    /// </summary>
     462    /// <remarks>
     463    /// Unfortunately, none of the given files for the TSP follow the description
     464    /// in the TSPLIB documentation.
     465    /// The faulty files use only one -1 to terminate the section as well as the tour
     466    /// whereas the documentation says that one -1 terminates the tour and another -1
     467    /// terminates the section.
     468    /// So the parser peeks at the next character after a -1. If the next character
     469    /// is an E as in EOF or the stream ends, the parser breaks. Otherwise it will
     470    /// continue to read tours until a -1 is followed by a -1.
     471    /// </remarks>
     472    private void ReadTourSection() {
     473      if (Dimension == 0)
     474        throw new InvalidDataException("Input file does not contain dimension information.");
     475
     476      var tours = new List<List<int>>();
     477      do {
     478        string[] nodes = NextLine().Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
     479        if (!nodes.Any()) break;
     480
     481        bool finished = false;
     482        foreach (var nodeString in nodes) {
     483          int node = int.Parse(nodeString, CultureInfo.InvariantCulture.NumberFormat);
     484          if (node == -1) {
     485            finished = (tours.Any() && tours.Last().Count == 0) // -1 followed by -1
     486              || (source.BaseStream.CanSeek && source.Peek() == -1)
     487              || source.Peek() == (int)'E';
     488            if (finished) break;
     489            tours.Add(new List<int>());
     490          } else {
     491            if (!tours.Any()) tours.Add(new List<int>());
     492            tours.Last().Add(node - 1);
    135493          }
    136494        }
    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)
     495        if (finished) break;
     496      } while (true);
     497      if (tours.Last().Count == 0) tours.RemoveAt(tours.Count - 1);
     498      Tour = tours.Select(x => x.ToArray()).ToArray();
     499    }
     500
     501    private void ReadEdgeWeightSection() {
     502      if (Dimension == 0)
    220503        throw new InvalidDataException("Input file does not contain dimension information.");
    221504
    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     }
     505      if (edgeWeightFormat == TSPLIBEdgeWeightFormats.UNKNWON)
     506        throw new InvalidDataException("Input file does not specify an edge weight format.");
     507
     508      if (edgeWeightFormat == TSPLIBEdgeWeightFormats.FUNCTION)
     509        return;
     510
     511      Distances = new double[Dimension, Dimension];
     512
     513      bool triangular = edgeWeightFormat != TSPLIBEdgeWeightFormats.FULL_MATRIX;
     514      bool upperTriangular = edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_COL
     515        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_COL
     516        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_ROW
     517        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_ROW;
     518      bool diagonal = edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_DIAG_COL
     519        || edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_DIAG_ROW
     520        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_COL
     521        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_ROW;
     522      bool rowWise = edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_DIAG_ROW
     523        || edgeWeightFormat == TSPLIBEdgeWeightFormats.LOWER_ROW
     524        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_DIAG_ROW
     525        || edgeWeightFormat == TSPLIBEdgeWeightFormats.UPPER_ROW;
     526
     527      int dim1 = !upperTriangular ? (diagonal ? 0 : 1) : 0;
     528      int dim2 = upperTriangular ? (diagonal ? 0 : 1) : 0;
     529      bool finished = false;
     530      while (!finished) {
     531        string line = NextLine();
     532        string[] weights = line.Split(itemSeparator, StringSplitOptions.RemoveEmptyEntries);
     533        foreach (var weightString in weights) {
     534          double weight;
     535          if (!double.TryParse(weightString, NumberStyles.Any, CultureInfo.InvariantCulture.NumberFormat, out weight))
     536            throw new InvalidDataException("Input file contains unreadable weight information (" + weightString + ") in line " + currentLineNumber + ".");
     537
     538          if (triangular) {
     539            Distances[dim1, dim2] = weight;
     540            Distances[dim2, dim1] = weight;
     541            if (upperTriangular) {
     542              if (rowWise) {
     543                dim2++;
     544                if (dim2 == Dimension) {
     545                  dim1++;
     546                  if (diagonal) dim2 = dim1;
     547                  else dim2 = dim1 + 1;
     548                }
     549              } else { // column-wise
     550                dim1++;
     551                if (diagonal && dim1 == dim2 + 1
     552                  || !diagonal && dim1 == dim2) {
     553                  dim2++;
     554                  dim1 = 0;
     555                }
     556              }
     557            } else { // lower-triangular
     558              if (rowWise) {
     559                dim2++;
     560                if (diagonal && dim2 == dim1 + 1
     561                  || !diagonal && dim2 == dim1) {
     562                  dim1++;
     563                  dim2 = 0;
     564                }
     565              } else { // column-wise
     566                dim1++;
     567                if (dim1 == Dimension) {
     568                  dim2++;
     569                  if (diagonal) dim1 = dim2;
     570                  else dim1 = dim2 + 1;
     571                }
     572              }
     573            }
     574          } else { // full-matrix
     575            Distances[dim1, dim2] = weight;
     576            dim2++;
     577            if (dim2 == Dimension) {
     578              dim1++;
     579              dim2 = 0;
     580            }
     581          }
     582        }
     583        finished = dim1 == Dimension || dim2 == Dimension;
     584      }
     585    }
     586
    234587  }
    235588}
Note: See TracChangeset for help on using the changeset viewer.