lemon/capacity_scaling.h
changeset 2533 aea952a1af99
parent 2509 a8081c9cd96a
child 2535 716024e7c080
equal deleted inserted replaced
4:03ce9e455775 5:d3a88fa60e48
    64   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
    64   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
    65   ///	convertible to \c SupplyMap::Value.
    65   ///	convertible to \c SupplyMap::Value.
    66   ///
    66   ///
    67   /// \author Peter Kovacs
    67   /// \author Peter Kovacs
    68 
    68 
    69 template < typename Graph,
    69   template < typename Graph,
    70 	   typename LowerMap = typename Graph::template EdgeMap<int>,
    70 	     typename LowerMap = typename Graph::template EdgeMap<int>,
    71 	   typename CapacityMap = LowerMap,
    71 	     typename CapacityMap = LowerMap,
    72 	   typename CostMap = typename Graph::template EdgeMap<int>,
    72 	     typename CostMap = typename Graph::template EdgeMap<int>,
    73 	   typename SupplyMap = typename Graph::template NodeMap
    73 	     typename SupplyMap = typename Graph::template NodeMap
    74 				<typename CapacityMap::Value> >
    74 				  <typename CapacityMap::Value> >
    75   class CapacityScaling
    75   class CapacityScaling
    76   {
    76   {
    77     typedef typename Graph::Node Node;
    77     typedef typename Graph::Node Node;
    78     typedef typename Graph::NodeIt NodeIt;
    78     typedef typename Graph::NodeIt NodeIt;
    79     typedef typename Graph::Edge Edge;
    79     typedef typename Graph::Edge Edge;
   636 	  imbalance[t] += d;
   636 	  imbalance[t] += d;
   637 	  if (imbalance[s] < delta) ++next_node;
   637 	  if (imbalance[s] < delta) ++next_node;
   638 	}
   638 	}
   639       }
   639       }
   640 #ifdef _DEBUG_ITER_
   640 #ifdef _DEBUG_ITER_
   641       std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
   641       std::cout << "Capacity Scaling algorithm finished with running Dijkstra algorithm "
   642 	<< dijk_num << " times." << std::endl;
   642 	<< dijk_num << " times." << std::endl;
   643 #endif
   643 #endif
   644 
   644 
   645       // Handling nonzero lower bounds
   645       // Handling nonzero lower bounds
   646       if (lower) {
   646       if (lower) {