ext/OGDF/src/energybased/DavidsonHarel.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  Iimplementation of class DavidsonHarel
  11  *
  12  * This class realizes the Davidson Harel Algorithm for
  13  * automtatic graph drawing. It minimizes the energy
  14  * of the drawing using simulated annealing. This file
  15  * contains the main simulated annealing algorithm and
  16  * the fnction for computing the next candidate layout
  17  * that should be considered.
  18  *
  19  * \author
  20  *
  21  * \par License:
  22  * This file is part of the Open Graph Drawing Framework (OGDF).
  23  *
  24  * \par
  25  * Copyright (C)<br>
  26  * See README.txt in the root directory of the OGDF installation for details.
  27  *
  28  * \par
  29  * This program is free software; you can redistribute it and/or
  30  * modify it under the terms of the GNU General Public License
  31  * Version 2 or 3 as published by the Free Software Foundation;
  32  * see the file LICENSE.txt included in the packaging of this file
  33  * for details.
  34  *
  35  * \par
  36  * This program is distributed in the hope that it will be useful,
  37  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  38  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  39  * GNU General Public License for more details.
  40  *
  41  * \par
  42  * You should have received a copy of the GNU General Public
  43  * License along with this program; if not, write to the Free
  44  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  45  * Boston, MA 02110-1301, USA.
  46  *
  47  * \see  http://www.gnu.org/copyleft/gpl.html
  48  ***************************************************************/
  49
  50 #include <ogdf/energybased/DavidsonHarel.h>
  51 #include <ogdf/basic/Math.h>
  52 #include <time.h>
  53
  54 //TODO: in addition to the layout size, node sizes should be used in
  55 //the initial radius computation in case of "all central" layouts with
  56 //huge nodes
  57 //the combinations for parameters should be checked: its only useful
  58 //to have a slow shrinking if you have enough time to shrink down to
  59 //small radius
  60
  61 namespace ogdf {
  62
  63         const int DavidsonHarel::m_defaultTemp = 1000;
  64         const double DavidsonHarel::m_defaultRadius = 100.0;
  65         const int DavidsonHarel::m_iterationMultiplier = 25;  //best//30;ori
  66         const double DavidsonHarel::m_coolingFactor = 0.80;  //0.75;ori
  67         const double DavidsonHarel::m_shrinkFactor = 0.8;
  68
  69         //initializes internal data and the random number generator
  70         DavidsonHarel::DavidsonHarel():
  71         m_temperature(m_defaultTemp),
  72         m_shrinkingFactor(m_shrinkFactor),
  73         m_diskRadius(m_defaultRadius),
  74         m_energy(0.0),
  75         m_numberOfIterations(0)
  76         {
  77                 srand((unsigned)time(NULL));
  78         }
  79
  80
  81         //allow resetting in between subsequent calls
  82         void DavidsonHarel::initParameters()
  83         {
  84                 m_diskRadius = m_defaultRadius;
  85                 m_energy = 0.0;
  86                 //m_numberOfIterations = 0; //is set in member function
  87                 m_shrinkingFactor = m_shrinkFactor;
  88
  89         }
  90
  91
  92         void DavidsonHarel::setStartTemperature(int startTemp)
  93         {
  94                 OGDF_ASSERT(startTemp >= 0);
  95                 m_temperature=startTemp;
  96         }
  97
  98         void DavidsonHarel::setNumberOfIterations(int steps)
  99         {
 100                 OGDF_ASSERT(steps >= 0);
 101                 m_numberOfIterations = steps;
 102         }
 103
 104         //whenever an energy function is added, the initial energy of the new function
 105         //is computed and added to the initial energy of the layout
 106         void DavidsonHarel::addEnergyFunction(EnergyFunction *F, double weight)
 107         {
 108                 m_energyFunctions.pushBack(F);
 109                 OGDF_ASSERT(weight >= 0);
 110                 m_weightsOfEnergyFunctions.pushBack(weight);
 111                 F->computeEnergy();
 112                 m_energy += F->energy();
 113         }
 114
 115         List<String> DavidsonHarel::returnEnergyFunctionNames()
 116         {
 117                 List<String> names;
 118                 ListIterator<EnergyFunction*> it;
 119                 for(it = m_energyFunctions.begin(); it.valid(); it = it.succ())
 120                         names.pushBack((*it)->getName());
 121                 return names;
 122         }
 123
 124         List<double> DavidsonHarel::returnEnergyFunctionWeights()
 125         {
 126                 List<double> weights;
 127                 ListIterator<double> it;
 128                 for(it = m_weightsOfEnergyFunctions.begin(); it.valid(); it = it.succ())
 129                         weights.pushBack(*it);
 130                 return weights;
 131         }
 132
 133         //newVal is the energy value of a candidate layout. It is accepted if it is lower
 134         //than the previous energy of the layout or if m_fineTune is not tpFine and
 135         //the difference to the old energy divided by the temperature is smaller than a
 136         //random number between zero and one
 137         bool DavidsonHarel::testEnergyValue(double newVal)
 138         {
 139                 bool accepted = true;
 140                 if(newVal > m_energy) {
 141                         accepted = false;
 142
 143                         double testval = exp((m_energy-newVal)/ m_temperature);
 144                         double compareVal = randNum(); // number between 0 and 1
 145
 146                         if(compareVal < testval)
 147                                 accepted = true;
 148
 149                 }
 150                 return accepted;
 151         }
 152
 153         //divides number returned by rand by RAND_MAX to get number between zero and one
 154         inline double DavidsonHarel::randNum() const
 155         {
 156                 double val = rand();
 157                 val /= RAND_MAX;
 158                 return val;
 159         }
 160
 161         //chooses random vertex and a new random position for it on a circle with radius m_diskRadius
 162         //around its previous position
 163         node DavidsonHarel::computeCandidateLayout(
 164         const GraphAttributes &AG,
 165         DPoint &newPos) const
 166         {
 167                 int randomPos = randomNumber(0,m_nonIsolatedNodes.size()-1);
 168                 node v = *(m_nonIsolatedNodes.get(randomPos));
 169                 double oldx = AG.x(v);
 170                 double oldy = AG.y(v);
 171                 double randomAngle = randNum() * 2.0 * Math::pi;
 172                 newPos.m_y = oldy+sin(randomAngle)*m_diskRadius;
 173                 newPos.m_x = oldx+cos(randomAngle)*m_diskRadius;
 174 #ifdef OGDF_DEBUG
 175                 double dist = sqrt((newPos.m_x - oldx)*(newPos.m_x - oldx)+(newPos.m_y-oldy)*(newPos.m_y-oldy));
 176                 OGDF_ASSERT(dist > 0.99 * m_diskRadius && dist < 1.01 * m_diskRadius);
 177 #endif
 178                 return v;
 179         }
 180
 181         //chooses the initial radius of the disk as half the maximum of width and height of
 182         //the initial layout or depending on the value of m_fineTune
 183         void DavidsonHarel::computeFirstRadius(const GraphAttributes &AG)
 184         {
 185                 const Graph &G = AG.constGraph();
 186                 node v = G.firstNode();
 187                 double minX = AG.x(v);
 188                 double minY = AG.y(v);
 189                 double maxX = minX;
 190                 double maxY = minY;
 191                 forall_nodes(v,G) {
 192                         minX = min(minX,AG.x(v));
 193                         maxX = max(maxX,AG.x(v));
 194                         minY = min(minY,AG.y(v));
 195                         maxY = max(maxY,AG.y(v));
 196                 }
 197                 // compute bounding box of current layout
 198                 // make values nonzero
 199                 double w = maxX-minX+1.0;
 200                 double h = maxY-minY+1.0;
 201
 202                 double ratio = h/w;
 203
 204                 double W = sqrt(G.numberOfNodes() / ratio);
 205
 206                 m_diskRadius = W / 5.0;//allow to move by a significant part of current layout size
 207                 m_diskRadius=max(m_diskRadius,max(maxX-minX,maxY-minY)/5.0);
 208
 209                 //TODO: also use node sizes
 210                 /*
 211                 double lengthSum(0.0);
 212                 node v;
 213                 forall_nodes(v,m_G) {
 214                         const IntersectionRectangle &i = shape(v);
 215                         lengthSum += i.width();
 216                         lengthSum += i.width();
 217                         }
 218                         lengthSum /= (2*m_G.numberOfNodes());
 219                         // lengthSum is now the average of all lengths and widths
 220                 */
 221                 //change the initial radius depending on the settings
 222                 //this is legacy crap
 223 //              double divo = 2.0;
 224 //              if (m_fineTune == tpCoarse) {
 225 //                      m_diskRadius = 1000.0;
 226 //                      divo = 0.5;
 227 //              }
 228 //              if (m_fineTune == tpFine) {
 229 //                      m_diskRadius = 10.0;
 230 //            divo = 15.0;
 231 //              }
 232 //              //m_diskRadius=max(m_diskRadius,max(maxX-minX,maxY-minY));
 233 //              m_diskRadius = max(maxX-minX,maxY-minY);
 234 //              m_diskRadius /= divo;
 235         }
 236
 237         //steps through all energy functions and adds the initial energy computed by each
 238         //function for the start layout
 239         void DavidsonHarel::computeInitialEnergy()
 240         {
 241                 OGDF_ASSERT(!m_energyFunctions.empty());
 242                 ListIterator<EnergyFunction*> it;
 243                 ListIterator<double> it2;
 244                 it2 = m_weightsOfEnergyFunctions.begin();
 245                 for(it = m_energyFunctions.begin(); it.valid() && it2.valid(); it=it.succ(), it2 = it2.succ())
 246                         m_energy += (*it)->energy() * (*it2);
 247         }
 248
 249         //the vertices with degree zero are placed below all other vertices on a horizontal
 250         // line centered with repect to the rest of the drawing
 251         void DavidsonHarel::placeIsolatedNodes(GraphAttributes &AG) const {
 252                 double minX = 0.0;
 253                 double minY = 0.0;
 254                 double maxX = 0.0;
 255                 double maxY = 0.0;
 256
 257                 if(!m_nonIsolatedNodes.empty()) {
 258                         //compute a rectangle that includes all non-isolated vertices
 259                         node v = m_nonIsolatedNodes.front();
 260                         minX = AG.x(v);
 261                         minY = AG.y(v);
 262                         maxX = minX;
 263                         maxY = minY;
 264                         ListConstIterator<node> it;
 265                         for(it = m_nonIsolatedNodes.begin(); it.valid(); ++it) {
 266                                 v = *it;
 267                                 double xVal = AG.x(v);
 268                                 double yVal = AG.y(v);
 269                                 double halfHeight = AG.height(v) / 2.0;
 270                                 double halfWidth = AG.width(v) / 2.0;
 271                                 if(xVal - halfWidth < minX) minX = xVal - halfWidth;
 272                                 if(xVal + halfWidth > maxX) maxX = xVal + halfWidth;
 273                                 if(yVal - halfHeight < minY) minY = yVal - halfHeight;
 274                                 if(yVal + halfHeight > maxY) maxY = yVal + halfHeight;
 275                         }
 276                 }
 277
 278                 // compute the width and height of the largest isolated node
 279                 List<node> isolated;
 280                 node v;
 281                 const Graph &G = AG.constGraph();
 282                 double maxWidth = 0;
 283                 double maxHeight = 0;
 284                 forall_nodes(v,G) if(v->degree() == 0) {
 285                         isolated.pushBack(v);
 286                         if(AG.height(v) > maxHeight) maxHeight = AG.height(v);
 287                         if(AG.width(v) > maxWidth) maxWidth = AG.width(v);
 288                 }
 289                 // The nodes are placed on a line in the middle under the non isolated vertices.
 290                 // Each node gets a box sized 2 maxWidth.
 291                 double boxWidth = 2.0*maxWidth;
 292                 double commonYCoord = minY-(1.5*maxHeight);
 293                 double XCenterOfDrawing = minX + ((maxX-minX)/2.0);
 294                 double startXCoord = XCenterOfDrawing - 0.5*(isolated.size()*boxWidth);
 295                 ListIterator<node> it;
 296                 double xcoord = startXCoord;
 297                 for(it = isolated.begin(); it.valid(); ++it) {
 298                         v = *it;
 299                         AG.x(v) = xcoord;
 300                         AG.y(v) = commonYCoord;
 301                         xcoord += boxWidth;
 302                 }
 303         }
 304
 305         //this is the main optimization routine with the loop that lowers the temperature
 306         //and the disk radius geometrically until the temperature is zero. For each
 307         //temperature, a certain number of new positions for a random vertex are tried
 308         void DavidsonHarel::call(GraphAttributes &AG)
 309         {
 310                 initParameters();
 311
 312                 m_shrinkingFactor = m_shrinkFactor;
 313
 314                 OGDF_ASSERT(!m_energyFunctions.empty());
 315
 316                 const Graph &G = AG.constGraph();
 317                 //compute the list of vertices with degree greater than zero
 318                 G.allNodes(m_nonIsolatedNodes);
 319                 ListIterator<node> it,itSucc;
 320                 for(it = m_nonIsolatedNodes.begin(); it.valid(); it = itSucc) {
 321                         itSucc = it.succ();
 322                         if((*it)->degree() == 0) m_nonIsolatedNodes.del(it);
 323                 }
 324                 if(G.numberOfEdges() > 0) { //else only isolated nodes
 325                         computeFirstRadius(AG);
 326                         computeInitialEnergy();
 327                         if(m_numberOfIterations == 0)
 328                                 m_numberOfIterations = m_nonIsolatedNodes.size() * m_iterationMultiplier;
 329                         //this is the main optimization loop
 330                         while(m_temperature > 0) {
 331                                 //iteration loop for each temperature
 332                                 for(int ic = 1; ic <= m_numberOfIterations; ic ++) {
 333                                         DPoint newPos;
 334                                         //choose random vertex and new position for vertex
 335                                         node v = computeCandidateLayout(AG,newPos);
 336                                         //compute candidate energy and decide if new layout is chosen
 337                                         ListIterator<EnergyFunction*> it;
 338                                         ListIterator<double> it2 = m_weightsOfEnergyFunctions.begin();
 339                                         double newEnergy = 0.0;
 340                                         for(it = m_energyFunctions.begin(); it.valid(); it = it.succ()) {
 341                                                 newEnergy += (*it)->computeCandidateEnergy(v,newPos) * (*it2);
 342                                                 it2 = it2.succ();
 343                                         }
 344                                         OGDF_ASSERT(newEnergy >= 0.0);
 345                                         //this tests if the new layout is accepted. If this is the case,
 346                                         //all energy functions are informed that the new layout is accepted
 347                                         if(testEnergyValue(newEnergy)) {
 348                                                 for(it = m_energyFunctions.begin(); it.valid(); it = it.succ())
 349                                                         (*it)->candidateTaken();
 350                                                 AG.x(v) = newPos.m_x;
 351                                                 AG.y(v) = newPos.m_y;
 352                                                 m_energy = newEnergy;
 353                                         }
 354                                 }
 355                                 //lower the temperature and decrease the disk radius
 356                                 m_temperature = (int)floor(m_temperature*m_coolingFactor);
 357                                 m_diskRadius *= m_shrinkingFactor;
 358                         }
 359                 }
 360                 //if there are zero degree vertices, they are placed using placeIsolatedNodes
 361                 if(m_nonIsolatedNodes.size() != G.numberOfNodes())
 362                         placeIsolatedNodes(AG);
 363
 364         }
 365 } //namespace