Changeset 3151


Ignore:
Timestamp:
03/21/10 23:55:23 (12 years ago)
Author:
swagner
Message:

Implemented import of optimal TSP solutions (#924).

Location:
trunk/sources
Files:
4 added
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/HeuristicLab.Problems.TSP.Views-3.3.csproj

    r3107 r3151  
    9292    </Compile>
    9393    <Compile Include="HeuristicLabProblemsTSPViewsPlugin.cs" />
     94    <Compile Include="TSPLIBImportDialog.cs">
     95      <SubType>Form</SubType>
     96    </Compile>
     97    <Compile Include="TSPLIBImportDialog.Designer.cs">
     98      <DependentUpon>TSPLIBImportDialog.cs</DependentUpon>
     99    </Compile>
    94100    <Compile Include="TSPView.cs">
    95101      <SubType>UserControl</SubType>
     
    109115      <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project>
    110116      <Name>HeuristicLab.Collections-3.3</Name>
     117    </ProjectReference>
     118    <ProjectReference Include="..\..\HeuristicLab.Common.Resources\3.2\HeuristicLab.Common.Resources-3.2.csproj">
     119      <Project>{0E27A536-1C4A-4624-A65E-DC4F4F23E3E1}</Project>
     120      <Name>HeuristicLab.Common.Resources-3.2</Name>
    111121    </ProjectReference>
    112122    <ProjectReference Include="..\..\HeuristicLab.Core.Views\3.3\HeuristicLab.Core.Views-3.3.csproj">
  • trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/HeuristicLabProblemsTSPViewsPlugin.cs.frame

    r3107 r3151  
    2929  [PluginFile("HeuristicLab.Problems.TSP.Views-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Collections", "3.3")]
     31  [PluginDependency("HeuristicLab.Common.Resources", "3.2")]
    3132  [PluginDependency("HeuristicLab.Core", "3.3")]
    3233  [PluginDependency("HeuristicLab.Core.Views", "3.3")]
  • trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/TSPView.Designer.cs

    r2917 r3151  
    3333    protected override void Dispose(bool disposing) {
    3434      if (disposing) {
     35        if (tsplibImportDialog != null) tsplibImportDialog.Dispose();
    3536        if (components != null) components.Dispose();
    3637      }
     
    4546    /// </summary>
    4647    private void InitializeComponent() {
    47       this.openFileDialog = new System.Windows.Forms.OpenFileDialog();
    4848      this.importButton = new System.Windows.Forms.Button();
    4949      ((System.ComponentModel.ISupportInitialize)(this.errorProvider)).BeginInit();
     
    6363      //
    6464      this.descriptionTextBox.Size = new System.Drawing.Size(457, 20);
    65       //
    66       // openFileDialog
    67       //
    68       this.openFileDialog.DefaultExt = "tsp";
    69       this.openFileDialog.FileName = "tspdata";
    70       this.openFileDialog.Filter = "TSPLIB Files|*.tsp|All Files|*.*";
    71       this.openFileDialog.Title = "Import TSP Data";
    7265      //
    7366      // importButton
     
    10497    #endregion
    10598
    106     private System.Windows.Forms.OpenFileDialog openFileDialog;
    10799    private System.Windows.Forms.Button importButton;
    108100
  • trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/TSPView.cs

    r2998 r3151  
    3333  [Content(typeof(TSP), true)]
    3434  public sealed partial class TSPView : ProblemView {
     35    private TSPLIBImportDialog tsplibImportDialog;
     36
    3537    public new TSP Content {
    3638      get { return (TSP)base.Content; }
     
    6365
    6466    private void importButton_Click(object sender, System.EventArgs e) {
    65       if (openFileDialog.ShowDialog(this) == DialogResult.OK) {
     67      if (tsplibImportDialog == null) tsplibImportDialog = new TSPLIBImportDialog();
     68
     69      if (tsplibImportDialog.ShowDialog(this) == DialogResult.OK) {
    6670        try {
    67           Content.ImportFromTSPLIB(openFileDialog.FileName);
     71          if (tsplibImportDialog.Quality == null)
     72            Content.ImportFromTSPLIB(tsplibImportDialog.TSPFileName, tsplibImportDialog.TourFileName);
     73          else
     74            Content.ImportFromTSPLIB(tsplibImportDialog.TSPFileName, tsplibImportDialog.TourFileName, (double)tsplibImportDialog.Quality);
    6875        }
    6976        catch (Exception ex) {
  • trunk/sources/HeuristicLab.Problems.TSP/3.3/HeuristicLab.Problems.TSP-3.3.csproj

    r3107 r3151  
    8484  </ItemGroup>
    8585  <ItemGroup>
     86    <Compile Include="TSPLIBTourParser.cs" />
    8687    <Compile Include="Interfaces\ICoordinatesTSPSolutionsVisualizer.cs" />
    8788    <Compile Include="Interfaces\IPathCoordinatesTSPSolutionsVisualizer.cs" />
  • trunk/sources/HeuristicLab.Problems.TSP/3.3/TSP.cs

    r3147 r3151  
    8282      get { return BestKnownQualityParameter; }
    8383    }
     84    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
     85      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
     86    }
    8487    #endregion
    8588
     
    124127      get { return BestKnownQualityParameter.Value; }
    125128      set { BestKnownQualityParameter.Value = value; }
     129    }
     130    public Permutation BestKnownSolution {
     131      get { return BestKnownSolutionParameter.Value; }
     132      set { BestKnownSolutionParameter.Value = value; }
    126133    }
    127134    private List<IPermutationOperator> operators;
     
    145152      Parameters.Add(new OptionalValueParameter<ITSPSolutionsVisualizer>("Visualizer", "The operator which should be used to visualize TSP solutions.", visualizer));
    146153      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this TSP instance."));
     154      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
    147155
    148156      creator.PermutationParameter.ActualName = "TSPTour";
     
    163171    }
    164172
    165     public void ImportFromTSPLIB(string filename) {
    166       TSPLIBParser parser = new TSPLIBParser(filename);
    167       parser.Parse();
    168       Name = parser.Name + " TSP (imported from TSPLIB)";
    169       Coordinates = new DoubleMatrix(parser.Vertices);
     173    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName) {
     174      TSPLIBParser tspParser = new TSPLIBParser(tspFileName);
     175      tspParser.Parse();
     176      Name = tspParser.Name + " TSP (imported from TSPLIB)";
     177      if (!string.IsNullOrEmpty(tspParser.Comment)) Description = tspParser.Comment;
     178      Coordinates = new DoubleMatrix(tspParser.Vertices);
     179      BestKnownQuality = null;
     180
     181      if (!string.IsNullOrEmpty(optimalTourFileName)) {
     182        TSPLIBTourParser tourParser = new TSPLIBTourParser(optimalTourFileName);
     183        tourParser.Parse();
     184        BestKnownSolution = new Permutation(tourParser.Tour);
     185      }
     186    }
     187    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName, double bestKnownQuality) {
     188      ImportFromTSPLIB(tspFileName, optimalTourFileName);
     189      BestKnownQuality = new DoubleValue(bestKnownQuality);
    170190    }
    171191
  • trunk/sources/HeuristicLab.Problems.TSP/3.3/TSPLIBParser.cs

    r2883 r3151  
    2626namespace HeuristicLab.Problems.TSP {
    2727  /// <summary>
    28   /// Parses a *.tsp file in the TSPLIB format and extracts its information about a TSP.
     28  /// Parses a *.tsp file in TSPLIB format and extracts its information about a TSP.
    2929  /// </summary>
    3030  public class TSPLIBParser {
     
    3232    private const int NAME = 1;
    3333    private const int TYPE = 2;
    34     private const int DIM = 3;
    35     private const int WEIGHTTYPE = 4;
    36     private const int NODETYPE = 5;
    37     private const int NODESECTION = 6;
     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;
    3839
    3940    private StreamReader source;
    4041
    41     private string myName;
     42    private string name;
    4243    /// <summary>
    4344    /// Gets the name of the parsed TSP.
    4445    /// </summary>
    4546    public string Name {
    46       get { return myName; }
    47     }
    48     private double[,] myVertices;
     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;
    4957    /// <summary>
    5058    /// Gets the vertices of the parsed TSP.
    5159    /// </summary>
    5260    public double[,] Vertices {
    53       get { return myVertices; }
    54     }
    55     private int myWeightType;
     61      get { return vertices; }
     62    }
     63    private int weightType;
    5664    /// <summary>
    5765    /// Gets the weight type of the parsed TSP.
    5866    /// </summary>
    5967    public int WeightType {
    60       get { return myWeightType; }
    61     }
    62 
    63     /// <summary>
    64     /// Initializes a new instance of <see cref="TSPParser"/> with the given <paramref name="path"/>.
    65     /// </summary>
    66     /// <exception cref="ArgumentException">Thrown when the input file name is not in TSP format (*.tsp)
     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)
    6775    /// </exception>
    6876    /// <param name="path">The path where the TSP is stored.</param>
    6977    public TSPLIBParser(String path) {
    7078      if (!path.EndsWith(".tsp"))
    71         throw new ArgumentException("Input file name has to be in TSP format (*.tsp)");
     79        throw new ArgumentException("Input file has to be a TSPLIB TSP file (*.tsp).");
    7280
    7381      source = new StreamReader(path);
    74       myName = path;
    75       myVertices = null;
    76       myWeightType = -1;
    77     }
    78 
    79     /// <summary>
    80     /// Reads the TSP file and parses the elements.
    81     /// </summary>
    82     /// <exception cref="InvalidDataException">Thrown when file contains unknown (edge) types.</exception>
     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>
    8392    public void Parse() {
    8493      int section = -1;
     
    100109              typeIsChecked = true;
    101110              break;
     111            case COMMENT:
     112              ReadComment(str);
     113              break;
    102114            case DIM:
    103115              InitVerticesArray(str);
     
    118130
    119131      if (!(typeIsChecked && weightTypeIsChecked))
    120         throw new InvalidDataException("File contains unknown (edge) types");
     132        throw new InvalidDataException("Input file does not contain type or edge weight type information.");
    121133    }
    122134
     
    136148      if (token.Equals("type", StringComparison.OrdinalIgnoreCase))
    137149        return TYPE;
     150      if (token.Equals("comment", StringComparison.OrdinalIgnoreCase))
     151        return COMMENT;
    138152      if (token.Equals("dimension", StringComparison.OrdinalIgnoreCase))
    139153        return DIM;
     
    150164    private void ReadName(string str) {
    151165      string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
    152       myName = tokens[tokens.Length - 1].Trim();
     166      name = tokens[tokens.Length - 1].Trim();
    153167    }
    154168
     
    158172      string type = tokens[tokens.Length - 1].Trim();
    159173      if (!type.Equals("tsp", StringComparison.OrdinalIgnoreCase))
    160         throw new InvalidDataException("Input data format is not \"TSP\"");
     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();
    161180    }
    162181
     
    166185
    167186      int dim = Int32.Parse(dimension);
    168       myVertices = new double[dim, 2];
     187      vertices = new double[dim, 2];
    169188    }
    170189
     
    174193
    175194      if (type.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
    176         myWeightType = 0;
     195        weightType = 0;
    177196      else if (type.Equals("geo", StringComparison.OrdinalIgnoreCase))
    178         myWeightType = 1;
     197        weightType = 1;
    179198      else
    180         throw new InvalidDataException("Unsupported type of edge weights");
     199        throw new InvalidDataException("Input file contains an unsupported edge weight type (only \"EUC_2D\" and \"GEO\" are supported).");
    181200    }
    182201
     
    186205
    187206      if (!type.Equals("twod_coords", StringComparison.OrdinalIgnoreCase))
    188         throw new InvalidDataException("Unsupported node type");
     207        throw new InvalidDataException("Input file contains an unsupported node coordinates type (only \"TWOD_COORDS\" is supported).");
    189208    }
    190209
    191210    private void ReadVertices() {
    192       if (myVertices == null)
    193         throw new InvalidDataException("Dimension not found");
    194 
    195       for (int i = 0; i < (myVertices.Length / 2); i++) {
     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++) {
    196215        string str = source.ReadLine();
    197216        string[] tokens = str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
    198217
    199218        if (tokens.Length != 3)
    200           throw new InvalidDataException("Invalid node format");
     219          throw new InvalidDataException("Input file contains invalid node coordinates.");
    201220
    202221        CultureInfo culture = new CultureInfo("en-US");
    203         myVertices[i, 0] = Double.Parse(tokens[1], culture.NumberFormat);
    204         myVertices[i, 1] = Double.Parse(tokens[2], culture.NumberFormat);
     222        vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
     223        vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
    205224      }
    206225    }
Note: See TracChangeset for help on using the changeset viewer.