ext/OGDF/src/orthogonal/ClusterOrthoLayout.cpp

   1 /*
   2  * $Revision: 2566 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 23:10:08 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements planar orthogonal drawing algorithm for
  11 //   cluster graphs.
  12  *
  13  * \author Carsten Gutwenger, Sebastian Leipert, Karsten Klein
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #include <ogdf/cluster/ClusterOrthoLayout.h>
  46 #include <ogdf/cluster/CconnectClusterPlanarEmbed.h>
  47
  48
  49 #include <ogdf/orthogonal/LongestPathCompaction.h>
  50 #include <ogdf/orthogonal/FlowCompaction.h>
  51 #include <ogdf/orthogonal/EdgeRouter.h>
  52 #include <ogdf/internal/orthogonal/RoutingChannel.h>
  53 #include <ogdf/orthogonal/MinimumEdgeDistances.h>
  54 #include <ogdf/cluster/ClusterOrthoShaper.h>
  55
  56
  57 namespace ogdf {
  58
  59
  60 ClusterOrthoLayout::ClusterOrthoLayout()
  61 {
  62         //drawing object distances
  63         m_separation = 40.0;
  64         m_cOverhang  = 0.2;
  65         m_margin     = 40.0;
  66         //preferred hierarchy direction is odNorth, but we use odSouth since gml's are flipped!
  67         m_preferedDir = odSouth;
  68         m_optionProfile = 0;
  69         //edge costs
  70         m_costAssoc   = 1;
  71         m_costGen     = 4;
  72         //align hierarchy nodes on same level
  73         m_align = false;
  74         //scale layout while improving it during compaction
  75         m_useScalingCompaction = false;
  76         m_scalingSteps = 6;
  77
  78         m_orthoStyle = 0; //traditional 0, progressive 1
  79 }
  80
  81
  82 /**--------------------------------------
  83 calling function without non-planar edges
  84 */
  85 void ClusterOrthoLayout::call(ClusterPlanRep &PG,
  86         adjEntry adjExternal,
  87         Layout &drawing)
  88 {
  89         List<NodePair> npEdges; //is empty
  90         List<edge> newEdges;    //is empty
  91         Graph G;
  92         call(PG, adjExternal, drawing, npEdges, newEdges, G);
  93 }//call c-planar
  94
  95 /**---------------------------------------------------
  96 calling function taking the planar representation, the
  97 external face (adjentry), the layout to be filled,
  98 a list of non-planar edges, a list of inserted edges
  99 and the original graph as input
 100 */
 101 void ClusterOrthoLayout::call(ClusterPlanRep &PG,
 102         adjEntry adjExternal,
 103         Layout &drawing,
 104         List<NodePair>& npEdges,
 105         List<edge>& newEdges,
 106         Graph& originalGraph)
 107 {
 108         // We don't care about UML hierarchies and therefore do not allow alignment
 109         OGDF_ASSERT(!m_align);
 110
 111         // if we have only one vertex in PG ...
 112         if(PG.numberOfNodes() == 1) {
 113                 node v1 = PG.firstNode();
 114                 node vOrig = PG.original(v1);
 115                 double w = PG.widthOrig(vOrig);
 116                 double h = PG.heightOrig(vOrig);
 117
 118                 drawing.x(v1) = m_margin + w/2;
 119                 drawing.y(v1) = m_margin + h/2;
 120                 m_boundingBox = DPoint(w + 2*m_margin, h + 2*m_margin);
 121                 return;
 122         }
 123
 124         OGDF_ASSERT(PG.representsCombEmbedding())
 125         //-------------------------
 126         // insert cluster boundaries
 127         PG.ModelBoundaries();
 128         OGDF_ASSERT(PG.representsCombEmbedding())
 129
 130
 131         //--------------------------
 132         // insert non-planar edges
 133         CombinatorialEmbedding* CE = new CombinatorialEmbedding(PG);
 134         if (!npEdges.empty())
 135         {
 136                 CPlanarEdgeInserter CEI;
 137                 CEI.call(PG, *CE, originalGraph, npEdges, newEdges);
 138         }//if
 139
 140         //------------------------------------------------------------
 141         // now we set the external face, currently to the largest face
 142         adjEntry extAdj = 0;
 143         int maximum = 0;
 144         edge e, eSucc;
 145
 146         for(e = PG.firstEdge(); e; e = eSucc)
 147         {
 148                 eSucc = e->succ();
 149                 if ( PG.clusterOfEdge(e) == PG.getClusterGraph().rootCluster() )
 150                 {
 151                         int asSize = CE->rightFace(e->adjSource())->size();
 152                         if ( asSize > maximum)
 153                         {
 154                                 maximum = asSize;
 155                                 extAdj = e->adjSource();
 156                         }
 157                         int atSize = CE->rightFace(e->adjTarget())->size();
 158                         if ( atSize > maximum)
 159                         {
 160                                 maximum = atSize;
 161                                 extAdj = e->adjTarget();
 162                         }
 163
 164                 }//if root edge
 165
 166         }//for
 167
 168         delete CE;
 169
 170         //returns adjEntry in rootcluster
 171         adjExternal = extAdj;
 172         OGDF_ASSERT(adjExternal != 0);
 173
 174
 175         //----------------------------------------------------------
 176         //Compaction scaling: help node cages to pass by each other:
 177         //First, the layout is blown up and then shrunk again in several steps
 178         //We change the separation value and save the original value.
 179         double l_orsep = m_separation;
 180         if (m_useScalingCompaction)
 181         {
 182                 double scaleFactor = double(int(1 << m_scalingSteps));
 183                 m_separation = scaleFactor*m_separation; //reduce this step by step in compaction
 184         }//if scaling
 185
 186         //***********************************
 187         // PHASE 1: determine orthogonal shape
 188
 189         //-------------------------------------------------------
 190         // expand high-degree vertices and generalization mergers
 191         PG.expand();
 192
 193         // get combinatorial embedding
 194         CombinatorialEmbedding E(PG);
 195         E.setExternalFace(E.rightFace(adjExternal));
 196
 197         // orthogonal shape representation
 198         OrthoRep OR;
 199
 200         ClusterOrthoShaper COF;
 201
 202         //set some options
 203         COF.align(false); //cannot be used yet with clusters
 204         COF.traditional(m_orthoStyle > 0 ? false : true); //prefer 90/270 degree angles over 180/180
 205         //bend cost depends on cluster depths avoiding unnecessary "inner" bends
 206         COF.bendCostTopDown(ClusterOrthoShaper::topDownCost);
 207
 208         // New Call
 209         //COF.call(PG,E,OR,2);
 210         // Original call without bend bounds(still valid)
 211         COF.call(PG, E, OR);
 212
 213         String msg;
 214         OGDF_ASSERT(OR.check(msg))
 215
 216         //******************************************************************
 217         // PHASE 2: construction of a feasible drawing of the expanded graph
 218
 219         //---------------------------
 220         // expand low degree vertices
 221         PG.expandLowDegreeVertices(OR);
 222
 223         OGDF_ASSERT(PG.representsCombEmbedding());
 224
 225         //------------------
 226         // restore embedding
 227         E.computeFaces();
 228         E.setExternalFace(E.rightFace(adjExternal));
 229
 230         OGDF_ASSERT(OR.check(msg))
 231
 232         //----------
 233         //COMPACTION
 234
 235         //--------------------------
 236         // apply constructive compaction heuristics
 237         OR.normalize();
 238         OR.dissect();
 239
 240         OR.orientate(PG,m_preferedDir);
 241
 242         OGDF_ASSERT(OR.check(msg))
 243
 244         // compute cage information and routing channels
 245         OR.computeCageInfoUML(PG);
 246         //temporary grid layout
 247         GridLayoutMapped gridDrawing(PG,OR,m_separation,m_cOverhang,4);
 248
 249         RoutingChannel<int> rcGrid(PG,gridDrawing.toGrid(m_separation),m_cOverhang);
 250         rcGrid.computeRoutingChannels(OR, m_align);
 251
 252         node v;
 253         const OrthoRep::VertexInfoUML *pInfoExp;
 254         forall_nodes(v,PG) {
 255                 pInfoExp = OR.cageInfo(v);
 256
 257                 if (pInfoExp) break;
 258         }
 259
 260         FlowCompaction fca(0,m_costGen,m_costAssoc);
 261         fca.constructiveHeuristics(PG,OR,rcGrid,gridDrawing);
 262
 263         OR.undissect(m_align);
 264
 265         if (!m_align)  {OGDF_ASSERT(OR.check(msg))}
 266
 267         //--------------------------
 268         //apply improvement compaction heuristics
 269         // call flow compaction on grid
 270         FlowCompaction fc(0,m_costGen,m_costAssoc);
 271         fc.align(m_align);
 272         fc.scalingSteps(m_scalingSteps);
 273
 274         fc.improvementHeuristics(PG,OR,rcGrid,gridDrawing);
 275
 276         if (m_align) OR.undissect(false);
 277
 278         //**************************
 279         // PHASE 3: routing of edges
 280
 281         OGDF_ASSERT(OR.check(msg) == true);
 282
 283         EdgeRouter router;
 284         MinimumEdgeDistances<int> minDistGrid(PG, gridDrawing.toGrid(m_separation));
 285         //router.setOrSep(int(gridDrawing.toGrid(l_orsep))); //scaling test
 286         router.call(PG,OR,gridDrawing,E,rcGrid,minDistGrid, gridDrawing.width(),
 287                 gridDrawing.height(), m_align);
 288
 289         OGDF_ASSERT(OR.check(msg) == true);
 290
 291         OR.orientate(pInfoExp->m_corner[odNorth],odNorth);
 292
 293         //*******************************************************
 294         // PHASE 4: apply improvement compaction heuristics again
 295
 296         // call flow compaction on grid
 297         fc.improvementHeuristics(PG, OR, minDistGrid, gridDrawing, int(gridDrawing.toGrid(l_orsep)));
 298
 299         // re-map result
 300         gridDrawing.remap(drawing);
 301
 302         //postProcess(PG);
 303
 304         //--------------------------
 305         // collapse all expanded vertices by introducing a new node in the center
 306         // of each cage representing the original vertex
 307         PG.collapseVertices(OR,drawing);
 308
 309         // finally set the bounding box
 310         computeBoundingBox(PG,drawing);
 311
 312         //set the separation again to the input value
 313         m_separation = l_orsep;
 314 }//call
 315
 316
 317
 318 // compute bounding box and move final drawing such that it is 0 aligned
 319 // respecting margins
 320 void ClusterOrthoLayout::computeBoundingBox(
 321         const ClusterPlanRep &PG,
 322         Layout &drawing)
 323 {
 324         double minX, maxX, minY, maxY;
 325
 326         minX = maxX = drawing.x(PG.firstNode());
 327         minY = maxY = drawing.y(PG.firstNode());
 328
 329         node v;
 330         forall_nodes(v,PG)
 331         {
 332                 double x = drawing.x(v);
 333                 if (x < minX) minX = x;
 334                 if (x > maxX) maxX = x;
 335
 336                 double y = drawing.y(v);
 337                 if (y < minY) minY = y;
 338                 if (y > maxY) maxY = y;
 339         }
 340
 341         double deltaX = m_margin - minX;
 342         double deltaY = m_margin - minY;
 343
 344         forall_nodes(v,PG)
 345         {
 346                 drawing.x(v) += deltaX;
 347                 drawing.y(v) += deltaY;
 348         }
 349
 350         m_boundingBox = DPoint(maxX+deltaX+m_margin, maxY+deltaY+m_margin);
 351 }
 352
 353
 354 } // end namespace ogdf
 355