1.1 --- a/lemon/capacity_scaling.h	Thu Sep 13 22:05:32 2007 +0000
     1.2 +++ b/lemon/capacity_scaling.h	Thu Sep 13 22:06:54 2007 +0000
     1.3 @@ -31,6 +31,10 @@
     1.4  
     1.5  #define WITH_SCALING
     1.6  
     1.7 +#ifdef WITH_SCALING
     1.8 +#define SCALING_FACTOR	  2
     1.9 +#endif
    1.10 +
    1.11  //#define _DEBUG_ITER_
    1.12  
    1.13  namespace lemon {
    1.14 @@ -542,7 +546,8 @@
    1.15  	if (supply[n] < -max_dem) max_dem = -supply[n];
    1.16        }
    1.17        if (max_dem < max_sup) max_sup = max_dem;
    1.18 -      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
    1.19 +      for ( delta = 1; SCALING_FACTOR * delta < max_sup;
    1.20 +	    delta *= SCALING_FACTOR ) ;
    1.21  #endif
    1.22        return true;
    1.23      }
    1.24 @@ -559,8 +564,8 @@
    1.25  
    1.26        // Processing capacity scaling phases
    1.27        ResNode s, t;
    1.28 -      for ( ; delta >= 1; delta = delta < 4 && delta > 1 ?
    1.29 -				  1 : delta / 4 )
    1.30 +      for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ?
    1.31 +				  1 : delta / SCALING_FACTOR )
    1.32        {
    1.33  	// Saturating edges not satisfying the optimality condition
    1.34  	Capacity r;

     2.1 --- a/lemon/network_simplex.h	Thu Sep 13 22:05:32 2007 +0000
     2.2 +++ b/lemon/network_simplex.h	Thu Sep 13 22:06:54 2007 +0000
     2.3 @@ -47,29 +47,22 @@
     2.4  #define UPPER	-1
     2.5  
     2.6  #ifdef EDGE_BLOCK_PIVOT
     2.7 -  /// \brief Number of blocks for the "Edge Block" pivot rule.
     2.8 -  #define BLOCK_NUM		100
     2.9 +  #include <cmath>
    2.10    /// \brief Lower bound for the size of blocks.
    2.11    #define MIN_BLOCK_SIZE	10
    2.12  #endif
    2.13  
    2.14  #ifdef CANDIDATE_LIST_PIVOT
    2.15 -  #include <list>
    2.16 -  /// \brief The maximum length of the edge list for the
    2.17 -  /// "Candidate List" pivot rule.
    2.18 -  #define LIST_LENGTH		100
    2.19 -  /// \brief The maximum number of minor iterations between two major
    2.20 -  /// itarations.
    2.21 -  #define MINOR_LIMIT		10
    2.22 +  #include <vector>
    2.23 +  #define LIST_LENGTH_DIV           50
    2.24 +  #define MINOR_LIMIT_DIV           200
    2.25  #endif
    2.26  
    2.27  #ifdef SORTED_LIST_PIVOT
    2.28 -  #include <deque>
    2.29 +  #include <vector>
    2.30    #include <algorithm>
    2.31 -  /// \brief The maximum length of the edge list for the
    2.32 -  /// "Sorted List" pivot rule.
    2.33 -  #define LIST_LENGTH		500
    2.34 -  #define LOWER_DIV		3
    2.35 +  #define LIST_LENGTH_DIV       100
    2.36 +  #define LOWER_DIV		4
    2.37  #endif
    2.38  
    2.39  namespace lemon {
    2.40 @@ -223,14 +216,24 @@
    2.41  #ifdef CANDIDATE_LIST_PIVOT
    2.42      /// \brief The list of candidate edges for the "Candidate List"
    2.43      /// pivot rule.
    2.44 -    std::list<Edge> candidates;
    2.45 +    std::vector<Edge> candidates;
    2.46 +    /// \brief The maximum length of the edge list for the
    2.47 +    /// "Candidate List" pivot rule.
    2.48 +    int list_length;
    2.49 +    /// \brief The maximum number of minor iterations between two major
    2.50 +    /// itarations.
    2.51 +    int minor_limit;
    2.52      /// \brief The number of minor iterations.
    2.53      int minor_count;
    2.54  #endif
    2.55  #ifdef SORTED_LIST_PIVOT
    2.56      /// \brief The list of candidate edges for the "Sorted List"
    2.57      /// pivot rule.
    2.58 -    std::deque<Edge> candidates;
    2.59 +    std::vector<Edge> candidates;
    2.60 +    /// \brief The maximum length of the edge list for the
    2.61 +    /// "Sorted List" pivot rule.
    2.62 +    int list_length;
    2.63 +    int list_index;
    2.64  #endif
    2.65  
    2.66      // Root node of the starting spanning tree.
    2.67 @@ -517,11 +520,21 @@
    2.68  #ifdef EDGE_BLOCK_PIVOT
    2.69        // Initializing block_size for the edge block pivot rule
    2.70        int edge_num = countEdges(graph);
    2.71 -      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
    2.72 -		   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
    2.73 +      block_size = 2 * int(sqrt(countEdges(graph)));
    2.74 +      if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
    2.75 +//      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
    2.76 +//                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
    2.77  #endif
    2.78  #ifdef CANDIDATE_LIST_PIVOT
    2.79 +      int edge_num = countEdges(graph);
    2.80        minor_count = 0;
    2.81 +      list_length = edge_num / LIST_LENGTH_DIV;
    2.82 +      minor_limit = edge_num / MINOR_LIMIT_DIV;
    2.83 +#endif
    2.84 +#ifdef SORTED_LIST_PIVOT
    2.85 +      int edge_num = countEdges(graph);
    2.86 +      list_index = 0;
    2.87 +      list_length = edge_num / LIST_LENGTH_DIV;
    2.88  #endif
    2.89  
    2.90        return sum == 0;
    2.91 @@ -602,34 +615,18 @@
    2.92  #endif
    2.93  
    2.94  #ifdef CANDIDATE_LIST_PIVOT
    2.95 -    /// \brief Functor class for removing non-eligible edges from the
    2.96 -    /// candidate list.
    2.97 -    class RemoveFunc
    2.98 -    {
    2.99 -    private:
   2.100 -      const IntEdgeMap &st;
   2.101 -      const ReducedCostMap &rc;
   2.102 -    public:
   2.103 -      RemoveFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
   2.104 -	st(_st), rc(_rc) {}
   2.105 -      bool operator()(const Edge &e) {
   2.106 -	return st[e] * rc[e] >= 0;
   2.107 -      }
   2.108 -    };
   2.109 -
   2.110      /// \brief Finds entering edge according to the "Candidate List"
   2.111      /// pivot rule.
   2.112      bool findEnteringEdge() {
   2.113 -      static RemoveFunc remove_func(state, red_cost);
   2.114 -      typedef typename std::list<Edge>::iterator ListIt;
   2.115 +      typedef typename std::vector<Edge>::iterator ListIt;
   2.116  
   2.117 -      candidates.remove_if(remove_func);
   2.118 -      if (minor_count >= MINOR_LIMIT || candidates.size() == 0) {
   2.119 +      if (minor_count >= minor_limit || candidates.size() == 0) {
   2.120  	// Major iteration
   2.121 +	candidates.clear();
   2.122  	for (EdgeIt e(graph); e != INVALID; ++e) {
   2.123  	  if (state[e] * red_cost[e] < 0) {
   2.124  	    candidates.push_back(e);
   2.125 -	    if (candidates.size() == LIST_LENGTH) break;
   2.126 +	    if (candidates.size() == list_length) break;
   2.127  	  }
   2.128  	}
   2.129  	if (candidates.size() == 0) return false;
   2.130 @@ -638,10 +635,12 @@
   2.131        // Minor iteration
   2.132        ++minor_count;
   2.133        Cost min = 0;
   2.134 -      for (ListIt it = candidates.begin(); it != candidates.end(); ++it) {
   2.135 -	if (state[*it] * red_cost[*it] < min) {
   2.136 -	  min = state[*it] * red_cost[*it];
   2.137 -	  in_edge = *it;
   2.138 +      Edge e;
   2.139 +      for (int i = 0; i < candidates.size(); ++i) {
   2.140 +        e = candidates[i];
   2.141 +	if (state[e] * red_cost[e] < min) {
   2.142 +	  min = state[e] * red_cost[e];
   2.143 +	  in_edge = e;
   2.144  	}
   2.145        }
   2.146        return true;
   2.147 @@ -670,25 +669,25 @@
   2.148        static SortFunc sort_func(state, red_cost);
   2.149  
   2.150        // Minor iteration
   2.151 -      while (candidates.size() > 0) {
   2.152 -	in_edge = candidates.front();
   2.153 -	candidates.pop_front();
   2.154 +      while (list_index < candidates.size()) {
   2.155 +	in_edge = candidates[list_index++];
   2.156  	if (state[in_edge] * red_cost[in_edge] < 0) return true;
   2.157        }
   2.158  
   2.159        // Major iteration
   2.160 +      candidates.clear();
   2.161        Cost curr, min = 0;
   2.162        for (EdgeIt e(graph); e != INVALID; ++e) {
   2.163  	if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
   2.164  	  candidates.push_back(e);
   2.165  	  if (curr < min) min = curr;
   2.166 -	  if (candidates.size() == LIST_LENGTH) break;
   2.167 +	  if (candidates.size() == list_length) break;
   2.168  	}
   2.169        }
   2.170        if (candidates.size() == 0) return false;
   2.171        sort(candidates.begin(), candidates.end(), sort_func);
   2.172 -      in_edge = candidates.front();
   2.173 -      candidates.pop_front();
   2.174 +      in_edge = candidates[0];
   2.175 +      list_index = 1;
   2.176        return true;
   2.177      }
   2.178  #endif