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 |
|
---|
22 | using System;
|
---|
23 | using System.Collections.Generic;
|
---|
24 | using System.Drawing;
|
---|
25 | using System.Linq;
|
---|
26 | using Cola;
|
---|
27 | using HeuristicLab.Common;
|
---|
28 | using HeuristicLab.Core;
|
---|
29 | using HeuristicLab.Random;
|
---|
30 | using Point = Cola.Point;
|
---|
31 |
|
---|
32 | namespace HeuristicLab.VariableInteractionNetworks.Views {
|
---|
33 | public class ConstrainedForceDirectedLayout {
|
---|
34 | public enum EdgeRouting : uint {
|
---|
35 | None,
|
---|
36 | Polyline,
|
---|
37 | Orthogonal
|
---|
38 | }
|
---|
39 | private ConstrainedFDLayout layoutEngine;
|
---|
40 | private TopologyNodePtrs topologyNodes;
|
---|
41 | private TopologyEdgePtrs topologyRoutes;
|
---|
42 | private Cola.Doubles edgeLengths;
|
---|
43 | private int topologyNodeCount;
|
---|
44 | private readonly IRandom random = new MersenneTwister();
|
---|
45 | private Dictionary<uint, uint> idMap;
|
---|
46 | private Dictionary<IVertex, int> indexMap;
|
---|
47 | public double IdealEdgeLength { get; set; } = 1;
|
---|
48 | public double DefaultEdgeLength { get; set; } = 200;
|
---|
49 | public bool PreventOverlaps { get; set; } = true;
|
---|
50 | public int LayoutWidth { get; set; } = 800;
|
---|
51 | public int LayoutHeight { get; set; } = 600;
|
---|
52 | public bool PerformEdgeRouting { get; set; } = true;
|
---|
53 | public int MinHorizontalSpacing { get; set; } = 0;
|
---|
54 | public int MinVerticalSpacing { get; set; } = 0;
|
---|
55 | public EdgeRouting EdgeRoutingMode { get; set; } = EdgeRouting.None;
|
---|
56 |
|
---|
57 | public Dictionary<IVertex, PointF> VertexPositions {
|
---|
58 | get {
|
---|
59 | var dict = new Dictionary<IVertex, PointF>();
|
---|
60 | foreach (var pair in indexMap) {
|
---|
61 | var node = topologyNodes[pair.Value];
|
---|
62 | var point = new PointF((float)node.rect.getMinX(), (float)node.rect.getMinY());
|
---|
63 | dict[pair.Key] = point;
|
---|
64 | }
|
---|
65 | return dict;
|
---|
66 | }
|
---|
67 | }
|
---|
68 |
|
---|
69 | private List<IArc> arcs;
|
---|
70 | public Dictionary<IArc, PointF[]> ArcRoutes {
|
---|
71 | get {
|
---|
72 | var dict = new Dictionary<IArc, PointF[]>();
|
---|
73 | for (int i = 0; i < arcs.Count; ++i) {
|
---|
74 | var arc = arcs[i];
|
---|
75 | var route = topologyRoutes[i];
|
---|
76 | var vs = new TopologyEdgePointConstPtrs();
|
---|
77 | route.getPath(vs);
|
---|
78 | dict[arc] = vs.Select(x => new PointF((float)x.posX(), (float)x.posY())).ToArray();
|
---|
79 | }
|
---|
80 | return dict;
|
---|
81 | }
|
---|
82 | }
|
---|
83 |
|
---|
84 | public ConstrainedForceDirectedLayout() { }
|
---|
85 |
|
---|
86 | public void Run(Dictionary<IVertex, RectangleF> nodeShapes) {
|
---|
87 | if (nodeShapes.Count == 0) return;
|
---|
88 | indexMap = new Dictionary<IVertex, int>();
|
---|
89 | idMap = new Dictionary<uint, uint>();
|
---|
90 | var rectangles = new Cola.RectanglePtrs();
|
---|
91 | int i = 0;
|
---|
92 | arcs = new List<IArc>();
|
---|
93 | foreach (var pair in nodeShapes) {
|
---|
94 | var v = pair.Key;
|
---|
95 | arcs.AddRange(v.InArcs);
|
---|
96 | var p = pair.Value;
|
---|
97 |
|
---|
98 | var width = p.Size.Width;
|
---|
99 | var height = p.Size.Height;
|
---|
100 |
|
---|
101 | var x = random.NextDouble() * (LayoutWidth - width);
|
---|
102 | var y = random.NextDouble() * (LayoutHeight - height);
|
---|
103 | // randomize coordinates before passing them to the layout engine
|
---|
104 | var rect = new Cola.Rectangle(x, x + width, y, y + height);
|
---|
105 | rectangles.Add(rect);
|
---|
106 |
|
---|
107 | indexMap[v] = i;
|
---|
108 | ++i;
|
---|
109 | }
|
---|
110 | topologyNodeCount = i;
|
---|
111 | var edges = new ColaEdges(arcs.Select(x => new ColaEdge((uint)indexMap[x.Source], (uint)indexMap[x.Target])).ToList());
|
---|
112 | edgeLengths = new Cola.Doubles(Enumerable.Range(0, edges.Count).Select(x => DefaultEdgeLength).ToList());
|
---|
113 |
|
---|
114 | layoutEngine = new ConstrainedFDLayout(rectangles, edges, IdealEdgeLength, PreventOverlaps, edgeLengths);
|
---|
115 | var clusters = IdentifyClusters(rectangles, edges).ToList();
|
---|
116 | if (clusters.Count > 1) {
|
---|
117 | var rootCluster = new RootCluster();
|
---|
118 | foreach (var cluster in clusters) {
|
---|
119 | rootCluster.addChildCluster(cluster);
|
---|
120 | }
|
---|
121 | layoutEngine.setClusterHierarchy(rootCluster);
|
---|
122 | }
|
---|
123 | var ccs = new CompoundConstraintPtrs();
|
---|
124 | for (i = 0; i < rectangles.Count - 1; ++i) {
|
---|
125 | for (int j = i + 1; j < rectangles.Count; ++j) {
|
---|
126 | if (MinHorizontalSpacing > 0)
|
---|
127 | ccs.Add(new SeparationConstraint(Dim.XDIM, (uint)i, (uint)j, MinHorizontalSpacing, false));
|
---|
128 | if (MinVerticalSpacing > 0)
|
---|
129 | ccs.Add(new SeparationConstraint(Dim.YDIM, (uint)i, (uint)j, MinVerticalSpacing, false));
|
---|
130 | }
|
---|
131 | }
|
---|
132 | if (ccs.Any()) layoutEngine.setConstraints(ccs);
|
---|
133 | var topology = new ColaTopologyAddon();
|
---|
134 | layoutEngine.setTopology(topology);
|
---|
135 | layoutEngine.makeFeasible();
|
---|
136 | // store topology after makeFeasible()
|
---|
137 | topology = ColaTopologyAddon.CastToConcreteType(layoutEngine.getTopology());
|
---|
138 | layoutEngine.run();
|
---|
139 |
|
---|
140 | topologyNodes = topology.topologyNodes;
|
---|
141 | topologyRoutes = topology.topologyRoutes;
|
---|
142 |
|
---|
143 | if (PerformEdgeRouting) {
|
---|
144 | RouteEdges(edges);
|
---|
145 | } else {
|
---|
146 | int id = topologyNodeCount;
|
---|
147 | foreach (var edge in edges) {
|
---|
148 | var eps = new TopologyEdgePointPtrs();
|
---|
149 | var src = topologyNodes[(int)edge.first];
|
---|
150 | var dst = topologyNodes[(int)edge.second];
|
---|
151 | eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));
|
---|
152 | eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));
|
---|
153 | topologyRoutes.Add(new Edge((uint)id++, IdealEdgeLength, eps));
|
---|
154 | }
|
---|
155 | }
|
---|
156 | }
|
---|
157 |
|
---|
158 | private static void ColourNeighbours(IVertex v) {
|
---|
159 | foreach (var arc in v.InArcs) {
|
---|
160 | if (arc.Source.Weight > 0) continue;
|
---|
161 | arc.Source.Weight = v.Weight;
|
---|
162 | ColourNeighbours(arc.Source);
|
---|
163 | }
|
---|
164 | foreach (var arc in v.OutArcs) {
|
---|
165 | if (arc.Target.Weight > 0) continue;
|
---|
166 | arc.Target.Weight = v.Weight;
|
---|
167 | ColourNeighbours(arc.Target);
|
---|
168 | }
|
---|
169 | }
|
---|
170 |
|
---|
171 | private static IEnumerable<Cluster> IdentifyClusters(RectanglePtrs rectangles, ColaEdges edges) {
|
---|
172 | var vertices = rectangles.Select(x => new Vertex()).ToList();
|
---|
173 | foreach (var e in edges) {
|
---|
174 | var i = (int)e.first;
|
---|
175 | var j = (int)e.second;
|
---|
176 | var arc = new Arc(vertices[i], vertices[j]);
|
---|
177 | vertices[i].AddArc(arc);
|
---|
178 | vertices[j].AddArc(arc);
|
---|
179 | }
|
---|
180 | while (vertices.Min(x => x.Weight).IsAlmost(0)) {
|
---|
181 | foreach (var v in vertices) {
|
---|
182 | if (v.Weight > 0) continue;
|
---|
183 | v.Weight = vertices.Max(x => x.Weight) + 1;
|
---|
184 | ColourNeighbours(v);
|
---|
185 | }
|
---|
186 | }
|
---|
187 | var colors = vertices.Select(x => (int)Math.Round(x.Weight)).ToList();
|
---|
188 | foreach (var i in colors.Distinct()) {
|
---|
189 | var cluster = new RectangularCluster();
|
---|
190 | for (int j = 0; j < colors.Count; ++j) {
|
---|
191 | if (colors[j] == i) cluster.addChildNode((uint)j);
|
---|
192 | }
|
---|
193 | yield return cluster;
|
---|
194 | }
|
---|
195 | }
|
---|
196 |
|
---|
197 | private void RouteEdges(ColaEdges edges) {
|
---|
198 | // after the layout is done, we need to use a router to route edges
|
---|
199 | RouterFlag rf;
|
---|
200 | switch (EdgeRoutingMode) {
|
---|
201 | case EdgeRouting.Polyline:
|
---|
202 | rf = RouterFlag.PolyLineRouting;
|
---|
203 | break;
|
---|
204 | case EdgeRouting.Orthogonal:
|
---|
205 | rf = RouterFlag.OrthogonalRouting;
|
---|
206 | break;
|
---|
207 | default:
|
---|
208 | rf = RouterFlag.PolyLineRouting;
|
---|
209 | break;
|
---|
210 | }
|
---|
211 | var router = new Router((uint)rf);
|
---|
212 | router.setRoutingParameter(RoutingParameter.shapeBufferDistance, 5);
|
---|
213 | //router.setRoutingParameter(RoutingParameter.idealNudgingDistance, 0);
|
---|
214 | router.UseLeesAlgorithm = true;
|
---|
215 | router.InvisibilityGrph = false;
|
---|
216 | //router.RubberBandRouting = true;
|
---|
217 | var shapes = new List<ShapeRef>();
|
---|
218 | // consider topology routes only for the topologyNodes associated with our objects (the rectangles)
|
---|
219 |
|
---|
220 | for (int i = 0; i < topologyNodeCount; ++i) {
|
---|
221 | var r = topologyNodes[i].rect;
|
---|
222 | var poly = new Polygon(4);
|
---|
223 | var xmin = r.getMinX();
|
---|
224 | var xmax = r.getMaxX();
|
---|
225 | var ymin = r.getMinY();
|
---|
226 | var ymax = r.getMaxY();
|
---|
227 |
|
---|
228 | poly.ps[0] = new Cola.Point(xmax, ymin);
|
---|
229 | poly.ps[1] = new Cola.Point(xmax, ymax);
|
---|
230 | poly.ps[2] = new Cola.Point(xmin, ymax);
|
---|
231 | poly.ps[3] = new Cola.Point(xmin, ymin);
|
---|
232 | var shapeRef = new ShapeRef(router, poly);
|
---|
233 | idMap[shapeRef.id()] = (uint)i;
|
---|
234 | shapes.Add(shapeRef);
|
---|
235 | }
|
---|
236 | router.processTransaction();
|
---|
237 |
|
---|
238 | var connRefs = new List<ConnRef>();
|
---|
239 | for (int i = 0; i < edges.Count; ++i) {
|
---|
240 | var edge = edges[i];
|
---|
241 | var src = topologyNodes[(int)edge.first];
|
---|
242 | var dst = topologyNodes[(int)edge.second];
|
---|
243 | var srcPt = new Cola.Point(src.rect.getCentreX(), src.rect.getCentreY());
|
---|
244 | var dstPt = new Cola.Point(dst.rect.getCentreX(), dst.rect.getCentreY());
|
---|
245 | var connRef = new ConnRef(router, new ConnEnd(srcPt), new ConnEnd(dstPt));
|
---|
246 | router.processTransaction();
|
---|
247 |
|
---|
248 | // var route = connRef.displayRoute().curvedPolyline(10);
|
---|
249 | var route = connRef.displayRoute();
|
---|
250 | var eps = new TopologyEdgePointPtrs(); // edge points
|
---|
251 | eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));
|
---|
252 | for (int j = 1; j < route.size() - 1; ++j) {
|
---|
253 | var p = route.ps[j];
|
---|
254 | var ri = CalculateIntersect(p);
|
---|
255 | if (idMap.ContainsKey(p.id)) {
|
---|
256 | var node = topologyNodes[(int)idMap[p.id]];
|
---|
257 | eps.Add(new EdgePoint(node, ri));
|
---|
258 | } else {
|
---|
259 | // the node is not part of the topology and only represents a point in the route polyline
|
---|
260 | // therefore, we do not add it to the topologyNodes (although it may need to be treated separately in some cases)
|
---|
261 | var id = router.newObjectId();
|
---|
262 | var node = new Node(id, new Cola.Rectangle(p.x, p.x + 1, p.y, p.y + 1));
|
---|
263 | //topologyNodes.Add(node);
|
---|
264 | idMap[id] = id;
|
---|
265 | eps.Add(new EdgePoint(node, ri));
|
---|
266 | }
|
---|
267 | }
|
---|
268 | eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));
|
---|
269 | topologyRoutes.Add(new Edge((uint)i, IdealEdgeLength, eps));
|
---|
270 | connRefs.Add(connRef);
|
---|
271 | }
|
---|
272 | }
|
---|
273 |
|
---|
274 | public void Run() { }
|
---|
275 |
|
---|
276 | public void UpdateNodePosition(IVertex v, PointF point) {
|
---|
277 | var node = topologyNodes[indexMap[v]];
|
---|
278 | }
|
---|
279 |
|
---|
280 | private static EdgePoint.RectIntersect CalculateIntersect(Point p) {
|
---|
281 | switch (p.vn) {
|
---|
282 | case 0:
|
---|
283 | return EdgePoint.RectIntersect.BR;
|
---|
284 | case 1:
|
---|
285 | return EdgePoint.RectIntersect.TR;
|
---|
286 | case 2:
|
---|
287 | return EdgePoint.RectIntersect.TL;
|
---|
288 | case 3:
|
---|
289 | return EdgePoint.RectIntersect.BL;
|
---|
290 | default:
|
---|
291 | return EdgePoint.RectIntersect.CENTRE;
|
---|
292 | }
|
---|
293 | }
|
---|
294 | }
|
---|
295 | }
|
---|