summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/connector-context.cpp2
-rw-r--r--src/graphlayout/graphlayout.cpp81
-rw-r--r--src/libcola/cola.cpp2
-rw-r--r--src/libcola/cola.h6
-rw-r--r--src/libcola/gradient_projection.cpp31
-rw-r--r--src/libcola/gradient_projection.h48
-rw-r--r--src/libcola/straightener.h2
-rw-r--r--src/libvpsc/block.cpp18
-rw-r--r--src/libvpsc/block.h6
-rw-r--r--src/libvpsc/blocks.cpp3
-rw-r--r--src/libvpsc/blocks.h2
-rw-r--r--src/libvpsc/constraint.cpp2
-rw-r--r--src/libvpsc/constraint.h2
-rw-r--r--src/libvpsc/csolve_VPSC.cpp19
-rw-r--r--src/libvpsc/csolve_VPSC.h28
-rw-r--r--src/libvpsc/generate-constraints.cpp3
-rw-r--r--src/libvpsc/generate-constraints.h2
-rw-r--r--src/libvpsc/remove_rectangle_overlap.cpp7
-rw-r--r--src/libvpsc/remove_rectangle_overlap.h4
-rw-r--r--src/libvpsc/solve_VPSC.cpp52
-rw-r--r--src/libvpsc/solve_VPSC.h15
-rw-r--r--src/libvpsc/variable.cpp3
-rw-r--r--src/libvpsc/variable.h6
-rw-r--r--src/removeoverlap/removeoverlap.cpp2
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<SPItem *>::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<SPItem *> neighbours;
- neighbours.insert<GSListConstIterator<SPItem *> >(neighbours.end(),nlist,NULL);
- for (list<SPItem *>::iterator j(neighbours.begin());
- j != neighbours.end();
+ GSList *nlist=iu->avoidRef->getAttachedConnectors(Avoid::runningFrom);
+ list<SPItem *> connectors;
+
+ connectors.insert<GSListConstIterator<SPItem *> >(connectors.end(),nlist,NULL);
+ for (list<SPItem *>::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<string,unsigned>::iterator v_pair=nodelookup.find(iv->id);
+ if(v_pair!=nodelookup.end()) {
+ unsigned v=v_pair->second;
+ cout << "Edge: (" << u <<","<<v<<")"<<endl;
+ es.push_back(make_pair(u,v));
+ if(conn->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<SPItem *>::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<straightener::Edge*>& 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<sedges.size();i++) {
diff --git a/src/libcola/cola.h b/src/libcola/cola.h
index d4b0d1421..cc99515bf 100644
--- a/src/libcola/cola.h
+++ b/src/libcola/cola.h
@@ -121,7 +121,7 @@ namespace cola {
class ConstrainedMajorizationLayout {
public:
ConstrainedMajorizationLayout(
- vector<Rectangle*>& rs,
+ vector<vpsc::Rectangle*>& rs,
vector<Edge>& 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 <iostream>
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<<str<<endl;
unsigned m;
- Constraint** cs = vpsc->getConstraints(m);
+ Constraint** cs = solver->getConstraints(m);
for(unsigned i=0;i<m;i++) {
cerr << *cs[i] << endl;
}
@@ -41,9 +42,9 @@ unsigned GradientProjection::solve(double * b) {
bool converged=false;
- IncVPSC* vpsc=NULL;
+ IncSolver* solver=NULL;
- vpsc = setupVPSC();
+ solver = setupVPSC();
//cerr << "in gradient projection: n=" << n << endl;
for (i=0;i<n;i++) {
assert(!isnan(place[i]));
@@ -51,9 +52,9 @@ unsigned GradientProjection::solve(double * b) {
vars[i]->desiredPosition=place[i];
}
try {
- vpsc->satisfy();
+ solver->satisfy();
} catch (char const *str) {
- dumpVPSCException(str,vpsc);
+ dumpVPSCException(str,solver);
}
for (i=0;i<n;i++) {
@@ -104,9 +105,9 @@ unsigned GradientProjection::solve(double * b) {
//project to constraint boundary
try {
- vpsc->satisfy();
+ solver->satisfy();
} catch (char const *str) {
- dumpVPSCException(str,vpsc);
+ dumpVPSCException(str,solver);
}
for (i=0;i<n;i++) {
place[i]=vars[i]->position();
@@ -155,7 +156,7 @@ unsigned GradientProjection::solve(double * b) {
converged=false;
}
}
- destroyVPSC(vpsc);
+ destroyVPSC(solver);
return counter;
}
// Setup an instance of the Variable Placement with Separation Constraints
@@ -164,7 +165,7 @@ unsigned GradientProjection::solve(double * b) {
// --- that are only relevant to one iteration, and merge these with the
// global constraint list (including alignment constraints,
// dir-edge constraints, containment constraints, etc).
-IncVPSC* GradientProjection::setupVPSC() {
+IncSolver* GradientProjection::setupVPSC() {
Constraint **cs;
//assert(lcs.size()==0);
@@ -192,13 +193,13 @@ IncVPSC* GradientProjection::setupVPSC() {
}
cs = new Constraint*[lcs.size() + gcs.size()];
unsigned m = 0 ;
- for(Constraints::iterator ci = lcs.begin();ci!=lcs.end();++ci) {
+ for(vector<Constraint*>::iterator ci = lcs.begin();ci!=lcs.end();++ci) {
cs[m++] = *ci;
}
- for(Constraints::iterator ci = gcs.begin();ci!=gcs.end();++ci) {
+ for(vector<Constraint*>::iterator ci = gcs.begin();ci!=gcs.end();++ci) {
cs[m++] = *ci;
}
- return new IncVPSC(vars.size(),vs,m,cs);
+ return new IncSolver(vars.size(),vs,m,cs);
}
void GradientProjection::clearDummyVars() {
for(DummyVars::iterator i=dummy_vars.begin();i!=dummy_vars.end();++i) {
@@ -206,7 +207,7 @@ void GradientProjection::clearDummyVars() {
}
dummy_vars.clear();
}
-void GradientProjection::destroyVPSC(IncVPSC *vpsc) {
+void GradientProjection::destroyVPSC(IncSolver *vpsc) {
if(acs) {
for(AlignmentConstraints::iterator ac=acs->begin(); ac!=acs->end();++ac) {
(*ac)->updatePosition();
@@ -218,7 +219,7 @@ void GradientProjection::destroyVPSC(IncVPSC *vpsc) {
delete vpsc;
delete [] cs;
delete [] vs;
- for(Constraints::iterator i=lcs.begin();i!=lcs.end();i++) {
+ for(vector<Constraint*>::iterator i=lcs.begin();i!=lcs.end();i++) {
delete *i;
}
lcs.clear();
diff --git a/src/libcola/gradient_projection.h b/src/libcola/gradient_projection.h
index e8b72180b..9ee3ff5c5 100644
--- a/src/libcola/gradient_projection.h
+++ b/src/libcola/gradient_projection.h
@@ -11,8 +11,8 @@
using namespace std;
-typedef vector<Constraint*> Constraints;
-typedef vector<Variable*> Variables;
+typedef vector<vpsc::Constraint*> Constraints;
+typedef vector<vpsc::Variable*> Variables;
typedef vector<pair<unsigned,double> > OffsetList;
class SimpleConstraint {
@@ -35,7 +35,7 @@ public:
void* guide;
double position;
private:
- Variable* variable;
+ vpsc::Variable* variable;
};
typedef vector<AlignmentConstraint*> AlignmentConstraints;
@@ -44,16 +44,16 @@ public:
PageBoundaryConstraints(double lm, double rm, double w)
: leftMargin(lm), rightMargin(rm), weight(w) { }
void createVarsAndConstraints(Variables &vs, Constraints &cs) {
- Variable* vl, * vr;
+ vpsc::Variable* vl, * vr;
// create 2 dummy vars, based on the dimension we are in
- vs.push_back(vl=new Variable(vs.size(), leftMargin, weight));
- vs.push_back(vr=new Variable(vs.size(), rightMargin, weight));
+ vs.push_back(vl=new vpsc::Variable(vs.size(), leftMargin, weight));
+ vs.push_back(vr=new vpsc::Variable(vs.size(), rightMargin, weight));
// for each of the "real" variables, create a constraint that puts that var
// between our two new dummy vars, depending on the dimension.
for(OffsetList::iterator o=offsets.begin(); o!=offsets.end(); ++o) {
- cs.push_back(new Constraint(vl, vs[o->first], 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;i<n;i++) {
- vars.push_back(new Variable(i,1,1));
+ vars.push_back(new vpsc::Variable(i,1,1));
}
if(acs) {
for(AlignmentConstraints::iterator iac=acs->begin();
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 <vector>
#include <iostream>
+template <class T> class PairingHeap;
+namespace vpsc {
class Variable;
class Constraint;
-template <class T> class PairingHeap;
-class StupidPriorityQueue;
class Block
{
@@ -55,6 +55,7 @@ public:
long timeStamp;
PairingHeap<Constraint*> *in;
PairingHeap<Constraint*> *out;
+ bool isActiveDirectedPathBetween(Variable* u, Variable *v);
private:
typedef enum {NONE, LEFT, RIGHT} Direction;
typedef std::pair<double, Constraint*> Pair;
@@ -71,4 +72,5 @@ private:
void setUpConstraintHeap(PairingHeap<Constraint*>* &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 <set>
#include <list>
+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 <cassert>
+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 <iostream>
#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 << "{"<<r.minX<<","<<r.maxX<<","<<r.minY<<","<<r.maxY<<"},";
return os;
}
+
Rectangle::Rectangle(double x, double X, double y, double Y)
: minX(x),maxX(X),minY(y),maxY(Y) {
assert(x<=X);
@@ -301,3 +303,4 @@ int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constrain
for(i=0;i<m;i++) cs[i]=constraints[i];
return m;
}
+}
diff --git a/src/libvpsc/generate-constraints.h b/src/libvpsc/generate-constraints.h
index 56ee9536a..8b858af3f 100644
--- a/src/libvpsc/generate-constraints.h
+++ b/src/libvpsc/generate-constraints.h
@@ -13,6 +13,7 @@
#define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
#include <iostream>
+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;i<n;i++) {
oldX[i]=vs[i]->desiredPosition;
}
- 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"<<endl;
@@ -73,7 +74,7 @@ void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double
// one another above are not considered overlapping
Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP);
m=generateYConstraints(n,rs,vs,cs);
- VPSC vpsc_y(n,vs,m,cs);
+ Solver vpsc_y(n,vs,m,cs);
#ifdef RECTANGLE_OVERLAP_LOGGING
f.open(LOGFILE,ios::app);
f<<"Calling VPSC: Vertical pass"<<endl;
@@ -91,7 +92,7 @@ void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double
delete [] cs;
Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
m=generateXConstraints(n,rs,vs,cs,false);
- VPSC vpsc_x2(n,vs,m,cs);
+ Solver vpsc_x2(n,vs,m,cs);
#ifdef RECTANGLE_OVERLAP_LOGGING
f.open(LOGFILE,ios::app);
f<<"Calling VPSC: Horizontal pass 2"<<endl;
diff --git a/src/libvpsc/remove_rectangle_overlap.h b/src/libvpsc/remove_rectangle_overlap.h
index 08b035e31..82f3ef494 100644
--- a/src/libvpsc/remove_rectangle_overlap.h
+++ b/src/libvpsc/remove_rectangle_overlap.h
@@ -13,9 +13,9 @@
* Released under GNU LGPL. Read the file 'COPYING' for more information.
*/
-class Rectangle;
+class vpsc::Rectangle;
-void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder);
+void removeRectangleOverlap(unsigned n, vpsc::Rectangle *rs[], double xBorder, double yBorder);
#endif /* !REMOVE_RECTANGLE_OVERLAP_H_SEEN */
diff --git a/src/libvpsc/solve_VPSC.cpp b/src/libvpsc/solve_VPSC.cpp
index 44918951d..ff0ff96bf 100644
--- a/src/libvpsc/solve_VPSC.cpp
+++ b/src/libvpsc/solve_VPSC.cpp
@@ -19,37 +19,35 @@
#include <sstream>
#ifdef RECTANGLE_OVERLAP_LOGGING
#include <fstream>
-using std::ios;
-using std::ofstream;
-using std::endl;
#endif
+#include <map>
+
+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<Block*>::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<Variable*> *vs=bs->totalOrder();
for(list<Variable*>::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()..."<<endl;
@@ -171,7 +169,7 @@ void IncVPSC::solve() {
* over an active constraint between the two variables. We choose the
* constraint with the most negative lagrangian multiplier.
*/
-void IncVPSC::satisfy() {
+void IncSolver::satisfy() {
#ifdef RECTANGLE_OVERLAP_LOGGING
ofstream f(LOGFILE,ios::app);
f<<"satisfy_inc()..."<<endl;
@@ -185,6 +183,11 @@ void IncVPSC::satisfy() {
if(lb != rb) {
lb->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()..."<<endl;
@@ -229,7 +232,7 @@ void IncVPSC::moveBlocks() {
f<<" moved blocks."<<endl;
#endif
}
-void IncVPSC::splitBlocks() {
+void IncSolver::splitBlocks() {
#ifdef RECTANGLE_OVERLAP_LOGGING
ofstream f(LOGFILE,ios::app);
#endif
@@ -271,7 +274,7 @@ void IncVPSC::splitBlocks() {
* Scan constraint list for the most violated constraint, or the first equality
* constraint
*/
-Constraint* IncVPSC::mostViolated(ConstraintList &l) {
+Constraint* IncSolver::mostViolated(ConstraintList &l) {
double minSlack = DBL_MAX;
Constraint* v=NULL;
#ifdef RECTANGLE_OVERLAP_LOGGING
@@ -304,15 +307,12 @@ Constraint* IncVPSC::mostViolated(ConstraintList &l) {
return v;
}
-#include <map>
-using std::map;
-using std::vector;
struct node {
set<node*> in;
set<node*> 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<Variable*, node*> varmap;
vector<node*> graph;
for(unsigned i=0;i<n;i++) {
@@ -359,7 +359,7 @@ bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
}
// useful in debugging - cycles would be BAD
-bool VPSC::blockGraphIsCyclic() {
+bool Solver::blockGraphIsCyclic() {
map<Block*, node*> bmap;
vector<node*> graph;
for(set<Block*>::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 <vector>
+
+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<Constraint*> 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 <vector>
#include <iostream>
-class Block;
-class Constraint;
#include "block.h"
+namespace vpsc {
+
+class Constraint;
typedef std::vector<Constraint*> 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
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-19 07:59:45 +0000