src/work/athos/lp/lp_test.cc
changeset 1271 40e5d0d44a65
parent 1263 a490938ad0aa
child 1272 17be4c5bc6c6
equal deleted inserted replaced
3:c76ad79ec316 4:5c66517a74b9
     1 #include"lp_solver_skeleton.h"
     1 #include"lp_solver_skeleton.h"
     2 #include"lp_glpk.h"
     2 #include"lp_glpk.h"
       
     3 #include<lemon/list_graph.h>
     3 
     4 
     4 using namespace lemon;
     5 using namespace lemon;
     5 
     6 
     6 void lpTest(LpSolverBase & lp)
     7 void lpTest(LpSolverBase & lp)
     7 {
     8 {
    34   lp.addRow(LP::INF,e,23);
    35   lp.addRow(LP::INF,e,23);
    35   lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
    36   lp.addRow(LP::INF,3.0*(p1+p2)-p3,23);
    36   lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
    37   lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
    37   lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23);
    38   lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23);
    38   lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
    39   lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
       
    40 
       
    41   lp.addRow(x[1]+x[3]<=x[5]-3);
       
    42   lp.addRow(-7<=x[1]+x[3]-12<=3);
    39 }
    43 }
    40 
    44 
       
    45 
       
    46 template<class G,class C>
       
    47 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
       
    48 {
       
    49   LpGlpk lp;
       
    50   
       
    51   typedef G Graph;
       
    52   typedef typename G::Node Node;
       
    53   typedef typename G::NodeIt NodeIt;
       
    54   typedef typename G::Edge Edge;
       
    55   typedef typename G::EdgeIt EdgeIt;
       
    56   typedef typename G::OutEdgeIt OutEdgeIt;
       
    57   typedef typename G::InEdgeIt InEdgeIt;
       
    58   
       
    59   typename G::EdgeMap<LpGlpk::Col> x(g);
       
    60   // lp.addColSet(x);
       
    61   for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol();
       
    62   
       
    63   for(EdgeIt e(g);e!=INVALID;++e) {
       
    64     lp.setColUpperBound(x[e],cap[e]);
       
    65     lp.setColLowerBound(x[e],0);
       
    66   }
       
    67 
       
    68   for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
       
    69     LpGlpk::Expr ex;
       
    70     for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
       
    71     for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
       
    72     lp.addRow(0,ex,0);
       
    73   }
       
    74   {
       
    75     LpGlpk::Expr ex;
       
    76     for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
       
    77     for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
       
    78     lp.setObj(ex);
       
    79   }
       
    80 
       
    81   lp.solve();
       
    82 
       
    83   return 0;
       
    84 }
    41 
    85 
    42 int main() 
    86 int main() 
    43 {
    87 {
    44   LpSolverSkeleton lp_skel;
    88   LpSolverSkeleton lp_skel;
    45   LpGlpk lp_glpk;
    89   LpGlpk lp_glpk;
    46 
    90 
    47   lpTest(lp_skel);
    91   lpTest(lp_skel);
    48   lpTest(lp_glpk);
    92   lpTest(lp_glpk);
       
    93 
       
    94   ListGraph g;
       
    95   ListGraph::EdgeMap<double> cap(g);
       
    96   
       
    97   maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g));
       
    98 
    49 }
    99 }