ext/OGDF/src/basic/GridLayout.cpp

   1 /*
   2  * $Revision: 2549 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-04 23:09:19 +0200 (Mi, 04. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements classes GridLayout and GridLayoutMapped
  11  *
  12  * \author 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
  44 #include <ogdf/basic/GridLayoutMapped.h>
  45 #include <ogdf/planarity/PlanRepUML.h>
  46 #include <ogdf/orthogonal/OrthoRep.h>
  47 #include <ogdf/basic/Layout.h>
  48 #include <ogdf/basic/HashArray.h>
  49
  50
  51 namespace ogdf {
  52
  53
  54 //---------------------------------------------------------
  55 // GridLayout
  56 //---------------------------------------------------------
  57
  58 IPolyline GridLayout::polyline(edge e) const
  59 {
  60         IPolyline ipl = m_bends[e];
  61         IPoint ipStart = IPoint(m_x[e->source()],m_y[e->source()]);
  62         IPoint ipEnd   = IPoint(m_x[e->target()],m_y[e->target()]);
  63
  64         if(ipl.empty() || ipStart != ipl.front())
  65                 ipl.pushFront(ipStart);
  66
  67         if(ipEnd != ipl.back() || ipl.size() < 2)
  68                 ipl.pushBack(ipEnd);
  69
  70         return ipl;
  71 }
  72
  73 struct OGDF_EXPORT GridPointInfo
  74 {
  75         GridPointInfo() : m_v(0), m_e(0) { }
  76         GridPointInfo(node v) : m_v(v), m_e(0) { }
  77         GridPointInfo(edge e) : m_v(0), m_e(e) { }
  78
  79         bool operator==(const GridPointInfo &i) const {
  80                 return (m_v == i.m_v && m_e == i.m_e);
  81         }
  82
  83         bool operator!=(const GridPointInfo &i) const {
  84                 return !operator==(i);
  85         }
  86
  87         node m_v;
  88         edge m_e;
  89 };
  90
  91 ostream &operator<<(ostream &os, const GridPointInfo &i)
  92 {
  93         if(i.m_v == 0 && i.m_e == 0)
  94                 os << "{}";
  95         else if(i.m_v != 0)
  96                 os << "{node " << i.m_v << "}";
  97         else
  98                 os << "{edge " << i.m_e << "}";
  99
 100         return os;
 101 }
 102
 103
 104 class IPointHashFunc {
 105 public:
 106         int hash(const IPoint &ip) {
 107                 return 7*ip.m_x + 23*ip.m_y;
 108         }
 109 };
 110
 111
 112 bool GridLayout::checkLayout()
 113 {
 114         const Graph &G = *m_x.graphOf();
 115         HashArray<IPoint,GridPointInfo> H;
 116
 117         node v;
 118         forall_nodes(v,G)
 119         {
 120                 IPoint ip = IPoint(m_x[v],m_y[v]);
 121                 GridPointInfo i = H[ip];
 122                 if(i != GridPointInfo()) {
 123                         cout << "conflict of " << v << " with " << H[ip] << endl;
 124                         return false;
 125                 }
 126
 127                 H[ip] = GridPointInfo(v);
 128         }
 129
 130         edge e;
 131         forall_edges(e,G)
 132         {
 133                 const IPolyline &bends = m_bends[e];
 134
 135                 ListConstIterator<IPoint> it;
 136                 for(it = bends.begin(); it.valid(); ++it) {
 137                         GridPointInfo i = H[*it];
 138                         if(i != GridPointInfo()) {
 139                                 cout << "conflict of bend point " << (*it) << " of edge " << e << " with " << H[*it] << endl;
 140                                 return false;
 141                         }
 142
 143                         H[*it] = GridPointInfo(e);
 144                 }
 145
 146         }
 147
 148         return true;
 149 }
 150
 151 bool GridLayout::isRedundant(IPoint &p1, IPoint &p2, IPoint &p3)
 152 {
 153         int dzy1 = p3.m_x - p2.m_x;
 154         int dzy2 = p3.m_y - p2.m_y;
 155         int dyx1 = p2.m_x - p1.m_x;
 156
 157         if (dzy1 == 0) return (dyx1 == 0 || dzy2 == 0);
 158
 159         int f = dyx1 * dzy2;
 160
 161         return (f % dzy1 == 0 && (p2.m_y - p1.m_y) == f / dzy1);
 162 }
 163
 164 void GridLayout::compact(IPolyline &ip)
 165 {
 166         if (ip.size() < 3) return;
 167
 168         ListIterator<IPoint> it = ip.begin();
 169         IPoint p = *it; ++it;
 170         for (it = it.succ(); it.valid(); ++it) {
 171                 ListIterator<IPoint> itPred = it.pred();
 172                 if(p == *itPred || isRedundant(p,*itPred,*it)) {
 173                         ip.del(itPred);
 174                 } else {
 175                         p = *itPred;
 176                 }
 177         }
 178 }
 179
 180 IPolyline GridLayout::getCompactBends(edge e) const
 181 {
 182         IPolyline ipl = m_bends[e];
 183
 184         if (ipl.size() == 0) return ipl;
 185
 186 #if 0
 187         IPoint ip_first = ipl.front();
 188         IPoint ip_last  = ipl.back();
 189 #endif
 190
 191         IPoint ip_src(m_x[e->source()],m_y[e->source()]);
 192         IPoint ip_tgt(m_x[e->target()],m_y[e->target()]);
 193
 194         ipl.pushFront(ip_src);
 195         ipl.pushBack (ip_tgt);
 196
 197         compact(ipl);
 198
 199         ipl.popFront();
 200         ipl.popBack();
 201
 202 #if 0
 203         if (ip_first != ip_src && (ipl.empty() || ip_first != ipl.front()))
 204                 ipl.pushFront(ip_first);
 205         if (ip_last != ip_tgt && (ipl.empty() || ip_last != ipl.back()))
 206                 ipl.pushBack(ip_last);
 207 #endif
 208
 209         return ipl;
 210 }
 211
 212
 213 void GridLayout::compactAllBends()
 214 {
 215         const Graph &G = *m_x.graphOf();
 216
 217         edge e;
 218         forall_edges(e,G)
 219                 m_bends[e] = getCompactBends(e);
 220 }
 221
 222 void GridLayout::remap(Layout &drawing)
 223 {
 224         const Graph &G = *m_x.graphOf();
 225
 226         node v;
 227         forall_nodes(v,G) {
 228                 drawing.x(v) = m_x[v];
 229                 drawing.y(v) = m_y[v];
 230         }
 231
 232 }
 233
 234
 235 void GridLayout::computeBoundingBox(int &xmin, int &xmax, int &ymin, int &ymax)
 236 {
 237         const Graph *pG = m_x.graphOf();
 238
 239         if(pG == 0 || pG->empty()) {
 240                 xmin = xmax = ymin = ymax = 0;
 241                 return;
 242         }
 243
 244         xmin = ymin = INT_MAX;
 245         xmax = ymax = INT_MIN;
 246
 247         node v;
 248         forall_nodes(v,*pG) {
 249                 int x = m_x[v];
 250                 if(x < xmin) xmin = x;
 251                 if(x > xmax) xmax = x;
 252
 253                 int y = m_y[v];
 254                 if(y < ymin) ymin = y;
 255                 if(y > ymax) ymax = y;
 256         }
 257
 258         edge e;
 259         forall_edges(e,*pG) {
 260                 ListConstIterator<IPoint> it;
 261                 for(it = m_bends[e].begin(); it.valid(); ++it) {
 262                         int x = (*it).m_x;
 263                         if(x < xmin) xmin = x;
 264                         if(x > xmax) xmax = x;
 265
 266                         int y = (*it).m_y;
 267                         if(y < ymin) ymin = y;
 268                         if(y > ymax) ymax = y;
 269                 }
 270         }
 271 }
 272
 273
 274 int GridLayout::manhattanDistance(const IPoint &ip1, const IPoint &ip2)
 275 {
 276         return abs(ip2.m_x-ip1.m_x) + abs(ip2.m_y-ip1.m_y);
 277 }
 278
 279 double GridLayout::euclideanDistance(const IPoint &ip1, const IPoint &ip2)
 280 {
 281         double dx = ip2.m_x-ip1.m_x;
 282         double dy = ip2.m_y-ip1.m_y;
 283
 284         return sqrt(dx*dx + dy*dy);
 285 }
 286
 287
 288 int GridLayout::totalManhattanEdgeLength() const
 289 {
 290         const Graph *pG = m_x.graphOf();
 291         int length = 0;
 292
 293         edge e;
 294         forall_edges(e,*pG)
 295                 length += manhattanEdgeLength(e);
 296         //{
 297         //      IPoint ip1 = IPoint(m_x[e->source()],m_y[e->source()]);
 298         //      ListConstIterator<IPoint> it = m_bends[e].begin();
 299         //      for(; it.valid(); ++it) {
 300         //              length += manhattanDistance(ip1,*it);
 301         //              ip1 = *it;
 302         //      }
 303         //      length += manhattanDistance(ip1,IPoint(m_x[e->target()],m_y[e->target()]));
 304         //}
 305
 306         return length;
 307 }
 308
 309
 310 int GridLayout::maxManhattanEdgeLength() const
 311 {
 312         const Graph *pG = m_x.graphOf();
 313         int length = 0;
 314
 315         edge e;
 316         forall_edges(e,*pG)
 317                 length = max( length, manhattanEdgeLength(e) );
 318
 319         return length;
 320 }
 321
 322
 323 int GridLayout::manhattanEdgeLength(edge e) const
 324 {
 325         int length = 0;
 326
 327         IPoint ip1 = IPoint(m_x[e->source()],m_y[e->source()]);
 328         ListConstIterator<IPoint> it = m_bends[e].begin();
 329         for(; it.valid(); ++it) {
 330                 length += manhattanDistance(ip1,*it);
 331                 ip1 = *it;
 332         }
 333         length += manhattanDistance(ip1,IPoint(m_x[e->target()],m_y[e->target()]));
 334
 335         return length;
 336 }
 337
 338
 339 double GridLayout::totalEdgeLength() const
 340 {
 341         const Graph *pG = m_x.graphOf();
 342         double length = 0;
 343
 344         edge e;
 345         forall_edges(e,*pG) {
 346                 IPoint ip1 = IPoint(m_x[e->source()],m_y[e->source()]);
 347                 ListConstIterator<IPoint> it = m_bends[e].begin();
 348                 for(; it.valid(); ++it) {
 349                         length += euclideanDistance(ip1,*it);
 350                         ip1 = *it;
 351                 }
 352                 length += euclideanDistance(ip1,IPoint(m_x[e->target()],m_y[e->target()]));
 353         }
 354
 355         return length;
 356 }
 357
 358
 359 int GridLayout::numberOfBends() const
 360 {
 361         const Graph *pG = m_x.graphOf();
 362         int num = 0;
 363
 364         edge e;
 365         forall_edges(e,*pG)
 366                 num += m_bends[e].size();
 367
 368         return num;
 369 }
 370
 371
 372 //---------------------------------------------------------
 373 // GridLayoutMapped
 374 //---------------------------------------------------------
 375
 376 GridLayoutMapped::GridLayoutMapped(
 377         const PlanRep &PG,
 378         const OrthoRep &OR,
 379         double separation,
 380         double cOverhang,
 381         int fineness) :
 382                 GridLayout(PG), m_gridWidth(PG,0), m_gridHeight(PG,0), m_pPG(&PG)
 383 {
 384         // determine grid mapping factor
 385         double minDelta = separation;
 386
 387         node v;
 388         forall_nodes(v,PG)
 389         {
 390                 node vOrig = PG.original(v);
 391                 if(vOrig == 0) continue;
 392
 393                 const OrthoRep::VertexInfoUML *pInfo = OR.cageInfo(v);
 394
 395                 for(int s = 0; s <= 3; ++s) {
 396                         const OrthoRep::SideInfoUML &si = pInfo->m_side[s];
 397                         double size = (s & 1) ? PG.widthOrig(vOrig) : PG.heightOrig(vOrig);
 398                         if (size == 0) continue;
 399
 400                         if(si.m_adjGen) {
 401                                 int k = max(si.m_nAttached[0],si.m_nAttached[1]);
 402                                 if (k == 0)
 403                                         minDelta = min(minDelta, size/2);
 404                                 else
 405                                         minDelta = min(minDelta, size / (2*(k + cOverhang)));
 406
 407                         } else {
 408                                 if (si.m_nAttached[0] == 0)
 409                                         minDelta = min(minDelta, size);
 410
 411                                 else if ( !((si.m_nAttached[0] == 1) && (cOverhang == 0.0)) ) //hier cov= 0 abfangen
 412                                         minDelta =  min(minDelta,
 413                                                 size / (si.m_nAttached[0] - 1 + 2*cOverhang));
 414                                 else
 415                                         minDelta = min(minDelta, size/2);
 416                         }
 417
 418                 }
 419
 420         }
 421
 422         if(0 < cOverhang && cOverhang < 1) {
 423                 /*double tryMinDelta = max(cOverhang * minDelta, separation/10000.0);
 424                 double tryMinDelta = max(cOverhang * minDelta, separation/10000.0);
 425                 if(tryMinDelta < minDelta)
 426                         minDelta = tryMinDelta;*/
 427                 minDelta *= cOverhang;
 428         }
 429
 430         m_fMapping = fineness / minDelta;
 431
 432
 433         // initialize grid sizes of vertices
 434         forall_nodes(v,PG)
 435         {
 436                 node vOrig = PG.original(v);
 437
 438                 if(vOrig) {
 439                         m_gridWidth [v] = toGrid(PG.widthOrig (vOrig));
 440                         m_gridHeight[v] = toGrid(PG.heightOrig(vOrig));
 441                 }
 442         }
 443 }
 444
 445
 446 void GridLayoutMapped::remap(Layout &drawing)
 447 {
 448         node v;
 449         forall_nodes(v,*m_pPG) {
 450                 //should use toDouble here
 451                 drawing.x(v) = (m_x[v]/cGridScale) / m_fMapping;
 452                 drawing.y(v) = (m_y[v]/cGridScale) / m_fMapping;
 453         }
 454 }
 455
 456
 457 } // end namespace ogdf
 458