source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSPLIBInstanceProvider.cs @ 13202

using System;
using System.Collections.Generic;
using System.IO;
using System.IO.Compression;
using System.Linq;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Problems.Instances.TSPLIB;

namespace HeuristicLab.Problems.PTSP {
  public class PTSPLIBInstanceProvider : TSPLIBInstanceProvider<PTSPData> {

    public override string Name {
      get { return "(P)TSPLIB (symmetric TSP)"; }
    }

    public override string Description {
      get { return "Adaption of the Traveling Salesman Problem Library for probabilistic instances"; }
    }

    protected override string FileExtension { get { return "tsp"; } }

    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
      Dictionary<string, string> solutions = new Dictionary<string, string>();
      var solutionsArchiveName = GetResourceName(FileExtension + @"\.opt\.tour\.zip");
      if (!String.IsNullOrEmpty(solutionsArchiveName)) {
        using (var solutionsZipFile = new ZipArchive(typeof(TSPLIBTSPInstanceProvider).Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) {
          foreach (var entry in solutionsZipFile.Entries)
            solutions.Add(entry.Name.Substring(0, entry.Name.Length - ".opt.tour".Length) + "." + FileExtension, entry.Name);
        }
      }
      var instanceArchiveName = GetResourceName(FileExtension + @"\.zip");
      if (String.IsNullOrEmpty(instanceArchiveName)) yield break;

      using (var instanceStream = new ZipArchive(typeof(TSPLIBTSPInstanceProvider).Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
        foreach (var entry in instanceStream.Entries.Select(x => x.Name).OrderBy(x => x)) {
          yield return new PTSPDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetInstanceDescription(), entry, solutions.ContainsKey(entry) ? solutions[entry] : String.Empty);
        }
      }
    }

    public override PTSPData LoadData(IDataDescriptor id) {
      var descriptor = (PTSPDataDescriptor)id;
      var instanceArchiveName = GetResourceName(FileExtension + @"\.zip");
      using (var instancesZipFile = new ZipArchive(typeof(TSPLIBTSPInstanceProvider).Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
        var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier);
        var stream = entry.Open();
        var parser = new TSPLIBParser(stream);
        var instance = LoadInstance(parser);

        if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) {
          var solutionsArchiveName = GetResourceName(FileExtension + @"\.opt\.tour\.zip");
          using (var solutionsZipFile = new ZipArchive(typeof(TSPLIBTSPInstanceProvider).Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) {
            entry = solutionsZipFile.GetEntry(descriptor.SolutionIdentifier);
            stream = entry.Open();
            parser = new TSPLIBParser(stream);
            LoadSolution(parser, instance);
          }
        }

        return instance;
      }
    }

    protected override PTSPData LoadInstance(TSPLIBParser parser) {
      parser.Parse();
      if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
      var instance = new PTSPData();
      instance.Dimension = parser.Dimension;
      instance.Coordinates = parser.Vertices ?? parser.DisplayVertices;
      instance.Distances = parser.Distances;
      switch (parser.EdgeWeightType) {
        case TSPLIBEdgeWeightTypes.ATT:
          instance.DistanceMeasure = DistanceMeasure.Att; break;
        case TSPLIBEdgeWeightTypes.CEIL_2D:
          instance.DistanceMeasure = DistanceMeasure.UpperEuclidean; break;
        case TSPLIBEdgeWeightTypes.EUC_2D:
          instance.DistanceMeasure = DistanceMeasure.RoundedEuclidean; break;
        case TSPLIBEdgeWeightTypes.EUC_3D:
          throw new InvalidDataException("3D coordinates are not supported.");
        case TSPLIBEdgeWeightTypes.EXPLICIT:
          instance.DistanceMeasure = DistanceMeasure.Direct; break;
        case TSPLIBEdgeWeightTypes.GEO:
          instance.DistanceMeasure = DistanceMeasure.Geo; break;
        case TSPLIBEdgeWeightTypes.MAN_2D:
          instance.DistanceMeasure = DistanceMeasure.Manhattan; break;
        case TSPLIBEdgeWeightTypes.MAN_3D:
          throw new InvalidDataException("3D coordinates are not supported.");
        case TSPLIBEdgeWeightTypes.MAX_2D:
          instance.DistanceMeasure = DistanceMeasure.Maximum; break;
        case TSPLIBEdgeWeightTypes.MAX_3D:
          throw new InvalidDataException("3D coordinates are not supported.");
        default:
          throw new InvalidDataException("The given edge weight is not supported by HeuristicLab.");
      }

      // use own hash function in case the implementation of String.GetHashCode() changes
      // ... and hope that System.Random doesn't change
      var random = new System.Random(Hash(parser.Name));
      instance.Probabilities = Enumerable.Range(0, parser.Dimension).Select(x => random.NextDouble() * 0.8 + 0.1).ToArray();
      instance.Name = parser.Name;
      instance.Description = parser.Comment
        + Environment.NewLine + Environment.NewLine
        + GetInstanceDescription();
      return instance;
    }

    protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
      // the TSP optimal tour isn't necessarily the PTSP optimal tour
    }

    public PTSPData LoadData(string tspFile, double? bestQuality) {
      var data = LoadInstance(new TSPLIBParser(tspFile));
      if (bestQuality.HasValue)
        data.BestKnownQuality = bestQuality.Value;
      return data;
    }

    private int Hash(string s) {
      var h = 3571;
      unchecked {
        for (var i = 0; i < s.Length; i++)
          h = h * 31 + s[i];
      }
      return h;
    }
  }

  internal class PTSPDataDescriptor : IDataDescriptor {
    public string Name { get; internal set; }
    public string Description { get; internal set; }

    internal string InstanceIdentifier { get; set; }
    internal string SolutionIdentifier { get; set; }

    internal PTSPDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
      this.Name = name;
      this.Description = description;
      this.InstanceIdentifier = instanceIdentifier;
      this.SolutionIdentifier = solutionIdentifier;
    }
  }
}