ext/OGDF/src/energybased/SpringEmbedderKK.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of Kamada-Kaway layout algorithm.
  11  *
  12  * \author Karsten Klein
  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/energybased/SpringEmbedderKK.h>
  44 #include <ogdf/basic/SList.h>
  45
  46 //only debugging
  47 #include <ogdf/basic/simple_graph_alg.h>
  48
  49 namespace ogdf {
  50 const double SpringEmbedderKK::startVal = DBL_MAX - 1.0;
  51 const double SpringEmbedderKK::minVal = DBL_MIN;
  52 const double SpringEmbedderKK::desMinLength = 0.0001;
  53
  54 void SpringEmbedderKK::initialize(
  55         GraphAttributes& GA,
  56         NodeArray<dpair>& partialDer,
  57         const EdgeArray<double>& eLength,
  58         NodeArray< NodeArray<double> >& oLength,
  59         NodeArray< NodeArray<double> >& sstrength,
  60         double & maxDist,
  61         bool simpleBFS)
  62 {
  63         node v;
  64         const Graph &G = GA.constGraph();
  65         //hier if m_spread vorlayout oder muss der Nutzer das extern erledigen?
  66         m_prevEnergy =  startVal;
  67         m_prevLEnergy =  startVal;
  68
  69         // all edges straight-line
  70         GA.clearAllBends();
  71         if (!m_useLayout)
  72                 shufflePositions(GA);
  73
  74         //the shortest path lengths
  75         forall_nodes (v, G) oLength[v].init(G, DBL_MAX);
  76
  77         //-------------------------------------
  78         //computes shortest path distances d_ij
  79         //-------------------------------------
  80         if (simpleBFS)
  81         {
  82                 //we use simply BFS n times
  83                 //TODO experimentally compare speed, also with bintree dijkstra
  84 //#ifdef OGDF_DEBUG
  85 //              double timeUsed;
  86 //              usedTime(timeUsed);
  87 //#endif
  88                 maxDist = allpairsspBFS(G, oLength);
  89 //#ifdef OGDF_DEBUG
  90 //              timeUsed = usedTime(timeUsed);
  91 //              cout << "\n******APSP BFS runtime: \n";
  92 //#endif
  93         }
  94         else
  95         {
  96                 EdgeArray<double> adaptedLength(G);
  97                 adaptLengths(G, GA, eLength, adaptedLength);
  98                 //we use simply the BFM n times or Floyd instead, leading to cubic runtime
  99                 //TODO experimentally compare speed, also with bintree dijkstra
 100                 maxDist = allpairssp(G, adaptedLength, oLength, DBL_MAX);
 101         }
 102         //------------------------------------
 103         //computes original spring length l_ij
 104         //------------------------------------
 105
 106         //first we determine desirable edge length L
 107         //nodes sizes may be non-uniform, we approximate the display size (grid)
 108         //this part relies on the fact that node sizes are set != zero
 109         //TODO check later if this is a good choice
 110         double L = m_desLength; //desirable length
 111         double Lzero; //Todo check with m_zeroLength
 112         if (L < desMinLength)
 113         {
 114                 double swidth = 0.0f, sheight = 0.0f;
 115
 116                 // Do all nodes lie on the same point? Check by computing BB of centers
 117                 // Then, perform simple shifting in layout
 118                 node vFirst = G.firstNode();
 119                 double minX = GA.x(vFirst), maxX = GA.x(vFirst),
 120                                 minY = GA.y(vFirst), maxY = GA.y(vFirst);
 121                 // Two goals:
 122                 //                              add node sizes to estimate desirable length
 123                 //                              compute BB to check degeneracy
 124                 forall_nodes(v, G)
 125                 {
 126                         swidth += GA.width(v);
 127                         sheight += GA.height(v);
 128
 129                         if(GA.x(v) < minX) minX = GA.x(v);
 130                         if(GA.x(v) > maxX) maxX = GA.x(v);
 131                         if(GA.y(v) < minY) minY = GA.y(v);
 132                         if(GA.y(v) > maxY) maxY = GA.y(v);
 133                 }
 134
 135                 double sroot = maxDist;//sqrt(G.numberOfNodes());
 136                 swidth = swidth / sroot;
 137                 sheight = sheight / sroot;
 138                 Lzero = max(2.0*sroot, 2.0*(swidth + sheight));
 139                 //test for multilevel
 140                 Lzero = max(max(maxX-minX, maxY-minY), 2.0*Lzero);
 141                 //cout << "Lzero: "<<Lzero<<"\n";
 142
 143
 144                 L = Lzero / maxDist;
 145 //#ifdef OGDF_DEBUG
 146 //              cout << "Desirable edge length computed: "<<L<<"\n";
 147 //#endif
 148         }//set L != 0
 149         //--------------------------------------------------
 150         // Having L we can compute the original lengths l_ij
 151         // Computes spring strengths k_ij
 152         //--------------------------------------------------
 153         node w;
 154         double dij;
 155         forall_nodes(v, G)
 156         {
 157                 sstrength[v].init(G);
 158                 forall_nodes(w, G)
 159                 {
 160                         dij = oLength[v][w];
 161                         if (dij == DBL_MAX)
 162                         {
 163                                 sstrength[v][w] = minVal;
 164                         }
 165                         else
 166                         {
 167                                 oLength[v][w] = L * dij;
 168                                 sstrength[v][w] = m_K / (dij * dij);
 169                         }
 170                 }
 171         }
 172 }//initialize
 173
 174
 175 void SpringEmbedderKK::mainStep(GraphAttributes& GA,
 176                                                                 NodeArray<dpair>& partialDer,
 177                                                                 NodeArray< NodeArray<double> >& oLength,
 178                                                                 NodeArray< NodeArray<double> >& sstrength,
 179                                                                 const double maxDist)
 180 {
 181         const Graph &G = GA.constGraph();
 182         node v;
 183
 184 #ifdef OGDF_DEBUG
 185         NodeArray<int> nodeCounts(G, 0);
 186         int nodeCount = 0; //number of moved nodes
 187 #endif
 188         // Now we compute delta_m, we search for the node with max value
 189         double delta_m = 0.0f;
 190         double delta_v;
 191         node best_m = G.firstNode();
 192
 193         // Compute the partial derivatives first
 194         forall_nodes (v, G)
 195         {
 196                 dpair parder = computeParDers(v, GA, sstrength, oLength);
 197                 partialDer[v] = parder;
 198                 //delta_m is sqrt of squares of partial derivatives
 199                 delta_v = sqrt(parder.x1()*parder.x1() + parder.x2()*parder.x2());
 200
 201                 if (delta_v > delta_m)
 202                 {
 203                         best_m = v;
 204                         delta_m = delta_v;
 205                 }
 206         }
 207
 208         int globalItCount, localItCount;
 209         if (m_computeMaxIt)
 210         {
 211                 globalItCount = m_gItBaseVal+m_gItFactor*G.numberOfNodes();
 212                 localItCount = 2*G.numberOfNodes();
 213         }
 214         else
 215         {
 216                 globalItCount = m_maxGlobalIt;
 217                 localItCount = m_maxLocalIt;
 218         }
 219
 220
 221         while (globalItCount-- > 0 && !finished(delta_m))
 222         {
 223 #ifdef OGDF_DEBUG
 224 //              cout <<"G: "<<globalItCount <<"\n";
 225 //              cout <<"New iteration on "<<best_m->index()<<"\n";
 226                 nodeCount++;
 227                 nodeCounts[best_m]++;
 228 #endif
 229                 // The contribution best_m makes to the partial derivatives of
 230                 // each vertex.
 231                 NodeArray<dpair> p_partials(G);
 232                 forall_nodes(v, G)
 233                 {
 234                         p_partials[v] = computeParDer(v, best_m, GA, sstrength, oLength);
 235                 }
 236
 237                 localItCount = 0;
 238                 do {
 239 #ifdef OGDF_DEBUG
 240 //                      cout <<"  New local iteration\n";
 241 //                      cout <<"   L: "<<localItCount <<"\n";
 242 #endif
 243                         // Compute the 4 elements of the Jacobian
 244                         double dE_dx_dx = 0.0f, dE_dx_dy = 0.0f, dE_dy_dx = 0.0f, dE_dy_dy = 0.0f;
 245                         forall_nodes(v, G)
 246                         {
 247                                 if (v != best_m) {
 248                                         double x_diff = GA.x(best_m) - GA.x(v);
 249                                         double y_diff = GA.y(best_m) - GA.y(v);
 250                                         double dist = sqrt(x_diff * x_diff + y_diff * y_diff);
 251                                         double dist3 = dist * dist * dist;
 252                                         OGDF_ASSERT(dist3 != 0.0);
 253                                         double k_mi = sstrength[best_m][v];
 254                                         double l_mi = oLength[best_m][v];
 255                                         dE_dx_dx += k_mi * (1 - (l_mi * y_diff * y_diff)/dist3);
 256                                         dE_dx_dy += k_mi * l_mi * x_diff * y_diff / dist3;
 257                                         dE_dy_dx += k_mi * l_mi * x_diff * y_diff / dist3;
 258                                         dE_dy_dy += k_mi * (1 - (l_mi * x_diff * x_diff)/dist3);
 259                                 }
 260                         }
 261
 262                         // Solve for delta_x and delta_y
 263                         double dE_dx = partialDer[best_m].x1();
 264                         double dE_dy = partialDer[best_m].x2();
 265
 266                         double delta_x =
 267                                 (dE_dx_dy * dE_dy - dE_dy_dy * dE_dx)
 268                                 / (dE_dx_dx * dE_dy_dy - dE_dx_dy * dE_dy_dx);
 269
 270                         double delta_y =
 271                                 (dE_dx_dx * dE_dy - dE_dy_dx * dE_dx)
 272                                 / (dE_dy_dx * dE_dx_dy - dE_dx_dx * dE_dy_dy);
 273
 274
 275                         // Move p by (delta_x, delta_y)
 276 #ifdef OGDF_DEBUG
 277                         // cout <<"   x"<< delta_x<<"\n";
 278                         // cout <<"   y" <<delta_y<<"\n";
 279 #endif
 280                         GA.x(best_m) += delta_x;
 281                         GA.y(best_m) += delta_y;
 282
 283                         // Recompute partial derivatives and delta_p
 284                         dpair deriv = computeParDers(best_m, GA, sstrength, oLength);
 285                         partialDer[best_m] = deriv;
 286
 287                         delta_m =
 288                                 sqrt(deriv.x1()*deriv.x1() + deriv.x2()*deriv.x2());
 289                 } while (localItCount-- > 0 && !finishedNode(delta_m));
 290
 291                 // Select new best_m by updating each partial derivative and delta
 292                 node old_p = best_m;
 293                 forall_nodes(v, G)
 294                 {
 295                         dpair old_deriv_p = p_partials[v];
 296                         dpair old_p_partial =
 297                                 computeParDer(v, old_p, GA, sstrength, oLength);
 298                         dpair deriv = partialDer[v];
 299
 300                         deriv.x1() += old_p_partial.x1() - old_deriv_p.x1();
 301                         deriv.x2() += old_p_partial.x2() - old_deriv_p.x2();
 302
 303                         partialDer[v] = deriv;
 304                         double delta = sqrt(deriv.x1()*deriv.x1() + deriv.x2()*deriv.x2());
 305
 306                         if (delta > delta_m) {
 307                                 best_m = v;
 308                                 delta_m = delta;
 309                         }
 310                 }
 311         }//while
 312 #ifdef OGDF_DEBUG
 313 //  cout << "NodeCount: "<<nodeCount<<"\n";
 314 //  forall_nodes(v, G)
 315 //  {
 316 //      cout<<"Counts "<<v->index()<<": "<<nodeCounts[v]<<"\n";
 317 //  }
 318 #endif
 319 }//mainStep
 320
 321
 322 void SpringEmbedderKK::doCall(GraphAttributes& GA, const EdgeArray<double>& eLength, bool simpleBFS)
 323 {
 324         const Graph& G = GA.constGraph();
 325         NodeArray<dpair> partialDer(G); //stores the partial derivative per node
 326         double maxDist; //maximum distance between nodes
 327         NodeArray< NodeArray<double> > oLength(G);//first distance, then original length
 328         NodeArray< NodeArray<double> > sstrength(G);//the spring strength
 329
 330         //only for debugging
 331         OGDF_ASSERT(isConnected(G));
 332
 333         //compute relevant values
 334         initialize(GA, partialDer, eLength, oLength, sstrength, maxDist, simpleBFS);
 335
 336         //main loop with node movement
 337         mainStep(GA, partialDer, oLength, sstrength, maxDist);
 338
 339         if (simpleBFS) scale(GA);
 340 }
 341
 342
 343 void SpringEmbedderKK::call(GraphAttributes& GA)
 344 {
 345         const Graph &G = GA.constGraph();
 346         if(G.numberOfEdges() < 1)
 347                 return;
 348
 349         EdgeArray<double> eLength(G);//, 1.0);is not used
 350         doCall(GA, eLength, true);
 351 }//call
 352
 353 void SpringEmbedderKK::call(GraphAttributes& GA,  const EdgeArray<double>& eLength)
 354 {
 355         const Graph &G = GA.constGraph();
 356         if(G.numberOfEdges() < 1)
 357                 return;
 358
 359         doCall(GA, eLength, false);
 360 }//call with edge lengths
 361
 362
 363 //changes given edge lengths (interpreted as weight factors)
 364 //according to additional parameters like node size etc.
 365 void SpringEmbedderKK::adaptLengths(
 366         const Graph& G,
 367         const GraphAttributes& GA,
 368         const EdgeArray<double>& eLengths,
 369         EdgeArray<double>& adaptedLengths)
 370 {
 371         //we use the edge lengths as factor and try to respect
 372         //the node sizes such that each node has enough distance
 373         edge e;
 374         //adapt to node sizes
 375         forall_edges(e, G)
 376         {
 377                 double smax = max(GA.width(e->source()), GA.height(e->source()));
 378                 double tmax = max(GA.width(e->target()), GA.height(e->target()));
 379                 if (smax+tmax > 0.0)
 380                         adaptedLengths[e] = (1+eLengths[e])*((smax+tmax));///2.0);
 381                 else adaptedLengths[e] = 5.0*eLengths[e];
 382         }
 383 }//adaptLengths
 384
 385 void SpringEmbedderKK::shufflePositions(GraphAttributes& GA)
 386 {
 387 //first check if degenerated or
 388 //just position all on a circle or random layout?
 389 }//shufflePositions
 390
 391
 392
 393 // Compute contribution of vertex u to the first partial
 394 // derivatives (dE/dx_m, dE/dy_m) (for vertex m) (eq. 7 and 8 in paper)
 395 SpringEmbedderKK::dpair SpringEmbedderKK::computeParDer(
 396         node m,
 397         node u,
 398         GraphAttributes& GA,
 399         NodeArray< NodeArray<double> >& ss,
 400         NodeArray< NodeArray<double> >& dist)
 401 {
 402         dpair result(0.0, 0.0);
 403         if (m != u)
 404         {
 405                 double x_diff = GA.x(m) - GA.x(u);
 406                 double y_diff = GA.y(m) - GA.y(u);
 407                 double distance = sqrt(x_diff * x_diff + y_diff * y_diff);
 408                 result.x1() = (ss[m][u]) * (x_diff - (dist[m][u])*x_diff/distance);
 409                 result.x2() = (ss[m][u]) * (y_diff - (dist[m][u])*y_diff/distance);
 410         }
 411
 412         return result;
 413 }
 414
 415
 416 //compute partial derivative for v
 417 SpringEmbedderKK::dpair SpringEmbedderKK::computeParDers(node v,
 418         GraphAttributes& GA,
 419         NodeArray< NodeArray<double> >& ss,
 420         NodeArray< NodeArray<double> >& dist)
 421 {
 422         node u;
 423         dpair result(0.0, 0.0);
 424         forall_nodes(u, GA.constGraph())
 425         {
 426                 dpair deriv = computeParDer(v, u, GA, ss, dist);
 427                 result.x1() += deriv.x1();
 428                 result.x2() += deriv.x2();
 429         }
 430
 431         return result;
 432 }
 433
 434
 435 /**
 436  * Initialise the original estimates from nodes and edges.
 437  */
 438
 439 //we could speed this up by not using nested NodeArrays and
 440 //by not doing the fully symmetrical computation on undirected graphs
 441 //All Pairs Shortest Path Floyd, initializes the whole matrix
 442 //returns maximum distance. Does not detect negative cycles (lead to neg. values on diagonal)
 443 //threshold is the value for the distance of non-adjacent nodes, distance has to be
 444 //initialized with
 445 double SpringEmbedderKK::allpairssp(const Graph& G, const EdgeArray<double>& eLengths, NodeArray< NodeArray<double> >& distance,
 446         const double threshold)
 447 {
 448         node v;
 449         edge e;
 450         double maxDist = -threshold;
 451
 452         forall_nodes(v, G)
 453         {
 454                 distance[v][v] = 0.0f;
 455         }
 456
 457         //TODO: Experimentally compare this against
 458         // all nodes and incident edges (memory access) on huge graphs
 459         forall_edges(e, G)
 460         {
 461                 distance[e->source()][e->target()] = eLengths[e];
 462                 distance[e->target()][e->source()] = eLengths[e];
 463         }
 464
 465 ///**
 466 // * And run the main loop of the algorithm.
 467 // */
 468         node u, w;
 469         forall_nodes(v, G)
 470         {
 471                 forall_nodes(u, G)
 472                 {
 473                         forall_nodes(w, G)
 474                         {
 475                                 if ((distance[u][v] < threshold) && (distance[v][w] < threshold))
 476                                 {
 477                                         distance[u][w] = min( distance[u][w], distance[u][v] + distance[v][w] );
 478                                         //distance[w][u] = distance[u][w]; //is done anyway afterwards
 479                                 }
 480                                 if (distance[u][w] < threshold)
 481                                         maxDist = max(maxDist,distance[u][w]);
 482                         }
 483                 }
 484         }
 485         //debug output
 486 //#ifdef OGDF_DEBUG
 487 //      forall_nodes(v, G)
 488 //      {
 489 //              if (distance[v][v] < 0.0) cerr << "\n###Error in shortest path computation###\n\n";
 490 //      }
 491 //      cout << "Maxdist: "<<maxDist<<"\n";
 492 //      forall_nodes(u, G)
 493 //      {
 494 //      forall_nodes(w, G)
 495 //      {
 496 ////            cout << "Distance " << u->index() << " -> "<<w->index()<<" "<<distance[u][w]<<"\n";
 497 //      }
 498 //      }
 499 //#endif
 500         return maxDist;
 501 }//allpairssp
 502
 503
 504 //the same without weights, i.e. all pairs shortest paths with BFS
 505 //Runs in time |V|²
 506 //for compatibility, distances are double
 507 double SpringEmbedderKK::allpairsspBFS(const Graph& G, NodeArray< NodeArray<double> >& distance)
 508 {
 509         node v;
 510         double maxDist = 0;
 511
 512         forall_nodes(v, G)
 513         {
 514                 distance[v][v] = 0.0f;
 515         }
 516
 517         v = G.firstNode();
 518
 519         //start in each node once
 520         while (v != 0)
 521         {
 522                 //do a bfs
 523                 NodeArray<bool> mark(G, true);
 524                 SListPure<node> bfs;
 525                 bfs.pushBack(v);
 526                 mark[v] = false;
 527
 528                 while (!bfs.empty())
 529                 {
 530                         node w = bfs.popFrontRet();
 531                         edge e;
 532                         double d = distance[v][w]+1.0f;
 533                         forall_adj_edges(e,w)
 534                         {
 535                                 node u = e->opposite(w);
 536                                 if (mark[u])
 537                                 {
 538                                         mark[u] = false;
 539                                         bfs.pushBack(u);
 540                                         distance[v][u] = d;
 541                                         maxDist = max(maxDist,d);
 542                                 }
 543                         }
 544                 }//while
 545
 546                 v = v->succ();
 547         }//while
 548         //check for negative cycles
 549         forall_nodes(v, G)
 550         {
 551                 if (distance[v][v] < 0.0) cerr << "\n###Error in shortest path computation###\n\n";
 552         }
 553
 554 //debug output
 555 //#ifdef OGDF_DEBUG
 556 //      node u, w;
 557 //      cout << "Maxdist: "<<maxDist<<"\n";
 558 //      forall_nodes(u, G)
 559 //      {
 560 //      forall_nodes(w, G)
 561 //      {
 562 ////            cout << "Distance " << u->index() << " -> "<<w->index()<<" "<<distance[u][w]<<"\n";
 563 //      }
 564 //      }
 565 //#endif
 566         return maxDist;
 567 }//allpairsspBFS
 568
 569
 570 void SpringEmbedderKK::scale(GraphAttributes& GA)
 571 {
 572 //Simple version: Just scale to max needed
 573 //We run over all edges, find the largest distance needed and scale
 574 //the edges uniformly
 575         node v;
 576         edge e;
 577         double maxFac = 0.0;
 578         bool scale = true;
 579         forall_edges(e, GA.constGraph())
 580         {
 581                 double w1 = sqrt(GA.width(e->source())*GA.width(e->source())+
 582                                                  GA.height(e->source())*GA.height(e->source()));
 583                 double w2 = sqrt(GA.width(e->target())*GA.width(e->target())+
 584                                                  GA.height(e->target())*GA.height(e->target()));
 585                 w2 = (w1+w2)/2.0; //half length of both diagonals
 586                 double xs = GA.x(e->source());
 587                 double xt = GA.x(e->target());
 588                 double ys = GA.y(e->source());
 589                 double yt = GA.y(e->target());
 590                 double xdist = xs-xt;
 591                 double ydist = ys-yt;
 592                 if ((fabs(xs) > (DBL_MAX / 2.0)-1) || (fabs(xt)> (DBL_MAX/2.0)-1) ||
 593                         (fabs(ys)> (DBL_MAX/2.0)-1) || (fabs(yt)> (DBL_MAX/2.0)-1))
 594                         scale = false; //never scale with huge numbers
 595                 //(even though the drawing may be small and could be shifted to origin)
 596                 double elength = sqrt(xdist*xdist+ydist*ydist);
 597
 598                 //Avoid a max factor of inf!!
 599                 if (DIsGreater(elength, 0.0001))
 600                 {
 601                         w2 = m_distFactor * w2 / elength;//relative to edge length
 602
 603                         if (w2 > maxFac)
 604                                 maxFac = w2;
 605                 }
 606         }
 607
 608
 609         if (maxFac > 1.0 && (maxFac < (DBL_MAX/2.0)-1) && scale) //only scale to increase distance
 610         {
 611                 //if maxFac is large, we scale in steps until we reach a threshold
 612                 if (maxFac > 2048)
 613                 {
 614                         double scaleF = maxFac+0.00001;
 615                         double base = 2.0;
 616                         maxFac = base;
 617
 618                         while (scale && maxFac<scaleF)
 619                         {
 620                         forall_nodes(v, GA.constGraph())
 621                         {
 622                                 GA.x(v) = GA.x(v)*base;
 623                                 GA.y(v) = GA.y(v)*base;
 624                                 if (GA.x(v) > (DBL_MAX / base)-1 || GA.y(v) > (DBL_MAX / base) - 1)
 625                                         scale = false;
 626                         }
 627                         maxFac *= base;
 628                         }
 629                 }
 630                 else
 631                 {
 632                         forall_nodes(v, GA.constGraph())
 633                         {
 634                                 GA.x(v) = GA.x(v)*maxFac;
 635                                 GA.y(v) = GA.y(v)*maxFac;
 636                         }
 637                 }
 638 //#ifdef OGDF_DEBUG
 639 //              cout << "Scaled by factor "<<maxFac<<"\n";
 640 //#endif
 641         }
 642 }//Scale
 643
 644 }//namespace