source: branches/HeuristicLab.VariableInteractionNetworks/HeuristicLab.VariableInteractionNetworks.Views/3.3/Layout/ConstrainedForceDirectedLayout.cs @ 13893

#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;
using Cola;
using HeuristicLab.Core;
using HeuristicLab.Random;
using Point = Cola.Point;

namespace HeuristicLab.VariableInteractionNetworks.Views {
  public class ConstrainedForceDirectedLayout {
    public enum EdgeRouting : uint {
      None,
      Polyline,
      Orthogonal
    }
    private ConstrainedFDLayout layoutEngine;
    private TopologyNodePtrs topologyNodes;
    private TopologyEdgePtrs topologyRoutes;
    private Cola.Doubles edgeLengths;
    private int topologyNodeCount;
    private readonly IRandom random = new MersenneTwister();
    private Dictionary<uint, uint> idMap;
    private Dictionary<IVertex, int> indexMap;
    public double IdealEdgeLength { get; set; }
    public double DefaultEdgeLength { get; set; }
    public bool PreventOverlaps { get; set; }
    public int LayoutWidth { get; set; }
    public int LayoutHeight { get; set; }
    public bool PerformEdgeRouting { get; set; }
    public int MinHorizontalSpacing { get; set; }
    public int MinVerticalSpacing { get; set; }
    public EdgeRouting EdgeRoutingMode { get; set; }

    public Dictionary<IVertex, PointF> VertexPositions {
      get {
        var dict = new Dictionary<IVertex, PointF>();
        foreach (var pair in indexMap) {
          var node = topologyNodes[pair.Value];
          var point = new PointF((float)node.rect.getMinX(), (float)node.rect.getMinY());
          dict[pair.Key] = point;
        }
        return dict;
      }
    }

    private List<IArc> arcs;
    public Dictionary<IArc, PointF[]> ArcRoutes {
      get {
        var dict = new Dictionary<IArc, PointF[]>();
        for (int i = 0; i < arcs.Count; ++i) {
          var arc = arcs[i];
          var route = topologyRoutes[i];
          var vs = new TopologyEdgePointConstPtrs();
          route.getPath(vs);
          dict[arc] = vs.Select(x => new PointF((float)x.posX(), (float)x.posY())).ToArray();
        }
        return dict;
      }
    }

    public ConstrainedForceDirectedLayout() {
      IdealEdgeLength = 1;
      DefaultEdgeLength = 200;
      PreventOverlaps = true;
      LayoutWidth = 800;
      LayoutHeight = 600;
      PerformEdgeRouting = true;
      MinHorizontalSpacing = 0;
      MinVerticalSpacing = 0;
      EdgeRoutingMode = EdgeRouting.None;
    }

    public void Run(Dictionary<IVertex, RectangleF> nodeShapes) {
      if (nodeShapes.Count == 0) return;
      indexMap = new Dictionary<IVertex, int>();
      idMap = new Dictionary<uint, uint>();
      var rectangles = new Cola.RectanglePtrs();
      int i = 0;
      arcs = new List<IArc>();
      foreach (var pair in nodeShapes) {
        var v = pair.Key;
        arcs.AddRange(v.InArcs);
        var p = pair.Value;

        var width = p.Size.Width;
        var height = p.Size.Height;

        var x = random.NextDouble() * (LayoutWidth - width);
        var y = random.NextDouble() * (LayoutHeight - height);
        // randomize coordinates before passing them to the layout engine
        var rect = new Cola.Rectangle(x, x + width, y, y + height);
        rectangles.Add(rect);

        indexMap[v] = i;
        ++i;
      }
      topologyNodeCount = i;
      var edges = new ColaEdges(arcs.Select(x => new ColaEdge((uint)indexMap[x.Source], (uint)indexMap[x.Target])).ToList());
      edgeLengths = new Cola.Doubles(Enumerable.Range(0, edges.Count).Select(x => DefaultEdgeLength).ToList());

      layoutEngine = new ConstrainedFDLayout(rectangles, edges, IdealEdgeLength, PreventOverlaps, edgeLengths);
      var clusters = IdentifyClusters(rectangles, edges).ToList();
      if (clusters.Count > 1) {
        var rootCluster = new RootCluster();
        foreach (var cluster in clusters) {
          rootCluster.addChildCluster(cluster);
        }
        layoutEngine.setClusterHierarchy(rootCluster);
      }
      var ccs = new CompoundConstraintPtrs();
      for (i = 0; i < rectangles.Count - 1; ++i) {
        for (int j = i + 1; j < rectangles.Count; ++j) {
          if (MinHorizontalSpacing > 0)
            ccs.Add(new SeparationConstraint(Dim.XDIM, (uint)i, (uint)j, MinHorizontalSpacing, false));
          if (MinVerticalSpacing > 0)
            ccs.Add(new SeparationConstraint(Dim.YDIM, (uint)i, (uint)j, MinVerticalSpacing, false));
        }
      }
      if (ccs.Any()) layoutEngine.setConstraints(ccs);
      var topology = new ColaTopologyAddon();
      layoutEngine.setTopology(topology);
      layoutEngine.makeFeasible();
      // store topology after makeFeasible()
      topology = ColaTopologyAddon.CastToConcreteType(layoutEngine.getTopology());
      layoutEngine.run();

      topologyNodes = topology.topologyNodes;
      topologyRoutes = topology.topologyRoutes;

      if (PerformEdgeRouting) {
        RouteEdges(edges);
      } else {
        int id = topologyNodeCount;
        foreach (var edge in edges) {
          var eps = new TopologyEdgePointPtrs();
          var src = topologyNodes[(int)edge.first];
          var dst = topologyNodes[(int)edge.second];
          eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));
          eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));
          topologyRoutes.Add(new Edge((uint)id++, IdealEdgeLength, eps));
        }
      }
    }

    private static void ColourNeighbours(IVertex v) {
      foreach (var arc in v.InArcs) {
        if (arc.Source.Weight > 0) continue;
        arc.Source.Weight = v.Weight;
        ColourNeighbours(arc.Source);
      }
      foreach (var arc in v.OutArcs) {
        if (arc.Target.Weight > 0) continue;
        arc.Target.Weight = v.Weight;
        ColourNeighbours(arc.Target);
      }
    }

    private static IEnumerable<Cluster> IdentifyClusters(RectanglePtrs rectangles, ColaEdges edges) {
      // build a graph using the rectangles and the edges
      var vertices = new List<IVertex>(rectangles.Select(x => new Vertex()));
      foreach (var e in edges) {
        var i = (int)e.first;
        var j = (int)e.second;
        var arc = new Arc(vertices[i], vertices[j]);
        vertices[i].AddArc(arc);
        vertices[j].AddArc(arc);
      }
      // group vertices into clusters
      var clusters = new List<RectangularCluster>();
      for (int i = 0; i < vertices.Count; ++i) {
        var v = vertices[i];
        if (v.Weight > 0) {
          clusters[(int)Math.Round(v.Weight) - 1].addChildNode((uint)i);
        } else {
          var cluster = new RectangularCluster();
          cluster.addChildNode((uint)i);
          clusters.Add(cluster);
          v.Weight = clusters.Count;
          ColourNeighbours(v);
        }
      }
      return clusters;
    }

    private void RouteEdges(ColaEdges edges) {
      // after the layout is done, we need to use a router to route edges
      RouterFlag rf;
      switch (EdgeRoutingMode) {
        case EdgeRouting.Polyline:
          rf = RouterFlag.PolyLineRouting;
          break;
        case EdgeRouting.Orthogonal:
          rf = RouterFlag.OrthogonalRouting;
          break;
        default:
          rf = RouterFlag.PolyLineRouting;
          break;
      }
      var router = new Router((uint)rf);
      router.setRoutingParameter(RoutingParameter.shapeBufferDistance, 5);
      //router.setRoutingParameter(RoutingParameter.idealNudgingDistance, 0);
      router.UseLeesAlgorithm = true;
      router.InvisibilityGrph = false;
      //router.RubberBandRouting = true;
      var shapes = new List<ShapeRef>();
      // consider topology routes only for the topologyNodes associated with our objects (the rectangles)

      for (int i = 0; i < topologyNodeCount; ++i) {
        var r = topologyNodes[i].rect;
        var poly = new Polygon(4);
        var xmin = r.getMinX();
        var xmax = r.getMaxX();
        var ymin = r.getMinY();
        var ymax = r.getMaxY();

        poly.ps[0] = new Cola.Point(xmax, ymin);
        poly.ps[1] = new Cola.Point(xmax, ymax);
        poly.ps[2] = new Cola.Point(xmin, ymax);
        poly.ps[3] = new Cola.Point(xmin, ymin);
        var shapeRef = new ShapeRef(router, poly);
        idMap[shapeRef.id()] = (uint)i;
        shapes.Add(shapeRef);
      }
      router.processTransaction();

      var connRefs = new List<ConnRef>();
      for (int i = 0; i < edges.Count; ++i) {
        var edge = edges[i];
        var src = topologyNodes[(int)edge.first];
        var dst = topologyNodes[(int)edge.second];
        var srcPt = new Cola.Point(src.rect.getCentreX(), src.rect.getCentreY());
        var dstPt = new Cola.Point(dst.rect.getCentreX(), dst.rect.getCentreY());
        var connRef = new ConnRef(router, new ConnEnd(srcPt), new ConnEnd(dstPt));
        router.processTransaction();

        //        var route = connRef.displayRoute().curvedPolyline(10);
        var route = connRef.displayRoute();
        var eps = new TopologyEdgePointPtrs(); // edge points
        eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));
        for (int j = 1; j < route.size() - 1; ++j) {
          var p = route.ps[j];
          var ri = CalculateIntersect(p);
          if (idMap.ContainsKey(p.id)) {
            var node = topologyNodes[(int)idMap[p.id]];
            eps.Add(new EdgePoint(node, ri));
          } else {
            // the node is not part of the topology and only represents a point in the route polyline
            // therefore, we do not add it to the topologyNodes (although it may need to be treated separately in some cases)
            var id = router.newObjectId();
            var node = new Node(id, new Cola.Rectangle(p.x, p.x + 1, p.y, p.y + 1));
            //topologyNodes.Add(node); 
            idMap[id] = id;
            eps.Add(new EdgePoint(node, ri));
          }
        }
        eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));
        topologyRoutes.Add(new Edge((uint)i, IdealEdgeLength, eps));
        connRefs.Add(connRef);
      }
    }

    public void Run() { }

    public void UpdateNodePosition(IVertex v, PointF point) {
      var node = topologyNodes[indexMap[v]];
    }

    private static EdgePoint.RectIntersect CalculateIntersect(Point p) {
      switch (p.vn) {
        case 0:
          return EdgePoint.RectIntersect.BR;
        case 1:
          return EdgePoint.RectIntersect.TR;
        case 2:
          return EdgePoint.RectIntersect.TL;
        case 3:
          return EdgePoint.RectIntersect.BL;
        default:
          return EdgePoint.RectIntersect.CENTRE;
      }
    }
  }
}