Added support for building deb packages.
5 #include<lemon/graph_reader.h>
6 #include<lemon/list_graph.h>
10 #include <lemon/lp_glpk.h>
12 #include <lemon/lp_cplex.h>
15 using namespace lemon;
18 typedef LpGlpk LpDefault;
20 typedef LpCplex LpDefault;
24 template<class G,class C>
25 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
30 typedef typename G::Node Node;
31 typedef typename G::NodeIt NodeIt;
32 typedef typename G::Edge Edge;
33 typedef typename G::EdgeIt EdgeIt;
34 typedef typename G::OutEdgeIt OutEdgeIt;
35 typedef typename G::InEdgeIt InEdgeIt;
37 typename G::template EdgeMap<LpDefault::Col> x(g);
40 for(EdgeIt e(g);e!=INVALID;++e) {
41 lp.colUpperBound(x[e],cap[e]);
42 lp.colLowerBound(x[e],0);
45 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
47 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
48 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
53 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e];
54 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
66 return lp.primalValue();
75 ListGraph::EdgeMap<double> cap(g);
77 GraphReader<ListGraph> reader(std::cin,g);
78 reader.readNode("source",s).readNode("target",t)
79 .readEdgeMap("capacity",cap).run();
81 // std::ifstream file("../test/preflow_");
82 // readDimacs(file, g, cap, s, t);
84 std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl;