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

#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 Point = Cola.Point;

namespace HeuristicLab.VariableInteractionNetworks.Views {
  public class ConstrainedForceDirectedLayout {
    #region edge routing modes 
    public enum EdgeRouting : uint {
      None,
      Polyline,
      Orthogonal
    }
    #endregion

    #region layout-related private members 
    private ConstrainedFDLayout alg;
    // graph and constraint definitions
    private TopologyNodePtrs topologyNodes;
    private TopologyEdgePtrs topologyRoutes;
    private RectanglePtrs rectangles;
    private ColaEdges edges;
    private Cola.Doubles edgeLengths;
    //private int topologyNodeCount;
    private Dictionary<uint, uint> idMap;
    private Dictionary<IVertex, int> indexMap;
    #endregion

    #region public properties
    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;
      }
    }
    #endregion

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

    /// <summary>
    /// This method accepts a dictionary mapping each vertex to a rectangular shape, so that the layout is aware of each node's width and height
    /// </summary>
    /// <param name="nodeShapes">The dictionary mapping graph vertices to rectangular shapes.</param>
    public void Run(Dictionary<IVertex, RectangleF> nodeShapes) {
      if (nodeShapes.Count == 0) return;
      // map vertices to node indices required by cola
      indexMap = new Dictionary<IVertex, int>();
      idMap = new Dictionary<uint, uint>();
      rectangles = new Cola.RectanglePtrs();
      int i = 0;
      arcs = new List<IArc>();
      topologyNodes = new TopologyNodePtrs();
      foreach (var pair in nodeShapes) {
        var v = pair.Key;
        arcs.AddRange(v.InArcs);
        var p = pair.Value;
        var rect = new Cola.Rectangle(p.X, p.X + p.Width, p.Y, p.Y + p.Height);
        rectangles.Add(rect);

        indexMap[v] = i;
        topologyNodes.Add(new Cola.Node((uint)i, rect));

        ++i;
      }
      //topologyNodeCount = i;
      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());

      // initialize the layout engine using the rectangles, edges, and desired settings 
      alg = new ConstrainedFDLayout(rectangles, edges, IdealEdgeLength, edgeLengths);
      alg.setAvoidNodeOverlaps(PreventOverlaps); // prevent overlap of node shapes

      // identify clusters and configure cluster hierarchy
      var clusters = IdentifyClusters(rectangles, edges).ToList();
      if (clusters.Count > 1) {
        var rootCluster = new RootCluster();
        foreach (var cluster in clusters) {
          rootCluster.addChildCluster(cluster);
        }
        alg.setClusterHierarchy(rootCluster);
      }

      var topology = new ColaTopologyAddon();
      alg.setTopology(topology);
      alg.makeFeasible();
      var newTopology = ColaTopologyAddon.CastToConcreteType(alg.getTopology()); // store topology after makeFeasible()

      topologyNodes = newTopology.topologyNodes;
      topologyRoutes = newTopology.topologyRoutes;

      RouteEdges();
      // finally, run the layout engine (the positions of the rectangles will be updated)
      alg.run();
    }

    public void Run(bool preserveTopology = true) {
      if (preserveTopology) {
        RouteEdges();
        var topology = new ColaTopologyAddon(topologyNodes, topologyRoutes);
        alg.setTopology(topology);
      }
      alg.run();
    }

    /// <summary>
    /// This method is used internally by the @IdentifyClusters method to separate vertices by color 
    /// (vertices of the same subgraph will have the same color)
    /// </summary>
    /// <param name="v">The starting vertex from which all adjacent vertices will be colored.</param>
    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);
      }
    }

    /// <summary>
    /// Method used to identify the disconnected components of the graph, so that they can be layouted separately and placed in non-overlapping areas of the drawing region.
    /// </summary>
    /// <param name="rectangles">The rectangles corresponding to the graph nodes.</param>
    /// <param name="edges">The edges connecting the rectangles.</param>
    /// <returns>A list of clusters representing the disconnected components.</returns>
    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;
    }

    /// <summary>
    /// This method performs edge routing, meaning that edges are moved such that they go around the nodes.
    /// Routing can produce polyline or orthogonal graph edges.
    /// </summary>
    private void RouteEdges() {
      topologyRoutes = new TopologyEdgePtrs();
      // 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:
          var id = topologyNodes.Count;
          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));
          }
          return;
      }
      var router = new Router((uint)rf);
      // set the minimal distance by which nodes should be avoided by the router
      router.setRoutingParameter(RoutingParameter.shapeBufferDistance, 5);
      router.UseLeesAlgorithm = true;
      router.InvisibilityGrph = false;
      // consider topology routes only for the topologyNodes associated with our objects (the rectangles)
      for (int i = 0; i < topologyNodes.Count; ++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;
      }
      router.processTransaction();

      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));
            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));
      }
    }

    /// <summary>
    /// Save the layouted graph to a svg file
    /// </summary>
    /// <param name="path">The save path.</param>
    public void OutputInstanceToSVG(string path) {
      alg.outputInstanceToSVG(path);
    }

    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;
      }
    }
  }
}