COIN-OR::LEMON - Graph Library

Changeset 2457:8c791ee69a45 in lemon-0.x for lemon/cycle_canceling.h


Ignore:
Timestamp:
06/15/07 16:36:24 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3294
Message:

Improvments in min cost flow algorithms

  • improved cycle cancelling
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r2440 r2457  
    2323///
    2424/// \file
    25 /// \brief A cycle canceling algorithm for finding a minimum cost flow.
     25/// \brief A cycle-canceling algorithm for finding a minimum cost flow.
    2626
    2727#include <vector>
     
    2929#include <lemon/graph_adaptor.h>
    3030
    31 /// \brief The used cycle canceling method.
     31/// \brief The used cycle-canceling method.
    3232#define LIMITED_CYCLE_CANCELING
    3333//#define MIN_MEAN_CYCLE_CANCELING
     
    3737  /// \brief The maximum number of iterations for the first execution
    3838  /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
     39  /// It should be at least 2.
    3940  #define STARTING_LIMIT        2
    4041  /// \brief The iteration limit for the
    4142  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
    42   /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
     43  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
     44  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
    4345  #define ALPHA_MUL             3
    4446  /// \brief The iteration limit for the
    4547  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
    46   /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
     48  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
     49  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
    4750  #define ALPHA_DIV             2
    4851
    4952//#define _ONLY_ONE_CYCLE_
     53//#define _NO_BACK_STEP_
    5054//#define _DEBUG_ITER_
    5155#endif
     
    6165  /// @{
    6266
    63   /// \brief Implementation of a cycle canceling algorithm for finding
     67  /// \brief Implementation of a cycle-canceling algorithm for finding
    6468  /// a minimum cost flow.
    6569  ///
    66   /// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle
    67   /// canceling algorithm for finding a minimum cost flow.
     70  /// \ref lemon::CycleCanceling "CycleCanceling" implements a
     71  /// cycle-canceling algorithm for finding a minimum cost flow.
    6872  ///
    6973  /// \param Graph The directed graph type the algorithm runs on.
     
    119123  protected:
    120124
    121     /// \brief Map adaptor class for demand map.
    122     class DemandMap : public MapBase<Node, Supply>
    123     {
    124     private:
    125 
    126       const SupplyMap *map;
    127 
    128     public:
    129 
    130       typedef typename MapBase<Node, Supply>::Value Value;
    131       typedef typename MapBase<Node, Supply>::Key Key;
    132 
    133       DemandMap(const SupplyMap &_map) : map(&_map) {}
    134 
    135       Value operator[](const Key &e) const {
    136         return -(*map)[e];
    137       }
    138 
    139     }; //class DemandMap
    140 
    141125    /// \brief Map adaptor class for handling residual edge costs.
    142126    class ResCostMap : public MapBase<ResEdge, Cost>
     
    171155    /// \brief The modified supply map.
    172156    SupplyRefMap supply;
    173     /// \brief The modified demand map.
    174     DemandMap demand;
    175157    /// \brief The sum of supply values equals zero.
    176158    bool valid_supply;
     
    200182                    const SupplyMap &_supply ) :
    201183      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    202       supply(_graph), demand(supply), flow(_graph, 0),
     184      supply(_graph), flow(_graph, 0),
    203185      res_graph(_graph, capacity, flow), res_cost(cost)
    204186    {
     
    230212                    const SupplyMap &_supply ) :
    231213      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    232       supply(_supply), demand(supply), flow(_graph, 0),
     214      supply(_supply), flow(_graph, 0),
    233215      res_graph(_graph, capacity, flow), res_cost(cost)
    234216    {
     
    260242                    Supply _flow_value ) :
    261243      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    262       supply(_graph), demand(supply), flow(_graph, 0),
     244      supply(_graph), flow(_graph, 0),
    263245      res_graph(_graph, capacity, flow), res_cost(cost)
    264246    {
     
    296278                    Supply _flow_value ) :
    297279      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    298       supply(_graph, 0), demand(supply), flow(_graph, 0),
     280      supply(_graph, 0), flow(_graph, 0),
    299281      res_graph(_graph, capacity, flow), res_cost(cost)
    300282    {
     
    346328      // Finding a feasible flow
    347329      Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,
    348                    CapacityRefMap, DemandMap >
     330                   CapacityRefMap, SupplyMap >
    349331        circulation( graph, constMap<Edge>((Capacity)0),
    350                      capacity, demand, flow );
     332                     capacity, supply, flow );
    351333      return circulation.run() == -1;
    352334    }
    353335
    354336#ifdef LIMITED_CYCLE_CANCELING
    355     /// \brief Executes a cycle canceling algorithm using
     337    /// \brief Executes a cycle-canceling algorithm using
    356338    /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
    357339    /// iteration count.
     
    374356        bool cycle_found = false;
    375357        while (!cycle_found) {
     358#ifdef _NO_BACK_STEP_
     359          int curr_iter_num = length_bound <= node_num ?
     360                              length_bound - iter_num : node_num - iter_num;
     361#else
    376362          int curr_iter_num = iter_num + length_bound <= node_num ?
    377363                              length_bound : node_num - iter_num;
     364#endif
    378365          iter_num += curr_iter_num;
    379366          int real_iter_num = curr_iter_num;
     
    433420
    434421#ifdef _DEBUG_ITER_
    435       std::cout << "Limited cycle canceling algorithm finished. "
     422      std::cout << "Limited cycle-canceling algorithm finished. "
    436423                << "Found " << cycle_num << " negative cycles."
    437424                << std::endl;
     
    448435
    449436#ifdef MIN_MEAN_CYCLE_CANCELING
    450     /// \brief Executes the minimum mean cycle canceling algorithm
     437    /// \brief Executes the minimum mean cycle-canceling algorithm
    451438    /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
    452439    bool start() {
     
    487474
    488475#ifdef _DEBUG_ITER_
    489       std::cout << "Minimum mean cycle canceling algorithm finished. "
     476      std::cout << "Minimum mean cycle-canceling algorithm finished. "
    490477                << "Found " << cycle_num << " negative cycles."
    491478                << std::endl;
Note: See TracChangeset for help on using the changeset viewer.