3 // Cassowary Incremental Constraint Solver
4 // Original Smalltalk Implementation by Alan Borning
5 // This C++ Implementation by Greg J. Badros, <gjb@cs.washington.edu>
6 // http://www.cs.washington.edu/homes/gjb
7 // (C) 1998, 1999 Greg J. Badros and Alan Borning
8 // See ../LICENSE for legal details regarding this software
12 #include <cassowary/Cl.h>
14 #include <cassowary/timer.h>
19 double UniformRandom()
20 { return double(rand())/RAND_MAX; }
28 bool fOkResult = true;
31 ClSimplexSolver solver;
33 ClLinearEquation eq(x,y+0.0);
36 solver.AddConstraint(eq);
37 cout << "x = " << x.Value() << endl
38 << "y = " << y.Value() << endl;
39 fOkResult = (x.Value() == y.Value());
42 catch (ExCLError &error)
44 cerr << "Exception! " << error.description() << endl;
49 cerr << "Unknown exception" << endl;
55 /* Add an edit variable to an empty solver */
62 ClSimplexSolver solver;
66 solver.SuggestValue(x,100);
69 cout << "x = " << x.Value() << endl;
71 catch (ExCLEditMisuse &error)
73 cout << "Success: got the exception" << endl;
76 catch (ExCLError &error)
78 cerr << "Exception! " << error.description() << endl;
83 cerr << "Unknown exception" << endl;
86 cerr << "Should have gotten an exception!" << endl;
96 bool fOkResult = true;
99 ClSimplexSolver solver;
102 solver.AddPointStay(x,y,1);
107 fOkResult = fOkResult && ClApprox(x,5);
108 fOkResult = fOkResult && ClApprox(y,10);
109 cout << "x == " << x.Value() << endl;
110 cout << "y == " << y.Value() << endl;
114 catch (ExCLError &error)
116 cerr << "Exception! " << error.description() << endl;
121 cerr << "Unknown exception" << endl;
133 bool fOkResult = true;
135 ClSimplexSolver solver;
137 solver.AddConstraint(new ClLinearEquation( x, 100, ClsWeak() ));
139 ClLinearInequality c10(x,cnLEQ,10.0);
140 ClLinearInequality c20(x,cnLEQ,20.0);
145 fOkResult = fOkResult && ClApprox(x,10.0);
146 cout << "x == " << x.Value() << endl;
148 cout << endl << solver << endl;
150 solver.RemoveConstraint(c10);
152 cout << endl << solver << endl;
154 fOkResult = fOkResult && ClApprox(x,20.0);
155 cout << "x == " << x.Value() << endl;
157 solver.RemoveConstraint(c20);
158 fOkResult = fOkResult && ClApprox(x,100.0);
159 cout << "x == " << x.Value() << endl;
161 ClLinearInequality c10again(x,cnLEQ,10.0);
165 .AddConstraint(c10again);
167 fOkResult = fOkResult && ClApprox(x,10.0);
168 cout << "x == " << x.Value() << endl;
170 solver.RemoveConstraint(c10);
171 fOkResult = fOkResult && ClApprox(x,10.0);
172 cout << "x == " << x.Value() << endl;
174 solver.RemoveConstraint(c10again);
175 fOkResult = fOkResult && ClApprox(x,100.0);
176 cout << "x == " << x.Value() << endl;
180 catch (ExCLError &error)
182 cerr << "Exception! " << error.description() << endl;
187 cerr << "Unknown exception" << endl;
197 bool fOkResult = true;
200 ClSimplexSolver solver;
203 .AddConstraint(new ClLinearEquation(x, 100.0, ClsWeak()))
204 .AddConstraint(new ClLinearEquation(y, 120.0, ClsStrong()));
206 ClLinearInequality c10(x,cnLEQ,10.0);
207 ClLinearInequality c20(x,cnLEQ,20.0);
212 fOkResult = fOkResult && ClApprox(x,10.0) && ClApprox(y,120.0);
213 cout << "x == " << x.Value() << ", y == " << y.Value() << endl;
215 solver.RemoveConstraint(c10);
216 fOkResult = fOkResult && ClApprox(x,20.0) && ClApprox(y,120.0);
217 cout << "x == " << x.Value() << ", y == " << y.Value() << endl;
219 ClLinearEquation cxy( 2*x, y);
220 solver.AddConstraint(cxy);
221 fOkResult = fOkResult && ClApprox(x,20.0) && ClApprox(y,40.0);
222 cout << "x == " << x.Value() << ", y == " << y.Value() << endl;
224 solver.RemoveConstraint(c20);
225 fOkResult = fOkResult && ClApprox(x,60.0) && ClApprox(y,120.0);
226 cout << "x == " << x.Value() << ", y == " << y.Value() << endl;
228 solver.RemoveConstraint(cxy);
229 fOkResult = fOkResult && ClApprox(x,100.0) && ClApprox(y,120.0);
230 cout << "x == " << x.Value() << ", y == " << y.Value() << endl;
235 catch (ExCLError &error)
237 cerr << "Exception! " << error.description() << endl;
242 cerr << "Unknown exception" << endl;
252 bool fOkResult = true;
255 ClSimplexSolver solver;
258 .AddConstraint(new ClLinearInequality(x,cnLEQ,y))
259 .AddConstraint(new ClLinearEquation(y, x+3.0))
260 .AddConstraint(new ClLinearEquation(x,10.0,ClsWeak()))
261 .AddConstraint(new ClLinearEquation(y,10.0,ClsWeak()))
264 fOkResult = fOkResult &&
265 ( ClApprox(x,10.0) && ClApprox(y,13.0) ||
266 ClApprox(x,7.0) && ClApprox(y,10.0) );
268 cout << "x == " << x.Value() << ", y == " << y.Value() << endl;
272 catch (ExCLError &error)
274 cerr << "Exception! " << error.description() << endl;
279 cerr << "Unknown exception" << endl;
287 ClSimplexSolver solver;
289 ClLinearEquation eq1(x,10.0);
290 ClLinearEquation eq2(x,5.0);
294 solver.AddConstraint( eq1 );
295 solver.AddConstraint( eq2 );
297 // no exception, we failed!
300 catch (ExCLRequiredFailure)
302 // we want this exception to get thrown
303 cout << "Success -- got the exception" << endl;
304 // solver.RemoveConstraint(eq2); this would throw a constraint not found exception
305 // cout << solver << endl;
308 catch (ExCLError &error)
310 cerr << "Exception! " << error.description() << endl;
315 cerr << "Unknown exception" << endl;
326 ClSimplexSolver solver;
329 .AddConstraint(new ClLinearInequality(x,cnGEQ,10.0))
330 .AddConstraint(new ClLinearInequality(x,cnLEQ, 5.0));
332 // no exception, we failed!
335 catch (ExCLRequiredFailure &)
337 // we want this exception to get thrown
338 cout << "Success -- got the exception" << endl;
339 // cout << solver << endl;
342 catch (ExCLError &error)
344 cerr << "Exception! " << error.description() << endl;
349 cerr << "Unknown exception" << endl;
363 ClSimplexSolver solver;
366 .AddConstraint(new ClLinearInequality(w,cnGEQ,10.0))
367 .AddConstraint(new ClLinearInequality(x,cnGEQ,w))
368 .AddConstraint(new ClLinearInequality(y,cnGEQ,x))
369 .AddConstraint(new ClLinearInequality(z,cnGEQ,y))
370 .AddConstraint(new ClLinearInequality(z,cnLEQ,4.0));
372 // no exception, we failed!
375 catch (ExCLRequiredFailure &)
377 // we want this exception to get thrown
378 cout << "Success -- got the exception" << endl;
379 // cout << solver << endl;
382 catch (ExCLError &error)
384 cerr << "Exception! " << error.description() << endl;
389 cerr << "Unknown exception" << endl;
400 bool fOkResult = true;
406 ClSimplexSolver solver;
424 cout << "x = " << x.Value() << "; y = " << y.Value() << endl
425 << "w = " << w.Value() << "; h = " << h.Value() << endl;
427 fOkResult = fOkResult &&
428 ClApprox(x,10) && ClApprox(y,20) && ClApprox(w,0) && ClApprox(h,0);
440 cout << "x = " << x.Value() << "; y = " << y.Value() << endl
441 << "w = " << w.Value() << "; h = " << h.Value() << endl;
443 fOkResult = fOkResult &&
444 ClApprox(x,10) && ClApprox(y,20) && ClApprox(w,30) && ClApprox(h,40);
451 cout << "x = " << x.Value() << "; y = " << y.Value() << endl
452 << "w = " << w.Value() << "; h = " << h.Value() << endl;
454 fOkResult = fOkResult &&
455 ClApprox(x,50) && ClApprox(y,60) && ClApprox(w,30) && ClApprox(h,40);
459 catch (ExCLError &error)
461 cerr << "Exception! " << error.description() << endl;
466 cerr << "Unknown exception" << endl;
469 cerr << "Should have gotten an exception!" << endl;
479 bool fOkResult = true;
485 ClSimplexSolver solver;
503 cout << "x = " << x.Value() << "; y = " << y.Value() << endl
504 << "w = " << w.Value() << "; h = " << h.Value() << endl;
506 fOkResult = fOkResult &&
507 ClApprox(x,10) && ClApprox(y,20) && ClApprox(w,0) && ClApprox(h,0);
521 cout << "x = " << x.Value() << "; y = " << y.Value() << endl
522 << "w = " << w.Value() << "; h = " << h.Value() << endl;
524 fOkResult = fOkResult &&
525 ClApprox(x,10) && ClApprox(y,20) && ClApprox(w,30) && ClApprox(h,40);
532 cout << "x = " << x.Value() << "; y = " << y.Value() << endl
533 << "w = " << w.Value() << "; h = " << h.Value() << endl;
535 fOkResult = fOkResult &&
536 ClApprox(x,50) && ClApprox(y,60) && ClApprox(w,30) && ClApprox(h,40);
540 catch (ExCLError &error)
542 cerr << "Exception! " << error.description() << endl;
547 cerr << "Unknown exception" << endl;
550 cerr << "Should have gotten an exception!" << endl;
555 // From a bug report from Steve Wolfman on his
556 // SAT project using "blackbox"
562 ClSimplexSolver solver;
573 ClConstraint *rgpcn[30];
574 for (int i=0; i<int(sizeof(rgpcn)/sizeof(rgpcn[0])); ++i)
577 rgpcn[1] = new ClLinearEquation(r1,60);
578 rgpcn[2] = new ClLinearEquation(r2,30);
579 rgpcn[12] = new ClLinearEquation(r3,2.5);
580 rgpcn[13] = new ClLinearEquation(r6,0);
581 rgpcn[14] = new ClLinearInequality(r5, cnGEQ, 0);
582 rgpcn[15] = new ClLinearInequality(r8, cnLEQ, 2.5);
583 rgpcn[16] = new ClLinearInequality(r7, cnGEQ, r6);
584 rgpcn[17] = new ClLinearInequality(r8, cnGEQ, r7);
585 rgpcn[18] = new ClLinearEquation(r4, r3 - r2/60.0);
586 rgpcn[19] = new ClLinearEquation(r5, r4 - r1/60.0);
587 rgpcn[20] = new ClLinearInequality(r4, cnGEQ, 0);
588 rgpcn[21] = new ClLinearInequality(r5, cnGEQ, 0);
589 rgpcn[22] = new ClLinearEquation(r7, r6 + r2/20.0);
590 rgpcn[23] = new ClLinearEquation(r8, r7 + r1/20.0);
591 rgpcn[24] = new ClLinearEquation(r4, r3 - r2/30.0);
592 rgpcn[25] = new ClLinearEquation(r5, r4 - r1/30.0);
593 rgpcn[26] = new ClLinearInequality(r4, cnGEQ, 0);
594 rgpcn[27] = new ClLinearInequality(r5, cnGEQ, 0);
595 rgpcn[28] = new ClLinearEquation(r7, r6 + r2/60.0);
596 rgpcn[29] = new ClLinearEquation(r8, r7 + r1/60.0);
607 cin.getline(szCmd,900);
610 if (strcasecmp(szCmd,"Add") == 0)
613 cout << "eq" << i << ": " << solver.AddConstraintNoException(rgpcn[i])
614 << "\t" << *(rgpcn[i]) << endl;
615 cout << r1 << " = " << r1.Value() << endl;
617 else if (strcasecmp(szCmd,"del") == 0)
620 cout << "REMeq" << i << ": " << solver.RemoveConstraintNoException(rgpcn[i])
621 << "\t" << *(rgpcn[i]) << endl;
622 cout << r1 << " = " << r1.Value() << endl;
624 else if (strcasecmp(szCmd,"dump") == 0)
626 cout << solver << endl;
628 else if (strcasecmp(szCmd,"val") == 0)
630 cout << r1 << " = " << r1.Value() << endl;
632 else if (strcasecmp(szCmd,"solve") == 0)
634 cout << solver.Solve() << endl;
636 else if (strcasecmp(szCmd,"autosolve") == 0)
638 solver.SetAutosolve(true);
640 else if (strcasecmp(szCmd,"noautosolve") == 0)
642 solver.SetAutosolve(true);
646 cout << r1 << " = " << r1.Value() << endl
647 << r2 << " = " << r2.Value() << endl
648 << r3 << " = " << r3.Value() << endl
649 << r4 << " = " << r4.Value() << endl
650 << r5 << " = " << r5.Value() << endl
651 << r6 << " = " << r6.Value() << endl
652 << r7 << " = " << r7.Value() << endl
653 << r8 << " = " << r8.Value() << endl;
657 catch (ExCLError &error)
659 cerr << "Exception! " << error.description() << endl;
664 cerr << "Unknown exception" << endl;
669 typedef ClVariable *PClVariable;
672 addDel(const int nCns = 900, const int nVars = 900, const int nResolves = 10000)
673 //addDel(int nCns = 300, int nVars = 300, int nResolves = 1000)
674 //addDel(int nCns = 30, int nVars = 30, int nResolves = 100)
677 // FIXGJB: from where did .12 come?
678 static const double ineqProb = 0.12;
679 static const int maxVars = 3;
681 cout << "starting timing test. nCns = " << nCns
682 << ", nVars = " << nVars << ", nResolves = " << nResolves << endl;
685 ClSimplexSolver solver;
686 solver.SetAutosolve(false);
688 ClVariable **rgpclv = new PClVariable[nVars];
689 for (int i = 0; i < nVars; i++)
691 rgpclv[i] = new ClVariable(i,"x");
692 solver.AddStay(*rgpclv[i]);
695 ClConstraint **rgpcns = new PClConstraint[nCns];
700 for (j = 0; j < nCns; j++)
702 // number of variables in this constraint
703 nvs = int(UniformRandom()*maxVars) + 1;
704 ClLinearExpression expr = UniformRandom()*20.0 - 10.0;
705 for (k = 0; k < nvs; k++)
707 coeff = UniformRandom()*10 - 5;
708 expr.AddExpression(*(rgpclv[int(UniformRandom()*nVars)]) * coeff);
710 if (UniformRandom() < ineqProb)
712 rgpcns[j] = new ClLinearInequality(expr);
716 rgpcns[j] = new ClLinearEquation(expr);
718 #ifdef CL_SHOW_CNS_IN_BENCHMARK
719 cout << "Cn[" << j << "]: " << *rgpcns[j] << endl;
723 cout << "done building data structures" << endl;
724 cout << "time = " << timer.ElapsedTime() << "\n" << endl;
727 #ifdef CL_SHOW_CNS_IN_BENCHMARK
728 cout << "Exceptions on: ";
730 for (j = 0; j < nCns; j++)
732 // Add the constraint -- if it's incompatible, just ignore it
735 solver.AddConstraint(rgpcns[j]);
737 catch (ExCLRequiredFailure &)
741 #ifdef CL_SHOW_CNS_IN_BENCHMARK
746 #ifdef CL_SHOW_CNS_IN_BENCHMARK
747 cout << "\n" << endl;
750 cout << "done adding constraints [" << cExceptions << " exceptions]" << endl;
751 cout << "time = " << timer.ElapsedTime() << "\n" << endl;
752 cout << "time per cn = " << timer.ElapsedTime()/nCns << "\n" << endl;
753 cout << "time per actual cn = " << timer.ElapsedTime()/(nCns - cExceptions) << "\n" <<endl;
756 int e1Index = int(UniformRandom()*nVars);
757 int e2Index = int(UniformRandom()*nVars);
759 ClVariable e1 = *(rgpclv[e1Index]);
760 ClVariable e2 = *(rgpclv[e2Index]);
766 cout << "done creating edit constraints -- about to start resolves" << endl;
767 cout << "time = " << timer.ElapsedTime() << "\n" << endl;
771 // FIXGJB start = Timer.now();
772 for (int m = 0; m < nResolves; ++m)
775 .SuggestValue(e1,e1->Value()*1.001)
776 .SuggestValue(e2,e2->Value()*1.001)
780 // cout << "run time: " <<
782 cout << "done resolves -- now removing constraints" << endl;
783 cout << "time = " << timer.ElapsedTime() << "\n" <<endl;
784 cout << "time per Resolve = " << timer.ElapsedTime()/nResolves << "\n" <<endl;
788 for (j = 0; j < nCns; j++)
792 solver.RemoveConstraint(rgpcns[j]);
796 // FIXGJB end = Timer.now();
797 // cout << "Total remove time: "
798 // << "remove time per cn"
799 cout << "done removing constraints and addDel timing test" << endl;
800 cout << "time = " << timer.ElapsedTime() << "\n" <<endl;
801 cout << "time per cn = " << timer.ElapsedTime()/nCns << "\n" <<endl;
802 cout << "time per actual cn = " << timer.ElapsedTime()/(nCns - cExceptions) << "\n" <<endl;
804 for (int i = 0; i < nVars; i++)
809 for (int j = 0; j < nCns; j++)
819 main( int argc, char **argv )
823 bool fAllOkResult = true;
826 // seed the random number generator for reproducible results
829 cout << "Cassowary version: " << szCassowaryVersion << endl;
831 #define RUN_TEST(x) \
832 cout << #x << ":" << endl; \
833 fResult = x(); fAllOkResult &= fResult; \
834 if (!fResult) cout << "Failed!" << endl;
839 RUN_TEST(addDelete1);
840 RUN_TEST(addDelete2);
842 RUN_TEST(inconsistent1);
843 RUN_TEST(inconsistent2);
844 RUN_TEST(inconsistent3);
846 RUN_TEST(multiedit2);
847 // RUN_TEST(blackboxsat);
849 int cns = 90, vars = 90, resolves = 100;
855 vars = atoi(argv[2]);
858 resolves = atoi(argv[3]);
862 cout << "addDel" << ":" << endl;
863 fResult = addDel(cns,vars,resolves); fAllOkResult &= fResult;
864 if (!fResult) cout << "Failed!" << endl;
870 cout << "ClAbstractVariables: " << ClAbstractVariable::cAbstractVariables
871 << "\nClDummyVariables: " << ClDummyVariable::cDummyVariables
872 << "\nClSlackVariables: " << ClSlackVariable::cSlackVariables
877 return (fAllOkResult? 0 : 255);
882 cerr << "exception!" << endl;