source: branches/OptimizationNetworks/HeuristicLab.Networks.Views.NetworkVisualization/3.3/Layout.cs @ 13833

Last change on this file since 13833 was 13833, checked in by jkarder, 4 years ago

#2205: worked on optimization networks

  • added layout algorithm prototype
  • fixed bug in LoadVisualProperties methods
File size: 8.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26
27namespace HeuristicLab.Networks.Views.NetworkVisualization {
28  public class Layout {
29    private const double RAD_TO_DEG = 180 / Math.PI;
30    private const double DEG_TO_RAD = 1 / RAD_TO_DEG;
31
32    private const double REPULSION_CONSTANT = 10000.0;
33    private const double ATTRACTION_CONSTANT = 0.1;
34    private const double EQUILIBRIUM = 15;
35
36    private readonly IList<Node> nodes = new List<Node>();
37
38    public bool AddNode(Node node) {
39      if (node == null) throw new ArgumentNullException("node");
40      if (nodes.Contains(node)) return false;
41
42      nodes.Add(node);
43      foreach (var c in node.Nodes) AddNode(c);
44      return true;
45    }
46
47    public void Arrange(double damping = 0.5, double springLength = 100, int maxIterations = 500, bool deterministic = true) {
48      var random = deterministic ? new Random(0) : new Random();
49
50      var nodeMechanics = new NodeMechanics[nodes.Count];
51      for (int i = 0; i < nodes.Count; i++) {
52        nodeMechanics[i] = new NodeMechanics(nodes[i], new Vector(), Point.Empty);
53        nodeMechanics[i].Node.Location = new Point(random.Next(-50, 50), random.Next(-50, 50));
54      }
55
56      for (int i = 0, eqCount = 0; i < maxIterations && eqCount <= EQUILIBRIUM; i++) {
57        double totalDisplacement = 0.0;
58
59        foreach (var current in nodeMechanics) {
60          var node = current.Node;
61          var currentPosition = new Vector(CalculateDistance(Point.Empty, node.Location), CalculateBearingAngle(Point.Empty, node.Location));
62          var netForce = new Vector();
63
64          foreach (var n in nodes)
65            if (n != node)
66              netForce += CalculateRepulsionForce(node, n);
67
68          foreach (var n in node.Nodes)
69            netForce += CalculateAttractionForce(node, n, springLength);
70
71          foreach (var n in nodes)
72            if (n.Nodes.Contains(node))
73              netForce += CalculateAttractionForce(node, n, springLength);
74
75          current.Velocity = (current.Velocity + netForce) * damping;
76          current.NextPosition = (currentPosition + current.Velocity).ToPoint();
77        }
78
79        foreach (var current in nodeMechanics) {
80          totalDisplacement += CalculateDistance(current.Node.Location, current.NextPosition);
81          current.Node.Location = current.NextPosition;
82        }
83
84        if (totalDisplacement < 10) eqCount++;
85      }
86    }
87
88    public void Arrange(Rectangle bounds, double damping = 0.5, double springLength = 100.0, int maxIterations = 500, bool deterministic = true) {
89      Arrange(damping, 200, maxIterations, deterministic);
90
91      var logicalBounds = GetLogicalBounds();
92      var center = new Point(logicalBounds.X + logicalBounds.Width / 2, logicalBounds.Y + logicalBounds.Height / 2);
93      int maxWidth = 0, maxHeight = 0;
94      foreach (var node in nodes) {
95        node.Location -= (Size)center;
96        if (node.Size.Width > maxWidth) maxWidth = node.Size.Width;
97        if (node.Size.Height > maxHeight) maxHeight = node.Size.Height;
98      }
99
100      bounds = new Rectangle(bounds.X + maxWidth / 2, bounds.Y + maxHeight / 2, bounds.Width - maxWidth, bounds.Height - maxHeight);
101      double scale = Math.Min((double)bounds.Width / logicalBounds.Width, (double)bounds.Height / logicalBounds.Height);
102      foreach (var node in nodes)
103        node.Location = ScalePoint(node.Location, scale);
104
105      logicalBounds = GetLogicalBounds();
106      center = new Point(logicalBounds.X + logicalBounds.Width / 2, logicalBounds.Y + logicalBounds.Height / 2);
107      center.Offset(-(bounds.X + bounds.Width / 2), bounds.Y + bounds.Height / 2);
108      foreach (var node in nodes)
109        node.Location -= (Size)center;
110    }
111
112    #region Forces
113    private Vector CalculateRepulsionForce(Node a, Node b) {
114      double r = Math.Max(CalculateDistance(a.Location, b.Location), 1.0);
115      double force = -(REPULSION_CONSTANT / (r * r));
116      double angle = CalculateBearingAngle(a.Location, b.Location);
117      return new Vector(force, angle);
118    }
119
120    private Vector CalculateAttractionForce(Node a, Node b, double springLength) {
121      double r = Math.Max(CalculateDistance(a.Location, b.Location), 1.0);
122      double force = ATTRACTION_CONSTANT * Math.Max(r - springLength, 0.0);
123      double angle = CalculateBearingAngle(a.Location, b.Location);
124      return new Vector(force, angle);
125    }
126    #endregion
127
128    #region Helpers
129    private static double CalculateDistance(Point a, Point b) {
130      double dX = a.X - b.X;
131      double dY = a.Y - b.Y;
132      return Math.Sqrt(dX * dX + dY * dY);
133    }
134
135    private static double CalculateBearingAngle(Point a, Point b) {
136      double dX = b.X - a.X;
137      double dY = b.Y - a.Y;
138      double angle = Math.Atan2(dY, dX) * RAD_TO_DEG;
139      return angle;
140    }
141
142    private static Point ScalePoint(Point p, double scalar) {
143      return new Point((int)Math.Round(p.X * scalar), (int)Math.Round(p.Y * scalar));
144    }
145
146    private Rectangle GetLogicalBounds() {
147      int minX = int.MaxValue, maxX = int.MinValue,
148          minY = int.MaxValue, maxY = int.MinValue;
149      foreach (var node in nodes) {
150        if (node.Location.X < minX) minX = node.Location.X;
151        if (node.Location.X > maxX) maxX = node.Location.X;
152        if (node.Location.Y < minY) minY = node.Location.Y;
153        if (node.Location.Y > maxY) maxY = node.Location.Y;
154      }
155
156      return Rectangle.FromLTRB(minX, minY, maxX, maxY);
157    }
158    #endregion
159
160    #region Vector
161    private struct Vector {
162      public double X { get; private set; }
163      public double Y { get; private set; }
164
165      public Vector(double magnitude, double direction) {
166        X = magnitude * Math.Cos(direction * DEG_TO_RAD);
167        Y = magnitude * Math.Sin(direction * DEG_TO_RAD);
168      }
169
170      public Point ToPoint() {
171        return new Point((int)Math.Round(X), (int)Math.Round(Y));
172      }
173
174      public static Vector operator +(Vector a, Vector b) {
175        return new Vector { X = a.X + b.X, Y = a.Y + b.Y };
176      }
177
178      public static Vector operator *(Vector v, double d) {
179        return new Vector { X = v.X * d, Y = v.Y * d };
180      }
181    }
182    #endregion
183
184    #region Nodes
185    public abstract class Node {
186      public Point Location { get; set; }
187      public abstract Size Size { get; }
188
189      private readonly List<Node> nodes = new List<Node>();
190      public IEnumerable<Node> Nodes { get { return nodes; } }
191
192      public bool AddNode(Node node) {
193        if (node == null) throw new ArgumentNullException("node");
194        if (node == this || nodes.Contains(node)) return false;
195
196        nodes.Add(node);
197        return true;
198      }
199    }
200
201    public class LayoutNode : Node {
202      private Size size;
203      public override Size Size { get { return size; } }
204
205      public LayoutNode(Size size) {
206        this.size = size;
207      }
208    }
209    #endregion
210
211    #region Mechanics
212    private class NodeMechanics {
213      public Node Node { get; private set; }
214      public Vector Velocity { get; set; }
215      public Point NextPosition { get; set; }
216
217      public NodeMechanics(Node node, Vector velocity, Point nextPosition) {
218        Node = node;
219        Velocity = velocity;
220        NextPosition = nextPosition;
221      }
222    }
223    #endregion
224  }
225}
Note: See TracBrowser for help on using the repository browser.