32using std::ostringstream;
36#ifndef RECTANGLE_OVERLAP_LOGGING
37 #define RECTANGLE_OVERLAP_LOGGING 0
42 inactive.assign(
cs,
cs+
m);
48 : bs(n, vs), cs(cs), m(m) {
51 assert(!constraintGraphIsCyclic(n,vs));
62 for(
unsigned i=0;i<
m;i++) {
80 if(!v->block->deleted) {
85 for(
unsigned i=0;i<
m;i++) {
86 if(
cs[i]->slack()<-0.0000001) {
89 f<<
"Error: Unsatisfied constraint: "<<*
cs[i]<<
"\n";
92 throw "Unsatisfied constraint";
98 for (
bool solved =
false; !solved;) {
101 b->setUpInConstraints();
102 b->setUpOutConstraints();
106 if(c!=
nullptr && c->
lm<0) {
109 f<<
"Split on constraint: "<<*c<<
"\n";
112 Block *l=
nullptr, *r=
nullptr;
121 for(
unsigned i=0;i<
m;i++) {
122 if(
cs[i]->slack()<-0.0000001) {
123 assert(
cs[i]->slack()>-0.0000001);
124 throw "Unsatisfied constraint";
142 f<<
"solve_inc()...\n";
144 double lastcost,cost =
bs.
cost();
152 f<<
" cost="<<cost<<
"\n";
154 }
while(fabs(lastcost-cost)>0.0001);
172 f<<
"satisfy_inc()...\n";
177 while(mostViolated(inactive,v)<-0.0000001) {
183 if(splitCtr++>10000) {
184 throw "Cycle Error!";
194 f<<
" finished merges.\n";
197 for(
unsigned i=0;i<
m;i++) {
199 if(v->
slack()<-0.0000001) {
202 s<<
"Unsatisfied constraint: "<<*v;
203 throw s.str().c_str();
208 f<<
" finished cleanup.\n";
215 f<<
"moveBlocks()...\n";
218 b->wposn = b->desiredWeightedPosition();
219 b->posn = b->wposn / b->weight;
223 f<<
" moved blocks.\n";
232 if(v!=
nullptr && v->
lm < -0.0000001) {
235 f<<
" found split point: "<<*v<<
" lm="<<v->
lm<<
"\n";
240 double pos = b2->
posn;
243 l->wposn = l->posn * l->weight;
244 r->wposn = r->posn * r->weight;
248 inactive.push_back(v);
251 f<<
" new blocks: "<<*l<<
" and "<<*r<<
"\n";
257 f<<
" finished splits.\n";
266double IncVPSC::mostViolated(ConstraintList &l,
Constraint* &v) {
267 double minSlack = DBL_MAX;
270 f<<
"Looking for most violated...\n";
272 ConstraintList::iterator end = l.end();
273 ConstraintList::iterator deletePoint = end;
274 for(ConstraintList::iterator i=l.begin();i!=end;i++) {
276 double slack = c->
slack();
277 if (slack < minSlack) {
287 if(deletePoint != end && minSlack<-0.0000001) {
288 *deletePoint = l[l.size()-1];
289 l.resize(l.size()-1);
293 f<<
" most violated is: "<<*v<<
"\n";
306bool VPSC::constraintGraphIsCyclic(
const unsigned n,
Variable *vs[]) {
307 map<Variable*, node*> varmap;
308 vector<std::unique_ptr<node>>
graph;
309 for(
unsigned i=0;i<n;i++) {
311 varmap[vs[i]]=
graph.back().get();
313 for(
unsigned i=0;i<n;i++) {
316 varmap[vs[i]]->
in.insert(varmap[l]);
321 varmap[vs[i]]->
out.insert(varmap[r]);
324 while(!
graph.empty()) {
326 vector<std::unique_ptr<node>>::iterator i=
graph.begin();
327 for(;i!=
graph.end();i++) {
347bool VPSC::blockGraphIsCyclic() {
348 map<Block*, node*> bmap;
349 vector<std::unique_ptr<node>>
graph;
352 bmap[b]=
graph.back().get();
355 b->setUpInConstraints();
359 bmap[b]->
in.insert(bmap[l]);
360 b->deleteMinInConstraint();
361 c=b->findMinInConstraint();
364 b->setUpOutConstraints();
365 c=b->findMinOutConstraint();
368 bmap[b]->
out.insert(bmap[r]);
369 b->deleteMinOutConstraint();
370 c=b->findMinOutConstraint();
373 while(!
graph.empty()) {
375 vector<std::unique_ptr<node>>::iterator i=
graph.begin();
376 for(;i!=
graph.end();i++) {
static void out(agerrlevel_t level, const char *fmt, va_list args)
Report messages using a user-supplied or default write function.
#define RECTANGLE_OVERLAP_LOGGING
#define LOGFILE
A block structure defined over the variables.
void split(Block *&l, Block *&r, Constraint *c)
Constraint * splitBetween(Variable *vl, Variable *vr, Block *&lb, Block *&rb)
std::unique_ptr< PairingHeap< Constraint * > > out
void merge(Block *b, Constraint *c, double dist)
std::unique_ptr< PairingHeap< Constraint * > > in
void split(Block *b, Block *&l, Block *&r, Constraint *c)
std::list< Variable * > totalOrder()
Agraph_t * graph(char *name)
A constraint determines a minimum or exact spacing required between two variables.
IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[])
VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[])