1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/demo/lp_demo.cc Wed Apr 06 07:24:48 2005 +0000
1.3 @@ -0,0 +1,61 @@
1.4 +#include<lemon/lp_glpk.h>
1.5 +#include<lemon/graph_reader.h>
1.6 +#include<lemon/list_graph.h>
1.7 +
1.8 +using namespace lemon;
1.9 +
1.10 +template<class G,class C>
1.11 +double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
1.12 +{
1.13 + LpGlpk lp;
1.14 +
1.15 + typedef G Graph;
1.16 + typedef typename G::Node Node;
1.17 + typedef typename G::NodeIt NodeIt;
1.18 + typedef typename G::Edge Edge;
1.19 + typedef typename G::EdgeIt EdgeIt;
1.20 + typedef typename G::OutEdgeIt OutEdgeIt;
1.21 + typedef typename G::InEdgeIt InEdgeIt;
1.22 +
1.23 + typename G::template EdgeMap<LpGlpk::Col> x(g);
1.24 + lp.addColSet(x);
1.25 +
1.26 + for(EdgeIt e(g);e!=INVALID;++e) {
1.27 + lp.colUpperBound(x[e],cap[e]);
1.28 + lp.colLowerBound(x[e],0);
1.29 + }
1.30 +
1.31 + for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
1.32 + LpGlpk::Expr ex;
1.33 + for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
1.34 + for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
1.35 + lp.addRow(ex==0);
1.36 + }
1.37 + {
1.38 + LpGlpk::Expr ex;
1.39 + for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e];
1.40 + for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
1.41 + lp.setObj(ex);
1.42 + }
1.43 +
1.44 + lp.solve();
1.45 +
1.46 + return 0;
1.47 +}
1.48 +
1.49 +int main()
1.50 +{
1.51 + LpGlpk lp_glpk;
1.52 +
1.53 + ListGraph g;
1.54 + ListGraph::Node s=g.addNode();
1.55 + ListGraph::Node t=g.addNode();
1.56 +
1.57 + ListGraph::EdgeMap<double> cap(g);
1.58 +
1.59 + GraphReader<ListGraph> reader(std::cin,g);
1.60 + reader.addEdgeMap("capacity",cap).run();
1.61 +
1.62 + maxFlow(g,cap,s,t);
1.63 +
1.64 +}
2.1 --- a/src/test/Makefile.am Tue Apr 05 22:37:19 2005 +0000
2.2 +++ b/src/test/Makefile.am Wed Apr 06 07:24:48 2005 +0000
2.3 @@ -1,4 +1,5 @@
2.4 AM_CPPFLAGS = -I$(top_srcdir)/src
2.5 +LDADD = $(top_builddir)/src/lemon/libemon.la -lglpk
2.6
2.7 EXTRA_DIST = preflow_graph.dim dijkstra_test.lgf
2.8 noinst_HEADERS = \
2.9 @@ -17,6 +18,7 @@
2.10 graph_wrapper_test \
2.11 graph_utils_test \
2.12 kruskal_test \
2.13 + lp_test \
2.14 max_matching_test \
2.15 maps_test \
2.16 min_cost_flow_test \
2.17 @@ -41,6 +43,7 @@
2.18 graph_utils_test_SOURCES = graph_utils_test.cc
2.19 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
2.20 kruskal_test_SOURCES = kruskal_test.cc
2.21 +lp_test_SOURCES = lp_test.cc
2.22 maps_test_SOURCES = maps_test.cc
2.23 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
2.24 max_matching_test_SOURCES = max_matching_test.cc
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/test/lp_test.cc Wed Apr 06 07:24:48 2005 +0000
3.3 @@ -0,0 +1,139 @@
3.4 +#include<lemon/lp_solver_skeleton.h>
3.5 +#include<lemon/lp_glpk.h>
3.6 +
3.7 +using namespace lemon;
3.8 +
3.9 +void lpTest(LpSolverBase & lp)
3.10 +{
3.11 + typedef LpSolverBase LP;
3.12 +
3.13 + std::vector<LP::Col> x(10);
3.14 + // for(int i=0;i<10;i++) x.push_back(lp.addCol());
3.15 + lp.addColSet(x);
3.16 +
3.17 + std::vector<LP::Col> y(10);
3.18 + lp.addColSet(y);
3.19 +
3.20 + std::map<int,LP::Col> z;
3.21 +
3.22 + z.insert(std::make_pair(12,INVALID));
3.23 + z.insert(std::make_pair(2,INVALID));
3.24 + z.insert(std::make_pair(7,INVALID));
3.25 + z.insert(std::make_pair(5,INVALID));
3.26 +
3.27 + lp.addColSet(z);
3.28 +
3.29 +
3.30 + LP::Expr e,f,g;
3.31 + LP::Col p1,p2,p3,p4,p5;
3.32 + LP::Constr c;
3.33 +
3.34 + e[p1]=2;
3.35 + e.constComp()=12;
3.36 + e[p1]+=2;
3.37 + e.constComp()+=12;
3.38 + e[p1]-=2;
3.39 + e.constComp()-=12;
3.40 +
3.41 + e=2;
3.42 + e=2.2;
3.43 + e=p1;
3.44 + e=f;
3.45 +
3.46 + e+=2;
3.47 + e+=2.2;
3.48 + e+=p1;
3.49 + e+=f;
3.50 +
3.51 + e-=2;
3.52 + e-=2.2;
3.53 + e-=p1;
3.54 + e-=f;
3.55 +
3.56 + e*=2;
3.57 + e*=2.2;
3.58 + e/=2;
3.59 + e/=2.2;
3.60 +
3.61 + e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
3.62 + (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
3.63 + (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
3.64 + 2.2*f+f*2.2+f/2.2+
3.65 + 2*f+f*2+f/2+
3.66 + 2.2*p1+p1*2.2+p1/2.2+
3.67 + 2*p1+p1*2+p1/2
3.68 + );
3.69 +
3.70 +
3.71 + c = (e <= f );
3.72 + c = (e <= 2.2);
3.73 + c = (e <= 2 );
3.74 + c = (e <= p1 );
3.75 + c = (2.2<= f );
3.76 + c = (2 <= f );
3.77 + c = (p1 <= f );
3.78 + c = (p1 <= p2 );
3.79 + c = (p1 <= 2.2);
3.80 + c = (p1 <= 2 );
3.81 + c = (2.2<= p2 );
3.82 + c = (2 <= p2 );
3.83 +
3.84 + c = (e >= f );
3.85 + c = (e >= 2.2);
3.86 + c = (e >= 2 );
3.87 + c = (e >= p1 );
3.88 + c = (2.2>= f );
3.89 + c = (2 >= f );
3.90 + c = (p1 >= f );
3.91 + c = (p1 >= p2 );
3.92 + c = (p1 >= 2.2);
3.93 + c = (p1 >= 2 );
3.94 + c = (2.2>= p2 );
3.95 + c = (2 >= p2 );
3.96 +
3.97 + c = (e == f );
3.98 + c = (e == 2.2);
3.99 + c = (e == 2 );
3.100 + c = (e == p1 );
3.101 + c = (2.2== f );
3.102 + c = (2 == f );
3.103 + c = (p1 == f );
3.104 + //c = (p1 == p2 );
3.105 + c = (p1 == 2.2);
3.106 + c = (p1 == 2 );
3.107 + c = (2.2== p2 );
3.108 + c = (2 == p2 );
3.109 +
3.110 + c = (2 <= e <= 3);
3.111 + c = (2 <= p1<= 3);
3.112 +
3.113 + c = (2 >= e >= 3);
3.114 + c = (2 >= p1>= 3);
3.115 +
3.116 + e[x[3]]=2;
3.117 + e[x[3]]=4;
3.118 + e[x[3]]=1;
3.119 + e.constComp()=12;
3.120 +
3.121 + lp.addRow(LP::INF,e,23);
3.122 + lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
3.123 + lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
3.124 +
3.125 + lp.addRow(x[1]+x[3]<=x[5]-3);
3.126 + lp.addRow(-7<=x[1]+x[3]-12<=3);
3.127 + lp.addRow(x[1]<=x[5]);
3.128 +
3.129 +
3.130 +
3.131 +}
3.132 +
3.133 +int main()
3.134 +{
3.135 + LpSolverSkeleton lp_skel;
3.136 + LpGlpk lp_glpk;
3.137 +
3.138 + lpTest(lp_skel);
3.139 + lpTest(lp_glpk);
3.140 +
3.141 + return 0;
3.142 +}
4.1 --- a/src/work/athos/lp/lp_test.cc Tue Apr 05 22:37:19 2005 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,184 +0,0 @@
4.4 -#include"lp_solver_skeleton.h"
4.5 -#include"lp_glpk.h"
4.6 -#include<lemon/list_graph.h>
4.7 -
4.8 -using namespace lemon;
4.9 -
4.10 -void lpTest(LpSolverBase & lp)
4.11 -{
4.12 - typedef LpSolverBase LP;
4.13 -
4.14 - std::vector<LP::Col> x;
4.15 - for(int i=0;i<10;i++) x.push_back(lp.addCol());
4.16 -
4.17 - std::vector<LP::Col> y(10);
4.18 - lp.addColSet(y);
4.19 -
4.20 - std::map<int,LP::Col> z;
4.21 -
4.22 - z.insert(std::make_pair(12,INVALID));
4.23 - z.insert(std::make_pair(2,INVALID));
4.24 - z.insert(std::make_pair(7,INVALID));
4.25 - z.insert(std::make_pair(5,INVALID));
4.26 -
4.27 - lp.addColSet(z);
4.28 -
4.29 -
4.30 - LP::Expr e,f,g;
4.31 - LP::Col p1,p2,p3,p4,p5;
4.32 - LP::Constr c;
4.33 -
4.34 - e[p1]=2;
4.35 - e.constComp()=12;
4.36 - e[p1]+=2;
4.37 - e.constComp()+=12;
4.38 - e[p1]-=2;
4.39 - e.constComp()-=12;
4.40 -
4.41 - e=2;
4.42 - e=2.2;
4.43 - e=p1;
4.44 - e=f;
4.45 -
4.46 - e+=2;
4.47 - e+=2.2;
4.48 - e+=p1;
4.49 - e+=f;
4.50 -
4.51 - e-=2;
4.52 - e-=2.2;
4.53 - e-=p1;
4.54 - e-=f;
4.55 -
4.56 - e*=2;
4.57 - e*=2.2;
4.58 - e/=2;
4.59 - e/=2.2;
4.60 -
4.61 - e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
4.62 - (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
4.63 - (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
4.64 - 2.2*f+f*2.2+f/2.2+
4.65 - 2*f+f*2+f/2+
4.66 - 2.2*p1+p1*2.2+p1/2.2+
4.67 - 2*p1+p1*2+p1/2
4.68 - );
4.69 -
4.70 -
4.71 - c = (e <= f );
4.72 - c = (e <= 2.2);
4.73 - c = (e <= 2 );
4.74 - c = (e <= p1 );
4.75 - c = (2.2<= f );
4.76 - c = (2 <= f );
4.77 - c = (p1 <= f );
4.78 - c = (p1 <= p2 );
4.79 - c = (p1 <= 2.2);
4.80 - c = (p1 <= 2 );
4.81 - c = (2.2<= p2 );
4.82 - c = (2 <= p2 );
4.83 -
4.84 - c = (e >= f );
4.85 - c = (e >= 2.2);
4.86 - c = (e >= 2 );
4.87 - c = (e >= p1 );
4.88 - c = (2.2>= f );
4.89 - c = (2 >= f );
4.90 - c = (p1 >= f );
4.91 - c = (p1 >= p2 );
4.92 - c = (p1 >= 2.2);
4.93 - c = (p1 >= 2 );
4.94 - c = (2.2>= p2 );
4.95 - c = (2 >= p2 );
4.96 -
4.97 - c = (e == f );
4.98 - c = (e == 2.2);
4.99 - c = (e == 2 );
4.100 - c = (e == p1 );
4.101 - c = (2.2== f );
4.102 - c = (2 == f );
4.103 - c = (p1 == f );
4.104 - //c = (p1 == p2 );
4.105 - c = (p1 == 2.2);
4.106 - c = (p1 == 2 );
4.107 - c = (2.2== p2 );
4.108 - c = (2 == p2 );
4.109 -
4.110 - c = (2 <= e <= 3);
4.111 - c = (2 <= p1<= 3);
4.112 -
4.113 - c = (2 >= e >= 3);
4.114 - c = (2 >= p1>= 3);
4.115 -
4.116 - e[x[3]]=2;
4.117 - e[x[3]]=4;
4.118 - e[x[3]]=1;
4.119 - e.constComp()=12;
4.120 -
4.121 - lp.addRow(LP::INF,e,23);
4.122 - lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
4.123 - lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
4.124 -
4.125 - lp.addRow(x[1]+x[3]<=x[5]-3);
4.126 - lp.addRow(-7<=x[1]+x[3]-12<=3);
4.127 - lp.addRow(x[1]<=x[5]);
4.128 -
4.129 -}
4.130 -
4.131 -
4.132 -template<class G,class C>
4.133 -double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
4.134 -{
4.135 - LpGlpk lp;
4.136 -
4.137 - typedef G Graph;
4.138 - typedef typename G::Node Node;
4.139 - typedef typename G::NodeIt NodeIt;
4.140 - typedef typename G::Edge Edge;
4.141 - typedef typename G::EdgeIt EdgeIt;
4.142 - typedef typename G::OutEdgeIt OutEdgeIt;
4.143 - typedef typename G::InEdgeIt InEdgeIt;
4.144 -
4.145 - typename G::template EdgeMap<LpGlpk::Col> x(g);
4.146 - lp.addColSet(x);
4.147 -
4.148 - for(EdgeIt e(g);e!=INVALID;++e) {
4.149 - lp.colUpperBound(x[e],cap[e]);
4.150 - lp.colLowerBound(x[e],0);
4.151 - }
4.152 -
4.153 - for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
4.154 - LpGlpk::Expr ex;
4.155 - for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
4.156 - for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
4.157 - lp.addRow(ex==0);
4.158 - }
4.159 - {
4.160 - LpGlpk::Expr ex;
4.161 - for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e];
4.162 - for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
4.163 - lp.setObj(ex);
4.164 - }
4.165 -
4.166 - lp.solve();
4.167 -
4.168 - return 0;
4.169 -}
4.170 -
4.171 -int main()
4.172 -{
4.173 - LpSolverSkeleton lp_skel;
4.174 - LpGlpk lp_glpk;
4.175 -
4.176 - lpTest(lp_skel);
4.177 - lpTest(lp_glpk);
4.178 -
4.179 - ListGraph g;
4.180 - ListGraph::Node s=g.addNode();
4.181 - ListGraph::Node t=g.addNode();
4.182 -
4.183 - ListGraph::EdgeMap<double> cap(g);
4.184 -
4.185 - maxFlow(g,cap,s,t);
4.186 -
4.187 -}