33using std::ostringstream;
37#ifndef RECTANGLE_OVERLAP_LOGGING
38 #define RECTANGLE_OVERLAP_LOGGING 0
43 :
VPSC(n, vs, m_, cs_) {
44 inactive.assign(cs_, cs_ + m_);
52 : bs(n, vs), cs(cs_), m(m_) {
55 assert(!constraintGraphIsCyclic(n,vs));
66 for(
unsigned i=0;i<
m;i++) {
84 if(!v->block->deleted) {
89 for(
unsigned i=0;i<
m;i++) {
90 if(
cs[i]->slack()<-0.0000001) {
93 f<<
"Error: Unsatisfied constraint: "<<*
cs[i]<<
"\n";
96 throw std::runtime_error(
"Unsatisfied constraint");
102 for (
bool solved =
false; !solved;) {
105 b->setUpInConstraints();
106 b->setUpOutConstraints();
110 if(c!=
nullptr && c->
lm<0) {
113 f<<
"Split on constraint: "<<*c<<
"\n";
116 Block *l=
nullptr, *r=
nullptr;
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");
146 f<<
"solve_inc()...\n";
148 double lastcost,cost =
bs.
cost();
156 f<<
" cost="<<cost<<
"\n";
158 }
while(fabs(lastcost-cost)>0.0001);
176 f<<
"satisfy_inc()...\n";
181 while(mostViolated(inactive,v)<-0.0000001) {
187 if(splitCtr++>10000) {
188 throw std::runtime_error(
"Cycle Error!");
198 f<<
" finished merges.\n";
201 for(
unsigned i=0;i<
m;i++) {
203 if(v->
slack()<-0.0000001) {
206 s<<
"Unsatisfied constraint: "<<*v;
207 throw std::runtime_error(
s.str());
212 f<<
" finished cleanup.\n";
219 f<<
"moveBlocks()...\n";
222 b->wposn = b->desiredWeightedPosition();
223 b->posn = b->wposn / b->weight;
227 f<<
" moved blocks.\n";
236 if(v!=
nullptr && v->
lm < -0.0000001) {
239 f<<
" found split point: "<<*v<<
" lm="<<v->
lm<<
"\n";
244 double pos = b2->
posn;
247 l->wposn = l->posn * l->weight;
248 r->wposn = r->posn * r->weight;
252 inactive.push_back(v);
255 f<<
" new blocks: "<<*l<<
" and "<<*r<<
"\n";
261 f<<
" finished splits.\n";
270double IncVPSC::mostViolated(ConstraintList &l,
Constraint* &v) {
271 double minSlack = DBL_MAX;
274 f<<
"Looking for most violated...\n";
276 ConstraintList::iterator end = l.end();
277 ConstraintList::iterator deletePoint = end;
278 for(ConstraintList::iterator i=l.begin();i!=end;i++) {
280 double slack = c->
slack();
281 if (slack < minSlack) {
291 if(deletePoint != end && minSlack<-0.0000001) {
292 *deletePoint = l[l.size()-1];
293 l.resize(l.size()-1);
297 f<<
" most violated is: "<<*v<<
"\n";
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++) {
315 varmap[vs[i]]=
graph.back().get();
317 for(
unsigned i=0;i<n;i++) {
320 varmap[vs[i]]->
in.insert(varmap[l]);
325 varmap[vs[i]]->
out.insert(varmap[r]);
328 while(!
graph.empty()) {
330 vector<std::unique_ptr<node>>::iterator i=
graph.begin();
331 for(;i!=
graph.end();i++) {
351bool VPSC::blockGraphIsCyclic() {
352 map<Block*, node*> bmap;
353 vector<std::unique_ptr<node>>
graph;
356 bmap[b]=
graph.back().get();
359 b->setUpInConstraints();
363 bmap[b]->
in.insert(bmap[l]);
364 b->deleteMinInConstraint();
365 c=b->findMinInConstraint();
368 b->setUpOutConstraints();
369 c=b->findMinOutConstraint();
372 bmap[b]->
out.insert(bmap[r]);
373 b->deleteMinOutConstraint();
374 c=b->findMinOutConstraint();
377 while(!
graph.empty()) {
379 vector<std::unique_ptr<node>>::iterator i=
graph.begin();
380 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.
std::vector< Constraint * > out
void split(Block *&l, Block *&r, Constraint *c)
Constraint * splitBetween(Variable *vl, Variable *vr, Block *&lb, Block *&rb)
std::vector< Constraint * > in
void merge(Block *b, Constraint *c, double dist)
void split(Block *b, Block *&l, Block *&r, Constraint *c)
std::list< Variable * > totalOrder()
static int in(Extype_t lhs, Exid_t *rhs, Exdisc_t *disc)
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[])