1.1 --- a/lemon/network_simplex.h Fri May 11 16:02:53 2007 +0000
1.2 +++ b/lemon/network_simplex.h Fri May 11 16:03:20 2007 +0000
1.3 @@ -30,12 +30,15 @@
1.4 #include <lemon/graph_utils.h>
1.5
1.6 /// \brief The pivot rule used in the algorithm.
1.7 -#define EDGE_BLOCK_PIVOT
1.8 //#define FIRST_ELIGIBLE_PIVOT
1.9 //#define BEST_ELIGIBLE_PIVOT
1.10 +#define EDGE_BLOCK_PIVOT
1.11 //#define CANDIDATE_LIST_PIVOT
1.12 //#define SORTED_LIST_PIVOT
1.13
1.14 +//#define _DEBUG_ITER_
1.15 +
1.16 +
1.17 /// \brief State constant for edges at their lower bounds.
1.18 #define LOWER 1
1.19 /// \brief State constant for edges in the spanning tree.
1.20 @@ -45,20 +48,19 @@
1.21
1.22 #ifdef EDGE_BLOCK_PIVOT
1.23 /// \brief Number of blocks for the "Edge Block" pivot rule.
1.24 - #define BLOCK_NUM 100
1.25 - /// \brief Lower bound for the number of edges to use "Edge Block"
1.26 - // pivot rule instead of "First Eligible" pivot rule.
1.27 - #define MIN_BOUND 1000
1.28 + #define BLOCK_NUM 100
1.29 + /// \brief Lower bound for the size of blocks.
1.30 + #define MIN_BLOCK_SIZE 10
1.31 #endif
1.32
1.33 #ifdef CANDIDATE_LIST_PIVOT
1.34 #include <list>
1.35 /// \brief The maximum length of the edge list for the
1.36 /// "Candidate List" pivot rule.
1.37 - #define LIST_LENGTH 100
1.38 + #define LIST_LENGTH 100
1.39 /// \brief The maximum number of minor iterations between two major
1.40 /// itarations.
1.41 - #define MINOR_LIMIT 50
1.42 + #define MINOR_LIMIT 10
1.43 #endif
1.44
1.45 #ifdef SORTED_LIST_PIVOT
1.46 @@ -66,12 +68,10 @@
1.47 #include <algorithm>
1.48 /// \brief The maximum length of the edge list for the
1.49 /// "Sorted List" pivot rule.
1.50 - #define LIST_LENGTH 500
1.51 - #define LOWER_DIV 4
1.52 + #define LIST_LENGTH 500
1.53 + #define LOWER_DIV 3
1.54 #endif
1.55
1.56 -//#define _DEBUG_ITER_
1.57 -
1.58 namespace lemon {
1.59
1.60 /// \addtogroup min_cost_flow
1.61 @@ -513,7 +513,8 @@
1.62 #ifdef EDGE_BLOCK_PIVOT
1.63 // Initializing block_size for the edge block pivot rule
1.64 int edge_num = countEdges(graph);
1.65 - block_size = edge_num > MIN_BOUND ? edge_num / BLOCK_NUM + 1 : 1;
1.66 + block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
1.67 + edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
1.68 #endif
1.69 #ifdef CANDIDATE_LIST_PIVOT
1.70 minor_count = 0;
1.71 @@ -563,29 +564,22 @@
1.72 /// \brief Finds entering edge according to the "Edge Block"
1.73 /// pivot rule.
1.74 bool findEnteringEdge(EdgeIt &next_edge) {
1.75 - if (block_size == 1) {
1.76 - // Performing first eligible selection
1.77 - for (EdgeIt e = next_edge; e != INVALID; ++e) {
1.78 - if (state[e] * red_cost[e] < 0) {
1.79 - in_edge = e;
1.80 - next_edge = ++e;
1.81 - return true;
1.82 - }
1.83 + // Performing edge block selection
1.84 + Cost curr, min = 0;
1.85 + EdgeIt min_edge(graph);
1.86 + int cnt = 0;
1.87 + for (EdgeIt e = next_edge; e != INVALID; ++e) {
1.88 + if ((curr = state[e] * red_cost[e]) < min) {
1.89 + min = curr;
1.90 + min_edge = e;
1.91 }
1.92 + if (++cnt == block_size) {
1.93 + if (min < 0) break;
1.94 + cnt = 0;
1.95 + }
1.96 + }
1.97 + if (!(min < 0)) {
1.98 for (EdgeIt e(graph); e != next_edge; ++e) {
1.99 - if (state[e] * red_cost[e] < 0) {
1.100 - in_edge = e;
1.101 - next_edge = ++e;
1.102 - return true;
1.103 - }
1.104 - }
1.105 - return false;
1.106 - } else {
1.107 - // Performing edge block selection
1.108 - Cost curr, min = 0;
1.109 - EdgeIt min_edge(graph);
1.110 - int cnt = 0;
1.111 - for (EdgeIt e = next_edge; e != INVALID; ++e) {
1.112 if ((curr = state[e] * red_cost[e]) < min) {
1.113 min = curr;
1.114 min_edge = e;
1.115 @@ -595,23 +589,11 @@
1.116 cnt = 0;
1.117 }
1.118 }
1.119 - if (!(min < 0)) {
1.120 - for (EdgeIt e(graph); e != next_edge; ++e) {
1.121 - if ((curr = state[e] * red_cost[e]) < min) {
1.122 - min = curr;
1.123 - min_edge = e;
1.124 - }
1.125 - if (++cnt == block_size) {
1.126 - if (min < 0) break;
1.127 - cnt = 0;
1.128 - }
1.129 - }
1.130 - }
1.131 - in_edge = min_edge;
1.132 - if ((next_edge = ++min_edge) == INVALID)
1.133 - next_edge = EdgeIt(graph);
1.134 - return min < 0;
1.135 }
1.136 + in_edge = min_edge;
1.137 + if ((next_edge = ++min_edge) == INVALID)
1.138 + next_edge = EdgeIt(graph);
1.139 + return min < 0;
1.140 }
1.141 #endif
1.142
1.143 @@ -696,11 +678,13 @@
1.144 if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
1.145 candidates.push_back(e);
1.146 if (curr < min) min = curr;
1.147 - if (candidates.size() >= LIST_LENGTH) break;
1.148 + if (candidates.size() == LIST_LENGTH) break;
1.149 }
1.150 }
1.151 if (candidates.size() == 0) return false;
1.152 sort(candidates.begin(), candidates.end(), sort_func);
1.153 + in_edge = candidates.front();
1.154 + candidates.pop_front();
1.155 return true;
1.156 }
1.157 #endif
1.158 @@ -909,9 +893,8 @@
1.159 }
1.160
1.161 #ifdef _DEBUG_ITER_
1.162 - t_iter.stop();
1.163 std::cout << "Network Simplex algorithm finished. " << iter_num
1.164 - << " pivot iterations performed.";
1.165 + << " pivot iterations performed." << std::endl;
1.166 #endif
1.167
1.168 // Checking if the flow amount equals zero on all the