- Timestamp:
- 12/09/16 15:56:22 (8 years ago)
- Location:
- branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS
- Files:
-
- 11 added
- 3 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/GcolDataDescriptor.cs
r14429 r14471 20 20 #endregion 21 21 22 namespace HeuristicLab.Problems.Instances. QAPLIB{23 internal class QAPLIBDataDescriptor : IDataDescriptor {22 namespace HeuristicLab.Problems.Instances.DIMACS { 23 internal class GcolDataDescriptor : IDataDescriptor { 24 24 public string Name { get; internal set; } 25 25 public string Description { get; internal set; } 26 26 27 27 internal string InstanceIdentifier { get; set; } 28 internal string SolutionIdentifier { get; set; }29 28 30 internal QAPLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {29 internal GcolDataDescriptor(string name, string description, string instanceIdentifier) { 31 30 this.Name = name; 32 31 this.Description = description; 33 32 this.InstanceIdentifier = instanceIdentifier; 34 this.SolutionIdentifier = solutionIdentifier;35 33 } 36 34 } -
branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/GcolInstanceProvider.cs
r14429 r14471 28 28 using System.Text.RegularExpressions; 29 29 30 namespace HeuristicLab.Problems.Instances.QAPLIB { 31 public class QAPLIBInstanceProvider : ProblemInstanceProvider<QAPData> { 32 #region Reversed instances 33 // These instances specified their best known solution in the wrong order 34 protected virtual HashSet<string> ReversedSolutions { 35 get { 36 return new HashSet<string>(new string[] { 37 "bur26a", 38 "bur26b", 39 "bur26c", 40 "bur26d", 41 "bur26e", 42 "bur26f", 43 "bur26g", 44 "bur26h", 45 "chr12a", 46 "chr12b", 47 "chr12c", 48 "chr15a", 49 "chr15b", 50 "chr15c", 51 "chr18a", 52 "chr18b", 53 "chr20a", 54 "chr20b", 55 "chr20c", 56 "chr22a", 57 "chr22b", 58 "chr25a", 59 "esc16a", 60 "esc16b", 61 "esc16c", 62 "esc16d", 63 "esc16e", 64 "esc16g", 65 "esc16h", 66 "esc16i", 67 "esc16j", 68 "esc32a", 69 "esc32b", 70 "esc32c", 71 "esc32d", 72 "esc32e", 73 "esc32f", 74 "esc32g", 75 "esc32h", 76 "had12", 77 "had14", 78 "had16", 79 "had18", 80 "had20", 81 "kra32", 82 "lipa20a", 83 "lipa30a", 84 "lipa40a", 85 "lipa50a", 86 "lipa60a", 87 "lipa70a", 88 "lipa80a", 89 "lipa90a", 90 "nug12", 91 "nug14", 92 "nug15", 93 "nug16a", 94 "nug16b", 95 "nug17", 96 "nug18", 97 "nug20", 98 "nug21", 99 "nug22", 100 "nug24", 101 "nug25", 102 "nug27", 103 "nug28", 104 "rou12", 105 "rou15", 106 "rou20", 107 "scr12", 108 "scr15", 109 "scr20", 110 "sko100a", 111 "sko100b", 112 "sko100c", 113 "sko100d", 114 "sko100e", 115 "sko100f", 116 "sko49", 117 "sko81", 118 "sko90", 119 "ste36a", 120 "ste36b", 121 "tai100a", 122 "tai100b", 123 "tai12a", 124 "tai12b", 125 "tai150b", 126 "tai15a", 127 "tai15b", 128 "tai17a", 129 "tai20a", 130 "tai20b", 131 "tai256c", 132 "tai25a", 133 "tai25b", 134 "tai30a", 135 "tai30b", 136 "tai35a", 137 "tai35b", 138 "tai40a", 139 "tai40b", 140 "tai50a", 141 "tai50b", 142 "tai60a", 143 "tai60b", 144 "tai64c", 145 "tai80a", 146 "tai80b", 147 "wil100" 148 }); 149 } 150 } 151 #endregion 30 namespace HeuristicLab.Problems.Instances.DIMACS { 31 public class GcolInstanceProvider : ProblemInstanceProvider<GCPData> { 152 32 153 33 public override string Name { 154 get { return " QAPLIB"; }34 get { return "DIMACS Graph Coloring"; } 155 35 } 156 36 157 37 public override string Description { 158 get { return " Quadratic Assignment Problem Library"; }38 get { return "Graph Coloring problem instance library"; } 159 39 } 160 40 161 41 public override Uri WebLink { 162 get { return new Uri("http ://www.seas.upenn.edu/qaplib/"); }42 get { return new Uri("https://turing.cs.hbg.psu.edu/txn131/graphcoloring.html"); } 163 43 } 164 44 165 45 public override string ReferencePublication { 166 46 get { 167 return @"R. E. Burkard, S. E. Karisch, and F. Rendl. 1997. 168 QAPLIB - A Quadratic Assignment Problem Library. 169 Journal of Global Optimization, 10, pp. 391-403."; 47 return string.Empty; 170 48 } 171 49 } 172 50 173 protected virtual string FileName { get { return " qap"; } }51 protected virtual string FileName { get { return "col"; } } 174 52 175 53 public override IEnumerable<IDataDescriptor> GetDataDescriptors() { 176 Dictionary<string, string> solutions = new Dictionary<string, string>(); 177 var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip"); 178 if (!String.IsNullOrEmpty(solutionsArchiveName)) { 179 using (var solutionsZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) { 180 foreach (var entry in solutionsZipFile.Entries) 181 solutions.Add(Path.GetFileNameWithoutExtension(entry.Name) + ".dat", entry.Name); 182 } 183 } 184 var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip"); 54 var instanceArchiveName = GetResourceName(FileName + @"\.zip"); 185 55 if (String.IsNullOrEmpty(instanceArchiveName)) yield break; 186 56 187 57 using (var instanceStream = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) { 188 58 foreach (var entry in instanceStream.Entries.Select(x => x.Name).OrderBy(x => x)) { 189 yield return new QAPLIBDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry, solutions.ContainsKey(entry) ? solutions[entry] : String.Empty);59 yield return new GcolDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry); 190 60 } 191 61 } 192 62 } 193 63 194 public override QAPData LoadData(IDataDescriptor id) {195 var descriptor = ( QAPLIBDataDescriptor)id;196 var instanceArchiveName = GetResourceName(FileName + @"\. dat\.zip");64 public override GCPData LoadData(IDataDescriptor id) { 65 var descriptor = (GcolDataDescriptor)id; 66 var instanceArchiveName = GetResourceName(FileName + @"\.zip"); 197 67 using (var instancesZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) { 198 68 var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier); 199 69 200 70 using (var stream = entry.Open()) { 201 var parser = new QAPLIBParser();71 var parser = new Parser(); 202 72 parser.Parse(stream); 203 73 var instance = Load(parser); 204 74 instance.Name = id.Name; 205 75 instance.Description = id.Description; 206 207 if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) { 208 var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip"); 209 using (var solutionsZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) { 210 entry = solutionsZipFile.GetEntry(descriptor.SolutionIdentifier); 211 using (var solStream = entry.Open()) { 212 var slnParser = new QAPLIBSolutionParser(); 213 slnParser.Parse(solStream, true); 214 if (slnParser.Error != null) throw slnParser.Error; 215 216 int[] assignment = slnParser.Assignment; 217 if (assignment != null && ReversedSolutions.Contains(instance.Name)) { 218 assignment = (int[])slnParser.Assignment.Clone(); 219 for (int i = 0; i < assignment.Length; i++) 220 assignment[slnParser.Assignment[i]] = i; 221 } 222 instance.BestKnownAssignment = assignment; 223 instance.BestKnownQuality = slnParser.Quality; 224 } 225 } 226 } 76 int bestknown; 77 if (bkq.TryGetValue(instance.Name, out bestknown)) 78 instance.BestKnownColors = bestknown; 227 79 return instance; 228 80 } … … 233 85 get { return true; } 234 86 } 235 public override QAPData ImportData(string path) {236 var parser = new QAPLIBParser();87 public override GCPData ImportData(string path) { 88 var parser = new Parser(); 237 89 parser.Parse(path); 238 90 var instance = Load(parser); … … 242 94 } 243 95 244 private QAPData Load(QAPLIBParser parser) { 245 var instance = new QAPData(); 246 instance.Dimension = parser.Size; 247 instance.Distances = parser.Distances; 248 instance.Weights = parser.Weights; 96 private GCPData Load(Parser parser) { 97 var instance = new GCPData(); 98 instance.Nodes = parser.Nodes; 99 var adjacencies = new int[parser.Edges, 2]; 100 var i = 0; 101 foreach (var a in parser.AdjacencyList) { 102 adjacencies[i, 0] = a.Item1 - 1; 103 adjacencies[i, 1] = a.Item2 - 1; 104 i++; 105 } 106 instance.Adjacencies = adjacencies; 249 107 return instance; 250 108 } … … 258 116 .Where(x => Regex.Match(x, @".*\.Data\." + fileName).Success).SingleOrDefault(); 259 117 } 118 119 private Dictionary<string, int> bkq = new Dictionary<string, int> { 120 { "fpsol2.i.1", 65 }, 121 { "fpsol2.i.2", 30 }, 122 { "fpsol2.i.3", 30 }, 123 { "inithx.i.1", 54 }, 124 { "inithx.i.2", 31 }, 125 { "inithx.i.3", 31 }, 126 { "le450_5a", 5 }, 127 { "le450_5b", 5 }, 128 { "le450_5c", 5 }, 129 { "le450_5d", 5 }, 130 { "le450_15a", 15 }, 131 { "le450_15b", 15 }, 132 { "le450_15c", 15 }, 133 { "le450_15d", 15 }, 134 { "le450_25a", 25 }, 135 { "le450_25b", 25 }, 136 { "le450_25c", 25 }, 137 { "le450_25d", 25 }, 138 { "mulsol.i.1", 49 }, 139 { "mulsol.i.2", 31 }, 140 { "mulsol.i.3", 31 }, 141 { "mulsol.i.4", 31 }, 142 { "mulsol.i.5", 31 }, 143 { "zeroin.i.1", 49 }, 144 { "zeroin.i.2", 30 }, 145 { "zeroin.i.3", 30 }, 146 { "anna", 11 }, 147 { "david", 11 }, 148 { "homer", 13 }, 149 { "huck", 11 }, 150 { "jean", 10 }, 151 { "games120", 9 }, 152 { "miles250", 8 }, 153 { "miles500", 20 }, 154 { "miles750", 31 }, 155 { "miles1000", 42 }, 156 { "miles1500", 73 }, 157 { "queen5_5", 5 }, 158 { "queen6_6", 7 }, 159 { "queen7_7", 7 }, 160 { "queen8_8", 9 }, 161 { "queen8_12", 12 }, 162 { "queen9_9", 10 }, 163 { "queen11_11", 11 }, 164 { "queen13_13", 13 }, 165 { "myciel3", 4 }, 166 { "myciel4", 5 }, 167 { "myciel5", 6 }, 168 { "myciel6", 7 }, 169 { "myciel7", 8 }, 170 { "mugg88_1", 4 }, 171 { "mugg88_25", 4 }, 172 { "mugg100_1", 4 }, 173 { "mugg100_25", 4 }, 174 { "1-Insertions_4", 4 }, 175 { "2-Insertions_3", 4 }, 176 { "2-Insertions_4", 4 }, 177 { "3-Insertions_3", 4 }, 178 { "4-Insertions_3", 3 }, 179 { "qg.order30", 30 }, 180 { "qg.order40", 40 }, 181 { "qg.order60", 60 }, 182 { "qg.order100", 100 } 183 }; 260 184 } 261 185 } -
branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/Parser.cs
r14429 r14471 21 21 22 22 using System; 23 using System.Collections.Generic; 23 24 using System.IO; 24 25 25 namespace HeuristicLab.Problems.Instances.QAPLIB { 26 public class QAPLIBParser { 27 public int Size { get; private set; } 28 public double[,] Distances { get; private set; } 29 public double[,] Weights { get; private set; } 26 namespace HeuristicLab.Problems.Instances.DIMACS { 27 public class Parser { 28 public int Nodes { get; private set; } 29 public int Edges { get; private set; } 30 public ICollection<Tuple<int, int>> AdjacencyList { get { return edges; } } 31 private HashSet<Tuple<int, int>> edges; 30 32 31 public QAPLIBParser() {33 public Parser() { 32 34 Reset(); 33 35 } 34 36 35 37 public void Reset() { 36 Size= 0;37 Distances = null;38 Weights = null;38 Nodes = 0; 39 Edges = 0; 40 edges = new HashSet<Tuple<int, int>>(); 39 41 } 40 42 … … 54 56 /// <returns>True if the file was successfully read or false otherwise.</returns> 55 57 public void Parse(Stream stream) { 58 char[] delim = new char[] { ' ', '\t' }; 56 59 var reader = new StreamReader(stream); 57 Size = int.Parse(reader.ReadLine()); 58 Distances = new double[Size, Size]; 59 Weights = new double[Size, Size]; 60 char[] delim = new char[] { ' ', '\t' }; 60 var line = reader.ReadLine().Trim(); 61 // skip comments 62 while (line.StartsWith("c", StringComparison.InvariantCultureIgnoreCase)) line = reader.ReadLine().Trim(); 61 63 62 Weights = ParseMatrix(reader, delim); 63 Distances = ParseMatrix(reader, delim); 64 } 65 66 private double[,] ParseMatrix(StreamReader reader, char[] delim) { 67 int read = 0, k = 0; 68 double[,] result = new double[Size, Size]; 69 while (k < Size) { 70 if (reader.EndOfStream) throw new InvalidDataException("Reached end of stream while reading second matrix."); 71 string valLine = reader.ReadLine(); 72 while (String.IsNullOrWhiteSpace(valLine)) valLine = reader.ReadLine(); 73 string[] vals = valLine.Split(delim, StringSplitOptions.RemoveEmptyEntries); 74 foreach (string val in vals) { 75 result[k, read++] = double.Parse(val); 76 if (read == Size) { 77 read = 0; 78 k++; 79 } 80 } 81 } 82 return result; 64 // p edge NODES EDGES 65 var split = line.Split(delim, StringSplitOptions.RemoveEmptyEntries); 66 Nodes = int.Parse(split[2]); 67 do { 68 line = reader.ReadLine(); 69 if (string.IsNullOrEmpty(line)) break; 70 // e XX YY 71 split = line.Split(delim, StringSplitOptions.RemoveEmptyEntries); 72 var src = int.Parse(split[1]); 73 var tgt = int.Parse(split[2]); 74 Tuple<int, int> e = null; 75 if (src < tgt) e = Tuple.Create(src, tgt); 76 else if (src > tgt) e = Tuple.Create(tgt, src); 77 else continue; // src == tgt 78 if (edges.Add(e)) Edges++; 79 } while (!reader.EndOfStream); 83 80 } 84 81 }
Note: See TracChangeset
for help on using the changeset viewer.