diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libcola/cola.h')
| -rw-r--r-- | src/3rdparty/adaptagrams/libcola/cola.h | 1002 |
1 files changed, 1002 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libcola/cola.h b/src/3rdparty/adaptagrams/libcola/cola.h new file mode 100644 index 0000000..40043cd --- /dev/null +++ b/src/3rdparty/adaptagrams/libcola/cola.h @@ -0,0 +1,1002 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libcola - A library providing force-directed network layout using the + * stress-majorization method subject to separation constraints. + * + * Copyright (C) 2006-2015 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * See the file LICENSE.LGPL distributed with the library. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * Author(s): Tim Dwyer + * Michael Wybrow +*/ + +#ifndef COLA_H +#define COLA_H + +#include <utility> +#include <iterator> +#include <vector> +#include <valarray> +#include <algorithm> +#include <cmath> +#include <iostream> + +#include "libcola/gradient_projection.h" +#include "libcola/cluster.h" +#include "libcola/straightener.h" +#include "libcola/exceptions.h" +#include "libcola/pseudorandom.h" + +namespace vpsc { class Rectangle; } +namespace topology { + class ColaTopologyAddon; +} +namespace dialect { + class Graph; +} + + +/** + * @namespace cola + * @brief libcola: Force-directed network layout subject to + * separation constraints library. + * + * You should use COLA via an instance of the ConstrainedFDLayout class. +*/ +namespace cola { + +class NonOverlapConstraints; +class NonOverlapConstraintExemptions; + +//! @brief A vector of node Indexes. +typedef std::vector<unsigned> NodeIndexes; + +//! @brief A vector of NodeIndexes. +typedef std::vector<NodeIndexes> ListOfNodeIndexes; + +//! Edges are simply a pair of indices to entries in the Node vector +typedef std::pair<unsigned, unsigned> Edge; + +//! EdgeLengths is a vector of ideal lengths for edges corresponding to +//! edges in the edge list. +typedef std::vector<double> EdgeLengths; +#define StandardEdgeLengths EdgeLengths() + +/** + * @brief A Lock specifies a required position for a node. + */ +class Lock { +public: + Lock() {} + /** + * @brief Constructs a Lock object for a given node and position. + * + * @param[in] id The index of the node in the Rectangles vector. + * @param[in] X The node's fixed position in the x-dimension. + * @param[in] Y The node's fixed position in the y-dimension. + */ + Lock(unsigned id, double X, double Y) : id(id), x(X), y(Y) { + } + unsigned getID() const { + return id; + } + double pos(vpsc::Dim dim) const { + return dim==vpsc::HORIZONTAL?x:y; + } +private: + unsigned id; + double x; + double y; +}; +//! @brief A vector of Lock objects. +typedef std::vector<cola::Lock> Locks; + +/** + * @brief A Resize specifies a new required bounding box for a node. + */ +class Resize { +public: + Resize() {} + /** + * @brief Constructs a Resize object for a given node and it's new + * bounding box. + * + * @param[in] id The index of the node in the Rectangles vector. + * @param[in] x The minimum horizontal value for the node's new + * bounding box. + * @param[in] y The minimum vertical value for the node's new + * bounding box. + * @param[in] w The width value for the node's new bounding box. + * @param[in] h The height value for the node's new bounding box. + */ + Resize(unsigned id, double x, double y, double w, double h) + : id(id), target(x,x+w,y,y+h) {} + unsigned getID() const { + return id; + } + const vpsc::Rectangle* getTarget() const { + return ⌖ + } +private: + unsigned id; + vpsc::Rectangle target; +}; +//! @brief A vector of Resize objects. +typedef std::vector<cola::Resize> Resizes; + +/* + * Setting a desired position for a node adds a term to the goal function + * drawing the node towards that desired position + */ +struct DesiredPosition { + unsigned id; + double x; + double y; + double weight; +}; +typedef std::vector<cola::DesiredPosition> DesiredPositions; + +/* + * desired positions which should override those computed by applying forces + * are passed in for a set of nodes. The first entry is the Node->id, the + * second is the desired position. + */ +typedef std::pair<unsigned,double> DesiredPositionInDim; +typedef std::vector<DesiredPositionInDim> DesiredPositionsInDim; + +/** + * @brief A default functor that is called before each iteration in the + * main loop of the ConstrainedFDLayout::run() method. + * + * Override the operator() for things like locking the position of nodes + * for the duration of the iteration. + * + * If the operator() returns false the subsequent iterations are + * abandoned, i.e., layout ends immediately. You can make it return true + * when a user-interrupt is detected, for instance. + */ +class PreIteration { +public: + /** + * @brief Constructs a PreIteration object that handles locking and + * resizing of nodes. + * + * @param[in] locks A list of nodes (by index) and positions at which + * they should be locked. + * @param[in] resizes A list of nodes (by index) and required dimensions + * for their bounding rects to be resized to. + */ + PreIteration( + Locks& locks=__locksNotUsed, + Resizes& resizes=__resizesNotUsed) + : locks(locks) + , resizes(resizes) + , changed(true) {} + PreIteration(Resizes& resizes) + : locks(__locksNotUsed) + , resizes(resizes) + , changed(true) {} + +// To prevent C++ objects from being destroyed in garbage collected languages +// when the libraries are called from SWIG, we hide the declarations of the +// destructors and prevent generation of default destructors. +#ifndef SWIG + virtual ~PreIteration() {} +#endif + virtual bool operator()() { return true; } + Locks& locks; + Resizes& resizes; + bool changed; +private: + static Locks __locksNotUsed; + static Resizes __resizesNotUsed; +}; + +/** + * @brief A default functor that is called after each iteration of the layout + * algorithm. + * + * You can either instantiate ConstrainedFDLayout with an instance of this + * class setting the tolerance and maxiterations as desired, or create a + * derived class implementing the operator() to do your own convergence test, + * or create your own operator() that calls the TestConvergence::operator() in + * order to do any other post processing you might need, e.g., to animate + * changes. + */ +class TestConvergence { +public: + double old_stress; + TestConvergence(const double tol = 1e-4, const unsigned maxiterations = 100) + : tolerance(tol), + maxiterations(maxiterations) + { reset(); } + virtual ~TestConvergence() {} + +public: + virtual bool operator()(const double new_stress, std::valarray<double> & X, std::valarray<double> & Y) + { + COLA_UNUSED(X); + COLA_UNUSED(Y); + + iterations++; + //std::cout<<"iteration="<<iterations<<", old_stress="<<old_stress<<", new_stress="<<new_stress<<std::endl; + if (old_stress == DBL_MAX) { + old_stress = new_stress; + return iterations >= maxiterations; + } + // converged if relative decrease in stress falls below threshold + // or if stress increases (shouldn't happen for straight majorization) + bool converged = + (old_stress - new_stress) / (new_stress + 1e-10) < tolerance + || iterations > maxiterations; + old_stress = new_stress; + return converged; + } + void reset() { + old_stress = DBL_MAX; + iterations = 0; + } + const double tolerance; + const unsigned maxiterations; + unsigned iterations; +}; + +/** + * @brief Implements the Constrained Majorization graph layout algorithm + * (deprecated). + * + * The optimisation method used is "stress majorization", where a sequence of + * quadratic functions which strictly bound the stress from above, is solved + * to monotonically reduce the stress (by iteratively changing the + * configuration of nodes). + * + * Once the problem has been set up, call run() or runOnce() to run the + * layout algorithm. + * + * @note We recommend the use of ConstrainedFDLayout instead of this class. + * ConstrainedFDLayout tends to produce better results and has more + * features. We are no longer working on ConstrainedMajorizationLayout. + */ +class ConstrainedMajorizationLayout { +public: + /** + * @brief Constructs a constrained majorization layout instance. + * + * @param[in] rs Bounding boxes of nodes at their initial positions. + * @param[in] es Simple pair edges, giving indices of the start and end + * nodes in rs. + * @param[in] clusterHierarchy A pointer to a RootCluster object defining + * the cluster hierarchy (optional). + * @param[in] idealLength Aa scalar modifier of ideal edge lengths in + * eLengths. + * @param[in] eLengths Individual ideal lengths for edges. + * The actual ideal length used for the ith edge is + * idealLength*eLengths[i], or if eLengths is empty + * then just idealLength is used (i.e., eLengths[i] + * is assumed to be 1). + * @param[in] done A test of convergence operation called at the end of + * each iteration (optional). + * @param[in] preIteration An operation called before each iteration + * (optional). + */ + ConstrainedMajorizationLayout( + vpsc::Rectangles& rs, + std::vector<Edge> const & es, + RootCluster* clusterHierarchy, + const double idealLength, + EdgeLengths eLengths = StandardEdgeLengths, + TestConvergence *doneTest = nullptr, + PreIteration* preIteration=nullptr, + bool useNeighbourStress = false); + /** + * @brief Specify a set of compound constraints to apply to the layout. + * + * @param[in] ccs The compound constraints. + */ + void setConstraints(cola::CompoundConstraints* ccs) { + constrainedLayout = true; + this->ccs=ccs; + } + + void setConstraintsVector(cola::CompoundConstraints& ccs) { + constrainedLayout = true; + cola::CompoundConstraints *ccsp = new cola::CompoundConstraints; + for (size_t i = 0; i < ccs.size(); ++i) { + ccsp->push_back(ccs.at(i)); + } + this->ccs=ccsp; + } + + /** + * @brief Register to receive information about unsatisfiable constraints. + * + * In the case of unsatisifiable constraints, the solver will drop + * unsatisfiable constraints of lowest priority. Information about these + * will be written to these lists after each iteration of constrained + * layout. + * + * param[out] unsatisfiableX A pointer to an UnsatisfiableConstraintInfos + * object that will be used to record + * unsatisfiable constraints in the x-dimension. + * param[out] unsatisfiableY A pointer to an UnsatisfiableConstraintInfos + * object that will be used to record + * unsatisfiable constraints in the y-dimension. + */ + void setUnsatisfiableConstraintInfo( + UnsatisfiableConstraintInfos *unsatisfiableX, + UnsatisfiableConstraintInfos *unsatisfiableY) { + this->unsatisfiableX = unsatisfiableX; + this->unsatisfiableY = unsatisfiableY; + } + /** + * Sticky nodes causes nodes to spring back to (startX,startY) when + * unconstrained. + */ + void setStickyNodes(const double stickyWeight, + std::valarray<double> const & startX, + std::valarray<double> const & startY); + + /** + * Scaling speeds up the solver by conditioning the quadratic terms matrix. + */ + void setScaling(bool scaling) { + this->scaling=scaling; + } + /** + * Says that the Mosek optimisation library should be used to solve the + * quadratic programs rather than the libvpsc solver. + */ + void setExternalSolver(bool externalSolver) { + this->externalSolver=externalSolver; + } + /** + * At each iteration of layout, generate constraints to avoid overlaps. + * If bool horizontal is true, all overlaps will be resolved horizontally, + * otherwise some overlaps will be left to be resolved vertically where + * doing so leads to less displacement + */ + void setAvoidOverlaps(bool horizontal = false) { + constrainedLayout = true; + this->avoidOverlaps = horizontal ? Horizontal : Both; + } + /** + * Add constraints to prevent clusters overlapping. + */ + void setNonOverlappingClusters() { + constrainedLayout = true; + nonOverlappingClusters = true; + } + /** + * For the specified edges (with routings), generate dummy vars and + * constraints to try and straighten them. bendWeight controls how hard we + * try to straighten existing bends potBendWeight controls how much we try + * to keep straight edges straight + */ + void setStraightenEdges(std::vector<straightener::Edge*>* straightenEdges, + double bendWeight = 0.01, double potBendWeight = 0.1, + bool xSkipping = true) { + for(std::vector<straightener::Edge*>::const_iterator e=straightenEdges->begin(); + e!=straightenEdges->end();e++) { + (*e)->rerouteAround(boundingBoxes); + } + constrainedLayout = true; + this->xSkipping = xSkipping; + this->straightenEdges = straightenEdges; + this->bendWeight = bendWeight; + this->potBendWeight = potBendWeight; + } + /** + * Update position of bounding boxes. + */ + void moveBoundingBoxes() { + for(unsigned i=0;i<n;i++) { + boundingBoxes[i]->moveCentre(X[i],Y[i]); + } + } + + ~ConstrainedMajorizationLayout() { + if (using_default_done) + { + delete done; + } + + if(constrainedLayout) { + delete gpX; + delete gpY; + } + } + /** + * @brief Implements the main layout loop, taking descent steps until + * stress is no-longer significantly reduced. + * + * @param[in] x If true, layout will be performed in x-dimension + * (default: true). + * @param[in] y If true, layout will be performed in y-dimension + * (default: true). + */ + void run(bool x=true, bool y=true); + /** + * @brief Same as run(), but only applies one iteration. + * + * This may be useful here it's too hard to implement a call-back + * (e.g., in java apps). + * + * @param[in] x If true, layout will be performed in x-dimension + * (default: true). + * @param[in] y If true, layout will be performed in y-dimension + * (default: true). + */ + void runOnce(bool x=true, bool y=true); + void straighten(std::vector<straightener::Edge*>&, vpsc::Dim); + void setConstrainedLayout(bool c) { + constrainedLayout=c; + } + double computeStress(); +private: + double euclidean_distance(unsigned i, unsigned j) { + return sqrt( + (X[i] - X[j]) * (X[i] - X[j]) + + (Y[i] - Y[j]) * (Y[i] - Y[j])); + } + double compute_stress(std::valarray<double> const & Dij); + void majorize(std::valarray<double> const & Dij,GradientProjection* gp, std::valarray<double>& coords, std::valarray<double> const & startCoords); + void newton(std::valarray<double> const & Dij,GradientProjection* gp, std::valarray<double>& coords, std::valarray<double> const & startCoords); + unsigned n; //< number of nodes + //std::valarray<double> degrees; + std::valarray<double> lap2; //< graph laplacian + std::valarray<double> Q; //< quadratic terms matrix used in computations + std::valarray<double> Dij; //< all pairs shortest path distances + double tol; //< convergence tolerance + TestConvergence *done; //< functor used to determine if layout is finished + bool using_default_done; // Whether we allocated a default TestConvergence object. + PreIteration* preIteration; //< client can use this to create locks on nodes + vpsc::Rectangles boundingBoxes; //< node bounding boxes + /* + * stickyNodes controls whether nodes are attracted to their starting + * positions (at time of ConstrainedMajorizationLayout instantiation) + * stored in startX, startY + */ + std::valarray<double> X, Y; + bool stickyNodes; + double stickyWeight; + std::valarray<double> startX; + std::valarray<double> startY; + double edge_length; + bool constrainedLayout; + bool nonOverlappingClusters; + /* + * A cluster is a set of nodes that are somehow semantically grouped + * and should therefore be kept together a bit more tightly than, and + * preferably without overlapping, the rest of the graph. + * + * We achieve this by augmenting the L matrix with stronger attractive + * forces between all members of a cluster (other than the root) + * and by maintaining a (preferably convex) hull around those + * constituents which, using constraints and dummy variables, is + * prevented from overlapping other parts of the graph. + * + * Clusters are defined over the graph in a hierarchy starting with + * a single root cluster. + * + * Need to: + * - augment Lap matrix with intra cluster forces + * - compute convex hull of each cluster + * - from convex hull generate "StraightenEdges" + */ + RootCluster *clusterHierarchy; + GradientProjection *gpX, *gpY; + cola::CompoundConstraints *ccs; + UnsatisfiableConstraintInfos *unsatisfiableX, *unsatisfiableY; + NonOverlapConstraintsMode avoidOverlaps; + std::vector<straightener::Edge*>* straightenEdges; + + double bendWeight, potBendWeight; + /* + * determines whether we should leave some overlaps to be resolved + * vertically when generating straightening constraints in the x-dim + */ + bool xSkipping; + /* + * when using the gradient projection optimisation method, the following + * controls whether the problem should be preconditioned by affine scaling + */ + bool scaling; + /* + * if the Mosek quadratic programming environment is available it may be + * used to solve each iteration of stress majorization... slow but useful + * for testing + */ + bool externalSolver; + bool majorization; +}; + +vpsc::Rectangle bounds(vpsc::Rectangles& rs); + +class ConstrainedFDLayout; + +/** + * @brief Interface for writing COLA addons to handle topology preserving + * layout. + */ +class TopologyAddonInterface +{ + public: + TopologyAddonInterface() + { + } + + virtual ~TopologyAddonInterface() + { + } + + virtual TopologyAddonInterface *clone(void) const + { + return new TopologyAddonInterface(*this); + } + + virtual void freeAssociatedObjects(void) + { + } + + virtual void handleResizes(const Resizes& resizeList, unsigned n, + std::valarray<double>& X, std::valarray<double>& Y, + cola::CompoundConstraints& ccs, + vpsc::Rectangles& boundingBoxes, + cola::RootCluster* clusterHierarchy) + { + COLA_UNUSED(resizeList); + COLA_UNUSED(n); + COLA_UNUSED(X); + COLA_UNUSED(Y); + COLA_UNUSED(ccs); + COLA_UNUSED(boundingBoxes); + COLA_UNUSED(clusterHierarchy); + } + virtual void computePathLengths(unsigned short** G) + { + COLA_UNUSED(G); + } + virtual double computeStress(void) const + { + return 0; + } + virtual bool useTopologySolver(void) const + { + return false; + } + virtual void makeFeasible(bool generateNonOverlapConstraints, + vpsc::Rectangles& boundingBoxes, + cola::RootCluster* clusterHierarchy) + { + COLA_UNUSED(generateNonOverlapConstraints); + COLA_UNUSED(boundingBoxes); + COLA_UNUSED(clusterHierarchy); + } + virtual void moveTo(const vpsc::Dim dim, vpsc::Variables& vs, + vpsc::Constraints& cs, std::valarray<double> &coords, + cola::RootCluster* clusterHierarchy) + { + COLA_UNUSED(dim); + COLA_UNUSED(vs); + COLA_UNUSED(cs); + COLA_UNUSED(coords); + COLA_UNUSED(clusterHierarchy); + } + virtual double 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) + { + COLA_UNUSED(layout); + COLA_UNUSED(dim); + COLA_UNUSED(g); + COLA_UNUSED(vs); + COLA_UNUSED(cs); + COLA_UNUSED(coords); + COLA_UNUSED(des); + COLA_UNUSED(oldStress); + return 0; + } +}; + + +/** + * @brief Implements a constrained force-directed layout algorithm. + * + * This method is based on a non-linear gradient projection technique. + * Conceptually it's similar to a force directed method like + * Fruchterman-Reingold---but using a more principled goal function and + * optimisation techniques. + */ +class ConstrainedFDLayout { +public: + /** + * @brief Constructs a constrained force-directed layout instance. + * + * If an empty edges (es) vector is passed to the constructor, then + * constraint satisfaction will be performed, but no force-directed + * layout. In this case, idealLength and eLengths have no effect. + * + * Conversely, if no constraints or clusters are specified and no overlap + * prevention is enabled, but edge info is given, then pure force-directed + * layout will be performed. + * + * @param[in] rs Bounding boxes of nodes at their initial positions. + * @param[in] es Simple pair edges, giving indices of the start and end + * nodes in rs. + * @param[in] idealLength A scalar modifier of ideal edge lengths in + * eLengths or of 1 if no ideal lengths are + * specified. + * @param[in] eLengths Individual ideal lengths for edges. + * The actual ideal length used for the ith edge is + * idealLength*eLengths[i], or if eLengths is nullptr a + * then just idealLength is used (i.e., eLengths[i] + * is assumed to be 1). + * @param[in] done A test of convergence operation called at the end of + * each iteration (optional). If not given, uses a + * default TestConvergence object. + * @param[in] preIteration An operation called before each iteration + * (optional). + */ + ConstrainedFDLayout( + const vpsc::Rectangles& rs, + const std::vector<cola::Edge>& es, + const double idealLength, + const EdgeLengths& eLengths = StandardEdgeLengths, + TestConvergence* doneTest = nullptr, + PreIteration* preIteration = nullptr); + ~ConstrainedFDLayout(); + + /** + * @brief Implements the main layout loop, taking descent steps until + * stress is no-longer significantly reduced. + * + * @param[in] x If true, layout will be performed in x-dimension + * (default: true). + * @param[in] y If true, layout will be performed in y-dimension + * (default: true). + */ + void run(bool x=true, bool y=true); + + /** + * @brief Same as run(), but only applies one iteration. + * + * This may be useful here it's too hard to implement a call-back + * (e.g., in java apps). + * + * @param[in] x If true, layout will be performed in x-dimension + * (default: true). + * @param[in] y If true, layout will be performed in y-dimension + * (default: true). + */ + void runOnce(bool x=true, bool y=true); + + /** + * @brief Specify a set of compound constraints to apply to the layout. + * + * @param[in] ccs The compound constraints. + */ + void setConstraints(const cola::CompoundConstraints& ccs); + + /** + * @brief Specifies whether non-overlap constraints should be + * automatically generated between all nodes, as well as any + * exemptions to this. + * + * The optional second parameter indicates groups of nodes that should be + * exempt from having non-overlap constraints generated between each other. + * For example, you might want to do this for nodes representing ports, or + * the child nodes in a particular cluster. + * + * @param[in] avoidOverlaps New boolean value for this option. + * @param[in] listOfNodeGroups A list of groups of node indexes which will + * not have non-overlap constraints generated + * between each other. + */ + void setAvoidNodeOverlaps(bool avoidOverlaps, + ListOfNodeIndexes listOfNodeGroups = + ListOfNodeIndexes()); + + /** + * @brief Set an addon for doing topology preserving layout. + * + * It is expected that you would use the topology::ColaTopologyAddon() + * from libtopology rather than write your own. This is done so that + * libcola does not have to depend on libtopology. + * + * @param[in] topology Instance of a class implementing the + * TopologyAddonInterface. + * @sa topology::ColaTopologyAddon + */ + void setTopology(TopologyAddonInterface *topology); + TopologyAddonInterface *getTopology(void); + + void setDesiredPositions(DesiredPositions *desiredPositions); + + /** + * @brief Specifies an optional hierarchy for clustering nodes. + * + * @param[in] hierarchy A pointer to a RootCluster object defining the + * the cluster hierarchy (optional). + */ + void setClusterHierarchy(RootCluster *hierarchy) + { + clusterHierarchy = hierarchy; + } + /** + * @brief Register to receive information about unsatisfiable constraints. + * + * In the case of unsatisifiable constraints, the solver will drop + * unsatisfiable constraints of lowest priority. Information about these + * will be written to these lists after each iteration of constrained + * layout. + * + * param[out] unsatisfiableX A pointer to a UnsatisfiableConstraintInfos + * object that will be used to record + * unsatisfiable constraints in the x-dimension. + * param[out] unsatisfiableY A pointer to a UnsatisfiableConstraintInfos + * object that will be used to record + * unsatisfiable constraints in the y-dimension. + */ + void setUnsatisfiableConstraintInfo( + UnsatisfiableConstraintInfos *unsatisfiableX, + UnsatisfiableConstraintInfos *unsatisfiableY) + { + unsatisfiable.resize(2); + unsatisfiable[0]=unsatisfiableX; + unsatisfiable[1]=unsatisfiableY; + } + /** + * @brief Finds a feasible starting position for nodes that satisfies the + * given constraints. + * + * Starts with an initial position (x, y) for the nodes. This position + * is then iteratively updated with a greedy heuristic that tries adding + * additional constraints based on compound constraint priority to the + * satisfiable set, so as to satisfy as many of the placement constraints + * as possible. This includes automatically generated constraints for + * non-overlap and cluster containment. + * + * @param[in] xBorder Optional border width to add to left and right + * sides of rectangles. Defaults to 1. + * @param[in] yBorder Optional border width to add to top and bottom + * sides of rectangles. Defaults to 1. + * + * @note This method doesn't do force-directed layout. All forces are + * ignored and it merely satisfies the constraints with minimal + * movement to nodes. + */ + void makeFeasible(double xBorder=1, double yBorder=1); + + /** + * @brief A convenience method that can be called from Java to free + * the memory of nodes (Rectangles), CompoundConstraints, etc. + * + * This assumes that the ConstrainedFDLayout instance takes ownership + * of all the objects passed to it. + * + * This is useful because in SWIG we have problems with Java wrapper + * classes going out of scope and causing objects like Rectanges to + * sometimes be freed when the layout instance still needs them. For + * this reason we prevent the Java wrappers from deleting the internal + * C++ instances, and let them be cleaned up later via this method. + */ + void freeAssociatedObjects(void); + + //! @brief Generates an SVG file containing debug output and code that + //! can be used to regenerate the instance. + //! + //! This method can be called before or after run() or makeFeasible() + //! have been called. + //! + //! @param[in] filename A string indicating the filename (without + //! extension) for the output file. Defaults to + //! "libcola-debug.svg" if no filename is given. + //! + void outputInstanceToSVG(std::string filename = std::string()); + + /** + * @brief Specifies whether neighbour stress should be used. + * + * Under neighbour stress, only the terms representing neighbouring + * nodes contribute to the stress function. This can help to distribute + * nodes more evenly, eliminating long-range forces. + * + * Default value is false. + * + * @param[in] useNeighbourStress New boolean value for this option. + */ + void setUseNeighbourStress(bool useNeighbourStress); + + /** + * @brief Retrieve a copy of the "D matrix" computed by the computePathLengths + * method, linearised as a vector. + * + * This is especially useful for projects in SWIG target languages that want to + * do their own computations with stress. + * + * D is the required euclidean distances between pairs of nodes + * based on the shortest paths between them (using + * m_idealEdgeLength*eLengths[edge] as the edge length, if eLengths array + * is provided otherwise just m_idealEdgeLength). + * + * @return vector representing the D matrix. + */ + std::vector<double> readLinearD(void); + + /** + * @brief Retrieve a copy of the "G matrix" computed by the computePathLengths + * method, linearised as a vector. + * + * * This is especially useful for projects in SWIG target languages that want to + * do their own computations with stress. + * + * G is a matrix of unsigned ints such that G[u][v]= + * 0 if there are no forces required between u and v + * (for example, if u and v are in unconnected components) + * 1 if attractive forces are required between u and v + * (i.e. if u and v are immediately connected by an edge and there is + * no topology route between u and v (for which an attractive force + * is computed elsewhere)) + * 2 if no attractive force is required between u and v but there is + * a connected path between them. + * + * @return vector representing the G matrix. + */ + std::vector<unsigned> readLinearG(void); + + double computeStress() const; + +private: + unsigned n; // number of nodes + std::valarray<double> X, Y; + vpsc::Rectangles boundingBoxes; + double applyForcesAndConstraints(const vpsc::Dim dim,const double oldStress); + double computeStepSize(const SparseMatrix& H, const std::valarray<double>& g, + const std::valarray<double>& d) const; + void computeDescentVectorOnBothAxes(const bool xaxis, const bool yaxis, + double stress, std::valarray<double>& x0, std::valarray<double>& x1); + void moveTo(const vpsc::Dim dim, std::valarray<double>& target); + double applyDescentVector( + const std::valarray<double>& d, + const std::valarray<double>& oldCoords, + std::valarray<double> &coords, + const double oldStress, + double stepsize + /*,topology::TopologyConstraints *s=nullptr*/); + void computePathLengths( + const std::vector<Edge>& es, std::valarray<double> eLengths); + void generateNonOverlapAndClusterCompoundConstraints( + vpsc::Variables (&vs)[2]); + void handleResizes(const Resizes&); + void setPosition(std::valarray<double>& pos); + void moveBoundingBoxes(); + bool noForces(double, double, unsigned) const; + void computeForces(const vpsc::Dim dim, SparseMap &H, + std::valarray<double> &g); + void recGenerateClusterVariablesAndConstraints( + vpsc::Variables (&vars)[2], unsigned int& priority, + cola::NonOverlapConstraints *noc, Cluster *cluster, + cola::CompoundConstraints& idleConstraints); + std::vector<double> offsetDir(double minD); + + void computeNeighbours(std::vector<Edge> es); + std::vector<std::vector<unsigned> > neighbours; + std::vector<std::vector<double> > neighbourLengths; + TestConvergence *done; + bool using_default_done; // Whether we allocated a default TestConvergence object. + PreIteration* preIteration; + cola::CompoundConstraints ccs; + double** D; + unsigned short** G; + double minD; + PseudoRandom random; + + TopologyAddonInterface *topologyAddon; + std::vector<UnsatisfiableConstraintInfos*> unsatisfiable; + bool rungekutta; + DesiredPositions *desiredPositions; + cola::CompoundConstraints extraConstraints; + + RootCluster *clusterHierarchy; + double rectClusterBuffer; + double m_idealEdgeLength; + bool m_generateNonOverlapConstraints; + bool m_useNeighbourStress; + const std::valarray<double> m_edge_lengths; + + NonOverlapConstraintExemptions *m_nonoverlap_exemptions; + + friend class topology::ColaTopologyAddon; + friend class dialect::Graph; +}; + +struct ProjectionResult { + int errorLevel; + std::string unsatinfo; +}; + +/** + * @brief Attempt to do a projection onto a vector of cola CompoundConstraints. + * @param dim the dimension in which to perform the projection + * @param rs the rectangles representing the nodes + * @param ccs the constraints + * @param preventOverlaps boolean saying whether you want overlap prevention + * constraints to be automatically generated + * @param accept an integer indicating which types of infeasibilities you will accept. + * The default value of 0 means you accept no infeasibility. + * For other values, see the description of the "errorLevel" in the + * doctext for the solve function below. + * @param debugLevel see solve function below + * @note Rectangle positions are updated if and only if the error level is less + * than or equal to the accept level. + * @return a ProjectionResult indicating whether the projection was feasible or not. + * @sa solve + */ +ProjectionResult projectOntoCCs(vpsc::Dim dim, vpsc::Rectangles &rs, cola::CompoundConstraints ccs, + bool preventOverlaps, int accept=0, unsigned debugLevel=0); + +/** + * @brief Constructs a solver and attempts to solve the passed constraints on the passed vars. + * @param debugLevel: controls how much information comes back when the projection fails. See below. + * @return a ProjectionResult, containing: + * errorLevel: + * 0: all constraints were satisfiable. + * 1: some constraints were unsatisfiable, but they were all nonoverlap constraints. + * 2: some constraints were unsatisfiable which were /not/ nonoverlap constraints. + * unsatinfo: + * The amount of information reported depends on the debugLevel: + * 0: nothing reported (empty string) + * 1: description of the unsatisfied constraints + * 2: the info from level 1, plus a description of all "related" constraints (those sharing a variable). + * This is useful for understanding the conflicts. + */ +ProjectionResult solve(vpsc::Variables &vs, vpsc::Constraints &cs, vpsc::Rectangles &rs, + unsigned debugLevel=0); + + +ConstrainedMajorizationLayout* simpleCMLFactory( + vpsc::Rectangles& rs, + std::vector<Edge> const & es, + RootCluster* clusterHierarchy, + const double idealLength, + bool useNeighbourStress = false + ); + +/* + * find shortest path lengths from node s to all other nodes. + * @param s starting node + * @param n total number of nodes + * @param d n vector of path lengths + * @param es edge pairs + * @param eLengths edge weights + */ +void dijkstra(const unsigned s, const unsigned n, double* d, + const std::vector<cola::Edge>& es, + const std::valarray<double> & eLengths); + +#if 0 +void removeClusterOverlapFast(RootCluster& clusterHierarchy, vpsc::Rectangles& rs, Locks& locks); +#endif + +void setupVarsAndConstraints(unsigned n, const CompoundConstraints& ccs, + const vpsc::Dim dim, vpsc::Rectangles& boundingBoxes, + RootCluster *clusterHierarchy, + vpsc::Variables& vs, vpsc::Constraints& cs, + std::valarray<double> &coords); +void setVariableDesiredPositions(vpsc::Variables& vs, vpsc::Constraints& cs, + const DesiredPositionsInDim& des, std::valarray<double>& coords); + +} +#endif // COLA_H |