# HG changeset patch
# User kpeter
# Date 1189721214 0
# Node ID ed70b226cc485dfe676c774ecc97c825a072ccf6
# Parent  46818ce27a60c05053b8daa58de4eb1fff1ddf55
Small changes in min. cost flow algorithms.

diff -r 46818ce27a60 -r ed70b226cc48 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h	Thu Sep 13 22:05:32 2007 +0000
+++ b/lemon/capacity_scaling.h	Thu Sep 13 22:06:54 2007 +0000
@@ -31,6 +31,10 @@
 
 #define WITH_SCALING
 
+#ifdef WITH_SCALING
+#define SCALING_FACTOR	  2
+#endif
+
 //#define _DEBUG_ITER_
 
 namespace lemon {
@@ -542,7 +546,8 @@
 	if (supply[n] < -max_dem) max_dem = -supply[n];
       }
       if (max_dem < max_sup) max_sup = max_dem;
-      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
+      for ( delta = 1; SCALING_FACTOR * delta < max_sup;
+	    delta *= SCALING_FACTOR ) ;
 #endif
       return true;
     }
@@ -559,8 +564,8 @@
 
       // Processing capacity scaling phases
       ResNode s, t;
-      for ( ; delta >= 1; delta = delta < 4 && delta > 1 ?
-				  1 : delta / 4 )
+      for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ?
+				  1 : delta / SCALING_FACTOR )
       {
 	// Saturating edges not satisfying the optimality condition
 	Capacity r;
diff -r 46818ce27a60 -r ed70b226cc48 lemon/network_simplex.h
--- a/lemon/network_simplex.h	Thu Sep 13 22:05:32 2007 +0000
+++ b/lemon/network_simplex.h	Thu Sep 13 22:06:54 2007 +0000
@@ -47,29 +47,22 @@
 #define UPPER	-1
 
 #ifdef EDGE_BLOCK_PIVOT
-  /// \brief Number of blocks for the "Edge Block" pivot rule.
-  #define BLOCK_NUM		100
+  #include <cmath>
   /// \brief Lower bound for the size of blocks.
   #define MIN_BLOCK_SIZE	10
 #endif
 
 #ifdef CANDIDATE_LIST_PIVOT
-  #include <list>
-  /// \brief The maximum length of the edge list for the
-  /// "Candidate List" pivot rule.
-  #define LIST_LENGTH		100
-  /// \brief The maximum number of minor iterations between two major
-  /// itarations.
-  #define MINOR_LIMIT		10
+  #include <vector>
+  #define LIST_LENGTH_DIV           50
+  #define MINOR_LIMIT_DIV           200
 #endif
 
 #ifdef SORTED_LIST_PIVOT
-  #include <deque>
+  #include <vector>
   #include <algorithm>
-  /// \brief The maximum length of the edge list for the
-  /// "Sorted List" pivot rule.
-  #define LIST_LENGTH		500
-  #define LOWER_DIV		3
+  #define LIST_LENGTH_DIV       100
+  #define LOWER_DIV		4
 #endif
 
 namespace lemon {
@@ -223,14 +216,24 @@
 #ifdef CANDIDATE_LIST_PIVOT
     /// \brief The list of candidate edges for the "Candidate List"
     /// pivot rule.
-    std::list<Edge> candidates;
+    std::vector<Edge> candidates;
+    /// \brief The maximum length of the edge list for the
+    /// "Candidate List" pivot rule.
+    int list_length;
+    /// \brief The maximum number of minor iterations between two major
+    /// itarations.
+    int minor_limit;
     /// \brief The number of minor iterations.
     int minor_count;
 #endif
 #ifdef SORTED_LIST_PIVOT
     /// \brief The list of candidate edges for the "Sorted List"
     /// pivot rule.
-    std::deque<Edge> candidates;
+    std::vector<Edge> candidates;
+    /// \brief The maximum length of the edge list for the
+    /// "Sorted List" pivot rule.
+    int list_length;
+    int list_index;
 #endif
 
     // Root node of the starting spanning tree.
@@ -517,11 +520,21 @@
 #ifdef EDGE_BLOCK_PIVOT
       // Initializing block_size for the edge block pivot rule
       int edge_num = countEdges(graph);
-      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
-		   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
+      block_size = 2 * int(sqrt(countEdges(graph)));
+      if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
+//      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
+//                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
+      int edge_num = countEdges(graph);
       minor_count = 0;
+      list_length = edge_num / LIST_LENGTH_DIV;
+      minor_limit = edge_num / MINOR_LIMIT_DIV;
+#endif
+#ifdef SORTED_LIST_PIVOT
+      int edge_num = countEdges(graph);
+      list_index = 0;
+      list_length = edge_num / LIST_LENGTH_DIV;
 #endif
 
       return sum == 0;
@@ -602,34 +615,18 @@
 #endif
 
 #ifdef CANDIDATE_LIST_PIVOT
-    /// \brief Functor class for removing non-eligible edges from the
-    /// candidate list.
-    class RemoveFunc
-    {
-    private:
-      const IntEdgeMap &st;
-      const ReducedCostMap &rc;
-    public:
-      RemoveFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
-	st(_st), rc(_rc) {}
-      bool operator()(const Edge &e) {
-	return st[e] * rc[e] >= 0;
-      }
-    };
-
     /// \brief Finds entering edge according to the "Candidate List"
     /// pivot rule.
     bool findEnteringEdge() {
-      static RemoveFunc remove_func(state, red_cost);
-      typedef typename std::list<Edge>::iterator ListIt;
+      typedef typename std::vector<Edge>::iterator ListIt;
 
-      candidates.remove_if(remove_func);
-      if (minor_count >= MINOR_LIMIT || candidates.size() == 0) {
+      if (minor_count >= minor_limit || candidates.size() == 0) {
 	// Major iteration
+	candidates.clear();
 	for (EdgeIt e(graph); e != INVALID; ++e) {
 	  if (state[e] * red_cost[e] < 0) {
 	    candidates.push_back(e);
-	    if (candidates.size() == LIST_LENGTH) break;
+	    if (candidates.size() == list_length) break;
 	  }
 	}
 	if (candidates.size() == 0) return false;
@@ -638,10 +635,12 @@
       // Minor iteration
       ++minor_count;
       Cost min = 0;
-      for (ListIt it = candidates.begin(); it != candidates.end(); ++it) {
-	if (state[*it] * red_cost[*it] < min) {
-	  min = state[*it] * red_cost[*it];
-	  in_edge = *it;
+      Edge e;
+      for (int i = 0; i < candidates.size(); ++i) {
+        e = candidates[i];
+	if (state[e] * red_cost[e] < min) {
+	  min = state[e] * red_cost[e];
+	  in_edge = e;
 	}
       }
       return true;
@@ -670,25 +669,25 @@
       static SortFunc sort_func(state, red_cost);
 
       // Minor iteration
-      while (candidates.size() > 0) {
-	in_edge = candidates.front();
-	candidates.pop_front();
+      while (list_index < candidates.size()) {
+	in_edge = candidates[list_index++];
 	if (state[in_edge] * red_cost[in_edge] < 0) return true;
       }
 
       // Major iteration
+      candidates.clear();
       Cost curr, min = 0;
       for (EdgeIt e(graph); e != INVALID; ++e) {
 	if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
 	  candidates.push_back(e);
 	  if (curr < min) min = curr;
-	  if (candidates.size() == LIST_LENGTH) break;
+	  if (candidates.size() == list_length) break;
 	}
       }
       if (candidates.size() == 0) return false;
       sort(candidates.begin(), candidates.end(), sort_func);
-      in_edge = candidates.front();
-      candidates.pop_front();
+      in_edge = candidates[0];
+      list_index = 1;
       return true;
     }
 #endif