Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 15529 was 14618, checked in by mkommend, 8 years ago

#2205: Corrected minor mistake in Layout.Vector struct (maybe connected to C# compiler version).

File size: 8.2 KB
RevLine 
[13833]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
[14618]165      public Vector(double magnitude, double direction)
166        : this() {
[13833]167        X = magnitude * Math.Cos(direction * DEG_TO_RAD);
168        Y = magnitude * Math.Sin(direction * DEG_TO_RAD);
169      }
170
171      public Point ToPoint() {
172        return new Point((int)Math.Round(X), (int)Math.Round(Y));
173      }
174
175      public static Vector operator +(Vector a, Vector b) {
176        return new Vector { X = a.X + b.X, Y = a.Y + b.Y };
177      }
178
179      public static Vector operator *(Vector v, double d) {
180        return new Vector { X = v.X * d, Y = v.Y * d };
181      }
182    }
183    #endregion
184
185    #region Nodes
186    public abstract class Node {
187      public Point Location { get; set; }
188      public abstract Size Size { get; }
189
190      private readonly List<Node> nodes = new List<Node>();
191      public IEnumerable<Node> Nodes { get { return nodes; } }
192
193      public bool AddNode(Node node) {
194        if (node == null) throw new ArgumentNullException("node");
195        if (node == this || nodes.Contains(node)) return false;
196
197        nodes.Add(node);
198        return true;
199      }
200    }
201
202    public class LayoutNode : Node {
203      private Size size;
204      public override Size Size { get { return size; } }
205
206      public LayoutNode(Size size) {
207        this.size = size;
208      }
209    }
210    #endregion
211
212    #region Mechanics
213    private class NodeMechanics {
214      public Node Node { get; private set; }
215      public Vector Velocity { get; set; }
216      public Point NextPosition { get; set; }
217
218      public NodeMechanics(Node node, Vector velocity, Point nextPosition) {
219        Node = node;
220        Velocity = velocity;
221        NextPosition = nextPosition;
222      }
223    }
224    #endregion
225  }
226}
Note: See TracBrowser for help on using the repository browser.