1.1 --- a/lemon/network_simplex.h Thu Sep 13 22:05:32 2007 +0000
1.2 +++ b/lemon/network_simplex.h Thu Sep 13 22:06:54 2007 +0000
1.3 @@ -47,29 +47,22 @@
1.4 #define UPPER -1
1.5
1.6 #ifdef EDGE_BLOCK_PIVOT
1.7 - /// \brief Number of blocks for the "Edge Block" pivot rule.
1.8 - #define BLOCK_NUM 100
1.9 + #include <cmath>
1.10 /// \brief Lower bound for the size of blocks.
1.11 #define MIN_BLOCK_SIZE 10
1.12 #endif
1.13
1.14 #ifdef CANDIDATE_LIST_PIVOT
1.15 - #include <list>
1.16 - /// \brief The maximum length of the edge list for the
1.17 - /// "Candidate List" pivot rule.
1.18 - #define LIST_LENGTH 100
1.19 - /// \brief The maximum number of minor iterations between two major
1.20 - /// itarations.
1.21 - #define MINOR_LIMIT 10
1.22 + #include <vector>
1.23 + #define LIST_LENGTH_DIV 50
1.24 + #define MINOR_LIMIT_DIV 200
1.25 #endif
1.26
1.27 #ifdef SORTED_LIST_PIVOT
1.28 - #include <deque>
1.29 + #include <vector>
1.30 #include <algorithm>
1.31 - /// \brief The maximum length of the edge list for the
1.32 - /// "Sorted List" pivot rule.
1.33 - #define LIST_LENGTH 500
1.34 - #define LOWER_DIV 3
1.35 + #define LIST_LENGTH_DIV 100
1.36 + #define LOWER_DIV 4
1.37 #endif
1.38
1.39 namespace lemon {
1.40 @@ -223,14 +216,24 @@
1.41 #ifdef CANDIDATE_LIST_PIVOT
1.42 /// \brief The list of candidate edges for the "Candidate List"
1.43 /// pivot rule.
1.44 - std::list<Edge> candidates;
1.45 + std::vector<Edge> candidates;
1.46 + /// \brief The maximum length of the edge list for the
1.47 + /// "Candidate List" pivot rule.
1.48 + int list_length;
1.49 + /// \brief The maximum number of minor iterations between two major
1.50 + /// itarations.
1.51 + int minor_limit;
1.52 /// \brief The number of minor iterations.
1.53 int minor_count;
1.54 #endif
1.55 #ifdef SORTED_LIST_PIVOT
1.56 /// \brief The list of candidate edges for the "Sorted List"
1.57 /// pivot rule.
1.58 - std::deque<Edge> candidates;
1.59 + std::vector<Edge> candidates;
1.60 + /// \brief The maximum length of the edge list for the
1.61 + /// "Sorted List" pivot rule.
1.62 + int list_length;
1.63 + int list_index;
1.64 #endif
1.65
1.66 // Root node of the starting spanning tree.
1.67 @@ -517,11 +520,21 @@
1.68 #ifdef EDGE_BLOCK_PIVOT
1.69 // Initializing block_size for the edge block pivot rule
1.70 int edge_num = countEdges(graph);
1.71 - block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
1.72 - edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
1.73 + block_size = 2 * int(sqrt(countEdges(graph)));
1.74 + if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
1.75 +// block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
1.76 +// edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
1.77 #endif
1.78 #ifdef CANDIDATE_LIST_PIVOT
1.79 + int edge_num = countEdges(graph);
1.80 minor_count = 0;
1.81 + list_length = edge_num / LIST_LENGTH_DIV;
1.82 + minor_limit = edge_num / MINOR_LIMIT_DIV;
1.83 +#endif
1.84 +#ifdef SORTED_LIST_PIVOT
1.85 + int edge_num = countEdges(graph);
1.86 + list_index = 0;
1.87 + list_length = edge_num / LIST_LENGTH_DIV;
1.88 #endif
1.89
1.90 return sum == 0;
1.91 @@ -602,34 +615,18 @@
1.92 #endif
1.93
1.94 #ifdef CANDIDATE_LIST_PIVOT
1.95 - /// \brief Functor class for removing non-eligible edges from the
1.96 - /// candidate list.
1.97 - class RemoveFunc
1.98 - {
1.99 - private:
1.100 - const IntEdgeMap &st;
1.101 - const ReducedCostMap &rc;
1.102 - public:
1.103 - RemoveFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
1.104 - st(_st), rc(_rc) {}
1.105 - bool operator()(const Edge &e) {
1.106 - return st[e] * rc[e] >= 0;
1.107 - }
1.108 - };
1.109 -
1.110 /// \brief Finds entering edge according to the "Candidate List"
1.111 /// pivot rule.
1.112 bool findEnteringEdge() {
1.113 - static RemoveFunc remove_func(state, red_cost);
1.114 - typedef typename std::list<Edge>::iterator ListIt;
1.115 + typedef typename std::vector<Edge>::iterator ListIt;
1.116
1.117 - candidates.remove_if(remove_func);
1.118 - if (minor_count >= MINOR_LIMIT || candidates.size() == 0) {
1.119 + if (minor_count >= minor_limit || candidates.size() == 0) {
1.120 // Major iteration
1.121 + candidates.clear();
1.122 for (EdgeIt e(graph); e != INVALID; ++e) {
1.123 if (state[e] * red_cost[e] < 0) {
1.124 candidates.push_back(e);
1.125 - if (candidates.size() == LIST_LENGTH) break;
1.126 + if (candidates.size() == list_length) break;
1.127 }
1.128 }
1.129 if (candidates.size() == 0) return false;
1.130 @@ -638,10 +635,12 @@
1.131 // Minor iteration
1.132 ++minor_count;
1.133 Cost min = 0;
1.134 - for (ListIt it = candidates.begin(); it != candidates.end(); ++it) {
1.135 - if (state[*it] * red_cost[*it] < min) {
1.136 - min = state[*it] * red_cost[*it];
1.137 - in_edge = *it;
1.138 + Edge e;
1.139 + for (int i = 0; i < candidates.size(); ++i) {
1.140 + e = candidates[i];
1.141 + if (state[e] * red_cost[e] < min) {
1.142 + min = state[e] * red_cost[e];
1.143 + in_edge = e;
1.144 }
1.145 }
1.146 return true;
1.147 @@ -670,25 +669,25 @@
1.148 static SortFunc sort_func(state, red_cost);
1.149
1.150 // Minor iteration
1.151 - while (candidates.size() > 0) {
1.152 - in_edge = candidates.front();
1.153 - candidates.pop_front();
1.154 + while (list_index < candidates.size()) {
1.155 + in_edge = candidates[list_index++];
1.156 if (state[in_edge] * red_cost[in_edge] < 0) return true;
1.157 }
1.158
1.159 // Major iteration
1.160 + candidates.clear();
1.161 Cost curr, min = 0;
1.162 for (EdgeIt e(graph); e != INVALID; ++e) {
1.163 if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
1.164 candidates.push_back(e);
1.165 if (curr < min) min = curr;
1.166 - if (candidates.size() == LIST_LENGTH) break;
1.167 + if (candidates.size() == list_length) break;
1.168 }
1.169 }
1.170 if (candidates.size() == 0) return false;
1.171 sort(candidates.begin(), candidates.end(), sort_func);
1.172 - in_edge = candidates.front();
1.173 - candidates.pop_front();
1.174 + in_edge = candidates[0];
1.175 + list_index = 1;
1.176 return true;
1.177 }
1.178 #endif