ext/OGDF/src/upward/DominanceLayout.cpp

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of dominance layout algorithm.
  11  *
  12  * \author Hoi-Ming Wong and Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #include <ogdf/upward/DominanceLayout.h>
  44 #include <math.h>
  45
  46 namespace ogdf {
  47
  48 void DominanceLayout::call(GraphAttributes &GA)
  49 {
  50         if (GA.constGraph().numberOfNodes() <= 1)
  51                 return;
  52
  53         //call upward planarizer
  54         UpwardPlanRep UPR;
  55         UPR.createEmpty(GA.constGraph());
  56         m_upPlanarizer.get().call(UPR);
  57         layout(GA, UPR);
  58 }
  59
  60
  61 void DominanceLayout::layout(GraphAttributes &GA, const UpwardPlanRep &UPROrig)
  62 {
  63
  64         UpwardPlanRep UPR = UPROrig;
  65
  66         //clear some data
  67         edge e;
  68         forall_edges(e, GA.constGraph()) {
  69                 GA.bends(e).clear();
  70         }
  71
  72         //compute and splite transitiv edges
  73         List<edge> splitMe;
  74         findTransitiveEdges(UPR, splitMe);
  75
  76         forall_listiterators(edge, it, splitMe) {
  77                 UPR.getEmbedding().split(*it);
  78         }
  79
  80         // set up first-/lastout, first-/lastin
  81         firstout.init(UPR, 0);
  82         lastout.init(UPR, 0);
  83         firstin.init(UPR, 0);
  84         lastin.init(UPR, 0);
  85
  86         node s = UPR.getSuperSource();
  87         node t = UPR.getSuperSink();
  88
  89         firstout[t] = lastout[t] = 0;
  90         firstin[s] = lastin[s] = 0;
  91         firstin[t] = lastin[t] =t->firstAdj()->theEdge();
  92         adjEntry adjRun = s->firstAdj();
  93         while (UPR.getEmbedding().rightFace(adjRun) != UPR.getEmbedding().externalFace()) {
  94                 adjRun = adjRun->cyclicSucc();
  95         }
  96         lastout[s] = adjRun->theEdge();
  97         firstout[s] = adjRun->cyclicSucc()->theEdge();
  98
  99         node v;
 100         forall_nodes(v, UPR) {
 101                 if (v == t || v == s) continue;
 102
 103                 adjEntry adj = UPR.leftInEdge(v);
 104                 firstin[v] = adj->theEdge();
 105                 firstout[v] = adj->cyclicSucc()->theEdge();
 106
 107                 adjEntry adjRightIn = adj;
 108                 while (adjRightIn->cyclicPred()->theEdge()->source() != v)
 109                         adjRightIn = adjRightIn->cyclicPred();
 110
 111                 lastin[v] = adjRightIn->theEdge();
 112                 lastout[v] = adjRightIn->cyclicPred()->theEdge();
 113         }
 114
 115
 116         //compute m_L and m_R for min. area drawing
 117         m_L = 0;
 118         m_R = 0;
 119         forall_edges(e, UPR) {
 120                 node src = e->source();
 121                 node tgt = e->target();
 122                 if (lastin[tgt] == e && firstout[src] == e)
 123                         m_L++;
 124                 if (firstin[tgt] == e && lastout[src] == e)
 125                         m_R++;
 126         }
 127
 128         // compute preleminary coordinate
 129         xPreCoord.init(UPR);
 130         yPreCoord.init(UPR);
 131         int count = 0;
 132         labelX(UPR, s, count);
 133         count = 0;
 134         labelY(UPR, s, count);
 135
 136         // compaction
 137         compact(UPR, GA);
 138
 139         // map coordinate to GA
 140         forall_nodes(v, GA.constGraph()) {
 141                 node vUPR = UPR.copy(v);
 142                 GA.x(v) = xCoord[vUPR];
 143                 GA.y(v) = yCoord[vUPR];
 144         }
 145         // add bends to original edges
 146         forall_edges(e, GA.constGraph()) {
 147                 List<edge> chain = UPR.chain(e);
 148                 forall_nonconst_listiterators(edge, it, chain) {
 149                         node tgtUPR = (*it)->target();
 150                         if (tgtUPR != chain.back()->target()) {
 151                                 DPoint p(xCoord[tgtUPR], yCoord[tgtUPR]);
 152                                 GA.bends(e).pushBack(p);
 153                         }
 154                 }
 155         }
 156
 157
 158         //rotate the drawing
 159         forall_nodes(v, GA.constGraph()) {
 160                 double r = sqrt(GA.x(v)*GA.x(v) + GA.y(v)*GA.y(v));
 161                 if (r == 0)
 162                         continue;
 163                 double alpha = asin(GA.y(v)/r);
 164                 double yNew = sin(alpha + m_angle)*r;
 165                 double xNew = cos(alpha + m_angle)*r;
 166                 GA.x(v) = xNew;
 167                 GA.y(v) = yNew;
 168         }
 169
 170         forall_edges(e, GA.constGraph()) {
 171                 DPolyline &poly = GA.bends(e);
 172                 DPoint pSrc(GA.x(e->source()), GA.y(e->source()));
 173                 DPoint pTgt(GA.x(e->target()), GA.y(e->target()));
 174                 poly.normalize(pSrc, pTgt);
 175
 176                 forall_nonconst_listiterators(DPoint, it, poly) {
 177                         double r = (*it).distance(DPoint(0,0));
 178
 179                         if (r == 0)
 180                                 continue;
 181
 182                         double alpha = asin( (*it).m_y/r);
 183                         double yNew = sin(alpha + m_angle)*r;
 184                         double xNew = cos(alpha + m_angle)*r;
 185                         (*it).m_x = xNew;
 186                         (*it).m_y = yNew;
 187                 }
 188
 189         }
 190 }
 191
 192
 193 void DominanceLayout::labelX(const UpwardPlanRep &UPR, node v, int &count)
 194 {
 195         xNodes.pushBack(v);
 196         xPreCoord[v] = count;
 197         count++;
 198         if (v != UPR.getSuperSink()) {
 199                 adjEntry adj = firstout[v]->adjSource();
 200                 do {
 201                         node w = adj->theEdge()->target();
 202                         if (adj->theEdge() == lastin[w])
 203                                 labelX(UPR, w, count);
 204                         adj = adj->cyclicSucc();
 205                 } while (adj->cyclicPred()->theEdge() != lastout[v]);
 206         }
 207 }
 208
 209
 210
 211 void DominanceLayout::labelY(const UpwardPlanRep &UPR, node v, int &count)
 212 {
 213         yNodes.pushBack(v);
 214         yPreCoord[v] = count;
 215         count++;
 216         if (v != UPR.getSuperSink()) {
 217                 adjEntry adj = lastout[v]->adjSource();
 218                 do {
 219                         node w = adj->theEdge()->target();
 220                         if (adj->theEdge() == firstin[w])
 221                                 labelY(UPR, w, count);
 222                         adj = adj->cyclicPred();
 223                 } while (adj->cyclicSucc()->theEdge() != firstout[v]);
 224         }
 225 }
 226
 227
 228 void DominanceLayout::compact(const UpwardPlanRep &UPR, GraphAttributes &GA)
 229 {
 230         double maxNodeSize = 0;
 231         node v;
 232         forall_nodes(v, GA.constGraph()) {
 233                 if (GA.width(v) > maxNodeSize || GA.height(v) > maxNodeSize)
 234                         maxNodeSize = max(GA.width(v), GA.height(v));
 235         }
 236
 237         int gridDist = m_grid_dist;
 238         if (gridDist < maxNodeSize+1)
 239                 gridDist = (int) maxNodeSize+1;
 240
 241         xCoord.init(UPR);
 242         yCoord.init(UPR);
 243
 244         //ASSIGN X COORDINATE
 245
 246         OGDF_ASSERT(!xNodes.empty());
 247
 248         v = xNodes.popFrontRet();
 249         xCoord[v] = 0;
 250         while (!xNodes.empty()) {
 251                 node u = xNodes.popFrontRet();
 252                 if ( (yPreCoord[v] > yPreCoord[u]) || (firstout[v] == lastout[v] && firstin[u] == lastin[u] && m_L <= m_R)) {
 253                         xCoord[u] = xCoord[v] + gridDist;
 254                 }
 255                 else
 256                         xCoord[u] = xCoord[v];
 257                 v = u;
 258         }
 259
 260         //ASSIGN Y COORDINATE
 261         OGDF_ASSERT(!yNodes.empty());
 262
 263         v = yNodes.popFrontRet();
 264         yCoord[v] = 0;
 265         while (!yNodes.empty()) {
 266                 node u = yNodes.popFrontRet();
 267                 if ( (xPreCoord[v] > xPreCoord[u]) || (firstout[v] == lastout[v] && firstin[u] == lastin[u] && m_L > m_R)) {
 268                         yCoord[u] = yCoord[v] + gridDist;
 269                 }
 270                 else
 271                         yCoord[u] = yCoord[v];
 272                 v = u;
 273         }
 274 }
 275
 276
 277
 278 void DominanceLayout::findTransitiveEdges(const UpwardPlanRep &UPR, List<edge> &edges)
 279 {
 280         // for st-graphs:
 281         // e = (u,v) transitive <=> ex. face f: e in f and u source-switch and v = sink-switch
 282         face f;
 283         forall_faces(f, UPR.getEmbedding()) {
 284                 if (f == UPR.getEmbedding().externalFace())
 285                         continue;
 286
 287                 adjEntry adj;
 288                 forall_face_adj(adj, f) {
 289                         node src = adj->theEdge()->source();
 290                         node tgt = adj->theEdge()->target();
 291                         if ( (adj->faceCycleSucc()->theEdge()->source() == src && adj->faceCyclePred()->theEdge()->target() == tgt)
 292                                 || (adj->faceCycleSucc()->theEdge()->target() == tgt && adj->faceCyclePred()->theEdge()->source() == src)) {
 293                                         edges.pushBack(adj->theEdge());
 294                                         break;
 295                         }
 296                 }
 297         }
 298 }
 299
 300
 301 }//namespace