COIN-OR::LEMON - Graph Library

Changeset 1166:d59484d5fc1f in lemon


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

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r1137 r1166  
    7070  /// \ref edmondskarp72theoretical. It is an efficient dual
    7171  /// solution method.
     72  ///
     73  /// This algorithm is typically slower than \ref CostScaling and
     74  /// \ref NetworkSimplex, but in special cases, it can be more
     75  /// efficient than them.
     76  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    7277  ///
    7378  /// Most of the parameters of the problem (except for the digraph)
     
    677682    }
    678683
    679     /// \brief Return the flow map (the primal solution).
     684    /// \brief Copy the flow values (the primal solution) into the
     685    /// given map.
    680686    ///
    681687    /// This function copies the flow value on each arc into the given
     
    701707    }
    702708
    703     /// \brief Return the potential map (the dual solution).
     709    /// \brief Copy the potential values (the dual solution) into the
     710    /// given map.
    704711    ///
    705712    /// This function copies the potential (dual value) of each node
  • lemon/capacity_scaling.h

    r1165 r1166  
    9393  ///
    9494  /// \warning Both \c V and \c C must be signed number types.
    95   /// \warning All input data (capacities, supply values, and costs) must
    96   /// be integer.
     95  /// \warning Capacity bounds and supply values must be integer, but
     96  /// arc costs can be arbitrary real numbers.
    9797  /// \warning This algorithm does not support negative costs for
    9898  /// arcs having infinite upper bound.
  • 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.