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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace HeuristicLab.Networks.Views.NetworkVisualization {
  public class Layout {
    private const double RAD_TO_DEG = 180 / Math.PI;
    private const double DEG_TO_RAD = 1 / RAD_TO_DEG;

    private const double REPULSION_CONSTANT = 10000.0;
    private const double ATTRACTION_CONSTANT = 0.1;
    private const double EQUILIBRIUM = 15;

    private readonly IList<Node> nodes = new List<Node>();

    public bool AddNode(Node node) {
      if (node == null) throw new ArgumentNullException("node");
      if (nodes.Contains(node)) return false;

      nodes.Add(node);
      foreach (var c in node.Nodes) AddNode(c);
      return true;
    }

    public void Arrange(double damping = 0.5, double springLength = 100, int maxIterations = 500, bool deterministic = true) {
      var random = deterministic ? new Random(0) : new Random();

      var nodeMechanics = new NodeMechanics[nodes.Count];
      for (int i = 0; i < nodes.Count; i++) {
        nodeMechanics[i] = new NodeMechanics(nodes[i], new Vector(), Point.Empty);
        nodeMechanics[i].Node.Location = new Point(random.Next(-50, 50), random.Next(-50, 50));
      }

      for (int i = 0, eqCount = 0; i < maxIterations && eqCount <= EQUILIBRIUM; i++) {
        double totalDisplacement = 0.0;

        foreach (var current in nodeMechanics) {
          var node = current.Node;
          var currentPosition = new Vector(CalculateDistance(Point.Empty, node.Location), CalculateBearingAngle(Point.Empty, node.Location));
          var netForce = new Vector();

          foreach (var n in nodes)
            if (n != node)
              netForce += CalculateRepulsionForce(node, n);

          foreach (var n in node.Nodes)
            netForce += CalculateAttractionForce(node, n, springLength);

          foreach (var n in nodes)
            if (n.Nodes.Contains(node))
              netForce += CalculateAttractionForce(node, n, springLength);

          current.Velocity = (current.Velocity + netForce) * damping;
          current.NextPosition = (currentPosition + current.Velocity).ToPoint();
        }

        foreach (var current in nodeMechanics) {
          totalDisplacement += CalculateDistance(current.Node.Location, current.NextPosition);
          current.Node.Location = current.NextPosition;
        }

        if (totalDisplacement < 10) eqCount++;
      }
    }

    public void Arrange(Rectangle bounds, double damping = 0.5, double springLength = 100.0, int maxIterations = 500, bool deterministic = true) {
      Arrange(damping, 200, maxIterations, deterministic);

      var logicalBounds = GetLogicalBounds();
      var center = new Point(logicalBounds.X + logicalBounds.Width / 2, logicalBounds.Y + logicalBounds.Height / 2);
      int maxWidth = 0, maxHeight = 0;
      foreach (var node in nodes) {
        node.Location -= (Size)center;
        if (node.Size.Width > maxWidth) maxWidth = node.Size.Width;
        if (node.Size.Height > maxHeight) maxHeight = node.Size.Height;
      }

      bounds = new Rectangle(bounds.X + maxWidth / 2, bounds.Y + maxHeight / 2, bounds.Width - maxWidth, bounds.Height - maxHeight);
      double scale = Math.Min((double)bounds.Width / logicalBounds.Width, (double)bounds.Height / logicalBounds.Height);
      foreach (var node in nodes)
        node.Location = ScalePoint(node.Location, scale);

      logicalBounds = GetLogicalBounds();
      center = new Point(logicalBounds.X + logicalBounds.Width / 2, logicalBounds.Y + logicalBounds.Height / 2);
      center.Offset(-(bounds.X + bounds.Width / 2), bounds.Y + bounds.Height / 2);
      foreach (var node in nodes)
        node.Location -= (Size)center;
    }

    #region Forces
    private Vector CalculateRepulsionForce(Node a, Node b) {
      double r = Math.Max(CalculateDistance(a.Location, b.Location), 1.0);
      double force = -(REPULSION_CONSTANT / (r * r));
      double angle = CalculateBearingAngle(a.Location, b.Location);
      return new Vector(force, angle);
    }

    private Vector CalculateAttractionForce(Node a, Node b, double springLength) {
      double r = Math.Max(CalculateDistance(a.Location, b.Location), 1.0);
      double force = ATTRACTION_CONSTANT * Math.Max(r - springLength, 0.0);
      double angle = CalculateBearingAngle(a.Location, b.Location);
      return new Vector(force, angle);
    }
    #endregion

    #region Helpers
    private static double CalculateDistance(Point a, Point b) {
      double dX = a.X - b.X;
      double dY = a.Y - b.Y;
      return Math.Sqrt(dX * dX + dY * dY);
    }

    private static double CalculateBearingAngle(Point a, Point b) {
      double dX = b.X - a.X;
      double dY = b.Y - a.Y;
      double angle = Math.Atan2(dY, dX) * RAD_TO_DEG;
      return angle;
    }

    private static Point ScalePoint(Point p, double scalar) {
      return new Point((int)Math.Round(p.X * scalar), (int)Math.Round(p.Y * scalar));
    }

    private Rectangle GetLogicalBounds() {
      int minX = int.MaxValue, maxX = int.MinValue,
          minY = int.MaxValue, maxY = int.MinValue;
      foreach (var node in nodes) {
        if (node.Location.X < minX) minX = node.Location.X;
        if (node.Location.X > maxX) maxX = node.Location.X;
        if (node.Location.Y < minY) minY = node.Location.Y;
        if (node.Location.Y > maxY) maxY = node.Location.Y;
      }

      return Rectangle.FromLTRB(minX, minY, maxX, maxY);
    }
    #endregion

    #region Vector
    private struct Vector {
      public double X { get; private set; }
      public double Y { get; private set; }

      public Vector(double magnitude, double direction) {
        X = magnitude * Math.Cos(direction * DEG_TO_RAD);
        Y = magnitude * Math.Sin(direction * DEG_TO_RAD);
      }

      public Point ToPoint() {
        return new Point((int)Math.Round(X), (int)Math.Round(Y));
      }

      public static Vector operator +(Vector a, Vector b) {
        return new Vector { X = a.X + b.X, Y = a.Y + b.Y };
      }

      public static Vector operator *(Vector v, double d) {
        return new Vector { X = v.X * d, Y = v.Y * d };
      }
    }
    #endregion

    #region Nodes
    public abstract class Node {
      public Point Location { get; set; }
      public abstract Size Size { get; }

      private readonly List<Node> nodes = new List<Node>();
      public IEnumerable<Node> Nodes { get { return nodes; } }

      public bool AddNode(Node node) {
        if (node == null) throw new ArgumentNullException("node");
        if (node == this || nodes.Contains(node)) return false;

        nodes.Add(node);
        return true;
      }
    }

    public class LayoutNode : Node {
      private Size size;
      public override Size Size { get { return size; } }

      public LayoutNode(Size size) {
        this.size = size;
      }
    }
    #endregion

    #region Mechanics
    private class NodeMechanics {
      public Node Node { get; private set; }
      public Vector Velocity { get; set; }
      public Point NextPosition { get; set; }

      public NodeMechanics(Node node, Vector velocity, Point nextPosition) {
        Node = node;
        Velocity = velocity;
        NextPosition = nextPosition;
      }
    }
    #endregion
  }
}