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/removeoverlap/blocks.cpp | 196 ------------------------------------------- 1 file changed, 196 deletions(-) delete mode 100644 src/removeoverlap/blocks.cpp (limited to 'src/removeoverlap/blocks.cpp') diff --git a/src/removeoverlap/blocks.cpp b/src/removeoverlap/blocks.cpp deleted file mode 100644 index 62b7e99f5..000000000 --- a/src/removeoverlap/blocks.cpp +++ /dev/null @@ -1,196 +0,0 @@ -/** - * \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 *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