Graphviz 13.0.0~dev.20250511.0440
Loading...
Searching...
No Matches
solve_VPSC.cpp
Go to the documentation of this file.
1
20#include <cassert>
21#include <vpsc/constraint.h>
22#include <vpsc/block.h>
23#include <vpsc/blocks.h>
24#include <vpsc/solve_VPSC.h>
25#include <math.h>
26#include <memory>
27#include <sstream>
28#include <fstream>
29#include <stdexcept>
30using std::ios;
31using std::ofstream;
32
33using std::ostringstream;
34using std::list;
35using std::set;
36
37#ifndef RECTANGLE_OVERLAP_LOGGING
38 #define RECTANGLE_OVERLAP_LOGGING 0
39#endif
40
41IncVPSC::IncVPSC(const unsigned n, Variable *vs[], const unsigned m_,
42 Constraint *cs_[])
43 : VPSC(n, vs, m_, cs_) {
44 inactive.assign(cs_, cs_ + m_);
45 for(Constraint *c : inactive) {
46 c->active=false;
47 }
48}
49
50VPSC::VPSC(const unsigned n, Variable *vs[], const unsigned m_,
51 Constraint *cs_[])
52 : bs(n, vs), cs(cs_), m(m_) {
55 assert(!constraintGraphIsCyclic(n,vs));
56 }
57}
58
59// useful in debugging
62 ofstream f(LOGFILE,ios::app);
63 for(Block *b : bs) {
64 f<<" "<<*b<<"\n";
65 }
66 for(unsigned i=0;i<m;i++) {
67 f<<" "<<*cs[i]<<"\n";
68 }
69 }
70}
82 list<Variable*> vs=bs.totalOrder();
83 for(Variable *v : vs) {
84 if(!v->block->deleted) {
85 bs.mergeLeft(v->block);
86 }
87 }
88 bs.cleanup();
89 for(unsigned i=0;i<m;i++) {
90 if(cs[i]->slack()<-0.0000001) {
92 ofstream f(LOGFILE,ios::app);
93 f<<"Error: Unsatisfied constraint: "<<*cs[i]<<"\n";
94 }
95 //assert(cs[i]->slack()>-0.0000001);
96 throw std::runtime_error("Unsatisfied constraint");
97 }
98 }
99}
100
101void VPSC::refine() {
102 for (bool solved = false; !solved;) {
103 solved=true;
104 for(Block *b : bs) {
105 b->setUpInConstraints();
106 b->setUpOutConstraints();
107 }
108 for(Block *b : bs) {
109 Constraint *c=b->findMinLM();
110 if(c!=nullptr && c->lm<0) {
112 ofstream f(LOGFILE,ios::app);
113 f<<"Split on constraint: "<<*c<<"\n";
114 }
115 // Split on c
116 Block *l=nullptr, *r=nullptr;
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 std::runtime_error("Unsatisfied constraint");
129 }
130 }
131}
139 satisfy();
140 refine();
141}
142
145 ofstream f(LOGFILE,ios::app);
146 f<<"solve_inc()...\n";
147 }
148 double lastcost,cost = bs.cost();
149 do {
150 lastcost=cost;
151 satisfy();
152 splitBlocks();
153 cost = bs.cost();
155 ofstream f(LOGFILE,ios::app);
156 f<<" cost="<<cost<<"\n";
157 }
158 } while(fabs(lastcost-cost)>0.0001);
159}
175 ofstream f(LOGFILE,ios::app);
176 f<<"satisfy_inc()...\n";
177 }
178 splitBlocks();
179 long splitCtr = 0;
180 Constraint* v = nullptr;
181 while(mostViolated(inactive,v)<-0.0000001) {
182 assert(!v->active);
183 Block *lb = v->left->block, *rb = v->right->block;
184 if(lb != rb) {
185 lb->merge(rb,v);
186 } else {
187 if(splitCtr++>10000) {
188 throw std::runtime_error("Cycle Error!");
189 }
190 // constraint is within block, need to split first
191 inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb));
192 lb->merge(rb,v);
193 bs.insert(lb);
194 }
195 }
197 ofstream f(LOGFILE,ios::app);
198 f<<" finished merges.\n";
199 }
200 bs.cleanup();
201 for(unsigned i=0;i<m;i++) {
202 v=cs[i];
203 if(v->slack()<-0.0000001) {
204 //assert(cs[i]->slack()>-0.0000001);
205 ostringstream s;
206 s<<"Unsatisfied constraint: "<<*v;
207 throw std::runtime_error(s.str());
208 }
209 }
211 ofstream f(LOGFILE,ios::app);
212 f<<" finished cleanup.\n";
213 printBlocks();
214 }
215}
218 ofstream f(LOGFILE,ios::app);
219 f<<"moveBlocks()...\n";
220 }
221 for(Block *b : bs) {
222 b->wposn = b->desiredWeightedPosition();
223 b->posn = b->wposn / b->weight;
224 }
226 ofstream f(LOGFILE,ios::app);
227 f<<" moved blocks.\n";
228 }
229}
231 moveBlocks();
232 splitCnt=0;
233 // Split each block if necessary on min LM
234 for(Block *b : bs) {
235 Constraint* v=b->findMinLM();
236 if(v!=nullptr && v->lm < -0.0000001) {
238 ofstream f(LOGFILE,ios::app);
239 f<<" found split point: "<<*v<<" lm="<<v->lm<<"\n";
240 }
241 splitCnt++;
242 Block *b2 = v->left->block, *l=nullptr, *r=nullptr;
243 assert(v->left->block == v->right->block);
244 double pos = b2->posn;
245 b2->split(l,r,v);
246 l->posn=r->posn=pos;
247 l->wposn = l->posn * l->weight;
248 r->wposn = r->posn * r->weight;
249 bs.insert(l);
250 bs.insert(r);
251 b2->deleted=true;
252 inactive.push_back(v);
254 ofstream f(LOGFILE,ios::app);
255 f<<" new blocks: "<<*l<<" and "<<*r<<"\n";
256 }
257 }
258 }
260 ofstream f(LOGFILE,ios::app);
261 f<<" finished splits.\n";
262 }
263 bs.cleanup();
264}
265
270double IncVPSC::mostViolated(ConstraintList &l, Constraint* &v) {
271 double minSlack = DBL_MAX;
273 ofstream f(LOGFILE,ios::app);
274 f<<"Looking for most violated...\n";
275 }
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 (slack < minSlack) {
282 minSlack=slack;
283 v=c;
284 deletePoint=i;
285 }
286 }
287 // Because the constraint list is not order dependent we just
288 // move the last element over the deletePoint and resize
289 // downwards. There is always at least 1 element in the
290 // vector because of search.
291 if(deletePoint != end && minSlack<-0.0000001) {
292 *deletePoint = l[l.size()-1];
293 l.resize(l.size()-1);
294 }
296 ofstream f(LOGFILE,ios::app);
297 f<<" most violated is: "<<*v<<"\n";
298 }
299 return minSlack;
300}
301
302#include <map>
303using std::map;
304using std::vector;
305struct node {
306 set<node*> in;
307 set<node*> out;
308};
309// useful in debugging - cycles would be BAD
310bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
311 map<Variable*, node*> varmap;
312 vector<std::unique_ptr<node>> graph;
313 for(unsigned i=0;i<n;i++) {
314 graph.emplace_back(new node);
315 varmap[vs[i]]=graph.back().get();
316 }
317 for(unsigned i=0;i<n;i++) {
318 for(Constraint *c : vs[i]->in) {
319 Variable *l=c->left;
320 varmap[vs[i]]->in.insert(varmap[l]);
321 }
322
323 for(Constraint *c : vs[i]->out) {
324 Variable *r=c->right;
325 varmap[vs[i]]->out.insert(varmap[r]);
326 }
327 }
328 while(!graph.empty()) {
329 node *u=nullptr;
330 vector<std::unique_ptr<node>>::iterator i=graph.begin();
331 for(;i!=graph.end();i++) {
332 u=(*i).get();
333 if(u->in.empty()) {
334 break;
335 }
336 }
337 if(i==graph.end()) {
338 //cycle found!
339 return true;
340 } else {
341 graph.erase(i);
342 for(node *v : u->out) {
343 v->in.erase(u);
344 }
345 }
346 }
347 return false;
348}
349
350// useful in debugging - cycles would be BAD
351bool VPSC::blockGraphIsCyclic() {
352 map<Block*, node*> bmap;
353 vector<std::unique_ptr<node>> graph;
354 for(Block *b : bs) {
355 graph.emplace_back(new node);
356 bmap[b]=graph.back().get();
357 }
358 for(Block *b : bs) {
359 b->setUpInConstraints();
360 Constraint *c=b->findMinInConstraint();
361 while(c!=nullptr) {
362 Block *l=c->left->block;
363 bmap[b]->in.insert(bmap[l]);
364 b->deleteMinInConstraint();
365 c=b->findMinInConstraint();
366 }
367
368 b->setUpOutConstraints();
369 c=b->findMinOutConstraint();
370 while(c!=nullptr) {
371 Block *r=c->right->block;
372 bmap[b]->out.insert(bmap[r]);
373 b->deleteMinOutConstraint();
374 c=b->findMinOutConstraint();
375 }
376 }
377 while(!graph.empty()) {
378 node *u=nullptr;
379 vector<std::unique_ptr<node>>::iterator i=graph.begin();
380 for(;i!=graph.end();i++) {
381 u=(*i).get();
382 if(u->in.empty()) {
383 break;
384 }
385 }
386 if(i==graph.end()) {
387 //cycle found!
388 return true;
389 }
390 graph.erase(i);
391 for(node *v : u->out) {
392 v->in.erase(u);
393 }
394 }
395 return false;
396}
static void out(agerrlevel_t level, const char *fmt, va_list args)
Report messages using a user-supplied or default write function.
Definition agerror.c:84
#define RECTANGLE_OVERLAP_LOGGING
Definition block.cpp:33
#define LOGFILE
A block structure defined over the variables.
Definition blocks.h:24
Definition block.h:28
std::vector< Constraint * > out
Definition block.h:56
bool deleted
Definition block.h:53
void split(Block *&l, Block *&r, Constraint *c)
Definition block.cpp:396
double posn
Definition block.h:32
Constraint * splitBetween(Variable *vl, Variable *vr, Block *&lb, Block *&rb)
Definition block.cpp:377
std::vector< Constraint * > in
Definition block.h:55
void merge(Block *b, Constraint *c, double dist)
Definition block.cpp:146
void cleanup()
Definition blocks.cpp:156
double cost()
Definition blocks.cpp:195
void split(Block *b, Block *&l, Block *&r, Constraint *c)
Definition blocks.cpp:171
std::list< Variable * > totalOrder()
Definition blocks.cpp:55
void mergeLeft(Block *r)
Definition blocks.cpp:86
static int in(Extype_t lhs, Exid_t *rhs, Exdisc_t *disc)
Definition compile.c:1678
Agraph_t * graph(char *name)
Definition gv.cpp:30
A constraint determines a minimum or exact spacing required between two variables.
Definition constraint.h:25
Variable * right
Definition constraint.h:29
double lm
Definition constraint.h:31
Variable * left
Definition constraint.h:28
bool active
Definition constraint.h:36
double slack() const
Definition constraint.h:34
void satisfy()
IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[])
void moveBlocks()
unsigned splitCnt
Definition solve_VPSC.h:49
void solve()
void splitBlocks()
void printBlocks()
VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[])
virtual void solve()
virtual void satisfy()
Constraint ** cs
Definition solve_VPSC.h:38
Blocks bs
Definition solve_VPSC.h:37
unsigned m
Definition solve_VPSC.h:39
Constraints out
Definition variable.h:36
Block * block
Definition variable.h:33
Constraints in
Definition variable.h:35
set< node * > out
set< node * > in
Definition grammar.c:93