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 +}