source: branches/2457_ExpertSystem/HeuristicLab.Problems.Instances.QAPLIB/3.3/OneSizeInstanceProvider.cs @ 15820

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace HeuristicLab.Problems.Instances.QAPLIB {
  public class OneSizeInstanceProvider : ProblemInstanceProvider<QAPData> {
    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
      var drezner = new DreznerQAPInstanceProvider();
      foreach (var desc in drezner.GetDataDescriptors()) {
        var dim = int.Parse(Regex.Match(desc.Name, "dre(?<g>\\d+)").Groups["g"].Value);
        if (dim < 25) continue;
        yield return new OneSizeDataDescriptor(desc.Name + (dim == 25 ? "" : "-25"), desc.Description, drezner, desc);
      }
      // Microarray instances are all greater than 25 dimensions
      var microarray = new MicroarrayQAPInstanceProvider();
      foreach (var desc in microarray.GetDataDescriptors()) {
        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, microarray, desc);
      }
      var qaplib = new QAPLIBInstanceProvider();
      foreach (var desc in qaplib.GetDataDescriptors()) {
        var instance = qaplib.LoadData(desc);
        if (instance.Dimension < 25) continue;
        yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == 25 ? "" : "-25"), desc.Description, qaplib, desc);
      }
      // Taillard's instances are basically from the same distribution
      // to avoid over-representation in the set only the tai27e are taken and reduced to 25 dimension
      var taillard = new TaillardQAPInstanceProvider();
      foreach (var desc in taillard.GetDataDescriptors()) {
        if (!desc.Name.StartsWith("tai27e")) continue;
        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, taillard, desc);
      }
    }

    public override QAPData LoadData(IDataDescriptor descriptor) {
      var desc = (OneSizeDataDescriptor)descriptor;
      var data = desc.ActualProvider.LoadData(desc.ActualDescriptor);
      data.BestKnownAssignment = null;
      data.BestKnownQuality = null;
      if (data.Dimension <= 25) {
        return data;
      }
      var rand = new Random(data.Dimension);

      var tmp = Enumerable.Range(0, data.Dimension).ToArray();
      Shuffle(tmp, rand);
      var throwAway = new bool[data.Dimension];
      foreach (var t in tmp.Take(data.Dimension - 25))
        throwAway[t] = true;

      var weights = new double[25, 25];
      var distances = new double[25, 25];
      var k = 0;
      for (var i = 0; i < data.Dimension; i++) {
        if (throwAway[i]) continue;
        var h = 0;
        for (var j = 0; j < data.Dimension; j++) {
          if (throwAway[j]) continue;
          weights[k, h] = data.Weights[i, j];
          distances[k, h] = data.Distances[i, j];
          h++;
        }
        k++;
      }

      data.Weights = weights;
      data.Distances = distances;
      data.BestKnownAssignment = null;
      data.BestKnownQuality = null;
      data.Dimension = 25;
      data.Name += "-25";
      data.Description += " (reduced to 25 dimensions)";

      return data;
    }

    public override string Name { get { return "One Size"; } }
    public override string Description { get { return string.Empty; } }
    public override Uri WebLink { get { return null; } }
    public override string ReferencePublication { get { return string.Empty; } }
    
    private static void Shuffle(int[] p, Random random) {
      for (var i = p.Length - 1; i > 0; i--) {
        var swapIndex = random.Next(i + 1);
        var h = p[swapIndex];
        p[swapIndex] = p[i];
        p[i] = h;
      }
    }
  }
}