1.1 --- a/lemon/capacity_scaling.h	Fri Jun 15 14:32:48 2007 +0000
     1.2 +++ b/lemon/capacity_scaling.h	Fri Jun 15 14:36:24 2007 +0000
     1.3 @@ -31,13 +31,15 @@
     1.4  
     1.5  #define WITH_SCALING
     1.6  
     1.7 +//#define _DEBUG_ITER_
     1.8 +
     1.9  namespace lemon {
    1.10  
    1.11    /// \addtogroup min_cost_flow
    1.12    /// @{
    1.13  
    1.14    /// \brief Implementation of the capacity scaling version of the
    1.15 -  /// succesive shortest path algorithm for finding a minimum cost flow.
    1.16 +  /// successive shortest path algorithm for finding a minimum cost flow.
    1.17    ///
    1.18    /// \ref lemon::CapacityScaling "CapacityScaling" implements a
    1.19    /// capacity scaling algorithm for finding a minimum cost flow.
    1.20 @@ -299,6 +301,9 @@
    1.21      /// \brief Map for identifing deficit nodes.
    1.22      DeficitBoolMap delta_deficit;
    1.23  
    1.24 +    /// \brief The deficit nodes.
    1.25 +    std::vector<ResNode> deficit_nodes;
    1.26 +
    1.27  #else //WITHOUT_CAPACITY_SCALING
    1.28      typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>
    1.29        ResDijkstra;
    1.30 @@ -510,9 +515,9 @@
    1.31        return c;
    1.32      }
    1.33  
    1.34 -    /// \brief Runs the successive shortest path algorithm.
    1.35 +    /// \brief Runs the algorithm.
    1.36      ///
    1.37 -    /// Runs the successive shortest path algorithm.
    1.38 +    /// Runs the algorithm.
    1.39      ///
    1.40      /// \return \c true if a feasible flow can be found.
    1.41      bool run() {
    1.42 @@ -531,11 +536,13 @@
    1.43  
    1.44  #ifdef WITH_SCALING
    1.45        // Initilaizing delta value
    1.46 -      Capacity max_cap = 0;
    1.47 -      for (EdgeIt e(graph); e != INVALID; ++e) {
    1.48 -	if (capacity[e] > max_cap) max_cap = capacity[e];
    1.49 +      Supply max_sup = 0, max_dem = 0;
    1.50 +      for (NodeIt n(graph); n != INVALID; ++n) {
    1.51 +	if (supply[n] >  max_sup) max_sup =  supply[n];
    1.52 +	if (supply[n] < -max_dem) max_dem = -supply[n];
    1.53        }
    1.54 -      for (delta = 1; 2 * delta < max_cap; delta *= 2) ;
    1.55 +      if (max_dem < max_sup) max_sup = max_dem;
    1.56 +      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
    1.57  #endif
    1.58        return true;
    1.59      }
    1.60 @@ -546,6 +553,9 @@
    1.61      bool start() {
    1.62        typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
    1.63        typedef typename DeltaResGraph::Edge DeltaResEdge;
    1.64 +#ifdef _DEBUG_ITER_
    1.65 +      int dijk_num = 0;
    1.66 +#endif
    1.67  
    1.68        // Processing capacity scaling phases
    1.69        ResNode s, t;
    1.70 @@ -564,18 +574,35 @@
    1.71  
    1.72  	// Finding excess nodes
    1.73  	excess_nodes.clear();
    1.74 +	deficit_nodes.clear();
    1.75  	for (ResNodeIt n(res_graph); n != INVALID; ++n) {
    1.76 -	  if (imbalance[n] >= delta) excess_nodes.push_back(n);
    1.77 +	  if (imbalance[n] >=  delta) excess_nodes.push_back(n);
    1.78 +	  if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
    1.79  	}
    1.80  	next_node = 0;
    1.81  
    1.82 -	// Finding successive shortest paths
    1.83 +	// Finding shortest paths
    1.84  	while (next_node < excess_nodes.size()) {
    1.85 +	  // Checking deficit nodes
    1.86 +	  if (delta > 1) {
    1.87 +	    bool delta_def = false;
    1.88 +	    for (int i = 0; i < deficit_nodes.size(); ++i) {
    1.89 +	      if (imbalance[deficit_nodes[i]] <= -delta) {
    1.90 +		delta_def = true;
    1.91 +		break;
    1.92 +	      }
    1.93 +	    }
    1.94 +	    if (!delta_def) break;
    1.95 +	  }
    1.96 +
    1.97  	  // Running Dijkstra
    1.98  	  s = excess_nodes[next_node];
    1.99  	  updater.init();
   1.100  	  dijkstra.init();
   1.101  	  dijkstra.addSource(s);
   1.102 +#ifdef _DEBUG_ITER_
   1.103 +	  ++dijk_num;
   1.104 +#endif
   1.105  	  if ((t = dijkstra.start(delta_deficit)) == INVALID) {
   1.106  	    if (delta > 1) {
   1.107  	      ++next_node;
   1.108 @@ -608,6 +635,10 @@
   1.109  	  if (imbalance[s] < delta) ++next_node;
   1.110  	}
   1.111        }
   1.112 +#ifdef _DEBUG_ITER_
   1.113 +      std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
   1.114 +	<< dijk_num << " times." << std::endl;
   1.115 +#endif
   1.116  
   1.117        // Handling nonzero lower bounds
   1.118        if (lower) {
   1.119 @@ -628,7 +659,7 @@
   1.120        if (excess_nodes.size() == 0) return true;
   1.121        next_node = 0;
   1.122  
   1.123 -      // Finding successive shortest paths
   1.124 +      // Finding shortest paths
   1.125        ResNode s, t;
   1.126        while ( imbalance[excess_nodes[next_node]] > 0 ||
   1.127  	      ++next_node < excess_nodes.size() )