Changeset 14275 for branches/HeuristicLab.VariableInteractionNetworks/HeuristicLab.VariableInteractionNetworks.Views/3.3/Layout/ConstrainedForceDirectedLayout.cs
- Timestamp:
- 09/07/16 15:20:29 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.VariableInteractionNetworks/HeuristicLab.VariableInteractionNetworks.Views/3.3/Layout/ConstrainedForceDirectedLayout.cs
r13893 r14275 26 26 using Cola; 27 27 using HeuristicLab.Core; 28 using HeuristicLab.Random;29 28 using Point = Cola.Point; 30 29 31 30 namespace HeuristicLab.VariableInteractionNetworks.Views { 32 31 public class ConstrainedForceDirectedLayout { 32 #region edge routing modes 33 33 public enum EdgeRouting : uint { 34 34 None, … … 36 36 Orthogonal 37 37 } 38 private ConstrainedFDLayout layoutEngine; 38 #endregion 39 40 #region layout-related private members 41 private ConstrainedFDLayout alg; 42 // graph and constraint definitions 39 43 private TopologyNodePtrs topologyNodes; 40 44 private TopologyEdgePtrs topologyRoutes; 45 private RectanglePtrs rectangles; 46 private ColaEdges edges; 41 47 private Cola.Doubles edgeLengths; 42 48 private int topologyNodeCount; 43 private readonly IRandom random = new MersenneTwister();44 49 private Dictionary<uint, uint> idMap; 45 50 private Dictionary<IVertex, int> indexMap; 51 #endregion 52 53 #region public properties 46 54 public double IdealEdgeLength { get; set; } 47 55 public double DefaultEdgeLength { get; set; } … … 80 88 } 81 89 } 90 #endregion 82 91 83 92 public ConstrainedForceDirectedLayout() { … … 87 96 LayoutWidth = 800; 88 97 LayoutHeight = 600; 89 PerformEdgeRouting = true;90 98 MinHorizontalSpacing = 0; 91 99 MinVerticalSpacing = 0; … … 93 101 } 94 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> 95 107 public void Run(Dictionary<IVertex, RectangleF> nodeShapes) { 96 108 if (nodeShapes.Count == 0) return; 109 // map vertices to node indices required by cola 97 110 indexMap = new Dictionary<IVertex, int>(); 98 111 idMap = new Dictionary<uint, uint>(); 99 varrectangles = new Cola.RectanglePtrs();112 rectangles = new Cola.RectanglePtrs(); 100 113 int i = 0; 101 114 arcs = new List<IArc>(); 115 topologyNodes = new TopologyNodePtrs(); 102 116 foreach (var pair in nodeShapes) { 103 117 var v = pair.Key; 104 118 arcs.AddRange(v.InArcs); 105 119 var p = pair.Value; 106 107 var width = p.Size.Width; 108 var height = p.Size.Height; 109 110 var x = random.NextDouble() * (LayoutWidth - width); 111 var y = random.NextDouble() * (LayoutHeight - height); 112 // randomize coordinates before passing them to the layout engine 113 var rect = new Cola.Rectangle(x, x + width, y, y + height); 120 var rect = new Cola.Rectangle(p.X, p.X + p.Width, p.Y, p.Y + p.Height); 114 121 rectangles.Add(rect); 115 122 116 123 indexMap[v] = i; 124 topologyNodes.Add(new Cola.Node((uint)i, rect)); 125 117 126 ++i; 118 127 } 119 128 topologyNodeCount = i; 120 varedges = new ColaEdges(arcs.Select(x => new ColaEdge((uint)indexMap[x.Source], (uint)indexMap[x.Target])).ToList());129 edges = new ColaEdges(arcs.Select(x => new ColaEdge((uint)indexMap[x.Source], (uint)indexMap[x.Target])).ToList()); 121 130 edgeLengths = new Cola.Doubles(Enumerable.Range(0, edges.Count).Select(x => DefaultEdgeLength).ToList()); 122 131 123 layoutEngine = new ConstrainedFDLayout(rectangles, edges, IdealEdgeLength, PreventOverlaps, edgeLengths); 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 124 137 var clusters = IdentifyClusters(rectangles, edges).ToList(); 125 138 if (clusters.Count > 1) { … … 128 141 rootCluster.addChildCluster(cluster); 129 142 } 130 layoutEngine.setClusterHierarchy(rootCluster); 131 } 132 var ccs = new CompoundConstraintPtrs(); 133 for (i = 0; i < rectangles.Count - 1; ++i) { 134 for (int j = i + 1; j < rectangles.Count; ++j) { 135 if (MinHorizontalSpacing > 0) 136 ccs.Add(new SeparationConstraint(Dim.XDIM, (uint)i, (uint)j, MinHorizontalSpacing, false)); 137 if (MinVerticalSpacing > 0) 138 ccs.Add(new SeparationConstraint(Dim.YDIM, (uint)i, (uint)j, MinVerticalSpacing, false)); 139 } 140 } 141 if (ccs.Any()) layoutEngine.setConstraints(ccs); 143 alg.setClusterHierarchy(rootCluster); 144 } 145 142 146 var topology = new ColaTopologyAddon(); 143 layoutEngine.setTopology(topology); 144 layoutEngine.makeFeasible(); 145 // store topology after makeFeasible() 146 topology = ColaTopologyAddon.CastToConcreteType(layoutEngine.getTopology()); 147 layoutEngine.run(); 148 149 topologyNodes = topology.topologyNodes; 150 topologyRoutes = topology.topologyRoutes; 151 152 if (PerformEdgeRouting) { 153 RouteEdges(edges); 154 } else { 155 int id = topologyNodeCount; 156 foreach (var edge in edges) { 157 var eps = new TopologyEdgePointPtrs(); 158 var src = topologyNodes[(int)edge.first]; 159 var dst = topologyNodes[(int)edge.second]; 160 eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE)); 161 eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE)); 162 topologyRoutes.Add(new Edge((uint)id++, IdealEdgeLength, eps)); 163 } 164 } 165 } 166 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> 167 173 private static void ColourNeighbours(IVertex v) { 168 174 foreach (var arc in v.InArcs) { … … 178 184 } 179 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> 180 192 private static IEnumerable<Cluster> IdentifyClusters(RectanglePtrs rectangles, ColaEdges edges) { 181 193 // build a graph using the rectangles and the edges … … 205 217 } 206 218 207 private void RouteEdges(ColaEdges edges) { 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(); 208 225 // after the layout is done, we need to use a router to route edges 209 226 RouterFlag rf; … … 216 233 break; 217 234 default: 218 rf = RouterFlag.PolyLineRouting; 219 break; 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; 220 245 } 221 246 var router = new Router((uint)rf); 247 // set the minimal distance by which nodes should be avoided by the router 222 248 router.setRoutingParameter(RoutingParameter.shapeBufferDistance, 5); 223 //router.setRoutingParameter(RoutingParameter.idealNudgingDistance, 0);224 249 router.UseLeesAlgorithm = true; 225 250 router.InvisibilityGrph = false; 226 //router.RubberBandRouting = true;227 var shapes = new List<ShapeRef>();228 251 // consider topology routes only for the topologyNodes associated with our objects (the rectangles) 229 230 252 for (int i = 0; i < topologyNodeCount; ++i) { 231 253 var r = topologyNodes[i].rect; … … 242 264 var shapeRef = new ShapeRef(router, poly); 243 265 idMap[shapeRef.id()] = (uint)i; 244 shapes.Add(shapeRef);245 266 } 246 267 router.processTransaction(); 247 268 248 var connRefs = new List<ConnRef>();249 269 for (int i = 0; i < edges.Count; ++i) { 250 270 var edge = edges[i]; … … 271 291 var id = router.newObjectId(); 272 292 var node = new Node(id, new Cola.Rectangle(p.x, p.x + 1, p.y, p.y + 1)); 273 //topologyNodes.Add(node);274 293 idMap[id] = id; 275 294 eps.Add(new EdgePoint(node, ri)); … … 278 297 eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE)); 279 298 topologyRoutes.Add(new Edge((uint)i, IdealEdgeLength, eps)); 280 connRefs.Add(connRef); 281 } 282 } 283 284 public void Run() { } 285 286 public void UpdateNodePosition(IVertex v, PointF point) { 287 var node = topologyNodes[indexMap[v]]; 299 } 300 } 301 302 public void OutputInstanceToSVG(string path) { 303 alg.outputInstanceToSVG(path); 288 304 } 289 305
Note: See TracChangeset
for help on using the changeset viewer.