COIN-OR::LEMON - Graph Library

Changeset 2556:74c2c81055e1 in lemon-0.x


Ignore:
Timestamp:
01/13/08 11:32:14 (11 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.

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r2553 r2556  
    2323///
    2424/// \file
    25 /// \brief The capacity scaling algorithm for finding a minimum cost
    26 /// flow.
     25/// \brief The capacity scaling algorithm for finding a minimum cost flow.
    2726
    2827#include <lemon/graph_adaptor.h>
     
    5049  ///
    5150  /// \warning
    52   /// - Edge capacities and costs should be nonnegative integers.
     51  /// - Edge capacities and costs should be non-negative integers.
    5352  ///   However \c CostMap::Value should be signed type.
    5453  /// - Supply values should be signed integers.
     
    6766  class CapacityScaling
    6867  {
    69     typedef typename Graph::Node Node;
    70     typedef typename Graph::NodeIt NodeIt;
    71     typedef typename Graph::Edge Edge;
    72     typedef typename Graph::EdgeIt EdgeIt;
    73     typedef typename Graph::InEdgeIt InEdgeIt;
    74     typedef typename Graph::OutEdgeIt OutEdgeIt;
     68    GRAPH_TYPEDEFS(typename Graph);
    7569
    7670    typedef typename LowerMap::Value Lower;
     
    7872    typedef typename CostMap::Value Cost;
    7973    typedef typename SupplyMap::Value Supply;
    80     typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
    81     typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
     74    typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
     75    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
    8276    typedef typename Graph::template NodeMap<Edge> PredMap;
    8377
    8478  public:
    8579
    86     /// \brief Type to enable or disable capacity scaling.
     80    /// Type to enable or disable capacity scaling.
    8781    enum ScalingEnum {
    8882      WITH_SCALING = 0,
     
    9084    };
    9185
    92     /// \brief The type of the flow map.
    93     typedef CapacityRefMap FlowMap;
    94     /// \brief The type of the potential map.
     86    /// The type of the flow map.
     87    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
     88    /// The type of the potential map.
    9589    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    9690
     
    111105    protected:
    112106
    113       /// \brief The directed graph the algorithm runs on.
     107      /// The directed graph the algorithm runs on.
    114108      const Graph &graph;
    115109
    116       /// \brief The flow map.
     110      /// The flow map.
    117111      const FlowMap &flow;
    118       /// \brief The residual capacity map.
    119       const CapacityRefMap &res_cap;
    120       /// \brief The cost map.
     112      /// The residual capacity map.
     113      const CapacityEdgeMap &res_cap;
     114      /// The cost map.
    121115      const CostMap &cost;
    122       /// \brief The excess map.
    123       const SupplyRefMap &excess;
    124 
    125       /// \brief The potential map.
     116      /// The excess map.
     117      const SupplyNodeMap &excess;
     118
     119      /// The potential map.
    126120      PotentialMap &potential;
    127121
    128       /// \brief The distance map.
     122      /// The distance map.
    129123      CostNodeMap dist;
    130       /// \brief The map of predecessors edges.
     124      /// The map of predecessors edges.
    131125      PredMap &pred;
    132       /// \brief The processed (i.e. permanently labeled) nodes.
     126      /// The processed (i.e. permanently labeled) nodes.
    133127      std::vector<Node> proc_nodes;
    134128
    135129    public:
    136130
    137       /// \brief The constructor of the class.
     131      /// The constructor of the class.
    138132      ResidualDijkstra( const Graph &_graph,
    139133                        const FlowMap &_flow,
    140                         const CapacityRefMap &_res_cap,
     134                        const CapacityEdgeMap &_res_cap,
    141135                        const CostMap &_cost,
    142136                        const SupplyMap &_excess,
     
    148142      {}
    149143
    150       /// \brief Runs the algorithm from the given source node.
     144      /// Runs the algorithm from the given source node.
    151145      Node run(Node s, Capacity delta) {
    152146        HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);
     
    223217  protected:
    224218
    225     /// \brief The directed graph the algorithm runs on.
     219    /// The directed graph the algorithm runs on.
    226220    const Graph &graph;
    227     /// \brief The original lower bound map.
     221    /// The original lower bound map.
    228222    const LowerMap *lower;
    229     /// \brief The modified capacity map.
    230     CapacityRefMap capacity;
    231     /// \brief The cost map.
     223    /// The modified capacity map.
     224    CapacityEdgeMap capacity;
     225    /// The cost map.
    232226    const CostMap &cost;
    233     /// \brief The modified supply map.
    234     SupplyRefMap supply;
    235     /// \brief The sum of supply values equals zero.
     227    /// The modified supply map.
     228    SupplyNodeMap supply;
    236229    bool valid_supply;
    237230
    238     /// \brief The edge map of the current flow.
     231    /// The edge map of the current flow.
    239232    FlowMap flow;
    240     /// \brief The potential node map.
     233    /// The potential node map.
    241234    PotentialMap potential;
    242235
    243     /// \brief The residual capacity map.
    244     CapacityRefMap res_cap;
    245     /// \brief The excess map.
    246     SupplyRefMap excess;
    247     /// \brief The excess nodes (i.e. nodes with positive excess).
     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).
    248241    std::vector<Node> excess_nodes;
    249     /// \brief The index of the next excess node.
    250     int next_node;
    251 
    252     /// \brief The scaling status (enabled or disabled).
     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).
    253246    ScalingEnum scaling;
    254     /// \brief The delta parameter used for capacity scaling.
     247    /// The \c delta parameter used for capacity scaling.
    255248    Capacity delta;
    256     /// \brief The maximum number of phases.
    257     Capacity phase_num;
    258     /// \brief The deficit nodes.
    259     std::vector<Node> deficit_nodes;
     249    /// The maximum number of phases.
     250    int phase_num;
    260251
    261252    /// \brief Implementation of the \ref Dijkstra algorithm for
    262253    /// finding augmenting shortest paths in the residual network.
    263254    ResidualDijkstra dijkstra;
    264     /// \brief The map of predecessors edges.
     255    /// The map of predecessors edges.
    265256    PredMap pred;
    266257
     
    286277      dijkstra(graph, flow, res_cap, cost, excess, potential, pred)
    287278    {
    288       // Removing nonzero lower bounds
     279      // Removing non-zero lower bounds
    289280      capacity = subMap(_capacity, _lower);
    290281      res_cap = capacity;
     
    336327    /// \param _t The target node.
    337328    /// \param _flow_value The required amount of flow from node \c _s
    338     /// to node \c _t (i.e. the supply of \c _s and the demand of
    339     /// \c _t).
     329    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    340330    CapacityScaling( const Graph &_graph,
    341331                     const LowerMap &_lower,
     
    349339      dijkstra(graph, flow, res_cap, cost, excess, potential)
    350340    {
    351       // Removing nonzero lower bounds
     341      // Removing non-zero lower bounds
    352342      capacity = subMap(_capacity, _lower);
    353343      res_cap = capacity;
     
    375365    /// \param _t The target node.
    376366    /// \param _flow_value The required amount of flow from node \c _s
    377     /// to node \c _t (i.e. the supply of \c _s and the demand of
    378     /// \c _t).
     367    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    379368    CapacityScaling( const Graph &_graph,
    380369                     const CapacityMap &_capacity,
     
    392381    }
    393382
     383    /// \brief Runs the algorithm.
     384    ///
     385    /// Runs the algorithm.
     386    ///
     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.
     390    /// If the maximum edge capacity and/or the amount of total supply
     391    /// is small, the algorithm could be slightly faster without
     392    /// scaling.
     393    ///
     394    /// \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
    394399    /// \brief Returns a const reference to the flow map.
    395400    ///
     
    425430    }
    426431
    427     /// \brief Runs the algorithm.
    428     ///
    429     /// Runs the algorithm.
    430     ///
    431     /// \param scaling_mode The scaling mode. In case of WITH_SCALING
    432     /// capacity scaling is enabled in the algorithm (this is the
    433     /// default value) otherwise it is disabled.
    434     /// If the maximum edge capacity and/or the amount of total supply
    435     /// is small, the algorithm could be faster without scaling.
    436     ///
    437     /// \return \c true if a feasible flow can be found.
    438     bool run(int scaling_mode = WITH_SCALING) {
    439       return init(scaling_mode) && start();
    440     }
    441 
    442432  protected:
    443433
    444     /// \brief Initializes the algorithm.
     434    /// Initializes the algorithm.
    445435    bool init(int scaling_mode) {
    446436      if (!valid_supply) return false;
     
    466456    }
    467457
    468     /// \brief Executes the algorithm.
     458    /// Executes the algorithm.
    469459    bool start() {
    470460      if (delta > 1)
     
    507497          if (excess[n] <= -delta) deficit_nodes.push_back(n);
    508498        }
    509         next_node = 0;
     499        int next_node = 0;
    510500
    511501        // Finding augmenting shortest paths
     
    573563      }
    574564
    575       // Handling nonzero lower bounds
     565      // Handling non-zero lower bounds
    576566      if (lower) {
    577567        for (EdgeIt e(graph); e != INVALID; ++e)
     
    585575    bool startWithoutScaling() {
    586576      // Finding excess nodes
    587       for (NodeIt n(graph); n != INVALID; ++n) {
     577      for (NodeIt n(graph); n != INVALID; ++n)
    588578        if (excess[n] > 0) excess_nodes.push_back(n);
    589       }
    590579      if (excess_nodes.size() == 0) return true;
    591       next_node = 0;
     580      int next_node = 0;
    592581
    593582      // Finding shortest paths
     
    632621      }
    633622
    634       // Handling nonzero lower bounds
     623      // Handling non-zero lower bounds
    635624      if (lower) {
    636625        for (EdgeIt e(graph); e != INVALID; ++e)
  • 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;
  • lemon/min_cost_flow.h

    r2553 r2556  
    3434  /// \brief An efficient algorithm for finding a minimum cost flow.
    3535  ///
    36   /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
    37   /// algorithm for finding a minimum cost flow.
     36  /// \ref MinCostFlow provides an efficient algorithm for finding
     37  /// a minimum cost flow.
    3838  ///
    39   /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
    40   /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
    41   /// efficient implementation for the minimum cost flow problem in the
    42   /// LEMON library according to our benchmark tests.
     39  /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
     40  /// which is the most efficient implementation for the minimum cost
     41  /// flow problem in the LEMON library according to our benchmark
     42  /// tests.
    4343  ///
    4444  /// \note There are three implementations for the minimum cost flow
    45   /// problem, that can be used in the same way.
    46   /// - \ref lemon::CapacityScaling "CapacityScaling"
    47   /// - \ref lemon::CycleCanceling "CycleCanceling"
    48   /// - \ref lemon::NetworkSimplex "NetworkSimplex"
     45  /// problem, that can be used exactly the same way.
     46  /// - \ref CapacityScaling
     47  /// - \ref CycleCanceling
     48  /// - \ref NetworkSimplex
     49  ///
     50  /// \note For the detailed documentation of this class see
     51  /// \ref NetworkSimplex.
    4952  ///
    5053  /// \param Graph The directed graph type the algorithm runs on.
     
    5558  ///
    5659  /// \warning
    57   /// - Edge capacities and costs should be nonnegative integers.
    58   ///   However \c CostMap::Value should be signed type.
     60  /// - Edge capacities and costs should be non-negative integers.
     61  ///   However \c CostMap::Value should be signed type.
    5962  /// - Supply values should be signed integers.
    6063  /// - \c LowerMap::Value must be convertible to
    61   ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    62   ///   convertible to \c SupplyMap::Value.
     64  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
     65  ///   convertible to \c SupplyMap::Value.
    6366  ///
    6467  /// \author Peter Kovacs
     
    7174                                  <typename CapacityMap::Value> >
    7275  class MinCostFlow :
    73     public NetworkSimplex< Graph,
    74                            LowerMap,
    75                            CapacityMap,
    76                            CostMap,
    77                            SupplyMap >
     76    public NetworkSimplex< Graph, LowerMap, CapacityMap,
     77                           CostMap, SupplyMap >
    7878  {
    7979    typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
    80                             CostMap, SupplyMap >
    81       MinCostFlowImpl;
     80                            CostMap, SupplyMap > MinCostFlowImpl;
    8281    typedef typename Graph::Node Node;
    8382    typedef typename SupplyMap::Value Supply;
     
    8584  public:
    8685
    87     /// \brief General constructor of the class (with lower bounds).
    88     MinCostFlow( const Graph &_graph,
    89                  const LowerMap &_lower,
    90                  const CapacityMap &_capacity,
    91                  const CostMap &_cost,
    92                  const SupplyMap &_supply ) :
    93       MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
     86    /// General constructor of the class (with lower bounds).
     87    MinCostFlow( const Graph &graph,
     88                 const LowerMap &lower,
     89                 const CapacityMap &capacity,
     90                 const CostMap &cost,
     91                 const SupplyMap &supply ) :
     92      MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
    9493
    95     /// \brief General constructor of the class (without lower bounds).
    96     MinCostFlow( const Graph &_graph,
    97                  const CapacityMap &_capacity,
    98                  const CostMap &_cost,
    99                  const SupplyMap &_supply ) :
    100       MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
     94    /// General constructor of the class (without lower bounds).
     95    MinCostFlow( const Graph &graph,
     96                 const CapacityMap &capacity,
     97                 const CostMap &_ost,
     98                 const SupplyMap &supply ) :
     99      MinCostFlowImpl(graph, capacity, cost, supply) {}
    101100
    102     /// \brief Simple constructor of the class (with lower bounds).
    103     MinCostFlow( const Graph &_graph,
    104                  const LowerMap &_lower,
    105                  const CapacityMap &_capacity,
    106                  const CostMap &_cost,
    107                  Node _s, Node _t,
    108                  Supply _flow_value ) :
    109       MinCostFlowImpl( _graph, _lower, _capacity, _cost,
    110                        _s, _t, _flow_value ) {}
     101    /// Simple constructor of the class (with lower bounds).
     102    MinCostFlow( const Graph &graph,
     103                 const LowerMap &lower,
     104                 const CapacityMap &capacity,
     105                 const CostMap &_ost,
     106                 Node s, Node t,
     107                 Supply flow_value ) :
     108      MinCostFlowImpl( graph, lower, capacity, cost,
     109                       s, t, flow_value ) {}
    111110
    112     /// \brief Simple constructor of the class (without lower bounds).
    113     MinCostFlow( const Graph &_graph,
    114                  const CapacityMap &_capacity,
    115                  const CostMap &_cost,
    116                  Node _s, Node _t,
    117                  Supply _flow_value ) :
    118       MinCostFlowImpl( _graph, _capacity, _cost,
    119                        _s, _t, _flow_value ) {}
     111    /// Simple constructor of the class (without lower bounds).
     112    MinCostFlow( const Graph &graph,
     113                 const CapacityMap &capacity,
     114                 const CostMap &cost,
     115                 Node s, Node t,
     116                 Supply flow_value ) :
     117      MinCostFlowImpl( graph, capacity, cost,
     118                       s, t, flow_value ) {}
    120119
    121120  }; //class MinCostFlow
  • lemon/min_cost_max_flow.h

    r2553 r2556  
    2323///
    2424/// \file
    25 /// \brief An efficient algorithm for finding a minimum cost maximum
    26 /// flow.
     25/// \brief An efficient algorithm for finding a minimum cost maximum flow.
    2726
    2827#include <lemon/preflow.h>
     
    3534  /// @{
    3635
    37   /// \brief An efficient algorithm for finding a minimum cost maximum
    38   /// flow.
     36  /// \brief An efficient algorithm for finding a minimum cost
     37  /// maximum flow.
    3938  ///
    40   /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient
    41   /// algorithm for finding a maximum flow having minimal total cost
    42   /// from a given source node to a given target node in a directed
    43   /// graph.
     39  /// \ref MinCostMaxFlow implements an efficient algorithm for
     40  /// finding a maximum flow having minimal total cost from a given
     41  /// source node to a given target node in a directed graph.
    4442  ///
    45   /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses
    46   /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum
    47   /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex"
    48   /// algorithm for finding a minimum cost flow of that value.
     43  /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
     44  /// the maximum flow value and \ref NetworkSimplex algorithm for
     45  /// finding a minimum cost flow of that value.
    4946  ///
    5047  /// \param Graph The directed graph type the algorithm runs on.
     
    5350  ///
    5451  /// \warning
    55   /// - Edge capacities and costs should be nonnegative integers.
    56   ///   However \c CostMap::Value should be signed type.
     52  /// - Edge capacities and costs should be non-negative integers.
     53  ///   However \c CostMap::Value should be signed type.
    5754  ///
    5855  /// \author Peter Kovacs
    5956
    6057  template < typename Graph,
    61              typename CapacityMap = typename Graph::template EdgeMap<int>,
    62              typename CostMap = typename Graph::template EdgeMap<int> >
     58             typename CapacityMap = typename Graph::template EdgeMap<int>,
     59             typename CostMap = typename Graph::template EdgeMap<int> >
    6360  class MinCostMaxFlow
    6461  {
     
    6764
    6865    typedef typename CapacityMap::Value Capacity;
     66    typedef typename CostMap::Value Cost;
    6967    typedef typename Graph::template NodeMap<Capacity> SupplyMap;
    7068    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
    71                             CostMap, SupplyMap >
     69                            CostMap, SupplyMap >
    7270      MinCostFlowImpl;
    7371
    7472  public:
    7573
    76     /// \brief The type of the flow map.
     74    /// The type of the flow map.
    7775    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    78     typedef typename CostMap::Value Cost;
    7976
    8077  private:
    8178
    82     /// \brief The directed graph the algorithm runs on.
     79    /// The directed graph the algorithm runs on.
    8380    const Graph &graph;
    84     /// \brief The modified capacity map.
     81    /// The modified capacity map.
    8582    const CapacityMap &capacity;
    86     /// \brief The cost map.
     83    /// The cost map.
    8784    const CostMap &cost;
    88     /// \brief The source node.
     85    /// The edge map of the found flow.
     86    FlowMap flow;
     87    /// The source node.
    8988    Node source;
    90     /// \brief The target node.
     89    /// The target node.
    9190    Node target;
    92     /// \brief The edge map of the found flow.
    93     FlowMap flow;
    9491
    95     typedef Preflow<Graph, CapacityMap> PreflowImpl;
    96     /// \brief \ref lemon::Preflow "Preflow" class for finding the
    97     /// maximum flow value.
    98     PreflowImpl preflow;
     92    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
     93    /// \brief \ref Preflow class for finding the maximum flow value.
     94    MaxFlowImpl preflow;
    9995
    10096  public:
     
    110106    /// \param _t The target node.
    111107    MinCostMaxFlow( const Graph &_graph,
    112                     const CapacityMap &_capacity,
    113                     const CostMap &_cost,
    114                     Node _s, Node _t ) :
     108                    const CapacityMap &_capacity,
     109                    const CostMap &_cost,
     110                    Node _s, Node _t ) :
    115111      graph(_graph), capacity(_capacity), cost(_cost),
    116112      source(_s), target(_t), flow(_graph),
     
    136132      Cost c = 0;
    137133      for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
    138         c += flow[e] * cost[e];
     134        c += flow[e] * cost[e];
    139135      return c;
    140136    }
     
    145141      preflow.runMinCut();
    146142      MinCostFlowImpl mcf_impl( graph, capacity, cost,
    147                                 source, target, preflow.flowValue() );
     143                                source, target, preflow.flowValue() );
    148144      mcf_impl.run();
    149145      flow = mcf_impl.flowMap();
  • lemon/network_simplex.h

    r2553 r2556  
    2323///
    2424/// \file
    25 /// \brief The network simplex algorithm for finding a minimum cost
    26 /// flow.
     25/// \brief The network simplex algorithm for finding a minimum cost flow.
    2726
    2827#include <limits>
     
    4140
    4241
    43 /// \brief State constant for edges at their lower bounds.
    44 #define LOWER   1
    45 /// \brief State constant for edges in the spanning tree.
    46 #define TREE    0
    47 /// \brief State constant for edges at their upper bounds.
    48 #define UPPER   -1
     42// State constant for edges at their lower bounds.
     43#define LOWER   1
     44// State constant for edges in the spanning tree.
     45#define TREE    0
     46// State constant for edges at their upper bounds.
     47#define UPPER   -1
    4948
    5049#ifdef EDGE_BLOCK_PIVOT
    5150  #include <cmath>
    52   /// \brief Lower bound for the size of blocks.
    53   #define MIN_BLOCK_SIZE        10
     51  #define MIN_BLOCK_SIZE        10
    5452#endif
    5553
    5654#ifdef CANDIDATE_LIST_PIVOT
    5755  #include <vector>
    58   #define LIST_LENGTH_DIV           50
    59   #define MINOR_LIMIT_DIV           200
     56  #define LIST_LENGTH_DIV       50
     57  #define MINOR_LIMIT_DIV       200
    6058#endif
    6159
     
    6462  #include <algorithm>
    6563  #define LIST_LENGTH_DIV       100
    66   #define LOWER_DIV             4
     64  #define LOWER_DIV             4
    6765#endif
    6866
     
    7573  /// finding a minimum cost flow.
    7674  ///
    77   /// \ref lemon::NetworkSimplex "NetworkSimplex" implements the
    78   /// network simplex algorithm for finding a minimum cost flow.
     75  /// \ref NetworkSimplex implements the network simplex algorithm for
     76  /// finding a minimum cost flow.
    7977  ///
    8078  /// \param Graph The directed graph type the algorithm runs on.
     
    8583  ///
    8684  /// \warning
    87   /// - Edge capacities and costs should be nonnegative integers.
    88   ///   However \c CostMap::Value should be signed type.
     85  /// - Edge capacities and costs should be non-negative integers.
     86  ///   However \c CostMap::Value should be signed type.
    8987  /// - Supply values should be signed integers.
    9088  /// - \c LowerMap::Value must be convertible to
    91   ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    92   ///   convertible to \c SupplyMap::Value.
     89  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
     90  ///   convertible to \c SupplyMap::Value.
    9391  ///
    9492  /// \author Peter Kovacs
     
    108106
    109107    typedef SmartGraph SGraph;
    110     typedef typename SGraph::Node Node;
    111     typedef typename SGraph::NodeIt NodeIt;
    112     typedef typename SGraph::Edge Edge;
    113     typedef typename SGraph::EdgeIt EdgeIt;
    114     typedef typename SGraph::InEdgeIt InEdgeIt;
    115     typedef typename SGraph::OutEdgeIt OutEdgeIt;
     108    GRAPH_TYPEDEFS(typename SGraph);
    116109
    117110    typedef typename SGraph::template EdgeMap<Lower> SLowerMap;
     
    132125  public:
    133126
    134     /// \brief The type of the flow map.
     127    /// The type of the flow map.
    135128    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    136     /// \brief The type of the potential map.
     129    /// The type of the potential map.
    137130    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    138131
    139132  protected:
    140133
    141     /// \brief Map adaptor class for handling reduced edge costs.
     134    /// Map adaptor class for handling reduced edge costs.
    142135    class ReducedCostMap : public MapBase<Edge, Cost>
    143136    {
     
    151144
    152145      ReducedCostMap( const SGraph &_gr,
    153                       const SCostMap &_cm,
    154                       const SPotentialMap &_pm ) :
    155         gr(_gr), cost_map(_cm), pot_map(_pm) {}
     146                      const SCostMap &_cm,
     147                      const SPotentialMap &_pm ) :
     148        gr(_gr), cost_map(_cm), pot_map(_pm) {}
    156149
    157150      Cost operator[](const Edge &e) const {
    158         return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
     151        return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
    159152      }
    160153
     
    163156  protected:
    164157
    165     /// \brief The directed graph the algorithm runs on.
     158    /// The directed graph the algorithm runs on.
    166159    SGraph graph;
    167     /// \brief The original graph.
     160    /// The original graph.
    168161    const Graph &graph_ref;
    169     /// \brief The original lower bound map.
     162    /// The original lower bound map.
    170163    const LowerMap *lower;
    171     /// \brief The capacity map.
     164    /// The capacity map.
    172165    SCapacityMap capacity;
    173     /// \brief The cost map.
     166    /// The cost map.
    174167    SCostMap cost;
    175     /// \brief The supply map.
     168    /// The supply map.
    176169    SSupplyMap supply;
    177     /// \brief The reduced cost map.
     170    /// The reduced cost map.
    178171    ReducedCostMap red_cost;
    179     /// \brief The sum of supply values equals zero.
    180172    bool valid_supply;
    181173
    182     /// \brief The edge map of the current flow.
     174    /// The edge map of the current flow.
    183175    SCapacityMap flow;
    184     /// \brief The edge map of the found flow on the original graph.
     176    /// The potential node map.
     177    SPotentialMap potential;
    185178    FlowMap flow_result;
    186     /// \brief The potential node map.
    187     SPotentialMap potential;
    188     /// \brief The potential node map on the original graph.
    189179    PotentialMap potential_result;
    190180
    191     /// \brief Node reference for the original graph.
     181    /// Node reference for the original graph.
    192182    NodeRefMap node_ref;
    193     /// \brief Edge reference for the original graph.
     183    /// Edge reference for the original graph.
    194184    EdgeRefMap edge_ref;
    195185
    196     /// \brief The depth node map of the spanning tree structure.
     186    /// The \c depth node map of the spanning tree structure.
    197187    IntNodeMap depth;
    198     /// \brief The parent node map of the spanning tree structure.
     188    /// The \c parent node map of the spanning tree structure.
    199189    NodeNodeMap parent;
    200     /// \brief The pred_edge node map of the spanning tree structure.
     190    /// The \c pred_edge node map of the spanning tree structure.
    201191    EdgeNodeMap pred_edge;
    202     /// \brief The thread node map of the spanning tree structure.
     192    /// The \c thread node map of the spanning tree structure.
    203193    NodeNodeMap thread;
    204     /// \brief The forward node map of the spanning tree structure.
     194    /// The \c forward node map of the spanning tree structure.
    205195    BoolNodeMap forward;
    206     /// \brief The state edge map.
     196    /// The state edge map.
    207197    IntEdgeMap state;
    208 
     198    /// The root node of the starting spanning tree.
     199    Node root;
     200
     201    // The entering edge of the current pivot iteration.
     202    Edge in_edge;
     203    // Temporary nodes used in the current pivot iteration.
     204    Node join, u_in, v_in, u_out, v_out;
     205    Node right, first, second, last;
     206    Node stem, par_stem, new_stem;
     207    // The maximum augment amount along the found cycle in the current
     208    // pivot iteration.
     209    Capacity delta;
    209210
    210211#ifdef EDGE_BLOCK_PIVOT
    211     /// \brief The size of blocks for the "Edge Block" pivot rule.
     212    /// The size of blocks for the "Edge Block" pivot rule.
    212213    int block_size;
    213214#endif
     
    235236#endif
    236237
    237     // Root node of the starting spanning tree.
    238     Node root;
    239     // The entering edge of the current pivot iteration.
    240     Edge in_edge;
    241     // Temporary nodes used in the current pivot iteration.
    242     Node join, u_in, v_in, u_out, v_out;
    243     Node right, first, second, last;
    244     Node stem, par_stem, new_stem;
    245     // The maximum augment amount along the cycle in the current pivot
    246     // iteration.
    247     Capacity delta;
    248 
    249238  public :
    250239
     
    259248    /// \param _supply The supply values of the nodes (signed).
    260249    NetworkSimplex( const Graph &_graph,
    261                     const LowerMap &_lower,
    262                     const CapacityMap &_capacity,
    263                     const CostMap &_cost,
    264                     const SupplyMap &_supply ) :
     250                    const LowerMap &_lower,
     251                    const CapacityMap &_capacity,
     252                    const CostMap &_cost,
     253                    const SupplyMap &_supply ) :
    265254      graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
    266255      supply(graph), flow(graph), flow_result(_graph), potential(graph),
     
    273262      Supply sum = 0;
    274263      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
    275         sum += _supply[n];
     264        sum += _supply[n];
    276265      if (!(valid_supply = sum == 0)) return;
    277266
     
    280269      graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
    281270      copyGraph(graph, graph_ref)
    282         .edgeMap(cost, _cost)
    283         .nodeRef(node_ref)
    284         .edgeRef(edge_ref)
    285         .run();
    286 
    287       // Removing nonzero lower bounds
     271        .edgeMap(cost, _cost)
     272        .nodeRef(node_ref)
     273        .edgeRef(edge_ref)
     274        .run();
     275
     276      // Removing non-zero lower bounds
    288277      for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
    289         capacity[edge_ref[e]] = _capacity[e] - _lower[e];
     278        capacity[edge_ref[e]] = _capacity[e] - _lower[e];
    290279      }
    291280      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
    292         Supply s = _supply[n];
    293         for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
    294           s += _lower[e];
    295         for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
    296           s -= _lower[e];
    297         supply[node_ref[n]] = s;
     281        Supply s = _supply[n];
     282        for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
     283          s += _lower[e];
     284        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
     285          s -= _lower[e];
     286        supply[node_ref[n]] = s;
    298287      }
    299288    }
     
    308297    /// \param _supply The supply values of the nodes (signed).
    309298    NetworkSimplex( const Graph &_graph,
    310                     const CapacityMap &_capacity,
    311                     const CostMap &_cost,
    312                     const SupplyMap &_supply ) :
     299                    const CapacityMap &_capacity,
     300                    const CostMap &_cost,
     301                    const SupplyMap &_supply ) :
    313302      graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
    314303      supply(graph), flow(graph), flow_result(_graph), potential(graph),
     
    321310      Supply sum = 0;
    322311      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
    323         sum += _supply[n];
     312        sum += _supply[n];
    324313      if (!(valid_supply = sum == 0)) return;
    325314
    326315      // Copying graph_ref to graph
    327316      copyGraph(graph, graph_ref)
    328         .edgeMap(capacity, _capacity)
    329         .edgeMap(cost, _cost)
    330         .nodeMap(supply, _supply)
    331         .nodeRef(node_ref)
    332         .edgeRef(edge_ref)
    333         .run();
     317        .edgeMap(capacity, _capacity)
     318        .edgeMap(cost, _cost)
     319        .nodeMap(supply, _supply)
     320        .nodeRef(node_ref)
     321        .edgeRef(edge_ref)
     322        .run();
    334323    }
    335324
     
    345334    /// \param _t The target node.
    346335    /// \param _flow_value The required amount of flow from node \c _s
    347     /// to node \c _t (i.e. the supply of \c _s and the demand of
    348     /// \c _t).
     336    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    349337    NetworkSimplex( const Graph &_graph,
    350                     const LowerMap &_lower,
    351                     const CapacityMap &_capacity,
    352                     const CostMap &_cost,
    353                     typename Graph::Node _s,
    354                     typename Graph::Node _t,
    355                     typename SupplyMap::Value _flow_value ) :
     338                    const LowerMap &_lower,
     339                    const CapacityMap &_capacity,
     340                    const CostMap &_cost,
     341                    typename Graph::Node _s,
     342                    typename Graph::Node _t,
     343                    typename SupplyMap::Value _flow_value ) :
    356344      graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
    357345      supply(graph), flow(graph), flow_result(_graph), potential(graph),
     
    363351      // Copying graph_ref to graph
    364352      copyGraph(graph, graph_ref)
    365         .edgeMap(cost, _cost)
    366         .nodeRef(node_ref)
    367         .edgeRef(edge_ref)
    368         .run();
    369 
    370       // Removing nonzero lower bounds
     353        .edgeMap(cost, _cost)
     354        .nodeRef(node_ref)
     355        .edgeRef(edge_ref)
     356        .run();
     357
     358      // Removing non-zero lower bounds
    371359      for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
    372         capacity[edge_ref[e]] = _capacity[e] - _lower[e];
     360        capacity[edge_ref[e]] = _capacity[e] - _lower[e];
    373361      }
    374362      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
    375         Supply s = 0;
    376         if (n == _s) s =  _flow_value;
    377         if (n == _t) s = -_flow_value;
    378         for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
    379           s += _lower[e];
    380         for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
    381           s -= _lower[e];
    382         supply[node_ref[n]] = s;
     363        Supply s = 0;
     364        if (n == _s) s =  _flow_value;
     365        if (n == _t) s = -_flow_value;
     366        for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
     367          s += _lower[e];
     368        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
     369          s -= _lower[e];
     370        supply[node_ref[n]] = s;
    383371      }
    384372      valid_supply = true;
     
    395383    /// \param _t The target node.
    396384    /// \param _flow_value The required amount of flow from node \c _s
    397     /// to node \c _t (i.e. the supply of \c _s and the demand of
    398     /// \c _t).
     385    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    399386    NetworkSimplex( const Graph &_graph,
    400                     const CapacityMap &_capacity,
    401                     const CostMap &_cost,
    402                     typename Graph::Node _s,
    403                     typename Graph::Node _t,
    404                     typename SupplyMap::Value _flow_value ) :
     387                    const CapacityMap &_capacity,
     388                    const CostMap &_cost,
     389                    typename Graph::Node _s,
     390                    typename Graph::Node _t,
     391                    typename SupplyMap::Value _flow_value ) :
    405392      graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
    406393      supply(graph, 0), flow(graph), flow_result(_graph), potential(graph),
     
    412399      // Copying graph_ref to graph
    413400      copyGraph(graph, graph_ref)
    414         .edgeMap(capacity, _capacity)
    415         .edgeMap(cost, _cost)
    416         .nodeRef(node_ref)
    417         .edgeRef(edge_ref)
    418         .run();
     401        .edgeMap(capacity, _capacity)
     402        .edgeMap(cost, _cost)
     403        .nodeRef(node_ref)
     404        .edgeRef(edge_ref)
     405        .run();
    419406      supply[node_ref[_s]] =  _flow_value;
    420407      supply[node_ref[_t]] = -_flow_value;
    421408      valid_supply = true;
     409    }
     410
     411    /// \brief Runs the algorithm.
     412    ///
     413    /// Runs the algorithm.
     414    ///
     415    /// \return \c true if a feasible flow can be found.
     416    bool run() {
     417      return init() && start();
    422418    }
    423419
     
    451447      Cost c = 0;
    452448      for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
    453         c += flow_result[e] * cost[edge_ref[e]];
     449        c += flow_result[e] * cost[edge_ref[e]];
    454450      return c;
    455     }
    456 
    457     /// \brief Runs the algorithm.
    458     ///
    459     /// Runs the algorithm.
    460     ///
    461     /// \return \c true if a feasible flow can be found.
    462     bool run() {
    463       return init() && start();
    464451    }
    465452
     
    473460      // Initializing state and flow maps
    474461      for (EdgeIt e(graph); e != INVALID; ++e) {
    475         flow[e] = 0;
    476         state[e] = LOWER;
     462        flow[e] = 0;
     463        state[e] = LOWER;
    477464      }
    478465
     
    492479      Cost max_cost = std::numeric_limits<Cost>::max() / 4;
    493480      for (NodeIt u(graph); u != INVALID; ++u) {
    494         if (u == root) continue;
    495         thread[last] = u;
    496         last = u;
    497         parent[u] = root;
    498         depth[u] = 1;
    499         sum += supply[u];
    500         if (supply[u] >= 0) {
    501           e = graph.addEdge(u, root);
    502           flow[e] = supply[u];
    503           forward[u] = true;
    504           potential[u] = max_cost;
    505         } else {
    506           e = graph.addEdge(root, u);
    507           flow[e] = -supply[u];
    508           forward[u] = false;
    509           potential[u] = -max_cost;
    510         }
    511         cost[e] = max_cost;
    512         capacity[e] = std::numeric_limits<Capacity>::max();
    513         state[e] = TREE;
    514         pred_edge[u] = e;
     481        if (u == root) continue;
     482        thread[last] = u;
     483        last = u;
     484        parent[u] = root;
     485        depth[u] = 1;
     486        sum += supply[u];
     487        if (supply[u] >= 0) {
     488          e = graph.addEdge(u, root);
     489          flow[e] = supply[u];
     490          forward[u] = true;
     491          potential[u] = max_cost;
     492        } else {
     493          e = graph.addEdge(root, u);
     494          flow[e] = -supply[u];
     495          forward[u] = false;
     496          potential[u] = -max_cost;
     497        }
     498        cost[e] = max_cost;
     499        capacity[e] = std::numeric_limits<Capacity>::max();
     500        state[e] = TREE;
     501        pred_edge[u] = e;
    515502      }
    516503      thread[last] = root;
     
    521508      block_size = 2 * int(sqrt(countEdges(graph)));
    522509      if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
    523 //      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
    524 //                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
    525510#endif
    526511#ifdef CANDIDATE_LIST_PIVOT
     
    544529    bool findEnteringEdge(EdgeIt &next_edge) {
    545530      for (EdgeIt e = next_edge; e != INVALID; ++e) {
    546         if (state[e] * red_cost[e] < 0) {
    547           in_edge = e;
    548           next_edge = ++e;
    549           return true;
    550         }
     531        if (state[e] * red_cost[e] < 0) {
     532          in_edge = e;
     533          next_edge = ++e;
     534          return true;
     535        }
    551536      }
    552537      for (EdgeIt e(graph); e != next_edge; ++e) {
    553         if (state[e] * red_cost[e] < 0) {
    554           in_edge = e;
    555           next_edge = ++e;
    556           return true;
    557         }
     538        if (state[e] * red_cost[e] < 0) {
     539          in_edge = e;
     540          next_edge = ++e;
     541          return true;
     542        }
    558543      }
    559544      return false;
     
    567552      Cost min = 0;
    568553      for (EdgeIt e(graph); e != INVALID; ++e) {
    569         if (state[e] * red_cost[e] < min) {
    570           min = state[e] * red_cost[e];
    571           in_edge = e;
    572         }
     554        if (state[e] * red_cost[e] < min) {
     555          min = state[e] * red_cost[e];
     556          in_edge = e;
     557        }
    573558      }
    574559      return min < 0;
     
    585570      int cnt = 0;
    586571      for (EdgeIt e = next_edge; e != INVALID; ++e) {
    587         if ((curr = state[e] * red_cost[e]) < min) {
    588           min = curr;
    589           min_edge = e;
    590         }
    591         if (++cnt == block_size) {
    592           if (min < 0) break;
    593           cnt = 0;
    594         }
     572        if ((curr = state[e] * red_cost[e]) < min) {
     573          min = curr;
     574          min_edge = e;
     575        }
     576        if (++cnt == block_size) {
     577          if (min < 0) break;
     578          cnt = 0;
     579        }
    595580      }
    596581      if (!(min < 0)) {
    597         for (EdgeIt e(graph); e != next_edge; ++e) {
    598           if ((curr = state[e] * red_cost[e]) < min) {
    599             min = curr;
    600             min_edge = e;
    601           }
    602           if (++cnt == block_size) {
    603             if (min < 0) break;
    604             cnt = 0;
    605           }
    606         }
     582        for (EdgeIt e(graph); e != next_edge; ++e) {
     583          if ((curr = state[e] * red_cost[e]) < min) {
     584            min = curr;
     585            min_edge = e;
     586          }
     587          if (++cnt == block_size) {
     588            if (min < 0) break;
     589            cnt = 0;
     590          }
     591        }
    607592      }
    608593      in_edge = min_edge;
    609594      if ((next_edge = ++min_edge) == INVALID)
    610         next_edge = EdgeIt(graph);
     595        next_edge = EdgeIt(graph);
    611596      return min < 0;
    612597    }
     
    620605
    621606      if (minor_count >= minor_limit || candidates.size() == 0) {
    622         // Major iteration
    623         candidates.clear();
    624         for (EdgeIt e(graph); e != INVALID; ++e) {
    625           if (state[e] * red_cost[e] < 0) {
    626             candidates.push_back(e);
    627             if (candidates.size() == list_length) break;
    628           }
    629         }
    630         if (candidates.size() == 0) return false;
     607        // Major iteration
     608        candidates.clear();
     609        for (EdgeIt e(graph); e != INVALID; ++e) {
     610          if (state[e] * red_cost[e] < 0) {
     611            candidates.push_back(e);
     612            if (candidates.size() == list_length) break;
     613          }
     614        }
     615        if (candidates.size() == 0) return false;
    631616      }
    632617
     
    637622      for (int i = 0; i < candidates.size(); ++i) {
    638623        e = candidates[i];
    639         if (state[e] * red_cost[e] < min) {
    640           min = state[e] * red_cost[e];
    641           in_edge = e;
    642         }
     624        if (state[e] * red_cost[e] < min) {
     625          min = state[e] * red_cost[e];
     626          in_edge = e;
     627        }
    643628      }
    644629      return true;
     
    656641    public:
    657642      SortFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
    658         st(_st), rc(_rc) {}
     643        st(_st), rc(_rc) {}
    659644      bool operator()(const Edge &e1, const Edge &e2) {
    660         return st[e1] * rc[e1] < st[e2] * rc[e2];
     645        return st[e1] * rc[e1] < st[e2] * rc[e2];
    661646      }
    662647    };
     
    669654      // Minor iteration
    670655      while (list_index < candidates.size()) {
    671         in_edge = candidates[list_index++];
    672         if (state[in_edge] * red_cost[in_edge] < 0) return true;
     656        in_edge = candidates[list_index++];
     657        if (state[in_edge] * red_cost[in_edge] < 0) return true;
    673658      }
    674659
     
    677662      Cost curr, min = 0;
    678663      for (EdgeIt e(graph); e != INVALID; ++e) {
    679         if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
    680           candidates.push_back(e);
    681           if (curr < min) min = curr;
    682           if (candidates.size() == list_length) break;
    683         }
     664        if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
     665          candidates.push_back(e);
     666          if (curr < min) min = curr;
     667          if (candidates.size() == list_length) break;
     668        }
    684669      }
    685670      if (candidates.size() == 0) return false;
     
    697682      Node v = graph.target(in_edge);
    698683      while (u != v) {
    699         if (depth[u] == depth[v]) {
    700           u = parent[u];
    701           v = parent[v];
    702         }
    703         else if (depth[u] > depth[v]) u = parent[u];
    704         else v = parent[v];
     684        if (depth[u] == depth[v]) {
     685          u = parent[u];
     686          v = parent[v];
     687        }
     688        else if (depth[u] > depth[v]) u = parent[u];
     689        else v = parent[v];
    705690      }
    706691      return u;
     
    713698      // of the cycle
    714699      if (state[in_edge] == LOWER) {
    715         first = graph.source(in_edge);
    716         second  = graph.target(in_edge);
     700        first = graph.source(in_edge);
     701        second  = graph.target(in_edge);
    717702      } else {
    718         first = graph.target(in_edge);
    719         second  = graph.source(in_edge);
     703        first = graph.target(in_edge);
     704        second  = graph.source(in_edge);
    720705      }
    721706      delta = capacity[in_edge];
     
    727712      // root node
    728713      for (Node u = first; u != join; u = parent[u]) {
    729         e = pred_edge[u];
    730         d = forward[u] ? flow[e] : capacity[e] - flow[e];
    731         if (d < delta) {
    732           delta = d;
    733           u_out = u;
    734           u_in = first;
    735           v_in = second;
    736           result = true;
    737         }
     714        e = pred_edge[u];
     715        d = forward[u] ? flow[e] : capacity[e] - flow[e];
     716        if (d < delta) {
     717          delta = d;
     718          u_out = u;
     719          u_in = first;
     720          v_in = second;
     721          result = true;
     722        }
    738723      }
    739724      // Searching the cycle along the path form the second node to the
    740725      // root node
    741726      for (Node u = second; u != join; u = parent[u]) {
    742         e = pred_edge[u];
    743         d = forward[u] ? capacity[e] - flow[e] : flow[e];
    744         if (d <= delta) {
    745           delta = d;
    746           u_out = u;
    747           u_in = second;
    748           v_in = first;
    749           result = true;
    750         }
     727        e = pred_edge[u];
     728        d = forward[u] ? capacity[e] - flow[e] : flow[e];
     729        if (d <= delta) {
     730          delta = d;
     731          u_out = u;
     732          u_in = second;
     733          v_in = first;
     734          result = true;
     735        }
    751736      }
    752737      return result;
    753738    }
    754739
    755     /// \brief Changes flow and state edge maps.
     740    /// \brief Changes \c flow and \c state edge maps.
    756741    void changeFlows(bool change) {
    757742      // Augmenting along the cycle
    758743      if (delta > 0) {
    759         Capacity val = state[in_edge] * delta;
    760         flow[in_edge] += val;
    761         for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
    762           flow[pred_edge[u]] += forward[u] ? -val : val;
    763         }
    764         for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
    765           flow[pred_edge[u]] += forward[u] ? val : -val;
    766         }
     744        Capacity val = state[in_edge] * delta;
     745        flow[in_edge] += val;
     746        for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
     747          flow[pred_edge[u]] += forward[u] ? -val : val;
     748        }
     749        for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
     750          flow[pred_edge[u]] += forward[u] ? val : -val;
     751        }
    767752      }
    768753      // Updating the state of the entering and leaving edges
    769754      if (change) {
    770         state[in_edge] = TREE;
    771         state[pred_edge[u_out]] =
    772           (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
     755        state[in_edge] = TREE;
     756        state[pred_edge[u_out]] =
     757          (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
    773758      } else {
    774         state[in_edge] = -state[in_edge];
    775       }
    776     }
    777 
    778     /// \brief Updates thread and parent node maps.
     759        state[in_edge] = -state[in_edge];
     760      }
     761    }
     762
     763    /// \brief Updates \c thread and \c parent node maps.
    779764    void updateThreadParent() {
    780765      Node u;
     
    784769      bool par_first = false;
    785770      if (join == v_out) {
    786         for (u = join; u != u_in && u != v_in; u = thread[u]) ;
    787         if (u == v_in) {
    788           par_first = true;
    789           while (thread[u] != u_out) u = thread[u];
    790           first = u;
    791         }
     771        for (u = join; u != u_in && u != v_in; u = thread[u]) ;
     772        if (u == v_in) {
     773          par_first = true;
     774          while (thread[u] != u_out) u = thread[u];
     775          first = u;
     776        }
    792777      }
    793778
     
    797782      right = thread[u];
    798783      if (thread[v_in] == u_out) {
    799         for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
    800         if (last == u_out) last = thread[last];
     784        for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
     785        if (last == u_out) last = thread[last];
    801786      }
    802787      else last = thread[v_in];
     
    806791      par_stem = v_in;
    807792      while (stem != u_out) {
    808         thread[u] = new_stem = parent[stem];
    809 
    810         // Finding the node just before the stem node (u) according to
    811         // the original thread index
    812         for (u = new_stem; thread[u] != stem; u = thread[u]) ;
    813         thread[u] = right;
    814 
    815         // Changing the parent node of stem and shifting stem and
    816         // par_stem nodes
    817         parent[stem] = par_stem;
    818         par_stem = stem;
    819         stem = new_stem;
    820 
    821         // Finding the last successor of stem (u) and the node after it
    822         // (right) according to the thread index
    823         for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
    824         right = thread[u];
     793        thread[u] = new_stem = parent[stem];
     794
     795        // Finding the node just before the stem node (u) according to
     796        // the original thread index
     797        for (u = new_stem; thread[u] != stem; u = thread[u]) ;
     798        thread[u] = right;
     799
     800        // Changing the parent node of stem and shifting stem and
     801        // par_stem nodes
     802        parent[stem] = par_stem;
     803        par_stem = stem;
     804        stem = new_stem;
     805
     806        // Finding the last successor of stem (u) and the node after it
     807        // (right) according to the thread index
     808        for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
     809        right = thread[u];
    825810      }
    826811      parent[u_out] = par_stem;
     
    828813
    829814      if (join == v_out && par_first) {
    830         if (first != v_in) thread[first] = right;
     815        if (first != v_in) thread[first] = right;
    831816      } else {
    832         for (u = v_out; thread[u] != u_out; u = thread[u]) ;
    833         thread[u] = right;
    834       }
    835     }
    836 
    837     /// \brief Updates pred_edge and forward node maps.
     817        for (u = v_out; thread[u] != u_out; u = thread[u]) ;
     818        thread[u] = right;
     819      }
     820    }
     821
     822    /// \brief Updates \c pred_edge and \c forward node maps.
    838823    void updatePredEdge() {
    839824      Node u = u_out, v;
    840825      while (u != u_in) {
    841         v = parent[u];
    842         pred_edge[u] = pred_edge[v];
    843         forward[u] = !forward[v];
    844         u = v;
     826        v = parent[u];
     827        pred_edge[u] = pred_edge[v];
     828        forward[u] = !forward[v];
     829        u = v;
    845830      }
    846831      pred_edge[u_in] = in_edge;
     
    848833    }
    849834
    850     /// \brief Updates depth and potential node maps.
     835    /// \brief Updates \c depth and \c potential node maps.
    851836    void updateDepthPotential() {
    852837      depth[u_in] = depth[v_in] + 1;
    853838      potential[u_in] = forward[u_in] ?
    854         potential[v_in] + cost[pred_edge[u_in]] :
    855         potential[v_in] - cost[pred_edge[u_in]];
     839        potential[v_in] + cost[pred_edge[u_in]] :
     840        potential[v_in] - cost[pred_edge[u_in]];
    856841
    857842      Node u = thread[u_in], v;
    858843      while (true) {
    859         v = parent[u];
    860         if (v == INVALID) break;
    861         depth[u] = depth[v] + 1;
    862         potential[u] = forward[u] ?
    863           potential[v] + cost[pred_edge[u]] :
    864           potential[v] - cost[pred_edge[u]];
    865         if (depth[u] <= depth[v_in]) break;
    866         u = thread[u];
     844        v = parent[u];
     845        if (v == INVALID) break;
     846        depth[u] = depth[v] + 1;
     847        potential[u] = forward[u] ?
     848          potential[v] + cost[pred_edge[u]] :
     849          potential[v] - cost[pred_edge[u]];
     850        if (depth[u] <= depth[v_in]) break;
     851        u = thread[u];
    867852      }
    868853    }
     
    881866#endif
    882867      {
    883         join = findJoinNode();
    884         bool change = findLeavingEdge();
    885         changeFlows(change);
    886         if (change) {
    887           updateThreadParent();
    888           updatePredEdge();
    889           updateDepthPotential();
    890         }
     868        join = findJoinNode();
     869        bool change = findLeavingEdge();
     870        changeFlows(change);
     871        if (change) {
     872          updateThreadParent();
     873          updatePredEdge();
     874          updateDepthPotential();
     875        }
    891876#ifdef _DEBUG_ITER_
    892         ++iter_num;
     877        ++iter_num;
    893878#endif
    894879      }
     
    896881#ifdef _DEBUG_ITER_
    897882      std::cout << "Network Simplex algorithm finished. " << iter_num
    898                 << " pivot iterations performed." << std::endl;
     883                << " pivot iterations performed." << std::endl;
    899884#endif
    900885
     
    902887      // artificial edges
    903888      for (InEdgeIt e(graph, root); e != INVALID; ++e)
    904         if (flow[e] > 0) return false;
     889        if (flow[e] > 0) return false;
    905890      for (OutEdgeIt e(graph, root); e != INVALID; ++e)
    906         if (flow[e] > 0) return false;
     891        if (flow[e] > 0) return false;
    907892
    908893      // Copying flow values to flow_result
    909894      if (lower) {
    910         for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
    911           flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
     895        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
     896          flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
    912897      } else {
    913         for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
    914           flow_result[e] = flow[edge_ref[e]];
     898        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
     899          flow_result[e] = flow[edge_ref[e]];
    915900      }
    916901      // Copying potential values to potential_result
    917902      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
    918         potential_result[n] = potential[node_ref[n]];
     903        potential_result[n] = potential[node_ref[n]];
    919904
    920905      return true;
Note: See TracChangeset for help on using the changeset viewer.