diff -r d8475431bbbb -r 8e85e6bbefdf src/demo/lp_maxflow_demo.cc --- a/src/demo/lp_maxflow_demo.cc Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,86 +0,0 @@ -#ifdef HAVE_CONFIG_H -#include -#endif - -#include -#include - - -#ifdef HAVE_GLPK -#include -#elif HAVE_CPLEX -#include -#endif - -using namespace lemon; - -#ifdef HAVE_GLPK -typedef LpGlpk LpDefault; -#elif HAVE_CPLEX -typedef LpCplex LpDefault; -#endif - - -template -double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) -{ - LpDefault lp; - - typedef G Graph; - typedef typename G::Node Node; - typedef typename G::NodeIt NodeIt; - typedef typename G::Edge Edge; - typedef typename G::EdgeIt EdgeIt; - typedef typename G::OutEdgeIt OutEdgeIt; - typedef typename G::InEdgeIt InEdgeIt; - - typename G::template EdgeMap x(g); - lp.addColSet(x); - - for(EdgeIt e(g);e!=INVALID;++e) { - lp.colUpperBound(x[e],cap[e]); - lp.colLowerBound(x[e],0); - } - - for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { - LpDefault::Expr ex; - for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; - for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; - lp.addRow(ex==0); - } - { - LpDefault::Expr ex; - for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; - for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; - lp.setObj(ex); - } - lp.max(); - -#ifdef HAVE_GLPK - lp.presolver(true); - lp.messageLevel(3); -#endif - - lp.solve(); - - return lp.primalValue(); -} - -int main() -{ - ListGraph g; - ListGraph::Node s; - ListGraph::Node t; - - ListGraph::EdgeMap cap(g); - - GraphReader reader(std::cin,g); - reader.readNode("source",s).readNode("target",t) - .readEdgeMap("capacity",cap).run(); - - // std::ifstream file("../test/preflow_"); -// readDimacs(file, g, cap, s, t); - - std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl; - -}