Changeset 14471 for branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/GcolInstanceProvider.cs

Timestamp:

12/09/16 15:56:22 (7 years ago)

Author:

abeham

Message:

#2701:

• Updated GraphColoringProblem and Problems.Instances
  • Added new fitness function from literature
  • Added DIMACS benchmark instances
• Updated LinearLinkageEncoding
  • Added HammingSimilarityCalculator

Location:

branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS

Files:

• . (added)
• 3.3 (added)
• 3.3/GcolInstanceProvider.cs (copied) (copied from branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.QAPLIB/3.3/QAPLIBInstanceProvider.cs) (4 diffs)

branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/GcolInstanceProvider.cs

@@ -28 +28 @@
 using System.Text.RegularExpressions;
 
-namespace HeuristicLab.Problems.Instances.QAPLIB {
-  public class QAPLIBInstanceProvider : ProblemInstanceProvider<QAPData> {
-    #region Reversed instances
-    // These instances specified their best known solution in the wrong order
-    protected virtual HashSet<string> ReversedSolutions {
-      get {
-        return new HashSet<string>(new string[] {
-              "bur26a",
-              "bur26b",
-              "bur26c",
-              "bur26d",
-              "bur26e",
-              "bur26f",
-              "bur26g",
-              "bur26h",
-              "chr12a",
-              "chr12b",
-              "chr12c",
-              "chr15a",
-              "chr15b",
-              "chr15c",
-              "chr18a",
-              "chr18b",
-              "chr20a",
-              "chr20b",
-              "chr20c",
-              "chr22a",
-              "chr22b",
-              "chr25a",
-              "esc16a",
-              "esc16b",
-              "esc16c",
-              "esc16d",
-              "esc16e",
-              "esc16g",
-              "esc16h",
-              "esc16i",
-              "esc16j",
-              "esc32a",
-              "esc32b",
-              "esc32c",
-              "esc32d",
-              "esc32e",
-              "esc32f",
-              "esc32g",
-              "esc32h",
-              "had12",
-              "had14",
-              "had16",
-              "had18",
-              "had20",
-              "kra32",
-              "lipa20a",
-              "lipa30a",
-              "lipa40a",
-              "lipa50a",
-              "lipa60a",
-              "lipa70a",
-              "lipa80a",
-              "lipa90a",
-              "nug12",
-              "nug14",
-              "nug15",
-              "nug16a",
-              "nug16b",
-              "nug17",
-              "nug18",
-              "nug20",
-              "nug21",
-              "nug22",
-              "nug24",
-              "nug25",
-              "nug27",
-              "nug28",
-              "rou12",
-              "rou15",
-              "rou20",
-              "scr12",
-              "scr15",
-              "scr20",
-              "sko100a",
-              "sko100b",
-              "sko100c",
-              "sko100d",
-              "sko100e",
-              "sko100f",
-              "sko49",
-              "sko81",
-              "sko90",
-              "ste36a",
-              "ste36b",
-              "tai100a",
-              "tai100b",
-              "tai12a",
-              "tai12b",
-              "tai150b",
-              "tai15a",
-              "tai15b",
-              "tai17a",
-              "tai20a",
-              "tai20b",
-              "tai256c",
-              "tai25a",
-              "tai25b",
-              "tai30a",
-              "tai30b",
-              "tai35a",
-              "tai35b",
-              "tai40a",
-              "tai40b",
-              "tai50a",
-              "tai50b",
-              "tai60a",
-              "tai60b",
-              "tai64c",
-              "tai80a",
-              "tai80b",
-              "wil100"
-        });
-      }
-    }
-    #endregion
+namespace HeuristicLab.Problems.Instances.DIMACS {
+  public class GcolInstanceProvider : ProblemInstanceProvider<GCPData> {
 
     public override string Name {
-      get { return "QAPLIB"; }
+      get { return "DIMACS Graph Coloring"; }
     }
 
     public override string Description {
-      get { return "Quadratic Assignment Problem Library"; }
+      get { return "Graph Coloring problem instance library"; }
     }
 
     public override Uri WebLink {
-      get { return new Uri("http://www.seas.upenn.edu/qaplib/"); }
+      get { return new Uri("https://turing.cs.hbg.psu.edu/txn131/graphcoloring.html"); }
     }
 
     public override string ReferencePublication {
       get {
-        return @"R. E. Burkard, S. E. Karisch, and F. Rendl. 1997.
-QAPLIB - A Quadratic Assignment Problem Library.
-Journal of Global Optimization, 10, pp. 391-403.";
+        return string.Empty;
       }
     }
 
-    protected virtual string FileName { get { return "qap"; } }
+    protected virtual string FileName { get { return "col"; } }
 
     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
-      Dictionary<string, string> solutions = new Dictionary<string, string>();
-      var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
-      if (!String.IsNullOrEmpty(solutionsArchiveName)) {
-        using (var solutionsZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) {
-          foreach (var entry in solutionsZipFile.Entries)
-            solutions.Add(Path.GetFileNameWithoutExtension(entry.Name) + ".dat", entry.Name);
-        }
-      }
-      var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
+      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
       if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
 
       using (var instanceStream = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
         foreach (var entry in instanceStream.Entries.Select(x => x.Name).OrderBy(x => x)) {
-          yield return new QAPLIBDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry, solutions.ContainsKey(entry) ? solutions[entry] : String.Empty);
+          yield return new GcolDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry);
         }
       }
     }
 
-    public override QAPData LoadData(IDataDescriptor id) {
-      var descriptor = (QAPLIBDataDescriptor)id;
-      var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
+    public override GCPData LoadData(IDataDescriptor id) {
+      var descriptor = (GcolDataDescriptor)id;
+      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
       using (var instancesZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
         var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier);
 
         using (var stream = entry.Open()) {
-          var parser = new QAPLIBParser();
+          var parser = new Parser();
           parser.Parse(stream);
           var instance = Load(parser);
           instance.Name = id.Name;
           instance.Description = id.Description;
-
-          if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) {
-            var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
-            using (var solutionsZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) {
-              entry = solutionsZipFile.GetEntry(descriptor.SolutionIdentifier);
-              using (var solStream = entry.Open()) {
-                var slnParser = new QAPLIBSolutionParser();
-                slnParser.Parse(solStream, true);
-                if (slnParser.Error != null) throw slnParser.Error;
-
-                int[] assignment = slnParser.Assignment;
-                if (assignment != null && ReversedSolutions.Contains(instance.Name)) {
-                  assignment = (int[])slnParser.Assignment.Clone();
-                  for (int i = 0; i < assignment.Length; i++)
-                    assignment[slnParser.Assignment[i]] = i;
-                }
-                instance.BestKnownAssignment = assignment;
-                instance.BestKnownQuality = slnParser.Quality;
-              }
-            }
-          }
+          int bestknown;
+          if (bkq.TryGetValue(instance.Name, out bestknown))
+            instance.BestKnownColors = bestknown;
           return instance;
         }
@@ -233 +85 @@
       get { return true; }
     }
-    public override QAPData ImportData(string path) {
-      var parser = new QAPLIBParser();
+    public override GCPData ImportData(string path) {
+      var parser = new Parser();
       parser.Parse(path);
       var instance = Load(parser);
@@ -242 +94 @@
     }
 
-    private QAPData Load(QAPLIBParser parser) {
-      var instance = new QAPData();
-      instance.Dimension = parser.Size;
-      instance.Distances = parser.Distances;
-      instance.Weights = parser.Weights;
+    private GCPData Load(Parser parser) {
+      var instance = new GCPData();
+      instance.Nodes = parser.Nodes;
+      var adjacencies = new int[parser.Edges, 2];
+      var i = 0;
+      foreach (var a in parser.AdjacencyList) {
+        adjacencies[i, 0] = a.Item1 - 1;
+        adjacencies[i, 1] = a.Item2 - 1;
+        i++;
+      }
+      instance.Adjacencies = adjacencies;
       return instance;
     }
@@ -258 +116 @@
               .Where(x => Regex.Match(x, @".*\.Data\." + fileName).Success).SingleOrDefault();
     }
+
+    private Dictionary<string, int> bkq = new Dictionary<string, int> {
+      { "fpsol2.i.1", 65 },
+      { "fpsol2.i.2", 30 },
+      { "fpsol2.i.3", 30 },
+      { "inithx.i.1", 54 },
+      { "inithx.i.2", 31 },
+      { "inithx.i.3", 31 },
+      { "le450_5a", 5 },
+      { "le450_5b", 5 },
+      { "le450_5c", 5 },
+      { "le450_5d", 5 },
+      { "le450_15a", 15 },
+      { "le450_15b", 15 },
+      { "le450_15c", 15 },
+      { "le450_15d", 15 },
+      { "le450_25a", 25 },
+      { "le450_25b", 25 },
+      { "le450_25c", 25 },
+      { "le450_25d", 25 },
+      { "mulsol.i.1", 49 },
+      { "mulsol.i.2", 31 },
+      { "mulsol.i.3", 31 },
+      { "mulsol.i.4", 31 },
+      { "mulsol.i.5", 31 },
+      { "zeroin.i.1", 49 },
+      { "zeroin.i.2", 30 },
+      { "zeroin.i.3", 30 },
+      { "anna", 11 },
+      { "david", 11 },
+      { "homer", 13 },
+      { "huck", 11 },
+      { "jean", 10 },
+      { "games120", 9 },
+      { "miles250", 8 },
+      { "miles500", 20 },
+      { "miles750", 31 },
+      { "miles1000", 42 },
+      { "miles1500", 73 },
+      { "queen5_5", 5 },
+      { "queen6_6", 7 },
+      { "queen7_7", 7 },
+      { "queen8_8", 9 },
+      { "queen8_12", 12 },
+      { "queen9_9", 10 },
+      { "queen11_11", 11 },
+      { "queen13_13", 13 },
+      { "myciel3", 4 },
+      { "myciel4", 5 },
+      { "myciel5", 6 },
+      { "myciel6", 7 },
+      { "myciel7", 8 },
+      { "mugg88_1", 4 },
+      { "mugg88_25", 4 },
+      { "mugg100_1", 4 },
+      { "mugg100_25", 4 },
+      { "1-Insertions_4", 4 },
+      { "2-Insertions_3", 4 },
+      { "2-Insertions_4", 4 },
+      { "3-Insertions_3", 4 },
+      { "4-Insertions_3", 3 },
+      { "qg.order30", 30 },
+      { "qg.order40", 40 },
+      { "qg.order60", 60 },
+      { "qg.order100", 100 }
+    };
   }
 }