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

Last change on this file since 14283 was 14283, checked in by bburlacu, 5 years ago

#2288: Small refactor

File size: 12.5 KB
Line 
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;
26using Cola;
27using HeuristicLab.Core;
28using Point = Cola.Point;
29
30namespace 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 layout-related 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 non-overlapping 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}
Note: See TracBrowser for help on using the repository browser.