19 namespace lemon { |
19 namespace lemon { |
20 |
20 |
21 template<typename Edge, typename EdgeIndexMap> |
21 template<typename Edge, typename EdgeIndexMap> |
22 class PrimalMap { |
22 class PrimalMap { |
23 protected: |
23 protected: |
24 LPSolverWrapper* lp; |
24 LPGLPK* lp; |
25 EdgeIndexMap* edge_index_map; |
25 EdgeIndexMap* edge_index_map; |
26 public: |
26 public: |
27 PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) : |
27 PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) : |
28 lp(&_lp), edge_index_map(&_edge_index_map) { } |
28 lp(&_lp), edge_index_map(&_edge_index_map) { } |
29 double operator[](Edge e) const { |
29 double operator[](Edge e) const { |
30 return lp->getPrimal((*edge_index_map)[e]); |
30 return lp->getPrimal((*edge_index_map)[e]); |
31 } |
31 } |
32 }; |
32 }; |
209 min_cost_flow.getFlow()[ewww]); |
209 min_cost_flow.getFlow()[ewww]); |
210 } |
210 } |
211 return (min_cost_flow.flowValue()>=expected); |
211 return (min_cost_flow.flowValue()>=expected); |
212 } |
212 } |
213 void runByLP() { |
213 void runByLP() { |
214 typedef LPSolverWrapper LPSolver; |
214 typedef LPGLPK LPSolver; |
215 LPSolver lp; |
215 LPSolver lp; |
216 lp.setMinimize(); |
216 lp.setMinimize(); |
217 typedef LPSolver::ColIt ColIt; |
217 typedef LPSolver::ColIt ColIt; |
218 typedef LPSolver::RowIt RowIt; |
218 typedef LPSolver::RowIt RowIt; |
219 typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap; |
219 typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap; |
221 PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map); |
221 PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map); |
222 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { |
222 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { |
223 ColIt col_it=lp.addCol(); |
223 ColIt col_it=lp.addCol(); |
224 edge_index_map.set(e, col_it); |
224 edge_index_map.set(e, col_it); |
225 if (lcapacity[e]==capacity[e]) |
225 if (lcapacity[e]==capacity[e]) |
226 lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]); |
226 lp.setColBounds(col_it, LPSolver::FIXED, lcapacity[e], capacity[e]); |
227 else |
227 else |
228 lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]); |
228 lp.setColBounds(col_it, LPSolver::DOUBLE, lcapacity[e], capacity[e]); |
229 lp.setObjCoef(col_it, cost[e]); |
229 lp.setObjCoef(col_it, cost[e]); |
230 } |
230 } |
231 LPSolver::ColIt col_it; |
231 LPSolver::ColIt col_it; |
232 for (lp.col_iter_map.first(col_it, lp.VALID_CLASS); |
232 for (lp.col_iter_map.first(col_it, lp.VALID_CLASS); |
233 lp.col_iter_map.valid(col_it); |
233 lp.col_iter_map.valid(col_it); |
234 lp.col_iter_map.next(col_it)) { |
234 lp.col_iter_map.next(col_it)) { |
235 std::cout << "ize " << lp.col_iter_map[col_it] << std::endl; |
235 // std::cout << "ize " << lp.col_iter_map[col_it] << std::endl; |
236 } |
236 } |
237 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { |
237 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { |
238 typename Graph::template EdgeMap<Num> coeffs(g, 0); |
238 typename Graph::template EdgeMap<Num> coeffs(g, 0); |
239 for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) |
239 for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) |
240 coeffs.set(e, coeffs[e]+1); |
240 coeffs.set(e, coeffs[e]+1); |
248 //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e]; |
248 //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e]; |
249 row.push_back(std::make_pair(edge_index_map[e], coeffs[e])); |
249 row.push_back(std::make_pair(edge_index_map[e], coeffs[e])); |
250 } |
250 } |
251 } |
251 } |
252 //std::cout << std::endl; |
252 //std::cout << std::endl; |
253 std::cout << " " << g.id(n) << " " << row.size() << std::endl; |
253 //std::cout << " " << g.id(n) << " " << row.size() << std::endl; |
254 lp.setRowCoeffs(row_it, row.begin(), row.end()); |
254 lp.setRowCoeffs(row_it, row.begin(), row.end()); |
255 lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0); |
255 lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0); |
256 } |
256 } |
257 lp.solveSimplex(); |
257 lp.solveSimplex(); |
258 //std::cout << lp.colNum() << std::endl; |
258 //std::cout << lp.colNum() << std::endl; |
259 //std::cout << lp.rowNum() << std::endl; |
259 //std::cout << lp.rowNum() << std::endl; |
260 //std::cout << "flow value: "<< lp.getObjVal() << std::endl; |
260 //std::cout << "flow value: "<< lp.getObjVal() << std::endl; |