1 /**
2 * \brief Remove overlaps function
3 *
4 * Authors:
5 * Tim Dwyer <tgdwyer@gmail.com>
6 *
7 * Copyright (C) 2005 Authors
8 *
9 * Released under GNU GPL. Read the file 'COPYING' for more information.
10 */
12 #include <cassert>
13 #include "constraint.h"
14 #include "block.h"
15 #include "blocks.h"
16 #include "solve_VPSC.h"
17 #ifdef RECTANGLE_OVERLAP_LOGGING
18 #include <fstream>
19 using std::ios;
20 using std::ofstream;
21 using std::endl;
22 #endif
24 using std::list;
25 using std::set;
27 VPSC::VPSC(Variable *vs[], const int n, Constraint *cs[], const int m) : cs(cs), m(m) {
28 //assert(!constraintGraphIsCyclic(vs,n));
29 bs=new Blocks(vs,n);
30 #ifdef RECTANGLE_OVERLAP_LOGGING
31 printBlocks();
32 #endif
33 }
34 VPSC::~VPSC() {
35 delete bs;
36 }
38 // useful in debugging
39 void VPSC::printBlocks() {
40 #ifdef RECTANGLE_OVERLAP_LOGGING
41 ofstream f(LOGFILE,ios::app);
42 for(set<Block*>::iterator i=bs->begin();i!=bs->end();i++) {
43 Block *b=*i;
44 f<<" "<<*b<<endl;
45 }
46 for(int i=0;i<m;i++) {
47 f<<" "<<*cs[i]<<endl;
48 }
49 #endif
50 }
51 /**
52 * Produces a feasible - though not necessarily optimal - solution by
53 * examining blocks in the partial order defined by the directed acyclic
54 * graph of constraints. For each block (when processing left to right) we
55 * maintain the invariant that all constraints to the left of the block
56 * (incoming constraints) are satisfied. This is done by repeatedly merging
57 * blocks into bigger blocks across violated constraints (most violated
58 * first) fixing the position of variables inside blocks relative to one
59 * another so that constraints internal to the block are satisfied.
60 */
61 void VPSC::satisfy() {
62 list<Variable*> *vs=bs->totalOrder();
63 for(list<Variable*>::iterator i=vs->begin();i!=vs->end();i++) {
64 Variable *v=*i;
65 if(!v->block->deleted) {
66 bs->mergeLeft(v->block);
67 }
68 }
69 bs->cleanup();
70 for(int i=0;i<m;i++) {
71 if(cs[i]->slack()<-0.0000001) {
72 #ifdef RECTANGLE_OVERLAP_LOGGING
73 ofstream f(LOGFILE,ios::app);
74 f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
75 #endif
76 //assert(cs[i]->slack()>-0.0000001);
77 throw "Unsatisfied constraint";
78 }
79 }
80 delete vs;
81 }
83 void VPSC::refine() {
84 bool solved=false;
85 // Solve shouldn't loop indefinately
86 // ... but just to make sure we limit the number of iterations
87 int maxtries=100;
88 while(!solved&&maxtries>=0) {
89 solved=true;
90 maxtries--;
91 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
92 Block *b=*i;
93 b->setUpInConstraints();
94 b->setUpOutConstraints();
95 }
96 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
97 Block *b=*i;
98 Constraint *c=b->findMinLM();
99 if(c!=NULL && c->lm<0) {
100 #ifdef RECTANGLE_OVERLAP_LOGGING
101 ofstream f(LOGFILE,ios::app);
102 f<<"Split on constraint: "<<*c<<endl;
103 #endif
104 // Split on c
105 Block *l=NULL, *r=NULL;
106 bs->split(b,l,r,c);
107 bs->cleanup();
108 // split alters the block set so we have to restart
109 solved=false;
110 break;
111 }
112 }
113 }
114 for(int i=0;i<m;i++) {
115 if(cs[i]->slack()<-0.0000001) {
116 assert(cs[i]->slack()>-0.0000001);
117 throw "Unsatisfied constraint";
118 }
119 }
120 }
121 /**
122 * Calculate the optimal solution. After using satisfy() to produce a
123 * feasible solution, refine() examines each block to see if further
124 * refinement is possible by splitting the block. This is done repeatedly
125 * until no further improvement is possible.
126 */
127 void VPSC::solve() {
128 satisfy();
129 refine();
130 }
132 /**
133 * incremental version of solve that should allow refinement after blocks are
134 * moved. Work in progress.
135 */
136 void VPSC::move_and_split() {
137 //assert(!blockGraphIsCyclic());
138 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
139 Block *b=*i;
140 if(!b->deleted) {
141 b->wposn = b->desiredWeightedPosition();
142 b->posn = b->wposn / b->weight;
143 Variable *v=b->vars->front();
144 bs->mergeLeft(b);
145 // b may be merged away, so get any new block from one of its members
146 bs->mergeRight(v->block);
147 }
148 }
149 bs->cleanup();
150 // assert(!blockGraphIsCyclic());
151 refine();
152 }
154 #include <map>
155 using std::map;
156 using std::vector;
157 struct node {
158 set<node*> in;
159 set<node*> out;
160 };
161 /*
162 // useful in debugging - cycles would be BAD
163 bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) {
164 map<Variable*, node*> varmap;
165 vector<node*> graph;
166 for(int i=0;i<n;i++) {
167 node *u=new node;
168 graph.push_back(u);
169 varmap[vs[i]]=u;
170 }
171 for(int i=0;i<n;i++) {
172 for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();c++) {
173 Variable *l=(*c)->left;
174 varmap[vs[i]]->in.insert(varmap[l]);
175 }
177 for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();c++) {
178 Variable *r=(*c)->right;
179 varmap[vs[i]]->out.insert(varmap[r]);
180 }
181 }
182 while(graph.size()>0) {
183 node *u=NULL;
184 vector<node*>::iterator i=graph.begin();
185 for(;i!=graph.end();i++) {
186 u=*i;
187 if(u->in.size()==0) {
188 break;
189 }
190 }
191 if(i==graph.end() && graph.size()>0) {
192 //cycle found!
193 return true;
194 } else {
195 graph.erase(i);
196 for(set<node*>::iterator j=u->out.begin();j!=u->out.end();j++) {
197 node *v=*j;
198 v->in.erase(u);
199 }
200 delete u;
201 }
202 }
203 for(unsigned i=0; i<graph.size(); i++) {
204 delete graph[i];
205 }
206 return false;
207 }
209 // useful in debugging - cycles would be BAD
210 bool VPSC::blockGraphIsCyclic() {
211 map<Block*, node*> bmap;
212 vector<node*> graph;
213 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
214 Block *b=*i;
215 node *u=new node;
216 graph.push_back(u);
217 bmap[b]=u;
218 }
219 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
220 Block *b=*i;
221 b->setUpInConstraints();
222 Constraint *c=b->findMinInConstraint();
223 while(c!=NULL) {
224 Block *l=c->left->block;
225 bmap[b]->in.insert(bmap[l]);
226 b->deleteMinInConstraint();
227 c=b->findMinInConstraint();
228 }
230 b->setUpOutConstraints();
231 c=b->findMinOutConstraint();
232 while(c!=NULL) {
233 Block *r=c->right->block;
234 bmap[b]->out.insert(bmap[r]);
235 b->deleteMinOutConstraint();
236 c=b->findMinOutConstraint();
237 }
238 }
239 while(graph.size()>0) {
240 node *u=NULL;
241 vector<node*>::iterator i=graph.begin();
242 for(;i!=graph.end();i++) {
243 u=*i;
244 if(u->in.size()==0) {
245 break;
246 }
247 }
248 if(i==graph.end() && graph.size()>0) {
249 //cycle found!
250 return true;
251 } else {
252 graph.erase(i);
253 for(set<node*>::iterator j=u->out.begin();j!=u->out.end();j++) {
254 node *v=*j;
255 v->in.erase(u);
256 }
257 delete u;
258 }
259 }
260 for(unsigned i=0; i<graph.size(); i++) {
261 delete graph[i];
262 }
263 return false;
264 }
265 */