Changeset 2471:ed70b226cc48 in lemon-0.x

Timestamp:

09/14/07 00:06:54 (17 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:

• capacity_scaling.h (modified) (3 diffs)
• network_simplex.h (modified) (9 diffs)

lemon/capacity_scaling.h

@@ -31 +31 @@
 
 #define WITH_SCALING
+
+#ifdef WITH_SCALING
+#define SCALING_FACTOR    2
+#endif
 
 //#define _DEBUG_ITER_
@@ -543 +547 @@
       }
       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;
@@ -560 +565 @@
       // 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

lemon/network_simplex.h

@@ -48 +48 @@
 
 #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
@@ -55 +54 @@
 
 #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
 
@@ -224 +217 @@
     /// \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;
@@ -231 +230 @@
     /// \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
 
@@ -518 +521 @@
       // 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
 
@@ -603 +616 @@
 
 #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;
-
-      candidates.remove_if(remove_func);
-      if (minor_count >= MINOR_LIMIT || candidates.size() == 0) {
+      typedef typename std::vector<Edge>::iterator ListIt;
+
+      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;
           }
         }
@@ -639 +636 @@
       ++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;
         }
       }
@@ -671 +670 @@
 
       // 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) {
@@ -683 +682 @@
           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;
     }