1 #include<lemon/lp_glpk.h> |
|
2 #include<lemon/graph_reader.h> |
1 #include<lemon/graph_reader.h> |
3 #include<lemon/list_graph.h> |
2 #include<lemon/list_graph.h> |
4 |
3 |
|
4 |
|
5 #ifdef HAVE_GLPK |
|
6 #include <lemon/lp_glpk.h> |
|
7 #elif HAVE_CPLEX |
|
8 #include <lemon/lp_cplex.h> |
|
9 #endif |
|
10 |
5 using namespace lemon; |
11 using namespace lemon; |
|
12 |
|
13 #ifdef HAVE_GLPK |
|
14 typedef LpGlpk LpDefault; |
|
15 #elif HAVE_CPLEX |
|
16 typedef LpCplex LpDefault; |
|
17 #endif |
|
18 |
6 |
19 |
7 template<class G,class C> |
20 template<class G,class C> |
8 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) |
21 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) |
9 { |
22 { |
10 LpGlpk lp; |
23 LpDefault lp; |
11 |
24 |
12 typedef G Graph; |
25 typedef G Graph; |
13 typedef typename G::Node Node; |
26 typedef typename G::Node Node; |
14 typedef typename G::NodeIt NodeIt; |
27 typedef typename G::NodeIt NodeIt; |
15 typedef typename G::Edge Edge; |
28 typedef typename G::Edge Edge; |
16 typedef typename G::EdgeIt EdgeIt; |
29 typedef typename G::EdgeIt EdgeIt; |
17 typedef typename G::OutEdgeIt OutEdgeIt; |
30 typedef typename G::OutEdgeIt OutEdgeIt; |
18 typedef typename G::InEdgeIt InEdgeIt; |
31 typedef typename G::InEdgeIt InEdgeIt; |
19 |
32 |
20 typename G::template EdgeMap<LpGlpk::Col> x(g); |
33 typename G::template EdgeMap<LpDefault::Col> x(g); |
21 lp.addColSet(x); |
34 lp.addColSet(x); |
22 |
35 |
23 for(EdgeIt e(g);e!=INVALID;++e) { |
36 for(EdgeIt e(g);e!=INVALID;++e) { |
24 lp.colUpperBound(x[e],cap[e]); |
37 lp.colUpperBound(x[e],cap[e]); |
25 lp.colLowerBound(x[e],0); |
38 lp.colLowerBound(x[e],0); |
26 } |
39 } |
27 |
40 |
28 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
41 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
29 LpGlpk::Expr ex; |
42 LpDefault::Expr ex; |
30 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
43 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
31 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
44 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
32 lp.addRow(ex==0); |
45 lp.addRow(ex==0); |
33 } |
46 } |
34 { |
47 { |
35 LpGlpk::Expr ex; |
48 LpDefault::Expr ex; |
36 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; |
49 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; |
37 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; |
50 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; |
38 lp.setObj(ex); |
51 lp.setObj(ex); |
39 } |
52 } |
40 lp.max(); |
53 lp.max(); |
41 |
54 |
|
55 #ifdef HAVE_GLPK |
42 lp.presolver(true); |
56 lp.presolver(true); |
43 |
|
44 lp.messageLevel(3); |
57 lp.messageLevel(3); |
|
58 #endif |
45 |
59 |
46 lp.solve(); |
60 lp.solve(); |
47 |
61 |
48 return lp.primalValue(); |
62 return lp.primalValue(); |
49 } |
63 } |