1 /**
2 * \brief Solve an instance of the "Variable Placement with Separation
3 * Constraints" problem.
4 *
5 * Authors:
6 * Tim Dwyer <tgdwyer@gmail.com>
7 *
8 * Copyright (C) 2005 Authors
9 *
10 * Released under GNU LGPL. Read the file 'COPYING' for more information.
11 */
13 #include <cassert>
14 #include "constraint.h"
15 #include "block.h"
16 #include "blocks.h"
17 #include "solve_VPSC.h"
18 #include <math.h>
19 #include <sstream>
20 #ifdef RECTANGLE_OVERLAP_LOGGING
21 #include <fstream>
22 using std::ios;
23 using std::ofstream;
24 using std::endl;
25 #endif
27 using std::ostringstream;
28 using std::list;
29 using std::set;
31 IncVPSC::IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[])
32 : VPSC(n,vs,m,cs) {
33 inactive.assign(cs,cs+m);
34 for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) {
35 (*i)->active=false;
36 }
37 }
38 VPSC::VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) : cs(cs), m(m), vs(vs) {
39 bs=new Blocks(n, vs);
40 #ifdef RECTANGLE_OVERLAP_LOGGING
41 printBlocks();
42 assert(!constraintGraphIsCyclic(n,vs));
43 #endif
44 }
45 VPSC::~VPSC() {
46 delete bs;
47 }
49 // useful in debugging
50 void VPSC::printBlocks() {
51 #ifdef RECTANGLE_OVERLAP_LOGGING
52 ofstream f(LOGFILE,ios::app);
53 for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
54 Block *b=*i;
55 f<<" "<<*b<<endl;
56 }
57 for(unsigned i=0;i<m;i++) {
58 f<<" "<<*cs[i]<<endl;
59 }
60 #endif
61 }
62 /**
63 * Produces a feasible - though not necessarily optimal - solution by
64 * examining blocks in the partial order defined by the directed acyclic
65 * graph of constraints. For each block (when processing left to right) we
66 * maintain the invariant that all constraints to the left of the block
67 * (incoming constraints) are satisfied. This is done by repeatedly merging
68 * blocks into bigger blocks across violated constraints (most violated
69 * first) fixing the position of variables inside blocks relative to one
70 * another so that constraints internal to the block are satisfied.
71 */
72 void VPSC::satisfy() {
73 list<Variable*> *vs=bs->totalOrder();
74 for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) {
75 Variable *v=*i;
76 if(!v->block->deleted) {
77 bs->mergeLeft(v->block);
78 }
79 }
80 bs->cleanup();
81 for(unsigned i=0;i<m;i++) {
82 if(cs[i]->slack()<-0.0000001) {
83 #ifdef RECTANGLE_OVERLAP_LOGGING
84 ofstream f(LOGFILE,ios::app);
85 f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
86 #endif
87 //assert(cs[i]->slack()>-0.0000001);
88 throw "Unsatisfied constraint";
89 }
90 }
91 delete vs;
92 }
94 void VPSC::refine() {
95 bool solved=false;
96 // Solve shouldn't loop indefinately
97 // ... but just to make sure we limit the number of iterations
98 unsigned maxtries=100;
99 while(!solved&&maxtries>0) {
100 solved=true;
101 maxtries--;
102 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
103 Block *b=*i;
104 b->setUpInConstraints();
105 b->setUpOutConstraints();
106 }
107 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
108 Block *b=*i;
109 Constraint *c=b->findMinLM();
110 if(c!=NULL && c->lm<0) {
111 #ifdef RECTANGLE_OVERLAP_LOGGING
112 ofstream f(LOGFILE,ios::app);
113 f<<"Split on constraint: "<<*c<<endl;
114 #endif
115 // Split on c
116 Block *l=NULL, *r=NULL;
117 bs->split(b,l,r,c);
118 bs->cleanup();
119 // split alters the block set so we have to restart
120 solved=false;
121 break;
122 }
123 }
124 }
125 for(unsigned i=0;i<m;i++) {
126 if(cs[i]->slack()<-0.0000001) {
127 assert(cs[i]->slack()>-0.0000001);
128 throw "Unsatisfied constraint";
129 }
130 }
131 }
132 /**
133 * Calculate the optimal solution. After using satisfy() to produce a
134 * feasible solution, refine() examines each block to see if further
135 * refinement is possible by splitting the block. This is done repeatedly
136 * until no further improvement is possible.
137 */
138 void VPSC::solve() {
139 satisfy();
140 refine();
141 }
143 void IncVPSC::solve() {
144 #ifdef RECTANGLE_OVERLAP_LOGGING
145 ofstream f(LOGFILE,ios::app);
146 f<<"solve_inc()..."<<endl;
147 #endif
148 double lastcost,cost = bs->cost();
149 do {
150 lastcost=cost;
151 satisfy();
152 splitBlocks();
153 cost = bs->cost();
154 #ifdef RECTANGLE_OVERLAP_LOGGING
155 f<<" cost="<<cost<<endl;
156 #endif
157 } while(fabs(lastcost-cost)>0.0001);
158 }
159 /**
160 * incremental version of satisfy that allows refinement after blocks are
161 * moved.
162 *
163 * - move blocks to new positions
164 * - repeatedly merge across most violated constraint until no more
165 * violated constraints exist
166 *
167 * Note: there is a special case to handle when the most violated constraint
168 * is between two variables in the same block. Then, we must split the block
169 * over an active constraint between the two variables. We choose the
170 * constraint with the most negative lagrangian multiplier.
171 */
172 void IncVPSC::satisfy() {
173 #ifdef RECTANGLE_OVERLAP_LOGGING
174 ofstream f(LOGFILE,ios::app);
175 f<<"satisfy_inc()..."<<endl;
176 #endif
177 splitBlocks();
178 long splitCtr = 0;
179 Constraint* v = NULL;
180 while((v=mostViolated(inactive))&&(v->equality || v->slack()<-0.000001)) {
181 assert(!v->active);
182 Block *lb = v->left->block, *rb = v->right->block;
183 if(lb != rb) {
184 lb->merge(rb,v);
185 } else {
186 if(splitCtr++>10000) {
187 throw "Cycle Error!";
188 }
189 // constraint is within block, need to split first
190 inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb));
191 lb->merge(rb,v);
192 bs->insert(lb);
193 }
194 }
195 #ifdef RECTANGLE_OVERLAP_LOGGING
196 f<<" finished merges."<<endl;
197 #endif
198 bs->cleanup();
199 for(unsigned i=0;i<m;i++) {
200 v=cs[i];
201 if(v->slack()<-0.0000001) {
202 //assert(cs[i]->slack()>-0.0000001);
203 ostringstream s;
204 s<<"Unsatisfied constraint: "<<*v;
205 throw s.str().c_str();
206 }
207 }
208 #ifdef RECTANGLE_OVERLAP_LOGGING
209 f<<" finished cleanup."<<endl;
210 printBlocks();
211 #endif
212 }
213 void IncVPSC::moveBlocks() {
214 #ifdef RECTANGLE_OVERLAP_LOGGING
215 ofstream f(LOGFILE,ios::app);
216 f<<"moveBlocks()..."<<endl;
217 #endif
218 for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
219 Block *b = *i;
220 b->wposn = b->desiredWeightedPosition();
221 b->posn = b->wposn / b->weight;
222 }
223 #ifdef RECTANGLE_OVERLAP_LOGGING
224 f<<" moved blocks."<<endl;
225 #endif
226 }
227 void IncVPSC::splitBlocks() {
228 #ifdef RECTANGLE_OVERLAP_LOGGING
229 ofstream f(LOGFILE,ios::app);
230 #endif
231 moveBlocks();
232 splitCnt=0;
233 // Split each block if necessary on min LM
234 for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
235 Block* b = *i;
236 Constraint* v=b->findMinLM();
237 if(v!=NULL && v->lm < -0.0000001) {
238 assert(!v->equality);
239 #ifdef RECTANGLE_OVERLAP_LOGGING
240 f<<" found split point: "<<*v<<" lm="<<v->lm<<endl;
241 #endif
242 splitCnt++;
243 Block *b = v->left->block, *l=NULL, *r=NULL;
244 assert(v->left->block == v->right->block);
245 double pos = b->posn;
246 b->split(l,r,v);
247 l->posn=r->posn=pos;
248 l->wposn = l->posn * l->weight;
249 r->wposn = r->posn * r->weight;
250 bs->insert(l);
251 bs->insert(r);
252 b->deleted=true;
253 inactive.push_back(v);
254 #ifdef RECTANGLE_OVERLAP_LOGGING
255 f<<" new blocks: "<<*l<<" and "<<*r<<endl;
256 #endif
257 }
258 }
259 #ifdef RECTANGLE_OVERLAP_LOGGING
260 f<<" finished splits."<<endl;
261 #endif
262 bs->cleanup();
263 }
265 /**
266 * Scan constraint list for the most violated constraint, or the first equality
267 * constraint
268 */
269 Constraint* IncVPSC::mostViolated(ConstraintList &l) {
270 double minSlack = DBL_MAX;
271 Constraint* v=NULL;
272 #ifdef RECTANGLE_OVERLAP_LOGGING
273 ofstream f(LOGFILE,ios::app);
274 f<<"Looking for most violated..."<<endl;
275 #endif
276 ConstraintList::iterator end = l.end();
277 ConstraintList::iterator deletePoint = end;
278 for(ConstraintList::iterator i=l.begin();i!=end;++i) {
279 Constraint *c=*i;
280 double slack = c->slack();
281 if(c->equality || slack < minSlack) {
282 minSlack=slack;
283 v=c;
284 deletePoint=i;
285 if(c->equality) break;
286 }
287 }
288 // Because the constraint list is not order dependent we just
289 // move the last element over the deletePoint and resize
290 // downwards. There is always at least 1 element in the
291 // vector because of search.
292 if(deletePoint != end && (minSlack<-0.0000001||v->equality)) {
293 *deletePoint = l[l.size()-1];
294 l.resize(l.size()-1);
295 }
296 #ifdef RECTANGLE_OVERLAP_LOGGING
297 f<<" most violated is: "<<*v<<endl;
298 #endif
299 return v;
300 }
302 #include <map>
303 using std::map;
304 using std::vector;
305 struct node {
306 set<node*> in;
307 set<node*> out;
308 };
309 // useful in debugging - cycles would be BAD
310 bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
311 map<Variable*, node*> varmap;
312 vector<node*> graph;
313 for(unsigned i=0;i<n;i++) {
314 node *u=new node;
315 graph.push_back(u);
316 varmap[vs[i]]=u;
317 }
318 for(unsigned i=0;i<n;i++) {
319 for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) {
320 Variable *l=(*c)->left;
321 varmap[vs[i]]->in.insert(varmap[l]);
322 }
324 for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) {
325 Variable *r=(*c)->right;
326 varmap[vs[i]]->out.insert(varmap[r]);
327 }
328 }
329 while(graph.size()>0) {
330 node *u=NULL;
331 vector<node*>::iterator i=graph.begin();
332 for(;i!=graph.end();++i) {
333 u=*i;
334 if(u->in.size()==0) {
335 break;
336 }
337 }
338 if(i==graph.end() && graph.size()>0) {
339 //cycle found!
340 return true;
341 } else {
342 graph.erase(i);
343 for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
344 node *v=*j;
345 v->in.erase(u);
346 }
347 delete u;
348 }
349 }
350 for(unsigned i=0; i<graph.size(); ++i) {
351 delete graph[i];
352 }
353 return false;
354 }
356 // useful in debugging - cycles would be BAD
357 bool VPSC::blockGraphIsCyclic() {
358 map<Block*, node*> bmap;
359 vector<node*> graph;
360 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
361 Block *b=*i;
362 node *u=new node;
363 graph.push_back(u);
364 bmap[b]=u;
365 }
366 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
367 Block *b=*i;
368 b->setUpInConstraints();
369 Constraint *c=b->findMinInConstraint();
370 while(c!=NULL) {
371 Block *l=c->left->block;
372 bmap[b]->in.insert(bmap[l]);
373 b->deleteMinInConstraint();
374 c=b->findMinInConstraint();
375 }
377 b->setUpOutConstraints();
378 c=b->findMinOutConstraint();
379 while(c!=NULL) {
380 Block *r=c->right->block;
381 bmap[b]->out.insert(bmap[r]);
382 b->deleteMinOutConstraint();
383 c=b->findMinOutConstraint();
384 }
385 }
386 while(graph.size()>0) {
387 node *u=NULL;
388 vector<node*>::iterator i=graph.begin();
389 for(;i!=graph.end();++i) {
390 u=*i;
391 if(u->in.size()==0) {
392 break;
393 }
394 }
395 if(i==graph.end() && graph.size()>0) {
396 //cycle found!
397 return true;
398 } else {
399 graph.erase(i);
400 for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
401 node *v=*j;
402 v->in.erase(u);
403 }
404 delete u;
405 }
406 }
407 for(unsigned i=0; i<graph.size(); i++) {
408 delete graph[i];
409 }
410 return false;
411 }