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