Changeset 3151

Timestamp:

03/21/10 23:55:23 (14 years ago)

Author:

swagner

Message:

Implemented import of optimal TSP solutions (#924).

Location:

trunk/sources

Files:

• HeuristicLab.Problems.TSP.Views/3.3/HeuristicLab.Problems.TSP.Views-3.3.csproj (modified) (2 diffs)
• HeuristicLab.Problems.TSP.Views/3.3/HeuristicLabProblemsTSPViewsPlugin.cs.frame (modified) (1 diff)
• HeuristicLab.Problems.TSP.Views/3.3/TSPLIBImportDialog.Designer.cs (added)
• HeuristicLab.Problems.TSP.Views/3.3/TSPLIBImportDialog.cs (added)
• HeuristicLab.Problems.TSP.Views/3.3/TSPView.Designer.cs (modified) (4 diffs)
• HeuristicLab.Problems.TSP.Views/3.3/TSPView.cs (modified) (2 diffs)
• HeuristicLab.Problems.TSP/3.3/HeuristicLab.Problems.TSP-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.TSP/3.3/TSP.cs (modified) (4 diffs)
• HeuristicLab.Problems.TSP/3.3/TSPLIBParser.cs (modified) (10 diffs)
• HeuristicLab.Problems.TSP/3.3/TSPLIBTourParser.cs (added)
• HeuristicLab.Problems.TSP/3.3/ch130.opt.tour (added)

trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/HeuristicLab.Problems.TSP.Views-3.3.csproj

@@ -92 +92 @@
     </Compile>
     <Compile Include="HeuristicLabProblemsTSPViewsPlugin.cs" />
+    <Compile Include="TSPLIBImportDialog.cs">
+      <SubType>Form</SubType>
+    </Compile>
+    <Compile Include="TSPLIBImportDialog.Designer.cs">
+      <DependentUpon>TSPLIBImportDialog.cs</DependentUpon>
+    </Compile>
     <Compile Include="TSPView.cs">
       <SubType>UserControl</SubType>
@@ -109 +115 @@
       <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project>
       <Name>HeuristicLab.Collections-3.3</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Common.Resources\3.2\HeuristicLab.Common.Resources-3.2.csproj">
+      <Project>{0E27A536-1C4A-4624-A65E-DC4F4F23E3E1}</Project>
+      <Name>HeuristicLab.Common.Resources-3.2</Name>
     </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Core.Views\3.3\HeuristicLab.Core.Views-3.3.csproj">

trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/HeuristicLabProblemsTSPViewsPlugin.cs.frame

@@ -29 +29 @@
   [PluginFile("HeuristicLab.Problems.TSP.Views-3.3.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Collections", "3.3")]
+  [PluginDependency("HeuristicLab.Common.Resources", "3.2")]
   [PluginDependency("HeuristicLab.Core", "3.3")]
   [PluginDependency("HeuristicLab.Core.Views", "3.3")]

trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/TSPView.Designer.cs

@@ -33 +33 @@
     protected override void Dispose(bool disposing) {
       if (disposing) {
+        if (tsplibImportDialog != null) tsplibImportDialog.Dispose();
         if (components != null) components.Dispose();
       }
@@ -45 +46 @@
     /// </summary>
     private void InitializeComponent() {
-      this.openFileDialog = new System.Windows.Forms.OpenFileDialog();
       this.importButton = new System.Windows.Forms.Button();
       ((System.ComponentModel.ISupportInitialize)(this.errorProvider)).BeginInit();
@@ -63 +63 @@
       // 
       this.descriptionTextBox.Size = new System.Drawing.Size(457, 20);
-      // 
-      // openFileDialog
-      // 
-      this.openFileDialog.DefaultExt = "tsp";
-      this.openFileDialog.FileName = "tspdata";
-      this.openFileDialog.Filter = "TSPLIB Files|*.tsp|All Files|*.*";
-      this.openFileDialog.Title = "Import TSP Data";
       // 
       // importButton
@@ -104 +97 @@
     #endregion
 
-    private System.Windows.Forms.OpenFileDialog openFileDialog;
     private System.Windows.Forms.Button importButton;
 

trunk/sources/HeuristicLab.Problems.TSP.Views/3.3/TSPView.cs

@@ -33 +33 @@
   [Content(typeof(TSP), true)]
   public sealed partial class TSPView : ProblemView {
+    private TSPLIBImportDialog tsplibImportDialog;
+
     public new TSP Content {
       get { return (TSP)base.Content; }
@@ -63 +65 @@
 
     private void importButton_Click(object sender, System.EventArgs e) {
-      if (openFileDialog.ShowDialog(this) == DialogResult.OK) {
+      if (tsplibImportDialog == null) tsplibImportDialog = new TSPLIBImportDialog();
+
+      if (tsplibImportDialog.ShowDialog(this) == DialogResult.OK) {
         try {
-          Content.ImportFromTSPLIB(openFileDialog.FileName);
+          if (tsplibImportDialog.Quality == null)
+            Content.ImportFromTSPLIB(tsplibImportDialog.TSPFileName, tsplibImportDialog.TourFileName);
+          else
+            Content.ImportFromTSPLIB(tsplibImportDialog.TSPFileName, tsplibImportDialog.TourFileName, (double)tsplibImportDialog.Quality);
         }
         catch (Exception ex) {

trunk/sources/HeuristicLab.Problems.TSP/3.3/HeuristicLab.Problems.TSP-3.3.csproj

@@ -84 +84 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="TSPLIBTourParser.cs" />
     <Compile Include="Interfaces\ICoordinatesTSPSolutionsVisualizer.cs" />
     <Compile Include="Interfaces\IPathCoordinatesTSPSolutionsVisualizer.cs" />

trunk/sources/HeuristicLab.Problems.TSP/3.3/TSP.cs

@@ -82 +82 @@
       get { return BestKnownQualityParameter; }
     }
+    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
+      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
+    }
     #endregion
 
@@ -124 +127 @@
       get { return BestKnownQualityParameter.Value; }
       set { BestKnownQualityParameter.Value = value; }
+    }
+    public Permutation BestKnownSolution {
+      get { return BestKnownSolutionParameter.Value; }
+      set { BestKnownSolutionParameter.Value = value; }
     }
     private List<IPermutationOperator> operators;
@@ -145 +152 @@
       Parameters.Add(new OptionalValueParameter<ITSPSolutionsVisualizer>("Visualizer", "The operator which should be used to visualize TSP solutions.", visualizer));
       Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this TSP instance."));
+      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
 
       creator.PermutationParameter.ActualName = "TSPTour";
@@ -163 +171 @@
     }
 
-    public void ImportFromTSPLIB(string filename) {
-      TSPLIBParser parser = new TSPLIBParser(filename);
-      parser.Parse();
-      Name = parser.Name + " TSP (imported from TSPLIB)";
-      Coordinates = new DoubleMatrix(parser.Vertices);
+    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName) {
+      TSPLIBParser tspParser = new TSPLIBParser(tspFileName);
+      tspParser.Parse();
+      Name = tspParser.Name + " TSP (imported from TSPLIB)";
+      if (!string.IsNullOrEmpty(tspParser.Comment)) Description = tspParser.Comment;
+      Coordinates = new DoubleMatrix(tspParser.Vertices);
+      BestKnownQuality = null;
+
+      if (!string.IsNullOrEmpty(optimalTourFileName)) {
+        TSPLIBTourParser tourParser = new TSPLIBTourParser(optimalTourFileName);
+        tourParser.Parse();
+        BestKnownSolution = new Permutation(tourParser.Tour);
+      }
+    }
+    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName, double bestKnownQuality) {
+      ImportFromTSPLIB(tspFileName, optimalTourFileName);
+      BestKnownQuality = new DoubleValue(bestKnownQuality);
     }
 

trunk/sources/HeuristicLab.Problems.TSP/3.3/TSPLIBParser.cs

@@ -26 +26 @@
 namespace HeuristicLab.Problems.TSP {
   /// <summary>
-  /// Parses a *.tsp file in the TSPLIB format and extracts its information about a TSP.
+  /// Parses a *.tsp file in TSPLIB format and extracts its information about a TSP.
   /// </summary>
   public class TSPLIBParser {
@@ -32 +32 @@
     private const int NAME = 1;
     private const int TYPE = 2;
-    private const int DIM = 3;
-    private const int WEIGHTTYPE = 4;
-    private const int NODETYPE = 5;
-    private const int NODESECTION = 6;
+    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 myName;
+    private string name;
     /// <summary>
     /// Gets the name of the parsed TSP.
     /// </summary>
     public string Name {
-      get { return myName; }
-    }
-    private double[,] myVertices;
+      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 myVertices; }
-    }
-    private int myWeightType;
+      get { return vertices; }
+    }
+    private int weightType;
     /// <summary>
     /// Gets the weight type of the parsed TSP.
     /// </summary>
     public int WeightType {
-      get { return myWeightType; }
-    }
-
-    /// <summary>
-    /// Initializes a new instance of <see cref="TSPParser"/> with the given <paramref name="path"/>.
-    /// </summary>
-    /// <exception cref="ArgumentException">Thrown when the input file name is not in TSP format (*.tsp)
+      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 name has to be in TSP format (*.tsp)");
+        throw new ArgumentException("Input file has to be a TSPLIB TSP file (*.tsp).");
 
       source = new StreamReader(path);
-      myName = path;
-      myVertices = null;
-      myWeightType = -1;
-    }
-
-    /// <summary>
-    /// Reads the TSP file and parses the elements.
-    /// </summary>
-    /// <exception cref="InvalidDataException">Thrown when file contains unknown (edge) types.</exception>
+      name = path;
+      comment = string.Empty;
+      vertices = null;
+      weightType = -1;
+    }
+
+    /// <summary>
+    /// Reads the TSPLIB TSP 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;
@@ -100 +109 @@
               typeIsChecked = true;
               break;
+            case COMMENT:
+              ReadComment(str);
+              break;
             case DIM:
               InitVerticesArray(str);
@@ -118 +130 @@
 
       if (!(typeIsChecked && weightTypeIsChecked))
-        throw new InvalidDataException("File contains unknown (edge) types");
+        throw new InvalidDataException("Input file does not contain type or edge weight type information.");
     }
 
@@ -136 +148 @@
       if (token.Equals("type", StringComparison.OrdinalIgnoreCase))
         return TYPE;
+      if (token.Equals("comment", StringComparison.OrdinalIgnoreCase))
+        return COMMENT;
       if (token.Equals("dimension", StringComparison.OrdinalIgnoreCase))
         return DIM;
@@ -150 +164 @@
     private void ReadName(string str) {
       string[] tokens = str.Split(new string[] { ":" }, StringSplitOptions.None);
-      myName = tokens[tokens.Length - 1].Trim();
+      name = tokens[tokens.Length - 1].Trim();
     }
 
@@ -158 +172 @@
       string type = tokens[tokens.Length - 1].Trim();
       if (!type.Equals("tsp", StringComparison.OrdinalIgnoreCase))
-        throw new InvalidDataException("Input data format is not \"TSP\"");
+        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();
     }
 
@@ -166 +185 @@
 
       int dim = Int32.Parse(dimension);
-      myVertices = new double[dim, 2];
+      vertices = new double[dim, 2];
     }
 
@@ -174 +193 @@
 
       if (type.Equals("euc_2d", StringComparison.OrdinalIgnoreCase))
-        myWeightType = 0;
+        weightType = 0;
       else if (type.Equals("geo", StringComparison.OrdinalIgnoreCase))
-        myWeightType = 1;
+        weightType = 1;
       else
-        throw new InvalidDataException("Unsupported type of edge weights");
+        throw new InvalidDataException("Input file contains an unsupported edge weight type (only \"EUC_2D\" and \"GEO\" are supported).");
     }
 
@@ -186 +205 @@
 
       if (!type.Equals("twod_coords", StringComparison.OrdinalIgnoreCase))
-        throw new InvalidDataException("Unsupported node type");
+        throw new InvalidDataException("Input file contains an unsupported node coordinates type (only \"TWOD_COORDS\" is supported).");
     }
 
     private void ReadVertices() {
-      if (myVertices == null)
-        throw new InvalidDataException("Dimension not found");
-
-      for (int i = 0; i < (myVertices.Length / 2); i++) {
+      if (vertices == null)
+        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("Invalid node format");
+          throw new InvalidDataException("Input file contains invalid node coordinates.");
 
         CultureInfo culture = new CultureInfo("en-US");
-        myVertices[i, 0] = Double.Parse(tokens[1], culture.NumberFormat);
-        myVertices[i, 1] = Double.Parse(tokens[2], culture.NumberFormat);
+        vertices[i, 0] = double.Parse(tokens[1], culture.NumberFormat);
+        vertices[i, 1] = double.Parse(tokens[2], culture.NumberFormat);
       }
     }