lemon-0.x: comparison lemon/network

equal deleted inserted replaced

-:7ef6c97ad0ab
+:76addb67b01f
 #include <limits>
 #include <lemon/smart_graph.h>
 #include <lemon/graph_utils.h>
 /// \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.
 #define LOWER	1
 /// \brief State constant for edges in the spanning tree.
 #define TREE	0
 /// \brief State constant for edges at their upper bounds.
 #define UPPER	-1
 #ifdef EDGE_BLOCK_PIVOT
 /// \brief Number of blocks for the "Edge Block" pivot rule.
-#define BLOCK_NUM	  100
+#define BLOCK_NUM		100
-/// \brief Lower bound for the number of edges to use "Edge Block"
+/// \brief Lower bound for the size of blocks.
-// pivot rule instead of "First Eligible" pivot rule.
+#define MIN_BLOCK_SIZE	10
-#define MIN_BOUND	  1000
 #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
+#define LIST_LENGTH		100
 /// \brief The maximum number of minor iterations between two major
 /// itarations.
-#define MINOR_LIMIT	  50
+#define MINOR_LIMIT		10
 #endif
 #ifdef SORTED_LIST_PIVOT
 #include <deque>
 #include <algorithm>
 /// \brief The maximum length of the edge list for the
 /// "Sorted List" pivot rule.
-#define LIST_LENGTH	  500
+#define LIST_LENGTH		500
-#define LOWER_DIV	  4
+#define LOWER_DIV		3
 #endif
-//#define _DEBUG_ITER_
 namespace lemon {
 /// \addtogroup min_cost_flow
 /// @{
 thread[last] = root;
 #ifdef EDGE_BLOCK_PIVOT
 // 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
 minor_count = 0;
 #endif
 #ifdef EDGE_BLOCK_PIVOT
 /// \brief Finds entering edge according to the "Edge Block"
 /// pivot rule.
 bool findEnteringEdge(EdgeIt &next_edge) {
-if (block_size == 1) {
+// Performing edge block selection
-	// Performing first eligible selection
+Cost curr, min = 0;
-	for (EdgeIt e = next_edge; e != INVALID; ++e) {
+EdgeIt min_edge(graph);
-	  if (state[e] * red_cost[e] < 0) {
+int cnt = 0;
-	    in_edge = e;
+for (EdgeIt e = next_edge; e != INVALID; ++e) {
-	    next_edge = ++e;
+	if ((curr = state[e] * red_cost[e]) < min) {
-	    return true;
+	  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;
 	    min_edge = e;
 	  }
 	  if (++cnt == block_size) {
 	    if (min < 0) break;
 	    cnt = 0;
 	  }
 	}
-	if (!(min < 0)) {
+}
-	  for (EdgeIt e(graph); e != next_edge; ++e) {
+in_edge = min_edge;
-	    if ((curr = state[e] * red_cost[e]) < min) {
+if ((next_edge = ++min_edge) == INVALID)
-	      min = curr;
+	next_edge = EdgeIt(graph);
-	      min_edge = e;
+return min < 0;
-	    }
-	    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;
-}
 }
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
 /// \brief Functor class for removing non-eligible edges from the
 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();
 return true;
 }
 #endif
 /// \brief Finds the join node.
 	++iter_num;
 #endif
 }
 #ifdef _DEBUG_ITER_
-t_iter.stop();
 std::cout << "Network Simplex algorithm finished. " << iter_num
-		<< " pivot iterations performed.";
+		<< " pivot iterations performed." << std::endl;
 #endif
 // Checking if the flow amount equals zero on all the
 // artificial edges
 for (InEdgeIt e(graph, root); e != INVALID; ++e)

changeset 2446	dd20d76eed13
parent 2440	c9218405595b
child 2457	8c791ee69a45