# HG changeset patch
# User deba
# Date 1181918184 0
# Node ID 8c791ee69a451b19896bc521379b27cd9668886f
# Parent  717a5134ddeb6b07e882180a37e913dd1af0b2ca
Improvments in min cost flow algorithms
 - improved cycle cancelling

diff -r 717a5134ddeb -r 8c791ee69a45 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h	Fri Jun 15 14:32:48 2007 +0000
+++ b/lemon/capacity_scaling.h	Fri Jun 15 14:36:24 2007 +0000
@@ -31,13 +31,15 @@
 
 #define WITH_SCALING
 
+//#define _DEBUG_ITER_
+
 namespace lemon {
 
   /// \addtogroup min_cost_flow
   /// @{
 
   /// \brief Implementation of the capacity scaling version of the
-  /// succesive shortest path algorithm for finding a minimum cost flow.
+  /// successive shortest path algorithm for finding a minimum cost flow.
   ///
   /// \ref lemon::CapacityScaling "CapacityScaling" implements a
   /// capacity scaling algorithm for finding a minimum cost flow.
@@ -299,6 +301,9 @@
     /// \brief Map for identifing deficit nodes.
     DeficitBoolMap delta_deficit;
 
+    /// \brief The deficit nodes.
+    std::vector<ResNode> deficit_nodes;
+
 #else //WITHOUT_CAPACITY_SCALING
     typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>
       ResDijkstra;
@@ -510,9 +515,9 @@
       return c;
     }
 
-    /// \brief Runs the successive shortest path algorithm.
+    /// \brief Runs the algorithm.
     ///
-    /// Runs the successive shortest path algorithm.
+    /// Runs the algorithm.
     ///
     /// \return \c true if a feasible flow can be found.
     bool run() {
@@ -531,11 +536,13 @@
 
 #ifdef WITH_SCALING
       // Initilaizing delta value
-      Capacity max_cap = 0;
-      for (EdgeIt e(graph); e != INVALID; ++e) {
-	if (capacity[e] > max_cap) max_cap = capacity[e];
+      Supply max_sup = 0, max_dem = 0;
+      for (NodeIt n(graph); n != INVALID; ++n) {
+	if (supply[n] >  max_sup) max_sup =  supply[n];
+	if (supply[n] < -max_dem) max_dem = -supply[n];
       }
-      for (delta = 1; 2 * delta < max_cap; delta *= 2) ;
+      if (max_dem < max_sup) max_sup = max_dem;
+      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
 #endif
       return true;
     }
@@ -546,6 +553,9 @@
     bool start() {
       typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
       typedef typename DeltaResGraph::Edge DeltaResEdge;
+#ifdef _DEBUG_ITER_
+      int dijk_num = 0;
+#endif
 
       // Processing capacity scaling phases
       ResNode s, t;
@@ -564,18 +574,35 @@
 
 	// Finding excess nodes
 	excess_nodes.clear();
+	deficit_nodes.clear();
 	for (ResNodeIt n(res_graph); n != INVALID; ++n) {
-	  if (imbalance[n] >= delta) excess_nodes.push_back(n);
+	  if (imbalance[n] >=  delta) excess_nodes.push_back(n);
+	  if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
 	}
 	next_node = 0;
 
-	// Finding successive shortest paths
+	// Finding shortest paths
 	while (next_node < excess_nodes.size()) {
+	  // Checking deficit nodes
+	  if (delta > 1) {
+	    bool delta_def = false;
+	    for (int i = 0; i < deficit_nodes.size(); ++i) {
+	      if (imbalance[deficit_nodes[i]] <= -delta) {
+		delta_def = true;
+		break;
+	      }
+	    }
+	    if (!delta_def) break;
+	  }
+
 	  // Running Dijkstra
 	  s = excess_nodes[next_node];
 	  updater.init();
 	  dijkstra.init();
 	  dijkstra.addSource(s);
+#ifdef _DEBUG_ITER_
+	  ++dijk_num;
+#endif
 	  if ((t = dijkstra.start(delta_deficit)) == INVALID) {
 	    if (delta > 1) {
 	      ++next_node;
@@ -608,6 +635,10 @@
 	  if (imbalance[s] < delta) ++next_node;
 	}
       }
+#ifdef _DEBUG_ITER_
+      std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
+	<< dijk_num << " times." << std::endl;
+#endif
 
       // Handling nonzero lower bounds
       if (lower) {
@@ -628,7 +659,7 @@
       if (excess_nodes.size() == 0) return true;
       next_node = 0;
 
-      // Finding successive shortest paths
+      // Finding shortest paths
       ResNode s, t;
       while ( imbalance[excess_nodes[next_node]] > 0 ||
 	      ++next_node < excess_nodes.size() )
diff -r 717a5134ddeb -r 8c791ee69a45 lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h	Fri Jun 15 14:32:48 2007 +0000
+++ b/lemon/cycle_canceling.h	Fri Jun 15 14:36:24 2007 +0000
@@ -22,13 +22,13 @@
 /// \ingroup min_cost_flow
 ///
 /// \file
-/// \brief A cycle canceling algorithm for finding a minimum cost flow.
+/// \brief A cycle-canceling algorithm for finding a minimum cost flow.
 
 #include <vector>
 #include <lemon/circulation.h>
 #include <lemon/graph_adaptor.h>
 
-/// \brief The used cycle canceling method.
+/// \brief The used cycle-canceling method.
 #define LIMITED_CYCLE_CANCELING
 //#define MIN_MEAN_CYCLE_CANCELING
 
@@ -36,17 +36,21 @@
   #include <lemon/bellman_ford.h>
   /// \brief The maximum number of iterations for the first execution
   /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
+  /// It should be at least 2.
   #define STARTING_LIMIT	2
   /// \brief The iteration limit for the
   /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
-  /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
+  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
   #define ALPHA_MUL		3
   /// \brief The iteration limit for the
   /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
-  /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
+  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
   #define ALPHA_DIV		2
 
 //#define _ONLY_ONE_CYCLE_
+//#define _NO_BACK_STEP_
 //#define _DEBUG_ITER_
 #endif
 
@@ -60,11 +64,11 @@
   /// \addtogroup min_cost_flow
   /// @{
 
-  /// \brief Implementation of a cycle canceling algorithm for finding
+  /// \brief Implementation of a cycle-canceling algorithm for finding
   /// a minimum cost flow.
   ///
-  /// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle
-  /// canceling algorithm for finding a minimum cost flow.
+  /// \ref lemon::CycleCanceling "CycleCanceling" implements a
+  /// cycle-canceling algorithm for finding a minimum cost flow.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
   /// \param LowerMap The type of the lower bound map.
@@ -118,26 +122,6 @@
 
   protected:
 
-    /// \brief Map adaptor class for demand map.
-    class DemandMap : public MapBase<Node, Supply>
-    {
-    private:
-
-      const SupplyMap *map;
-
-    public:
-
-      typedef typename MapBase<Node, Supply>::Value Value;
-      typedef typename MapBase<Node, Supply>::Key Key;
-
-      DemandMap(const SupplyMap &_map) : map(&_map) {}
-
-      Value operator[](const Key &e) const {
-	return -(*map)[e];
-      }
-
-    }; //class DemandMap
-
     /// \brief Map adaptor class for handling residual edge costs.
     class ResCostMap : public MapBase<ResEdge, Cost>
     {
@@ -170,8 +154,6 @@
     const CostMap &cost;
     /// \brief The modified supply map.
     SupplyRefMap supply;
-    /// \brief The modified demand map.
-    DemandMap demand;
     /// \brief The sum of supply values equals zero.
     bool valid_supply;
 
@@ -199,7 +181,7 @@
 		    const CostMap &_cost,
 		    const SupplyMap &_supply ) :
       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
-      supply(_graph), demand(supply), flow(_graph, 0),
+      supply(_graph), flow(_graph, 0),
       res_graph(_graph, capacity, flow), res_cost(cost)
     {
       // Removing nonzero lower bounds
@@ -229,7 +211,7 @@
 		    const CostMap &_cost,
 		    const SupplyMap &_supply ) :
       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
-      supply(_supply), demand(supply), flow(_graph, 0),
+      supply(_supply), flow(_graph, 0),
       res_graph(_graph, capacity, flow), res_cost(cost)
     {
       // Checking the sum of supply values
@@ -259,7 +241,7 @@
 		    Node _s, Node _t,
 		    Supply _flow_value ) :
       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
-      supply(_graph), demand(supply), flow(_graph, 0),
+      supply(_graph), flow(_graph, 0),
       res_graph(_graph, capacity, flow), res_cost(cost)
     {
       // Removing nonzero lower bounds
@@ -295,7 +277,7 @@
 		    Node _s, Node _t,
 		    Supply _flow_value ) :
       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
-      supply(_graph, 0), demand(supply), flow(_graph, 0),
+      supply(_graph, 0), flow(_graph, 0),
       res_graph(_graph, capacity, flow), res_cost(cost)
     {
       supply[_s] =  _flow_value;
@@ -345,14 +327,14 @@
 
       // Finding a feasible flow
       Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,
-		   CapacityRefMap, DemandMap >
+		   CapacityRefMap, SupplyMap >
 	circulation( graph, constMap<Edge>((Capacity)0),
-		     capacity, demand, flow );
+		     capacity, supply, flow );
       return circulation.run() == -1;
     }
 
 #ifdef LIMITED_CYCLE_CANCELING
-    /// \brief Executes a cycle canceling algorithm using
+    /// \brief Executes a cycle-canceling algorithm using
     /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
     /// iteration count.
     bool start() {
@@ -373,8 +355,13 @@
 	int iter_num = 0;
 	bool cycle_found = false;
 	while (!cycle_found) {
+#ifdef _NO_BACK_STEP_
+	  int curr_iter_num = length_bound <= node_num ?
+			      length_bound - iter_num : node_num - iter_num;
+#else
 	  int curr_iter_num = iter_num + length_bound <= node_num ?
 			      length_bound : node_num - iter_num;
+#endif
 	  iter_num += curr_iter_num;
 	  int real_iter_num = curr_iter_num;
 	  for (int i = 0; i < curr_iter_num; ++i) {
@@ -432,7 +419,7 @@
       }
 
 #ifdef _DEBUG_ITER_
-      std::cout << "Limited cycle canceling algorithm finished. "
+      std::cout << "Limited cycle-canceling algorithm finished. "
 		<< "Found " << cycle_num << " negative cycles."
 		<< std::endl;
 #endif
@@ -447,7 +434,7 @@
 #endif
 
 #ifdef MIN_MEAN_CYCLE_CANCELING
-    /// \brief Executes the minimum mean cycle canceling algorithm
+    /// \brief Executes the minimum mean cycle-canceling algorithm
     /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
     bool start() {
       typedef Path<ResGraph> ResPath;
@@ -486,7 +473,7 @@
       }
 
 #ifdef _DEBUG_ITER_
-      std::cout << "Minimum mean cycle canceling algorithm finished. "
+      std::cout << "Minimum mean cycle-canceling algorithm finished. "
 		<< "Found " << cycle_num << " negative cycles."
 		<< std::endl;
 #endif
diff -r 717a5134ddeb -r 8c791ee69a45 lemon/network_simplex.h
--- a/lemon/network_simplex.h	Fri Jun 15 14:32:48 2007 +0000
+++ b/lemon/network_simplex.h	Fri Jun 15 14:36:24 2007 +0000
@@ -275,6 +275,8 @@
       if (!(valid_supply = sum == 0)) return;
 
       // Copying graph_ref to graph
+      graph.reserveNode(countNodes(graph_ref) + 1);
+      graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
       copyGraph(graph, graph_ref)
 	.edgeMap(cost, _cost)
 	.nodeRef(node_ref)
@@ -477,7 +479,9 @@
       root = graph.addNode();
       parent[root] = INVALID;
       pred_edge[root] = INVALID;
-      depth[root] = supply[root] = potential[root] = 0;
+      depth[root] = 0;
+      supply[root] = 0;
+      potential[root] = 0;
 
       // Adding artificial edges to the graph and initializing the node
       // maps of the spanning tree data structure
@@ -513,7 +517,7 @@
 #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 ? 
+      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
 		   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
 #endif
 #ifdef CANDIDATE_LIST_PIVOT