lemon/capacity_scaling.h
author deba
Sun, 05 Oct 2008 20:08:13 +0000
changeset 2622 fa2877651022
parent 2589 1bbb28acb8c9
child 2623 90defb96ee61
permissions -rw-r--r--
Fix _setCoeff
deba@2440
     1
/* -*- C++ -*-
deba@2440
     2
 *
deba@2440
     3
 * This file is a part of LEMON, a generic C++ optimization library
deba@2440
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
deba@2440
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2440
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2440
     8
 *
deba@2440
     9
 * Permission to use, modify and distribute this software is granted
deba@2440
    10
 * provided that this copyright notice appears in all copies. For
deba@2440
    11
 * precise terms see the accompanying LICENSE file.
deba@2440
    12
 *
deba@2440
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@2440
    14
 * express or implied, and with no claim as to its suitability for any
deba@2440
    15
 * purpose.
deba@2440
    16
 *
deba@2440
    17
 */
deba@2440
    18
deba@2440
    19
#ifndef LEMON_CAPACITY_SCALING_H
deba@2440
    20
#define LEMON_CAPACITY_SCALING_H
deba@2440
    21
deba@2440
    22
/// \ingroup min_cost_flow
deba@2440
    23
///
deba@2440
    24
/// \file
kpeter@2574
    25
/// \brief Capacity scaling algorithm for finding a minimum cost flow.
kpeter@2574
    26
kpeter@2574
    27
#include <vector>
kpeter@2535
    28
#include <lemon/bin_heap.h>
deba@2457
    29
deba@2440
    30
namespace lemon {
deba@2440
    31
deba@2440
    32
  /// \addtogroup min_cost_flow
deba@2440
    33
  /// @{
deba@2440
    34
kpeter@2574
    35
  /// \brief Implementation of the capacity scaling algorithm for
kpeter@2574
    36
  /// finding a minimum cost flow.
deba@2440
    37
  ///
kpeter@2535
    38
  /// \ref CapacityScaling implements the capacity scaling version
kpeter@2535
    39
  /// of the successive shortest path algorithm for finding a minimum
kpeter@2535
    40
  /// cost flow.
deba@2440
    41
  ///
kpeter@2574
    42
  /// \tparam Graph The directed graph type the algorithm runs on.
kpeter@2574
    43
  /// \tparam LowerMap The type of the lower bound map.
kpeter@2574
    44
  /// \tparam CapacityMap The type of the capacity (upper bound) map.
kpeter@2574
    45
  /// \tparam CostMap The type of the cost (length) map.
kpeter@2574
    46
  /// \tparam SupplyMap The type of the supply map.
deba@2440
    47
  ///
deba@2440
    48
  /// \warning
kpeter@2574
    49
  /// - Edge capacities and costs should be \e non-negative \e integers.
kpeter@2574
    50
  /// - Supply values should be \e signed \e integers.
kpeter@2581
    51
  /// - The value types of the maps should be convertible to each other.
kpeter@2581
    52
  /// - \c CostMap::Value must be signed type.
deba@2440
    53
  ///
deba@2440
    54
  /// \author Peter Kovacs
kpeter@2533
    55
  template < typename Graph,
kpeter@2535
    56
             typename LowerMap = typename Graph::template EdgeMap<int>,
kpeter@2574
    57
             typename CapacityMap = typename Graph::template EdgeMap<int>,
kpeter@2535
    58
             typename CostMap = typename Graph::template EdgeMap<int>,
kpeter@2574
    59
             typename SupplyMap = typename Graph::template NodeMap<int> >
deba@2440
    60
  class CapacityScaling
deba@2440
    61
  {
kpeter@2556
    62
    GRAPH_TYPEDEFS(typename Graph);
deba@2440
    63
deba@2440
    64
    typedef typename CapacityMap::Value Capacity;
deba@2440
    65
    typedef typename CostMap::Value Cost;
deba@2440
    66
    typedef typename SupplyMap::Value Supply;
kpeter@2556
    67
    typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
kpeter@2556
    68
    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
kpeter@2535
    69
    typedef typename Graph::template NodeMap<Edge> PredMap;
deba@2440
    70
deba@2440
    71
  public:
deba@2440
    72
kpeter@2556
    73
    /// The type of the flow map.
kpeter@2556
    74
    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
kpeter@2556
    75
    /// The type of the potential map.
deba@2440
    76
    typedef typename Graph::template NodeMap<Cost> PotentialMap;
deba@2440
    77
kpeter@2574
    78
  private:
deba@2440
    79
kpeter@2535
    80
    /// \brief Special implementation of the \ref Dijkstra algorithm
kpeter@2574
    81
    /// for finding shortest paths in the residual network.
kpeter@2574
    82
    ///
kpeter@2574
    83
    /// \ref ResidualDijkstra is a special implementation of the
kpeter@2574
    84
    /// \ref Dijkstra algorithm for finding shortest paths in the
kpeter@2574
    85
    /// residual network of the graph with respect to the reduced edge
kpeter@2574
    86
    /// costs and modifying the node potentials according to the
kpeter@2574
    87
    /// distance of the nodes.
kpeter@2535
    88
    class ResidualDijkstra
deba@2440
    89
    {
kpeter@2535
    90
      typedef typename Graph::template NodeMap<int> HeapCrossRef;
kpeter@2535
    91
      typedef BinHeap<Cost, HeapCrossRef> Heap;
kpeter@2535
    92
kpeter@2574
    93
    private:
kpeter@2535
    94
kpeter@2574
    95
      // The directed graph the algorithm runs on
kpeter@2574
    96
      const Graph &_graph;
kpeter@2535
    97
kpeter@2574
    98
      // The main maps
kpeter@2574
    99
      const FlowMap &_flow;
kpeter@2574
   100
      const CapacityEdgeMap &_res_cap;
kpeter@2574
   101
      const CostMap &_cost;
kpeter@2574
   102
      const SupplyNodeMap &_excess;
kpeter@2574
   103
      PotentialMap &_potential;
kpeter@2535
   104
kpeter@2574
   105
      // The distance map
kpeter@2588
   106
      PotentialMap _dist;
kpeter@2574
   107
      // The pred edge map
kpeter@2574
   108
      PredMap &_pred;
kpeter@2574
   109
      // The processed (i.e. permanently labeled) nodes
kpeter@2574
   110
      std::vector<Node> _proc_nodes;
deba@2440
   111
deba@2440
   112
    public:
deba@2440
   113
kpeter@2581
   114
      /// Constructor.
kpeter@2574
   115
      ResidualDijkstra( const Graph &graph,
kpeter@2574
   116
                        const FlowMap &flow,
kpeter@2574
   117
                        const CapacityEdgeMap &res_cap,
kpeter@2574
   118
                        const CostMap &cost,
kpeter@2574
   119
                        const SupplyMap &excess,
kpeter@2574
   120
                        PotentialMap &potential,
kpeter@2574
   121
                        PredMap &pred ) :
kpeter@2574
   122
        _graph(graph), _flow(flow), _res_cap(res_cap), _cost(cost),
kpeter@2574
   123
        _excess(excess), _potential(potential), _dist(graph),
kpeter@2574
   124
        _pred(pred)
kpeter@2535
   125
      {}
deba@2440
   126
kpeter@2620
   127
      /// Run the algorithm from the given source node.
kpeter@2588
   128
      Node run(Node s, Capacity delta = 1) {
kpeter@2574
   129
        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
kpeter@2535
   130
        Heap heap(heap_cross_ref);
kpeter@2535
   131
        heap.push(s, 0);
kpeter@2574
   132
        _pred[s] = INVALID;
kpeter@2574
   133
        _proc_nodes.clear();
kpeter@2535
   134
kpeter@2535
   135
        // Processing nodes
kpeter@2574
   136
        while (!heap.empty() && _excess[heap.top()] > -delta) {
kpeter@2535
   137
          Node u = heap.top(), v;
kpeter@2574
   138
          Cost d = heap.prio() + _potential[u], nd;
kpeter@2574
   139
          _dist[u] = heap.prio();
kpeter@2535
   140
          heap.pop();
kpeter@2574
   141
          _proc_nodes.push_back(u);
kpeter@2535
   142
kpeter@2535
   143
          // Traversing outgoing edges
kpeter@2574
   144
          for (OutEdgeIt e(_graph, u); e != INVALID; ++e) {
kpeter@2574
   145
            if (_res_cap[e] >= delta) {
kpeter@2574
   146
              v = _graph.target(e);
kpeter@2535
   147
              switch(heap.state(v)) {
kpeter@2535
   148
              case Heap::PRE_HEAP:
kpeter@2574
   149
                heap.push(v, d + _cost[e] - _potential[v]);
kpeter@2574
   150
                _pred[v] = e;
kpeter@2535
   151
                break;
kpeter@2535
   152
              case Heap::IN_HEAP:
kpeter@2574
   153
                nd = d + _cost[e] - _potential[v];
kpeter@2535
   154
                if (nd < heap[v]) {
kpeter@2535
   155
                  heap.decrease(v, nd);
kpeter@2574
   156
                  _pred[v] = e;
kpeter@2535
   157
                }
kpeter@2535
   158
                break;
kpeter@2535
   159
              case Heap::POST_HEAP:
kpeter@2535
   160
                break;
kpeter@2535
   161
              }
kpeter@2535
   162
            }
kpeter@2535
   163
          }
kpeter@2535
   164
kpeter@2535
   165
          // Traversing incoming edges
kpeter@2574
   166
          for (InEdgeIt e(_graph, u); e != INVALID; ++e) {
kpeter@2574
   167
            if (_flow[e] >= delta) {
kpeter@2574
   168
              v = _graph.source(e);
kpeter@2535
   169
              switch(heap.state(v)) {
kpeter@2535
   170
              case Heap::PRE_HEAP:
kpeter@2574
   171
                heap.push(v, d - _cost[e] - _potential[v]);
kpeter@2574
   172
                _pred[v] = e;
kpeter@2535
   173
                break;
kpeter@2535
   174
              case Heap::IN_HEAP:
kpeter@2574
   175
                nd = d - _cost[e] - _potential[v];
kpeter@2535
   176
                if (nd < heap[v]) {
kpeter@2535
   177
                  heap.decrease(v, nd);
kpeter@2574
   178
                  _pred[v] = e;
kpeter@2535
   179
                }
kpeter@2535
   180
                break;
kpeter@2535
   181
              case Heap::POST_HEAP:
kpeter@2535
   182
                break;
kpeter@2535
   183
              }
kpeter@2535
   184
            }
kpeter@2535
   185
          }
kpeter@2535
   186
        }
kpeter@2535
   187
        if (heap.empty()) return INVALID;
kpeter@2535
   188
kpeter@2535
   189
        // Updating potentials of processed nodes
kpeter@2535
   190
        Node t = heap.top();
kpeter@2574
   191
        Cost t_dist = heap.prio();
kpeter@2574
   192
        for (int i = 0; i < int(_proc_nodes.size()); ++i)
kpeter@2574
   193
          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
kpeter@2535
   194
kpeter@2535
   195
        return t;
deba@2440
   196
      }
deba@2440
   197
kpeter@2535
   198
    }; //class ResidualDijkstra
deba@2440
   199
kpeter@2574
   200
  private:
deba@2440
   201
kpeter@2574
   202
    // The directed graph the algorithm runs on
kpeter@2574
   203
    const Graph &_graph;
kpeter@2574
   204
    // The original lower bound map
kpeter@2574
   205
    const LowerMap *_lower;
kpeter@2574
   206
    // The modified capacity map
kpeter@2574
   207
    CapacityEdgeMap _capacity;
kpeter@2574
   208
    // The original cost map
kpeter@2574
   209
    const CostMap &_cost;
kpeter@2574
   210
    // The modified supply map
kpeter@2574
   211
    SupplyNodeMap _supply;
kpeter@2574
   212
    bool _valid_supply;
deba@2440
   213
kpeter@2574
   214
    // Edge map of the current flow
kpeter@2581
   215
    FlowMap *_flow;
kpeter@2581
   216
    bool _local_flow;
kpeter@2574
   217
    // Node map of the current potentials
kpeter@2581
   218
    PotentialMap *_potential;
kpeter@2581
   219
    bool _local_potential;
deba@2440
   220
kpeter@2574
   221
    // The residual capacity map
kpeter@2574
   222
    CapacityEdgeMap _res_cap;
kpeter@2574
   223
    // The excess map
kpeter@2574
   224
    SupplyNodeMap _excess;
kpeter@2574
   225
    // The excess nodes (i.e. nodes with positive excess)
kpeter@2574
   226
    std::vector<Node> _excess_nodes;
kpeter@2574
   227
    // The deficit nodes (i.e. nodes with negative excess)
kpeter@2574
   228
    std::vector<Node> _deficit_nodes;
deba@2440
   229
kpeter@2574
   230
    // The delta parameter used for capacity scaling
kpeter@2574
   231
    Capacity _delta;
kpeter@2574
   232
    // The maximum number of phases
kpeter@2574
   233
    int _phase_num;
deba@2440
   234
kpeter@2574
   235
    // The pred edge map
kpeter@2574
   236
    PredMap _pred;
kpeter@2574
   237
    // Implementation of the Dijkstra algorithm for finding augmenting
kpeter@2574
   238
    // shortest paths in the residual network
kpeter@2581
   239
    ResidualDijkstra *_dijkstra;
deba@2440
   240
kpeter@2581
   241
  public:
deba@2440
   242
kpeter@2581
   243
    /// \brief General constructor (with lower bounds).
deba@2440
   244
    ///
kpeter@2581
   245
    /// General constructor (with lower bounds).
deba@2440
   246
    ///
kpeter@2574
   247
    /// \param graph The directed graph the algorithm runs on.
kpeter@2574
   248
    /// \param lower The lower bounds of the edges.
kpeter@2574
   249
    /// \param capacity The capacities (upper bounds) of the edges.
kpeter@2574
   250
    /// \param cost The cost (length) values of the edges.
kpeter@2574
   251
    /// \param supply The supply values of the nodes (signed).
kpeter@2574
   252
    CapacityScaling( const Graph &graph,
kpeter@2574
   253
                     const LowerMap &lower,
kpeter@2574
   254
                     const CapacityMap &capacity,
kpeter@2574
   255
                     const CostMap &cost,
kpeter@2574
   256
                     const SupplyMap &supply ) :
kpeter@2574
   257
      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
kpeter@2581
   258
      _supply(graph), _flow(0), _local_flow(false),
kpeter@2581
   259
      _potential(0), _local_potential(false),
kpeter@2581
   260
      _res_cap(graph), _excess(graph), _pred(graph)
deba@2440
   261
    {
kpeter@2556
   262
      // Removing non-zero lower bounds
kpeter@2574
   263
      _capacity = subMap(capacity, lower);
kpeter@2574
   264
      _res_cap = _capacity;
deba@2440
   265
      Supply sum = 0;
kpeter@2574
   266
      for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@2574
   267
        Supply s = supply[n];
kpeter@2574
   268
        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
kpeter@2574
   269
          s += lower[e];
kpeter@2574
   270
        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
kpeter@2574
   271
          s -= lower[e];
kpeter@2574
   272
        _supply[n] = s;
kpeter@2535
   273
        sum += s;
deba@2440
   274
      }
kpeter@2574
   275
      _valid_supply = sum == 0;
deba@2440
   276
    }
deba@2440
   277
kpeter@2581
   278
    /// \brief General constructor (without lower bounds).
deba@2440
   279
    ///
kpeter@2581
   280
    /// General constructor (without lower bounds).
deba@2440
   281
    ///
kpeter@2574
   282
    /// \param graph The directed graph the algorithm runs on.
kpeter@2574
   283
    /// \param capacity The capacities (upper bounds) of the edges.
kpeter@2574
   284
    /// \param cost The cost (length) values of the edges.
kpeter@2574
   285
    /// \param supply The supply values of the nodes (signed).
kpeter@2574
   286
    CapacityScaling( const Graph &graph,
kpeter@2574
   287
                     const CapacityMap &capacity,
kpeter@2574
   288
                     const CostMap &cost,
kpeter@2574
   289
                     const SupplyMap &supply ) :
kpeter@2574
   290
      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
kpeter@2581
   291
      _supply(supply), _flow(0), _local_flow(false),
kpeter@2581
   292
      _potential(0), _local_potential(false),
kpeter@2581
   293
      _res_cap(capacity), _excess(graph), _pred(graph)
deba@2440
   294
    {
deba@2440
   295
      // Checking the sum of supply values
deba@2440
   296
      Supply sum = 0;
kpeter@2574
   297
      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
kpeter@2574
   298
      _valid_supply = sum == 0;
deba@2440
   299
    }
deba@2440
   300
kpeter@2581
   301
    /// \brief Simple constructor (with lower bounds).
deba@2440
   302
    ///
kpeter@2581
   303
    /// Simple constructor (with lower bounds).
deba@2440
   304
    ///
kpeter@2574
   305
    /// \param graph The directed graph the algorithm runs on.
kpeter@2574
   306
    /// \param lower The lower bounds of the edges.
kpeter@2574
   307
    /// \param capacity The capacities (upper bounds) of the edges.
kpeter@2574
   308
    /// \param cost The cost (length) values of the edges.
kpeter@2574
   309
    /// \param s The source node.
kpeter@2574
   310
    /// \param t The target node.
kpeter@2574
   311
    /// \param flow_value The required amount of flow from node \c s
kpeter@2574
   312
    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
kpeter@2574
   313
    CapacityScaling( const Graph &graph,
kpeter@2574
   314
                     const LowerMap &lower,
kpeter@2574
   315
                     const CapacityMap &capacity,
kpeter@2574
   316
                     const CostMap &cost,
kpeter@2574
   317
                     Node s, Node t,
kpeter@2574
   318
                     Supply flow_value ) :
kpeter@2574
   319
      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
kpeter@2581
   320
      _supply(graph), _flow(0), _local_flow(false),
kpeter@2581
   321
      _potential(0), _local_potential(false),
kpeter@2581
   322
      _res_cap(graph), _excess(graph), _pred(graph)
deba@2440
   323
    {
kpeter@2556
   324
      // Removing non-zero lower bounds
kpeter@2574
   325
      _capacity = subMap(capacity, lower);
kpeter@2574
   326
      _res_cap = _capacity;
kpeter@2574
   327
      for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@2574
   328
        Supply sum = 0;
kpeter@2574
   329
        if (n == s) sum =  flow_value;
kpeter@2574
   330
        if (n == t) sum = -flow_value;
kpeter@2574
   331
        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
kpeter@2574
   332
          sum += lower[e];
kpeter@2574
   333
        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
kpeter@2574
   334
          sum -= lower[e];
kpeter@2574
   335
        _supply[n] = sum;
deba@2440
   336
      }
kpeter@2574
   337
      _valid_supply = true;
deba@2440
   338
    }
deba@2440
   339
kpeter@2581
   340
    /// \brief Simple constructor (without lower bounds).
deba@2440
   341
    ///
kpeter@2581
   342
    /// Simple constructor (without lower bounds).
deba@2440
   343
    ///
kpeter@2574
   344
    /// \param graph The directed graph the algorithm runs on.
kpeter@2574
   345
    /// \param capacity The capacities (upper bounds) of the edges.
kpeter@2574
   346
    /// \param cost The cost (length) values of the edges.
kpeter@2574
   347
    /// \param s The source node.
kpeter@2574
   348
    /// \param t The target node.
kpeter@2574
   349
    /// \param flow_value The required amount of flow from node \c s
kpeter@2574
   350
    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
kpeter@2574
   351
    CapacityScaling( const Graph &graph,
kpeter@2574
   352
                     const CapacityMap &capacity,
kpeter@2574
   353
                     const CostMap &cost,
kpeter@2574
   354
                     Node s, Node t,
kpeter@2574
   355
                     Supply flow_value ) :
kpeter@2574
   356
      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
kpeter@2581
   357
      _supply(graph, 0), _flow(0), _local_flow(false),
kpeter@2581
   358
      _potential(0), _local_potential(false),
kpeter@2581
   359
      _res_cap(capacity), _excess(graph), _pred(graph)
deba@2440
   360
    {
kpeter@2574
   361
      _supply[s] =  flow_value;
kpeter@2574
   362
      _supply[t] = -flow_value;
kpeter@2574
   363
      _valid_supply = true;
deba@2440
   364
    }
deba@2440
   365
kpeter@2581
   366
    /// Destructor.
kpeter@2581
   367
    ~CapacityScaling() {
kpeter@2581
   368
      if (_local_flow) delete _flow;
kpeter@2581
   369
      if (_local_potential) delete _potential;
kpeter@2581
   370
      delete _dijkstra;
kpeter@2581
   371
    }
kpeter@2581
   372
kpeter@2620
   373
    /// \brief Set the flow map.
kpeter@2581
   374
    ///
kpeter@2620
   375
    /// Set the flow map.
kpeter@2581
   376
    ///
kpeter@2581
   377
    /// \return \c (*this)
kpeter@2581
   378
    CapacityScaling& flowMap(FlowMap &map) {
kpeter@2581
   379
      if (_local_flow) {
kpeter@2581
   380
        delete _flow;
kpeter@2581
   381
        _local_flow = false;
kpeter@2581
   382
      }
kpeter@2581
   383
      _flow = &map;
kpeter@2581
   384
      return *this;
kpeter@2581
   385
    }
kpeter@2581
   386
kpeter@2620
   387
    /// \brief Set the potential map.
kpeter@2581
   388
    ///
kpeter@2620
   389
    /// Set the potential map.
kpeter@2581
   390
    ///
kpeter@2581
   391
    /// \return \c (*this)
kpeter@2581
   392
    CapacityScaling& potentialMap(PotentialMap &map) {
kpeter@2581
   393
      if (_local_potential) {
kpeter@2581
   394
        delete _potential;
kpeter@2581
   395
        _local_potential = false;
kpeter@2581
   396
      }
kpeter@2581
   397
      _potential = &map;
kpeter@2581
   398
      return *this;
kpeter@2581
   399
    }
kpeter@2581
   400
kpeter@2581
   401
    /// \name Execution control
kpeter@2581
   402
kpeter@2581
   403
    /// @{
kpeter@2581
   404
kpeter@2620
   405
    /// \brief Run the algorithm.
kpeter@2556
   406
    ///
kpeter@2620
   407
    /// This function runs the algorithm.
kpeter@2556
   408
    ///
kpeter@2574
   409
    /// \param scaling Enable or disable capacity scaling.
kpeter@2556
   410
    /// If the maximum edge capacity and/or the amount of total supply
kpeter@2574
   411
    /// is rather small, the algorithm could be slightly faster without
kpeter@2556
   412
    /// scaling.
kpeter@2556
   413
    ///
kpeter@2556
   414
    /// \return \c true if a feasible flow can be found.
kpeter@2574
   415
    bool run(bool scaling = true) {
kpeter@2574
   416
      return init(scaling) && start();
kpeter@2556
   417
    }
kpeter@2556
   418
kpeter@2581
   419
    /// @}
kpeter@2581
   420
kpeter@2581
   421
    /// \name Query Functions
kpeter@2620
   422
    /// The results of the algorithm can be obtained using these
kpeter@2620
   423
    /// functions.\n
kpeter@2620
   424
    /// \ref lemon::CapacityScaling::run() "run()" must be called before
kpeter@2620
   425
    /// using them.
kpeter@2581
   426
kpeter@2581
   427
    /// @{
kpeter@2581
   428
kpeter@2620
   429
    /// \brief Return a const reference to the edge map storing the
kpeter@2574
   430
    /// found flow.
deba@2440
   431
    ///
kpeter@2620
   432
    /// Return a const reference to the edge map storing the found flow.
deba@2440
   433
    ///
deba@2440
   434
    /// \pre \ref run() must be called before using this function.
deba@2440
   435
    const FlowMap& flowMap() const {
kpeter@2581
   436
      return *_flow;
deba@2440
   437
    }
deba@2440
   438
kpeter@2620
   439
    /// \brief Return a const reference to the node map storing the
kpeter@2574
   440
    /// found potentials (the dual solution).
deba@2440
   441
    ///
kpeter@2620
   442
    /// Return a const reference to the node map storing the found
kpeter@2574
   443
    /// potentials (the dual solution).
deba@2440
   444
    ///
deba@2440
   445
    /// \pre \ref run() must be called before using this function.
deba@2440
   446
    const PotentialMap& potentialMap() const {
kpeter@2581
   447
      return *_potential;
kpeter@2581
   448
    }
kpeter@2581
   449
kpeter@2620
   450
    /// \brief Return the flow on the given edge.
kpeter@2581
   451
    ///
kpeter@2620
   452
    /// Return the flow on the given edge.
kpeter@2581
   453
    ///
kpeter@2581
   454
    /// \pre \ref run() must be called before using this function.
kpeter@2581
   455
    Capacity flow(const Edge& edge) const {
kpeter@2581
   456
      return (*_flow)[edge];
kpeter@2581
   457
    }
kpeter@2581
   458
kpeter@2620
   459
    /// \brief Return the potential of the given node.
kpeter@2581
   460
    ///
kpeter@2620
   461
    /// Return the potential of the given node.
kpeter@2581
   462
    ///
kpeter@2581
   463
    /// \pre \ref run() must be called before using this function.
kpeter@2581
   464
    Cost potential(const Node& node) const {
kpeter@2581
   465
      return (*_potential)[node];
deba@2440
   466
    }
deba@2440
   467
kpeter@2620
   468
    /// \brief Return the total cost of the found flow.
deba@2440
   469
    ///
kpeter@2620
   470
    /// Return the total cost of the found flow. The complexity of the
deba@2440
   471
    /// function is \f$ O(e) \f$.
deba@2440
   472
    ///
deba@2440
   473
    /// \pre \ref run() must be called before using this function.
deba@2440
   474
    Cost totalCost() const {
deba@2440
   475
      Cost c = 0;
kpeter@2574
   476
      for (EdgeIt e(_graph); e != INVALID; ++e)
kpeter@2581
   477
        c += (*_flow)[e] * _cost[e];
deba@2440
   478
      return c;
deba@2440
   479
    }
deba@2440
   480
kpeter@2581
   481
    /// @}
kpeter@2581
   482
kpeter@2574
   483
  private:
deba@2440
   484
kpeter@2620
   485
    /// Initialize the algorithm.
kpeter@2574
   486
    bool init(bool scaling) {
kpeter@2574
   487
      if (!_valid_supply) return false;
kpeter@2581
   488
kpeter@2581
   489
      // Initializing maps
kpeter@2581
   490
      if (!_flow) {
kpeter@2581
   491
        _flow = new FlowMap(_graph);
kpeter@2581
   492
        _local_flow = true;
kpeter@2581
   493
      }
kpeter@2581
   494
      if (!_potential) {
kpeter@2581
   495
        _potential = new PotentialMap(_graph);
kpeter@2581
   496
        _local_potential = true;
kpeter@2581
   497
      }
kpeter@2581
   498
      for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
kpeter@2581
   499
      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
kpeter@2574
   500
      _excess = _supply;
deba@2440
   501
kpeter@2581
   502
      _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost,
kpeter@2581
   503
                                        _excess, *_potential, _pred );
kpeter@2581
   504
kpeter@2581
   505
      // Initializing delta value
kpeter@2574
   506
      if (scaling) {
kpeter@2535
   507
        // With scaling
kpeter@2535
   508
        Supply max_sup = 0, max_dem = 0;
kpeter@2574
   509
        for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@2574
   510
          if ( _supply[n] > max_sup) max_sup =  _supply[n];
kpeter@2574
   511
          if (-_supply[n] > max_dem) max_dem = -_supply[n];
kpeter@2535
   512
        }
kpeter@2588
   513
        Capacity max_cap = 0;
kpeter@2588
   514
        for (EdgeIt e(_graph); e != INVALID; ++e) {
kpeter@2588
   515
          if (_capacity[e] > max_cap) max_cap = _capacity[e];
kpeter@2588
   516
        }
kpeter@2588
   517
        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
kpeter@2574
   518
        _phase_num = 0;
kpeter@2574
   519
        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
kpeter@2574
   520
          ++_phase_num;
kpeter@2535
   521
      } else {
kpeter@2535
   522
        // Without scaling
kpeter@2574
   523
        _delta = 1;
deba@2440
   524
      }
kpeter@2581
   525
deba@2440
   526
      return true;
deba@2440
   527
    }
deba@2440
   528
kpeter@2535
   529
    bool start() {
kpeter@2574
   530
      if (_delta > 1)
kpeter@2535
   531
        return startWithScaling();
kpeter@2535
   532
      else
kpeter@2535
   533
        return startWithoutScaling();
kpeter@2535
   534
    }
kpeter@2535
   535
kpeter@2620
   536
    /// Execute the capacity scaling algorithm.
kpeter@2535
   537
    bool startWithScaling() {
kpeter@2535
   538
      // Processing capacity scaling phases
kpeter@2535
   539
      Node s, t;
kpeter@2535
   540
      int phase_cnt = 0;
kpeter@2535
   541
      int factor = 4;
kpeter@2535
   542
      while (true) {
kpeter@2535
   543
        // Saturating all edges not satisfying the optimality condition
kpeter@2574
   544
        for (EdgeIt e(_graph); e != INVALID; ++e) {
kpeter@2574
   545
          Node u = _graph.source(e), v = _graph.target(e);
kpeter@2581
   546
          Cost c = _cost[e] + (*_potential)[u] - (*_potential)[v];
kpeter@2574
   547
          if (c < 0 && _res_cap[e] >= _delta) {
kpeter@2574
   548
            _excess[u] -= _res_cap[e];
kpeter@2574
   549
            _excess[v] += _res_cap[e];
kpeter@2581
   550
            (*_flow)[e] = _capacity[e];
kpeter@2574
   551
            _res_cap[e] = 0;
kpeter@2535
   552
          }
kpeter@2581
   553
          else if (c > 0 && (*_flow)[e] >= _delta) {
kpeter@2581
   554
            _excess[u] += (*_flow)[e];
kpeter@2581
   555
            _excess[v] -= (*_flow)[e];
kpeter@2581
   556
            (*_flow)[e] = 0;
kpeter@2574
   557
            _res_cap[e] = _capacity[e];
kpeter@2535
   558
          }
kpeter@2535
   559
        }
kpeter@2535
   560
kpeter@2535
   561
        // Finding excess nodes and deficit nodes
kpeter@2574
   562
        _excess_nodes.clear();
kpeter@2574
   563
        _deficit_nodes.clear();
kpeter@2574
   564
        for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@2574
   565
          if (_excess[n] >=  _delta) _excess_nodes.push_back(n);
kpeter@2574
   566
          if (_excess[n] <= -_delta) _deficit_nodes.push_back(n);
kpeter@2535
   567
        }
kpeter@2620
   568
        int next_node = 0, next_def_node = 0;
kpeter@2535
   569
kpeter@2535
   570
        // Finding augmenting shortest paths
kpeter@2574
   571
        while (next_node < int(_excess_nodes.size())) {
kpeter@2535
   572
          // Checking deficit nodes
kpeter@2574
   573
          if (_delta > 1) {
kpeter@2535
   574
            bool delta_deficit = false;
kpeter@2620
   575
            for ( ; next_def_node < int(_deficit_nodes.size());
kpeter@2620
   576
                    ++next_def_node ) {
kpeter@2620
   577
              if (_excess[_deficit_nodes[next_def_node]] <= -_delta) {
kpeter@2535
   578
                delta_deficit = true;
kpeter@2535
   579
                break;
kpeter@2535
   580
              }
kpeter@2535
   581
            }
kpeter@2535
   582
            if (!delta_deficit) break;
kpeter@2535
   583
          }
kpeter@2535
   584
kpeter@2535
   585
          // Running Dijkstra
kpeter@2574
   586
          s = _excess_nodes[next_node];
kpeter@2581
   587
          if ((t = _dijkstra->run(s, _delta)) == INVALID) {
kpeter@2574
   588
            if (_delta > 1) {
kpeter@2535
   589
              ++next_node;
kpeter@2535
   590
              continue;
kpeter@2535
   591
            }
kpeter@2535
   592
            return false;
kpeter@2535
   593
          }
kpeter@2535
   594
kpeter@2535
   595
          // Augmenting along a shortest path from s to t.
kpeter@2588
   596
          Capacity d = std::min(_excess[s], -_excess[t]);
kpeter@2535
   597
          Node u = t;
kpeter@2535
   598
          Edge e;
kpeter@2574
   599
          if (d > _delta) {
kpeter@2574
   600
            while ((e = _pred[u]) != INVALID) {
kpeter@2535
   601
              Capacity rc;
kpeter@2574
   602
              if (u == _graph.target(e)) {
kpeter@2574
   603
                rc = _res_cap[e];
kpeter@2574
   604
                u = _graph.source(e);
kpeter@2535
   605
              } else {
kpeter@2581
   606
                rc = (*_flow)[e];
kpeter@2574
   607
                u = _graph.target(e);
kpeter@2535
   608
              }
kpeter@2535
   609
              if (rc < d) d = rc;
kpeter@2535
   610
            }
kpeter@2535
   611
          }
kpeter@2535
   612
          u = t;
kpeter@2574
   613
          while ((e = _pred[u]) != INVALID) {
kpeter@2574
   614
            if (u == _graph.target(e)) {
kpeter@2581
   615
              (*_flow)[e] += d;
kpeter@2574
   616
              _res_cap[e] -= d;
kpeter@2574
   617
              u = _graph.source(e);
kpeter@2535
   618
            } else {
kpeter@2581
   619
              (*_flow)[e] -= d;
kpeter@2574
   620
              _res_cap[e] += d;
kpeter@2574
   621
              u = _graph.target(e);
kpeter@2535
   622
            }
kpeter@2535
   623
          }
kpeter@2574
   624
          _excess[s] -= d;
kpeter@2574
   625
          _excess[t] += d;
kpeter@2535
   626
kpeter@2574
   627
          if (_excess[s] < _delta) ++next_node;
kpeter@2535
   628
        }
kpeter@2535
   629
kpeter@2574
   630
        if (_delta == 1) break;
kpeter@2574
   631
        if (++phase_cnt > _phase_num / 4) factor = 2;
kpeter@2574
   632
        _delta = _delta <= factor ? 1 : _delta / factor;
kpeter@2535
   633
      }
kpeter@2535
   634
kpeter@2556
   635
      // Handling non-zero lower bounds
kpeter@2574
   636
      if (_lower) {
kpeter@2574
   637
        for (EdgeIt e(_graph); e != INVALID; ++e)
kpeter@2581
   638
          (*_flow)[e] += (*_lower)[e];
kpeter@2535
   639
      }
kpeter@2535
   640
      return true;
kpeter@2535
   641
    }
kpeter@2535
   642
kpeter@2620
   643
    /// Execute the successive shortest path algorithm.
kpeter@2535
   644
    bool startWithoutScaling() {
deba@2440
   645
      // Finding excess nodes
kpeter@2574
   646
      for (NodeIt n(_graph); n != INVALID; ++n)
kpeter@2574
   647
        if (_excess[n] > 0) _excess_nodes.push_back(n);
kpeter@2574
   648
      if (_excess_nodes.size() == 0) return true;
kpeter@2556
   649
      int next_node = 0;
deba@2440
   650
deba@2457
   651
      // Finding shortest paths
kpeter@2535
   652
      Node s, t;
kpeter@2574
   653
      while ( _excess[_excess_nodes[next_node]] > 0 ||
kpeter@2574
   654
              ++next_node < int(_excess_nodes.size()) )
deba@2440
   655
      {
kpeter@2535
   656
        // Running Dijkstra
kpeter@2574
   657
        s = _excess_nodes[next_node];
kpeter@2589
   658
        if ((t = _dijkstra->run(s)) == INVALID) return false;
deba@2440
   659
kpeter@2535
   660
        // Augmenting along a shortest path from s to t
kpeter@2588
   661
        Capacity d = std::min(_excess[s], -_excess[t]);
kpeter@2535
   662
        Node u = t;
kpeter@2535
   663
        Edge e;
kpeter@2588
   664
        if (d > 1) {
kpeter@2588
   665
          while ((e = _pred[u]) != INVALID) {
kpeter@2588
   666
            Capacity rc;
kpeter@2588
   667
            if (u == _graph.target(e)) {
kpeter@2588
   668
              rc = _res_cap[e];
kpeter@2588
   669
              u = _graph.source(e);
kpeter@2588
   670
            } else {
kpeter@2588
   671
              rc = (*_flow)[e];
kpeter@2588
   672
              u = _graph.target(e);
kpeter@2588
   673
            }
kpeter@2588
   674
            if (rc < d) d = rc;
kpeter@2535
   675
          }
kpeter@2535
   676
        }
kpeter@2535
   677
        u = t;
kpeter@2574
   678
        while ((e = _pred[u]) != INVALID) {
kpeter@2574
   679
          if (u == _graph.target(e)) {
kpeter@2581
   680
            (*_flow)[e] += d;
kpeter@2574
   681
            _res_cap[e] -= d;
kpeter@2574
   682
            u = _graph.source(e);
kpeter@2535
   683
          } else {
kpeter@2581
   684
            (*_flow)[e] -= d;
kpeter@2574
   685
            _res_cap[e] += d;
kpeter@2574
   686
            u = _graph.target(e);
kpeter@2535
   687
          }
kpeter@2535
   688
        }
kpeter@2574
   689
        _excess[s] -= d;
kpeter@2574
   690
        _excess[t] += d;
deba@2440
   691
      }
deba@2440
   692
kpeter@2556
   693
      // Handling non-zero lower bounds
kpeter@2574
   694
      if (_lower) {
kpeter@2574
   695
        for (EdgeIt e(_graph); e != INVALID; ++e)
kpeter@2581
   696
          (*_flow)[e] += (*_lower)[e];
deba@2440
   697
      }
deba@2440
   698
      return true;
deba@2440
   699
    }
deba@2440
   700
deba@2440
   701
  }; //class CapacityScaling
deba@2440
   702
deba@2440
   703
  ///@}
deba@2440
   704
deba@2440
   705
} //namespace lemon
deba@2440
   706
deba@2440
   707
#endif //LEMON_CAPACITY_SCALING_H