COIN-OR::LEMON - Graph Library

Changeset 2619:30fb4d68b0e8 in lemon-0.x


Ignore:
Timestamp:
10/05/08 15:36:43 (15 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3504
Message:

Improve network simplex algorithm

  • Remove "Limited Search" and "Combined" pivot rules.
  • Add a new pivot rule "Altering Candidate List".
  • Make the edge selection faster in every pivot rule.
  • Set the default rule to "Block Search".
  • Doc improvements.

The algorithm became about 15-35 percent faster on various input files.
"Block Search" pivot rule proved to be by far the fastest on all inputs.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r2593 r2619  
    3333#include <lemon/math.h>
    3434
     35#define _DEBUG_
     36
    3537namespace lemon {
    3638
     
    3840  /// @{
    3941
    40   /// \brief Implementation of the network simplex algorithm for
    41   /// finding a minimum cost flow.
     42  /// \brief Implementation of the primal network simplex algorithm
     43  /// for finding a minimum cost flow.
    4244  ///
    43   /// \ref NetworkSimplex implements the network simplex algorithm for
    44   /// finding a minimum cost flow.
     45  /// \ref NetworkSimplex implements the primal network simplex algorithm
     46  /// for finding a minimum cost flow.
    4547  ///
    4648  /// \tparam Graph The directed graph type the algorithm runs on.
     
    5658  /// - \c CostMap::Value must be signed type.
    5759  ///
    58   /// \note \ref NetworkSimplex provides six different pivot rule
     60  /// \note \ref NetworkSimplex provides five different pivot rule
    5961  /// implementations that significantly affect the efficiency of the
    6062  /// algorithm.
    61   /// By default a combined pivot rule is used, which is the fastest
    62   /// implementation according to our benchmark tests.
    63   /// Another pivot rule can be selected using \ref run() function
    64   /// with the proper parameter.
     63  /// By default "Block Search" pivot rule is used, which proved to be
     64  /// by far the most efficient according to our benchmark tests.
     65  /// However another pivot rule can be selected using \ref run()
     66  /// function with the proper parameter.
    6567  ///
    6668  /// \author Peter Kovacs
    67 
    6869  template < typename Graph,
    6970             typename LowerMap = typename Graph::template EdgeMap<int>,
     
    9091    typedef typename SGraph::template NodeMap<Edge> EdgeNodeMap;
    9192    typedef typename SGraph::template EdgeMap<int> IntEdgeMap;
     93    typedef typename SGraph::template EdgeMap<bool> BoolEdgeMap;
    9294
    9395    typedef typename Graph::template NodeMap<Node> NodeRefMap;
    9496    typedef typename Graph::template EdgeMap<Edge> EdgeRefMap;
     97
     98    typedef std::vector<Edge> EdgeVector;
    9599
    96100  public:
     
    108112      BEST_ELIGIBLE_PIVOT,
    109113      BLOCK_SEARCH_PIVOT,
    110       LIMITED_SEARCH_PIVOT,
    111114      CANDIDATE_LIST_PIVOT,
    112       COMBINED_PIVOT
     115      ALTERING_LIST_PIVOT
    113116    };
    114117
     
    149152    /// This class implements the "First Eligible" pivot rule
    150153    /// for the \ref NetworkSimplex "network simplex" algorithm.
     154    ///
     155    /// For more information see \ref NetworkSimplex::run().
    151156    class FirstEligiblePivotRule
    152157    {
    153158    private:
    154159
     160      // References to the NetworkSimplex class
    155161      NetworkSimplex &_ns;
    156       EdgeIt _next_edge;
     162      EdgeVector &_edges;
     163
     164      int _next_edge;
    157165
    158166    public:
    159167
    160       /// Constructor.
    161       FirstEligiblePivotRule(NetworkSimplex &ns) :
    162         _ns(ns), _next_edge(ns._graph) {}
    163 
    164       /// Finds the next entering edge.
    165       bool findEnteringEdge() {
    166         for (EdgeIt e = _next_edge; e != INVALID; ++e) {
     168      /// Constructor
     169      FirstEligiblePivotRule(NetworkSimplex &ns, EdgeVector &edges) :
     170        _ns(ns), _edges(edges), _next_edge(0) {}
     171
     172      /// Find next entering edge
     173      inline bool findEnteringEdge() {
     174        Edge e;
     175        for (int i = _next_edge; i < int(_edges.size()); ++i) {
     176          e = _edges[i];
    167177          if (_ns._state[e] * _ns._red_cost[e] < 0) {
    168178            _ns._in_edge = e;
    169             _next_edge = ++e;
     179            _next_edge = i + 1;
    170180            return true;
    171181          }
    172182        }
    173         for (EdgeIt e(_ns._graph); e != _next_edge; ++e) {
     183        for (int i = 0; i < _next_edge; ++i) {
     184          e = _edges[i];
    174185          if (_ns._state[e] * _ns._red_cost[e] < 0) {
    175186            _ns._in_edge = e;
    176             _next_edge = ++e;
     187            _next_edge = i + 1;
    177188            return true;
    178189          }
     
    187198    /// This class implements the "Best Eligible" pivot rule
    188199    /// for the \ref NetworkSimplex "network simplex" algorithm.
     200    ///
     201    /// For more information see \ref NetworkSimplex::run().
    189202    class BestEligiblePivotRule
    190203    {
    191204    private:
    192205
     206      // References to the NetworkSimplex class
    193207      NetworkSimplex &_ns;
     208      EdgeVector &_edges;
    194209
    195210    public:
    196211
    197       /// Constructor.
    198       BestEligiblePivotRule(NetworkSimplex &ns) : _ns(ns) {}
    199 
    200       /// Finds the next entering edge.
    201       bool findEnteringEdge() {
     212      /// Constructor
     213      BestEligiblePivotRule(NetworkSimplex &ns, EdgeVector &edges) :
     214        _ns(ns), _edges(edges) {}
     215
     216      /// Find next entering edge
     217      inline bool findEnteringEdge() {
    202218        Cost min = 0;
    203         for (EdgeIt e(_ns._graph); e != INVALID; ++e) {
     219        Edge e;
     220        for (int i = 0; i < int(_edges.size()); ++i) {
     221          e = _edges[i];
    204222          if (_ns._state[e] * _ns._red_cost[e] < min) {
    205223            min = _ns._state[e] * _ns._red_cost[e];
     
    216234    /// This class implements the "Block Search" pivot rule
    217235    /// for the \ref NetworkSimplex "network simplex" algorithm.
     236    ///
     237    /// For more information see \ref NetworkSimplex::run().
    218238    class BlockSearchPivotRule
    219239    {
    220240    private:
    221241
     242      // References to the NetworkSimplex class
    222243      NetworkSimplex &_ns;
    223       EdgeIt _next_edge, _min_edge;
     244      EdgeVector &_edges;
     245
    224246      int _block_size;
    225 
    226       static const int MIN_BLOCK_SIZE = 10;
     247      int _next_edge, _min_edge;
    227248
    228249    public:
    229250
    230       /// Constructor.
    231       BlockSearchPivotRule(NetworkSimplex &ns) :
    232         _ns(ns), _next_edge(ns._graph), _min_edge(ns._graph)
     251      /// Constructor
     252      BlockSearchPivotRule(NetworkSimplex &ns, EdgeVector &edges) :
     253        _ns(ns), _edges(edges), _next_edge(0), _min_edge(0)
    233254      {
    234         _block_size = 2 * int(sqrt(countEdges(_ns._graph)));
    235         if (_block_size < MIN_BLOCK_SIZE) _block_size = MIN_BLOCK_SIZE;
    236       }
    237 
    238       /// Finds the next entering edge.
    239       bool findEnteringEdge() {
     255        // The main parameters of the pivot rule
     256        const double BLOCK_SIZE_FACTOR = 2.0;
     257        const int MIN_BLOCK_SIZE = 10;
     258
     259        _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_edges.size())),
     260                                MIN_BLOCK_SIZE );
     261      }
     262
     263      /// Find next entering edge
     264      inline bool findEnteringEdge() {
    240265        Cost curr, min = 0;
    241         int cnt = 0;
    242         for (EdgeIt e = _next_edge; e != INVALID; ++e) {
     266        Edge e;
     267        int cnt = _block_size;
     268        int i;
     269        for (i = _next_edge; i < int(_edges.size()); ++i) {
     270          e = _edges[i];
    243271          if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) {
    244272            min = curr;
    245             _min_edge = e;
     273            _min_edge = i;
    246274          }
    247           if (++cnt == _block_size) {
     275          if (--cnt == 0) {
    248276            if (min < 0) break;
    249             cnt = 0;
     277            cnt = _block_size;
    250278          }
    251279        }
    252         if (min == 0) {
    253           for (EdgeIt e(_ns._graph); e != _next_edge; ++e) {
     280        if (min == 0 || cnt > 0) {
     281          for (i = 0; i < _next_edge; ++i) {
     282            e = _edges[i];
    254283            if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) {
    255284              min = curr;
    256               _min_edge = e;
     285              _min_edge = i;
    257286            }
    258             if (++cnt == _block_size) {
     287            if (--cnt == 0) {
    259288              if (min < 0) break;
    260               cnt = 0;
     289              cnt = _block_size;
    261290            }
    262291          }
    263292        }
    264         _ns._in_edge = _min_edge;
    265         _next_edge = ++_min_edge;
    266         return min < 0;
     293        if (min >= 0) return false;
     294        _ns._in_edge = _edges[_min_edge];
     295        _next_edge = i;
     296        return true;
    267297      }
    268298    }; //class BlockSearchPivotRule
    269 
    270     /// \brief Implementation of the "Limited Search" pivot rule for the
    271     /// \ref NetworkSimplex "network simplex" algorithm.
    272     ///
    273     /// This class implements the "Limited Search" pivot rule
    274     /// for the \ref NetworkSimplex "network simplex" algorithm.
    275     class LimitedSearchPivotRule
    276     {
    277     private:
    278 
    279       NetworkSimplex &_ns;
    280       EdgeIt _next_edge, _min_edge;
    281       int _sample_size;
    282 
    283       static const int SAMPLE_SIZE_FACTOR = 15;
    284       static const int MIN_SAMPLE_SIZE = 10;
    285 
    286     public:
    287 
    288       /// Constructor.
    289       LimitedSearchPivotRule(NetworkSimplex &ns) :
    290         _ns(ns), _next_edge(ns._graph), _min_edge(ns._graph)
    291       {
    292         _sample_size = countEdges(_ns._graph) *
    293                        SAMPLE_SIZE_FACTOR / 10000;
    294         if (_sample_size < MIN_SAMPLE_SIZE)
    295           _sample_size = MIN_SAMPLE_SIZE;
    296       }
    297 
    298       /// Finds the next entering edge.
    299       bool findEnteringEdge() {
    300         Cost curr, min = 0;
    301         int cnt = 0;
    302         for (EdgeIt e = _next_edge; e != INVALID; ++e) {
    303           if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) {
    304             min = curr;
    305             _min_edge = e;
    306           }
    307           if (curr < 0 && ++cnt == _sample_size) break;
    308         }
    309         if (min == 0) {
    310           for (EdgeIt e(_ns._graph); e != _next_edge; ++e) {
    311             if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) {
    312               min = curr;
    313               _min_edge = e;
    314             }
    315             if (curr < 0 && ++cnt == _sample_size) break;
    316           }
    317         }
    318         _ns._in_edge = _min_edge;
    319         _next_edge = ++_min_edge;
    320         return min < 0;
    321       }
    322     }; //class LimitedSearchPivotRule
    323299
    324300    /// \brief Implementation of the "Candidate List" pivot rule for the
     
    327303    /// This class implements the "Candidate List" pivot rule
    328304    /// for the \ref NetworkSimplex "network simplex" algorithm.
     305    ///
     306    /// For more information see \ref NetworkSimplex::run().
    329307    class CandidateListPivotRule
    330308    {
    331309    private:
    332310
     311      // References to the NetworkSimplex class
    333312      NetworkSimplex &_ns;
    334 
    335       // The list of candidate edges.
    336       std::vector<Edge> _candidates;
    337       // The maximum length of the edge list.
    338       int _list_length;
    339       // The maximum number of minor iterations between two major
    340       // itarations.
    341       int _minor_limit;
    342 
    343       int _minor_count;
    344       EdgeIt _next_edge;
    345 
    346       static const int LIST_LENGTH_FACTOR = 20;
    347       static const int MINOR_LIMIT_FACTOR = 10;
    348       static const int MIN_LIST_LENGTH = 10;
    349       static const int MIN_MINOR_LIMIT = 2;
     313      EdgeVector &_edges;
     314
     315      EdgeVector _candidates;
     316      int _list_length, _minor_limit;
     317      int _curr_length, _minor_count;
     318      int _next_edge, _min_edge;
    350319
    351320    public:
    352321
    353       /// Constructor.
    354       CandidateListPivotRule(NetworkSimplex &ns) :
    355         _ns(ns), _next_edge(ns._graph)
     322      /// Constructor
     323      CandidateListPivotRule(NetworkSimplex &ns, EdgeVector &edges) :
     324        _ns(ns), _edges(edges), _next_edge(0), _min_edge(0)
    356325      {
    357         int edge_num = countEdges(_ns._graph);
    358         _minor_count = 0;
    359         _list_length = edge_num * LIST_LENGTH_FACTOR / 10000;
    360         if (_list_length < MIN_LIST_LENGTH)
    361           _list_length = MIN_LIST_LENGTH;
    362         _minor_limit = _list_length * MINOR_LIMIT_FACTOR / 100;
    363         if (_minor_limit < MIN_MINOR_LIMIT)
    364           _minor_limit = MIN_MINOR_LIMIT;
    365       }
    366 
    367       /// Finds the next entering edge.
    368       bool findEnteringEdge() {
     326        // The main parameters of the pivot rule
     327        const double LIST_LENGTH_FACTOR = 1.0;
     328        const int MIN_LIST_LENGTH = 10;
     329        const double MINOR_LIMIT_FACTOR = 0.1;
     330        const int MIN_MINOR_LIMIT = 3;
     331
     332        _list_length = std::max( int(LIST_LENGTH_FACTOR * sqrt(_edges.size())),
     333                                 MIN_LIST_LENGTH );
     334        _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
     335                                 MIN_MINOR_LIMIT );
     336        _curr_length = _minor_count = 0;
     337        _candidates.resize(_list_length);
     338      }
     339
     340      /// Find next entering edge
     341      inline bool findEnteringEdge() {
    369342        Cost min, curr;
    370         if (_minor_count < _minor_limit && _candidates.size() > 0) {
    371           // Minor iteration
     343        if (_curr_length > 0 && _minor_count < _minor_limit) {
     344          // Minor iteration: selecting the best eligible edge from
     345          // the current candidate list
    372346          ++_minor_count;
    373347          Edge e;
    374348          min = 0;
    375           for (int i = 0; i < int(_candidates.size()); ++i) {
     349          for (int i = 0; i < _curr_length; ++i) {
    376350            e = _candidates[i];
    377             if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) {
    378               min = curr;
    379               _ns._in_edge = e;
    380             }
    381           }
    382           if (min < 0) return true;
    383         }
    384 
    385         // Major iteration
    386         _candidates.clear();
    387         EdgeIt e = _next_edge;
    388         min = 0;
    389         for ( ; e != INVALID; ++e) {
    390           if ((curr = _ns._state[e] * _ns._red_cost[e]) < 0) {
    391             _candidates.push_back(e);
     351            curr = _ns._state[e] * _ns._red_cost[e];
    392352            if (curr < min) {
    393353              min = curr;
    394354              _ns._in_edge = e;
    395355            }
    396             if (int(_candidates.size()) == _list_length) break;
     356            if (curr >= 0) {
     357              _candidates[i--] = _candidates[--_curr_length];
     358            }
    397359          }
    398         }
    399         if (int(_candidates.size()) < _list_length) {
    400           for (e = EdgeIt(_ns._graph); e != _next_edge; ++e) {
     360          if (min < 0) return true;
     361        }
     362
     363        // Major iteration: building a new candidate list
     364        Edge e;
     365        min = 0;
     366        _curr_length = 0;
     367        int i;
     368        for (i = _next_edge; i < int(_edges.size()); ++i) {
     369          e = _edges[i];
     370          if ((curr = _ns._state[e] * _ns._red_cost[e]) < 0) {
     371            _candidates[_curr_length++] = e;
     372            if (curr < min) {
     373              min = curr;
     374              _min_edge = i;
     375            }
     376            if (_curr_length == _list_length) break;
     377          }
     378        }
     379        if (_curr_length < _list_length) {
     380          for (i = 0; i < _next_edge; ++i) {
     381            e = _edges[i];
    401382            if ((curr = _ns._state[e] * _ns._red_cost[e]) < 0) {
    402               _candidates.push_back(e);
     383              _candidates[_curr_length++] = e;
    403384              if (curr < min) {
    404385                min = curr;
    405                 _ns._in_edge = e;
     386                _min_edge = i;
    406387              }
    407               if (int(_candidates.size()) == _list_length) break;
     388              if (_curr_length == _list_length) break;
    408389            }
    409390          }
    410391        }
    411         if (_candidates.size() == 0) return false;
     392        if (_curr_length == 0) return false;
    412393        _minor_count = 1;
    413         _next_edge = ++e;
     394        _ns._in_edge = _edges[_min_edge];
     395        _next_edge = i;
    414396        return true;
    415397      }
    416398    }; //class CandidateListPivotRule
     399
     400    /// \brief Implementation of the "Altering Candidate List" pivot rule
     401    /// for the \ref NetworkSimplex "network simplex" algorithm.
     402    ///
     403    /// This class implements the "Altering Candidate List" pivot rule
     404    /// for the \ref NetworkSimplex "network simplex" algorithm.
     405    ///
     406    /// For more information see \ref NetworkSimplex::run().
     407    class AlteringListPivotRule
     408    {
     409    private:
     410
     411      // References to the NetworkSimplex class
     412      NetworkSimplex &_ns;
     413      EdgeVector &_edges;
     414
     415      EdgeVector _candidates;
     416      SCostMap _cand_cost;
     417      int _block_size, _head_length, _curr_length;
     418      int _next_edge;
     419
     420      // Functor class to compare edges during sort of the candidate list
     421      class SortFunc
     422      {
     423      private:
     424        const SCostMap &_map;
     425      public:
     426        SortFunc(const SCostMap &map) : _map(map) {}
     427        bool operator()(const Edge &e1, const Edge &e2) {
     428          return _map[e1] < _map[e2];
     429        }
     430      };
     431
     432      SortFunc _sort_func;
     433
     434    public:
     435
     436      /// Constructor
     437      AlteringListPivotRule(NetworkSimplex &ns, EdgeVector &edges) :
     438        _ns(ns), _edges(edges), _cand_cost(_ns._graph),
     439        _next_edge(0), _sort_func(_cand_cost)
     440      {
     441        // The main parameters of the pivot rule
     442        const double BLOCK_SIZE_FACTOR = 1.0;
     443        const int MIN_BLOCK_SIZE = 10;
     444        const double HEAD_LENGTH_FACTOR = 0.1;
     445        const int MIN_HEAD_LENGTH = 5;
     446
     447        _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_edges.size())),
     448                                MIN_BLOCK_SIZE );
     449        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
     450                                 MIN_HEAD_LENGTH );
     451        _candidates.resize(_head_length + _block_size);
     452        _curr_length = 0;
     453      }
     454
     455      /// Find next entering edge
     456      inline bool findEnteringEdge() {
     457        // Checking the current candidate list
     458        Edge e;
     459        for (int idx = 0; idx < _curr_length; ++idx) {
     460          e = _candidates[idx];
     461          if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) >= 0) {
     462            _candidates[idx--] = _candidates[--_curr_length];
     463          }
     464        }
     465
     466        // Extending the list
     467        int cnt = _block_size;
     468        int last_edge = 0;
     469        int limit = _head_length;
     470        for (int i = _next_edge; i < int(_edges.size()); ++i) {
     471          e = _edges[i];
     472          if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) < 0) {
     473            _candidates[_curr_length++] = e;
     474            last_edge = i;
     475          }
     476          if (--cnt == 0) {
     477            if (_curr_length > limit) break;
     478            limit = 0;
     479            cnt = _block_size;
     480          }
     481        }
     482        if (_curr_length <= limit) {
     483          for (int i = 0; i < _next_edge; ++i) {
     484            e = _edges[i];
     485            if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) < 0) {
     486              _candidates[_curr_length++] = e;
     487              last_edge = i;
     488            }
     489            if (--cnt == 0) {
     490              if (_curr_length > limit) break;
     491              limit = 0;
     492              cnt = _block_size;
     493            }
     494          }
     495        }
     496        if (_curr_length == 0) return false;
     497        _next_edge = last_edge + 1;
     498
     499        // Sorting the list partially
     500        EdgeVector::iterator sort_end = _candidates.begin();
     501        EdgeVector::iterator vector_end = _candidates.begin();
     502        for (int idx = 0; idx < _curr_length; ++idx) {
     503          ++vector_end;
     504          if (idx <= _head_length) ++sort_end;
     505        }
     506        partial_sort(_candidates.begin(), sort_end, vector_end, _sort_func);
     507
     508        _ns._in_edge = _candidates[0];
     509        if (_curr_length > _head_length) {
     510          _candidates[0] = _candidates[_head_length - 1];
     511          _curr_length = _head_length - 1;
     512        } else {
     513          _candidates[0] = _candidates[_curr_length - 1];
     514          --_curr_length;
     515        }
     516
     517        return true;
     518      }
     519    }; //class AlteringListPivotRule
    417520
    418521  private:
     
    424527      STATE_LOWER =  1
    425528    };
    426 
    427     // Constant for the combined pivot rule.
    428     static const int COMBINED_PIVOT_MAX_DEG = 5;
    429529
    430530  private:
     
    466566    // The reduced cost map
    467567    ReducedCostMap _red_cost;
     568
     569    // The non-artifical edges
     570    EdgeVector _edges;
    468571
    469572    // Members for handling the original graph
     
    673776    }
    674777
    675     /// \brief Sets the flow map.
    676     ///
    677     /// Sets the flow map.
     778    /// \brief Set the flow map.
     779    ///
     780    /// Set the flow map.
    678781    ///
    679782    /// \return \c (*this)
     
    687790    }
    688791
    689     /// \brief Sets the potential map.
    690     ///
    691     /// Sets the potential map.
     792    /// \brief Set the potential map.
     793    ///
     794    /// Set the potential map.
    692795    ///
    693796    /// \return \c (*this)
     
    702805
    703806    /// \name Execution control
    704     /// The only way to execute the algorithm is to call the run()
    705     /// function.
    706807
    707808    /// @{
     
    727828    /// edge is selected from this block (\ref BlockSearchPivotRule).
    728829    ///
    729     /// - LIMITED_SEARCH_PIVOT A specified number of eligible edges are
    730     /// examined in every iteration in a wraparound fashion and the best
    731     /// one is selected from them (\ref LimitedSearchPivotRule).
    732     ///
    733     /// - CANDIDATE_LIST_PIVOT In major iterations a candidate list is
    734     /// built from eligible edges and it is used for edge selection in
    735     /// the following minor iterations (\ref CandidateListPivotRule).
    736     ///
    737     /// - COMBINED_PIVOT This is a combined version of the two fastest
    738     /// pivot rules.
    739     /// For rather sparse graphs \ref LimitedSearchPivotRule
    740     /// "Limited Search" implementation is used, otherwise
    741     /// \ref BlockSearchPivotRule "Block Search" pivot rule is used.
    742     /// According to our benchmark tests this combined method is the
    743     /// most efficient.
     830    /// - CANDIDATE_LIST_PIVOT In a major iteration a candidate list is
     831    /// built from eligible edges in a wraparound fashion and in the
     832    /// following minor iterations the best eligible edge is selected
     833    /// from this list (\ref CandidateListPivotRule).
     834    ///
     835    /// - ALTERING_LIST_PIVOT It is a modified version of the
     836    /// "Candidate List" pivot rule. It keeps only the several best
     837    /// eligible edges from the former candidate list and extends this
     838    /// list in every iteration (\ref AlteringListPivotRule).
     839    ///
     840    /// According to our comprehensive benchmark tests the "Block Search"
     841    /// pivot rule proved to be by far the fastest and the most robust
     842    /// on various test inputs. Thus it is the default option.
    744843    ///
    745844    /// \return \c true if a feasible flow can be found.
    746     bool run(PivotRuleEnum pivot_rule = COMBINED_PIVOT) {
     845    bool run(PivotRuleEnum pivot_rule = BLOCK_SEARCH_PIVOT) {
    747846      return init() && start(pivot_rule);
    748847    }
     
    751850
    752851    /// \name Query Functions
    753     /// The result of the algorithm can be obtained using these
    754     /// functions.
    755     /// \n run() must be called before using them.
     852    /// The results of the algorithm can be obtained using these
     853    /// functions.\n
     854    /// \ref lemon::NetworkSimplex::run() "run()" must be called before
     855    /// using them.
    756856
    757857    /// @{
    758858
    759     /// \brief Returns a const reference to the edge map storing the
     859    /// \brief Return a const reference to the edge map storing the
    760860    /// found flow.
    761861    ///
    762     /// Returns a const reference to the edge map storing the found flow.
     862    /// Return a const reference to the edge map storing the found flow.
    763863    ///
    764864    /// \pre \ref run() must be called before using this function.
     
    767867    }
    768868
    769     /// \brief Returns a const reference to the node map storing the
     869    /// \brief Return a const reference to the node map storing the
    770870    /// found potentials (the dual solution).
    771871    ///
    772     /// Returns a const reference to the node map storing the found
     872    /// Return a const reference to the node map storing the found
    773873    /// potentials (the dual solution).
    774874    ///
     
    778878    }
    779879
    780     /// \brief Returns the flow on the given edge.
    781     ///
    782     /// Returns the flow on the given edge.
     880    /// \brief Return the flow on the given edge.
     881    ///
     882    /// Return the flow on the given edge.
    783883    ///
    784884    /// \pre \ref run() must be called before using this function.
     
    787887    }
    788888
    789     /// \brief Returns the potential of the given node.
    790     ///
    791     /// Returns the potential of the given node.
     889    /// \brief Return the potential of the given node.
     890    ///
     891    /// Return the potential of the given node.
    792892    ///
    793893    /// \pre \ref run() must be called before using this function.
     
    796896    }
    797897
    798     /// \brief Returns the total cost of the found flow.
    799     ///
    800     /// Returns the total cost of the found flow. The complexity of the
     898    /// \brief Return the total cost of the found flow.
     899    ///
     900    /// Return the total cost of the found flow. The complexity of the
    801901    /// function is \f$ O(e) \f$.
    802902    ///
     
    813913  private:
    814914
    815     /// \brief Extends the underlaying graph and initializes all the
     915    /// \brief Extend the underlying graph and initialize all the
    816916    /// node and edge maps.
    817917    bool init() {
     
    828928      }
    829929
    830       // Initializing state and flow maps
     930      // Initializing the edge vector and the edge maps
     931      _edges.reserve(countEdges(_graph));
    831932      for (EdgeIt e(_graph); e != INVALID; ++e) {
     933        _edges.push_back(e);
    832934        _flow[e] = 0;
    833935        _state[e] = STATE_LOWER;
     
    874976    }
    875977
    876     /// Finds the join node.
    877     Node findJoinNode() {
     978    /// Find the join node.
     979    inline Node findJoinNode() {
    878980      Node u = _graph.source(_in_edge);
    879981      Node v = _graph.target(_in_edge);
     
    889991    }
    890992
    891     /// \brief Finds the leaving edge of the cycle. Returns \c true if
    892     /// the leaving edge is not the same as the entering edge.
    893     bool findLeavingEdge() {
     993    /// \brief Find the leaving edge of the cycle.
     994    /// \return \c true if the leaving edge is not the same as the
     995    /// entering edge.
     996    inline bool findLeavingEdge() {
    894997      // Initializing first and second nodes according to the direction
    895998      // of the cycle
     
    9351038    }
    9361039
    937     /// Changes \c flow and \c state edge maps.
    938     void changeFlows(bool change) {
     1040    /// Change \c flow and \c state edge maps.
     1041    inline void changeFlows(bool change) {
    9391042      // Augmenting along the cycle
    9401043      if (delta > 0) {
     
    9581061    }
    9591062
    960     /// Updates \c thread and \c parent node maps.
    961     void updateThreadParent() {
     1063    /// Update \c thread and \c parent node maps.
     1064    inline void updateThreadParent() {
    9621065      Node u;
    9631066      v_out = _parent[u_out];
     
    10171120    }
    10181121
    1019     /// Updates \c pred_edge and \c forward node maps.
    1020     void updatePredEdge() {
     1122    /// Update \c pred_edge and \c forward node maps.
     1123    inline void updatePredEdge() {
    10211124      Node u = u_out, v;
    10221125      while (u != u_in) {
     
    10301133    }
    10311134
    1032     /// Updates \c depth and \c potential node maps.
    1033     void updateDepthPotential() {
     1135    /// Update \c depth and \c potential node maps.
     1136    inline void updateDepthPotential() {
    10341137      _depth[u_in] = _depth[v_in] + 1;
    10351138      _potential[u_in] = _forward[u_in] ?
     
    10501153    }
    10511154
    1052     /// Executes the algorithm.
     1155    /// Execute the algorithm.
    10531156    bool start(PivotRuleEnum pivot_rule) {
     1157      // Selecting the pivot rule implementation
    10541158      switch (pivot_rule) {
    10551159        case FIRST_ELIGIBLE_PIVOT:
     
    10591163        case BLOCK_SEARCH_PIVOT:
    10601164          return start<BlockSearchPivotRule>();
    1061         case LIMITED_SEARCH_PIVOT:
    1062           return start<LimitedSearchPivotRule>();
    10631165        case CANDIDATE_LIST_PIVOT:
    10641166          return start<CandidateListPivotRule>();
    1065         case COMBINED_PIVOT:
    1066           if ( countEdges(_graph) / countNodes(_graph) <=
    1067                COMBINED_PIVOT_MAX_DEG )
    1068             return start<LimitedSearchPivotRule>();
    1069           else
    1070             return start<BlockSearchPivotRule>();
     1167        case ALTERING_LIST_PIVOT:
     1168          return start<AlteringListPivotRule>();
    10711169      }
    10721170      return false;
     
    10751173    template<class PivotRuleImplementation>
    10761174    bool start() {
    1077       PivotRuleImplementation pivot(*this);
     1175      PivotRuleImplementation pivot(*this, _edges);
    10781176
    10791177      // Executing the network simplex algorithm
Note: See TracChangeset for help on using the changeset viewer.