COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
11/07/12 17:39:39 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1163:e344f0887c59 (diff), 1165:16f55008c863 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge docfix #437

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r1136 r1166  
    4949  ///
    5050  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    51   /// implementations available in LEMON for this problem.
     51  /// implementations available in LEMON for solving this problem.
     52  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5253  /// Furthermore, this class supports both directions of the supply/demand
    5354  /// inequality constraints. For more information, see \ref SupplyType.
     
    10101011    }
    10111012
    1012     /// \brief Return the flow map (the primal solution).
     1013    /// \brief Copy the flow values (the primal solution) into the
     1014    /// given map.
    10131015    ///
    10141016    /// This function copies the flow value on each arc into the given
     
    10341036    }
    10351037
    1036     /// \brief Return the potential map (the dual solution).
     1038    /// \brief Copy the potential values (the dual solution) into the
     1039    /// given map.
    10371040    ///
    10381041    /// This function copies the potential (dual value) of each node
  • lemon/network_simplex.h

    r1165 r1166  
    124124    /// the \ref run() function.
    125125    ///
    126     /// \ref NetworkSimplex provides five different pivot rule
    127     /// implementations that significantly affect the running time
     126    /// \ref NetworkSimplex provides five different implementations for
     127    /// the pivot strategy that significantly affects the running time
    128128    /// of the algorithm.
    129     /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    130     /// turend out to be the most efficient and the most robust on various
    131     /// test inputs.
    132     /// However, another pivot rule can be selected using the \ref run()
    133     /// function with the proper parameter.
     129    /// According to experimental tests conducted on various problem
     130    /// instances, \ref BLOCK_SEARCH "Block Search" and
     131    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
     132    /// to be the most efficient.
     133    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
     134    /// seemed to be slightly more robust, it is used by default.
     135    /// However, another pivot rule can easily be selected using the
     136    /// \ref run() function with the proper parameter.
    134137    enum PivotRule {
    135138
     
    157160      /// The \e Altering \e Candidate \e List pivot rule.
    158161      /// It is a modified version of the Candidate List method.
    159       /// It keeps only the several best eligible arcs from the former
     162      /// It keeps only a few of the best eligible arcs from the former
    160163      /// candidate list and extends this list in every iteration.
    161164      ALTERING_LIST
     
    540543        SortFunc(const CostVector &map) : _map(map) {}
    541544        bool operator()(int left, int right) {
    542           return _map[left] > _map[right];
     545          return _map[left] < _map[right];
    543546        }
    544547      };
     
    558561        const double BLOCK_SIZE_FACTOR = 1.0;
    559562        const int MIN_BLOCK_SIZE = 10;
    560         const double HEAD_LENGTH_FACTOR = 0.1;
     563        const double HEAD_LENGTH_FACTOR = 0.01;
    561564        const int MIN_HEAD_LENGTH = 3;
    562565
     
    602605        }
    603606        for (e = 0; e != _next_arc; ++e) {
    604           _cand_cost[e] = _state[e] *
    605             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    606           if (_cand_cost[e] < 0) {
     607          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     608          if (c < 0) {
     609            _cand_cost[e] = c;
    607610            _candidates[_curr_length++] = e;
    608611          }
     
    617620      search_end:
    618621
    619         // Make heap of the candidate list (approximating a partial sort)
    620         make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    621                    _sort_func );
    622 
    623         // Pop the first element of the heap
     622        // Perform partial sort operation on the candidate list
     623        int new_length = std::min(_head_length + 1, _curr_length);
     624        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
     625                          _candidates.begin() + _curr_length, _sort_func);
     626
     627        // Select the entering arc and remove it from the list
    624628        _in_arc = _candidates[0];
    625629        _next_arc = e;
    626         pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    627                   _sort_func );
    628         _curr_length = std::min(_head_length, _curr_length - 1);
     630        _candidates[0] = _candidates[new_length - 1];
     631        _curr_length = new_length - 1;
    629632        return true;
    630633      }
Note: See TracChangeset for help on using the changeset viewer.