COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2574:7058c9690e7d in lemon-0.x for lemon/capacity_scaling.h


Ignore:
Timestamp:
02/18/08 04:30:53 (16 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3456
Message:

Improvements in CapacityScaling?.

Main changes:

  • Use -potenital[] instead of potential[] to conform to the usual

terminology.

  • Change the name of private members to start with "_".
  • Change the name of function parameters not to start with "_".
  • Remove unnecessary documentation for private members.
  • Doc improvements.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r2556 r2574  
    2323///
    2424/// \file
    25 /// \brief The capacity scaling algorithm for finding a minimum cost flow.
     25/// \brief Capacity scaling algorithm for finding a minimum cost flow.
     26
     27#include <vector>
    2628
    2729#include <lemon/graph_adaptor.h>
    2830#include <lemon/bin_heap.h>
    29 #include <vector>
    3031
    3132namespace lemon {
    … …  
    3435  /// @{
    3536
    36   /// \brief Implementation of the capacity scaling version of the
    37   /// successive shortest path algorithm for finding a minimum cost
    38   /// flow.
     37  /// \brief Implementation of the capacity scaling algorithm for
     38  /// finding a minimum cost flow.
    3939  ///
    4040  /// \ref CapacityScaling implements the capacity scaling version
    … …  
    4242  /// cost flow.
    4343  ///
    44   /// \param Graph The directed graph type the algorithm runs on.
    45   /// \param LowerMap The type of the lower bound map.
    46   /// \param CapacityMap The type of the capacity (upper bound) map.
    47   /// \param CostMap The type of the cost (length) map.
    48   /// \param SupplyMap The type of the supply map.
     44  /// \tparam Graph The directed graph type the algorithm runs on.
     45  /// \tparam LowerMap The type of the lower bound map.
     46  /// \tparam CapacityMap The type of the capacity (upper bound) map.
     47  /// \tparam CostMap The type of the cost (length) map.
     48  /// \tparam SupplyMap The type of the supply map.
    4949  ///
    5050  /// \warning
    51   /// - Edge capacities and costs should be non-negative integers.
    52   ///   However \c CostMap::Value should be signed type.
    53   /// - Supply values should be signed integers.
    54   /// - \c LowerMap::Value must be convertible to
    55   ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    56   ///   convertible to \c SupplyMap::Value.
     51  /// - Edge capacities and costs should be \e non-negative \e integers.
     52  /// - Supply values should be \e signed \e integers.
     53  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
     54  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
     55  ///   convertible to each other.
     56  /// - All value types must be convertible to \c CostMap::Value, which
     57  ///   must be signed type.
    5758  ///
    5859  /// \author Peter Kovacs
    … …  
    6061  template < typename Graph,
    6162             typename LowerMap = typename Graph::template EdgeMap<int>,
    62              typename CapacityMap = LowerMap,
     63             typename CapacityMap = typename Graph::template EdgeMap<int>,
    6364             typename CostMap = typename Graph::template EdgeMap<int>,
    64              typename SupplyMap = typename Graph::template NodeMap
    65                                   <typename CapacityMap::Value> >
     65             typename SupplyMap = typename Graph::template NodeMap<int> >
    6666  class CapacityScaling
    6767  {
    6868    GRAPH_TYPEDEFS(typename Graph);
    6969
    70     typedef typename LowerMap::Value Lower;
    7170    typedef typename CapacityMap::Value Capacity;
    7271    typedef typename CostMap::Value Cost;
    … …  
    7877  public:
    7978
    80     /// Type to enable or disable capacity scaling.
    81     enum ScalingEnum {
    82       WITH_SCALING = 0,
    83       WITHOUT_SCALING = -1
    84     };
    85 
    8679    /// The type of the flow map.
    8780    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    … …  
    8982    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    9083
    91   protected:
     84  private:
    9285
    9386    /// \brief Special implementation of the \ref Dijkstra algorithm
    94     /// for finding shortest paths in the residual network of the graph
    95     /// with respect to the reduced edge costs and modifying the
    96     /// node potentials according to the distance of the nodes.
     87    /// for finding shortest paths in the residual network.
     88    ///
     89    /// \ref ResidualDijkstra is a special implementation of the
     90    /// \ref Dijkstra algorithm for finding shortest paths in the
     91    /// residual network of the graph with respect to the reduced edge
     92    /// costs and modifying the node potentials according to the
     93    /// distance of the nodes.
    9794    class ResidualDijkstra
    9895    {
    … …  
    103100      typedef BinHeap<Cost, HeapCrossRef> Heap;
    104101
    105     protected:
    106 
    107       /// The directed graph the algorithm runs on.
    108       const Graph &graph;
    109 
    110       /// The flow map.
    111       const FlowMap &flow;
    112       /// The residual capacity map.
    113       const CapacityEdgeMap &res_cap;
    114       /// The cost map.
    115       const CostMap &cost;
    116       /// The excess map.
    117       const SupplyNodeMap &excess;
    118 
    119       /// The potential map.
    120       PotentialMap &potential;
    121 
    122       /// The distance map.
    123       CostNodeMap dist;
    124       /// The map of predecessors edges.
    125       PredMap &pred;
    126       /// The processed (i.e. permanently labeled) nodes.
    127       std::vector<Node> proc_nodes;
     102    private:
     103
     104      // The directed graph the algorithm runs on
     105      const Graph &_graph;
     106
     107      // The main maps
     108      const FlowMap &_flow;
     109      const CapacityEdgeMap &_res_cap;
     110      const CostMap &_cost;
     111      const SupplyNodeMap &_excess;
     112      PotentialMap &_potential;
     113
     114      // The distance map
     115      CostNodeMap _dist;
     116      // The pred edge map
     117      PredMap &_pred;
     118      // The processed (i.e. permanently labeled) nodes
     119      std::vector<Node> _proc_nodes;
    128120
    129121    public:
    130122
    131123      /// The constructor of the class.
    132       ResidualDijkstra( const Graph &_graph,
    133                         const FlowMap &_flow,
    134                         const CapacityEdgeMap &_res_cap,
    135                         const CostMap &_cost,
    136                         const SupplyMap &_excess,
    137                         PotentialMap &_potential,
    138                         PredMap &_pred ) :
    139         graph(_graph), flow(_flow), res_cap(_res_cap), cost(_cost),
    140         excess(_excess), potential(_potential), dist(_graph),
    141         pred(_pred)
     124      ResidualDijkstra( const Graph &graph,
     125                        const FlowMap &flow,
     126                        const CapacityEdgeMap &res_cap,
     127                        const CostMap &cost,
     128                        const SupplyMap &excess,
     129                        PotentialMap &potential,
     130                        PredMap &pred ) :
     131        _graph(graph), _flow(flow), _res_cap(res_cap), _cost(cost),
     132        _excess(excess), _potential(potential), _dist(graph),
     133        _pred(pred)
    142134      {}
    143135
    144136      /// Runs the algorithm from the given source node.
    145137      Node run(Node s, Capacity delta) {
    146         HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);
     138        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
    147139        Heap heap(heap_cross_ref);
    148140        heap.push(s, 0);
    149         pred[s] = INVALID;
    150         proc_nodes.clear();
     141        _pred[s] = INVALID;
     142        _proc_nodes.clear();
    151143
    152144        // Processing nodes
    153         while (!heap.empty() && excess[heap.top()] > -delta) {
     145        while (!heap.empty() && _excess[heap.top()] > -delta) {
    154146          Node u = heap.top(), v;
    155           Cost d = heap.prio() - potential[u], nd;
    156           dist[u] = heap.prio();
     147          Cost d = heap.prio() + _potential[u], nd;
     148          _dist[u] = heap.prio();
    157149          heap.pop();
    158           proc_nodes.push_back(u);
     150          _proc_nodes.push_back(u);
    159151
    160152          // Traversing outgoing edges
    161           for (OutEdgeIt e(graph, u); e != INVALID; ++e) {
    162             if (res_cap[e] >= delta) {
    163               v = graph.target(e);
     153          for (OutEdgeIt e(_graph, u); e != INVALID; ++e) {
     154            if (_res_cap[e] >= delta) {
     155              v = _graph.target(e);
    164156              switch(heap.state(v)) {
    165157              case Heap::PRE_HEAP:
    166                 heap.push(v, d + cost[e] + potential[v]);
    167                 pred[v] = e;
     158                heap.push(v, d + _cost[e] - _potential[v]);
     159                _pred[v] = e;
    168160                break;
    169161              case Heap::IN_HEAP:
    170                 nd = d + cost[e] + potential[v];
     162                nd = d + _cost[e] - _potential[v];
    171163                if (nd < heap[v]) {
    172164                  heap.decrease(v, nd);
    173                   pred[v] = e;
     165                  _pred[v] = e;
    174166                }
    175167                break;
    … …  
    181173
    182174          // Traversing incoming edges
    183           for (InEdgeIt e(graph, u); e != INVALID; ++e) {
    184             if (flow[e] >= delta) {
    185               v = graph.source(e);
     175          for (InEdgeIt e(_graph, u); e != INVALID; ++e) {
     176            if (_flow[e] >= delta) {
     177              v = _graph.source(e);
    186178              switch(heap.state(v)) {
    187179              case Heap::PRE_HEAP:
    188                 heap.push(v, d - cost[e] + potential[v]);
    189                 pred[v] = e;
     180                heap.push(v, d - _cost[e] - _potential[v]);
     181                _pred[v] = e;
    190182                break;
    191183              case Heap::IN_HEAP:
    192                 nd = d - cost[e] + potential[v];
     184                nd = d - _cost[e] - _potential[v];
    193185                if (nd < heap[v]) {
    194186                  heap.decrease(v, nd);
    195                   pred[v] = e;
     187                  _pred[v] = e;
    196188                }
    197189                break;
    … …  
    206198        // Updating potentials of processed nodes
    207199        Node t = heap.top();
    208         Cost dt = heap.prio();
    209         for (int i = 0; i < proc_nodes.size(); ++i)
    210           potential[proc_nodes[i]] -= dist[proc_nodes[i]] - dt;
     200        Cost t_dist = heap.prio();
     201        for (int i = 0; i < int(_proc_nodes.size()); ++i)
     202          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
    211203
    212204        return t;
    … …  
    215207    }; //class ResidualDijkstra
    216208
    217   protected:
    218 
    219     /// The directed graph the algorithm runs on.
    220     const Graph &graph;
    221     /// The original lower bound map.
    222     const LowerMap *lower;
    223     /// The modified capacity map.
    224     CapacityEdgeMap capacity;
    225     /// The cost map.
    226     const CostMap &cost;
    227     /// The modified supply map.
    228     SupplyNodeMap supply;
    229     bool valid_supply;
    230 
    231     /// The edge map of the current flow.
    232     FlowMap flow;
    233     /// The potential node map.
    234     PotentialMap potential;
    235 
    236     /// The residual capacity map.
    237     CapacityEdgeMap res_cap;
    238     /// The excess map.
    239     SupplyNodeMap excess;
    240     /// The excess nodes (i.e. the nodes with positive excess).
    241     std::vector<Node> excess_nodes;
    242     /// The deficit nodes (i.e. the nodes with negative excess).
    243     std::vector<Node> deficit_nodes;
    244 
    245     /// The scaling status (enabled or disabled).
    246     ScalingEnum scaling;
    247     /// The \c delta parameter used for capacity scaling.
    248     Capacity delta;
    249     /// The maximum number of phases.
    250     int phase_num;
    251 
    252     /// \brief Implementation of the \ref Dijkstra algorithm for
    253     /// finding augmenting shortest paths in the residual network.
    254     ResidualDijkstra dijkstra;
    255     /// The map of predecessors edges.
    256     PredMap pred;
     209  private:
     210
     211    // The directed graph the algorithm runs on
     212    const Graph &_graph;
     213    // The original lower bound map
     214    const LowerMap *_lower;
     215    // The modified capacity map
     216    CapacityEdgeMap _capacity;
     217    // The original cost map
     218    const CostMap &_cost;
     219    // The modified supply map
     220    SupplyNodeMap _supply;
     221    bool _valid_supply;
     222
     223    // Edge map of the current flow
     224    FlowMap _flow;
     225    // Node map of the current potentials
     226    PotentialMap _potential;
     227
     228    // The residual capacity map
     229    CapacityEdgeMap _res_cap;
     230    // The excess map
     231    SupplyNodeMap _excess;
     232    // The excess nodes (i.e. nodes with positive excess)
     233    std::vector<Node> _excess_nodes;
     234    // The deficit nodes (i.e. nodes with negative excess)
     235    std::vector<Node> _deficit_nodes;
     236
     237    // The delta parameter used for capacity scaling
     238    Capacity _delta;
     239    // The maximum number of phases
     240    int _phase_num;
     241
     242    // The pred edge map
     243    PredMap _pred;
     244    // Implementation of the Dijkstra algorithm for finding augmenting
     245    // shortest paths in the residual network
     246    ResidualDijkstra _dijkstra;
    257247
    258248  public :
    … …  
    262252    /// General constructor of the class (with lower bounds).
    263253    ///
    264     /// \param _graph The directed graph the algorithm runs on.
    265     /// \param _lower The lower bounds of the edges.
    266     /// \param _capacity The capacities (upper bounds) of the edges.
    267     /// \param _cost The cost (length) values of the edges.
    268     /// \param _supply The supply values of the nodes (signed).
    269     CapacityScaling( const Graph &_graph,
    270                      const LowerMap &_lower,
    271                      const CapacityMap &_capacity,
    272                      const CostMap &_cost,
    273                      const SupplyMap &_supply ) :
    274       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    275       supply(_graph), flow(_graph, 0), potential(_graph, 0),
    276       res_cap(_graph), excess(_graph), pred(_graph),
    277       dijkstra(graph, flow, res_cap, cost, excess, potential, pred)
     254    /// \param graph The directed graph the algorithm runs on.
     255    /// \param lower The lower bounds of the edges.
     256    /// \param capacity The capacities (upper bounds) of the edges.
     257    /// \param cost The cost (length) values of the edges.
     258    /// \param supply The supply values of the nodes (signed).
     259    CapacityScaling( const Graph &graph,
     260                     const LowerMap &lower,
     261                     const CapacityMap &capacity,
     262                     const CostMap &cost,
     263                     const SupplyMap &supply ) :
     264      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
     265      _supply(graph), _flow(graph, 0), _potential(graph, 0),
     266      _res_cap(graph), _excess(graph), _pred(graph),
     267      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
    278268    {
    279269      // Removing non-zero lower bounds
    280       capacity = subMap(_capacity, _lower);
    281       res_cap = capacity;
     270      _capacity = subMap(capacity, lower);
     271      _res_cap = _capacity;
    282272      Supply sum = 0;
    283       for (NodeIt n(graph); n != INVALID; ++n) {
    284         Supply s = _supply[n];
    285         for (InEdgeIt e(graph, n); e != INVALID; ++e)
    286           s += _lower[e];
    287         for (OutEdgeIt e(graph, n); e != INVALID; ++e)
    288           s -= _lower[e];
    289         supply[n] = s;
     273      for (NodeIt n(_graph); n != INVALID; ++n) {
     274        Supply s = supply[n];
     275        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
     276          s += lower[e];
     277        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
     278          s -= lower[e];
     279        _supply[n] = s;
    290280        sum += s;
    291281      }
    292       valid_supply = sum == 0;
     282      _valid_supply = sum == 0;
    293283    }
    294284
    … …  
    297287    /// General constructor of the class (without lower bounds).
    298288    ///
    299     /// \param _graph The directed graph the algorithm runs on.
    300     /// \param _capacity The capacities (upper bounds) of the edges.
    301     /// \param _cost The cost (length) values of the edges.
    302     /// \param _supply The supply values of the nodes (signed).
    303     CapacityScaling( const Graph &_graph,
    304                      const CapacityMap &_capacity,
    305                      const CostMap &_cost,
    306                      const SupplyMap &_supply ) :
    307       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    308       supply(_supply), flow(_graph, 0), potential(_graph, 0),
    309       res_cap(_capacity), excess(_graph), pred(_graph),
    310       dijkstra(graph, flow, res_cap, cost, excess, potential)
     289    /// \param graph The directed graph the algorithm runs on.
     290    /// \param capacity The capacities (upper bounds) of the edges.
     291    /// \param cost The cost (length) values of the edges.
     292    /// \param supply The supply values of the nodes (signed).
     293    CapacityScaling( const Graph &graph,
     294                     const CapacityMap &capacity,
     295                     const CostMap &cost,
     296                     const SupplyMap &supply ) :
     297      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
     298      _supply(supply), _flow(graph, 0), _potential(graph, 0),
     299      _res_cap(capacity), _excess(graph), _pred(graph),
     300      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
    311301    {
    312302      // Checking the sum of supply values
    313303      Supply sum = 0;
    314       for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
    315       valid_supply = sum == 0;
     304      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
     305      _valid_supply = sum == 0;
    316306    }
    317307
    … …  
    320310    /// Simple constructor of the class (with lower bounds).
    321311    ///
    322     /// \param _graph The directed graph the algorithm runs on.
    323     /// \param _lower The lower bounds of the edges.
    324     /// \param _capacity The capacities (upper bounds) of the edges.
    325     /// \param _cost The cost (length) values of the edges.
    326     /// \param _s The source node.
    327     /// \param _t The target node.
    328     /// \param _flow_value The required amount of flow from node \c _s
    329     /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    330     CapacityScaling( const Graph &_graph,
    331                      const LowerMap &_lower,
    332                      const CapacityMap &_capacity,
    333                      const CostMap &_cost,
    334                      Node _s, Node _t,
    335                      Supply _flow_value ) :
    336       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    337       supply(_graph), flow(_graph, 0), potential(_graph, 0),
    338       res_cap(_graph), excess(_graph), pred(_graph),
    339       dijkstra(graph, flow, res_cap, cost, excess, potential)
     312    /// \param graph The directed graph the algorithm runs on.
     313    /// \param lower The lower bounds of the edges.
     314    /// \param capacity The capacities (upper bounds) of the edges.
     315    /// \param cost The cost (length) values of the edges.
     316    /// \param s The source node.
     317    /// \param t The target node.
     318    /// \param flow_value The required amount of flow from node \c s
     319    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
     320    CapacityScaling( const Graph &graph,
     321                     const LowerMap &lower,
     322                     const CapacityMap &capacity,
     323                     const CostMap &cost,
     324                     Node s, Node t,
     325                     Supply flow_value ) :
     326      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
     327      _supply(graph), _flow(graph, 0), _potential(graph, 0),
     328      _res_cap(graph), _excess(graph), _pred(graph),
     329      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
    340330    {
    341331      // Removing non-zero lower bounds
    342       capacity = subMap(_capacity, _lower);
    343       res_cap = capacity;
    344       for (NodeIt n(graph); n != INVALID; ++n) {
    345         Supply s = 0;
    346         if (n == _s) s =  _flow_value;
    347         if (n == _t) s = -_flow_value;
    348         for (InEdgeIt e(graph, n); e != INVALID; ++e)
    349           s += _lower[e];
    350         for (OutEdgeIt e(graph, n); e != INVALID; ++e)
    351           s -= _lower[e];
    352         supply[n] = s;
    353       }
    354       valid_supply = true;
     332      _capacity = subMap(capacity, lower);
     333      _res_cap = _capacity;
     334      for (NodeIt n(_graph); n != INVALID; ++n) {
     335        Supply sum = 0;
     336        if (n == s) sum =  flow_value;
     337        if (n == t) sum = -flow_value;
     338        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
     339          sum += lower[e];
     340        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
     341          sum -= lower[e];
     342        _supply[n] = sum;
     343      }
     344      _valid_supply = true;
    355345    }
    356346
    … …  
    359349    /// Simple constructor of the class (without lower bounds).
    360350    ///
    361     /// \param _graph The directed graph the algorithm runs on.
    362     /// \param _capacity The capacities (upper bounds) of the edges.
    363     /// \param _cost The cost (length) values of the edges.
    364     /// \param _s The source node.
    365     /// \param _t The target node.
    366     /// \param _flow_value The required amount of flow from node \c _s
    367     /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    368     CapacityScaling( const Graph &_graph,
    369                      const CapacityMap &_capacity,
    370                      const CostMap &_cost,
    371                      Node _s, Node _t,
    372                      Supply _flow_value ) :
    373       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    374       supply(_graph, 0), flow(_graph, 0), potential(_graph, 0),
    375       res_cap(_capacity), excess(_graph), pred(_graph),
    376       dijkstra(graph, flow, res_cap, cost, excess, potential)
     351    /// \param graph The directed graph the algorithm runs on.
     352    /// \param capacity The capacities (upper bounds) of the edges.
     353    /// \param cost The cost (length) values of the edges.
     354    /// \param s The source node.
     355    /// \param t The target node.
     356    /// \param flow_value The required amount of flow from node \c s
     357    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
     358    CapacityScaling( const Graph &graph,
     359                     const CapacityMap &capacity,
     360                     const CostMap &cost,
     361                     Node s, Node t,
     362                     Supply flow_value ) :
     363      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
     364      _supply(graph, 0), _flow(graph, 0), _potential(graph, 0),
     365      _res_cap(capacity), _excess(graph), _pred(graph),
     366      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
    377367    {
    378       supply[_s] =  _flow_value;
    379       supply[_t] = -_flow_value;
    380       valid_supply = true;
     368      _supply[s] =  flow_value;
     369      _supply[t] = -flow_value;
     370      _valid_supply = true;
    381371    }
    382372
    … …  
    385375    /// Runs the algorithm.
    386376    ///
    387     /// \param scaling_mode The scaling mode. In case of WITH_SCALING
    388     /// capacity scaling is enabled in the algorithm (this is the
    389     /// default) otherwise it is disabled.
     377    /// \param scaling Enable or disable capacity scaling.
    390378    /// If the maximum edge capacity and/or the amount of total supply
    391     /// is small, the algorithm could be slightly faster without
     379    /// is rather small, the algorithm could be slightly faster without
    392380    /// scaling.
    393381    ///
    394382    /// \return \c true if a feasible flow can be found.
    395     bool run(int scaling_mode = WITH_SCALING) {
    396       return init(scaling_mode) && start();
    397     }
    398 
    399     /// \brief Returns a const reference to the flow map.
    400     ///
    401     /// Returns a const reference to the flow map.
     383    bool run(bool scaling = true) {
     384      return init(scaling) && start();
     385    }
     386
     387    /// \brief Returns a const reference to the edge map storing the
     388    /// found flow.
     389    ///
     390    /// Returns a const reference to the edge map storing the found flow.
    402391    ///
    403392    /// \pre \ref run() must be called before using this function.
    404393    const FlowMap& flowMap() const {
    405       return flow;
    406     }
    407 
    408     /// \brief Returns a const reference to the potential map (the dual
    409     /// solution).
    410     ///
    411     /// Returns a const reference to the potential map (the dual
    412     /// solution).
     394      return _flow;
     395    }
     396
     397    /// \brief Returns a const reference to the node map storing the
     398    /// found potentials (the dual solution).
     399    ///
     400    /// Returns a const reference to the node map storing the found
     401    /// potentials (the dual solution).
    413402    ///
    414403    /// \pre \ref run() must be called before using this function.
    415404    const PotentialMap& potentialMap() const {
    416       return potential;
     405      return _potential;
    417406    }
    418407
    … …  
    425414    Cost totalCost() const {
    426415      Cost c = 0;
    427       for (EdgeIt e(graph); e != INVALID; ++e)
    428         c += flow[e] * cost[e];
     416      for (EdgeIt e(_graph); e != INVALID; ++e)
     417        c += _flow[e] * _cost[e];
    429418      return c;
    430419    }
    431420
    432   protected:
     421  private:
    433422
    434423    /// Initializes the algorithm.
    435     bool init(int scaling_mode) {
    436       if (!valid_supply) return false;
    437       excess = supply;
     424    bool init(bool scaling) {
     425      if (!_valid_supply) return false;
     426      _excess = _supply;
    438427
    439428      // Initilaizing delta value
    440       if (scaling_mode == WITH_SCALING) {
     429      if (scaling) {
    441430        // With scaling
    442431        Supply max_sup = 0, max_dem = 0;
    443         for (NodeIt n(graph); n != INVALID; ++n) {
    444           if ( supply[n] > max_sup) max_sup =  supply[n];
    445           if (-supply[n] > max_dem) max_dem = -supply[n];
     432        for (NodeIt n(_graph); n != INVALID; ++n) {
     433          if ( _supply[n] > max_sup) max_sup =  _supply[n];
     434          if (-_supply[n] > max_dem) max_dem = -_supply[n];
    446435        }
    447436        if (max_dem < max_sup) max_sup = max_dem;
    448         phase_num = 0;
    449         for (delta = 1; 2 * delta <= max_sup; delta *= 2)
    450           ++phase_num;
     437        _phase_num = 0;
     438        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
     439          ++_phase_num;
    451440      } else {
    452441        // Without scaling
    453         delta = 1;
     442        _delta = 1;
    454443      }
    455444      return true;
    456445    }
    457446
    458     /// Executes the algorithm.
    459447    bool start() {
    460       if (delta > 1)
     448      if (_delta > 1)
    461449        return startWithScaling();
    462450      else
    … …  
    464452    }
    465453
    466     /// \brief Executes the capacity scaling version of the successive
    467     /// shortest path algorithm.
     454    /// Executes the capacity scaling algorithm.
    468455    bool startWithScaling() {
    469456      // Processing capacity scaling phases
    … …  
    473460      while (true) {
    474461        // Saturating all edges not satisfying the optimality condition
    475         for (EdgeIt e(graph); e != INVALID; ++e) {
    476           Node u = graph.source(e), v = graph.target(e);
    477           Cost c = cost[e] - potential[u] + potential[v];
    478           if (c < 0 && res_cap[e] >= delta) {
    479             excess[u] -= res_cap[e];
    480             excess[v] += res_cap[e];
    481             flow[e] = capacity[e];
    482             res_cap[e] = 0;
    483           }
    484           else if (c > 0 && flow[e] >= delta) {
    485             excess[u] += flow[e];
    486             excess[v] -= flow[e];
    487             flow[e] = 0;
    488             res_cap[e] = capacity[e];
     462        for (EdgeIt e(_graph); e != INVALID; ++e) {
     463          Node u = _graph.source(e), v = _graph.target(e);
     464          Cost c = _cost[e] + _potential[u] - _potential[v];
     465          if (c < 0 && _res_cap[e] >= _delta) {
     466            _excess[u] -= _res_cap[e];
     467            _excess[v] += _res_cap[e];
     468            _flow[e] = _capacity[e];
     469            _res_cap[e] = 0;
     470          }
     471          else if (c > 0 && _flow[e] >= _delta) {
     472            _excess[u] += _flow[e];
     473            _excess[v] -= _flow[e];
     474            _flow[e] = 0;
     475            _res_cap[e] = _capacity[e];
    489476          }
    490477        }
    491478
    492479        // Finding excess nodes and deficit nodes
    493         excess_nodes.clear();
    494         deficit_nodes.clear();
    495         for (NodeIt n(graph); n != INVALID; ++n) {
    496           if (excess[n] >=  delta) excess_nodes.push_back(n);
    497           if (excess[n] <= -delta) deficit_nodes.push_back(n);
     480        _excess_nodes.clear();
     481        _deficit_nodes.clear();
     482        for (NodeIt n(_graph); n != INVALID; ++n) {
     483          if (_excess[n] >=  _delta) _excess_nodes.push_back(n);
     484          if (_excess[n] <= -_delta) _deficit_nodes.push_back(n);
    498485        }
    499486        int next_node = 0;
    500487
    501488        // Finding augmenting shortest paths
    502         while (next_node < excess_nodes.size()) {
     489        while (next_node < int(_excess_nodes.size())) {
    503490          // Checking deficit nodes
    504           if (delta > 1) {
     491          if (_delta > 1) {
    505492            bool delta_deficit = false;
    506             for (int i = 0; i < deficit_nodes.size(); ++i) {
    507               if (excess[deficit_nodes[i]] <= -delta) {
     493            for (int i = 0; i < int(_deficit_nodes.size()); ++i) {
     494              if (_excess[_deficit_nodes[i]] <= -_delta) {
    508495                delta_deficit = true;
    509496                break;
    … …  
    514501
    515502          // Running Dijkstra
    516           s = excess_nodes[next_node];
    517           if ((t = dijkstra.run(s, delta)) == INVALID) {
    518             if (delta > 1) {
     503          s = _excess_nodes[next_node];
     504          if ((t = _dijkstra.run(s, _delta)) == INVALID) {
     505            if (_delta > 1) {
    519506              ++next_node;
    520507              continue;
    … …  
    524511
    525512          // Augmenting along a shortest path from s to t.
    526           Capacity d = excess[s] < -excess[t] ? excess[s] : -excess[t];
     513          Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
    527514          Node u = t;
    528515          Edge e;
    529           if (d > delta) {
    530             while ((e = pred[u]) != INVALID) {
     516          if (d > _delta) {
     517            while ((e = _pred[u]) != INVALID) {
    531518              Capacity rc;
    532               if (u == graph.target(e)) {
    533                 rc = res_cap[e];
    534                 u = graph.source(e);
     519              if (u == _graph.target(e)) {
     520                rc = _res_cap[e];
     521                u = _graph.source(e);
    535522              } else {
    536                 rc = flow[e];
    537                 u = graph.target(e);
     523                rc = _flow[e];
     524                u = _graph.target(e);
    538525              }
    539526              if (rc < d) d = rc;
    … …  
    541528          }
    542529          u = t;
    543           while ((e = pred[u]) != INVALID) {
    544             if (u == graph.target(e)) {
    545               flow[e] += d;
    546               res_cap[e] -= d;
    547               u = graph.source(e);
     530          while ((e = _pred[u]) != INVALID) {
     531            if (u == _graph.target(e)) {
     532              _flow[e] += d;
     533              _res_cap[e] -= d;
     534              u = _graph.source(e);
    548535            } else {
    549               flow[e] -= d;
    550               res_cap[e] += d;
    551               u = graph.target(e);
     536              _flow[e] -= d;
     537              _res_cap[e] += d;
     538              u = _graph.target(e);
    552539            }
    553540          }
    554           excess[s] -= d;
    555           excess[t] += d;
    556 
    557           if (excess[s] < delta) ++next_node;
     541          _excess[s] -= d;
     542          _excess[t] += d;
     543
     544          if (_excess[s] < _delta) ++next_node;
    558545        }
    559546
    560         if (delta == 1) break;
    561         if (++phase_cnt > phase_num / 4) factor = 2;
    562         delta = delta <= factor ? 1 : delta / factor;
     547        if (_delta == 1) break;
     548        if (++phase_cnt > _phase_num / 4) factor = 2;
     549        _delta = _delta <= factor ? 1 : _delta / factor;
    563550      }
    564551
    565552      // Handling non-zero lower bounds
    566       if (lower) {
    567         for (EdgeIt e(graph); e != INVALID; ++e)
    568           flow[e] += (*lower)[e];
     553      if (_lower) {
     554        for (EdgeIt e(_graph); e != INVALID; ++e)
     555          _flow[e] += (*_lower)[e];
    569556      }
    570557      return true;
    571558    }
    572559
    573     /// \brief Executes the successive shortest path algorithm without
    574     /// capacity scaling.
     560    /// Executes the successive shortest path algorithm.
    575561    bool startWithoutScaling() {
    576562      // Finding excess nodes
    577       for (NodeIt n(graph); n != INVALID; ++n)
    578         if (excess[n] > 0) excess_nodes.push_back(n);
    579       if (excess_nodes.size() == 0) return true;
     563      for (NodeIt n(_graph); n != INVALID; ++n)
     564        if (_excess[n] > 0) _excess_nodes.push_back(n);
     565      if (_excess_nodes.size() == 0) return true;
    580566      int next_node = 0;
    581567
    582568      // Finding shortest paths
    583569      Node s, t;
    584       while ( excess[excess_nodes[next_node]] > 0 ||
    585               ++next_node < excess_nodes.size() )
     570      while ( _excess[_excess_nodes[next_node]] > 0 ||
     571              ++next_node < int(_excess_nodes.size()) )
    586572      {
    587573        // Running Dijkstra
    588         s = excess_nodes[next_node];
    589         if ((t = dijkstra.run(s, 1)) == INVALID)
     574        s = _excess_nodes[next_node];
     575        if ((t = _dijkstra.run(s, 1)) == INVALID)
    590576          return false;
    591577
    592578        // Augmenting along a shortest path from s to t
    593         Capacity d = excess[s] < -excess[t] ? excess[s] : -excess[t];
     579        Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
    594580        Node u = t;
    595581        Edge e;
    596         while ((e = pred[u]) != INVALID) {
     582        while ((e = _pred[u]) != INVALID) {
    597583          Capacity rc;
    598           if (u == graph.target(e)) {
    599             rc = res_cap[e];
    600             u = graph.source(e);
     584          if (u == _graph.target(e)) {
     585            rc = _res_cap[e];
     586            u = _graph.source(e);
    601587          } else {
    602             rc = flow[e];
    603             u = graph.target(e);
     588            rc = _flow[e];
     589            u = _graph.target(e);
    604590          }
    605591          if (rc < d) d = rc;
    606592        }
    607593        u = t;
    608         while ((e = pred[u]) != INVALID) {
    609           if (u == graph.target(e)) {
    610             flow[e] += d;
    611             res_cap[e] -= d;
    612             u = graph.source(e);
     594        while ((e = _pred[u]) != INVALID) {
     595          if (u == _graph.target(e)) {
     596            _flow[e] += d;
     597            _res_cap[e] -= d;
     598            u = _graph.source(e);
    613599          } else {
    614             flow[e] -= d;
    615             res_cap[e] += d;
    616             u = graph.target(e);
     600            _flow[e] -= d;
     601            _res_cap[e] += d;
     602            u = _graph.target(e);
    617603          }
    618604        }
    619         excess[s] -= d;
    620         excess[t] += d;
     605        _excess[s] -= d;
     606        _excess[t] += d;
    621607      }
    622608
    623609      // Handling non-zero lower bounds
    624       if (lower) {
    625         for (EdgeIt e(graph); e != INVALID; ++e)
    626           flow[e] += (*lower)[e];
     610      if (_lower) {
     611        for (EdgeIt e(_graph); e != INVALID; ++e)
     612          _flow[e] += (*_lower)[e];
    627613      }
    628614      return true;
Note: See TracChangeset for help on using the changeset viewer.