32 typedef typename G::Edge Edge; |
32 typedef typename G::Edge Edge; |
33 typedef typename G::EdgeIt EdgeIt; |
33 typedef typename G::EdgeIt EdgeIt; |
34 typedef typename G::OutEdgeIt OutEdgeIt; |
34 typedef typename G::OutEdgeIt OutEdgeIt; |
35 typedef typename G::InEdgeIt InEdgeIt; |
35 typedef typename G::InEdgeIt InEdgeIt; |
36 |
36 |
|
37 //Define a map on the edges for the variables of the LP problem |
37 typename G::template EdgeMap<LpDefault::Col> x(g); |
38 typename G::template EdgeMap<LpDefault::Col> x(g); |
38 lp.addColSet(x); |
39 lp.addColSet(x); |
39 |
40 |
|
41 //Nonnegativity and capacity constraints |
40 for(EdgeIt e(g);e!=INVALID;++e) { |
42 for(EdgeIt e(g);e!=INVALID;++e) { |
41 lp.colUpperBound(x[e],cap[e]); |
43 lp.colUpperBound(x[e],cap[e]); |
42 lp.colLowerBound(x[e],0); |
44 lp.colLowerBound(x[e],0); |
43 } |
45 } |
44 |
46 |
|
47 |
|
48 //Flow conservation constraints for the nodes (except for 's' and 't') |
45 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
49 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
46 LpDefault::Expr ex; |
50 LpDefault::Expr ex; |
47 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
51 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
48 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
52 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
49 lp.addRow(ex==0); |
53 lp.addRow(ex==0); |
50 } |
54 } |
|
55 |
|
56 //Objective function: the flow value entering 't' |
51 { |
57 { |
52 LpDefault::Expr ex; |
58 LpDefault::Expr ex; |
53 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; |
59 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; |
54 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; |
60 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; |
55 lp.setObj(ex); |
61 lp.setObj(ex); |
56 } |
62 } |
|
63 |
|
64 //Maximization |
57 lp.max(); |
65 lp.max(); |
58 |
66 |
59 #ifdef HAVE_GLPK |
67 #ifdef HAVE_GLPK |
60 lp.presolver(true); |
68 lp.presolver(true); |
61 lp.messageLevel(3); |
69 lp.messageLevel(3); |
62 #endif |
70 #endif |
63 |
71 |
|
72 //Solve with the underlying solver |
64 lp.solve(); |
73 lp.solve(); |
65 |
74 |
66 return lp.primalValue(); |
75 return lp.primalValue(); |
67 } |
76 } |
68 |
77 |