diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp')
| -rw-r--r-- | src/3rdparty/adaptagrams/libvpsc/tests/satisfy_inc.cpp | 666 |
1 files changed, 666 insertions, 0 deletions
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; +} |