1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Drawing;


25  using System.Linq;


26  using Cola;


27  using HeuristicLab.Core;


28  using Point = Cola.Point;


29 


30  namespace HeuristicLab.VariableInteractionNetworks.Views {


31  public class ConstrainedForceDirectedLayout {


32  #region edge routing modes


33  public enum EdgeRouting : uint {


34  None,


35  Polyline,


36  Orthogonal


37  }


38  #endregion


39 


40  #region layoutrelated private members


41  private ConstrainedFDLayout alg;


42  // graph and constraint definitions


43  private TopologyNodePtrs topologyNodes;


44  private TopologyEdgePtrs topologyRoutes;


45  private RectanglePtrs rectangles;


46  private ColaEdges edges;


47  private Cola.Doubles edgeLengths;


48  //private int topologyNodeCount;


49  private Dictionary<uint, uint> idMap;


50  private Dictionary<IVertex, int> indexMap;


51  #endregion


52 


53  #region public properties


54  public double IdealEdgeLength { get; set; }


55  public double DefaultEdgeLength { get; set; }


56  public bool PreventOverlaps { get; set; }


57  public int LayoutWidth { get; set; }


58  public int LayoutHeight { get; set; }


59  public bool PerformEdgeRouting { get; set; }


60  public int MinHorizontalSpacing { get; set; }


61  public int MinVerticalSpacing { get; set; }


62  public EdgeRouting EdgeRoutingMode { get; set; }


63 


64  public Dictionary<IVertex, PointF> VertexPositions {


65  get {


66  var dict = new Dictionary<IVertex, PointF>();


67  foreach (var pair in indexMap) {


68  var node = topologyNodes[pair.Value];


69  var point = new PointF((float)node.rect.getMinX(), (float)node.rect.getMinY());


70  dict[pair.Key] = point;


71  }


72  return dict;


73  }


74  }


75 


76  private List<IArc> arcs;


77  public Dictionary<IArc, PointF[]> ArcRoutes {


78  get {


79  var dict = new Dictionary<IArc, PointF[]>();


80  for (int i = 0; i < arcs.Count; ++i) {


81  var arc = arcs[i];


82  var route = topologyRoutes[i];


83  var vs = new TopologyEdgePointConstPtrs();


84  route.getPath(vs);


85  dict[arc] = vs.Select(x => new PointF((float)x.posX(), (float)x.posY())).ToArray();


86  }


87  return dict;


88  }


89  }


90  #endregion


91 


92  public ConstrainedForceDirectedLayout() {


93  IdealEdgeLength = 1;


94  DefaultEdgeLength = 200;


95  PreventOverlaps = true;


96  LayoutWidth = 800;


97  LayoutHeight = 600;


98  MinHorizontalSpacing = 0;


99  MinVerticalSpacing = 0;


100  EdgeRoutingMode = EdgeRouting.None;


101  }


102 


103  /// <summary>


104  /// 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


105  /// </summary>


106  /// <param name="nodeShapes">The dictionary mapping graph vertices to rectangular shapes.</param>


107  public void Run(Dictionary<IVertex, RectangleF> nodeShapes) {


108  if (nodeShapes.Count == 0) return;


109  // map vertices to node indices required by cola


110  indexMap = new Dictionary<IVertex, int>();


111  idMap = new Dictionary<uint, uint>();


112  rectangles = new Cola.RectanglePtrs();


113  int i = 0;


114  arcs = new List<IArc>();


115  topologyNodes = new TopologyNodePtrs();


116  foreach (var pair in nodeShapes) {


117  var v = pair.Key;


118  arcs.AddRange(v.InArcs);


119  var p = pair.Value;


120  var rect = new Cola.Rectangle(p.X, p.X + p.Width, p.Y, p.Y + p.Height);


121  rectangles.Add(rect);


122 


123  indexMap[v] = i;


124  topologyNodes.Add(new Cola.Node((uint)i, rect));


125 


126  ++i;


127  }


128  //topologyNodeCount = i;


129  edges = new ColaEdges(arcs.Select(x => new ColaEdge((uint)indexMap[x.Source], (uint)indexMap[x.Target])).ToList());


130  edgeLengths = new Cola.Doubles(Enumerable.Range(0, edges.Count).Select(x => DefaultEdgeLength).ToList());


131 


132  // initialize the layout engine using the rectangles, edges, and desired settings


133  alg = new ConstrainedFDLayout(rectangles, edges, IdealEdgeLength, edgeLengths);


134  alg.setAvoidNodeOverlaps(PreventOverlaps); // prevent overlap of node shapes


135 


136  // identify clusters and configure cluster hierarchy


137  var clusters = IdentifyClusters(rectangles, edges).ToList();


138  if (clusters.Count > 1) {


139  var rootCluster = new RootCluster();


140  foreach (var cluster in clusters) {


141  rootCluster.addChildCluster(cluster);


142  }


143  alg.setClusterHierarchy(rootCluster);


144  }


145 


146  var topology = new ColaTopologyAddon();


147  alg.setTopology(topology);


148  alg.makeFeasible();


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


150 


151  topologyNodes = newTopology.topologyNodes;


152  topologyRoutes = newTopology.topologyRoutes;


153 


154  RouteEdges();


155  // finally, run the layout engine (the positions of the rectangles will be updated)


156  alg.run();


157  }


158 


159  public void Run(bool preserveTopology = true) {


160  if (preserveTopology) {


161  RouteEdges();


162  var topology = new ColaTopologyAddon(topologyNodes, topologyRoutes);


163  alg.setTopology(topology);


164  }


165  alg.run();


166  }


167 


168  /// <summary>


169  /// This method is used internally by the @IdentifyClusters method to separate vertices by color


170  /// (vertices of the same subgraph will have the same color)


171  /// </summary>


172  /// <param name="v">The starting vertex from which all adjacent vertices will be colored.</param>


173  private static void ColourNeighbours(IVertex v) {


174  foreach (var arc in v.InArcs) {


175  if (arc.Source.Weight > 0) continue;


176  arc.Source.Weight = v.Weight;


177  ColourNeighbours(arc.Source);


178  }


179  foreach (var arc in v.OutArcs) {


180  if (arc.Target.Weight > 0) continue;


181  arc.Target.Weight = v.Weight;


182  ColourNeighbours(arc.Target);


183  }


184  }


185 


186  /// <summary>


187  /// Method used to identify the disconnected components of the graph, so that they can be layouted separately and placed in nonoverlapping areas of the drawing region.


188  /// </summary>


189  /// <param name="rectangles">The rectangles corresponding to the graph nodes.</param>


190  /// <param name="edges">The edges connecting the rectangles.</param>


191  /// <returns>A list of clusters representing the disconnected components.</returns>


192  private static IEnumerable<Cluster> IdentifyClusters(RectanglePtrs rectangles, ColaEdges edges) {


193  // build a graph using the rectangles and the edges


194  var vertices = new List<IVertex>(rectangles.Select(x => new Vertex()));


195  foreach (var e in edges) {


196  var i = (int)e.first;


197  var j = (int)e.second;


198  var arc = new Arc(vertices[i], vertices[j]);


199  vertices[i].AddArc(arc);


200  vertices[j].AddArc(arc);


201  }


202  // group vertices into clusters


203  var clusters = new List<RectangularCluster>();


204  for (int i = 0; i < vertices.Count; ++i) {


205  var v = vertices[i];


206  if (v.Weight > 0) {


207  clusters[(int)Math.Round(v.Weight)  1].addChildNode((uint)i);


208  } else {


209  var cluster = new RectangularCluster();


210  cluster.addChildNode((uint)i);


211  clusters.Add(cluster);


212  v.Weight = clusters.Count;


213  ColourNeighbours(v);


214  }


215  }


216  return clusters;


217  }


218 


219  /// <summary>


220  /// This method performs edge routing, meaning that edges are moved such that they go around the nodes.


221  /// Routing can produce polyline or orthogonal graph edges.


222  /// </summary>


223  private void RouteEdges() {


224  topologyRoutes = new TopologyEdgePtrs();


225  // after the layout is done, we need to use a router to route edges


226  RouterFlag rf;


227  switch (EdgeRoutingMode) {


228  case EdgeRouting.Polyline:


229  rf = RouterFlag.PolyLineRouting;


230  break;


231  case EdgeRouting.Orthogonal:


232  rf = RouterFlag.OrthogonalRouting;


233  break;


234  default:


235  var id = topologyNodes.Count;


236  foreach (var edge in edges) {


237  var eps = new TopologyEdgePointPtrs();


238  var src = topologyNodes[(int)edge.first];


239  var dst = topologyNodes[(int)edge.second];


240  eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));


241  eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));


242  topologyRoutes.Add(new Edge((uint)id++, IdealEdgeLength, eps));


243  }


244  return;


245  }


246  var router = new Router((uint)rf);


247  // set the minimal distance by which nodes should be avoided by the router


248  router.setRoutingParameter(RoutingParameter.shapeBufferDistance, 5);


249  router.UseLeesAlgorithm = true;


250  router.InvisibilityGrph = false;


251  // consider topology routes only for the topologyNodes associated with our objects (the rectangles)


252  for (int i = 0; i < topologyNodes.Count; ++i) {


253  var r = topologyNodes[i].rect;


254  var poly = new Polygon(4);


255  var xmin = r.getMinX();


256  var xmax = r.getMaxX();


257  var ymin = r.getMinY();


258  var ymax = r.getMaxY();


259 


260  poly.ps[0] = new Cola.Point(xmax, ymin);


261  poly.ps[1] = new Cola.Point(xmax, ymax);


262  poly.ps[2] = new Cola.Point(xmin, ymax);


263  poly.ps[3] = new Cola.Point(xmin, ymin);


264  var shapeRef = new ShapeRef(router, poly);


265  idMap[shapeRef.id()] = (uint)i;


266  }


267  router.processTransaction();


268 


269  for (int i = 0; i < edges.Count; ++i) {


270  var edge = edges[i];


271  var src = topologyNodes[(int)edge.first];


272  var dst = topologyNodes[(int)edge.second];


273  var srcPt = new Cola.Point(src.rect.getCentreX(), src.rect.getCentreY());


274  var dstPt = new Cola.Point(dst.rect.getCentreX(), dst.rect.getCentreY());


275  var connRef = new ConnRef(router, new ConnEnd(srcPt), new ConnEnd(dstPt));


276  router.processTransaction();


277 


278  // var route = connRef.displayRoute().curvedPolyline(10);


279  var route = connRef.displayRoute();


280  var eps = new TopologyEdgePointPtrs(); // edge points


281  eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));


282  for (int j = 1; j < route.size()  1; ++j) {


283  var p = route.ps[j];


284  var ri = CalculateIntersect(p);


285  if (idMap.ContainsKey(p.id)) {


286  var node = topologyNodes[(int)idMap[p.id]];


287  eps.Add(new EdgePoint(node, ri));


288  } else {


289  // the node is not part of the topology and only represents a point in the route polyline


290  // therefore, we do not add it to the topologyNodes (although it may need to be treated separately in some cases)


291  var id = router.newObjectId();


292  var node = new Node(id, new Cola.Rectangle(p.x, p.x + 1, p.y, p.y + 1));


293  idMap[id] = id;


294  eps.Add(new EdgePoint(node, ri));


295  }


296  }


297  eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));


298  topologyRoutes.Add(new Edge((uint)i, IdealEdgeLength, eps));


299  }


300  }


301 


302  /// <summary>


303  /// Save the layouted graph to a svg file


304  /// </summary>


305  /// <param name="path">The save path.</param>


306  public void OutputInstanceToSVG(string path) {


307  alg.outputInstanceToSVG(path);


308  }


309 


310  private static EdgePoint.RectIntersect CalculateIntersect(Point p) {


311  switch (p.vn) {


312  case 0:


313  return EdgePoint.RectIntersect.BR;


314  case 1:


315  return EdgePoint.RectIntersect.TR;


316  case 2:


317  return EdgePoint.RectIntersect.TL;


318  case 3:


319  return EdgePoint.RectIntersect.BL;


320  default:


321  return EdgePoint.RectIntersect.CENTRE;


322  }


323  }


324  }


325  }

