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

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

#2288: Clean up code and add comments in the ConstrainedForceDirectedLayout class. Minor changes to view and directed graph chart. Introduced an INetworkNode interface for more flexibility. Updated cola and adaptagrams dlls with latest changes from upstream.

File size: 12.3 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 = topologyNodeCount;
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 < topologyNodeCount; ++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    public void OutputInstanceToSVG(string path) {
303      alg.outputInstanceToSVG(path);
304    }
305
306    private static EdgePoint.RectIntersect CalculateIntersect(Point p) {
307      switch (p.vn) {
308        case 0:
309          return EdgePoint.RectIntersect.BR;
310        case 1:
311          return EdgePoint.RectIntersect.TR;
312        case 2:
313          return EdgePoint.RectIntersect.TL;
314        case 3:
315          return EdgePoint.RectIntersect.BL;
316        default:
317          return EdgePoint.RectIntersect.CENTRE;
318      }
319    }
320  }
321}
Note: See TracBrowser for help on using the repository browser.