1 #include"lp_solver_skeleton.h" |
1 #include<lemon/lp_solver_skeleton.h> |
2 #include"lp_glpk.h" |
2 #include<lemon/lp_glpk.h> |
3 #include<lemon/list_graph.h> |
|
4 |
3 |
5 using namespace lemon; |
4 using namespace lemon; |
6 |
5 |
7 void lpTest(LpSolverBase & lp) |
6 void lpTest(LpSolverBase & lp) |
8 { |
7 { |
9 typedef LpSolverBase LP; |
8 typedef LpSolverBase LP; |
10 |
9 |
11 std::vector<LP::Col> x; |
10 std::vector<LP::Col> x(10); |
12 for(int i=0;i<10;i++) x.push_back(lp.addCol()); |
11 // for(int i=0;i<10;i++) x.push_back(lp.addCol()); |
|
12 lp.addColSet(x); |
13 |
13 |
14 std::vector<LP::Col> y(10); |
14 std::vector<LP::Col> y(10); |
15 lp.addColSet(y); |
15 lp.addColSet(y); |
16 |
16 |
17 std::map<int,LP::Col> z; |
17 std::map<int,LP::Col> z; |
121 |
121 |
122 lp.addRow(x[1]+x[3]<=x[5]-3); |
122 lp.addRow(x[1]+x[3]<=x[5]-3); |
123 lp.addRow(-7<=x[1]+x[3]-12<=3); |
123 lp.addRow(-7<=x[1]+x[3]-12<=3); |
124 lp.addRow(x[1]<=x[5]); |
124 lp.addRow(x[1]<=x[5]); |
125 |
125 |
126 } |
|
127 |
126 |
128 |
|
129 template<class G,class C> |
|
130 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) |
|
131 { |
|
132 LpGlpk lp; |
|
133 |
127 |
134 typedef G Graph; |
|
135 typedef typename G::Node Node; |
|
136 typedef typename G::NodeIt NodeIt; |
|
137 typedef typename G::Edge Edge; |
|
138 typedef typename G::EdgeIt EdgeIt; |
|
139 typedef typename G::OutEdgeIt OutEdgeIt; |
|
140 typedef typename G::InEdgeIt InEdgeIt; |
|
141 |
|
142 typename G::template EdgeMap<LpGlpk::Col> x(g); |
|
143 lp.addColSet(x); |
|
144 |
|
145 for(EdgeIt e(g);e!=INVALID;++e) { |
|
146 lp.colUpperBound(x[e],cap[e]); |
|
147 lp.colLowerBound(x[e],0); |
|
148 } |
|
149 |
|
150 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
|
151 LpGlpk::Expr ex; |
|
152 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
|
153 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
|
154 lp.addRow(ex==0); |
|
155 } |
|
156 { |
|
157 LpGlpk::Expr ex; |
|
158 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; |
|
159 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; |
|
160 lp.setObj(ex); |
|
161 } |
|
162 |
|
163 lp.solve(); |
|
164 |
|
165 return 0; |
|
166 } |
128 } |
167 |
129 |
168 int main() |
130 int main() |
169 { |
131 { |
170 LpSolverSkeleton lp_skel; |
132 LpSolverSkeleton lp_skel; |
171 LpGlpk lp_glpk; |
133 LpGlpk lp_glpk; |
172 |
134 |
173 lpTest(lp_skel); |
135 lpTest(lp_skel); |
174 lpTest(lp_glpk); |
136 lpTest(lp_glpk); |
175 |
137 |
176 ListGraph g; |
138 return 0; |
177 ListGraph::Node s=g.addNode(); |
|
178 ListGraph::Node t=g.addNode(); |
|
179 |
|
180 ListGraph::EdgeMap<double> cap(g); |
|
181 |
|
182 maxFlow(g,cap,s,t); |
|
183 |
|
184 } |
139 } |