From 12b21e1d27f43deaa748419919b40b80cedd0ddd Mon Sep 17 00:00:00 2001 From: Tim Dwyer Date: Wed, 12 Jul 2006 00:55:58 +0000 Subject: Previously graph layout was done using the Kamada-Kawai layout algorithm implemented in Boost. I am replacing this with a custom implementation of a constrained stress-majorization algorithm. The stress-majorization algorithm is more robust and has better convergence characteristics than Kamada-Kawai, and also simple constraints can be placed on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints). Another big advantage is that we no longer need Boost. I've tested the basic functionality, but I have yet to properly handle disconnected graphs or to properly scale the resulting layout. This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola. (bzr r1394) --- src/libvpsc/blocks.cpp | 196 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 196 insertions(+) create mode 100644 src/libvpsc/blocks.cpp (limited to 'src/libvpsc/blocks.cpp') diff --git a/src/libvpsc/blocks.cpp b/src/libvpsc/blocks.cpp new file mode 100644 index 000000000..48f0237bf --- /dev/null +++ b/src/libvpsc/blocks.cpp @@ -0,0 +1,196 @@ +/** + * \brief A block structure defined over the variables + * + * A block structure defined over the variables such that each block contains + * 1 or more variables, with the invariant that all constraints inside a block + * are satisfied by keeping the variables fixed relative to one another + * + * Authors: + * Tim Dwyer + * + * Copyright (C) 2005 Authors + * + * Released under GNU LGPL. Read the file 'COPYING' for more information. + */ + +#include "blocks.h" +#include "block.h" +#include "constraint.h" +#ifdef RECTANGLE_OVERLAP_LOGGING +#include +using std::ios; +using std::ofstream; +using std::endl; +#endif +using std::set; +using std::vector; +using std::iterator; +using std::list; +using std::copy; + +long blockTimeCtr; + +Blocks::Blocks(const int n, Variable* const vs[]) : vs(vs),nvs(n) { + blockTimeCtr=0; + for(int i=0;i::iterator i=begin();i!=end();++i) { + delete *i; + } + clear(); +} + +/** + * returns a list of variables with total ordering determined by the constraint + * DAG + */ +list *Blocks::totalOrder() { + list *order = new list; + for(int i=0;ivisited=false; + } + for(int i=0;iin.size()==0) { + dfsVisit(vs[i],order); + } + } + return order; +} +// Recursive depth first search giving total order by pushing nodes in the DAG +// onto the front of the list when we finish searching them +void Blocks::dfsVisit(Variable *v, list *order) { + v->visited=true; + vector::iterator it=v->out.begin(); + for(;it!=v->out.end();++it) { + Constraint *c=*it; + if(!c->right->visited) { + dfsVisit(c->right, order); + } + } +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" order="<<*v<push_front(v); +} +/** + * Processes incoming constraints, most violated to least, merging with the + * neighbouring (left) block until no more violated constraints are found + */ +void Blocks::mergeLeft(Block *r) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"mergeLeft called on "<<*r<timeStamp=++blockTimeCtr; + r->setUpInConstraints(); + Constraint *c=r->findMinInConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"mergeLeft on constraint: "<<*c<deleteMinInConstraint(); + Block *l = c->left->block; + if (l->in==NULL) l->setUpInConstraints(); + double dist = c->right->offset - c->left->offset - c->gap; + if (r->vars->size() < l->vars->size()) { + dist=-dist; + std::swap(l, r); + } + blockTimeCtr++; + r->merge(l, c, dist); + r->mergeIn(l); + r->timeStamp=blockTimeCtr; + removeBlock(l); + c=r->findMinInConstraint(); + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"merged "<<*r<setUpOutConstraints(); + Constraint *c = l->findMinOutConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"mergeRight on constraint: "<<*c<deleteMinOutConstraint(); + Block *r = c->right->block; + r->setUpOutConstraints(); + double dist = c->left->offset + c->gap - c->right->offset; + if (l->vars->size() > r->vars->size()) { + dist=-dist; + std::swap(l, r); + } + l->merge(r, c, dist); + l->mergeOut(r); + removeBlock(r); + c=l->findMinOutConstraint(); + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"merged "<<*l<deleted=true; + //erase(doomed); +} +void Blocks::cleanup() { + vector bcopy(begin(),end()); + for(vector::iterator i=bcopy.begin();i!=bcopy.end();++i) { + Block *b=*i; + if(b->deleted) { + erase(b); + delete b; + } + } +} +/** + * Splits block b across constraint c into two new blocks, l and r (c's left + * and right sides respectively) + */ +void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) { + b->split(l,r,c); +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split left: "<<*l<posn = b->posn; + r->wposn = r->posn * r->weight; + mergeLeft(l); + // r may have been merged! + r = c->right->block; + r->wposn = r->desiredWeightedPosition(); + r->posn = r->wposn / r->weight; + mergeRight(r); + removeBlock(b); + + insert(l); + insert(r); +} +/** + * returns the cost total squared distance of variables from their desired + * positions + */ +double Blocks::cost() { + double c = 0; + for(set::iterator i=begin();i!=end();++i) { + c += (*i)->cost(); + } + return c; +} + -- cgit v1.2.3