Changeset 898:75c97c3786d6 in lemon for lemon/cycle_canceling.h
- Timestamp:
- 02/10/10 19:05:20 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cycle_canceling.h
r886 r898 251 251 "The cost type of CycleCanceling must be signed"); 252 252 253 // Reset data structures 254 reset(); 255 } 256 257 /// \name Parameters 258 /// The parameters of the algorithm can be specified using these 259 /// functions. 260 261 /// @{ 262 263 /// \brief Set the lower bounds on the arcs. 264 /// 265 /// This function sets the lower bounds on the arcs. 266 /// If it is not used before calling \ref run(), the lower bounds 267 /// will be set to zero on all arcs. 268 /// 269 /// \param map An arc map storing the lower bounds. 270 /// Its \c Value type must be convertible to the \c Value type 271 /// of the algorithm. 272 /// 273 /// \return <tt>(*this)</tt> 274 template <typename LowerMap> 275 CycleCanceling& lowerMap(const LowerMap& map) { 276 _have_lower = true; 277 for (ArcIt a(_graph); a != INVALID; ++a) { 278 _lower[_arc_idf[a]] = map[a]; 279 _lower[_arc_idb[a]] = map[a]; 280 } 281 return *this; 282 } 283 284 /// \brief Set the upper bounds (capacities) on the arcs. 285 /// 286 /// This function sets the upper bounds (capacities) on the arcs. 287 /// If it is not used before calling \ref run(), the upper bounds 288 /// will be set to \ref INF on all arcs (i.e. the flow value will be 289 /// unbounded from above). 290 /// 291 /// \param map An arc map storing the upper bounds. 292 /// Its \c Value type must be convertible to the \c Value type 293 /// of the algorithm. 294 /// 295 /// \return <tt>(*this)</tt> 296 template<typename UpperMap> 297 CycleCanceling& upperMap(const UpperMap& map) { 298 for (ArcIt a(_graph); a != INVALID; ++a) { 299 _upper[_arc_idf[a]] = map[a]; 300 } 301 return *this; 302 } 303 304 /// \brief Set the costs of the arcs. 305 /// 306 /// This function sets the costs of the arcs. 307 /// If it is not used before calling \ref run(), the costs 308 /// will be set to \c 1 on all arcs. 309 /// 310 /// \param map An arc map storing the costs. 311 /// Its \c Value type must be convertible to the \c Cost type 312 /// of the algorithm. 313 /// 314 /// \return <tt>(*this)</tt> 315 template<typename CostMap> 316 CycleCanceling& costMap(const CostMap& map) { 317 for (ArcIt a(_graph); a != INVALID; ++a) { 318 _cost[_arc_idf[a]] = map[a]; 319 _cost[_arc_idb[a]] = -map[a]; 320 } 321 return *this; 322 } 323 324 /// \brief Set the supply values of the nodes. 325 /// 326 /// This function sets the supply values of the nodes. 327 /// If neither this function nor \ref stSupply() is used before 328 /// calling \ref run(), the supply of each node will be set to zero. 329 /// 330 /// \param map A node map storing the supply values. 331 /// Its \c Value type must be convertible to the \c Value type 332 /// of the algorithm. 333 /// 334 /// \return <tt>(*this)</tt> 335 template<typename SupplyMap> 336 CycleCanceling& supplyMap(const SupplyMap& map) { 337 for (NodeIt n(_graph); n != INVALID; ++n) { 338 _supply[_node_id[n]] = map[n]; 339 } 340 return *this; 341 } 342 343 /// \brief Set single source and target nodes and a supply value. 344 /// 345 /// This function sets a single source node and a single target node 346 /// and the required flow value. 347 /// If neither this function nor \ref supplyMap() is used before 348 /// calling \ref run(), the supply of each node will be set to zero. 349 /// 350 /// Using this function has the same effect as using \ref supplyMap() 351 /// with such a map in which \c k is assigned to \c s, \c -k is 352 /// assigned to \c t and all other nodes have zero supply value. 353 /// 354 /// \param s The source node. 355 /// \param t The target node. 356 /// \param k The required amount of flow from node \c s to node \c t 357 /// (i.e. the supply of \c s and the demand of \c t). 358 /// 359 /// \return <tt>(*this)</tt> 360 CycleCanceling& stSupply(const Node& s, const Node& t, Value k) { 361 for (int i = 0; i != _res_node_num; ++i) { 362 _supply[i] = 0; 363 } 364 _supply[_node_id[s]] = k; 365 _supply[_node_id[t]] = -k; 366 return *this; 367 } 368 369 /// @} 370 371 /// \name Execution control 372 /// The algorithm can be executed using \ref run(). 373 374 /// @{ 375 376 /// \brief Run the algorithm. 377 /// 378 /// This function runs the algorithm. 379 /// The paramters can be specified using functions \ref lowerMap(), 380 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 381 /// For example, 382 /// \code 383 /// CycleCanceling<ListDigraph> cc(graph); 384 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 385 /// .supplyMap(sup).run(); 386 /// \endcode 387 /// 388 /// This function can be called more than once. All the given parameters 389 /// are kept for the next call, unless \ref resetParams() or \ref reset() 390 /// is used, thus only the modified parameters have to be set again. 391 /// If the underlying digraph was also modified after the construction 392 /// of the class (or the last \ref reset() call), then the \ref reset() 393 /// function must be called. 394 /// 395 /// \param method The cycle-canceling method that will be used. 396 /// For more information, see \ref Method. 397 /// 398 /// \return \c INFEASIBLE if no feasible flow exists, 399 /// \n \c OPTIMAL if the problem has optimal solution 400 /// (i.e. it is feasible and bounded), and the algorithm has found 401 /// optimal flow and node potentials (primal and dual solutions), 402 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 403 /// and infinite upper bound. It means that the objective function 404 /// is unbounded on that arc, however, note that it could actually be 405 /// bounded over the feasible flows, but this algroithm cannot handle 406 /// these cases. 407 /// 408 /// \see ProblemType, Method 409 /// \see resetParams(), reset() 410 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 411 ProblemType pt = init(); 412 if (pt != OPTIMAL) return pt; 413 start(method); 414 return OPTIMAL; 415 } 416 417 /// \brief Reset all the parameters that have been given before. 418 /// 419 /// This function resets all the paramaters that have been given 420 /// before using functions \ref lowerMap(), \ref upperMap(), 421 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 422 /// 423 /// It is useful for multiple \ref run() calls. Basically, all the given 424 /// parameters are kept for the next \ref run() call, unless 425 /// \ref resetParams() or \ref reset() is used. 426 /// If the underlying digraph was also modified after the construction 427 /// of the class or the last \ref reset() call, then the \ref reset() 428 /// function must be used, otherwise \ref resetParams() is sufficient. 429 /// 430 /// For example, 431 /// \code 432 /// CycleCanceling<ListDigraph> cs(graph); 433 /// 434 /// // First run 435 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 436 /// .supplyMap(sup).run(); 437 /// 438 /// // Run again with modified cost map (resetParams() is not called, 439 /// // so only the cost map have to be set again) 440 /// cost[e] += 100; 441 /// cc.costMap(cost).run(); 442 /// 443 /// // Run again from scratch using resetParams() 444 /// // (the lower bounds will be set to zero on all arcs) 445 /// cc.resetParams(); 446 /// cc.upperMap(capacity).costMap(cost) 447 /// .supplyMap(sup).run(); 448 /// \endcode 449 /// 450 /// \return <tt>(*this)</tt> 451 /// 452 /// \see reset(), run() 453 CycleCanceling& resetParams() { 454 for (int i = 0; i != _res_node_num; ++i) { 455 _supply[i] = 0; 456 } 457 int limit = _first_out[_root]; 458 for (int j = 0; j != limit; ++j) { 459 _lower[j] = 0; 460 _upper[j] = INF; 461 _cost[j] = _forward[j] ? 1 : -1; 462 } 463 for (int j = limit; j != _res_arc_num; ++j) { 464 _lower[j] = 0; 465 _upper[j] = INF; 466 _cost[j] = 0; 467 _cost[_reverse[j]] = 0; 468 } 469 _have_lower = false; 470 return *this; 471 } 472 473 /// \brief Reset the internal data structures and all the parameters 474 /// that have been given before. 475 /// 476 /// This function resets the internal data structures and all the 477 /// paramaters that have been given before using functions \ref lowerMap(), 478 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 479 /// 480 /// It is useful for multiple \ref run() calls. Basically, all the given 481 /// parameters are kept for the next \ref run() call, unless 482 /// \ref resetParams() or \ref reset() is used. 483 /// If the underlying digraph was also modified after the construction 484 /// of the class or the last \ref reset() call, then the \ref reset() 485 /// function must be used, otherwise \ref resetParams() is sufficient. 486 /// 487 /// See \ref resetParams() for examples. 488 /// 489 /// \return <tt>(*this)</tt> 490 /// 491 /// \see resetParams(), run() 492 CycleCanceling& reset() { 253 493 // Resize vectors 254 494 _node_num = countNodes(_graph); … … 316 556 317 557 // Reset parameters 318 reset(); 319 } 320 321 /// \name Parameters 322 /// The parameters of the algorithm can be specified using these 323 /// functions. 324 325 /// @{ 326 327 /// \brief Set the lower bounds on the arcs. 328 /// 329 /// This function sets the lower bounds on the arcs. 330 /// If it is not used before calling \ref run(), the lower bounds 331 /// will be set to zero on all arcs. 332 /// 333 /// \param map An arc map storing the lower bounds. 334 /// Its \c Value type must be convertible to the \c Value type 335 /// of the algorithm. 336 /// 337 /// \return <tt>(*this)</tt> 338 template <typename LowerMap> 339 CycleCanceling& lowerMap(const LowerMap& map) { 340 _have_lower = true; 341 for (ArcIt a(_graph); a != INVALID; ++a) { 342 _lower[_arc_idf[a]] = map[a]; 343 _lower[_arc_idb[a]] = map[a]; 344 } 345 return *this; 346 } 347 348 /// \brief Set the upper bounds (capacities) on the arcs. 349 /// 350 /// This function sets the upper bounds (capacities) on the arcs. 351 /// If it is not used before calling \ref run(), the upper bounds 352 /// will be set to \ref INF on all arcs (i.e. the flow value will be 353 /// unbounded from above). 354 /// 355 /// \param map An arc map storing the upper bounds. 356 /// Its \c Value type must be convertible to the \c Value type 357 /// of the algorithm. 358 /// 359 /// \return <tt>(*this)</tt> 360 template<typename UpperMap> 361 CycleCanceling& upperMap(const UpperMap& map) { 362 for (ArcIt a(_graph); a != INVALID; ++a) { 363 _upper[_arc_idf[a]] = map[a]; 364 } 365 return *this; 366 } 367 368 /// \brief Set the costs of the arcs. 369 /// 370 /// This function sets the costs of the arcs. 371 /// If it is not used before calling \ref run(), the costs 372 /// will be set to \c 1 on all arcs. 373 /// 374 /// \param map An arc map storing the costs. 375 /// Its \c Value type must be convertible to the \c Cost type 376 /// of the algorithm. 377 /// 378 /// \return <tt>(*this)</tt> 379 template<typename CostMap> 380 CycleCanceling& costMap(const CostMap& map) { 381 for (ArcIt a(_graph); a != INVALID; ++a) { 382 _cost[_arc_idf[a]] = map[a]; 383 _cost[_arc_idb[a]] = -map[a]; 384 } 385 return *this; 386 } 387 388 /// \brief Set the supply values of the nodes. 389 /// 390 /// This function sets the supply values of the nodes. 391 /// If neither this function nor \ref stSupply() is used before 392 /// calling \ref run(), the supply of each node will be set to zero. 393 /// 394 /// \param map A node map storing the supply values. 395 /// Its \c Value type must be convertible to the \c Value type 396 /// of the algorithm. 397 /// 398 /// \return <tt>(*this)</tt> 399 template<typename SupplyMap> 400 CycleCanceling& supplyMap(const SupplyMap& map) { 401 for (NodeIt n(_graph); n != INVALID; ++n) { 402 _supply[_node_id[n]] = map[n]; 403 } 404 return *this; 405 } 406 407 /// \brief Set single source and target nodes and a supply value. 408 /// 409 /// This function sets a single source node and a single target node 410 /// and the required flow value. 411 /// If neither this function nor \ref supplyMap() is used before 412 /// calling \ref run(), the supply of each node will be set to zero. 413 /// 414 /// Using this function has the same effect as using \ref supplyMap() 415 /// with such a map in which \c k is assigned to \c s, \c -k is 416 /// assigned to \c t and all other nodes have zero supply value. 417 /// 418 /// \param s The source node. 419 /// \param t The target node. 420 /// \param k The required amount of flow from node \c s to node \c t 421 /// (i.e. the supply of \c s and the demand of \c t). 422 /// 423 /// \return <tt>(*this)</tt> 424 CycleCanceling& stSupply(const Node& s, const Node& t, Value k) { 425 for (int i = 0; i != _res_node_num; ++i) { 426 _supply[i] = 0; 427 } 428 _supply[_node_id[s]] = k; 429 _supply[_node_id[t]] = -k; 430 return *this; 431 } 432 433 /// @} 434 435 /// \name Execution control 436 /// The algorithm can be executed using \ref run(). 437 438 /// @{ 439 440 /// \brief Run the algorithm. 441 /// 442 /// This function runs the algorithm. 443 /// The paramters can be specified using functions \ref lowerMap(), 444 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 445 /// For example, 446 /// \code 447 /// CycleCanceling<ListDigraph> cc(graph); 448 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 449 /// .supplyMap(sup).run(); 450 /// \endcode 451 /// 452 /// This function can be called more than once. All the parameters 453 /// that have been given are kept for the next call, unless 454 /// \ref reset() is called, thus only the modified parameters 455 /// have to be set again. See \ref reset() for examples. 456 /// However, the underlying digraph must not be modified after this 457 /// class have been constructed, since it copies and extends the graph. 458 /// 459 /// \param method The cycle-canceling method that will be used. 460 /// For more information, see \ref Method. 461 /// 462 /// \return \c INFEASIBLE if no feasible flow exists, 463 /// \n \c OPTIMAL if the problem has optimal solution 464 /// (i.e. it is feasible and bounded), and the algorithm has found 465 /// optimal flow and node potentials (primal and dual solutions), 466 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 467 /// and infinite upper bound. It means that the objective function 468 /// is unbounded on that arc, however, note that it could actually be 469 /// bounded over the feasible flows, but this algroithm cannot handle 470 /// these cases. 471 /// 472 /// \see ProblemType, Method 473 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 474 ProblemType pt = init(); 475 if (pt != OPTIMAL) return pt; 476 start(method); 477 return OPTIMAL; 478 } 479 480 /// \brief Reset all the parameters that have been given before. 481 /// 482 /// This function resets all the paramaters that have been given 483 /// before using functions \ref lowerMap(), \ref upperMap(), 484 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 485 /// 486 /// It is useful for multiple run() calls. If this function is not 487 /// used, all the parameters given before are kept for the next 488 /// \ref run() call. 489 /// However, the underlying digraph must not be modified after this 490 /// class have been constructed, since it copies and extends the graph. 491 /// 492 /// For example, 493 /// \code 494 /// CycleCanceling<ListDigraph> cs(graph); 495 /// 496 /// // First run 497 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 498 /// .supplyMap(sup).run(); 499 /// 500 /// // Run again with modified cost map (reset() is not called, 501 /// // so only the cost map have to be set again) 502 /// cost[e] += 100; 503 /// cc.costMap(cost).run(); 504 /// 505 /// // Run again from scratch using reset() 506 /// // (the lower bounds will be set to zero on all arcs) 507 /// cc.reset(); 508 /// cc.upperMap(capacity).costMap(cost) 509 /// .supplyMap(sup).run(); 510 /// \endcode 511 /// 512 /// \return <tt>(*this)</tt> 513 CycleCanceling& reset() { 514 for (int i = 0; i != _res_node_num; ++i) { 515 _supply[i] = 0; 516 } 517 int limit = _first_out[_root]; 518 for (int j = 0; j != limit; ++j) { 519 _lower[j] = 0; 520 _upper[j] = INF; 521 _cost[j] = _forward[j] ? 1 : -1; 522 } 523 for (int j = limit; j != _res_arc_num; ++j) { 524 _lower[j] = 0; 525 _upper[j] = INF; 526 _cost[j] = 0; 527 _cost[_reverse[j]] = 0; 528 } 529 _have_lower = false; 558 resetParams(); 530 559 return *this; 531 560 }
Note: See TracChangeset
for help on using the changeset viewer.