ext/OGDF/src/energybased/SpringEmbedderFR.cpp

   1 /*
   2  * $Revision: 2552 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of Spring-Embedder algorithm
  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 #include <ogdf/energybased/SpringEmbedderFR.h>
  44 #include <ogdf/packing/TileToRowsCCPacker.h>
  45 #include <ogdf/basic/GraphCopyAttributes.h>
  46 #include <ogdf/basic/simple_graph_alg.h>
  47 #include <math.h>
  48
  49
  50 namespace ogdf {
  51
  52
  53 SpringEmbedderFR::SpringEmbedderFR()
  54 {
  55         m_A = 0;
  56         // default parameters
  57         m_iterations   = 400;
  58         m_fineness     = 0.51;
  59
  60         m_xleft = m_ysmall = 0.0;
  61         m_xright = m_ybig = 250.0;
  62         m_noise = true;
  63
  64         m_scaling = scScaleFunction;
  65         m_scaleFactor = 8.0;
  66         m_bbXmin = 0.0;
  67         m_bbXmax = 100.0;
  68         m_bbYmin = 0.0;
  69         m_bbYmax = 100.0;
  70
  71         m_minDistCC = 20;
  72         m_pageRatio = 1.0;
  73 }
  74
  75
  76 void SpringEmbedderFR::call(GraphAttributes &AG)
  77 {
  78         const Graph &G = AG.constGraph();
  79         if(G.empty())
  80                 return;
  81
  82         // all edges straight-line
  83         AG.clearAllBends();
  84
  85         GraphCopy GC;
  86         GC.createEmpty(G);
  87
  88         // compute connected component of G
  89         NodeArray<int> component(G);
  90         int numCC = connectedComponents(G,component);
  91
  92         // intialize the array of lists of nodes contained in a CC
  93         Array<List<node> > nodesInCC(numCC);
  94
  95         node v;
  96         forall_nodes(v,G)
  97                 nodesInCC[component[v]].pushBack(v);
  98
  99         EdgeArray<edge> auxCopy(G);
 100         Array<DPoint> boundingBox(numCC);
 101
 102         int i;
 103         for(i = 0; i < numCC; ++i)
 104         {
 105                 GC.initByNodes(nodesInCC[i],auxCopy);
 106
 107                 GraphCopyAttributes AGC(GC,AG);
 108                 node vCopy;
 109                 forall_nodes(vCopy, GC) {
 110                         node vOrig = GC.original(vCopy);
 111                         AGC.x(vCopy) = AG.x(vOrig);
 112                         AGC.y(vCopy) = AG.y(vOrig);
 113                 }
 114
 115                 // original
 116                 if (initialize(GC, AGC) == true)
 117                 {
 118                         for(int i = 1; i <= m_iterations; i++)
 119                                 mainStep(GC, AGC);
 120
 121                 }
 122                 cleanup();
 123                 // end original
 124
 125                 node vFirst = GC.firstNode();
 126                 double minX = AGC.x(vFirst), maxX = AGC.x(vFirst),
 127                         minY = AGC.y(vFirst), maxY = AGC.y(vFirst);
 128
 129                 forall_nodes(vCopy,GC) {
 130                         node v = GC.original(vCopy);
 131                         AG.x(v) = AGC.x(vCopy);
 132                         AG.y(v) = AGC.y(vCopy);
 133
 134                         if(AG.x(v)-AG.width (v)/2 < minX) minX = AG.x(v)-AG.width(v) /2;
 135                         if(AG.x(v)+AG.width (v)/2 > maxX) maxX = AG.x(v)+AG.width(v) /2;
 136                         if(AG.y(v)-AG.height(v)/2 < minY) minY = AG.y(v)-AG.height(v)/2;
 137                         if(AG.y(v)+AG.height(v)/2 > maxY) maxY = AG.y(v)+AG.height(v)/2;
 138                 }
 139
 140                 minX -= m_minDistCC;
 141                 minY -= m_minDistCC;
 142
 143                 forall_nodes(vCopy,GC) {
 144                         node v = GC.original(vCopy);
 145                         AG.x(v) -= minX;
 146                         AG.y(v) -= minY;
 147                 }
 148
 149                 boundingBox[i] = DPoint(maxX - minX, maxY - minY);
 150         }
 151
 152         Array<DPoint> offset(numCC);
 153         TileToRowsCCPacker packer;
 154         packer.call(boundingBox,offset,m_pageRatio);
 155
 156         // The arrangement is given by offset to the origin of the coordinate
 157         // system. We still have to shift each node and edge by the offset
 158         // of its connected component.
 159
 160         for(i = 0; i < numCC; ++i)
 161         {
 162                 const List<node> &nodes = nodesInCC[i];
 163
 164                 const double dx = offset[i].m_x;
 165                 const double dy = offset[i].m_y;
 166
 167                 // iterate over all nodes in ith CC
 168                 ListConstIterator<node> it;
 169                 for(it = nodes.begin(); it.valid(); ++it)
 170                 {
 171                         node v = *it;
 172
 173                         AG.x(v) += dx;
 174                         AG.y(v) += dy;
 175                 }
 176         }
 177
 178         m_lit.init();
 179 }
 180
 181
 182 bool SpringEmbedderFR::initialize(GraphCopy &G, GraphCopyAttributes &AG)
 183 {
 184         if(G.numberOfNodes() <= 1)
 185                 return false;  // nothing to do
 186
 187         m_A = 0;
 188
 189         // compute a suitable area (xleft,ysmall), (xright,ybig)
 190         // zoom the current layout into that area
 191
 192         double w_sum = 0.0, h_sum = 0.0;
 193         double xmin, xmax, ymin, ymax;
 194
 195         node v = G.firstNode();
 196         xmin = xmax = AG.x(v);
 197         ymin = ymax = AG.y(v);
 198
 199         forall_nodes(v,G) {
 200                 if(AG.x(v) < xmin) xmin = AG.x(v);
 201                 if(AG.x(v) > xmax) xmax = AG.x(v);
 202                 if(AG.y(v) < ymin) ymin = AG.y(v);
 203                 if(AG.y(v) > ymax) ymax = AG.y(v);
 204                 w_sum += AG.getWidth (v);
 205                 h_sum += AG.getHeight(v);
 206         }
 207
 208         switch(m_scaling) {
 209         case scInput:
 210                 m_xleft  = xmin;
 211                 m_xright = xmax;
 212                 m_ysmall = ymin;
 213                 m_ybig  = ymax;
 214                 break;
 215
 216         case scUserBoundingBox:
 217         case scScaleFunction:
 218
 219                 if (m_scaling == scUserBoundingBox) {
 220                         m_xleft  = m_bbXmin;
 221                         m_xright = m_bbXmax;
 222                         m_ysmall = m_bbYmin;
 223                         m_ybig   = m_bbYmax;
 224
 225                 } else {
 226                         double sqrt_n = sqrt((double)G.numberOfNodes());
 227                         m_xleft  = 0;
 228                         m_ysmall = 0;
 229                         m_xright = (w_sum > 0) ? m_scaleFactor * w_sum / sqrt_n : 1;
 230                         m_ybig   = (h_sum > 0) ? m_scaleFactor * h_sum / sqrt_n : 1;
 231                 }
 232                 // Compute scaling such that layout coordinates fit into used bounding box
 233                 double fx = (xmax == xmin) ? 1.0 : m_xright / (xmax - xmin);
 234                 double fy = (ymax == ymin) ? 1.0 : m_ybig   / (ymax - ymin);
 235                 // Adjust coordinates accordingly
 236                 forall_nodes(v,G) {
 237                         AG.x(v) = m_xleft  + (AG.x(v) - xmin) * fx;
 238                         AG.y(v) = m_ysmall + (AG.y(v) - ymin) * fy;
 239                 }
 240         }
 241
 242
 243         m_lit.init(G);
 244
 245
 246         m_width  = m_xright - m_xleft;
 247         m_height = m_ybig - m_ysmall;
 248
 249         OGDF_ASSERT((m_width >= 0) && (m_height >= 0))
 250
 251         m_txNull = m_width/50;
 252         m_tyNull = m_height/50;
 253         m_tx = m_txNull;
 254         m_ty = m_tyNull;
 255
 256         //m_k = sqrt(m_width*m_height / G.numberOfNodes()) / 2;
 257         m_k = m_fineness * sqrt(m_width*m_height / G.numberOfNodes());
 258         m_k2 = 2*m_k;
 259         m_kk = m_k*m_k;
 260
 261         m_ki = int(m_k);
 262
 263         if (m_ki == 0) m_ki = 1;
 264
 265         m_cF = 1;
 266
 267         // build  matrix of node lists
 268         m_xA = int(m_width / m_ki + 1);
 269         m_yA = int(m_height / m_ki + 1);
 270         m_A = new Array2D<List<node> >(-1,m_xA,-1,m_yA);
 271
 272         forall_nodes(v,G)
 273         {
 274                 double xv = AG.x(v);
 275                 double yv = AG.y(v);
 276
 277                 int i = int((xv - m_xleft) / m_ki);
 278                 int j = int((yv - m_ysmall) / m_ki);
 279
 280                 OGDF_ASSERT( (i < m_xA) && (i > -1) )
 281                 OGDF_ASSERT( (j < m_yA) && (j > -1) )
 282
 283                 m_lit[v] = (*m_A)(i,j).pushFront(v);
 284         }
 285
 286         return true;
 287 }
 288
 289
 290 #define FREPULSE(d) ((m_k2 > (d)) ? m_kk/(d) : 0)
 291
 292
 293 void SpringEmbedderFR::mainStep(GraphCopy &G, GraphCopyAttributes &AG)
 294 {
 295         //const Graph &G = AG.constGraph();
 296
 297         node u,v;
 298         edge e;
 299
 300         NodeArray<double> xdisp(G,0);
 301         NodeArray<double> ydisp(G,0);
 302
 303         // repulsive forces
 304         forall_nodes(v,G)
 305         {
 306                 double xv = AG.x(v);
 307                 double yv = AG.y(v);
 308
 309                 int i = int((xv - m_xleft) / m_ki);
 310                 int j = int((yv - m_ysmall) / m_ki);
 311
 312                 for(int m = -1; m <= 1; m++)
 313                 {
 314                         for(int n = -1; n <= 1; n++)
 315                         {
 316                                 ListIterator<node> it;
 317                                 for(it = (*m_A)(i+m,j+n).begin(); it.valid(); ++it)
 318                                 {
 319                                         u = *it;
 320
 321                                         if(u == v) continue;
 322                                         double xdist = xv - AG.x(u);
 323                                         double ydist = yv - AG.y(u);
 324                                         double dist = sqrt(xdist*xdist + ydist*ydist);
 325                                         if(dist < 1e-3)
 326                                                 dist = 1e-3;
 327                                         xdisp[v] += FREPULSE(dist) * xdist / dist;
 328                                         ydisp[v] += FREPULSE(dist) * ydist / dist;
 329                                 }
 330                         }
 331                 }
 332         }
 333
 334         // attractive forces
 335         forall_edges(e,G)
 336         {
 337                 node u = e->source();
 338                 node v = e->target();
 339                 double xdist = AG.x(v) - AG.x(u);
 340                 double ydist = AG.y(v) - AG.y(u);
 341                 double dist = sqrt(xdist*xdist + ydist*ydist);
 342
 343                 double f = (u->degree()+v->degree())/6.0;
 344
 345                 dist /= f;
 346
 347                 double fac = dist / m_k;
 348
 349                 xdisp[v] -= xdist*fac;
 350                 ydisp[v] -= ydist*fac;
 351                 xdisp[u] += xdist*fac;
 352                 ydisp[u] += ydist*fac;
 353         }
 354
 355         // noise
 356         if(m_noise)
 357         {
 358                 forall_nodes(v,G)
 359                 {
 360                         xdisp[v] *= (double(randomNumber(750,1250))/1000.0);
 361                         ydisp[v] *= (double(randomNumber(750,1250))/1000.0);
 362                 }
 363         }
 364
 365
 366         // preventions
 367
 368         forall_nodes(v,G)
 369         {
 370                 double xv = AG.x(v);
 371                 double yv = AG.y(v);
 372
 373                 int i0 = int((xv - m_xleft) / m_ki);
 374                 int j0 = int((yv - m_ysmall) / m_ki);
 375
 376                 double xd = xdisp[v];
 377                 double yd = ydisp[v];
 378                 double dist = sqrt(xd*xd+yd*yd);
 379
 380                 if (dist < 1)
 381                         dist = 1;
 382
 383                 xd = m_tx*xd/dist;
 384                 yd = m_ty*yd/dist;
 385
 386                 double xp = xv + xd;
 387                 double yp = yv + yd;
 388
 389                 int i,j;
 390
 391                 if( (xp > m_xleft) && (xp < m_xright) )
 392                 {
 393                         AG.x(v) = xp;
 394                         i = int((xp - m_xleft) / m_ki);
 395                 } else
 396                         i = i0;
 397
 398                 if( (yp > m_ysmall) && (yp < m_ybig) )
 399                 {
 400                         AG.y(v) = yp;
 401                         j = int((yp - m_ysmall) / m_ki);
 402                 } else
 403                         j = j0;
 404
 405                 if( (i != i0) || (j != j0) )
 406                 {
 407                         OGDF_ASSERT(m_lit[v].valid());
 408
 409                         (*m_A)(i0,j0).moveToFront(m_lit[v], (*m_A)(i,j));
 410                 }
 411         }
 412
 413         m_tx = m_txNull / mylog2(m_cF);
 414         m_ty = m_tyNull / mylog2(m_cF);
 415
 416         m_cF++;
 417 }
 418
 419
 420 } // end namespace ogdf