ext/OGDF/src/energybased/CoinTutteLayout.cpp

   1 /*
   2  * $Revision: 2599 $
   3  *
   4  * last checkin:
   5  *   $Author: chimani $
   6  *   $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of Tutte's Algorithm
  11  *
  12  * \author David Alberts \and Andrea Wagner
  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 #ifdef USE_COIN
  44
  45 #include <ogdf/basic/Math.h>
  46 #include <ogdf/energybased/CoinTutteLayout.h>
  47 #include <ogdf/basic/GraphCopyAttributes.h>
  48 #include <ogdf/basic/extended_graph_alg.h>
  49
  50 namespace ogdf {
  51
  52 // solves a system of linear equations with a linear solver for optimization problems.
  53 // I'm sorry but there is no Gauss-Algorithm (or some numerical stuff) in OGDF...
  54 bool solveLP(
  55         int cols,
  56         const CoinPackedMatrix &Matrix,
  57         const Array<double> &rightHandSide,
  58         Array<double> &x)
  59 {
  60         int i;
  61
  62         OsiSolverInterface *osi = CoinManager::createCorrectOsiSolverInterface();
  63
  64         // constructs a dummy optimization problem.
  65         // The given system of equations is used as constraint.
  66         osi->setObjSense(-1);                        // maximize...
  67         Array<double> obj(0,cols-1,1);               // ...the sum of variables
  68         Array<double> lowerBound(0,cols-1,-1*(osi->getInfinity()));
  69         Array<double> upperBound(0,cols-1,osi->getInfinity());
  70
  71         // loads the problem to Coin-Osi
  72         osi->loadProblem(Matrix, &lowerBound[0], &upperBound[0], &obj[0], &rightHandSide[0], &rightHandSide[0]);
  73
  74         // solves the linear program
  75         osi->initialSolve();
  76
  77         // gets the solution and returns true if it is optimal
  78         const double *sol = osi->getColSolution();
  79         for(i=0; i<cols; i++) x[i] = sol[i];
  80
  81         if(osi->isProvenOptimal()) {
  82                 delete osi;
  83                 return true;
  84         }
  85         else {
  86                 delete osi;
  87                 return false;
  88         }
  89 }
  90
  91 TutteLayout::TutteLayout()
  92 {
  93         m_bbox = DRect (0.0, 0.0, 250.0, 250.0);
  94 }
  95
  96
  97
  98 // sets the positions of the nodes in a largest face of G in the form
  99 // of a regular k-gon. The corresponding nodes and their positions are
 100 // stored in nodes and pos, respectively.
 101 void TutteLayout::setFixedNodes(
 102         const Graph &G,
 103         List<node>& nodes,
 104         List<DPoint>& pos,
 105         double radius)
 106 {
 107         // compute faces of a copy of G
 108         GraphCopy GC(G);
 109
 110         // compute a planar embedding if \a G is planar
 111         if(isPlanar(G)) planarEmbed(GC);
 112         //FIXME this stuff above seems wrong!!
 113
 114         CombinatorialEmbedding E(GC);
 115         E.computeFaces();
 116
 117         // search for largest face
 118         face maxFace = E.maximalFace();
 119
 120         // delete possible old entries in nodes and pos
 121         nodes.clear();
 122         pos.clear();
 123
 124         // set nodes and pos
 125         NodeArray<bool> addMe(GC,true);
 126         adjEntry adj;
 127
 128         List<node> maxNodes;
 129         forall_face_adj(adj,maxFace) {
 130                 maxNodes.pushBack(adj->theNode());
 131         }
 132
 133         forall_nonconst_listiterators(node, it, maxNodes) {
 134                 node &w = *it;
 135                 if(addMe[w]) {
 136                         nodes.pushBack(w);
 137                         addMe[w] = false;
 138                 }
 139         }
 140
 141         double step  = 2.0 * Math::pi / (double)(nodes.size());
 142         double alpha = 0.0;
 143         forall_listiterators(node, it, nodes) {
 144                 pos.pushBack(DPoint(radius * cos(alpha), radius * sin(alpha)));
 145                 alpha += step;
 146         }
 147 }
 148
 149 // Overload setFixedNodes for given nodes
 150 void TutteLayout::setFixedNodes(
 151         const Graph &G,
 152         List<node>& nodes,
 153         const List<node>& givenNodes,
 154         List<DPoint>& pos,
 155         double radius)
 156 {
 157         GraphCopy GC(G);
 158
 159         // delete possible old entries in nodes and pos
 160         nodes.clear();
 161         pos.clear();
 162
 163         // set nodes and pos
 164
 165         forall_listiterators(node, it, givenNodes) {
 166                 node theOrig = *it;
 167                 node theCopy = GC.copy(theOrig);
 168                 nodes.pushBack(theCopy);
 169         }
 170
 171         double step  = 2.0 * Math::pi / (double)(nodes.size());
 172         double alpha = 0.0;
 173         forall_listiterators(node, it, nodes) {
 174                 pos.pushBack(DPoint(radius * cos(alpha), radius * sin(alpha)));
 175                 alpha += step;
 176         }
 177 }
 178
 179 void TutteLayout::call(GraphAttributes &AG, const List<node> &givenNodes)
 180 {
 181         const Graph &G = AG.constGraph();
 182
 183         List<node> fixedNodes;
 184         List<DPoint> positions;
 185
 186         double diam =
 187         sqrt((m_bbox.width()) * (m_bbox.width())
 188                  + (m_bbox.height()) * (m_bbox.height()));
 189
 190         // handle graphs with less than two nodes
 191         switch (G.numberOfNodes()) {
 192                 case 0:
 193                         return;
 194                 case 1:
 195                         node v = G.firstNode();
 196
 197                         DPoint center(0.5 * m_bbox.width(),0.5 * m_bbox.height());
 198                         center = center + m_bbox.p1();
 199
 200                         AG.x(v) = center.m_x;
 201                         AG.y(v) = center.m_y;
 202
 203                         return;
 204         }
 205
 206         // increase radius to have no overlap on the outer circle
 207         node v = G.firstNode();
 208
 209         double r        = diam/2.8284271;
 210         int    n        = G.numberOfNodes();
 211         double nodeDiam = 2.0*sqrt((AG.width(v)) * (AG.width(v))
 212                          + (AG.height(v)) * (AG.height(v)));
 213
 214         if(r<nodeDiam/(2*sin(2*Math::pi/n))) {
 215                 r=nodeDiam/(2*sin(2*Math::pi/n));
 216                 m_bbox = DRect (0.0, 0.0, 2*r, 2*r);
 217         }
 218
 219         setFixedNodes(G,fixedNodes,givenNodes,positions,r);
 220
 221         doCall(AG,fixedNodes,positions);
 222 }
 223
 224 void TutteLayout::call(GraphAttributes &AG)
 225 {
 226         const Graph &G = AG.constGraph();
 227
 228         List<node> fixedNodes;
 229         List<DPoint> positions;
 230
 231         double diam =
 232         sqrt((m_bbox.width()) * (m_bbox.width())
 233                  + (m_bbox.height()) * (m_bbox.height()));
 234
 235         // handle graphs with less than two nodes
 236         switch (G.numberOfNodes()) {
 237                 case 0:
 238                         return;
 239                 case 1:
 240                         node v = G.firstNode();
 241
 242                         DPoint center(0.5 * m_bbox.width(),0.5 * m_bbox.height());
 243                         center = center + m_bbox.p1();
 244
 245                         AG.x(v) = center.m_x;
 246                         AG.y(v) = center.m_y;
 247
 248                         return;
 249         }
 250
 251         // increase radius to have no overlap on the outer circle
 252         node v = G.firstNode();
 253
 254         double r        = diam/2.8284271;
 255         int n           = G.numberOfNodes();
 256         double nodeDiam = 2.0*sqrt((AG.width(v)) * (AG.width(v))
 257                          + (AG.height(v)) * (AG.height(v)));
 258
 259         if(r<nodeDiam/(2*sin(2*Math::pi/n))) {
 260                 r=nodeDiam/(2*sin(2*Math::pi/n));
 261                 m_bbox = DRect (0.0, 0.0, 2*r, 2*r);
 262         }
 263
 264         setFixedNodes(G,fixedNodes,positions,r);
 265
 266         doCall(AG,fixedNodes,positions);
 267 }
 268
 269
 270
 271 // does the actual computation. fixedNodes and fixedPositions
 272 // contain the nodes with fixed positions.
 273 bool TutteLayout::doCall(
 274         GraphAttributes &AG,
 275         const List<node> &fixedNodes,
 276         List<DPoint> &fixedPositions)
 277 {
 278         node v, w;
 279         edge e;
 280
 281         const Graph &G = AG.constGraph();
 282         GraphCopy GC(G);
 283         GraphCopyAttributes AGC(GC, AG);
 284
 285         // mark fixed nodes and set their positions in a
 286         NodeArray<bool> fixed(GC,false);
 287         forall_listiterators(node, it, fixedNodes) {
 288                 fixed[*it] = true;
 289                 DPoint p = fixedPositions.popFrontRet();   // slightly dirty...
 290                 fixedPositions.pushBack(p);          // ...
 291
 292                 AGC.x(*it) = p.m_x;
 293                 AGC.y(*it) = p.m_y;
 294         }
 295
 296         if(fixedNodes.size() == G.numberOfNodes()) {
 297                 forall_nodes(v,GC) {
 298                         AG.x(GC.original(v)) = AGC.x(v);
 299                         AG.y(GC.original(v)) = AGC.y(v);
 300                 }
 301                 return true;
 302                 }
 303                 // all nodes have fixed positions - nothing left to do
 304
 305                 // collect other nodes
 306                 List<node> otherNodes;
 307                 forall_nodes(v,GC) if(!fixed[v]) otherNodes.pushBack(v);
 308
 309                 NodeArray<int> ind(GC);       // position of v in otherNodes and A
 310
 311                 int i = 0;
 312
 313                 forall_listiterators(node, it, otherNodes) ind[*it] = i++;
 314
 315                 int n = otherNodes.size();           // #other nodes
 316                 Array<double> coord(n);              // coordinates (first x then y)
 317                 Array<double> rhs(n);                // right hand side
 318                 double oneOverD = 0.0;
 319
 320                 CoinPackedMatrix A(false,0,0);       // equations
 321                 A.setDimensions(n,n);
 322
 323                 // initialize non-zero entries in matrix A
 324                 forall_listiterators(node, it, otherNodes) {
 325                         oneOverD = (double)(1.0/((*it)->degree()));
 326                         forall_adj_edges(e,*it) {
 327                         // get second node of e
 328                         w = (*it == e->source()) ? e->target() : e->source();
 329                         if(!fixed[w]) {
 330                                 A.modifyCoefficient(ind[*it],ind[w],oneOverD);
 331                         }
 332                 }
 333                 A.modifyCoefficient(ind[*it],ind[*it],-1);
 334         }
 335
 336         // compute right hand side for x coordinates
 337         forall_listiterators(node, it, otherNodes) {
 338                 rhs[ind[*it]] = 0;
 339                 oneOverD = (double)(1.0/((*it)->degree()));
 340                 forall_adj_edges(e,*it) {
 341                         // get second node of e
 342                         w = (*it == e->source()) ? e->target() : e->source();
 343                         if(fixed[w]) rhs[ind[*it]] -= (oneOverD*AGC.x(w));
 344                 }
 345         }
 346
 347         // compute x coordinates
 348         if(!(solveLP(n, A, rhs, coord))) return false;
 349         forall_listiterators(node, it, otherNodes) AGC.x(*it) = coord[ind[*it]];
 350
 351         // compute right hand side for y coordinates
 352         forall_listiterators(node, it, otherNodes) {
 353                 rhs[ind[*it]] = 0;
 354                 oneOverD = (double)(1.0/((*it)->degree()));
 355                 forall_adj_edges(e,*it) {
 356                         // get second node of e
 357                         w = (*it == e->source()) ? e->target() : e->source();
 358                         if(fixed[w]) rhs[ind[*it]] -= (oneOverD*AGC.y(w));
 359                 }
 360         }
 361
 362         // compute y coordinates
 363         if(!(solveLP(n, A, rhs, coord))) return false;
 364         forall_listiterators(node, it, otherNodes) AGC.y(*it) = coord[ind[*it]];
 365
 366         // translate coordinates, such that the center lies in
 367         // the center of the bounding box
 368         DPoint center(0.5 * m_bbox.width(),0.5 * m_bbox.height());
 369
 370         forall_nodes (v, GC) {
 371                 AGC.x(v) += center.m_x;
 372                 AGC.y(v) += center.m_y;
 373         }
 374
 375         forall_nodes(v,GC) {
 376                 AG.x(GC.original(v)) = AGC.x(v);
 377                 AG.y(GC.original(v)) = AGC.y(v);
 378         }
 379
 380         return true;
 381 }
 382 } // end namespace ogdf
 383
 384 #endif