COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2556:74c2c81055e1 in lemon-0.x for lemon/cycle_canceling.h


Ignore:
Timestamp:
01/13/08 11:32:14 (16 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3437
Message:

Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/cycle_canceling.h

    r2553 r2556  
    3535#ifdef LIMITED_CYCLE_CANCELING
    3636  #include <lemon/bellman_ford.h>
    37   /// \brief The maximum number of iterations for the first execution
    38   /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
    39   /// It should be at least 2.
    40   #define STARTING_LIMIT        2
    41   /// \brief The iteration limit for the
    42   /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
    43   /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
    44   /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
    45   #define ALPHA_MUL             3
    46   /// \brief The iteration limit for the
    47   /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
    48   /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
    49   /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
    50   #define ALPHA_DIV             2
     37  // The maximum number of iterations for the first execution of the
     38  // Bellman-Ford algorithm. It should be at least 2.
     39  #define STARTING_LIMIT        2
     40  // The iteration limit for the Bellman-Ford algorithm is multiplied by
     41  // <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
     42  // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
     43  #define ALPHA_MUL             3
     44  #define ALPHA_DIV             2
    5145
    5246//#define _ONLY_ONE_CYCLE_
    5347//#define _NO_BACK_STEP_
    54 //#define _DEBUG_ITER_
    5548#endif
    5649
    … …  
    6053#endif
    6154
     55//#define _DEBUG_ITER_
     56
    6257namespace lemon {
    6358
    … …  
    6560  /// @{
    6661
    67   /// \brief Implementation of a cycle-canceling algorithm for finding
    68   /// a minimum cost flow.
     62  /// \brief Implementation of a cycle-canceling algorithm for
     63  /// finding a minimum cost flow.
    6964  ///
    70   /// \ref lemon::CycleCanceling "CycleCanceling" implements a
    71   /// cycle-canceling algorithm for finding a minimum cost flow.
     65  /// \ref CycleCanceling implements a cycle-canceling algorithm for
     66  /// finding a minimum cost flow.
    7267  ///
    7368  /// \param Graph The directed graph type the algorithm runs on.
    … …  
    7873  ///
    7974  /// \warning
    80   /// - Edge capacities and costs should be nonnegative integers.
    81   ///   However \c CostMap::Value should be signed type.
     75  /// - Edge capacities and costs should be non-negative integers.
     76  ///   However \c CostMap::Value should be signed type.
    8277  /// - Supply values should be signed integers.
    8378  /// - \c LowerMap::Value must be convertible to
    84   ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    85   ///   convertible to \c SupplyMap::Value.
     79  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
     80  ///   convertible to \c SupplyMap::Value.
    8681  ///
    8782  /// \author Peter Kovacs
    … …  
    9590  class CycleCanceling
    9691  {
    97     typedef typename Graph::Node Node;
    98     typedef typename Graph::NodeIt NodeIt;
    99     typedef typename Graph::Edge Edge;
    100     typedef typename Graph::EdgeIt EdgeIt;
    101     typedef typename Graph::InEdgeIt InEdgeIt;
    102     typedef typename Graph::OutEdgeIt OutEdgeIt;
     92    GRAPH_TYPEDEFS(typename Graph);
    10393
    10494    typedef typename LowerMap::Value Lower;
    … …  
    10696    typedef typename CostMap::Value Cost;
    10797    typedef typename SupplyMap::Value Supply;
    108     typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
    109     typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
     98    typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
     99    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
    110100
    111101    typedef ResGraphAdaptor< const Graph, Capacity,
    112                              CapacityRefMap, CapacityRefMap > ResGraph;
     102                             CapacityEdgeMap, CapacityEdgeMap > ResGraph;
    113103    typedef typename ResGraph::Node ResNode;
    114104    typedef typename ResGraph::NodeIt ResNodeIt;
    … …  
    118108  public:
    119109
    120     /// \brief The type of the flow map.
    121     typedef CapacityRefMap FlowMap;
     110    /// The type of the flow map.
     111    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    122112
    123113  protected:
    124114
    125     /// \brief Map adaptor class for handling residual edge costs.
     115    /// Map adaptor class for handling residual edge costs.
    126116    class ResCostMap : public MapBase<ResEdge, Cost>
    127117    {
    … …  
    135125
    136126      Cost operator[](const ResEdge &e) const {
    137         return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
     127        return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
    138128      }
    139129
    … …  
    142132  protected:
    143133
    144     /// \brief The directed graph the algorithm runs on.
     134    /// The directed graph the algorithm runs on.
    145135    const Graph &graph;
    146     /// \brief The original lower bound map.
     136    /// The original lower bound map.
    147137    const LowerMap *lower;
    148     /// \brief The modified capacity map.
    149     CapacityRefMap capacity;
    150     /// \brief The cost map.
     138    /// The modified capacity map.
     139    CapacityEdgeMap capacity;
     140    /// The cost map.
    151141    const CostMap &cost;
    152     /// \brief The modified supply map.
    153     SupplyRefMap supply;
    154     /// \brief The sum of supply values equals zero.
     142    /// The modified supply map.
     143    SupplyNodeMap supply;
    155144    bool valid_supply;
    156145
    157     /// \brief The current flow.
     146    /// The current flow.
    158147    FlowMap flow;
    159     /// \brief The residual graph.
     148    /// The residual graph.
    160149    ResGraph res_graph;
    161     /// \brief The residual cost map.
     150    /// The residual cost map.
    162151    ResCostMap res_cost;
    163152
    … …  
    174163    /// \param _supply The supply values of the nodes (signed).
    175164    CycleCanceling( const Graph &_graph,
    176                     const LowerMap &_lower,
    177                     const CapacityMap &_capacity,
    178                     const CostMap &_cost,
    179                     const SupplyMap &_supply ) :
     165                    const LowerMap &_lower,
     166                    const CapacityMap &_capacity,
     167                    const CostMap &_cost,
     168                    const SupplyMap &_supply ) :
    180169      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    181170      supply(_graph), flow(_graph, 0),
    182171      res_graph(_graph, capacity, flow), res_cost(cost)
    183172    {
    184       // Removing nonzero lower bounds
     173      // Removing non-zero lower bounds
    185174      capacity = subMap(_capacity, _lower);
    186175      Supply sum = 0;
    187176      for (NodeIt n(graph); n != INVALID; ++n) {
    188         Supply s = _supply[n];
    189         for (InEdgeIt e(graph, n); e != INVALID; ++e)
    190           s += _lower[e];
    191         for (OutEdgeIt e(graph, n); e != INVALID; ++e)
    192           s -= _lower[e];
    193         sum += (supply[n] = s);
     177        Supply s = _supply[n];
     178        for (InEdgeIt e(graph, n); e != INVALID; ++e)
     179          s += _lower[e];
     180        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
     181          s -= _lower[e];
     182        sum += (supply[n] = s);
    194183      }
    195184      valid_supply = sum == 0;
    … …  
    205194    /// \param _supply The supply values of the nodes (signed).
    206195    CycleCanceling( const Graph &_graph,
    207                     const CapacityMap &_capacity,
    208                     const CostMap &_cost,
    209                     const SupplyMap &_supply ) :
     196                    const CapacityMap &_capacity,
     197                    const CostMap &_cost,
     198                    const SupplyMap &_supply ) :
    210199      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    211200      supply(_supply), flow(_graph, 0),
    … …  
    218207    }
    219208
    220 
    221209    /// \brief Simple constructor of the class (with lower bounds).
    222210    ///
    … …  
    230218    /// \param _t The target node.
    231219    /// \param _flow_value The required amount of flow from node \c _s
    232     /// to node \c _t (i.e. the supply of \c _s and the demand of
    233     /// \c _t).
     220    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    234221    CycleCanceling( const Graph &_graph,
    235                     const LowerMap &_lower,
    236                     const CapacityMap &_capacity,
    237                     const CostMap &_cost,
    238                     Node _s, Node _t,
    239                     Supply _flow_value ) :
     222                    const LowerMap &_lower,
     223                    const CapacityMap &_capacity,
     224                    const CostMap &_cost,
     225                    Node _s, Node _t,
     226                    Supply _flow_value ) :
    240227      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    241228      supply(_graph), flow(_graph, 0),
    242229      res_graph(_graph, capacity, flow), res_cost(cost)
    243230    {
    244       // Removing nonzero lower bounds
     231      // Removing non-zero lower bounds
    245232      capacity = subMap(_capacity, _lower);
    246233      for (NodeIt n(graph); n != INVALID; ++n) {
    247         Supply s = 0;
    248         if (n == _s) s =  _flow_value;
    249         if (n == _t) s = -_flow_value;
    250         for (InEdgeIt e(graph, n); e != INVALID; ++e)
    251           s += _lower[e];
    252         for (OutEdgeIt e(graph, n); e != INVALID; ++e)
    253           s -= _lower[e];
    254         supply[n] = s;
     234        Supply s = 0;
     235        if (n == _s) s =  _flow_value;
     236        if (n == _t) s = -_flow_value;
     237        for (InEdgeIt e(graph, n); e != INVALID; ++e)
     238          s += _lower[e];
     239        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
     240          s -= _lower[e];
     241        supply[n] = s;
    255242      }
    256243      valid_supply = true;
    … …  
    267254    /// \param _t The target node.
    268255    /// \param _flow_value The required amount of flow from node \c _s
    269     /// to node \c _t (i.e. the supply of \c _s and the demand of
    270     /// \c _t).
     256    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    271257    CycleCanceling( const Graph &_graph,
    272                     const CapacityMap &_capacity,
    273                     const CostMap &_cost,
    274                     Node _s, Node _t,
    275                     Supply _flow_value ) :
     258                    const CapacityMap &_capacity,
     259                    const CostMap &_cost,
     260                    Node _s, Node _t,
     261                    Supply _flow_value ) :
    276262      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    277263      supply(_graph, 0), flow(_graph, 0),
    … …  
    283269    }
    284270
     271    /// \brief Runs the algorithm.
     272    ///
     273    /// Runs the algorithm.
     274    ///
     275    /// \return \c true if a feasible flow can be found.
     276    bool run() {
     277      return init() && start();
     278    }
     279
    285280    /// \brief Returns a const reference to the flow map.
    286281    ///
    … …  
    301296      Cost c = 0;
    302297      for (EdgeIt e(graph); e != INVALID; ++e)
    303         c += flow[e] * cost[e];
     298        c += flow[e] * cost[e];
    304299      return c;
    305300    }
    306301
    307     /// \brief Runs the algorithm.
    308     ///
    309     /// Runs the algorithm.
    310     ///
    311     /// \return \c true if a feasible flow can be found.
    312     bool run() {
    313       return init() && start();
    314     }
    315 
    316302  protected:
    317303
    318     /// \brief Initializes the algorithm.
     304    /// Initializes the algorithm.
    319305    bool init() {
    320306      // Checking the sum of supply values
    … …  
    324310
    325311      // Finding a feasible flow
    326       Circulation< Graph, ConstMap<Edge, Capacity>, CapacityRefMap,
    327                    SupplyMap >
    328         circulation( graph, constMap<Edge>((Capacity)0), capacity,
    329                      supply );
     312      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
     313                   SupplyMap >
     314        circulation( graph, constMap<Edge>((Capacity)0), capacity,
     315                     supply );
    330316      circulation.flowMap(flow);
    331317      return circulation.run();
    … …  
    334320#ifdef LIMITED_CYCLE_CANCELING
    335321    /// \brief Executes a cycle-canceling algorithm using
    336     /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
    337     /// iteration count.
     322    /// \ref Bellman-Ford algorithm with limited iteration count.
    338323    bool start() {
    339324      typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
    … …  
    348333      bool optimal = false;
    349334      while (!optimal) {
    350         BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
    351         bf.predMap(pred);
    352         bf.init(0);
    353         int iter_num = 0;
    354         bool cycle_found = false;
    355         while (!cycle_found) {
     335        BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
     336        bf.predMap(pred);
     337        bf.init(0);
     338        int iter_num = 0;
     339        bool cycle_found = false;
     340        while (!cycle_found) {
    356341#ifdef _NO_BACK_STEP_
    357           int curr_iter_num = length_bound <= node_num ?
    358                               length_bound - iter_num : node_num - iter_num;
     342          int curr_iter_num = length_bound <= node_num ?
     343                              length_bound - iter_num : node_num - iter_num;
    359344#else
    360           int curr_iter_num = iter_num + length_bound <= node_num ?
    361                               length_bound : node_num - iter_num;
    362 #endif
    363           iter_num += curr_iter_num;
    364           int real_iter_num = curr_iter_num;
    365           for (int i = 0; i < curr_iter_num; ++i) {
    366             if (bf.processNextWeakRound()) {
    367               real_iter_num = i;
    368               break;
    369             }
    370           }
    371           if (real_iter_num < curr_iter_num) {
    372             optimal = true;
    373             break;
    374           } else {
    375             // Searching for node disjoint negative cycles
    376             for (ResNodeIt n(res_graph); n != INVALID; ++n)
    377               visited[n] = 0;
    378             int id = 0;
    379             for (ResNodeIt n(res_graph); n != INVALID; ++n) {
    380               if (visited[n] > 0) continue;
    381               visited[n] = ++id;
    382               ResNode u = pred[n] == INVALID ?
    383                           INVALID : res_graph.source(pred[n]);
    384               while (u != INVALID && visited[u] == 0) {
    385                 visited[u] = id;
    386                 u = pred[u] == INVALID ?
    387                     INVALID : res_graph.source(pred[u]);
    388               }
    389               if (u != INVALID && visited[u] == id) {
    390                 // Finding the negative cycle
    391                 cycle_found = true;
    392                 cycle.clear();
    393                 ResEdge e = pred[u];
    394                 cycle.push_back(e);
    395                 Capacity d = res_graph.rescap(e);
    396                 while (res_graph.source(e) != u) {
    397                   cycle.push_back(e = pred[res_graph.source(e)]);
    398                   if (res_graph.rescap(e) < d)
    399                     d = res_graph.rescap(e);
    400                 }
    401 #ifdef _DEBUG_ITER_
    402                 ++cycle_num;
    403 #endif
    404                 // Augmenting along the cycle
    405                 for (int i = 0; i < cycle.size(); ++i)
    406                   res_graph.augment(cycle[i], d);
     345          int curr_iter_num = iter_num + length_bound <= node_num ?
     346                              length_bound : node_num - iter_num;
     347#endif
     348          iter_num += curr_iter_num;
     349          int real_iter_num = curr_iter_num;
     350          for (int i = 0; i < curr_iter_num; ++i) {
     351            if (bf.processNextWeakRound()) {
     352              real_iter_num = i;
     353              break;
     354            }
     355          }
     356          if (real_iter_num < curr_iter_num) {
     357            optimal = true;
     358            break;
     359          } else {
     360            // Searching for node disjoint negative cycles
     361            for (ResNodeIt n(res_graph); n != INVALID; ++n)
     362              visited[n] = 0;
     363            int id = 0;
     364            for (ResNodeIt n(res_graph); n != INVALID; ++n) {
     365              if (visited[n] > 0) continue;
     366              visited[n] = ++id;
     367              ResNode u = pred[n] == INVALID ?
     368                          INVALID : res_graph.source(pred[n]);
     369              while (u != INVALID && visited[u] == 0) {
     370                visited[u] = id;
     371                u = pred[u] == INVALID ?
     372                    INVALID : res_graph.source(pred[u]);
     373              }
     374              if (u != INVALID && visited[u] == id) {
     375                // Finding the negative cycle
     376                cycle_found = true;
     377                cycle.clear();
     378                ResEdge e = pred[u];
     379                cycle.push_back(e);
     380                Capacity d = res_graph.rescap(e);
     381                while (res_graph.source(e) != u) {
     382                  cycle.push_back(e = pred[res_graph.source(e)]);
     383                  if (res_graph.rescap(e) < d)
     384                    d = res_graph.rescap(e);
     385                }
     386#ifdef _DEBUG_ITER_
     387                ++cycle_num;
     388#endif
     389                // Augmenting along the cycle
     390                for (int i = 0; i < cycle.size(); ++i)
     391                  res_graph.augment(cycle[i], d);
    407392#ifdef _ONLY_ONE_CYCLE_
    408                 break;
    409 #endif
    410               }
    411             }
    412           }
    413 
    414           if (!cycle_found)
    415             length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
    416         }
     393                break;
     394#endif
     395              }
     396            }
     397          }
     398
     399          if (!cycle_found)
     400            length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
     401        }
    417402      }
    418403
    419404#ifdef _DEBUG_ITER_
    420405      std::cout << "Limited cycle-canceling algorithm finished. "
    421                 << "Found " << cycle_num << " negative cycles."
    422                 << std::endl;
    423 #endif
    424 
    425       // Handling nonzero lower bounds
     406                << "Found " << cycle_num << " negative cycles."
     407                << std::endl;
     408#endif
     409
     410      // Handling non-zero lower bounds
    426411      if (lower) {
    427         for (EdgeIt e(graph); e != INVALID; ++e)
    428           flow[e] += (*lower)[e];
     412        for (EdgeIt e(graph); e != INVALID; ++e)
     413          flow[e] += (*lower)[e];
    429414      }
    430415      return true;
    … …  
    434419#ifdef MIN_MEAN_CYCLE_CANCELING
    435420    /// \brief Executes the minimum mean cycle-canceling algorithm
    436     /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
     421    /// using \ref MinMeanCycle.
    437422    bool start() {
    438423      typedef Path<ResGraph> ResPath;
    … …  
    445430      mmc.cyclePath(cycle).init();
    446431      if (mmc.findMinMean()) {
    447         while (mmc.cycleLength() < 0) {
    448 #ifdef _DEBUG_ITER_
    449           ++iter;
    450 #endif
    451           // Finding the cycle
    452           mmc.findCycle();
    453 
    454           // Finding the largest flow amount that can be augmented
    455           // along the cycle
    456           Capacity delta = 0;
    457           for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
    458             if (delta == 0 || res_graph.rescap(e) < delta)
    459               delta = res_graph.rescap(e);
    460           }
    461 
    462           // Augmenting along the cycle
    463           for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
    464             res_graph.augment(e, delta);
    465 
    466           // Finding the minimum cycle mean for the modified residual
    467           // graph
    468           mmc.reset();
    469           if (!mmc.findMinMean()) break;
    470         }
     432        while (mmc.cycleLength() < 0) {
     433#ifdef _DEBUG_ITER_
     434          ++cycle_num;
     435#endif
     436          // Finding the cycle
     437          mmc.findCycle();
     438
     439          // Finding the largest flow amount that can be augmented
     440          // along the cycle
     441          Capacity delta = 0;
     442          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
     443            if (delta == 0 || res_graph.rescap(e) < delta)
     444              delta = res_graph.rescap(e);
     445          }
     446
     447          // Augmenting along the cycle
     448          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
     449            res_graph.augment(e, delta);
     450
     451          // Finding the minimum cycle mean for the modified residual
     452          // graph
     453          mmc.reset();
     454          if (!mmc.findMinMean()) break;
     455        }
    471456      }
    472457
    473458#ifdef _DEBUG_ITER_
    474459      std::cout << "Minimum mean cycle-canceling algorithm finished. "
    475                 << "Found " << cycle_num << " negative cycles."
    476                 << std::endl;
    477 #endif
    478 
    479       // Handling nonzero lower bounds
     460                << "Found " << cycle_num << " negative cycles."
     461                << std::endl;
     462#endif
     463
     464      // Handling non-zero lower bounds
    480465      if (lower) {
    481         for (EdgeIt e(graph); e != INVALID; ++e)
    482           flow[e] += (*lower)[e];
     466        for (EdgeIt e(graph); e != INVALID; ++e)
     467          flow[e] += (*lower)[e];
    483468      }
    484469      return true;
Note: See TracChangeset for help on using the changeset viewer.