312 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
312 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
313 "The flow type of CapacityScaling must be signed"); |
313 "The flow type of CapacityScaling must be signed"); |
314 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
314 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
315 "The cost type of CapacityScaling must be signed"); |
315 "The cost type of CapacityScaling must be signed"); |
316 |
316 |
|
317 // Reset data structures |
|
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 CapacityScaling& 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 CapacityScaling& 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 CapacityScaling& 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 CapacityScaling& 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 CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { |
|
425 for (int i = 0; i != _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 /// CapacityScaling<ListDigraph> cs(graph); |
|
448 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) |
|
449 /// .supplyMap(sup).run(); |
|
450 /// \endcode |
|
451 /// |
|
452 /// This function can be called more than once. All the given parameters |
|
453 /// are kept for the next call, unless \ref resetParams() or \ref reset() |
|
454 /// is used, thus only the modified parameters have to be set again. |
|
455 /// If the underlying digraph was also modified after the construction |
|
456 /// of the class (or the last \ref reset() call), then the \ref reset() |
|
457 /// function must be called. |
|
458 /// |
|
459 /// \param factor The capacity scaling factor. It must be larger than |
|
460 /// one to use scaling. If it is less or equal to one, then scaling |
|
461 /// will be disabled. |
|
462 /// |
|
463 /// \return \c INFEASIBLE if no feasible flow exists, |
|
464 /// \n \c OPTIMAL if the problem has optimal solution |
|
465 /// (i.e. it is feasible and bounded), and the algorithm has found |
|
466 /// optimal flow and node potentials (primal and dual solutions), |
|
467 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost |
|
468 /// and infinite upper bound. It means that the objective function |
|
469 /// is unbounded on that arc, however, note that it could actually be |
|
470 /// bounded over the feasible flows, but this algroithm cannot handle |
|
471 /// these cases. |
|
472 /// |
|
473 /// \see ProblemType |
|
474 /// \see resetParams(), reset() |
|
475 ProblemType run(int factor = 4) { |
|
476 _factor = factor; |
|
477 ProblemType pt = init(); |
|
478 if (pt != OPTIMAL) return pt; |
|
479 return start(); |
|
480 } |
|
481 |
|
482 /// \brief Reset all the parameters that have been given before. |
|
483 /// |
|
484 /// This function resets all the paramaters that have been given |
|
485 /// before using functions \ref lowerMap(), \ref upperMap(), |
|
486 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). |
|
487 /// |
|
488 /// It is useful for multiple \ref run() calls. Basically, all the given |
|
489 /// parameters are kept for the next \ref run() call, unless |
|
490 /// \ref resetParams() or \ref reset() is used. |
|
491 /// If the underlying digraph was also modified after the construction |
|
492 /// of the class or the last \ref reset() call, then the \ref reset() |
|
493 /// function must be used, otherwise \ref resetParams() is sufficient. |
|
494 /// |
|
495 /// For example, |
|
496 /// \code |
|
497 /// CapacityScaling<ListDigraph> cs(graph); |
|
498 /// |
|
499 /// // First run |
|
500 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) |
|
501 /// .supplyMap(sup).run(); |
|
502 /// |
|
503 /// // Run again with modified cost map (resetParams() is not called, |
|
504 /// // so only the cost map have to be set again) |
|
505 /// cost[e] += 100; |
|
506 /// cs.costMap(cost).run(); |
|
507 /// |
|
508 /// // Run again from scratch using resetParams() |
|
509 /// // (the lower bounds will be set to zero on all arcs) |
|
510 /// cs.resetParams(); |
|
511 /// cs.upperMap(capacity).costMap(cost) |
|
512 /// .supplyMap(sup).run(); |
|
513 /// \endcode |
|
514 /// |
|
515 /// \return <tt>(*this)</tt> |
|
516 /// |
|
517 /// \see reset(), run() |
|
518 CapacityScaling& resetParams() { |
|
519 for (int i = 0; i != _node_num; ++i) { |
|
520 _supply[i] = 0; |
|
521 } |
|
522 for (int j = 0; j != _res_arc_num; ++j) { |
|
523 _lower[j] = 0; |
|
524 _upper[j] = INF; |
|
525 _cost[j] = _forward[j] ? 1 : -1; |
|
526 } |
|
527 _have_lower = false; |
|
528 return *this; |
|
529 } |
|
530 |
|
531 /// \brief Reset the internal data structures and all the parameters |
|
532 /// that have been given before. |
|
533 /// |
|
534 /// This function resets the internal data structures and all the |
|
535 /// paramaters that have been given before using functions \ref lowerMap(), |
|
536 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). |
|
537 /// |
|
538 /// It is useful for multiple \ref run() calls. Basically, all the given |
|
539 /// parameters are kept for the next \ref run() call, unless |
|
540 /// \ref resetParams() or \ref reset() is used. |
|
541 /// If the underlying digraph was also modified after the construction |
|
542 /// of the class or the last \ref reset() call, then the \ref reset() |
|
543 /// function must be used, otherwise \ref resetParams() is sufficient. |
|
544 /// |
|
545 /// See \ref resetParams() for examples. |
|
546 /// |
|
547 /// \return <tt>(*this)</tt> |
|
548 /// |
|
549 /// \see resetParams(), run() |
|
550 CapacityScaling& reset() { |
317 // Resize vectors |
551 // Resize vectors |
318 _node_num = countNodes(_graph); |
552 _node_num = countNodes(_graph); |
319 _arc_num = countArcs(_graph); |
553 _arc_num = countArcs(_graph); |
320 _res_arc_num = 2 * (_arc_num + _node_num); |
554 _res_arc_num = 2 * (_arc_num + _node_num); |
321 _root = _node_num; |
555 _root = _node_num; |
375 _reverse[fi] = bi; |
609 _reverse[fi] = bi; |
376 _reverse[bi] = fi; |
610 _reverse[bi] = fi; |
377 } |
611 } |
378 |
612 |
379 // Reset parameters |
613 // Reset parameters |
380 reset(); |
614 resetParams(); |
381 } |
|
382 |
|
383 /// \name Parameters |
|
384 /// The parameters of the algorithm can be specified using these |
|
385 /// functions. |
|
386 |
|
387 /// @{ |
|
388 |
|
389 /// \brief Set the lower bounds on the arcs. |
|
390 /// |
|
391 /// This function sets the lower bounds on the arcs. |
|
392 /// If it is not used before calling \ref run(), the lower bounds |
|
393 /// will be set to zero on all arcs. |
|
394 /// |
|
395 /// \param map An arc map storing the lower bounds. |
|
396 /// Its \c Value type must be convertible to the \c Value type |
|
397 /// of the algorithm. |
|
398 /// |
|
399 /// \return <tt>(*this)</tt> |
|
400 template <typename LowerMap> |
|
401 CapacityScaling& lowerMap(const LowerMap& map) { |
|
402 _have_lower = true; |
|
403 for (ArcIt a(_graph); a != INVALID; ++a) { |
|
404 _lower[_arc_idf[a]] = map[a]; |
|
405 _lower[_arc_idb[a]] = map[a]; |
|
406 } |
|
407 return *this; |
|
408 } |
|
409 |
|
410 /// \brief Set the upper bounds (capacities) on the arcs. |
|
411 /// |
|
412 /// This function sets the upper bounds (capacities) on the arcs. |
|
413 /// If it is not used before calling \ref run(), the upper bounds |
|
414 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
|
415 /// unbounded from above). |
|
416 /// |
|
417 /// \param map An arc map storing the upper bounds. |
|
418 /// Its \c Value type must be convertible to the \c Value type |
|
419 /// of the algorithm. |
|
420 /// |
|
421 /// \return <tt>(*this)</tt> |
|
422 template<typename UpperMap> |
|
423 CapacityScaling& upperMap(const UpperMap& map) { |
|
424 for (ArcIt a(_graph); a != INVALID; ++a) { |
|
425 _upper[_arc_idf[a]] = map[a]; |
|
426 } |
|
427 return *this; |
|
428 } |
|
429 |
|
430 /// \brief Set the costs of the arcs. |
|
431 /// |
|
432 /// This function sets the costs of the arcs. |
|
433 /// If it is not used before calling \ref run(), the costs |
|
434 /// will be set to \c 1 on all arcs. |
|
435 /// |
|
436 /// \param map An arc map storing the costs. |
|
437 /// Its \c Value type must be convertible to the \c Cost type |
|
438 /// of the algorithm. |
|
439 /// |
|
440 /// \return <tt>(*this)</tt> |
|
441 template<typename CostMap> |
|
442 CapacityScaling& costMap(const CostMap& map) { |
|
443 for (ArcIt a(_graph); a != INVALID; ++a) { |
|
444 _cost[_arc_idf[a]] = map[a]; |
|
445 _cost[_arc_idb[a]] = -map[a]; |
|
446 } |
|
447 return *this; |
|
448 } |
|
449 |
|
450 /// \brief Set the supply values of the nodes. |
|
451 /// |
|
452 /// This function sets the supply values of the nodes. |
|
453 /// If neither this function nor \ref stSupply() is used before |
|
454 /// calling \ref run(), the supply of each node will be set to zero. |
|
455 /// |
|
456 /// \param map A node map storing the supply values. |
|
457 /// Its \c Value type must be convertible to the \c Value type |
|
458 /// of the algorithm. |
|
459 /// |
|
460 /// \return <tt>(*this)</tt> |
|
461 template<typename SupplyMap> |
|
462 CapacityScaling& supplyMap(const SupplyMap& map) { |
|
463 for (NodeIt n(_graph); n != INVALID; ++n) { |
|
464 _supply[_node_id[n]] = map[n]; |
|
465 } |
|
466 return *this; |
|
467 } |
|
468 |
|
469 /// \brief Set single source and target nodes and a supply value. |
|
470 /// |
|
471 /// This function sets a single source node and a single target node |
|
472 /// and the required flow value. |
|
473 /// If neither this function nor \ref supplyMap() is used before |
|
474 /// calling \ref run(), the supply of each node will be set to zero. |
|
475 /// |
|
476 /// Using this function has the same effect as using \ref supplyMap() |
|
477 /// with such a map in which \c k is assigned to \c s, \c -k is |
|
478 /// assigned to \c t and all other nodes have zero supply value. |
|
479 /// |
|
480 /// \param s The source node. |
|
481 /// \param t The target node. |
|
482 /// \param k The required amount of flow from node \c s to node \c t |
|
483 /// (i.e. the supply of \c s and the demand of \c t). |
|
484 /// |
|
485 /// \return <tt>(*this)</tt> |
|
486 CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { |
|
487 for (int i = 0; i != _node_num; ++i) { |
|
488 _supply[i] = 0; |
|
489 } |
|
490 _supply[_node_id[s]] = k; |
|
491 _supply[_node_id[t]] = -k; |
|
492 return *this; |
|
493 } |
|
494 |
|
495 /// @} |
|
496 |
|
497 /// \name Execution control |
|
498 /// The algorithm can be executed using \ref run(). |
|
499 |
|
500 /// @{ |
|
501 |
|
502 /// \brief Run the algorithm. |
|
503 /// |
|
504 /// This function runs the algorithm. |
|
505 /// The paramters can be specified using functions \ref lowerMap(), |
|
506 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). |
|
507 /// For example, |
|
508 /// \code |
|
509 /// CapacityScaling<ListDigraph> cs(graph); |
|
510 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) |
|
511 /// .supplyMap(sup).run(); |
|
512 /// \endcode |
|
513 /// |
|
514 /// This function can be called more than once. All the parameters |
|
515 /// that have been given are kept for the next call, unless |
|
516 /// \ref reset() is called, thus only the modified parameters |
|
517 /// have to be set again. See \ref reset() for examples. |
|
518 /// However, the underlying digraph must not be modified after this |
|
519 /// class have been constructed, since it copies and extends the graph. |
|
520 /// |
|
521 /// \param factor The capacity scaling factor. It must be larger than |
|
522 /// one to use scaling. If it is less or equal to one, then scaling |
|
523 /// will be disabled. |
|
524 /// |
|
525 /// \return \c INFEASIBLE if no feasible flow exists, |
|
526 /// \n \c OPTIMAL if the problem has optimal solution |
|
527 /// (i.e. it is feasible and bounded), and the algorithm has found |
|
528 /// optimal flow and node potentials (primal and dual solutions), |
|
529 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost |
|
530 /// and infinite upper bound. It means that the objective function |
|
531 /// is unbounded on that arc, however, note that it could actually be |
|
532 /// bounded over the feasible flows, but this algroithm cannot handle |
|
533 /// these cases. |
|
534 /// |
|
535 /// \see ProblemType |
|
536 ProblemType run(int factor = 4) { |
|
537 _factor = factor; |
|
538 ProblemType pt = init(); |
|
539 if (pt != OPTIMAL) return pt; |
|
540 return start(); |
|
541 } |
|
542 |
|
543 /// \brief Reset all the parameters that have been given before. |
|
544 /// |
|
545 /// This function resets all the paramaters that have been given |
|
546 /// before using functions \ref lowerMap(), \ref upperMap(), |
|
547 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). |
|
548 /// |
|
549 /// It is useful for multiple run() calls. If this function is not |
|
550 /// used, all the parameters given before are kept for the next |
|
551 /// \ref run() call. |
|
552 /// However, the underlying digraph must not be modified after this |
|
553 /// class have been constructed, since it copies and extends the graph. |
|
554 /// |
|
555 /// For example, |
|
556 /// \code |
|
557 /// CapacityScaling<ListDigraph> cs(graph); |
|
558 /// |
|
559 /// // First run |
|
560 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) |
|
561 /// .supplyMap(sup).run(); |
|
562 /// |
|
563 /// // Run again with modified cost map (reset() is not called, |
|
564 /// // so only the cost map have to be set again) |
|
565 /// cost[e] += 100; |
|
566 /// cs.costMap(cost).run(); |
|
567 /// |
|
568 /// // Run again from scratch using reset() |
|
569 /// // (the lower bounds will be set to zero on all arcs) |
|
570 /// cs.reset(); |
|
571 /// cs.upperMap(capacity).costMap(cost) |
|
572 /// .supplyMap(sup).run(); |
|
573 /// \endcode |
|
574 /// |
|
575 /// \return <tt>(*this)</tt> |
|
576 CapacityScaling& reset() { |
|
577 for (int i = 0; i != _node_num; ++i) { |
|
578 _supply[i] = 0; |
|
579 } |
|
580 for (int j = 0; j != _res_arc_num; ++j) { |
|
581 _lower[j] = 0; |
|
582 _upper[j] = INF; |
|
583 _cost[j] = _forward[j] ? 1 : -1; |
|
584 } |
|
585 _have_lower = false; |
|
586 return *this; |
615 return *this; |
587 } |
616 } |
588 |
617 |
589 /// @} |
618 /// @} |
590 |
619 |