ext/OGDF/src/orthogonal/OrthoLayout.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  * mixed-upward embedded graphs
  12  *
  13  * \author Carsten Gutwenger, Sebastian Leipert
  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/orthogonal/OrthoLayout.h>
  46 #include <ogdf/orthogonal/LongestPathCompaction.h>
  47 #include <ogdf/orthogonal/FlowCompaction.h>
  48 #include <ogdf/orthogonal/EdgeRouter.h>
  49 #include <ogdf/internal/orthogonal/RoutingChannel.h>
  50 #include <ogdf/orthogonal/MinimumEdgeDistances.h>
  51 #include <ogdf/orthogonal/OrthoShaper.h>
  52
  53
  54 namespace ogdf {
  55
  56
  57 OrthoLayout::OrthoLayout()
  58 {
  59         //drawing object distances
  60         m_separation = 40.0;
  61         m_cOverhang  = 0.2;
  62         m_margin     = 40.0;
  63         //preferred hierarchy direction
  64         // SHOULD ACTUALLY BE odNorth, but we use odSouth since gml's are flipped!
  65         m_preferedDir = odSouth;
  66         m_optionProfile = 0;
  67         //edge costs
  68         m_costAssoc   = 1;//should be set by profile
  69         m_costGen     = 4;
  70         //align hierarchy nodes on same level
  71         m_align = false;
  72         //scale layout while improving it
  73         m_useScalingCompaction = false;
  74         m_scalingSteps = 0;
  75         m_bendBound = 2; //bounds number of bends per edge in ortho shaper
  76
  77         m_orthoStyle = 0;//0; //traditional 0, progressive 1
  78
  79 }
  80
  81
  82 void OrthoLayout::call(PlanRepUML &PG,
  83         adjEntry adjExternal,
  84         Layout &drawing)
  85 {
  86         // if we have only one vertex in PG ...
  87         if(PG.numberOfNodes() == 1) {
  88                 node v1 = PG.firstNode();
  89                 node vOrig = PG.original(v1);
  90                 double w = PG.widthOrig(vOrig);
  91                 double h = PG.heightOrig(vOrig);
  92
  93                 drawing.x(v1) = m_margin + w/2;
  94                 drawing.y(v1) = m_margin + h/2;
  95                 m_boundingBox = DPoint(w + 2*m_margin, h + 2*m_margin);
  96                 return;
  97         }
  98
  99
 100         //classify brother-to-brother hierarchy edges to allow alignment
 101         if (m_align)
 102         {
 103                 classifyEdges(PG, adjExternal);
 104         }//if align
 105         //compaction with scaling: help node cages to pass by each other
 106         double l_orsep = m_separation;
 107         if (m_useScalingCompaction)
 108         {
 109                 m_scalingSteps = 6;
 110                 double scaleFactor = double(int(1 << m_scalingSteps));
 111                 m_separation = scaleFactor*m_separation; //reduce this step by step in compaction
 112         }//if scaling
 113
 114
 115         //***********************************
 116         // PHASE 1: determine orthogonal shape
 117
 118         // expand high-degree vertices and generalization mergers
 119         PG.expand();
 120
 121         //check preconditions, currently not necessary
 122         //assureDrawability(PG);
 123
 124         // get combinatorial embedding
 125         CombinatorialEmbedding E(PG);
 126         E.setExternalFace(E.rightFace(adjExternal));
 127
 128         // determine orthogonal shape
 129         OrthoRep OR;
 130
 131         //OrthoFormerUML OF;
 132         OrthoShaper OFG;
 133
 134         //set some options
 135         OFG.align(m_align);    //align brother objects on hierarchy levels
 136         OFG.traditional(m_orthoStyle > 0 ? false : true); //prefer 90/270 degree angles over 180/180
 137
 138         // New Call
 139         OFG.setBendBound(m_bendBound);
 140         OFG.call(PG,E,OR);
 141
 142         // remove face splitter
 143         edge e, eSucc;
 144         for(e = PG.firstEdge(); e; e = eSucc)
 145         {
 146                 eSucc = e->succ();
 147                 if(PG.faceSplitter(e)) {
 148                         OR.angle(e->adjSource()->cyclicPred()) = 2;
 149                         OR.angle(e->adjTarget()->cyclicPred()) = 2;
 150                         PG.delEdge(e);
 151                 }
 152         }
 153
 154         //******************************************************************
 155         // PHASE 2: construction of a feasible drawing of the expanded graph
 156
 157         // expand low degree vertices
 158         PG.expandLowDegreeVertices(OR);
 159
 160         OGDF_ASSERT(PG.representsCombEmbedding());
 161
 162         // restore embedding
 163         E.computeFaces();
 164         E.setExternalFace(E.rightFace(adjExternal));
 165
 166         // apply constructive compaction heuristics
 167
 168         OR.normalize();
 169         OR.dissect2(&PG); //OR.dissect();
 170
 171         OR.orientate(PG,m_preferedDir);
 172
 173         // compute cage information and routing channels
 174         OR.computeCageInfoUML(PG);
 175
 176         // adjust value of cOverhang
 177         if(m_cOverhang < 0.05)
 178                 m_cOverhang = 0.0;
 179         if(m_cOverhang > 0.5)
 180                 m_cOverhang = 0.5;
 181
 182         //temporary grid layout
 183         GridLayoutMapped gridDrawing(PG,OR,m_separation,m_cOverhang,2);
 184
 185         RoutingChannel<int> rcGrid(PG,gridDrawing.toGrid(m_separation),m_cOverhang);
 186         rcGrid.computeRoutingChannels(OR, m_align);
 187
 188
 189         node v;
 190         const OrthoRep::VertexInfoUML *pInfoExp;
 191         forall_nodes(v,PG) {
 192                 pInfoExp = OR.cageInfo(v);
 193
 194                 if (pInfoExp) break;
 195         }
 196
 197         FlowCompaction fca(0,m_costGen,m_costAssoc);
 198
 199         fca.constructiveHeuristics(PG,OR,rcGrid,gridDrawing);
 200
 201         OR.undissect(m_align);
 202
 203         // call flow compaction on grid
 204         FlowCompaction fc(0,m_costGen,m_costAssoc);
 205         fc.align(m_align);
 206         fc.scalingSteps(m_scalingSteps);
 207
 208         fc.improvementHeuristics(PG,OR,rcGrid,gridDrawing);
 209
 210         //remove alignment edges before edgerouter call because compaction
 211         //may do an unsplit at the nodes corners, which is impossible if
 212         //there are alignment edges attached
 213         if (m_align) OR.undissect(false);
 214
 215         // PHASE 3: routing of edges
 216         //
 217
 218         EdgeRouter router;
 219         MinimumEdgeDistances<int> minDistGrid(PG, gridDrawing.toGrid(m_separation));
 220         //router.setOrSep(int(gridDrawing.toGrid(l_orsep))); //scaling test
 221         router.call(PG,OR,gridDrawing,E,rcGrid,minDistGrid, gridDrawing.width(),
 222                 gridDrawing.height(), m_align);
 223
 224
 225         String msg;
 226         OGDF_ASSERT(OR.check(msg) == true);
 227
 228         OR.orientate(pInfoExp->m_corner[odNorth],odNorth);
 229
 230         //*************************************************
 231         // PHASE 4: apply improvement compaction heuristics
 232
 233         // call flow compaction on grid
 234         fc.improvementHeuristics(PG, OR, minDistGrid, gridDrawing, int(gridDrawing.toGrid(l_orsep)));
 235
 236
 237         // re-map result
 238         gridDrawing.remap(drawing);
 239
 240         // collapse all expanded vertices by introducing a new node in the center
 241         // of each cage representing the original vertex
 242         PG.collapseVertices(OR,drawing);
 243
 244         // finally set the bounding box
 245         computeBoundingBox(PG,drawing);
 246
 247         m_separation = l_orsep;
 248 }//call
 249
 250
 251
 252 //-----------------------------------------------------------------------------
 253 //Helpers
 254 //-----------------------------------------------------------------------------
 255 void OrthoLayout::classifyEdges(PlanRepUML &PG, adjEntry &adjExternal)
 256 {
 257         //classify brother-to-brother hierarchy edges to allow alignment
 258         //when shifting this to planrep, guarantee edge type correction in planarization
 259         //save external face entry
 260
 261         //PG.classifyEdges
 262         //potential direct connection are all non-gen. edges that are alignUpward
 263         edge e, eSucc;
 264         for(e = PG.firstEdge(); e; e = eSucc)
 265         {
 266                 eSucc = e->succ();
 267                 if (PG.typeOf(e) != Graph::generalization)
 268                 {
 269                         adjEntry as = e->adjSource();
 270                         node v = e->source();
 271                         if ( (PG.alignUpward(as))
 272                                 && (PG.typeOf(e->target()) != Graph::dummy)//TODO: crossings ?
 273                                 && (PG.typeOf(v) != Graph::dummy)
 274                                 )
 275                         {
 276                                 edge gen1, gen2;
 277                                 int stop = 0;
 278                                 adjEntry runAE = as->cyclicSucc();
 279                                 edge run = runAE->theEdge();
 280                                 while ( (stop < v->degree()) &&  //only once
 281                                         ((PG.typeOf(run) != Graph::generalization) || //search generalization
 282                                         (run->source() != v) //outgoing gen
 283                                         )
 284                                         )
 285                                 {
 286                                         stop++;
 287                                         runAE = runAE->cyclicSucc();
 288                                         run = runAE->theEdge();
 289                                 }//while
 290                                 OGDF_ASSERT(stop <= v->degree());
 291
 292                                 //now we have the outgoing generalization (to the merger) at v
 293                                 gen1 = run;
 294
 295                                 node w = e->target(); //crossings ?
 296                                 adjEntry asTwin = as->twin();
 297
 298                                 stop = 0;
 299                                 runAE = asTwin->cyclicSucc();
 300                                 run = runAE->theEdge();
 301                                 while ( (stop < w->degree()) &&
 302                                         ((PG.typeOf(run) != Graph::generalization) ||
 303                                         (run->source() != w)
 304                                         )
 305                                         )
 306                                 {
 307                                         stop++;
 308                                         runAE = runAE->cyclicSucc();
 309                                         run = runAE->theEdge();
 310                                 }//while
 311                                 OGDF_ASSERT(stop <= w->degree());
 312
 313                                 //now we have the outgoing generalization (to the merger) at w
 314                                 gen2 = run;
 315
 316                                 //two possible orientations
 317                                 //left to right
 318                                 bool ltr = ( gen1->adjSource()->faceCycleSucc() == gen2->adjTarget() );
 319                                 //right to left
 320                                 bool rtl = ( gen2->adjSource()->faceCycleSucc() == gen1->adjTarget() );
 321                                 if (ltr || rtl) //should be disjoint cases because of merger node
 322                                 {
 323                                         PG.setBrother(e);
 324
 325                                         //now check if the embedding does include unnecessary nodes in the slope
 326                                         if (ltr)
 327                                         {
 328                                                 //there are edges between e and gen2 at target
 329                                                 if (!(e->adjTarget()->faceCyclePred() == gen2->adjTarget()))
 330                                                 {
 331                                                         OGDF_ASSERT(v != e->target());
 332                                                         PG.moveAdj(e->adjTarget(), before, gen2->adjTarget()->twin());
 333                                                 }
 334                                                 //there are edges between e and gen1 at source
 335                                                 if (!(e->adjTarget()->faceCycleSucc() == gen1->adjSource()))
 336                                                 {
 337                                                         //test if we discard the outer face entry
 338                                                         if (adjExternal == e->adjSource())
 339                                                         {
 340                                                                 adjExternal = e->adjSource()->faceCyclePred();
 341                                                         }
 342                                                         PG.moveAdj(e->adjSource(), after, gen1->adjSource());
 343                                                 }
 344                                         }//if gen 1 left of gen 2
 345                                         if (rtl)
 346                                         {
 347                                                 //there are edges between e and gen2 at target
 348                                                 if (!(e->adjSource()->faceCycleSucc() == gen2->adjSource()))
 349                                                 {
 350                                                         //test if we discard the outer face entry
 351                                                         if (adjExternal == e->adjTarget())
 352                                                         {
 353                                                                 adjExternal = e->adjTarget()->faceCycleSucc();
 354                                                         }
 355                                                         PG.moveAdj(e->adjTarget(), after, gen2->adjSource());
 356                                                 }
 357                                                 //there are edges between e and gen1 at source
 358                                                 if (!(e->adjSource()->faceCyclePred() == gen1->adjTarget()))
 359                                                 {
 360                                                         PG.moveAdj(e->adjSource(), before, gen1->adjSource());
 361                                                 }
 362
 363                                         }//if gen 2 left of gen 1
 364                                 }//if
 365                                 else PG.setHalfBrother(e);
 366
 367                         }//if upward edge
 368                 }//if not generalization
 369         }//for
 370 }//classifyedges
 371
 372
 373
 374 // compute bounding box and move final drawing such that it is 0 aligned
 375 // respecting margins
 376 void OrthoLayout::computeBoundingBox(
 377         const PlanRepUML &PG,
 378         Layout &drawing)
 379 {
 380         double minX, maxX, minY, maxY;
 381
 382         minX = maxX = drawing.x(PG.firstNode());
 383         minY = maxY = drawing.y(PG.firstNode());
 384
 385         node v;
 386         forall_nodes(v,PG)
 387         {
 388                 double x = drawing.x(v);
 389                 if (x < minX) minX = x;
 390                 if (x > maxX) maxX = x;
 391
 392                 double y = drawing.y(v);
 393                 if (y < minY) minY = y;
 394                 if (y > maxY) maxY = y;
 395         }
 396
 397         double deltaX = m_margin - minX;
 398         double deltaY = m_margin - minY;
 399
 400         forall_nodes(v,PG)
 401         {
 402                 drawing.x(v) += deltaX;
 403                 drawing.y(v) += deltaY;
 404         }
 405
 406         m_boundingBox = DPoint(maxX+deltaX+m_margin, maxY+deltaY+m_margin);
 407 }
 408
 409
 410 } // end namespace ogdf
 411