diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libvpsc/tests')
-rw-r--r-- | src/3rdparty/adaptagrams/libvpsc/tests/Makefile.am | 15 | ||||
-rw-r--r-- | src/3rdparty/adaptagrams/libvpsc/tests/block.cpp | 105 | ||||
-rw-r--r-- | src/3rdparty/adaptagrams/libvpsc/tests/cycle.cpp | 106 | ||||
-rw-r--r-- | src/3rdparty/adaptagrams/libvpsc/tests/rectangleoverlap.cpp | 660 | ||||
-rw-r--r-- | src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp | 666 |
5 files changed, 1552 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/Makefile.am b/src/3rdparty/adaptagrams/libvpsc/tests/Makefile.am new file mode 100644 index 0000000..d155c52 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/Makefile.am @@ -0,0 +1,15 @@ +AM_CPPFLAGS = -I$(top_srcdir) + +check_PROGRAMS = rectangleoverlap block satisfy_inc # cycle +satisfy_inc_SOURCES = satisfy_inc.cpp +satisfy_inc_LDADD = $(top_builddir)/libvpsc/libvpsc.la # -L$(mosek_home)/bin -lmosek -lguide -limf -lirc +block_SOURCES = block.cpp +block_LDADD = $(top_builddir)/libvpsc/libvpsc.la +rectangleoverlap_SOURCES = rectangleoverlap.cpp +rectangleoverlap_LDADD = $(top_builddir)/libvpsc/libvpsc.la + +#cycle_SOURCES = cycle.cpp +#cycle_LDADD = $(top_builddir)/libvpsc/libvpsc.la + +TESTS = $(check_PROGRAMS) + diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/block.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/block.cpp new file mode 100644 index 0000000..08080e9 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/block.cpp @@ -0,0 +1,105 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cassert> +#include <iostream> + +#include "libvpsc/variable.h" +#include "libvpsc/constraint.h" +#include "libvpsc/blocks.h" +#include "libvpsc/block.h" +using namespace std; +using namespace vpsc; + + +void test1() { + Blocks *blocks = new Blocks(Variables()); + cout << "Block test 1..." << endl; + Variable *a1=new Variable(1,0,1); + Variable *a2=new Variable(2,0,1); + Constraint *c=new Constraint(a1,a2,1); + a1->out.push_back(c); + a2->in.push_back(c); + Block *b1=new Block(blocks, a1); + Block *b2=new Block(blocks, a2); + b1->merge(b2,c); + cout << "Block: " << *b1 << endl; + a1->desiredPosition = -1; + a2->desiredPosition = 2; + Constraint *m = b1->findMinLMBetween(a1,a2); + cout << "Min lm constraint: " << *m << endl; + assert(c==m); + cout << " lm=" << c->lm << endl; + cout << "Block test 1... Success!" << endl; +} + +/* + * Constraint tree: + * \_/ + * / \ + */ +void test2() { + Blocks *blocks = new Blocks(Variables()); + cout << "Block test 2..." << endl; + Variable *a[]={ + new Variable(0,0,1), + new Variable(1,0,1), + new Variable(2,1,1), + new Variable(3,2,1), + new Variable(4,3,1), + new Variable(5,3,1)}; + Constraint *c[]={ + new Constraint(a[0],a[2],2), + new Constraint(a[1],a[2],2), + new Constraint(a[2],a[3],2), + new Constraint(a[3],a[4],2), + new Constraint(a[3],a[5],2)}; + for(int i=0;i<6;i++) { + new Block(blocks,a[i]); + } + for(int i=0;i<5;i++) { + c[i]->left->out.push_back(c[i]); + c[i]->right->in.push_back(c[i]); + } + for(int i=0;i<5;i++) { + Block *l=c[i]->left->block, *r=c[i]->right->block; + l->merge(r,c[i]); + } + Block *b=a[0]->block; + cout << "Block: " << *b << endl; + for(int i=0;i<6;i++) { + a[i]->desiredPosition = i!=4?-2:5; + } + cout << "calc min lm:" << endl; + Constraint *m = b->findMinLMBetween(a[0],a[4]); + cout << "Min lm constraint: " << *m << endl; + assert(m==c[3]); + cout << "Block test 2... Success!" << endl; +} +int main() { + test1(); + test2(); + return 0; +} diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/cycle.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/cycle.cpp new file mode 100644 index 0000000..26dda3a --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/cycle.cpp @@ -0,0 +1,106 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <iostream> +#include <cassert> +#include <cmath> +#include <algorithm> +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +using namespace std; +using namespace vpsc; +inline bool approxEquals(const double a, const double b) { + return fabs((double)a-b)<0.0001; +} +void test1() { + cout << "Test 1..." << endl; + vector<Variable*> a; + a.push_back(new Variable(0,0,1)); + a.push_back(new Variable(1,1,1)); + vector<Constraint*> c; + c.push_back(new Constraint(a[0],a[1],2)); + c.push_back(new Constraint(a[1],a[0],2)); + double expected[]={1.5,-0.5}; + try { + IncSolver vpsc(a,c); + vpsc.solve(); + } catch (UnsatisfiableException& e) { + cerr << "Unsatisfiable" << endl; + for(vector<Constraint*>::iterator i=e.path.begin(); + i!=e.path.end();i++) { + cout << **i << endl; + } + exit(1); + } + //catch(...) { + //cerr << "Unknown error!" << endl; + //exit(1); + //} + + for(size_t i=0;i<a.size();i++) { + assert(approxEquals(a[i]->finalPosition,expected[i])); + } + for_each(a.begin(),a.end(),delete_object()); + for_each(c.begin(),c.end(),delete_object()); + cout << "Test 1... done." << endl; +} +void test2() { + cout << "Test 2..." << endl; + vector<Variable *> a; + a.push_back(new Variable(0,8,1)); + a.push_back(new Variable(1,5,1)); + a.push_back(new Variable(2,3,1)); + a.push_back(new Variable(3,1,1)); + vector<Constraint*> c; + c.push_back(new Constraint(a[0],a[3],3)); + c.push_back(new Constraint(a[0],a[1],3)); + c.push_back(new Constraint(a[1],a[3],3)); + c.push_back(new Constraint(a[1],a[2],3)); + c.push_back(new Constraint(a[2],a[3],3)); + c.push_back(new Constraint(a[2],a[3],3)); + //double expected[]={-3.71429,4,1,-0.714286,2.28571,2.28571,7,5.28571,8.28571,11.2857}; + try { + IncSolver vpsc(a,c); + vpsc.solve(); + } catch (char const *msg) { + cerr << msg << endl; + exit(1); + } + + /* + for(int i=0;i<n;i++) { + assert(approxEquals(a[i]->position(),expected[i])); + } + */ + cout << "Test 2... done." << endl; + for_each(a.begin(),a.end(),delete_object()); + for_each(c.begin(),c.end(),delete_object()); +} +int main() { + test1(); + return 0; +} diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/rectangleoverlap.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/rectangleoverlap.cpp new file mode 100644 index 0000000..d8ad72e --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/rectangleoverlap.cpp @@ -0,0 +1,660 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cstdio> +#include <cassert> +#include <cstdlib> +#include <math.h> +#include <time.h> +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +using namespace std; +using namespace vpsc; + +inline double getRand(double range) { + return range*rand()/RAND_MAX; +} +void printRects(vector<Rectangle*> &rs) { + printf("Set of %d rectangles:\n",(int)rs.size()); + for(unsigned i=0;i<rs.size();++i) { + cout << *rs[i] << endl; + } +} +void generateRandomRects(unsigned n, vector<Rectangle*> &rs) { + rs.resize(n); + static double const rect_size = 5; + static double const min_rect_size = 1e-4; + static double const fld_size = sqrt(rect_size * n / 2.0); + double coords[4]; + for (unsigned i = 0; i < n; ++i) { + for (unsigned d = 0; d < 2; ++d) { + //unsigned const end = 1 + (rand() % (fld_size - 1)); + //unsigned const start = rand() % end; + double const start = getRand(fld_size); + double const end = start + min_rect_size + + getRand(rect_size); + coords[2 * d] = start; + coords[2 * d + 1] = end; + } + rs[i]=new Rectangle(coords[0],coords[1],coords[2],coords[3]); + } +} +vector<Rectangle*>& generateRects(double coords[][4], unsigned n,vector<Rectangle *>& rs) { + rs.resize(n); + for (unsigned i = 0; i < n; ++i) { + rs[i]=new Rectangle(coords[i][0],coords[i][1],coords[i][2],coords[i][3]); + } + return rs; +} +void test(vector<Rectangle *> &rs, double &cost, double &duration) { + unsigned n=rs.size(); + vector<Rectangle *> ors(n); + for (unsigned i = 0; i < n; ++i) { + ors[i]=new Rectangle(rs[i]->getMinX(),rs[i]->getMaxX(),rs[i]->getMinY(),rs[i]->getMaxY()); + } + + clock_t starttime = clock(); + removeoverlaps(rs); + duration = (double)(clock() - starttime)/CLOCKS_PER_SEC; + cost = 0; + for(unsigned i=0;i<n;i++) { + double dx=rs[i]->getCentreX()-ors[i]->getCentreX(); + double dy=rs[i]->getCentreY()-ors[i]->getCentreY(); + cost+=sqrt(dx*dx+dy*dy); + delete rs[i]; + delete ors[i]; + } +} +double test1[][4]={ { 0, 50, 0, 30 }, { 10, 20, 10, 29 }, +{ 30, 70, 39, 70 }, { 0, 90, 40, 50 }, { 30, 70, 1, 29 } }; +unsigned n1=5; +double test2[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, +{ 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, +{ 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; +unsigned n2=8; +double test3[][4]={ { 8, 32, 29, 36 }, { 19, 24, 2, 27 }, +{ 4, 5, 27, 55 }, { 6, 7, 13, 26 }, { 3, 39, 46, 62 }, +{ 6, 23, 2, 19 }, { 18, 39, 5, 23 }, { 35, 63, 42, 78 }, +{ 16, 18, 14, 72 }, { 12, 32, 10, 58 } }; +unsigned n3=10; +double test4[][4]={ { 315.755, 355.288, 353.595, 449.627 }, +{ 395.048, 395.635, 253.943, 362.228 }, +{ 254.439, 393.289, 278.708, 286.346 }, +{ 209.852, 370.831, 326.496, 507.255 }, +{ 271.947, 415.74, 362.228, 450.318 }, +{ 293.408, 405.197, 220.61, 244.119 }, +{ 276.482, 386.472, 286.346, 435.767 }, +{ 268.211, 436.23, 192.807, 220.61 }, +{ 378.008, 502.118, 358.437, 475.587 }, +{ 340.68, 472.597, 249.492, 335.448 } }; +unsigned n4=10; +double test5[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, +{ 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, +{ 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; +unsigned n5=8; +double test6[][4]={ { 40, 69, 63, 69 }, { 1, 5, 27, 64 }, +{ 34, 66, 20, 22 }, { 1, 24, 10, 25 }, { 1, 19, 9, 61 }, +{ 0, 56, 8, 70 }, { 33, 35, 13, 28 }, { 11, 31, 33, 35 }, +{ 12, 22, 3, 23 } }; +unsigned n6=9; +double test7[][4]={ { 341.594, 388.459, 373.491, 518.168 }, +{ 271.214, 324.782, 311.332, 409.166 }, +{ 293.848, 475.064, 305.194, 391.162 }, +{ 255.317, 447.738, 342.671, 489.923 }, +{ 228.375, 261.057, 206.422, 327.794 }, +{ 383.552, 462.834, 363.132, 412.843 }, +{ 288.859, 481.054, 351.895, 497.728 }, +{ 201.307, 368.511, 387.02, 394.95 }, +{ 257.961, 259.673, 386.503, 518.403 }, +{ 200.178, 275.606, 364.968, 466.787 } }; +unsigned n7=10; +double test8[][4]={{12.807,15.7566,14.9478,16.7924}, +{7.76228,11.6532,4.75249,4.75349}, +{7.84596,10.1387,15.465,16.7709}, +{1.80748,3.0357,5.9983,6.16279}, +{6.46447,7.47249,12.8694,13.4378}, +{14.0026,17.3342,5.10141,9.81088}, +{6.84223,6.85932,6.40395,9.21135}, +{7.63462,10.3552,6.78124,8.59953}, +{0.26429,2.80847,14.5724,17.7455}, +{14.7686,15.7148,3.46036,5.66776}, +{10.635,11.4893,12.5044,16.941}, +{6.32027,10.7117,14.2953,15.6276}, +{11.9942,13.1118,10.6893,11.4477}, +{11.9384,15.1357,2.20982,6.92982}, +{2.89395,4.29002,11.7058,16.2896}, +{9.44116,12.7547,9.75556,11.1811}, +{5.2475,8.00607,15.3652,17.026}, +{2.09541,3.76981,2.5526,3.16739}, +{3.14595,6.66351,10.3007,14.4881}, +{4.88109,9.38044,9.02416,10.2954}, +{7.55378,9.14715,13.9686,16.0468}, +{1.70299,5.42198,14.1913,14.2191}, +{14.4877,14.4897,6.14013,8.50074}, +{12.9909,14.5163,10.322,12.4457}, +{11.616,12.0848,3.7601,5.45419}, +{10.3087,13.358,3.04666,3.53389}, +{2.28263,2.44881,13.806,15.8206}, +{3.31805,5.47662,3.91187,6.85355}, +{0.484138,2.06164,3.57335,7.87753}, +{4.73784,5.12359,9.383,11.9217}, +{12.2921,12.7769,12.329,12.8139}, +{12.7351,16.7141,12.7658,13.78}, +{3.71614,5.79872,1.53137,4.97126}, +{10.7423,14.8183,2.57104,2.94168}, +{9.93995,10.1557,1.3432,1.499}, +{0.198099,0.204966,9.29459,11.8795}, +{14.1043,18.8473,11.2028,14.1971}, +{4.23857,4.95743,14.7047,17.1439}, +{13.936,15.9612,10.7744,14.8598}, +{11.355,15.6824,2.49113,5.96963}, +{12.8528,16.3913,3.82582,6.67259}, +{13.9445,14.7354,10.8576,12.9503}, +{13.0041,15.6166,2.07035,3.70034}, +{2.31809,5.03195,1.13659,5.8604}, +{10.2454,14.5396,10.9442,15.4321}, +{7.12259,11.3929,7.20864,10.4059}, +{6.54862,9.88399,1.82828,5.89899}, +{4.27072,7.52613,7.99016,11.1703}, +{8.84828,9.15453,10.1489,11.7934}, +{7.71027,8.97206,3.26462,4.02636}, +{14.3383,15.1727,3.02586,3.26268}, +{9.21233,11.1919,13.9814,16.1433}, +{13.1946,16.1613,12.2268,13.1319}, +{13.0462,15.6689,7.03513,8.59752}, +{8.72724,11.3859,5.69193,7.8238}, +{10.6241,14.1033,7.88946,9.95327}, +{8.48376,10.8714,8.86955,11.2137}, +{3.55633,4.14351,13.7308,18.4988}, +{1.79802,4.68843,11.0964,11.6543}, +{13.1535,14.6895,1.52144,2.50643}, +{1.24533,4.27261,13.345,13.4925}, +{14.4031,18.7944,15.4447,18.0096}, +{8.56933,11.3392,0.446787,1.18762}, +{11.311,16.0574,8.41,8.76508}, +{13.5332,17.8479,8.2067,11.4446}, +{5.73826,6.63581,10.8364,11.6186}, +{10.1995,11.5202,6.54248,9.49804}, +{14.6456,16.7915,7.01621,7.57531}, +{15.1444,16.4184,1.45761,2.35577}, +{11.8169,12.0382,14.8149,19.3316}, +{10.148,11.1227,15.0087,18.1595}, +{10.9498,14.7849,12.3852,13.9467}, +{10.7631,10.9141,5.24419,8.64319}, +{11.2486,12.6029,6.25029,10.0076}, +{12.8731,16.0703,4.96619,8.54006}, +{6.92828,8.53172,8.36509,11.8971}, +{3.1677,7.20423,14.5582,17.1794}, +{14.1426,16.9327,15.1198,19.1306}, +{2.52943,6.64027,5.18935,8.58545}, +{6.89613,11.4515,3.7672,6.23813}, +{2.91428,6.40636,1.4231,4.10552}, +{9.81892,12.9687,8.25114,10.1775}, +{14.6192,14.7412,10.8349,15.1725}, +{6.96657,11.7009,11.0638,11.8966}, +{7.03182,9.20687,2.04293,2.60462}, +{7.47955,9.28533,7.45213,8.37318}, +{6.24651,9.79246,8.61803,9.91034}, +{4.73642,7.48461,9.59481,12.748}, +{8.70644,11.1702,2.54172,4.26587}, +{14.9028,19.4109,6.238,8.04256}, +{5.22907,8.45899,1.98714,4.94042}, +{8.96884,12.3636,1.72663,3.39844}, +{6.96563,8.04735,10.6198,11.3663}, +{1.65099,5.65883,10.5002,13.9039}, +{11.3337,11.5138,5.31369,7.75029}, +{2.79561,4.08151,7.04269,9.00167}}; + +unsigned n8=96; +double test9[][4]={{2.67865,4.81342,8.67025,11.5025}, +{5.77912,6.94355,9.80043,12.2904}, +{11.9459,13.8675,3.66967,7.38408}, +{6.72663,8.30474,3.37566,7.24571}, +{9.2081,10.9827,10.9557,11.8868}, +{0.161903,3.31202,3.35371,3.84933}, +{4.46508,9.18934,9.43037,10.9125}, +{3.84059,5.2565,8.66868,8.70713}, +{4.67598,5.15207,5.2252,8.92099}, +{1.19252,1.31215,7.97481,8.27191}, +{4.57641,5.71063,0.440628,4.17365}, +{6.80268,11.5523,3.78375,4.79819}, +{11.2172,13.7652,8.44876,11.1649}, +{11.4673,13.1644,6.09156,7.41026}, +{12.2995,13.585,0.155239,4.63887}, +{12.3513,15.3947,8.3437,11.1337}, +{3.92566,6.15611,12.432,16.3993}, +{12.6351,14.6039,9.96391,13.1152}, +{0.682894,2.48867,7.66904,8.86704}, +{3.50189,7.28939,8.37741,8.96276}, +{2.37719,4.19762,11.1129,12.0465}, +{5.53568,8.1444,11.9056,15.5818}, +{7.32876,11.2713,12.1655,15.0785}, +{2.534,6.15563,9.30845,11.2833}, +{8.00852,12.8051,2.16786,4.90262}, +{11.8095,12.814,11.5818,13.7731}, +{7.54398,9.23043,7.36953,10.7315}, +{8.36918,9.83071,11.8668,11.8776}, +{5.72267,9.66642,1.46379,3.71362}, +{11.2725,14.6538,4.76772,7.30304}, +{5.8638,10.7623,5.99865,10.0994}, +{11.0224,12.6455,0.852638,2.20201}, +{4.03151,8.51056,6.12449,10.3672}, +{7.75136,10.6782,10.648,11.8606}, +{11.9663,14.3993,2.83154,5.46437}, +{6.05275,8.00044,10.9675,15.3426}, +{10.9702,13.146,8.98465,12.4718}, +{4.99665,7.91376,9.19241,9.71153}, +{3.7422,4.00542,2.00556,2.53918}, +{9.01679,10.9439,12.8107,15.1367}, +{10.0117,11.5009,0.194049,3.08568}, +{8.29117,13.1323,6.99045,8.65707}, +{5.97395,10.5816,5.77559,7.35126}, +{5.68856,6.51699,4.40392,5.82242}, +{0.209729,3.89072,7.36013,8.98447}, +{0.360264,1.88558,0.319886,3.22738}, +{2.02163,2.07428,3.2753,8.12958}, +{5.05075,5.86987,12.7958,16.7689}, +{10.6484,15.5931,7.23546,10.4741}, +{7.20998,7.46939,2.44384,5.10459}, +{12.5022,15.1819,10.6593,13.5708}, +{2.3619,2.45407,5.75168,7.28966}, +{12.131,16.661,4.39608,8.19289}, +{9.81023,10.731,6.67919,9.31523}, +{6.97712,10.166,8.4813,13.3432}, +{6.45378,7.44457,8.96504,11.9806}, +{8.70396,11.5729,7.15588,12.1524}, +{9.93058,14.0306,0.849502,1.80855}, +{8.32174,8.34616,7.52595,12.0431}, +{2.79979,5.93358,4.90296,7.6893}, +{0.72484,5.42439,3.48229,5.77743}, +{6.05275,10.2779,7.4252,7.72184}, +{4.41176,6.91184,11.8809,15.3923}, +{6.50435,8.04432,11.4826,15.3172}, +{12.16,14.3518,1.13763,4.17255}, +{7.82506,10.5124,8.05713,9.03876}}; +unsigned n9=66; +double test10[][4]={{15.9875,18.9768,15.3193,17.9811}, +{16.5669,19.7216,1.05824,1.58667}, +{8.80629,9.88527,9.71101,13.2142}, +{19.568,20.1767,3.28922,8.03561}, +{13.6363,15.6827,12.9329,16.6542}, +{2.32913,3.58085,8.28597,12.6503}, +{6.86597,11.2847,5.9172,10.236}, +{8.57413,11.0048,18.0203,18.4095}, +{7.68828,8.89193,9.52038,12.3945}, +{13.5784,15.499,0.824193,4.7533}, +{5.70392,8.26946,10.1955,12.8184}, +{17.9857,22.6483,14.2013,16.0377}, +{14.7965,16.4222,11.9332,16.5984}, +{20.5111,23.1383,0.355473,0.834461}, +{5.88763,9.2761,8.31995,11.6173}, +{13.8307,16.6334,17.2376,19.8715}, +{7.20005,8.99179,19.0137,23.483}, +{3.67112,6.97933,18.6142,21.1208}, +{0.936183,5.81945,5.11063,7.47703}, +{9.85383,12.4861,7.80027,11.677}, +{8.07584,11.1964,13.8571,17.9736}, +{8.07017,10.0661,8.42816,9.79417}, +{10.8259,11.6232,16.7028,19.3248}, +{18.55,19.3911,17.174,22.0082}, +{1.34073,1.93538,17.9341,20.4509}, +{11.7558,12.1994,0.295703,2.19289}, +{12.4063,13.662,0.965124,5.21391}, +{2.2033,2.85518,16.4455,20.0191}, +{6.3853,9.77239,0.892142,2.17773}, +{0.546736,5.29679,12.1949,15.2469}, +{14.1365,17.5213,14.7027,15.1512}, +{9.46879,11.9145,11.8539,14.4408}, +{8.49611,8.98075,17.1388,17.5066}, +{1.53577,2.52014,0.615943,4.13396}, +{7.12078,9.05901,20.3739,23.44}, +{2.7104,7.09713,16.4442,20.8587}, +{12.9707,14.2845,12.5642,16.2281}, +{13.5086,14.3207,17.7611,20.1056}, +{19.2264,24.1481,2.063,5.27645}, +{15.2016,18.2491,1.10228,3.37286}, +{16.7733,18.1385,2.35807,7.0123}, +{19.8272,21.9464,18.27,22.8376}, +{4.27133,8.48869,19.5925,21.488}, +{19.6951,23.7284,10.5207,11.1889}, +{0.799027,3.61863,1.42504,3.44902}, +{1.31871,5.95584,16.4147,18.2479}, +{19.8398,21.0495,15.2495,15.8842}, +{3.15773,5.76599,11.1562,12.2007}, +{4.61422,4.78559,16.6607,16.9497}, +{11.0064,11.5745,16.521,19.5463}, +{13.3865,15.7969,12.215,14.3112}, +{0.272424,4.59201,7.19502,9.58004}, +{15.6377,16.4926,18.5978,19.0178}, +{1.44957,1.65985,5.24023,10.1284}, +{0.0559948,0.138395,3.75354,4.46554}, +{3.24015,3.86196,12.205,14.0543}, +{2.64686,3.51587,16.1429,16.6103}, +{2.56003,5.14236,5.6624,8.31491}, +{13.7143,16.5806,7.32777,10.6354}, +{15.8994,20.4036,0.171759,0.567584}, +{11.1247,11.5263,7.61341,8.80042}, +{10.7869,11.8353,7.73861,8.39933}, +{16.7563,18.1604,15.6377,20.3633}, +{4.7627,5.87556,0.850618,4.25755}, +{11.2178,15.6734,14.2378,15.9026}, +{2.00323,5.94744,1.78428,4.77571}, +{16.0705,20.0359,9.50528,12.9563}, +{14.9808,18.3586,9.56819,10.8817}, +{13.7005,17.173,10.5755,15.5172}, +{6.24185,6.44174,11.9766,16.0609}, +{14.0767,16.1476,11.9904,14.2274}, +{18.3009,20.9378,0.109473,0.330122}, +{0.395109,4.35458,19.8694,23.5078}, +{17.4949,22.4626,6.16132,10.5268}, +{0.992178,2.11099,18.813,22.5419}, +{8.41369,12.6754,20.0682,22.6}, +{19.5239,23.6359,3.22945,3.81068}, +{6.60361,6.84761,11.8174,12.6899}, +{8.95351,9.96275,11.2373,12.3269}, +{13.8414,17.1229,18.182,20.7568}, +{13.0468,17.4872,16.8349,21.2615}, +{16.6053,17.1026,5.24778,8.1272}, +{1.20043,2.96974,10.1904,13.8153}, +{7.73924,7.74809,1.53703,3.76274}, +{15.0915,18.4866,18.6576,18.9426}, +{10.69,13.9811,6.92511,9.44625}, +{8.66032,12.8382,6.67974,9.08735}, +{3.24707,3.91176,7.21641,8.75134}, +{20.5281,23.518,5.04016,5.38868}, +{8.78238,13.6922,11.9149,12.334}, +{19.1358,19.5264,15.9157,16.8192}, +{4.52551,7.52884,12.1049,16.4566}, +{18.467,22.8957,2.97024,7.48362}, +{17.9618,18.9449,2.7601,4.06645}, +{10.8057,15.3718,7.7254,8.32173}, +{19.6416,21.5781,7.62473,11.5731}, +{5.14712,8.87694,0.495145,1.50088}, +{4.11719,6.22953,3.59814,8.25023}, +{6.34314,9.83141,1.90886,3.52039}, +{11.6041,11.7642,12.6177,16.2647}, +{17.4351,19.786,0.846214,2.85357}, +{7.90974,12.4031,10.5818,10.868}, +{3.33578,5.53021,19.271,22.6137}, +{14.3296,18.1074,3.76864,6.21134}, +{1.39798,4.21194,14.7015,18.9814}, +{13.3463,13.89,4.76333,8.78979}, +{7.78517,12.3834,12.0445,12.1204}, +{1.21553,4.14149,10.9523,11.5827}, +{10.7328,15.0635,11.2248,16.0148}, +{1.89816,6.42421,6.21479,9.51491}, +{5.76369,9.87896,0.471237,2.08597}, +{1.10543,3.50571,6.4243,6.85217}, +{13.4916,16.9187,13.4167,14.751}, +{6.61683,9.79075,4.44435,7.2165}, +{17.5276,21.8159,3.22316,7.12862}, +{8.09408,10.3727,0.167984,1.77021}, +{8.04815,12.6168,7.91666,11.0816}, +{1.32248,2.63905,12.5164,17.4845}, +{7.324,11.7358,9.05354,13.7152}, +{15.0274,18.5751,11.55,13.6444}, +{15.3627,16.1478,19.7391,21.3528}, +{16.5701,19.0741,18.0876,18.9877}, +{19.9719,20.1289,10.2999,14.2899}, +{5.77124,9.49847,20.3551,23.9988}, +{9.4065,13.7029,1.45775,2.17524}, +{8.22117,12.8533,16.9079,17.5996}, +{8.20293,12.4012,15.7691,15.783}, +{9.33037,11.8253,0.286895,2.70091}, +{12.5114,14.6471,11.0241,13.8678}, +{14.6423,15.2091,5.08987,9.29257}, +{10.4729,12.308,1.7717,6.27227}, +{9.65187,11.9638,14.3196,18.937}, +{5.1704,6.94718,18.4884,22.8028}, +{4.66015,8.43071,12.6095,14.2635}, +{19.5384,21.1589,7.47562,10.9592}, +{20.3595,24.407,0.804689,2.94465}, +{0.775119,2.53222,1.35017,2.38185}, +{14.1459,18.0717,13.111,17.3643}, +{15.9535,16.9371,3.47482,6.36462}, +{15.1727,17.7769,13.1324,16.2993}, +{17.2678,19.5719,19.2912,23.3942}, +{14.5832,17.1443,19.2559,24.0751}, +{1.57289,3.42857,7.75497,11.9183}, +{2.63994,5.18274,5.84108,8.64802}, +{7.56056,8.51991,0.284378,0.750091}, +{8.4225,12.0985,13.1443,16.5509}, +{12.4397,13.7349,16.1177,21.0089}, +{18.411,22.1179,12.4302,16.1478}, +{16.7343,19.9381,0.87138,4.38391}, +{0.729191,5.0941,0.4316,3.36382}, +{7.96699,10.079,15.0613,19.489}, +{14.4215,16.2705,13.932,15.6623}, +{9.37756,12.4608,12.8857,16.6014}, +{12.0729,12.5163,2.59841,7.39714}, +{7.52658,11.0203,15.2853,19.805}, +{16.0919,20.3462,13.6464,15.1218}, +{6.17075,10.0034,17.5729,21.8258}, +{8.94533,11.0185,7.98461,12.5047}, +{0.249775,1.8787,2.72361,7.6554}, +{11.5167,11.8826,8.7937,10.8008}, +{14.3038,17.8052,19.0873,20.7193}, +{19.7272,24.1131,5.29434,7.64106}, +{19.7624,20.0966,13.2827,17.354}, +{5.58186,7.99298,3.3987,5.8269}, +{19.7479,20.3262,16.1492,17.465}, +{3.25902,6.3684,17.0948,20.9851}, +{12.7549,14.4322,1.40931,6.02218}, +{12.232,13.2567,0.559319,3.07481}, +{0.138414,4.75571,14.9273,18.2745}, +{6.04241,6.23422,9.62104,10.3701}}; +unsigned n10=170; +double test11[][4]={{2.20847,5.99613,25.7684,29.5065}, +{4.38169,7.14163,-7.79499,-7.42678}, +{17.1816,19.4476,-5.03151,-3.38153}, +{10.6383,11.0169,-0.356332,3.85003}, +{13.3309,15.7634,21.4146,24.0122}, +{17.1354,20.5384,27.9053,29.8839}, +{4.82128,7.88931,4.90792,5.71239}, +{13.1802,14.7891,24.0123,26.5035}, +{9.1468,9.95493,-3.73661,-1.29955}, +{14.4021,17.8989,19.2669,23.5805}, +{3.53936,4.95206,17.2632,19.2913}, +{11.2732,15.3951,10.4298,11.6976}, +{9.82902,13.9892,17.9523,19.9811}, +{10.0265,11.0793,16.4791,17.5196}, +{1.27427,5.64116,7.85316,8.33764}, +{3.70992,7.16293,5.06311,6.98578}, +{9.95501,13.9876,-3.13412,-1.29965}, +{17.6086,21.8963,15.3022,17.9743}, +{2.05607,2.66477,-0.552748,0.286511}, +{12.6971,13.3533,-4.23798,-3.73671}, +{7.7961,11.69,7.35371,11.9837}, +{7.68167,9.93012,1.7933,3.98514}, +{1.2176,2.27018,0.286611,3.17168}, +{4.98578,7.91342,12.8464,16.1781}, +{16.5918,21.3527,4.59687,5.72758}, +{9.12809,9.56481,1.38197,2.061}, +{14.6904,19.1649,-3.38143,-1.21492}, +{11.3046,15.5357,14.6315,17.2819}, +{3.69836,4.52282,5.06311,5.67974}, +{12.2713,13.7058,11.6977,14.6314}, +{0.130993,3.26738,-4.32728,-3.7221}, +{11.4317,12.3544,19.9812,22.2083}, +{10.0298,10.1041,11.1483,12.7055}, +{16.2023,16.7313,1.49517,4.59677}, +{12.4149,15.8265,4.33334,6.45789}, +{17.575,19.9519,12.3124,15.3021}, +{17.0991,22.0233,3.78959,6.02599}, +{3.99216,5.32933,0.583351,0.882127}, +{16.5929,18.003,14.3823,17.6574}, +{13.5273,15.1372,16.4791,20.1285}, +{12.3687,15.2044,6.45799,7.83514}, +{8.04258,9.47375,17.3137,21.5515}, +{7.329,10.9322,7.65703,11.5161}, +{1.98895,2.89459,1.84656,3.17168}, +{0.520521,2.46608,6.71895,10.4866}, +{13.184,16.1474,6.45799,7.30869}, +{2.13915,4.58689,17.2632,19.8192}, +{15.8375,18.2786,15.9558,18.1255}, +{14.7223,16.4109,16.4791,17.3636}, +{4.00206,7.29287,-4.32728,-1.41062}, +{16.6028,18.6157,14.6315,17.1786}, +{3.19495,7.10528,-1.41052,0.583251}, +{1.69626,5.11997,0.326338,1.84646}, +{12.1579,12.759,-0.356332,0.328198}, +{3.51735,7.12098,5.71249,7.85306}, +{0.953512,5.10372,3.17178,5.06301}, +{13.2737,14.3319,18.7924,21.1975}, +{1.46188,5.99876,10.3471,12.8463}, +{8.39195,9.77825,1.66426,2.061}, +{1.81344,5.57851,-3.53802,0.326238}, +{1.31773,2.99152,29.5066,33.3419}, +{5.33625,7.15652,19.4265,19.8527}, +{0.432492,3.44635,7.60608,10.3589}, +{1.60933,2.36115,-1.16144,0.286511}, +{9.27774,10.4284,-1.86525,-1.56998}, +{11.8878,13.7671,-5.11518,-4.23808}, +{10.0073,10.2574,11.282,12.9297}, +{10.5778,11.703,0.629406,0.965262}, +{3.17349,7.96657,16.1782,17.2631}, +{11.2281,13.6998,12.2002,12.4339}, +{13.7166,18.3124,19.2669,21.4145}, +{10.5388,15.0813,0.328298,4.33324}, +{9.05987,12.0136,-1.29945,-0.356432}, +{6.74526,7.05518,-8.26859,-7.79509}, +{17.7736,20.6859,5.72768,8.29825}, +{2.22113,7.1491,21.4284,25.7683}, +{16.1247,17.7842,2.70437,3.3773}, +{8.34023,10.0276,13.9827,18.7779}, +{15.1872,18.2348,17.1787,17.2902}, +{16.5308,17.6299,6.45799,8.71682}, +{5.98601,9.22204,23.2905,26.0581}, +{7.64095,10.7424,18.778,22.0208}, +{15.0585,19.52,17.7993,19.2668}, +{17.646,20.037,0.451228,3.78949}, +{0.0160052,1.94859,4.68464,6.71885}, +{7.29434,9.17489,13.9827,17.3136}, +{17.7896,21.639,6.02609,9.48842}, +{4.43065,8.71164,19.8528,23.2904}, +{16.5231,21.0708,3.3774,4.59677}, +{14.2096,16.0172,17.282,17.9522}, +{8.32648,9.09478,3.98524,7.65693}, +{3.6703,7.6841,0.583351,4.90782}, +{9.90605,10.9591,11.5162,13.1508}, +{14.7669,18.5129,-1.21482,3.3773}, +{3.48104,6.74301,29.5066,30.5551}, +{9.22657,10.4539,-5.59946,-1.29955}, +{8.12181,8.34154,-2.11601,1.66416}, +{4.11375,5.37752,30.5552,34.3283}, +{9.11434,12.5991,8.88212,10.4297}, +{11.3365,14.9133,-8.77796,-4.9549}, +{15.7809,16.0235,-2.30357,0.667869}, +{15.4629,16.7224,4.59687,6.45789}, +{13.3766,16.7042,21.4146,25.1652}, +{7.87643,10.2361,12.8464,13.9826}, +{7.38842,11.7536,11.5162,16.479}, +{5.15799,9.74446,-7.42668,-4.32738}, +{16.0009,16.044,-3.82308,0.667869}, +{15.6318,18.7733,8.71692,11.607}, +{10.7258,12.2305,7.30879,8.88202}, +{8.17133,9.84923,-1.56988,1.38187}, +{3.5179,5.38762,0.583351,5.06301}, +{9.4516,10.8319,22.0209,26.7891}, +{9.94456,11.8221,19.9812,21.2926}, +{5.14479,8.31779,3.92878,7.65693}, +{14.6057,18.2633,0.667969,4.59677}, +{5.62784,8.67939,17.3137,19.4264}, +{10.9244,13.5481,-1.29955,-1.29945}, +{5.76759,6.30746,-3.722,-3.5131}, +{7.13259,9.6258,8.33774,11.5161}, +{1.05144,1.32443,10.359,10.9074}, +{16.4807,19.9127,26.5036,27.9052}, +{5.9629,7.66553,-1.41052,-1.14028}, +{13.6489,16.9728,22.2084,25.5279}, +{2.50777,4.43837,19.8193,21.4283}, +{1.57577,3.7409,15.383,18.2258}, +{17.1816,18.8466,17.2903,17.7992}, +{8.43156,13.0154,-4.9548,-3.13422}, +{1.88827,6.19077,6.98588,10.347}, +{14.73,15.2147,17.9523,18.7923}, +{5.55742,8.69305,2.0611,3.92868}}; +unsigned n11=130; +double test12[][4]={ +{4.92744,6.6604,4.27234,8.301}, +{1.54924,2.51053,4.48526,9.19033}, +{1.55587,5.56226,-0.660563,3.35611}, +{1.87055,2.251,3.56944,6.75421}, +{1.58179,2.94863,5.24022,8.78858}, +{1.88069,5.98638,3.94188,5.24012}, +{1.81447,5.62383,5.24022,9.22211}, +{4.06842,6.37182,-0.053975,3.94178}, +{4.03643,4.2387,3.35621,3.94178}, +{1.16362,3.67328,0.29063,3.01001}, +}; +unsigned n12=10; +int main() { + double c,t; + vector<Rectangle*> rs; + cout << "test1" << endl; + test(generateRects(test1,n1,rs),c,t); + cout << "test2" << endl; + test(generateRects(test2,n2,rs),c,t); + cout << "test3" << endl; + test(generateRects(test3,n3,rs),c,t); + cout << "test4" << endl; + test(generateRects(test4,n4,rs),c,t); + cout << "test5" << endl; + test(generateRects(test5,n5,rs),c,t); + cout << "test6" << endl; + test(generateRects(test6,n6,rs),c,t); + cout << "test7" << endl; + test(generateRects(test7,n7,rs),c,t); + cout << "test8" << endl; + test(generateRects(test8,n8,rs),c,t); + cout << "test9" << endl; + test(generateRects(test9,n9,rs),c,t); + cout << "test10" << endl; + test(generateRects(test10,n10,rs),c,t); + cout << "test11" << endl; + test(generateRects(test11,n11,rs),c,t); + cout << "test12" << endl; + test(generateRects(test12,n12,rs),c,t); + int max_size=100, repeats=100,step=10; + //srand(time(nullptr)); + for(int i=10;i<=max_size;i+=step) { + //if(i%5==0) cout << i << endl; + double disp=0, time=0; + for(int repeat=repeats;repeat--;) { + vector<Rectangle*> rs; + generateRandomRects(i,rs); + //printRects(rs); + test(rs,c,t); + disp+=c; + time+=t; + } + disp/=repeats; + time/=repeats; + cout << i << "," << time << "," << disp << endl; + } + return 0; +} diff --git a/src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp b/src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp new file mode 100644 index 0000000..60aeb09 --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp @@ -0,0 +1,666 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +#include <algorithm> +#include <cstdio> +#include <ctime> +#include <cmath> +#include <cassert> + +using namespace std; +using namespace vpsc; + +static inline double getRand(const int range) { + return (double)range*rand()/(RAND_MAX+1.0); +} +inline bool approxEquals(const double a, const double b) { + return fabs((double)a-b)<0.01; +} +typedef vector<Constraint*> CS; + +bool checkResult(unsigned n, Variable *a[], unsigned m, Constraint *c[], double expected[]=nullptr) { + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); +#ifdef MOSEK_AVAILABLE + //printf("Checking with mosek..."); + MosekEnv* menv = mosek_init_sep_ls(n,c,m); + float *b=new float[n]; + float *x=new float[n]; + for(unsigned i=0;i<n;i++) { + b[i]=a[i]->desiredPosition; + } + mosek_quad_solve_sep(menv,b,x); + mosek_delete(menv); +#endif + for(unsigned i=0;i<n;i++) { + char s=','; + if(i==n-1) s='\n'; +#ifdef MOSEK_AVAILABLE + //printf("%f(%f)%c",a[i]->finalPosition,x[i],s); + if(!(approxEquals(a[i]->finalPosition,x[i]))) { + return false; + } + assert(approxEquals(a[i]->finalPosition,x[i])); +#endif + if(expected) assert(approxEquals(a[i]->finalPosition,expected[i])); + } +#ifdef MOSEK_AVAILABLE + delete [] b; + delete [] x; +#endif + return true; +} +void dumpMatlabProblem(unsigned n, Variable *a[], unsigned m, Constraint *c[]){ + printf("H=2*eye(%d);\n",n); + printf("f=-2*[ "); + for(unsigned i=0;i<n;i++) { + printf("%f ",a[i]->desiredPosition); + } + printf("];\n"); + printf("s=[ "); + for(unsigned i=0;i<n;i++) { + printf("%f ",a[i]->scale); + } + printf("];\n"); + printf("C=zeros(%d,%d);\n",m,n); + for(unsigned i=0;i<m;i++) { + printf("C(%d,[%d %d])=[1 -1];\n",i+1,c[i]->left->id+1,c[i]->right->id+1); + } + printf("A=C*diag(s);\n"); + printf("b=[ "); + for(unsigned i=0;i<m;i++) { + printf("%f ",-1.*c[i]->gap); + } + printf("];\n"); + printf("quadprog(H,f,A,b)\n"); +} +void test1() { + cout << "Test 1..." << endl; + Variable *a[] = { + new Variable(0,2,1,1.), + new Variable(1,9,1,1), + new Variable(2,9,1,1), + new Variable(3,9,1,1), + new Variable(4,2,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[1],3), + new Constraint(a[1],a[2],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={1.4,4.4,7.4,7.4,10.4}; + checkResult(n,a,m,c,expected); + cout << "Test 1... done." << endl; +} +void test1a() { + cout << "Test 1a..." << endl; + /* matlab: + H=2*eye(2) + f=[0 0] + A=[ 2 -1 ] + b=[ -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,0,1,2.), + new Variable(1,0,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={-0.8,0.4}; + checkResult(n,a,m,c,expected); + cout << "Test 1a... done." << endl; +} +void test1b() { + cout << "Test 1b..." << endl; + /* matlab: + H=2*eye(2) + f=[0 0] + A=[ 1 -2 ] + b=[ -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,0,1,1.), + new Variable(1,0,1,2)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={-0.4,0.8}; + checkResult(n,a,m,c,expected); + cout << "Test 1b... done." << endl; +} +void test1c() { + cout << "Test 1c..." << endl; + /* matlab: + H=2*eye(3) + f=-2*[ 1 1 1 ] + s=[ 3 2 4 ] + C=zeros(2,3) + C(1,1:2)=[1 -1] + C(2,2:3)=[1 -1] + A=C*diag(s) + b=[-2 -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,1,1,3), + new Variable(1,1,1,2), + new Variable(2,1,1,4)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2), + new Constraint(a[1],a[2],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={0.2623, 1.3934, 1.1967}; + checkResult(n,a,m,c,expected); + cout << "Test 1c... done." << endl; +} + +// no splits required +void test2() { + cout << "Test 2..." << endl; + Variable *a[] = { + new Variable(0,4,1), + new Variable(1,6,1), + new Variable(2,9,1), + new Variable(3,2,1), + new Variable(4,5,1)}; + Constraint *c[] = { + new Constraint(a[0],a[2],3), + new Constraint(a[0],a[3],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3)}; + double expected[]={0.5,6,3.5,6.5,9.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 2... done." << endl; +} + +// split required +void test3() { + /* matlab: + H=2*eye(5) + f=-2*[ 5 6 7 4 3 ] + s=[ 1 1 1 1 1 ] + C=zeros(5,5) + C(1,[1 5])=[1 -1] + C(2,[2 3])=[1 -1] + C(3,[3 4])=[1 -1] + C(4,[3 5])=[1 -1] + C(5,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(5,1) + quadprog(H,f,A,b) + */ + cout << "Test 3..." << endl; + Variable *a[] = { + new Variable(0,5,1), + new Variable(1,6,1), + new Variable(2,7,1), + new Variable(3,4,1), + new Variable(4,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[1],a[2],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + double expected[]={5,0.5,3.5,6.5,9.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 3... done." << endl; +} +// split required +void test4() { + /* matlab: + H=2*eye(5) + f=-2*[ 7 1 6 0 2 ] + s=[ 5 8 3 1 7 ] + C=zeros(6,5) + C(1,[1 4])=[1 -1] + C(2,[1 2])=[1 -1] + C(3,[2 5])=[1 -1] + C(4,[3 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(6,1) + quadprog(H,f,A,b) + */ + cout << "Test 4..." << endl; + Variable *a[] = { + new Variable(0,7,1,1), + new Variable(1,1,1,1), + new Variable(2,6,1,1), + new Variable(3,0,1,1), + new Variable(4,2,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[3],3), + new Constraint(a[0],a[1],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3)}; + double expected[]={0.8,3.8,0.8,3.8,6.8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 4... done." << endl; +} +void test5() { + cout << "Test 5..." << endl; + Variable *a[] = { + new Variable(0,0,1), new Variable(1,9,1), new + Variable(2,1,1), new Variable(3,9,1), new + Variable(4,5,1), new Variable(5,1,1), new + Variable(6,2,1), new Variable(7,1,1), new + Variable(8,6,1), new Variable(9,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[3],3), new Constraint(a[1],a[8],3), + new Constraint(a[1],a[6],3), new Constraint(a[2],a[6],3), + new Constraint(a[3],a[5],3), new Constraint(a[3],a[6],3), + new Constraint(a[3],a[7],3), new Constraint(a[4],a[8],3), + new Constraint(a[4],a[7],3), new Constraint(a[5],a[8],3), + new Constraint(a[5],a[7],3), new Constraint(a[5],a[8],3), + new Constraint(a[6],a[9],3), new Constraint(a[7],a[8],3), + new Constraint(a[7],a[9],3), new Constraint(a[8],a[9],3) + }; + double expected[]={-3.71429,4,1,-0.714286,2.28571,2.28571,7,5.28571,8.28571,11.2857}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 5... done." << endl; +} +void test6() { + cout << "Test 6..." << endl; + Variable *a[] = { + new Variable(0,7,1), + new Variable(1,0,1), + new Variable(2,3,1), + new Variable(3,1,1), + new Variable(4,4,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[3],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-0.75,0,2.25,5.25,8.25}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 6... done." << endl; +} +void test7() { + cout << "Test 7..." << endl; + Variable *a[] = { + new Variable(0,4,1), + new Variable(1,2,1), + new Variable(2,3,1), + new Variable(3,1,1), + new Variable(4,8,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[3],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-0.5,2,2.5,5.5,8.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 7... done." << endl; +} +void test8() { + /* matlab: + H=2*eye(5) + f=-2*[ 3 4 0 5 6 ] + s=[ 1 1 1 1 1 ] + C=zeros(6,5) + C(1,[1 2])=[1 -1] + C(2,[1 3])=[1 -1] + C(3,[2 3])=[1 -1] + C(4,[2 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(6,1) + quadprog(H,f,A,b) + */ + // This cycles when using the heuristic of merging on the least + // violated, violated constraint first. + cout << "Test 8..." << endl; + Variable *a[] = { + new Variable(0,3,1), + new Variable(1,4,1), + new Variable(2,0,1), + new Variable(3,5,1), + new Variable(4,6,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[1],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-2.4,0.6,3.6,6.6,9.6}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 8... done." << endl; +} +void test9() { + /* matlab: + H=2*eye(5) + f=-2*[ 8 2 6 5 3 ] + s=[ 1 1 1 1 1 ] + C=zeros(7,5) + C(1,[1 5])=[1 -1] + C(2,[1 4])=[1 -1] + C(3,[2 3])=[1 -1] + C(4,[2 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[3 5])=[1 -1] + C(7,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(7,1) + quadprog(H,f,A,b) + */ + cout << "Test 9..." << endl; + Variable *a[] = { + new Variable(0,8,1), + new Variable(1,2,1), + new Variable(2,6,1), + new Variable(3,5,1), + new Variable(4,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[3],3), + new Constraint(a[1],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + double expected[]={3.6,0.6,3.6,6.6,9.6}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 9... done." << endl; +} + +void test10() { + cout << "Test 10..." << endl; + Variable *a[] = { + new Variable(0,8.56215,1,4.99888), +new Variable(1,1.27641,1,8.06009), +new Variable(2,6.28523,1,1.06585), +new Variable(3,4.09743,1,0.924166), +new Variable(4,0.369025,1,6.12702)}; + + Constraint *c[] = { + new Constraint(a[0],a[2],3), +new Constraint(a[0],a[1],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 10... done." << endl; +} +void test11() { + cout << "Test 11..." << endl; + Variable *a[] = { + new Variable(0,1.31591,1,9.02545), +new Variable(1,1.48155,1,3.68918), +new Variable(2,3.5091,1,2.07033), +new Variable(3,3.47131,1,8.75145), +new Variable(4,0.77374,1,0.967941)}; + + Constraint *c[] = { +new Constraint(a[0],a[3],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 11... done." << endl; +} +void test12() { + cout << "Test 12..." << endl; + Variable *a[] = { +new Variable(0,2.83063,1,6.67901), +new Variable(1,6.81696,1,7.28642), +new Variable(2,9.27616,1,0.918345), +new Variable(3,3.4094,1,3.39673), +new Variable(4,2.92492,1,2.36269)}; + + Constraint *c[] = { +new Constraint(a[0],a[3],3), +new Constraint(a[0],a[2],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 12... done." << endl; +} +void test13() { + cout << "Test 13..." << endl; + Variable *a[] = { +new Variable(0,0.485024,1,1), +new Variable(1,3.52714,1,1), +new Variable(2,4.01263,1,1), +new Variable(3,4.58524,1,1), +new Variable(4,5.40796,1,1)}; + + Constraint *c[] = { +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[2],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[3],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + assert(checkResult(n,a,m,c,nullptr)); + cout << "Test 13... done." << endl; +} + +// n=number vars +// m=max constraints per var +void rand_test(unsigned n, unsigned m) { + Variable **a=new Variable*[n]; + CS cs; + for(unsigned i=0;i<n;i++) { + a[i]=new Variable(i,getRand(10),1,1);//getRand(10)); + } + for(unsigned i=0;i<n-1;i++) { + for(int j=0;j<getRand(m)+1;j++) { + int e = static_cast<int>(i + getRand(n-1-i)+1); + cs.push_back(new Constraint(a[i],a[e],3)); + } + } + Constraint **acs=new Constraint*[cs.size()]; + for(unsigned i=0;i<cs.size();i++) { + acs[i]=cs[i]; + } + try { + if(!checkResult(n,a,cs.size(),acs)) { + throw "Check failed!"; + } + } catch (char const *msg) { + cout << msg << endl; + cout<<"digraph g {"<<endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + Constraint *c=*i; + cout << c->left->id << "->" << c->right->id << ";" << endl; + } + cout<<"}"<<endl; + for(unsigned i=0;i<n;i++) { + if(i!=0) cout << "," << endl; + cout << "new Variable("<<i<<","<<a[i]->desiredPosition<< ",1," + << a[i]->scale <<")"; + //cout << "a[i]->Pos="<<a[i]->position() << endl; + } + cout << "};" << endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + if(i!=cs.begin()) cout << "," << endl; + Constraint *c=*i; + //cout << c->left->id << "->" << c->right->id << ";" << endl; + cout << "new Constraint(a[" << c->left->id << "],a[" << c->right->id << "],3)"; + + } + cout << "};" << endl; + throw "test failed!"; + } + /* + for(unsigned i=0;i<n;i++) { + a[i]->desiredPosition=getRand(10); + } + vpsc.solve(); + try { + if(!checkResult(n,a,m,acs)) { + throw "2nd Check failed!"; + } + } catch (char const *msg) { + cout << msg << endl; + for(unsigned i=0;i<n;i++) { + if(i!=0) cout << "," << endl; + cout << "new Variable("<<i<<","<<a[i]->desiredPosition<< ",1)"; + //cout << "a[i]->Pos="<<a[i]->position() << endl; + } + cout << "};" << endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + if(i!=cs.begin()) cout << "," << endl; + Constraint *c=*i; + //cout << c->left->id << "->" << c->right->id << ";" << endl; + cout << "new Constraint(a[" << c->left->id << "],a[" << c->right->id << "],3)"; + + } + cout << "};" << endl; + throw "test failed!"; + } + */ + for_each(a,a+n,delete_object()); + delete [] a; + for_each(cs.begin(),cs.end(),delete_object()); + delete [] acs; +} +int main() { + srand(time(nullptr)); + test10(); + test2(); + test3(); + test4(); + test5(); + test6(); + test7(); + test8(); + test9(); + test10(); + test11(); + test12(); + test13(); + for(int i=0;i<1000;i++) { + if(i%100==0) cout << "i=" << i << endl; + rand_test(100,3); + } + for(int i=0;i<10000;i++) { + if(i%100==0) cout << "i=" << i << endl; + rand_test(5,3); + } + return 0; +} |