1 /* 2 * vim: ts=4 sw=4 et tw=0 wm=0 3 * 4 * libcola - A library providing force-directed network layout using the 5 * stress-majorization method subject to separation constraints. 6 * 7 * Copyright (C) 2006-2015 Monash University 8 * 9 * This library is free software; you can redistribute it and/or 10 * modify it under the terms of the GNU Lesser General Public 11 * License as published by the Free Software Foundation; either 12 * version 2.1 of the License, or (at your option) any later version. 13 * See the file LICENSE.LGPL distributed with the library. 14 * 15 * This library is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 18 * 19 * Author(s): Tim Dwyer 20 * Michael Wybrow 21 */ 22 23 #ifndef COLA_H 24 #define COLA_H 25 26 #include <utility> 27 #include <iterator> 28 #include <vector> 29 #include <valarray> 30 #include <algorithm> 31 #include <cmath> 32 #include <iostream> 33 34 #include "libcola/gradient_projection.h" 35 #include "libcola/cluster.h" 36 #include "libcola/straightener.h" 37 #include "libcola/exceptions.h" 38 #include "libcola/pseudorandom.h" 39 40 namespace vpsc { class Rectangle; } 41 namespace topology { 42 class ColaTopologyAddon; 43 } 44 namespace dialect { 45 class Graph; 46 } 47 48 49 /** 50 * @namespace cola 51 * @brief libcola: Force-directed network layout subject to 52 * separation constraints library. 53 * 54 * You should use COLA via an instance of the ConstrainedFDLayout class. 55 */ 56 namespace cola { 57 58 class NonOverlapConstraints; 59 class NonOverlapConstraintExemptions; 60 61 //! @brief A vector of node Indexes. 62 typedef std::vector<unsigned> NodeIndexes; 63 64 //! @brief A vector of NodeIndexes. 65 typedef std::vector<NodeIndexes> ListOfNodeIndexes; 66 67 //! Edges are simply a pair of indices to entries in the Node vector 68 typedef std::pair<unsigned, unsigned> Edge; 69 70 //! EdgeLengths is a vector of ideal lengths for edges corresponding to 71 //! edges in the edge list. 72 typedef std::vector<double> EdgeLengths; 73 #define StandardEdgeLengths EdgeLengths() 74 75 /** 76 * @brief A Lock specifies a required position for a node. 77 */ 78 class Lock { 79 public: Lock()80 Lock() {} 81 /** 82 * @brief Constructs a Lock object for a given node and position. 83 * 84 * @param[in] id The index of the node in the Rectangles vector. 85 * @param[in] X The node's fixed position in the x-dimension. 86 * @param[in] Y The node's fixed position in the y-dimension. 87 */ Lock(unsigned id,double X,double Y)88 Lock(unsigned id, double X, double Y) : id(id), x(X), y(Y) { 89 } getID()90 unsigned getID() const { 91 return id; 92 } pos(vpsc::Dim dim)93 double pos(vpsc::Dim dim) const { 94 return dim==vpsc::HORIZONTAL?x:y; 95 } 96 private: 97 unsigned id; 98 double x; 99 double y; 100 }; 101 //! @brief A vector of Lock objects. 102 typedef std::vector<cola::Lock> Locks; 103 104 /** 105 * @brief A Resize specifies a new required bounding box for a node. 106 */ 107 class Resize { 108 public: Resize()109 Resize() {} 110 /** 111 * @brief Constructs a Resize object for a given node and it's new 112 * bounding box. 113 * 114 * @param[in] id The index of the node in the Rectangles vector. 115 * @param[in] x The minimum horizontal value for the node's new 116 * bounding box. 117 * @param[in] y The minimum vertical value for the node's new 118 * bounding box. 119 * @param[in] w The width value for the node's new bounding box. 120 * @param[in] h The height value for the node's new bounding box. 121 */ Resize(unsigned id,double x,double y,double w,double h)122 Resize(unsigned id, double x, double y, double w, double h) 123 : id(id), target(x,x+w,y,y+h) {} getID()124 unsigned getID() const { 125 return id; 126 } getTarget()127 const vpsc::Rectangle* getTarget() const { 128 return ⌖ 129 } 130 private: 131 unsigned id; 132 vpsc::Rectangle target; 133 }; 134 //! @brief A vector of Resize objects. 135 typedef std::vector<cola::Resize> Resizes; 136 137 /* 138 * Setting a desired position for a node adds a term to the goal function 139 * drawing the node towards that desired position 140 */ 141 struct DesiredPosition { 142 unsigned id; 143 double x; 144 double y; 145 double weight; 146 }; 147 typedef std::vector<cola::DesiredPosition> DesiredPositions; 148 149 /* 150 * desired positions which should override those computed by applying forces 151 * are passed in for a set of nodes. The first entry is the Node->id, the 152 * second is the desired position. 153 */ 154 typedef std::pair<unsigned,double> DesiredPositionInDim; 155 typedef std::vector<DesiredPositionInDim> DesiredPositionsInDim; 156 157 /** 158 * @brief A default functor that is called before each iteration in the 159 * main loop of the ConstrainedFDLayout::run() method. 160 * 161 * Override the operator() for things like locking the position of nodes 162 * for the duration of the iteration. 163 * 164 * If the operator() returns false the subsequent iterations are 165 * abandoned, i.e., layout ends immediately. You can make it return true 166 * when a user-interrupt is detected, for instance. 167 */ 168 class PreIteration { 169 public: 170 /** 171 * @brief Constructs a PreIteration object that handles locking and 172 * resizing of nodes. 173 * 174 * @param[in] locks A list of nodes (by index) and positions at which 175 * they should be locked. 176 * @param[in] resizes A list of nodes (by index) and required dimensions 177 * for their bounding rects to be resized to. 178 */ 179 PreIteration( 180 Locks& locks=__locksNotUsed, 181 Resizes& resizes=__resizesNotUsed) locks(locks)182 : locks(locks) 183 , resizes(resizes) 184 , changed(true) {} PreIteration(Resizes & resizes)185 PreIteration(Resizes& resizes) 186 : locks(__locksNotUsed) 187 , resizes(resizes) 188 , changed(true) {} 189 190 // To prevent C++ objects from being destroyed in garbage collected languages 191 // when the libraries are called from SWIG, we hide the declarations of the 192 // destructors and prevent generation of default destructors. 193 #ifndef SWIG ~PreIteration()194 virtual ~PreIteration() {} 195 #endif operator()196 virtual bool operator()() { return true; } 197 Locks& locks; 198 Resizes& resizes; 199 bool changed; 200 private: 201 static Locks __locksNotUsed; 202 static Resizes __resizesNotUsed; 203 }; 204 205 /** 206 * @brief A default functor that is called after each iteration of the layout 207 * algorithm. 208 * 209 * You can either instantiate ConstrainedFDLayout with an instance of this 210 * class setting the tolerance and maxiterations as desired, or create a 211 * derived class implementing the operator() to do your own convergence test, 212 * or create your own operator() that calls the TestConvergence::operator() in 213 * order to do any other post processing you might need, e.g., to animate 214 * changes. 215 */ 216 class TestConvergence { 217 public: 218 double old_stress; 219 TestConvergence(const double tol = 1e-4, const unsigned maxiterations = 100) tolerance(tol)220 : tolerance(tol), 221 maxiterations(maxiterations) 222 { reset(); } ~TestConvergence()223 virtual ~TestConvergence() {} 224 225 public: operator()226 virtual bool operator()(const double new_stress, std::valarray<double> & X, std::valarray<double> & Y) 227 { 228 COLA_UNUSED(X); 229 COLA_UNUSED(Y); 230 231 iterations++; 232 //std::cout<<"iteration="<<iterations<<", old_stress="<<old_stress<<", new_stress="<<new_stress<<std::endl; 233 if (old_stress == DBL_MAX) { 234 old_stress = new_stress; 235 return iterations >= maxiterations; 236 } 237 // converged if relative decrease in stress falls below threshold 238 // or if stress increases (shouldn't happen for straight majorization) 239 bool converged = 240 (old_stress - new_stress) / (new_stress + 1e-10) < tolerance 241 || iterations > maxiterations; 242 old_stress = new_stress; 243 return converged; 244 } reset()245 void reset() { 246 old_stress = DBL_MAX; 247 iterations = 0; 248 } 249 const double tolerance; 250 const unsigned maxiterations; 251 unsigned iterations; 252 }; 253 254 /** 255 * @brief Implements the Constrained Majorization graph layout algorithm 256 * (deprecated). 257 * 258 * The optimisation method used is "stress majorization", where a sequence of 259 * quadratic functions which strictly bound the stress from above, is solved 260 * to monotonically reduce the stress (by iteratively changing the 261 * configuration of nodes). 262 * 263 * Once the problem has been set up, call run() or runOnce() to run the 264 * layout algorithm. 265 * 266 * @note We recommend the use of ConstrainedFDLayout instead of this class. 267 * ConstrainedFDLayout tends to produce better results and has more 268 * features. We are no longer working on ConstrainedMajorizationLayout. 269 */ 270 class ConstrainedMajorizationLayout { 271 public: 272 /** 273 * @brief Constructs a constrained majorization layout instance. 274 * 275 * @param[in] rs Bounding boxes of nodes at their initial positions. 276 * @param[in] es Simple pair edges, giving indices of the start and end 277 * nodes in rs. 278 * @param[in] clusterHierarchy A pointer to a RootCluster object defining 279 * the cluster hierarchy (optional). 280 * @param[in] idealLength Aa scalar modifier of ideal edge lengths in 281 * eLengths. 282 * @param[in] eLengths Individual ideal lengths for edges. 283 * The actual ideal length used for the ith edge is 284 * idealLength*eLengths[i], or if eLengths is empty 285 * then just idealLength is used (i.e., eLengths[i] 286 * is assumed to be 1). 287 * @param[in] done A test of convergence operation called at the end of 288 * each iteration (optional). 289 * @param[in] preIteration An operation called before each iteration 290 * (optional). 291 */ 292 ConstrainedMajorizationLayout( 293 vpsc::Rectangles& rs, 294 std::vector<Edge> const & es, 295 RootCluster* clusterHierarchy, 296 const double idealLength, 297 EdgeLengths eLengths = StandardEdgeLengths, 298 TestConvergence *doneTest = nullptr, 299 PreIteration* preIteration=nullptr, 300 bool useNeighbourStress = false); 301 /** 302 * @brief Specify a set of compound constraints to apply to the layout. 303 * 304 * @param[in] ccs The compound constraints. 305 */ setConstraints(cola::CompoundConstraints * ccs)306 void setConstraints(cola::CompoundConstraints* ccs) { 307 constrainedLayout = true; 308 this->ccs=ccs; 309 } 310 setConstraintsVector(cola::CompoundConstraints & ccs)311 void setConstraintsVector(cola::CompoundConstraints& ccs) { 312 constrainedLayout = true; 313 cola::CompoundConstraints *ccsp = new cola::CompoundConstraints; 314 for (size_t i = 0; i < ccs.size(); ++i) { 315 ccsp->push_back(ccs.at(i)); 316 } 317 this->ccs=ccsp; 318 } 319 320 /** 321 * @brief Register to receive information about unsatisfiable constraints. 322 * 323 * In the case of unsatisifiable constraints, the solver will drop 324 * unsatisfiable constraints of lowest priority. Information about these 325 * will be written to these lists after each iteration of constrained 326 * layout. 327 * 328 * param[out] unsatisfiableX A pointer to an UnsatisfiableConstraintInfos 329 * object that will be used to record 330 * unsatisfiable constraints in the x-dimension. 331 * param[out] unsatisfiableY A pointer to an UnsatisfiableConstraintInfos 332 * object that will be used to record 333 * unsatisfiable constraints in the y-dimension. 334 */ setUnsatisfiableConstraintInfo(UnsatisfiableConstraintInfos * unsatisfiableX,UnsatisfiableConstraintInfos * unsatisfiableY)335 void setUnsatisfiableConstraintInfo( 336 UnsatisfiableConstraintInfos *unsatisfiableX, 337 UnsatisfiableConstraintInfos *unsatisfiableY) { 338 this->unsatisfiableX = unsatisfiableX; 339 this->unsatisfiableY = unsatisfiableY; 340 } 341 /** 342 * Sticky nodes causes nodes to spring back to (startX,startY) when 343 * unconstrained. 344 */ 345 void setStickyNodes(const double stickyWeight, 346 std::valarray<double> const & startX, 347 std::valarray<double> const & startY); 348 349 /** 350 * Scaling speeds up the solver by conditioning the quadratic terms matrix. 351 */ setScaling(bool scaling)352 void setScaling(bool scaling) { 353 this->scaling=scaling; 354 } 355 /** 356 * Says that the Mosek optimisation library should be used to solve the 357 * quadratic programs rather than the libvpsc solver. 358 */ setExternalSolver(bool externalSolver)359 void setExternalSolver(bool externalSolver) { 360 this->externalSolver=externalSolver; 361 } 362 /** 363 * At each iteration of layout, generate constraints to avoid overlaps. 364 * If bool horizontal is true, all overlaps will be resolved horizontally, 365 * otherwise some overlaps will be left to be resolved vertically where 366 * doing so leads to less displacement 367 */ 368 void setAvoidOverlaps(bool horizontal = false) { 369 constrainedLayout = true; 370 this->avoidOverlaps = horizontal ? Horizontal : Both; 371 } 372 /** 373 * Add constraints to prevent clusters overlapping. 374 */ setNonOverlappingClusters()375 void setNonOverlappingClusters() { 376 constrainedLayout = true; 377 nonOverlappingClusters = true; 378 } 379 /** 380 * For the specified edges (with routings), generate dummy vars and 381 * constraints to try and straighten them. bendWeight controls how hard we 382 * try to straighten existing bends potBendWeight controls how much we try 383 * to keep straight edges straight 384 */ 385 void setStraightenEdges(std::vector<straightener::Edge*>* straightenEdges, 386 double bendWeight = 0.01, double potBendWeight = 0.1, 387 bool xSkipping = true) { 388 for(std::vector<straightener::Edge*>::const_iterator e=straightenEdges->begin(); 389 e!=straightenEdges->end();e++) { 390 (*e)->rerouteAround(boundingBoxes); 391 } 392 constrainedLayout = true; 393 this->xSkipping = xSkipping; 394 this->straightenEdges = straightenEdges; 395 this->bendWeight = bendWeight; 396 this->potBendWeight = potBendWeight; 397 } 398 /** 399 * Update position of bounding boxes. 400 */ moveBoundingBoxes()401 void moveBoundingBoxes() { 402 for(unsigned i=0;i<n;i++) { 403 boundingBoxes[i]->moveCentre(X[i],Y[i]); 404 } 405 } 406 ~ConstrainedMajorizationLayout()407 ~ConstrainedMajorizationLayout() { 408 if (using_default_done) 409 { 410 delete done; 411 } 412 413 if(constrainedLayout) { 414 delete gpX; 415 delete gpY; 416 } 417 } 418 /** 419 * @brief Implements the main layout loop, taking descent steps until 420 * stress is no-longer significantly reduced. 421 * 422 * @param[in] x If true, layout will be performed in x-dimension 423 * (default: true). 424 * @param[in] y If true, layout will be performed in y-dimension 425 * (default: true). 426 */ 427 void run(bool x=true, bool y=true); 428 /** 429 * @brief Same as run(), but only applies one iteration. 430 * 431 * This may be useful here it's too hard to implement a call-back 432 * (e.g., in java apps). 433 * 434 * @param[in] x If true, layout will be performed in x-dimension 435 * (default: true). 436 * @param[in] y If true, layout will be performed in y-dimension 437 * (default: true). 438 */ 439 void runOnce(bool x=true, bool y=true); 440 void straighten(std::vector<straightener::Edge*>&, vpsc::Dim); setConstrainedLayout(bool c)441 void setConstrainedLayout(bool c) { 442 constrainedLayout=c; 443 } 444 double computeStress(); 445 private: euclidean_distance(unsigned i,unsigned j)446 double euclidean_distance(unsigned i, unsigned j) { 447 return sqrt( 448 (X[i] - X[j]) * (X[i] - X[j]) + 449 (Y[i] - Y[j]) * (Y[i] - Y[j])); 450 } 451 double compute_stress(std::valarray<double> const & Dij); 452 void majorize(std::valarray<double> const & Dij,GradientProjection* gp, std::valarray<double>& coords, std::valarray<double> const & startCoords); 453 void newton(std::valarray<double> const & Dij,GradientProjection* gp, std::valarray<double>& coords, std::valarray<double> const & startCoords); 454 unsigned n; //< number of nodes 455 //std::valarray<double> degrees; 456 std::valarray<double> lap2; //< graph laplacian 457 std::valarray<double> Q; //< quadratic terms matrix used in computations 458 std::valarray<double> Dij; //< all pairs shortest path distances 459 double tol; //< convergence tolerance 460 TestConvergence *done; //< functor used to determine if layout is finished 461 bool using_default_done; // Whether we allocated a default TestConvergence object. 462 PreIteration* preIteration; //< client can use this to create locks on nodes 463 vpsc::Rectangles boundingBoxes; //< node bounding boxes 464 /* 465 * stickyNodes controls whether nodes are attracted to their starting 466 * positions (at time of ConstrainedMajorizationLayout instantiation) 467 * stored in startX, startY 468 */ 469 std::valarray<double> X, Y; 470 bool stickyNodes; 471 double stickyWeight; 472 std::valarray<double> startX; 473 std::valarray<double> startY; 474 double edge_length; 475 bool constrainedLayout; 476 bool nonOverlappingClusters; 477 /* 478 * A cluster is a set of nodes that are somehow semantically grouped 479 * and should therefore be kept together a bit more tightly than, and 480 * preferably without overlapping, the rest of the graph. 481 * 482 * We achieve this by augmenting the L matrix with stronger attractive 483 * forces between all members of a cluster (other than the root) 484 * and by maintaining a (preferably convex) hull around those 485 * constituents which, using constraints and dummy variables, is 486 * prevented from overlapping other parts of the graph. 487 * 488 * Clusters are defined over the graph in a hierarchy starting with 489 * a single root cluster. 490 * 491 * Need to: 492 * - augment Lap matrix with intra cluster forces 493 * - compute convex hull of each cluster 494 * - from convex hull generate "StraightenEdges" 495 */ 496 RootCluster *clusterHierarchy; 497 GradientProjection *gpX, *gpY; 498 cola::CompoundConstraints *ccs; 499 UnsatisfiableConstraintInfos *unsatisfiableX, *unsatisfiableY; 500 NonOverlapConstraintsMode avoidOverlaps; 501 std::vector<straightener::Edge*>* straightenEdges; 502 503 double bendWeight, potBendWeight; 504 /* 505 * determines whether we should leave some overlaps to be resolved 506 * vertically when generating straightening constraints in the x-dim 507 */ 508 bool xSkipping; 509 /* 510 * when using the gradient projection optimisation method, the following 511 * controls whether the problem should be preconditioned by affine scaling 512 */ 513 bool scaling; 514 /* 515 * if the Mosek quadratic programming environment is available it may be 516 * used to solve each iteration of stress majorization... slow but useful 517 * for testing 518 */ 519 bool externalSolver; 520 bool majorization; 521 }; 522 523 vpsc::Rectangle bounds(vpsc::Rectangles& rs); 524 525 class ConstrainedFDLayout; 526 527 /** 528 * @brief Interface for writing COLA addons to handle topology preserving 529 * layout. 530 */ 531 class TopologyAddonInterface 532 { 533 public: TopologyAddonInterface()534 TopologyAddonInterface() 535 { 536 } 537 ~TopologyAddonInterface()538 virtual ~TopologyAddonInterface() 539 { 540 } 541 clone(void)542 virtual TopologyAddonInterface *clone(void) const 543 { 544 return new TopologyAddonInterface(*this); 545 } 546 freeAssociatedObjects(void)547 virtual void freeAssociatedObjects(void) 548 { 549 } 550 handleResizes(const Resizes & resizeList,unsigned n,std::valarray<double> & X,std::valarray<double> & Y,cola::CompoundConstraints & ccs,vpsc::Rectangles & boundingBoxes,cola::RootCluster * clusterHierarchy)551 virtual void handleResizes(const Resizes& resizeList, unsigned n, 552 std::valarray<double>& X, std::valarray<double>& Y, 553 cola::CompoundConstraints& ccs, 554 vpsc::Rectangles& boundingBoxes, 555 cola::RootCluster* clusterHierarchy) 556 { 557 COLA_UNUSED(resizeList); 558 COLA_UNUSED(n); 559 COLA_UNUSED(X); 560 COLA_UNUSED(Y); 561 COLA_UNUSED(ccs); 562 COLA_UNUSED(boundingBoxes); 563 COLA_UNUSED(clusterHierarchy); 564 } computePathLengths(unsigned short ** G)565 virtual void computePathLengths(unsigned short** G) 566 { 567 COLA_UNUSED(G); 568 } computeStress(void)569 virtual double computeStress(void) const 570 { 571 return 0; 572 } useTopologySolver(void)573 virtual bool useTopologySolver(void) const 574 { 575 return false; 576 } makeFeasible(bool generateNonOverlapConstraints,vpsc::Rectangles & boundingBoxes,cola::RootCluster * clusterHierarchy)577 virtual void makeFeasible(bool generateNonOverlapConstraints, 578 vpsc::Rectangles& boundingBoxes, 579 cola::RootCluster* clusterHierarchy) 580 { 581 COLA_UNUSED(generateNonOverlapConstraints); 582 COLA_UNUSED(boundingBoxes); 583 COLA_UNUSED(clusterHierarchy); 584 } moveTo(const vpsc::Dim dim,vpsc::Variables & vs,vpsc::Constraints & cs,std::valarray<double> & coords,cola::RootCluster * clusterHierarchy)585 virtual void moveTo(const vpsc::Dim dim, vpsc::Variables& vs, 586 vpsc::Constraints& cs, std::valarray<double> &coords, 587 cola::RootCluster* clusterHierarchy) 588 { 589 COLA_UNUSED(dim); 590 COLA_UNUSED(vs); 591 COLA_UNUSED(cs); 592 COLA_UNUSED(coords); 593 COLA_UNUSED(clusterHierarchy); 594 } applyForcesAndConstraints(ConstrainedFDLayout * layout,const vpsc::Dim dim,std::valarray<double> & g,vpsc::Variables & vs,vpsc::Constraints & cs,std::valarray<double> & coords,DesiredPositionsInDim & des,double oldStress)595 virtual double applyForcesAndConstraints(ConstrainedFDLayout *layout, 596 const vpsc::Dim dim, std::valarray<double>& g, 597 vpsc::Variables& vs, vpsc::Constraints& cs, 598 std::valarray<double> &coords, 599 DesiredPositionsInDim& des, double oldStress) 600 { 601 COLA_UNUSED(layout); 602 COLA_UNUSED(dim); 603 COLA_UNUSED(g); 604 COLA_UNUSED(vs); 605 COLA_UNUSED(cs); 606 COLA_UNUSED(coords); 607 COLA_UNUSED(des); 608 COLA_UNUSED(oldStress); 609 return 0; 610 } 611 }; 612 613 614 /** 615 * @brief Implements a constrained force-directed layout algorithm. 616 * 617 * This method is based on a non-linear gradient projection technique. 618 * Conceptually it's similar to a force directed method like 619 * Fruchterman-Reingold---but using a more principled goal function and 620 * optimisation techniques. 621 */ 622 class ConstrainedFDLayout { 623 public: 624 /** 625 * @brief Constructs a constrained force-directed layout instance. 626 * 627 * If an empty edges (es) vector is passed to the constructor, then 628 * constraint satisfaction will be performed, but no force-directed 629 * layout. In this case, idealLength and eLengths have no effect. 630 * 631 * Conversely, if no constraints or clusters are specified and no overlap 632 * prevention is enabled, but edge info is given, then pure force-directed 633 * layout will be performed. 634 * 635 * @param[in] rs Bounding boxes of nodes at their initial positions. 636 * @param[in] es Simple pair edges, giving indices of the start and end 637 * nodes in rs. 638 * @param[in] idealLength A scalar modifier of ideal edge lengths in 639 * eLengths or of 1 if no ideal lengths are 640 * specified. 641 * @param[in] eLengths Individual ideal lengths for edges. 642 * The actual ideal length used for the ith edge is 643 * idealLength*eLengths[i], or if eLengths is nullptr a 644 * then just idealLength is used (i.e., eLengths[i] 645 * is assumed to be 1). 646 * @param[in] done A test of convergence operation called at the end of 647 * each iteration (optional). If not given, uses a 648 * default TestConvergence object. 649 * @param[in] preIteration An operation called before each iteration 650 * (optional). 651 */ 652 ConstrainedFDLayout( 653 const vpsc::Rectangles& rs, 654 const std::vector<cola::Edge>& es, 655 const double idealLength, 656 const EdgeLengths& eLengths = StandardEdgeLengths, 657 TestConvergence* doneTest = nullptr, 658 PreIteration* preIteration = nullptr); 659 ~ConstrainedFDLayout(); 660 661 /** 662 * @brief Implements the main layout loop, taking descent steps until 663 * stress is no-longer significantly reduced. 664 * 665 * @param[in] x If true, layout will be performed in x-dimension 666 * (default: true). 667 * @param[in] y If true, layout will be performed in y-dimension 668 * (default: true). 669 */ 670 void run(bool x=true, bool y=true); 671 672 /** 673 * @brief Same as run(), but only applies one iteration. 674 * 675 * This may be useful here it's too hard to implement a call-back 676 * (e.g., in java apps). 677 * 678 * @param[in] x If true, layout will be performed in x-dimension 679 * (default: true). 680 * @param[in] y If true, layout will be performed in y-dimension 681 * (default: true). 682 */ 683 void runOnce(bool x=true, bool y=true); 684 685 /** 686 * @brief Specify a set of compound constraints to apply to the layout. 687 * 688 * @param[in] ccs The compound constraints. 689 */ 690 void setConstraints(const cola::CompoundConstraints& ccs); 691 692 /** 693 * @brief Specifies whether non-overlap constraints should be 694 * automatically generated between all nodes, as well as any 695 * exemptions to this. 696 * 697 * The optional second parameter indicates groups of nodes that should be 698 * exempt from having non-overlap constraints generated between each other. 699 * For example, you might want to do this for nodes representing ports, or 700 * the child nodes in a particular cluster. 701 * 702 * @param[in] avoidOverlaps New boolean value for this option. 703 * @param[in] listOfNodeGroups A list of groups of node indexes which will 704 * not have non-overlap constraints generated 705 * between each other. 706 */ 707 void setAvoidNodeOverlaps(bool avoidOverlaps, 708 ListOfNodeIndexes listOfNodeGroups = 709 ListOfNodeIndexes()); 710 711 /** 712 * @brief Set an addon for doing topology preserving layout. 713 * 714 * It is expected that you would use the topology::ColaTopologyAddon() 715 * from libtopology rather than write your own. This is done so that 716 * libcola does not have to depend on libtopology. 717 * 718 * @param[in] topology Instance of a class implementing the 719 * TopologyAddonInterface. 720 * @sa topology::ColaTopologyAddon 721 */ 722 void setTopology(TopologyAddonInterface *topology); 723 TopologyAddonInterface *getTopology(void); 724 725 void setDesiredPositions(DesiredPositions *desiredPositions); 726 727 /** 728 * @brief Specifies an optional hierarchy for clustering nodes. 729 * 730 * @param[in] hierarchy A pointer to a RootCluster object defining the 731 * the cluster hierarchy (optional). 732 */ setClusterHierarchy(RootCluster * hierarchy)733 void setClusterHierarchy(RootCluster *hierarchy) 734 { 735 clusterHierarchy = hierarchy; 736 } 737 /** 738 * @brief Register to receive information about unsatisfiable constraints. 739 * 740 * In the case of unsatisifiable constraints, the solver will drop 741 * unsatisfiable constraints of lowest priority. Information about these 742 * will be written to these lists after each iteration of constrained 743 * layout. 744 * 745 * param[out] unsatisfiableX A pointer to a UnsatisfiableConstraintInfos 746 * object that will be used to record 747 * unsatisfiable constraints in the x-dimension. 748 * param[out] unsatisfiableY A pointer to a UnsatisfiableConstraintInfos 749 * object that will be used to record 750 * unsatisfiable constraints in the y-dimension. 751 */ setUnsatisfiableConstraintInfo(UnsatisfiableConstraintInfos * unsatisfiableX,UnsatisfiableConstraintInfos * unsatisfiableY)752 void setUnsatisfiableConstraintInfo( 753 UnsatisfiableConstraintInfos *unsatisfiableX, 754 UnsatisfiableConstraintInfos *unsatisfiableY) 755 { 756 unsatisfiable.resize(2); 757 unsatisfiable[0]=unsatisfiableX; 758 unsatisfiable[1]=unsatisfiableY; 759 } 760 /** 761 * @brief Finds a feasible starting position for nodes that satisfies the 762 * given constraints. 763 * 764 * Starts with an initial position (x, y) for the nodes. This position 765 * is then iteratively updated with a greedy heuristic that tries adding 766 * additional constraints based on compound constraint priority to the 767 * satisfiable set, so as to satisfy as many of the placement constraints 768 * as possible. This includes automatically generated constraints for 769 * non-overlap and cluster containment. 770 * 771 * @param[in] xBorder Optional border width to add to left and right 772 * sides of rectangles. Defaults to 1. 773 * @param[in] yBorder Optional border width to add to top and bottom 774 * sides of rectangles. Defaults to 1. 775 * 776 * @note This method doesn't do force-directed layout. All forces are 777 * ignored and it merely satisfies the constraints with minimal 778 * movement to nodes. 779 */ 780 void makeFeasible(double xBorder=1, double yBorder=1); 781 782 /** 783 * @brief A convenience method that can be called from Java to free 784 * the memory of nodes (Rectangles), CompoundConstraints, etc. 785 * 786 * This assumes that the ConstrainedFDLayout instance takes ownership 787 * of all the objects passed to it. 788 * 789 * This is useful because in SWIG we have problems with Java wrapper 790 * classes going out of scope and causing objects like Rectanges to 791 * sometimes be freed when the layout instance still needs them. For 792 * this reason we prevent the Java wrappers from deleting the internal 793 * C++ instances, and let them be cleaned up later via this method. 794 */ 795 void freeAssociatedObjects(void); 796 797 //! @brief Generates an SVG file containing debug output and code that 798 //! can be used to regenerate the instance. 799 //! 800 //! This method can be called before or after run() or makeFeasible() 801 //! have been called. 802 //! 803 //! @param[in] filename A string indicating the filename (without 804 //! extension) for the output file. Defaults to 805 //! "libcola-debug.svg" if no filename is given. 806 //! 807 void outputInstanceToSVG(std::string filename = std::string()); 808 809 /** 810 * @brief Specifies whether neighbour stress should be used. 811 * 812 * Under neighbour stress, only the terms representing neighbouring 813 * nodes contribute to the stress function. This can help to distribute 814 * nodes more evenly, eliminating long-range forces. 815 * 816 * Default value is false. 817 * 818 * @param[in] useNeighbourStress New boolean value for this option. 819 */ 820 void setUseNeighbourStress(bool useNeighbourStress); 821 822 /** 823 * @brief Retrieve a copy of the "D matrix" computed by the computePathLengths 824 * method, linearised as a vector. 825 * 826 * This is especially useful for projects in SWIG target languages that want to 827 * do their own computations with stress. 828 * 829 * D is the required euclidean distances between pairs of nodes 830 * based on the shortest paths between them (using 831 * m_idealEdgeLength*eLengths[edge] as the edge length, if eLengths array 832 * is provided otherwise just m_idealEdgeLength). 833 * 834 * @return vector representing the D matrix. 835 */ 836 std::vector<double> readLinearD(void); 837 838 /** 839 * @brief Retrieve a copy of the "G matrix" computed by the computePathLengths 840 * method, linearised as a vector. 841 * 842 * * This is especially useful for projects in SWIG target languages that want to 843 * do their own computations with stress. 844 * 845 * G is a matrix of unsigned ints such that G[u][v]= 846 * 0 if there are no forces required between u and v 847 * (for example, if u and v are in unconnected components) 848 * 1 if attractive forces are required between u and v 849 * (i.e. if u and v are immediately connected by an edge and there is 850 * no topology route between u and v (for which an attractive force 851 * is computed elsewhere)) 852 * 2 if no attractive force is required between u and v but there is 853 * a connected path between them. 854 * 855 * @return vector representing the G matrix. 856 */ 857 std::vector<unsigned> readLinearG(void); 858 859 double computeStress() const; 860 861 private: 862 unsigned n; // number of nodes 863 std::valarray<double> X, Y; 864 vpsc::Rectangles boundingBoxes; 865 double applyForcesAndConstraints(const vpsc::Dim dim,const double oldStress); 866 double computeStepSize(const SparseMatrix& H, const std::valarray<double>& g, 867 const std::valarray<double>& d) const; 868 void computeDescentVectorOnBothAxes(const bool xaxis, const bool yaxis, 869 double stress, std::valarray<double>& x0, std::valarray<double>& x1); 870 void moveTo(const vpsc::Dim dim, std::valarray<double>& target); 871 double applyDescentVector( 872 const std::valarray<double>& d, 873 const std::valarray<double>& oldCoords, 874 std::valarray<double> &coords, 875 const double oldStress, 876 double stepsize 877 /*,topology::TopologyConstraints *s=nullptr*/); 878 void computePathLengths( 879 const std::vector<Edge>& es, std::valarray<double> eLengths); 880 void generateNonOverlapAndClusterCompoundConstraints( 881 vpsc::Variables (&vs)[2]); 882 void handleResizes(const Resizes&); 883 void setPosition(std::valarray<double>& pos); 884 void moveBoundingBoxes(); 885 bool noForces(double, double, unsigned) const; 886 void computeForces(const vpsc::Dim dim, SparseMap &H, 887 std::valarray<double> &g); 888 void recGenerateClusterVariablesAndConstraints( 889 vpsc::Variables (&vars)[2], unsigned int& priority, 890 cola::NonOverlapConstraints *noc, Cluster *cluster, 891 cola::CompoundConstraints& idleConstraints); 892 std::vector<double> offsetDir(double minD); 893 894 void computeNeighbours(std::vector<Edge> es); 895 std::vector<std::vector<unsigned> > neighbours; 896 std::vector<std::vector<double> > neighbourLengths; 897 TestConvergence *done; 898 bool using_default_done; // Whether we allocated a default TestConvergence object. 899 PreIteration* preIteration; 900 cola::CompoundConstraints ccs; 901 double** D; 902 unsigned short** G; 903 double minD; 904 PseudoRandom random; 905 906 TopologyAddonInterface *topologyAddon; 907 std::vector<UnsatisfiableConstraintInfos*> unsatisfiable; 908 bool rungekutta; 909 DesiredPositions *desiredPositions; 910 cola::CompoundConstraints extraConstraints; 911 912 RootCluster *clusterHierarchy; 913 double rectClusterBuffer; 914 double m_idealEdgeLength; 915 bool m_generateNonOverlapConstraints; 916 bool m_useNeighbourStress; 917 const std::valarray<double> m_edge_lengths; 918 919 NonOverlapConstraintExemptions *m_nonoverlap_exemptions; 920 921 friend class topology::ColaTopologyAddon; 922 friend class dialect::Graph; 923 }; 924 925 struct ProjectionResult { 926 int errorLevel; 927 std::string unsatinfo; 928 }; 929 930 /** 931 * @brief Attempt to do a projection onto a vector of cola CompoundConstraints. 932 * @param dim the dimension in which to perform the projection 933 * @param rs the rectangles representing the nodes 934 * @param ccs the constraints 935 * @param preventOverlaps boolean saying whether you want overlap prevention 936 * constraints to be automatically generated 937 * @param accept an integer indicating which types of infeasibilities you will accept. 938 * The default value of 0 means you accept no infeasibility. 939 * For other values, see the description of the "errorLevel" in the 940 * doctext for the solve function below. 941 * @param debugLevel see solve function below 942 * @note Rectangle positions are updated if and only if the error level is less 943 * than or equal to the accept level. 944 * @return a ProjectionResult indicating whether the projection was feasible or not. 945 * @sa solve 946 */ 947 ProjectionResult projectOntoCCs(vpsc::Dim dim, vpsc::Rectangles &rs, cola::CompoundConstraints ccs, 948 bool preventOverlaps, int accept=0, unsigned debugLevel=0); 949 950 /** 951 * @brief Constructs a solver and attempts to solve the passed constraints on the passed vars. 952 * @param debugLevel: controls how much information comes back when the projection fails. See below. 953 * @return a ProjectionResult, containing: 954 * errorLevel: 955 * 0: all constraints were satisfiable. 956 * 1: some constraints were unsatisfiable, but they were all nonoverlap constraints. 957 * 2: some constraints were unsatisfiable which were /not/ nonoverlap constraints. 958 * unsatinfo: 959 * The amount of information reported depends on the debugLevel: 960 * 0: nothing reported (empty string) 961 * 1: description of the unsatisfied constraints 962 * 2: the info from level 1, plus a description of all "related" constraints (those sharing a variable). 963 * This is useful for understanding the conflicts. 964 */ 965 ProjectionResult solve(vpsc::Variables &vs, vpsc::Constraints &cs, vpsc::Rectangles &rs, 966 unsigned debugLevel=0); 967 968 969 ConstrainedMajorizationLayout* simpleCMLFactory( 970 vpsc::Rectangles& rs, 971 std::vector<Edge> const & es, 972 RootCluster* clusterHierarchy, 973 const double idealLength, 974 bool useNeighbourStress = false 975 ); 976 977 /* 978 * find shortest path lengths from node s to all other nodes. 979 * @param s starting node 980 * @param n total number of nodes 981 * @param d n vector of path lengths 982 * @param es edge pairs 983 * @param eLengths edge weights 984 */ 985 void dijkstra(const unsigned s, const unsigned n, double* d, 986 const std::vector<cola::Edge>& es, 987 const std::valarray<double> & eLengths); 988 989 #if 0 990 void removeClusterOverlapFast(RootCluster& clusterHierarchy, vpsc::Rectangles& rs, Locks& locks); 991 #endif 992 993 void setupVarsAndConstraints(unsigned n, const CompoundConstraints& ccs, 994 const vpsc::Dim dim, vpsc::Rectangles& boundingBoxes, 995 RootCluster *clusterHierarchy, 996 vpsc::Variables& vs, vpsc::Constraints& cs, 997 std::valarray<double> &coords); 998 void setVariableDesiredPositions(vpsc::Variables& vs, vpsc::Constraints& cs, 999 const DesiredPositionsInDim& des, std::valarray<double>& coords); 1000 1001 } 1002 #endif // COLA_H 1003