1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/demo/lp_maxflow_demo.cc Fri Apr 15 20:46:18 2005 +0000
1.3 @@ -0,0 +1,68 @@
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 + lp.max();
1.44 +
1.45 + lp.presolver(true);
1.46 +
1.47 + lp.messageLevel(3);
1.48 +
1.49 + lp.solve();
1.50 +
1.51 + return lp.primalValue();
1.52 +}
1.53 +
1.54 +int main()
1.55 +{
1.56 + ListGraph g;
1.57 + ListGraph::Node s;
1.58 + ListGraph::Node t;
1.59 +
1.60 + ListGraph::EdgeMap<double> cap(g);
1.61 +
1.62 + GraphReader<ListGraph> reader(std::cin,g);
1.63 + reader.addNode("source",s).addNode("target",t)
1.64 + .addEdgeMap("capacity",cap).run();
1.65 +
1.66 + // std::ifstream file("../test/preflow_");
1.67 +// readDimacs(file, g, cap, s, t);
1.68 +
1.69 + std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl;
1.70 +
1.71 +}