Changeset 1264:92ba3e62825d in lemon-0.x for src
- Timestamp:
- 03/25/05 19:56:07 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1691
- Location:
- src/work/athos/lp
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/athos/lp/lin_expr.h
r1259 r1264 19 19 20 20 #include<vector> 21 22 23 21 #include<map> 24 22 #include<lemon/utility.h> 25 23 ///\file 26 24 ///\brief Classes to handle linear expressions … … 40 38 Coeff const_comp; 41 39 public: 40 typedef True IsLinExpression; 42 41 ///\e 43 42 SparseLinExpr() : Base(), const_comp(0) { } … … 263 262 /// 264 263 template <class V> 264 SparseLinExpr<V> operator+(const V &v,const typename V::ExprValue &c) { 265 SparseLinExpr<V> tmp(v); 266 tmp.constComp()=c; 267 return tmp; 268 } 269 270 ///\e 271 272 ///\relates SparseLinExpr 273 /// 274 template <class V> 275 SparseLinExpr<V> operator-(const V &v,const typename V::ExprValue &c) { 276 SparseLinExpr<V> tmp(v); 277 tmp.constComp()=-c; 278 return tmp; 279 } 280 281 ///\e 282 283 ///\relates SparseLinExpr 284 /// 285 template <class V> 286 SparseLinExpr<V> operator+(const typename V::ExprValue &c,const V &v) { 287 SparseLinExpr<V> tmp(v); 288 tmp.constComp()=c; 289 return tmp; 290 } 291 292 ///\e 293 294 ///\relates SparseLinExpr 295 /// 296 template <class V> 297 SparseLinExpr<V> operator-(const typename V::ExprValue &c,const V &v) { 298 SparseLinExpr<V> tmp(c); 299 tmp[v]=-1; 300 return tmp; 301 } 302 303 ///\e 304 305 ///\relates SparseLinExpr 306 /// 307 template <class V> 265 308 SparseLinExpr<V> operator+(const V &v1,const V &v2) { 266 309 SparseLinExpr<V> tmp(v1); … … 303 346 304 347 348 ////////////////////////////////////////////////////////////////////// 349 /// Constraints 350 ////////////////////////////////////////////////////////////////////// 351 352 template <class E> 353 class LinConstr 354 { 355 public: 356 typedef E Expr; 357 typedef typename E::Var Var; 358 typedef typename E::Coeff Coeff; 359 360 static const Coeff INF; 361 static const Coeff NaN; 362 // static const Coeff INF=0; 363 // static const Coeff NaN=1; 364 365 Expr expr; 366 Coeff lb,ub; 367 368 LinConstr() : expr(), lb(NaN), ub(NaN) {} 369 LinConstr(Coeff _lb,const Expr &e,Coeff _ub) : 370 expr(e), lb(_lb), ub(_ub) {} 371 LinConstr(const Expr &e,Coeff _ub) : 372 expr(e), lb(NaN), ub(_ub) {} 373 LinConstr(Coeff _lb,const Expr &e) : 374 expr(e), lb(_lb), ub(NaN) {} 375 }; 376 377 template<class E> 378 const typename LinConstr<E>::Coeff LinConstr<E>::INF= 379 std::numeric_limits<Coeff>::infinity(); 380 template<class E> 381 const typename LinConstr<E>::Coeff LinConstr<E>::NaN= 382 std::numeric_limits<Coeff>::quiet_NaN(); 383 384 385 template<class E> 386 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 387 operator<=(const E &e,const E &f) 388 { 389 return LinConstr<E>(-LinConstr<E>::INF,e-f,0); 390 } 391 392 template<class E> 393 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 394 operator>=(const E &e,const E &f) 395 { 396 return LinConstr<E>(-LinConstr<E>::INF,f-e,0); 397 } 398 399 template<class E> 400 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 401 operator==(const E &e,const E &f) 402 { 403 return LinConstr<E>(0,e-f,0); 404 } 405 406 ////////////////////////////// 407 408 template<class E> 409 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 410 operator<=(const E &e,const typename E::Coeff &n) 411 { 412 return LinConstr<E>(e,n); 413 } 414 415 template<class E> 416 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 417 operator>=(const E &e,const typename E::Coeff &n) 418 { 419 return LinConstr<E>(n,e); 420 } 421 422 template<class E> 423 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 424 operator==(const E &e,const typename E::Coeff &n) 425 { 426 return LinConstr<E>(n,e,n); 427 } 428 429 ////////////////////////////// 430 431 template<class E> 432 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 433 operator<=(const typename E::Coeff &n,const E &e) 434 { 435 return LinConstr<E>(n,e); 436 } 437 438 template<class E> 439 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 440 operator>=(const typename E::Coeff &n,const E &e) 441 { 442 return LinConstr<E>(e,n); 443 } 444 445 template<class E> 446 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 447 operator==(const typename E::Coeff &n,const E &e) 448 { 449 return LinConstr<E>(n,e,n); 450 } 451 452 ////////////////////////////// 453 454 template<class E> 455 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 456 operator<=(const typename E::Coeff &n,const LinConstr<E> &c) 457 { 458 LinConstr<E> tmp(c); 459 if(tmp.lb!=tmp.NaN) throw LogicError(); 460 else tmp.lb=n; 461 return tmp; 462 } 463 464 template<class E> 465 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 466 operator>=(const typename E::Coeff &n,const LinConstr<E> &c) 467 { 468 LinConstr<E> tmp(c); 469 if(tmp.ub!=tmp.NaN) throw LogicError(); 470 else tmp.ub=n; 471 return tmp; 472 } 473 474 template<class E> 475 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 476 operator<=(const LinConstr<E> &c,const typename E::Coeff &n) 477 { 478 LinConstr<E> tmp(c); 479 if(tmp.ub!=tmp.NaN) throw LogicError(); 480 else tmp.ub=n; 481 return tmp; 482 } 483 484 template<class E> 485 typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type 486 operator>=(const LinConstr<E> &c,const typename E::Coeff &n) 487 { 488 LinConstr<E> tmp(c); 489 if(tmp.lb!=tmp.NaN) throw LogicError(); 490 else tmp.lb=n; 491 return tmp; 492 } 493 494 495 305 496 } //namespace lemon 306 497 -
src/work/athos/lp/lp_base.cc
r1256 r1264 23 23 const LpSolverBase::Value 24 24 LpSolverBase::INF = std::numeric_limits<Value>::infinity(); 25 const LpSolverBase::Value 26 LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN(); 25 27 26 28 -
src/work/athos/lp/lp_base.h
r1263 r1264 117 117 ///The infinity constant 118 118 static const Value INF; 119 ///The not a number constant 120 static const Value NaN; 119 121 120 122 ///Refer to a column of the LP. … … 168 170 ///Linear expression 169 171 typedef SparseLinExpr<Col> Expr; 172 ///Linear constraint 173 typedef LinConstr<Expr> Constr; 170 174 171 175 protected: … … 319 323 } 320 324 325 ///Set a row (i.e a constaint) of the LP 326 327 ///\param r is the row to be modified 328 ///\param c is a linear expression (see \ref Constr) 329 ///\bug This is a temportary function. The interface will change to 330 ///a better one. 331 void setRow(Row r, const Constr &c) { 332 Value lb= c.lb==NaN?-INF:lb; 333 Value ub= c.ub==NaN?INF:lb; 334 setRow(r,lb,c.expr,ub); 335 } 336 321 337 ///Add a new row (i.e a new constaint) to the LP 322 338 … … 333 349 } 334 350 351 ///Add a new row (i.e a new constaint) to the LP 352 353 ///\param c is a linear expression (see \ref Constr) 354 ///\return The created row. 355 ///\bug This is a temportary function. The interface will change to 356 ///a better one. 357 Row addRow(const Constr &c) { 358 Row r=addRow(); 359 setRow(r,c); 360 return r; 361 } 362 335 363 /// Set the lower bound of a column (i.e a variable) 336 364 -
src/work/athos/lp/lp_test.cc
r1263 r1264 1 1 #include"lp_solver_skeleton.h" 2 2 #include"lp_glpk.h" 3 #include<lemon/list_graph.h> 3 4 4 5 using namespace lemon; … … 37 38 lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23); 38 39 lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23); 40 41 lp.addRow(x[1]+x[3]<=x[5]-3); 42 lp.addRow(-7<=x[1]+x[3]-12<=3); 39 43 } 40 44 45 46 template<class G,class C> 47 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) 48 { 49 LpGlpk lp; 50 51 typedef G Graph; 52 typedef typename G::Node Node; 53 typedef typename G::NodeIt NodeIt; 54 typedef typename G::Edge Edge; 55 typedef typename G::EdgeIt EdgeIt; 56 typedef typename G::OutEdgeIt OutEdgeIt; 57 typedef typename G::InEdgeIt InEdgeIt; 58 59 typename G::EdgeMap<LpGlpk::Col> x(g); 60 // lp.addColSet(x); 61 for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol(); 62 63 for(EdgeIt e(g);e!=INVALID;++e) { 64 lp.setColUpperBound(x[e],cap[e]); 65 lp.setColLowerBound(x[e],0); 66 } 67 68 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { 69 LpGlpk::Expr ex; 70 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; 71 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; 72 lp.addRow(0,ex,0); 73 } 74 { 75 LpGlpk::Expr ex; 76 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; 77 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; 78 lp.setObj(ex); 79 } 80 81 lp.solve(); 82 83 return 0; 84 } 41 85 42 86 int main() … … 47 91 lpTest(lp_skel); 48 92 lpTest(lp_glpk); 93 94 ListGraph g; 95 ListGraph::EdgeMap<double> cap(g); 96 97 maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g)); 98 49 99 }
Note: See TracChangeset
for help on using the changeset viewer.