From 4f818baab8a232b03f5b4802094ce598ff2e56fb Mon Sep 17 00:00:00 2001 From: tgdwyer Date: Fri, 14 Jul 2006 04:09:40 +0000 Subject: [PATCH] - Connectors with end-markers now constrained to point downwards in graph layout - vpsc namespace added to libvpsc --- src/connector-context.cpp | 2 +- src/graphlayout/graphlayout.cpp | 81 ++++++++++++++++-------- src/libcola/cola.cpp | 2 +- src/libcola/cola.h | 6 +- src/libcola/gradient_projection.cpp | 31 ++++----- src/libcola/gradient_projection.h | 48 +++++++------- src/libcola/straightener.h | 2 +- src/libvpsc/block.cpp | 18 ++++++ src/libvpsc/block.h | 6 +- src/libvpsc/blocks.cpp | 3 + src/libvpsc/blocks.h | 2 + src/libvpsc/constraint.cpp | 2 + src/libvpsc/constraint.h | 2 + src/libvpsc/csolve_VPSC.cpp | 19 +++--- src/libvpsc/csolve_VPSC.h | 28 ++++---- src/libvpsc/generate-constraints.cpp | 3 + src/libvpsc/generate-constraints.h | 2 + src/libvpsc/remove_rectangle_overlap.cpp | 7 +- src/libvpsc/remove_rectangle_overlap.h | 4 +- src/libvpsc/solve_VPSC.cpp | 52 +++++++-------- src/libvpsc/solve_VPSC.h | 15 +++-- src/libvpsc/variable.cpp | 3 +- src/libvpsc/variable.h | 6 +- src/removeoverlap/removeoverlap.cpp | 2 + 24 files changed, 213 insertions(+), 133 deletions(-) diff --git a/src/connector-context.cpp b/src/connector-context.cpp index e68c8f521..bb0c8e740 100644 --- a/src/connector-context.cpp +++ b/src/connector-context.cpp @@ -9,7 +9,7 @@ * Released under GNU GPL, read the file 'COPYING' for more information * * TODO: - * o Have shapes avoid coonvex hulls of objects, rather than their + * o Have shapes avoid convex hulls of objects, rather than their * bounding box. Possibly implement the unfinished ConvexHull * class in libnr. * (HOWEVER, using the convex hull C of a shape S does the wrong thing if a diff --git a/src/graphlayout/graphlayout.cpp b/src/graphlayout/graphlayout.cpp index ac2d5429f..432f3c942 100644 --- a/src/graphlayout/graphlayout.cpp +++ b/src/graphlayout/graphlayout.cpp @@ -22,6 +22,7 @@ #include "sp-item.h" #include "sp-item-transform.h" #include "sp-conn-end-pair.h" +#include "style.h" #include "conn-avoid-ref.h" #include "libavoid/connector.h" #include "libavoid/geomtypes.h" @@ -31,6 +32,7 @@ using namespace std; using namespace cola; +using namespace vpsc; /** * Returns true if item is a connector @@ -90,9 +92,28 @@ void graphlayout(GSList const *const items) { minX=min(ll[0],minX); minY=min(ll[1],minY); maxX=max(ur[0],maxX); maxY=max(ur[1],maxY); nodelookup[u->id]=rs.size(); + cout << "Node " << rs.size() << endl; rs.push_back(new Rectangle(ll[0],ur[0],ll[1],ur[1])); } + SimpleConstraints scy; + double ideal_connector_length = prefs_get_double_attribute("tools.connector","length",100); + double directed_edge_height_modifier = 1.0; + gchar const *directed_str = NULL, *overlaps_str = NULL; + directed_str = prefs_get_string_attribute("tools.connector", + "directedlayout"); + overlaps_str = prefs_get_string_attribute("tools.connector", + "avoidoverlaplayout"); + bool avoid_overlaps = false; + bool directed = false; + if (directed_str && !strcmp(directed_str, "true")) { + cout << "Directed layout requested.\n"; + directed = true; + } + if (overlaps_str && !strcmp(overlaps_str, "true")) { + cout << "Avoid overlaps requested.\n"; + avoid_overlaps = true; + } for (list::iterator i(selected.begin()); i != selected.end(); @@ -100,17 +121,38 @@ void graphlayout(GSList const *const items) { { SPItem *iu=*i; unsigned u=nodelookup[iu->id]; - GSList *nlist=iu->avoidRef->getAttachedShapes(Avoid::runningFrom); - list neighbours; - neighbours.insert >(neighbours.end(),nlist,NULL); - for (list::iterator j(neighbours.begin()); - j != neighbours.end(); + GSList *nlist=iu->avoidRef->getAttachedConnectors(Avoid::runningFrom); + list connectors; + + connectors.insert >(connectors.end(),nlist,NULL); + for (list::iterator j(connectors.begin()); + j != connectors.end(); ++j) { - - SPItem *iv=*j; + SPItem *conn=*j; + SPItem *iv; + SPItem *items[2]; + assert(isConnector(conn)); + SP_PATH(conn)->connEndPair.getAttachedItems(items); + if(items[0]==iu) { + iv=items[1]; + } else { + iv=items[0]; + } + // What do we do if iv not in nodelookup?!?! - unsigned v=nodelookup[iv->id]; - es.push_back(make_pair(u,v)); + map::iterator v_pair=nodelookup.find(iv->id); + if(v_pair!=nodelookup.end()) { + unsigned v=v_pair->second; + cout << "Edge: (" << u <<","<style->marker[SP_MARKER_LOC_END].set) { + if(directed && strcmp(conn->style->marker[SP_MARKER_LOC_END].value,"none")) { + cout << conn->style->marker[SP_MARKER_LOC_END].value << endl; + scy.push_back(new SimpleConstraint(v, u, + (ideal_connector_length * directed_edge_height_modifier))); + } + } + } } if(nlist) { g_slist_free(nlist); @@ -122,24 +164,9 @@ void graphlayout(GSList const *const items) { double eweights[E]; fill(eweights,eweights+E,1); - ConstrainedMajorizationLayout alg(rs,es,eweights, - prefs_get_double_attribute("tools.connector","length",100)); - gchar const *directed = NULL, *overlaps = NULL; - directed = prefs_get_string_attribute("tools.connector", - "directedlayout"); - overlaps = prefs_get_string_attribute("tools.connector", - "avoidoverlaplayout"); - bool avoid_overlaps = false; - if (directed && !strcmp(directed, "true")) { - cout << "Directed layout requested, but not yet implemented\n"; - cout << " because we haven't coded cyclic removal alg...\n"; - } - if (overlaps && !strcmp(overlaps, "true")) { - cout << "Avoid overlaps requested.\n"; - avoid_overlaps = true; - } + ConstrainedMajorizationLayout alg(rs,es,eweights,ideal_connector_length); alg.setupConstraints(NULL,NULL,avoid_overlaps, - NULL,NULL,NULL,NULL,NULL,NULL); + NULL,NULL,NULL,&scy,NULL,NULL); alg.run(); for (list::iterator it(selected.begin()); @@ -156,3 +183,5 @@ void graphlayout(GSList const *const items) { } } } +// vim: set cindent +// vim: ts=4 sw=4 et tw=0 wm=0 diff --git a/src/libcola/cola.cpp b/src/libcola/cola.cpp index 74663f501..3499d729a 100644 --- a/src/libcola/cola.cpp +++ b/src/libcola/cola.cpp @@ -253,7 +253,7 @@ void ConstrainedMajorizationLayout::straighten(vector& sedg } } GradientProjection gp(dim,n,Q,coords,tol,100, - (AlignmentConstraints*)NULL,false,(Rectangle**)NULL,(PageBoundaryConstraints*)NULL,&cs); + (AlignmentConstraints*)NULL,false,(vpsc::Rectangle**)NULL,(PageBoundaryConstraints*)NULL,&cs); constrainedLayout = true; majlayout(Dij,&gp,coords,b); for(unsigned i=0;i& rs, + vector& rs, vector& es, double* eweights, double idealLength, @@ -141,7 +141,7 @@ namespace cola { straightenEdges(NULL) { assert(rs.size()==n); - boundingBoxes = new Rectangle*[rs.size()]; + boundingBoxes = new vpsc::Rectangle*[rs.size()]; copy(rs.begin(),rs.end(),boundingBoxes); double** D=new double*[n]; @@ -229,7 +229,7 @@ namespace cola { double** Dij; double tol; TestConvergence& done; - Rectangle** boundingBoxes; + vpsc::Rectangle** boundingBoxes; double *X, *Y; Clusters* clusters; double edge_length; diff --git a/src/libcola/gradient_projection.cpp b/src/libcola/gradient_projection.cpp index 061ba0f1a..cec59c57a 100644 --- a/src/libcola/gradient_projection.cpp +++ b/src/libcola/gradient_projection.cpp @@ -19,12 +19,13 @@ #include using namespace std; +using namespace vpsc; //#define CONMAJ_LOGGING 1 -static void dumpVPSCException(char const *str, IncVPSC* vpsc) { +static void dumpVPSCException(char const *str, IncSolver* solver) { cerr<getConstraints(m); + Constraint** cs = solver->getConstraints(m); for(unsigned i=0;ifirst], o->second)); - cs.push_back(new Constraint(vs[o->first], vr, o->second)); + cs.push_back(new vpsc::Constraint(vl, vs[o->first], o->second)); + cs.push_back(new vpsc::Constraint(vs[o->first], vr, o->second)); } } OffsetList offsets; @@ -99,19 +99,19 @@ friend class GradientProjection; */ void setupVPSC(Variables &vars, Constraints &cs) { double weight=1; - left = new Variable(vars.size(),place_l,weight); + left = new vpsc::Variable(vars.size(),place_l,weight); vars.push_back(left); - right = new Variable(vars.size(),place_r,weight); + right = new vpsc::Variable(vars.size(),place_r,weight); vars.push_back(right); for(CList::iterator cit=leftof.begin(); cit!=leftof.end(); ++cit) { - Variable* v = vars[(*cit).first]; - cs.push_back(new Constraint(left,v,(*cit).second)); + vpsc::Variable* v = vars[(*cit).first]; + cs.push_back(new vpsc::Constraint(left,v,(*cit).second)); } for(CList::iterator cit=rightof.begin(); cit!=rightof.end(); ++cit) { - Variable* v = vars[(*cit).first]; - cs.push_back(new Constraint(v,right,(*cit).second)); + vpsc::Variable* v = vars[(*cit).first]; + cs.push_back(new vpsc::Constraint(v,right,(*cit).second)); } } /** @@ -163,8 +163,8 @@ friend class GradientProjection; } double dist; // ideal distance between vars double b; // linear coefficient in quad form for left (b_right = -b) - Variable* left; // Variables used in constraints - Variable* right; + vpsc::Variable* left; // Variables used in constraints + vpsc::Variable* right; double lap2; // laplacian entry double g; // descent vec for quad form for left (g_right = -g) double old_place_l; // old_place is where the descent vec g was computed @@ -185,7 +185,7 @@ public: unsigned max_iterations, AlignmentConstraints* acs=NULL, bool nonOverlapConstraints=false, - Rectangle** rs=NULL, + vpsc::Rectangle** rs=NULL, PageBoundaryConstraints *pbc = NULL, SimpleConstraints *sc = NULL) : k(k), n(n), A(A), place(x), rs(rs), @@ -195,18 +195,18 @@ public: constrained(false) { for(unsigned i=0;ibegin(); iac!=acs->end();++iac) { AlignmentConstraint* ac=*iac; - Variable *v=ac->variable=new Variable(vars.size(),ac->position,0.0001); + vpsc::Variable *v=ac->variable=new vpsc::Variable(vars.size(),ac->position,0.0001); vars.push_back(v); for(OffsetList::iterator o=ac->offsets.begin(); o!=ac->offsets.end(); o++) { - gcs.push_back(new Constraint(v,vars[o->first],o->second,true)); + gcs.push_back(new vpsc::Constraint(v,vars[o->first],o->second,true)); } } } @@ -215,7 +215,7 @@ public: } if (sc) { for(SimpleConstraints::iterator c=sc->begin(); c!=sc->end();++c) { - gcs.push_back(new Constraint( + gcs.push_back(new vpsc::Constraint( vars[(*c)->left],vars[(*c)->right],(*c)->gap)); } } @@ -239,8 +239,8 @@ public: unsigned solve(double* b); DummyVars dummy_vars; // special vars that must be considered in Lapl. private: - IncVPSC* setupVPSC(); - void destroyVPSC(IncVPSC *vpsc); + vpsc::IncSolver* setupVPSC(); + void destroyVPSC(vpsc::IncSolver *vpsc); Dim k; unsigned n; // number of actual vars double** A; // Graph laplacian matrix @@ -250,7 +250,7 @@ private: Constraints gcs; /* global constraints - persist throughout all iterations */ Constraints lcs; /* local constraints - only for current iteration */ - Rectangle** rs; + vpsc::Rectangle** rs; bool nonOverlapConstraints; double tolerance; AlignmentConstraints* acs; diff --git a/src/libcola/straightener.h b/src/libcola/straightener.h index 33af0c697..e2c50a3a6 100644 --- a/src/libcola/straightener.h +++ b/src/libcola/straightener.h @@ -97,7 +97,7 @@ namespace straightener { bool dummy; double weight; bool open; - Node(unsigned id, Rectangle* r) : + Node(unsigned id, vpsc::Rectangle* r) : id(id),x(r->getCentreX()),y(r->getCentreY()), width(r->width()), height(r->height()), xmin(x-width/2),xmax(x+width/2), ymin(y-height/2),ymax(y+height/2), diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp index 69a439cd7..221df536a 100644 --- a/src/libvpsc/block.cpp +++ b/src/libvpsc/block.cpp @@ -23,6 +23,7 @@ using std::endl; #endif using std::vector; +namespace vpsc { void Block::addVariable(Variable* const v) { v->block=this; vars->push_back(v); @@ -346,6 +347,22 @@ void Block::populateSplitBlock(Block *b, Variable* const v, Variable* const u) { populateSplitBlock(b, (*c)->right, v); } } +// Search active constraint tree from u to see if there is a directed path to v. +// Returns true if path is found with all constraints in path having their visited flag +// set true. +bool Block::isActiveDirectedPathBetween(Variable* u, Variable *v) { + if(u==v) return true; + for (Cit c=u->out.begin();c!=u->out.end();++c) { + if(canFollowRight(*c,NULL)) { + if(isActiveDirectedPathBetween((*c)->right,v)) { + (*c)->visited=true; + return true; + } + (*c)->visited=false; + } + } + return false; +} /** * Block needs to be split because of a violated constraint between vl and vr. * We need to search the active constraint tree between l and r and find the constraint @@ -402,3 +419,4 @@ ostream& operator <<(ostream &os, const Block& b) } return os; } +} diff --git a/src/libvpsc/block.h b/src/libvpsc/block.h index 81e6c7637..9c285f311 100644 --- a/src/libvpsc/block.h +++ b/src/libvpsc/block.h @@ -16,10 +16,10 @@ #include #include +template class PairingHeap; +namespace vpsc { class Variable; class Constraint; -template class PairingHeap; -class StupidPriorityQueue; class Block { @@ -55,6 +55,7 @@ public: long timeStamp; PairingHeap *in; PairingHeap *out; + bool isActiveDirectedPathBetween(Variable* u, Variable *v); private: typedef enum {NONE, LEFT, RIGHT} Direction; typedef std::pair Pair; @@ -71,4 +72,5 @@ private: void setUpConstraintHeap(PairingHeap* &h,bool in); }; +} #endif // SEEN_REMOVEOVERLAP_BLOCK_H diff --git a/src/libvpsc/blocks.cpp b/src/libvpsc/blocks.cpp index 48f0237bf..fe0caacfc 100644 --- a/src/libvpsc/blocks.cpp +++ b/src/libvpsc/blocks.cpp @@ -28,6 +28,8 @@ using std::iterator; using std::list; using std::copy; +namespace vpsc { + long blockTimeCtr; Blocks::Blocks(const int n, Variable* const vs[]) : vs(vs),nvs(n) { @@ -194,3 +196,4 @@ double Blocks::cost() { return c; } +} diff --git a/src/libvpsc/blocks.h b/src/libvpsc/blocks.h index 0be1d7636..72363ef66 100644 --- a/src/libvpsc/blocks.h +++ b/src/libvpsc/blocks.h @@ -23,6 +23,7 @@ #include #include +namespace vpsc { class Block; class Variable; class Constraint; @@ -50,4 +51,5 @@ private: }; extern long blockTimeCtr; +} #endif // SEEN_REMOVEOVERLAP_BLOCKS_H diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp index 7c200878b..af5da941a 100644 --- a/src/libvpsc/constraint.cpp +++ b/src/libvpsc/constraint.cpp @@ -12,6 +12,7 @@ #include "constraint.h" #include +namespace vpsc { Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality) : left(left), right(right), @@ -45,3 +46,4 @@ std::ostream& operator <<(std::ostream &os, const Constraint &c) } return os; } +} diff --git a/src/libvpsc/constraint.h b/src/libvpsc/constraint.h index 3da7449cd..c73776daf 100644 --- a/src/libvpsc/constraint.h +++ b/src/libvpsc/constraint.h @@ -15,6 +15,7 @@ #include #include "variable.h" +namespace vpsc { class Constraint { @@ -54,5 +55,6 @@ static inline bool compareConstraints(Constraint *const &l, Constraint *const &r } return sl < sr; } +} #endif // SEEN_REMOVEOVERLAP_CONSTRAINT_H diff --git a/src/libvpsc/csolve_VPSC.cpp b/src/libvpsc/csolve_VPSC.cpp index b78b01054..bd7db5ab2 100644 --- a/src/libvpsc/csolve_VPSC.cpp +++ b/src/libvpsc/csolve_VPSC.cpp @@ -15,6 +15,7 @@ #include "generate-constraints.h" #include "solve_VPSC.h" #include "csolve_VPSC.h" +using namespace vpsc; extern "C" { Variable* newVariable(int id, double desiredPos, double weight) { return new Variable(id,desiredPos,weight); @@ -22,11 +23,11 @@ Variable* newVariable(int id, double desiredPos, double weight) { Constraint* newConstraint(Variable* left, Variable* right, double gap) { return new Constraint(left,right,gap); } -VPSC* newVPSC(int n, Variable* vs[], int m, Constraint* cs[]) { - return new VPSC(n,vs,m,cs); +Solver* newSolver(int n, Variable* vs[], int m, Constraint* cs[]) { + return new Solver(n,vs,m,cs); } -VPSC* newIncVPSC(int n, Variable* vs[], int m, Constraint* cs[]) { - return (VPSC*)new IncVPSC(n,vs,m,cs); +Solver* newIncSolver(int n, Variable* vs[], int m, Constraint* cs[]) { + return (Solver*)new vpsc::IncSolver(n,vs,m,cs); } int genXConstraints(int n, boxf* bb, Variable** vs, Constraint*** cs,int transitiveClosure) { @@ -67,7 +68,7 @@ void deleteConstraint(Constraint* c) { void deleteVariable(Variable* v) { delete v; } -void satisfyVPSC(VPSC* vpsc) { +void satisfyVPSC(Solver* vpsc) { try { vpsc->satisfy(); } catch(const char *e) { @@ -75,17 +76,17 @@ void satisfyVPSC(VPSC* vpsc) { exit(1); } } -int getSplitCnt(IncVPSC *vpsc) { +int getSplitCnt(IncSolver *vpsc) { return vpsc->splitCnt; } -void deleteVPSC(VPSC *vpsc) { +void deleteVPSC(Solver *vpsc) { assert(vpsc!=NULL); delete vpsc; } -void solveVPSC(VPSC* vpsc) { +void solveVPSC(Solver* vpsc) { vpsc->solve(); } -void splitIncVPSC(IncVPSC* vpsc) { +void splitIncVPSC(IncSolver* vpsc) { vpsc->splitBlocks(); } void setVariableDesiredPos(Variable *v, double desiredPos) { diff --git a/src/libvpsc/csolve_VPSC.h b/src/libvpsc/csolve_VPSC.h index cd879effe..81e50d990 100644 --- a/src/libvpsc/csolve_VPSC.h +++ b/src/libvpsc/csolve_VPSC.h @@ -11,19 +11,26 @@ #ifndef _CSOLVE_VPSC_H_ #define _CSOLVE_VPSC_H_ #ifdef __cplusplus +class vpsc::Variable; +class vpsc::Constraint; +class vpsc::Solver; +class vpsc::IncSolver; +using namespace vpsc; extern "C" { -#endif +#else typedef struct Variable Variable; +typedef struct Constraint Constraint; +typedef struct Solver Solver; +typedef struct IncSolver IncSolver; +#endif Variable* newVariable(int id, double desiredPos, double weight); void setVariableDesiredPos(Variable *, double desiredPos); double getVariablePos(Variable*); -typedef struct Constraint Constraint; Constraint* newConstraint(Variable* left, Variable* right, double gap); -typedef struct VPSC VPSC; -VPSC* newVPSC(int n, Variable* vs[], int m, Constraint* cs[]); -void deleteVPSC(VPSC*); +Solver* newSolver(int n, Variable* vs[], int m, Constraint* cs[]); +void deleteSolver(Solver*); void deleteConstraint(Constraint*); void deleteVariable(Variable*); Constraint** newConstraints(int m); @@ -42,12 +49,11 @@ int genXConstraints(int n, boxf[], Variable** vs, Constraint*** cs, int transitiveClosure); int genYConstraints(int n, boxf[], Variable** vs, Constraint*** cs); -void satisfyVPSC(VPSC*); -void solveVPSC(VPSC*); -typedef struct IncVPSC IncVPSC; -VPSC* newIncVPSC(int n, Variable* vs[], int m, Constraint* cs[]); -void splitIncVPSC(IncVPSC*); -int getSplitCnt(IncVPSC *vpsc); +void satisfyVPSC(Solver*); +void solveVPSC(Solver*); +Solver* newIncSolver(int n, Variable* vs[], int m, Constraint* cs[]); +void splitIncSolver(IncSolver*); +int getSplitCnt(IncSolver *vpsc); #ifdef __cplusplus } #endif diff --git a/src/libvpsc/generate-constraints.cpp b/src/libvpsc/generate-constraints.cpp index 312ad960b..3b69e7968 100644 --- a/src/libvpsc/generate-constraints.cpp +++ b/src/libvpsc/generate-constraints.cpp @@ -20,10 +20,12 @@ using std::set; using std::vector; +namespace vpsc { std::ostream& operator <<(std::ostream &os, const Rectangle &r) { os << "{"< +namespace vpsc { class Rectangle { friend std::ostream& operator <<(std::ostream &os, const Rectangle &r); public: @@ -74,5 +75,6 @@ class Constraint; int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists); int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs); +} #endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H diff --git a/src/libvpsc/remove_rectangle_overlap.cpp b/src/libvpsc/remove_rectangle_overlap.cpp index 6f6ace03a..78df24b22 100644 --- a/src/libvpsc/remove_rectangle_overlap.cpp +++ b/src/libvpsc/remove_rectangle_overlap.cpp @@ -24,6 +24,7 @@ using std::endl; #endif #define EXTRA_GAP 0.0001 +using namespace vpsc; double Rectangle::xBorder=0; double Rectangle::yBorder=0; @@ -55,7 +56,7 @@ void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double for(int i=0;idesiredPosition; } - VPSC vpsc_x(n,vs,m,cs); + Solver vpsc_x(n,vs,m,cs); #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"Calling VPSC: Horizontal pass 1"< #ifdef RECTANGLE_OVERLAP_LOGGING #include -using std::ios; -using std::ofstream; -using std::endl; #endif +#include + +using namespace std; -using std::ostringstream; -using std::list; -using std::set; +namespace vpsc { static const double ZERO_UPPERBOUND=-0.0000001; -IncVPSC::IncVPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) - : VPSC(n,vs,m,cs) { +IncSolver::IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) + : Solver(n,vs,m,cs) { inactive.assign(cs,cs+m); for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) { (*i)->active=false; } } -VPSC::VPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) { +Solver::Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) { bs=new Blocks(n, vs); #ifdef RECTANGLE_OVERLAP_LOGGING printBlocks(); - assert(!constraintGraphIsCyclic(n,vs)); + //assert(!constraintGraphIsCyclic(n,vs)); #endif } -VPSC::~VPSC() { +Solver::~Solver() { delete bs; } // useful in debugging -void VPSC::printBlocks() { +void Solver::printBlocks() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); for(set::iterator i=bs->begin();i!=bs->end();++i) { @@ -71,7 +69,7 @@ void VPSC::printBlocks() { * first) fixing the position of variables inside blocks relative to one * another so that constraints internal to the block are satisfied. */ -void VPSC::satisfy() { +void Solver::satisfy() { list *vs=bs->totalOrder(); for(list::iterator i=vs->begin();i!=vs->end();++i) { Variable *v=*i; @@ -93,7 +91,7 @@ void VPSC::satisfy() { delete vs; } -void VPSC::refine() { +void Solver::refine() { bool solved=false; // Solve shouldn't loop indefinately // ... but just to make sure we limit the number of iterations @@ -137,12 +135,12 @@ void VPSC::refine() { * refinement is possible by splitting the block. This is done repeatedly * until no further improvement is possible. */ -void VPSC::solve() { +void Solver::solve() { satisfy(); refine(); } -void IncVPSC::solve() { +void IncSolver::solve() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"solve_inc()..."<merge(rb,v); } else { + if(lb->isActiveDirectedPathBetween(v->right,v->left)) { + // cycle found, relax the violated, cyclic constraint + v->gap = v->slack(); + continue; + } if(splitCtr++>10000) { throw "Cycle Error!"; } @@ -215,7 +218,7 @@ void IncVPSC::satisfy() { printBlocks(); #endif } -void IncVPSC::moveBlocks() { +void IncSolver::moveBlocks() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"moveBlocks()..."< -using std::map; -using std::vector; struct node { set in; set out; }; // useful in debugging - cycles would be BAD -bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) { +bool Solver::constraintGraphIsCyclic(const unsigned n, Variable* const vs[]) { map varmap; vector graph; for(unsigned i=0;i bmap; vector graph; for(set::const_iterator i=bs->begin();i!=bs->end();++i) { @@ -414,4 +414,4 @@ bool VPSC::blockGraphIsCyclic() { } return false; } - +} diff --git a/src/libvpsc/solve_VPSC.h b/src/libvpsc/solve_VPSC.h index 4cd5559d6..0f919a22a 100644 --- a/src/libvpsc/solve_VPSC.h +++ b/src/libvpsc/solve_VPSC.h @@ -21,6 +21,8 @@ #define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H #include + +namespace vpsc { class Variable; class Constraint; class Blocks; @@ -28,13 +30,13 @@ class Blocks; /** * Variable Placement with Separation Constraints problem instance */ -class VPSC { +class Solver { public: virtual void satisfy(); virtual void solve(); - VPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); - virtual ~VPSC(); + Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); + virtual ~Solver(); Constraint** getConstraints(unsigned &m) { m=this->m; return cs; } const Variable* const * getVariables(unsigned &n) { n=this->n; return vs; } protected: @@ -46,21 +48,22 @@ protected: void printBlocks(); private: void refine(); - bool constraintGraphIsCyclic(const unsigned n, Variable *vs[]); + bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]); bool blockGraphIsCyclic(); }; -class IncVPSC : public VPSC { +class IncSolver : public Solver { public: unsigned splitCnt; void satisfy(); void solve(); void moveBlocks(); void splitBlocks(); - IncVPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); + IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); private: typedef std::vector ConstraintList; ConstraintList inactive; Constraint* mostViolated(ConstraintList &l); }; +} #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H diff --git a/src/libvpsc/variable.cpp b/src/libvpsc/variable.cpp index 1890f788e..19dc0746a 100644 --- a/src/libvpsc/variable.cpp +++ b/src/libvpsc/variable.cpp @@ -8,8 +8,9 @@ * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include "variable.h" +namespace vpsc { std::ostream& operator <<(std::ostream &os, const Variable &v) { os << "(" << v.id << "=" << v.position() << ")"; return os; } - +} diff --git a/src/libvpsc/variable.h b/src/libvpsc/variable.h index b1ab66c95..d2c689723 100644 --- a/src/libvpsc/variable.h +++ b/src/libvpsc/variable.h @@ -12,10 +12,11 @@ #include #include -class Block; -class Constraint; #include "block.h" +namespace vpsc { + +class Constraint; typedef std::vector Constraints; class Variable { @@ -48,4 +49,5 @@ public: out.clear(); } }; +} #endif // SEEN_REMOVEOVERLAP_VARIABLE_H diff --git a/src/removeoverlap/removeoverlap.cpp b/src/removeoverlap/removeoverlap.cpp index 3a8481db2..c640fb407 100644 --- a/src/removeoverlap/removeoverlap.cpp +++ b/src/removeoverlap/removeoverlap.cpp @@ -15,6 +15,8 @@ #include "libvpsc/generate-constraints.h" #include "libvpsc/remove_rectangle_overlap.h" +using vpsc::Rectangle; + /** * Takes a list of inkscape items and moves them as little as possible * such that rectangular bounding boxes are separated by at least xGap -- 2.30.2