Changeset 2444:06f3702bf18d in lemon-0.x for lemon/network_simplex.h

Timestamp:

05/11/07 18:03:20 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3281

Message:

Patch in network simplex

Patch from Peter Kovacs

File:

• lemon/network_simplex.h (modified) (9 diffs)

lemon/network_simplex.h

@@ -31 +31 @@
 
 /// \brief The pivot rule used in the algorithm.
-#define EDGE_BLOCK_PIVOT
 //#define FIRST_ELIGIBLE_PIVOT
 //#define BEST_ELIGIBLE_PIVOT
+#define EDGE_BLOCK_PIVOT
 //#define CANDIDATE_LIST_PIVOT
 //#define SORTED_LIST_PIVOT
+
+//#define _DEBUG_ITER_
+
 
 /// \brief State constant for edges at their lower bounds.
@@ -46 +49 @@
 #ifdef EDGE_BLOCK_PIVOT
   /// \brief Number of blocks for the "Edge Block" pivot rule.
-  #define BLOCK_NUM       100
-  /// \brief Lower bound for the number of edges to use "Edge Block"
-  // pivot rule instead of "First Eligible" pivot rule.
-  #define MIN_BOUND       1000
+  #define BLOCK_NUM             100
+  /// \brief Lower bound for the size of blocks.
+  #define MIN_BLOCK_SIZE        10
 #endif
 
@@ -56 +58 @@
   /// \brief The maximum length of the edge list for the
   /// "Candidate List" pivot rule.
-  #define LIST_LENGTH     100
+  #define LIST_LENGTH           100
   /// \brief The maximum number of minor iterations between two major
   /// itarations.
-  #define MINOR_LIMIT     50
+  #define MINOR_LIMIT           10
 #endif
 
@@ -67 +69 @@
   /// \brief The maximum length of the edge list for the
   /// "Sorted List" pivot rule.
-  #define LIST_LENGTH     500
-  #define LOWER_DIV       4
-#endif
-
-//#define _DEBUG_ITER_
+  #define LIST_LENGTH           500
+  #define LOWER_DIV             3
+#endif
 
 namespace lemon {
@@ -514 +514 @@
       // Initializing block_size for the edge block pivot rule
       int edge_num = countEdges(graph);
-      block_size = edge_num > MIN_BOUND ? edge_num / BLOCK_NUM + 1 : 1;
+      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 
+                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
@@ -564 +565 @@
     /// pivot rule.
     bool findEnteringEdge(EdgeIt &next_edge) {
-      if (block_size == 1) {
-        // Performing first eligible selection
-        for (EdgeIt e = next_edge; e != INVALID; ++e) {
-          if (state[e] * red_cost[e] < 0) {
-            in_edge = e;
-            next_edge = ++e;
-            return true;
-          }
-        }
+      // Performing edge block selection
+      Cost curr, min = 0;
+      EdgeIt min_edge(graph);
+      int cnt = 0;
+      for (EdgeIt e = next_edge; e != INVALID; ++e) {
+        if ((curr = state[e] * red_cost[e]) < min) {
+          min = curr;
+          min_edge = e;
+        }
+        if (++cnt == block_size) {
+          if (min < 0) break;
+          cnt = 0;
+        }
+      }
+      if (!(min < 0)) {
         for (EdgeIt e(graph); e != next_edge; ++e) {
-          if (state[e] * red_cost[e] < 0) {
-            in_edge = e;
-            next_edge = ++e;
-            return true;
-          }
-        }
-        return false;
-      } else {
-        // Performing edge block selection
-        Cost curr, min = 0;
-        EdgeIt min_edge(graph);
-        int cnt = 0;
-        for (EdgeIt e = next_edge; e != INVALID; ++e) {
           if ((curr = state[e] * red_cost[e]) < min) {
             min = curr;
@@ -596 +590 @@
           }
         }
-        if (!(min < 0)) {
-          for (EdgeIt e(graph); e != next_edge; ++e) {
-            if ((curr = state[e] * red_cost[e]) < min) {
-              min = curr;
-              min_edge = e;
-            }
-            if (++cnt == block_size) {
-              if (min < 0) break;
-              cnt = 0;
-            }
-          }
-        }
-        in_edge = min_edge;
-        if ((next_edge = ++min_edge) == INVALID)
-          next_edge = EdgeIt(graph);
-        return min < 0;
-      }
+      }
+      in_edge = min_edge;
+      if ((next_edge = ++min_edge) == INVALID)
+        next_edge = EdgeIt(graph);
+      return min < 0;
     }
 #endif
@@ -697 +679 @@
           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();
       return true;
     }
@@ -910 +894 @@
 
 #ifdef _DEBUG_ITER_
-      t_iter.stop();
       std::cout << "Network Simplex algorithm finished. " << iter_num
-                << " pivot iterations performed.";
+                << " pivot iterations performed." << std::endl;
 #endif