Free cookie consent management tool by TermsFeed Policy Generator

source: branches/QAP/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QAPView.cs @ 5648

Last change on this file since 5648 was 5648, checked in by abeham, 12 years ago

#1330

  • Unified QAP visualization in solution and problem view
  • Fixed bug in gradient-descent gradient calculation when performing multidimensional scaling
  • Extended QAPLIB parsers to cover some file format variations
  • Added unit tests to check if all QAPLIB instances import without error
  • Changed BestKnownSolution to be an OptionalValueParameter
File size: 18.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Drawing;
24using System.Drawing.Drawing2D;
25using System.Drawing.Text;
26using System.Globalization;
27using System.Windows.Forms;
28using HeuristicLab.Common;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.PermutationEncoding;
31
32namespace HeuristicLab.Problems.QuadraticAssignment.Views {
33  public partial class QAPView : UserControl {
34    private Bitmap bitmap;
35    private Bitmap defaultBitmap;
36
37    #region Properties
38    private DoubleMatrix distances;
39    public DoubleMatrix Distances {
40      get { return distances; }
41      set {
42        DeregisterDistancesEvents();
43        distances = value;
44        RegisterDistancesEvents();
45        OnRedraw();
46      }
47    }
48
49    private DoubleMatrix weights;
50    public DoubleMatrix Weights {
51      get { return weights; }
52      set {
53        DeregisterWeightsEvents();
54        weights = value;
55        RegisterWeightsEvents();
56        OnRedraw();
57      }
58    }
59
60    private Permutation assignment;
61    public Permutation Assignment {
62      get { return assignment; }
63      set {
64        DeregisterAssignmentEvents();
65        assignment = value;
66        RegisterAssignmentEvents();
67        OnRedraw();
68      }
69    }
70    #endregion
71
72    #region Event Handling
73    private void DeregisterDistancesEvents() {
74      if (Distances != null) {
75        Distances.Reset -= new EventHandler(Redraw);
76        Distances.RowsChanged -= new EventHandler(Redraw);
77        Distances.ColumnsChanged -= new EventHandler(Redraw);
78        Distances.ItemChanged -= new EventHandler<EventArgs<int, int>>(Redraw);
79      }
80    }
81
82    private void RegisterDistancesEvents() {
83      if (Distances != null) {
84        Distances.Reset += new EventHandler(Redraw);
85        Distances.RowsChanged += new EventHandler(Redraw);
86        Distances.ColumnsChanged += new EventHandler(Redraw);
87        Distances.ItemChanged += new EventHandler<EventArgs<int, int>>(Redraw);
88      }
89    }
90
91    private void DeregisterWeightsEvents() {
92      if (Weights != null) {
93        Weights.Reset -= new EventHandler(Redraw);
94        Weights.RowsChanged -= new EventHandler(Redraw);
95        Weights.ColumnsChanged -= new EventHandler(Redraw);
96        Weights.ItemChanged -= new EventHandler<EventArgs<int, int>>(Redraw);
97      }
98    }
99
100    private void RegisterWeightsEvents() {
101      if (Weights != null) {
102        Weights.Reset += new EventHandler(Redraw);
103        Weights.RowsChanged += new EventHandler(Redraw);
104        Weights.ColumnsChanged += new EventHandler(Redraw);
105        Weights.ItemChanged += new EventHandler<EventArgs<int, int>>(Redraw);
106      }
107    }
108
109    private void DeregisterAssignmentEvents() {
110      if (Assignment != null) {
111        Assignment.Reset -= new EventHandler(Redraw);
112        Assignment.ItemChanged -= new EventHandler<EventArgs<int>>(Redraw);
113      }
114    }
115
116    private void RegisterAssignmentEvents() {
117      if (Assignment != null) {
118        Assignment.Reset += new EventHandler(Redraw);
119        Assignment.ItemChanged += new EventHandler<EventArgs<int>>(Redraw);
120      }
121    }
122
123    private void Redraw(object sender, EventArgs e) {
124      if (sender is RadioButton && !((RadioButton)sender).Checked)
125        return;
126      OnRedraw();
127    }
128
129    private void Redraw(object sender, EventArgs<int, int> e) {
130      OnRedraw();
131    }
132
133    private void pictureBox_SizeChanged(object sender, EventArgs e) {
134      SetupDefaultBitmap();
135      OnRedraw();
136    }
137    #endregion
138
139    public QAPView() {
140      InitializeComponent();
141      SetupDefaultBitmap();
142    }
143
144    private void SetupDefaultBitmap() {
145      if (defaultBitmap != null) defaultBitmap.Dispose();
146      defaultBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
147      WriteCenteredTextToBitmap(ref defaultBitmap, "No visualization available");
148    }
149
150    private void WriteCenteredTextToBitmap(ref Bitmap bitmap, string text) {
151      using (Graphics g = Graphics.FromImage(bitmap)) {
152        g.TextRenderingHint = TextRenderingHint.AntiAlias;
153        g.SmoothingMode = SmoothingMode.AntiAlias;
154
155        SizeF strSize = g.MeasureString(text, Font);
156        g.DrawString(text, Font, Brushes.Black, (float)(pictureBox.Width - strSize.Width) / 2.0f, (float)(pictureBox.Height - strSize.Height) / 2.0f);
157      }
158    }
159
160    private void OnRedraw() {
161      if (InvokeRequired) {
162        Invoke((Action)OnRedraw, null);
163      } else {
164        GenerateImage();
165      }
166    }
167
168    private void GenerateImage() {
169      Bitmap newBitmap = null;
170      stressLabel.Text = "-";
171      if (distancesRadioButton.Checked && Distances != null && Distances.Rows > 0
172        && Distances.Rows == Distances.Columns) {
173        if (Distances.Rows > 30) {
174          newBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
175          WriteCenteredTextToBitmap(ref newBitmap, "Problem dimension too large for visualization.");
176        } else newBitmap = GenerateDistanceImage();
177      } else if (weightsRadioButton.Checked && Weights != null && Weights.Rows > 0
178        && Weights.Rows == Weights.Columns) {
179        if (Weights.Rows > 30) {
180          newBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
181          WriteCenteredTextToBitmap(ref newBitmap, "Problem dimension too large for visualization.");
182        } else newBitmap = GenerateWeightsImage();
183      } else if (assignmentRadioButton.Checked
184        && Assignment != null && Assignment.Length > 0
185        && Weights != null && Weights.Rows > 0
186        && Distances != null && Distances.Rows > 0
187        && Weights.Rows == Weights.Columns
188        && Distances.Rows == Distances.Columns
189        && Assignment.Length == Weights.Rows
190        && Assignment.Length == Distances.Rows
191        && Assignment.Validate()) {
192        newBitmap = GenerateAssignmentImage();
193      }
194
195      pictureBox.Image = newBitmap != null ? newBitmap : defaultBitmap;
196      if (bitmap != null) bitmap.Dispose();
197      if (newBitmap != null) bitmap = newBitmap;
198      else bitmap = null;
199    }
200
201    #region Draw distances
202    private Bitmap GenerateDistanceImage() {
203      if ((pictureBox.Width > 0) && (pictureBox.Height > 0)) {
204        Bitmap newBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
205
206        for (int i = 0; i < distances.Rows; i++) {
207          for (int j = i + 1; j < distances.Rows; j++)
208            if (distances[i, j] != distances[j, i]) {
209              WriteCenteredTextToBitmap(ref newBitmap, "Distance matrix is not symmetric");
210              return newBitmap;
211            }
212        }
213
214        double stress;
215        DoubleMatrix coordinates = MultidimensionalScaling.MetricByDistance(distances, out stress);
216        stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
217        double xMin = double.MaxValue, yMin = double.MaxValue, xMax = double.MinValue, yMax = double.MinValue;
218        double maxDistance = double.MinValue;
219        for (int i = 0; i < coordinates.Rows; i++) {
220          if (xMin > coordinates[i, 0]) xMin = coordinates[i, 0];
221          if (yMin > coordinates[i, 1]) yMin = coordinates[i, 1];
222          if (xMax < coordinates[i, 0]) xMax = coordinates[i, 0];
223          if (yMax < coordinates[i, 1]) yMax = coordinates[i, 1];
224
225          for (int j = i + 1; j < coordinates.Rows; j++) {
226            if (distances[i, j] > maxDistance) maxDistance = distances[i, j];
227            if (distances[j, i] > maxDistance) maxDistance = distances[j, i];
228          }
229        }
230
231        int border = 20;
232        double xStep = xMax != xMin ? (pictureBox.Width - 2 * border) / (xMax - xMin) : 1;
233        double yStep = yMax != yMin ? (pictureBox.Height - 2 * border) / (yMax - yMin) : 1;
234
235        Point[] points = new Point[coordinates.Rows];
236        for (int i = 0; i < coordinates.Rows; i++)
237          points[i] = new Point(border + ((int)((coordinates[i, 0] - xMin) * xStep)),
238                                newBitmap.Height - (border + ((int)((coordinates[i, 1] - yMin) * yStep))));
239
240        Random rand = new Random();
241        using (Graphics graphics = Graphics.FromImage(newBitmap)) {
242          graphics.SmoothingMode = SmoothingMode.AntiAlias;
243          graphics.TextRenderingHint = TextRenderingHint.AntiAlias;
244          graphics.DrawString("Showing locations spaced out according to their distances", Font, Brushes.Black, 5, 2);
245
246          for (int i = 0; i < coordinates.Rows - 1; i++) {
247            for (int j = i + 1; j < coordinates.Rows; j++) {
248              Point start = points[i], end = points[j];
249              string caption = String.Empty;
250              double d = Math.Max(distances[i, j], distances[j, i]);
251              float width = (float)Math.Ceiling(5.0 * d / maxDistance);
252              if (d > 0) {
253                graphics.DrawLine(new Pen(Color.IndianRed, width), start, end);
254                if (distances[i, j] != distances[j, i])
255                  caption = distances[i, j].ToString(CultureInfo.InvariantCulture.NumberFormat)
256                    + " / " + distances[j, i].ToString(CultureInfo.InvariantCulture.NumberFormat);
257                else
258                  caption = distances[i, j].ToString(CultureInfo.InvariantCulture.NumberFormat);
259              }
260              if (!String.IsNullOrEmpty(caption)) {
261                double r = rand.NextDouble();
262                while (r < 0.2 || r > 0.8) r = rand.NextDouble();
263                float x = (float)(start.X + (end.X - start.X) * r + 5);
264                float y = (float)(start.Y + (end.Y - start.Y) * r + 5);
265                graphics.DrawString(caption, Font, Brushes.Black, x, y);
266              }
267            }
268          }
269
270          for (int i = 0; i < points.Length; i++) {
271            Point p = new Point(points[i].X - 3, points[i].Y - 3);
272            graphics.FillRectangle(Brushes.Black, p.X, p.Y, 8, 8);
273            graphics.DrawString(i.ToString(), Font, Brushes.Black, p.X, p.Y + 10);
274          }
275        }
276        return newBitmap;
277      }
278      return null;
279    }
280    #endregion
281
282    #region Draw weights
283    private Bitmap GenerateWeightsImage() {
284      if ((pictureBox.Width > 0) && (pictureBox.Height > 0)) {
285        Bitmap newBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
286
287        double maxWeight = double.MinValue;
288        for (int i = 0; i < weights.Rows; i++)
289          for (int j = i + 1; j < weights.Rows; j++) {
290            if (weights[i, j] > maxWeight)
291              maxWeight = weights[i, j] + weights[j, i];
292
293            if (weights[i, j] != weights[j, i]) {
294              WriteCenteredTextToBitmap(ref newBitmap, "Weights matrix is not symmetric");
295              return newBitmap;
296            }
297          }
298
299        DoubleMatrix distances = new DoubleMatrix(weights.Rows, weights.Columns);
300        for (int i = 0; i < distances.Rows; i++)
301          for (int j = 0; j < distances.Columns; j++) {
302            distances[i, j] = maxWeight + 1 - weights[i, j];
303          }
304
305        double stress;
306        DoubleMatrix coordinates = MultidimensionalScaling.MetricByDistance(distances, out stress);
307        stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
308        double xMin = double.MaxValue, yMin = double.MaxValue, xMax = double.MinValue, yMax = double.MinValue;
309        for (int i = 0; i < coordinates.Rows; i++) {
310          if (xMin > coordinates[i, 0]) xMin = coordinates[i, 0];
311          if (yMin > coordinates[i, 1]) yMin = coordinates[i, 1];
312          if (xMax < coordinates[i, 0]) xMax = coordinates[i, 0];
313          if (yMax < coordinates[i, 1]) yMax = coordinates[i, 1];
314        }
315
316        int border = 20;
317        double xStep = xMax != xMin ? (pictureBox.Width - 2 * border) / (xMax - xMin) : 1;
318        double yStep = yMax != yMin ? (pictureBox.Height - 2 * border) / (yMax - yMin) : 1;
319
320        Point[] points = new Point[coordinates.Rows];
321        for (int i = 0; i < coordinates.Rows; i++)
322          points[i] = new Point(border + ((int)((coordinates[i, 0] - xMin) * xStep)),
323                                newBitmap.Height - (border + ((int)((coordinates[i, 1] - yMin) * yStep))));
324
325        Random rand = new Random();
326        using (Graphics graphics = Graphics.FromImage(newBitmap)) {
327          graphics.SmoothingMode = SmoothingMode.AntiAlias;
328          graphics.TextRenderingHint = TextRenderingHint.AntiAlias;
329          graphics.DrawString("Showing facilities spaced out according to their weights", Font, Brushes.Black, 5, 2);
330
331          for (int i = 0; i < coordinates.Rows - 1; i++) {
332            for (int j = i + 1; j < coordinates.Rows; j++) {
333              Point start = points[i], end = points[j];
334              string caption = String.Empty;
335              double d = Math.Max(distances[i, j], distances[j, i]);
336              double w = weights[i, j];
337              if (w > 0) {
338                float width = (float)Math.Ceiling(3.0 * w / maxWeight);
339                graphics.DrawLine(new Pen(Color.MediumBlue, width), start, end);
340                caption = w.ToString(CultureInfo.InvariantCulture.NumberFormat);
341              }
342              if (!String.IsNullOrEmpty(caption)) {
343                double r = rand.NextDouble();
344                while (r < 0.2 || r > 0.8) r = rand.NextDouble();
345                float x = (float)(start.X + (end.X - start.X) * r + 5);
346                float y = (float)(start.Y + (end.Y - start.Y) * r + 5);
347                graphics.DrawString(caption, Font, Brushes.Black, x, y);
348              }
349            }
350          }
351          for (int i = 0; i < points.Length; i++) {
352            Point p = new Point(points[i].X - 3, points[i].Y - 3);
353            graphics.FillRectangle(Brushes.Black, p.X, p.Y, 8, 8);
354            graphics.DrawString(i.ToString(), Font, Brushes.Black, p.X, p.Y + 10);
355          }
356        }
357        return newBitmap;
358      }
359      return null;
360    }
361    #endregion
362
363    #region Draw assignment
364    private Bitmap GenerateAssignmentImage() {
365      if ((pictureBox.Width > 0) && (pictureBox.Height > 0)) {
366        Bitmap newBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
367
368        for (int i = 0; i < distances.Rows; i++) {
369          for (int j = i + 1; j < distances.Rows; j++) {
370            if (distances[i, j] != distances[j, i]) {
371              WriteCenteredTextToBitmap(ref newBitmap, "Distance matrix is not symmetric");
372              return newBitmap;
373            }
374            if (weights[i, j] != weights[j, i]) {
375              WriteCenteredTextToBitmap(ref newBitmap, "Weights matrix is not symmetric");
376            }
377          }
378        }
379
380        double stress;
381        DoubleMatrix coordinates = MultidimensionalScaling.MetricByDistance(distances, out stress);
382        stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
383        double xMin = double.MaxValue, yMin = double.MaxValue, xMax = double.MinValue, yMax = double.MinValue;
384        double maxWeight = double.MinValue;
385        for (int i = 0; i < coordinates.Rows; i++) {
386          if (xMin > coordinates[i, 0]) xMin = coordinates[i, 0];
387          if (yMin > coordinates[i, 1]) yMin = coordinates[i, 1];
388          if (xMax < coordinates[i, 0]) xMax = coordinates[i, 0];
389          if (yMax < coordinates[i, 1]) yMax = coordinates[i, 1];
390
391          for (int j = i + 1; j < coordinates.Rows; j++) {
392            if (weights[i, j] > maxWeight) maxWeight = weights[i, j];
393          }
394        }
395
396        int border = 20;
397        double xStep = xMax != xMin ? (pictureBox.Width - 2 * border) / (xMax - xMin) : 1;
398        double yStep = yMax != yMin ? (pictureBox.Height - 2 * border) / (yMax - yMin) : 1;
399
400        Point[] points = new Point[coordinates.Rows];
401        for (int i = 0; i < coordinates.Rows; i++)
402          points[i] = new Point(border + ((int)((coordinates[i, 0] - xMin) * xStep)),
403                                newBitmap.Height - (border + ((int)((coordinates[i, 1] - yMin) * yStep))));
404
405        Random rand = new Random();
406        using (Graphics graphics = Graphics.FromImage(newBitmap)) {
407          graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
408          graphics.TextRenderingHint = System.Drawing.Text.TextRenderingHint.AntiAlias;
409
410          for (int i = 0; i < assignment.Length - 1; i++) {
411            for (int j = i + 1; j < assignment.Length; j++) {
412              Point start, end;
413              string caption = String.Empty;
414              double d = distances[i, j];
415              start = points[assignment[i]];
416              end = points[assignment[j]];
417              double w = weights[i, j];
418              if (w > 0) {
419                float width = (float)Math.Ceiling(4.0 * w / maxWeight);
420                graphics.DrawLine(new Pen(Color.MediumBlue, width), start, end);
421                caption = w.ToString(CultureInfo.InvariantCulture.NumberFormat);
422              }
423              if (!String.IsNullOrEmpty(caption)) {
424                double r = rand.NextDouble();
425                while (r < 0.2 || r > 0.8) r = rand.NextDouble();
426                float x = (float)(start.X + (end.X - start.X) * r + 5);
427                float y = (float)(start.Y + (end.Y - start.Y) * r + 5);
428                graphics.DrawString(caption, Font, Brushes.Black, x, y);
429              }
430            }
431          }
432
433          for (int i = 0; i < points.Length; i++) {
434            Point p = new Point(points[i].X - 3, points[i].Y - 3);
435            graphics.FillRectangle(Brushes.Black, p.X, p.Y, 8, 8);
436            graphics.DrawString(i.ToString(), Font, Brushes.Black, p.X, p.Y + 10);
437          }
438        }
439        return newBitmap;
440      }
441      return null;
442    }
443    #endregion
444
445    private void CustomDispose(bool disposing) {
446      DeregisterDistancesEvents();
447      DeregisterWeightsEvents();
448      DeregisterAssignmentEvents();
449      if (bitmap != null) bitmap.Dispose();
450      bitmap = null;
451      defaultBitmap.Dispose();
452      defaultBitmap = null;
453    }
454  }
455}
Note: See TracBrowser for help on using the repository browser.