COIN-OR::LEMON - Graph Library

Changeset 2471:ed70b226cc48 in lemon-0.x


Ignore:
Timestamp:
09/14/07 00:06:54 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3309
Message:

Small changes in min. cost flow algorithms.

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r2457 r2471  
    3131
    3232#define WITH_SCALING
     33
     34#ifdef WITH_SCALING
     35#define SCALING_FACTOR    2
     36#endif
    3337
    3438//#define _DEBUG_ITER_
     
    543547      }
    544548      if (max_dem < max_sup) max_sup = max_dem;
    545       for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
     549      for ( delta = 1; SCALING_FACTOR * delta < max_sup;
     550            delta *= SCALING_FACTOR ) ;
    546551#endif
    547552      return true;
     
    560565      // Processing capacity scaling phases
    561566      ResNode s, t;
    562       for ( ; delta >= 1; delta = delta < 4 && delta > 1 ?
    563                                   1 : delta / 4 )
     567      for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ?
     568                                  1 : delta / SCALING_FACTOR )
    564569      {
    565570        // Saturating edges not satisfying the optimality condition
  • lemon/network_simplex.h

    r2457 r2471  
    4848
    4949#ifdef EDGE_BLOCK_PIVOT
    50   /// \brief Number of blocks for the "Edge Block" pivot rule.
    51   #define BLOCK_NUM             100
     50  #include <cmath>
    5251  /// \brief Lower bound for the size of blocks.
    5352  #define MIN_BLOCK_SIZE        10
     
    5554
    5655#ifdef CANDIDATE_LIST_PIVOT
    57   #include <list>
    58   /// \brief The maximum length of the edge list for the
    59   /// "Candidate List" pivot rule.
    60   #define LIST_LENGTH           100
    61   /// \brief The maximum number of minor iterations between two major
    62   /// itarations.
    63   #define MINOR_LIMIT           10
     56  #include <vector>
     57  #define LIST_LENGTH_DIV           50
     58  #define MINOR_LIMIT_DIV           200
    6459#endif
    6560
    6661#ifdef SORTED_LIST_PIVOT
    67   #include <deque>
     62  #include <vector>
    6863  #include <algorithm>
    69   /// \brief The maximum length of the edge list for the
    70   /// "Sorted List" pivot rule.
    71   #define LIST_LENGTH           500
    72   #define LOWER_DIV             3
     64  #define LIST_LENGTH_DIV       100
     65  #define LOWER_DIV             4
    7366#endif
    7467
     
    224217    /// \brief The list of candidate edges for the "Candidate List"
    225218    /// pivot rule.
    226     std::list<Edge> candidates;
     219    std::vector<Edge> candidates;
     220    /// \brief The maximum length of the edge list for the
     221    /// "Candidate List" pivot rule.
     222    int list_length;
     223    /// \brief The maximum number of minor iterations between two major
     224    /// itarations.
     225    int minor_limit;
    227226    /// \brief The number of minor iterations.
    228227    int minor_count;
     
    231230    /// \brief The list of candidate edges for the "Sorted List"
    232231    /// pivot rule.
    233     std::deque<Edge> candidates;
     232    std::vector<Edge> candidates;
     233    /// \brief The maximum length of the edge list for the
     234    /// "Sorted List" pivot rule.
     235    int list_length;
     236    int list_index;
    234237#endif
    235238
     
    518521      // Initializing block_size for the edge block pivot rule
    519522      int edge_num = countEdges(graph);
    520       block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
    521                    edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
     523      block_size = 2 * int(sqrt(countEdges(graph)));
     524      if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
     525//      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
     526//                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
    522527#endif
    523528#ifdef CANDIDATE_LIST_PIVOT
     529      int edge_num = countEdges(graph);
    524530      minor_count = 0;
     531      list_length = edge_num / LIST_LENGTH_DIV;
     532      minor_limit = edge_num / MINOR_LIMIT_DIV;
     533#endif
     534#ifdef SORTED_LIST_PIVOT
     535      int edge_num = countEdges(graph);
     536      list_index = 0;
     537      list_length = edge_num / LIST_LENGTH_DIV;
    525538#endif
    526539
     
    603616
    604617#ifdef CANDIDATE_LIST_PIVOT
    605     /// \brief Functor class for removing non-eligible edges from the
    606     /// candidate list.
    607     class RemoveFunc
    608     {
    609     private:
    610       const IntEdgeMap &st;
    611       const ReducedCostMap &rc;
    612     public:
    613       RemoveFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
    614         st(_st), rc(_rc) {}
    615       bool operator()(const Edge &e) {
    616         return st[e] * rc[e] >= 0;
    617       }
    618     };
    619 
    620618    /// \brief Finds entering edge according to the "Candidate List"
    621619    /// pivot rule.
    622620    bool findEnteringEdge() {
    623       static RemoveFunc remove_func(state, red_cost);
    624       typedef typename std::list<Edge>::iterator ListIt;
    625 
    626       candidates.remove_if(remove_func);
    627       if (minor_count >= MINOR_LIMIT || candidates.size() == 0) {
     621      typedef typename std::vector<Edge>::iterator ListIt;
     622
     623      if (minor_count >= minor_limit || candidates.size() == 0) {
    628624        // Major iteration
     625        candidates.clear();
    629626        for (EdgeIt e(graph); e != INVALID; ++e) {
    630627          if (state[e] * red_cost[e] < 0) {
    631628            candidates.push_back(e);
    632             if (candidates.size() == LIST_LENGTH) break;
     629            if (candidates.size() == list_length) break;
    633630          }
    634631        }
     
    639636      ++minor_count;
    640637      Cost min = 0;
    641       for (ListIt it = candidates.begin(); it != candidates.end(); ++it) {
    642         if (state[*it] * red_cost[*it] < min) {
    643           min = state[*it] * red_cost[*it];
    644           in_edge = *it;
     638      Edge e;
     639      for (int i = 0; i < candidates.size(); ++i) {
     640        e = candidates[i];
     641        if (state[e] * red_cost[e] < min) {
     642          min = state[e] * red_cost[e];
     643          in_edge = e;
    645644        }
    646645      }
     
    671670
    672671      // Minor iteration
    673       while (candidates.size() > 0) {
    674         in_edge = candidates.front();
    675         candidates.pop_front();
     672      while (list_index < candidates.size()) {
     673        in_edge = candidates[list_index++];
    676674        if (state[in_edge] * red_cost[in_edge] < 0) return true;
    677675      }
    678676
    679677      // Major iteration
     678      candidates.clear();
    680679      Cost curr, min = 0;
    681680      for (EdgeIt e(graph); e != INVALID; ++e) {
     
    683682          candidates.push_back(e);
    684683          if (curr < min) min = curr;
    685           if (candidates.size() == LIST_LENGTH) break;
     684          if (candidates.size() == list_length) break;
    686685        }
    687686      }
    688687      if (candidates.size() == 0) return false;
    689688      sort(candidates.begin(), candidates.end(), sort_func);
    690       in_edge = candidates.front();
    691       candidates.pop_front();
     689      in_edge = candidates[0];
     690      list_index = 1;
    692691      return true;
    693692    }
Note: See TracChangeset for help on using the changeset viewer.