COIN-OR::LEMON - Graph Library

Changeset 2509:a8081c9cd96a in lemon-0.x for lemon/capacity_scaling.h


Ignore:
Timestamp:
11/14/07 07:28:08 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3374
Message:

Small changes in the min. cost flow classes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r2507 r2509  
    2727
    2828#include <vector>
     29#include <lemon/graph_adaptor.h>
    2930#include <lemon/dijkstra.h>
    30 #include <lemon/graph_adaptor.h>
    3131
    3232#define WITH_SCALING
     
    4444
    4545  /// \brief Implementation of the capacity scaling version of the
    46   /// successive shortest path algorithm for finding a minimum cost flow.
     46  /// successive shortest path algorithm for finding a minimum cost
     47  /// flow.
    4748  ///
    48   /// \ref lemon::CapacityScaling "CapacityScaling" implements a
    49   /// capacity scaling algorithm for finding a minimum cost flow.
     49  /// \ref lemon::CapacityScaling "CapacityScaling" implements the
     50  /// capacity scaling version of the successive shortest path
     51  /// algorithm for finding a minimum cost flow.
    5052  ///
    5153  /// \param Graph The directed graph type the algorithm runs on.
     
    5860  /// - Edge capacities and costs should be nonnegative integers.
    5961  ///   However \c CostMap::Value should be signed type.
    60   /// - Supply values should be integers.
     62  /// - Supply values should be signed integers.
    6163  /// - \c LowerMap::Value must be convertible to
    6264  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
     
    114116    public:
    115117
    116       typedef typename MapBase<ResEdge, Cost>::Value Value;
    117       typedef typename MapBase<ResEdge, Cost>::Key Key;
    118 
    119118      ReducedCostMap( const ResGraph &_gr,
    120119                      const CostMap &_cost,
     
    122121        gr(_gr), cost_map(_cost), pot_map(_pot) {}
    123122
    124       Value operator[](const Key &e) const {
     123      Cost operator[](const ResEdge &e) const {
    125124        return ResGraph::forward(e) ?
    126125           cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :
     
    130129    }; //class ReducedCostMap
    131130
    132     /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to
    133     /// update node potentials.
     131    /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra"
     132    /// algorithm to update node potentials.
    134133    class PotentialUpdateMap : public MapBase<ResNode, Cost>
    135134    {
     
    142141    public:
    143142
    144       typedef typename MapBase<ResNode, Cost>::Value Value;
    145       typedef typename MapBase<ResNode, Cost>::Key Key;
    146 
    147143      void potentialMap(PotentialMap &_pot) {
    148144        pot = &_pot;
     
    153149      }
    154150
    155       void set(const Key &n, const Value &v) {
     151      void set(const ResNode &n, const Cost &v) {
    156152        data.push_back(Pair(n, v));
    157153      }
     
    186182
    187183    /// \brief Map adaptor class for filtering edges with at least
    188     /// \c delta residual capacity
     184    /// \c delta residual capacity.
    189185    class DeltaFilterMap : public MapBase<ResEdge, bool>
    190186    {
     
    196192    public:
    197193
    198       typedef typename MapBase<ResEdge, Cost>::Value Value;
    199       typedef typename MapBase<ResEdge, Cost>::Key Key;
    200 
    201194      DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :
    202195        gr(_gr), delta(_delta) {}
    203196
    204       Value operator[](const Key &e) const {
     197      bool operator[](const ResEdge &e) const {
    205198        return gr.rescap(e) >= delta;
    206199      }
     
    299292    /// \brief The delta parameter used for capacity scaling.
    300293    Capacity delta;
    301     /// \brief Edge filter map.
     294    /// \brief Edge filter map for filtering edges with at least
     295    /// \c delta residual capacity.
    302296    DeltaFilterMap delta_filter;
    303     /// \brief The delta residual graph.
     297    /// \brief The delta residual graph (i.e. the subgraph of the
     298    /// residual graph consisting of edges with at least \c delta
     299    /// residual capacity).
    304300    DeltaResGraph dres_graph;
    305301    /// \brief Map for identifing deficit nodes.
     
    574570          if (red_cost[e] < 0) {
    575571            res_graph.augment(e, r = res_graph.rescap(e));
     572            imbalance[dres_graph.source(e)] -= r;
    576573            imbalance[dres_graph.target(e)] += r;
    577             imbalance[dres_graph.source(e)] -= r;
    578574          }
    579575        }
Note: See TracChangeset for help on using the changeset viewer.