/// \ref lemon::CapacityScaling "CapacityScaling" implements the

   /// \ref CapacityScaling implements the capacity scaling version

   /// capacity scaling version of the successive shortest path

   /// of the successive shortest path algorithm for finding a minimum

   /// algorithm for finding a minimum cost flow.

   /// cost flow.

   ///	However \c CostMap::Value should be signed type.

   ///   However \c CostMap::Value should be signed type.

   ///	\c CapacityMap::Value and \c CapacityMap::Value must be

   ///   \c CapacityMap::Value and \c CapacityMap::Value must be

   ///	convertible to \c SupplyMap::Value.

   ///   convertible to \c SupplyMap::Value.

 	     typename LowerMap = typename Graph::template EdgeMap<int>,

              typename LowerMap = typename Graph::template EdgeMap<int>,

 	     typename CapacityMap = LowerMap,

              typename CapacityMap = LowerMap,

 	     typename CostMap = typename Graph::template EdgeMap<int>,

              typename CostMap = typename Graph::template EdgeMap<int>,

 	     typename SupplyMap = typename Graph::template NodeMap

              typename SupplyMap = typename Graph::template NodeMap

 				  <typename CapacityMap::Value> >

                                   <typename CapacityMap::Value> >

     typedef typename Graph::template NodeMap<Edge> PredMap;

     typedef ResGraphAdaptor< const Graph, Capacity,

 			     CapacityRefMap, CapacityRefMap > ResGraph;

     typedef typename ResGraph::Node ResNode;

     typedef typename ResGraph::NodeIt ResNodeIt;

     typedef typename ResGraph::Edge ResEdge;

     typedef typename ResGraph::EdgeIt ResEdgeIt;

     /// \brief Map adaptor class for handling reduced edge costs.

     /// \brief Special implementation of the \ref Dijkstra algorithm

     class ReducedCostMap : public MapBase<ResEdge, Cost>

     /// for finding shortest paths in the residual network of the graph

     /// with respect to the reduced edge costs and modifying the

     /// node potentials according to the distance of the nodes.

     class ResidualDijkstra

     private:

       typedef typename Graph::template NodeMap<Cost> CostNodeMap;

       typedef typename Graph::template NodeMap<Edge> PredMap;

       const ResGraph &gr;

       const CostMap &cost_map;

       typedef typename Graph::template NodeMap<int> HeapCrossRef;

       const PotentialMap &pot_map;

       typedef BinHeap<Cost, HeapCrossRef> Heap;

     protected:

       /// \brief The directed graph the algorithm runs on.

       const Graph &graph;

       /// \brief The flow map.

       const FlowMap &flow;

       /// \brief The residual capacity map.

       const CapacityRefMap &res_cap;

       /// \brief The cost map.

       const CostMap &cost;

       /// \brief The excess map.

       const SupplyRefMap &excess;

       /// \brief The potential map.

       PotentialMap &potential;

       /// \brief The distance map.

       CostNodeMap dist;

       /// \brief The map of predecessors edges.

       PredMap &pred;

       /// \brief The processed (i.e. permanently labeled) nodes.

       std::vector<Node> proc_nodes;

       ReducedCostMap( const ResGraph &_gr,

       /// \brief The constructor of the class.

 		      const CostMap &_cost,

       ResidualDijkstra( const Graph &_graph,

 		      const PotentialMap &_pot ) :

                         const FlowMap &_flow,

 	gr(_gr), cost_map(_cost), pot_map(_pot) {}

                         const CapacityRefMap &_res_cap,

                         const CostMap &_cost,

       Cost operator[](const ResEdge &e) const {

                         const SupplyMap &_excess,

 	return ResGraph::forward(e) ?

                         PotentialMap &_potential,

 	   cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :

                         PredMap &_pred ) :

 	  -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];

         graph(_graph), flow(_flow), res_cap(_res_cap), cost(_cost),

       }

         excess(_excess), potential(_potential), dist(_graph),

         pred(_pred)

     }; //class ReducedCostMap

       {}

     /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra"

       /// \brief Runs the algorithm from the given source node.

     /// algorithm to update node potentials.

       Node run(Node s, Capacity delta) {

     class PotentialUpdateMap : public MapBase<ResNode, Cost>

         HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);

     {

         Heap heap(heap_cross_ref);

     private:

         heap.push(s, 0);

         pred[s] = INVALID;

       PotentialMap *pot;

         proc_nodes.clear();

       typedef std::pair<ResNode, Cost> Pair;

       std::vector<Pair> data;

         // Processing nodes

         while (!heap.empty() && excess[heap.top()] > -delta) {

     public:

           Node u = heap.top(), v;

           Cost d = heap.prio() - potential[u], nd;

       void potentialMap(PotentialMap &_pot) {

           dist[u] = heap.prio();

 	pot = &_pot;

           heap.pop();

       }

           proc_nodes.push_back(u);

       void init() {

           // Traversing outgoing edges

 	data.clear();

           for (OutEdgeIt e(graph, u); e != INVALID; ++e) {

       }

             if (res_cap[e] >= delta) {

               v = graph.target(e);

       void set(const ResNode &n, const Cost &v) {

               switch(heap.state(v)) {

 	data.push_back(Pair(n, v));

               case Heap::PRE_HEAP:

       }

                 heap.push(v, d + cost[e] + potential[v]);

                 pred[v] = e;

       void update() {

                 break;

 	Cost val = data[data.size()-1].second;

               case Heap::IN_HEAP:

 	for (int i = 0; i < data.size()-1; ++i)

                 nd = d + cost[e] + potential[v];

 	  (*pot)[data[i].first] += val - data[i].second;

                 if (nd < heap[v]) {

       }

                   heap.decrease(v, nd);

                   pred[v] = e;

     }; //class PotentialUpdateMap

                 }

                 break;

 #ifdef WITH_SCALING

               case Heap::POST_HEAP:

     /// \brief Map adaptor class for identifing deficit nodes.

                 break;

     class DeficitBoolMap : public MapBase<ResNode, bool>

               }

     {

             }

     private:

           }

       const SupplyRefMap &imb;

           // Traversing incoming edges

       const Capacity δ

           for (InEdgeIt e(graph, u); e != INVALID; ++e) {

             if (flow[e] >= delta) {

     public:

               v = graph.source(e);

               switch(heap.state(v)) {

       DeficitBoolMap(const SupplyRefMap &_imb, const Capacity &_delta) :

               case Heap::PRE_HEAP:

 	imb(_imb), delta(_delta) {}

                 heap.push(v, d - cost[e] + potential[v]);

                 pred[v] = e;

       bool operator[](const ResNode &n) const {

                 break;

 	return imb[n] <= -delta;

               case Heap::IN_HEAP:

       }

                 nd = d - cost[e] + potential[v];

                 if (nd < heap[v]) {

     }; //class DeficitBoolMap

                   heap.decrease(v, nd);

                   pred[v] = e;

     /// \brief Map adaptor class for filtering edges with at least

                 }

     /// \c delta residual capacity.

                 break;

     class DeltaFilterMap : public MapBase<ResEdge, bool>

               case Heap::POST_HEAP:

     {

                 break;

     private:

               }

             }

       const ResGraph &gr;

           }

       const Capacity δ

         }

         if (heap.empty()) return INVALID;

     public:

         // Updating potentials of processed nodes

       DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :

         Node t = heap.top();

 	gr(_gr), delta(_delta) {}

         Cost dt = heap.prio();

         for (int i = 0; i < proc_nodes.size(); ++i)

       bool operator[](const ResEdge &e) const {

           potential[proc_nodes[i]] -= dist[proc_nodes[i]] - dt;

 	return gr.rescap(e) >= delta;

       }

         return t;

       }

     }; //class DeltaFilterMap

     }; //class ResidualDijkstra

     typedef EdgeSubGraphAdaptor<const ResGraph, const DeltaFilterMap>

       DeltaResGraph;

     /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.

     class ResDijkstraTraits :

       public DijkstraDefaultTraits<DeltaResGraph, ReducedCostMap>

     {

     public:

       typedef PotentialUpdateMap DistMap;

       static DistMap *createDistMap(const DeltaResGraph&) {

 	return new DistMap();

       }

     }; //class ResDijkstraTraits

 #else //WITHOUT_CAPACITY_SCALING

     /// \brief Map adaptor class for identifing deficit nodes.

     class DeficitBoolMap : public MapBase<ResNode, bool>

     {

     private:

       const SupplyRefMap &imb;

     public:

       DeficitBoolMap(const SupplyRefMap &_imb) : imb(_imb) {}

       bool operator[](const ResNode &n) const {

 	return imb[n] < 0;

       }

     }; //class DeficitBoolMap

     /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.

     class ResDijkstraTraits :

       public DijkstraDefaultTraits<ResGraph, ReducedCostMap>

     {

     public:

       typedef PotentialUpdateMap DistMap;

       static DistMap *createDistMap(const ResGraph&) {

 	return new DistMap();

       }

     }; //class ResDijkstraTraits

 #endif

     /// \brief The residual graph.

     ResGraph res_graph;

     /// \brief The residual capacity map.

     /// \brief The reduced cost map.

     CapacityRefMap res_cap;

     ReducedCostMap red_cost;

     /// \brief The excess map.

     SupplyRefMap excess;

     /// \brief The imbalance map.

     /// \brief The excess nodes (i.e. nodes with positive excess).

     SupplyRefMap imbalance;

     std::vector<Node> excess_nodes;

     /// \brief The excess nodes.

     std::vector<ResNode> excess_nodes;

 #ifdef WITH_SCALING

     /// \brief The scaling status (enabled or disabled).

     typedef Dijkstra<DeltaResGraph, ReducedCostMap, ResDijkstraTraits>

     ScalingEnum scaling;

       ResDijkstra;

     /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding

     /// shortest paths in the residual graph with respect to the

     /// reduced edge costs.

     ResDijkstra dijkstra;

     /// \brief Edge filter map for filtering edges with at least

     /// \brief The maximum number of phases.

     /// \c delta residual capacity.

     Capacity phase_num;

     DeltaFilterMap delta_filter;

     /// \brief The delta residual graph (i.e. the subgraph of the

     /// residual graph consisting of edges with at least \c delta

     /// residual capacity).

     DeltaResGraph dres_graph;

     /// \brief Map for identifing deficit nodes.

     DeficitBoolMap delta_deficit;

     std::vector<ResNode> deficit_nodes;

     std::vector<Node> deficit_nodes;

 #else //WITHOUT_CAPACITY_SCALING

     /// \brief Implementation of the \ref Dijkstra algorithm for

     typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>

     /// finding augmenting shortest paths in the residual network.

       ResDijkstra;

     ResidualDijkstra dijkstra;

     /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding

     /// \brief The map of predecessors edges.

     /// shortest paths in the residual graph with respect to the

     PredMap pred;

     /// reduced edge costs.

     ResDijkstra dijkstra;

     /// \brief Map for identifing deficit nodes.

     DeficitBoolMap has_deficit;

 #endif

     /// \brief Pred map for the \ref lemon::Dijkstra "Dijkstra" class.

     typename ResDijkstra::PredMap pred;

     /// \brief Dist map for the \ref lemon::Dijkstra "Dijkstra" class to

     /// update node potentials.

     PotentialUpdateMap updater;

 		     const LowerMap &_lower,

                      const LowerMap &_lower,

 		     const CapacityMap &_capacity,

                      const CapacityMap &_capacity,

 		     const CostMap &_cost,

                      const CostMap &_cost,

 		     const SupplyMap &_supply ) :

                      const SupplyMap &_supply ) :

       res_graph(_graph, capacity, flow),

       res_cap(_graph), excess(_graph), pred(_graph),

       red_cost(res_graph, cost, potential), imbalance(_graph),

       dijkstra(graph, flow, res_cap, cost, excess, potential, pred)

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

 	Supply s = _supply[n];

         Supply s = _supply[n];

 	for (InEdgeIt e(graph, n); e != INVALID; ++e)

         for (InEdgeIt e(graph, n); e != INVALID; ++e)

 	  s += _lower[e];

           s += _lower[e];

 	for (OutEdgeIt e(graph, n); e != INVALID; ++e)

         for (OutEdgeIt e(graph, n); e != INVALID; ++e)

 	  s -= _lower[e];

           s -= _lower[e];

 	supply[n] = s;

         supply[n] = s;

 	sum += s;

         sum += s;

 		     const CapacityMap &_capacity,

                      const CapacityMap &_capacity,

 		     const CostMap &_cost,

                      const CostMap &_cost,

 		     const SupplyMap &_supply ) :

                      const SupplyMap &_supply ) :

       res_graph(_graph, capacity, flow),

       res_cap(_capacity), excess(_graph), pred(_graph),

       red_cost(res_graph, cost, potential), imbalance(_graph),

       dijkstra(graph, flow, res_cap, cost, excess, potential)

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

 		     const LowerMap &_lower,

                      const LowerMap &_lower,

 		     const CapacityMap &_capacity,

                      const CapacityMap &_capacity,

 		     const CostMap &_cost,

                      const CostMap &_cost,

 		     Node _s, Node _t,

                      Node _s, Node _t,

 		     Supply _flow_value ) :

                      Supply _flow_value ) :

       res_graph(_graph, capacity, flow),

       res_cap(_graph), excess(_graph), pred(_graph),

       red_cost(res_graph, cost, potential), imbalance(_graph),

       dijkstra(graph, flow, res_cap, cost, excess, potential)

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

 	Supply s = 0;

         Supply s = 0;

 	if (n == _s) s =  _flow_value;

         if (n == _s) s =  _flow_value;

 	if (n == _t) s = -_flow_value;

         if (n == _t) s = -_flow_value;

 	for (InEdgeIt e(graph, n); e != INVALID; ++e)

         for (InEdgeIt e(graph, n); e != INVALID; ++e)

 	  s += _lower[e];

           s += _lower[e];

 	for (OutEdgeIt e(graph, n); e != INVALID; ++e)

         for (OutEdgeIt e(graph, n); e != INVALID; ++e)

 	  s -= _lower[e];

           s -= _lower[e];

 	supply[n] = s;

         supply[n] = s;

 		     const CapacityMap &_capacity,

                      const CapacityMap &_capacity,

 		     const CostMap &_cost,

                      const CostMap &_cost,

 		     Node _s, Node _t,

                      Node _s, Node _t,

 		     Supply _flow_value ) :

                      Supply _flow_value ) :

       res_graph(_graph, capacity, flow),

       res_cap(_capacity), excess(_graph), pred(_graph),

       red_cost(res_graph, cost, potential), imbalance(_graph),

       dijkstra(graph, flow, res_cap, cost, excess, potential)

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

 	c += flow[e] * cost[e];

         c += flow[e] * cost[e];

     bool run() {

     bool run(int scaling_mode = WITH_SCALING) {

       return init() && start();

       return init(scaling_mode) && start();

     bool init() {

     bool init(int scaling_mode) {

       imbalance = supply;

       excess = supply;

       // Initalizing Dijkstra class

       updater.potentialMap(potential);

       dijkstra.distMap(updater).predMap(pred);

 #ifdef WITH_SCALING

       Supply max_sup = 0, max_dem = 0;

       if (scaling_mode == WITH_SCALING) {

       for (NodeIt n(graph); n != INVALID; ++n) {

         // With scaling

 	if (supply[n] >  max_sup) max_sup =  supply[n];

         Supply max_sup = 0, max_dem = 0;

 	if (supply[n] < -max_dem) max_dem = -supply[n];

         for (NodeIt n(graph); n != INVALID; ++n) {

       }

           if ( supply[n] > max_sup) max_sup =  supply[n];

       if (max_dem < max_sup) max_sup = max_dem;

           if (-supply[n] > max_dem) max_dem = -supply[n];

       for ( delta = 1; SCALING_FACTOR * delta < max_sup;

         }

 	    delta *= SCALING_FACTOR ) ;

         if (max_dem < max_sup) max_sup = max_dem;

 #endif

         phase_num = 0;

         for (delta = 1; 2 * delta <= max_sup; delta *= 2)

           ++phase_num;

       } else {

         // Without scaling

         delta = 1;

       }

 #ifdef WITH_SCALING

     /// \brief Executes the algorithm.

     bool start() {

       if (delta > 1)

         return startWithScaling();

       else

         return startWithoutScaling();

     }

     bool start() {

     bool startWithScaling() {

       typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;

       typedef typename DeltaResGraph::Edge DeltaResEdge;

 #ifdef _DEBUG_ITER_

       int dijk_num = 0;

 #endif

       ResNode s, t;

       Node s, t;

       for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ?

       int phase_cnt = 0;

 				  1 : delta / SCALING_FACTOR )

       int factor = 4;

       {

       while (true) {

 	// Saturating edges not satisfying the optimality condition

         // Saturating all edges not satisfying the optimality condition

 	Capacity r;

         for (EdgeIt e(graph); e != INVALID; ++e) {

 	for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) {

           Node u = graph.source(e), v = graph.target(e);

 	  if (red_cost[e] < 0) {

           Cost c = cost[e] - potential[u] + potential[v];

 	    res_graph.augment(e, r = res_graph.rescap(e));

           if (c < 0 && res_cap[e] >= delta) {

 	    imbalance[dres_graph.source(e)] -= r;

             excess[u] -= res_cap[e];

 	    imbalance[dres_graph.target(e)] += r;

             excess[v] += res_cap[e];

 	  }

             flow[e] = capacity[e];

 	}

             res_cap[e] = 0;

           }

 	// Finding excess nodes

           else if (c > 0 && flow[e] >= delta) {

 	excess_nodes.clear();

             excess[u] += flow[e];

 	deficit_nodes.clear();

             excess[v] -= flow[e];

 	for (ResNodeIt n(res_graph); n != INVALID; ++n) {

             flow[e] = 0;

 	  if (imbalance[n] >=  delta) excess_nodes.push_back(n);

             res_cap[e] = capacity[e];

 	  if (imbalance[n] <= -delta) deficit_nodes.push_back(n);

           }

 	}

         }

 	next_node = 0;

         // Finding excess nodes and deficit nodes

 	// Finding shortest paths

         excess_nodes.clear();

 	while (next_node < excess_nodes.size()) {

         deficit_nodes.clear();

 	  // Checking deficit nodes

         for (NodeIt n(graph); n != INVALID; ++n) {

 	  if (delta > 1) {

           if (excess[n] >=  delta) excess_nodes.push_back(n);

 	    bool delta_def = false;

           if (excess[n] <= -delta) deficit_nodes.push_back(n);

 	    for (int i = 0; i < deficit_nodes.size(); ++i) {

         }

 	      if (imbalance[deficit_nodes[i]] <= -delta) {

         next_node = 0;

 		delta_def = true;

 		break;

         // Finding augmenting shortest paths

 	      }

         while (next_node < excess_nodes.size()) {

 	    }

           // Checking deficit nodes

 	    if (!delta_def) break;

           if (delta > 1) {

 	  }

             bool delta_deficit = false;

             for (int i = 0; i < deficit_nodes.size(); ++i) {

 	  // Running Dijkstra

               if (excess[deficit_nodes[i]] <= -delta) {

 	  s = excess_nodes[next_node];

                 delta_deficit = true;

 	  updater.init();

                 break;

 	  dijkstra.init();

               }

 	  dijkstra.addSource(s);

             }

 #ifdef _DEBUG_ITER_

             if (!delta_deficit) break;

 	  ++dijk_num;

           }

 #endif

 	  if ((t = dijkstra.start(delta_deficit)) == INVALID) {

           // Running Dijkstra

 	    if (delta > 1) {

           s = excess_nodes[next_node];

 	      ++next_node;

           if ((t = dijkstra.run(s, delta)) == INVALID) {

 	      continue;

             if (delta > 1) {

 	    }

               ++next_node;

 	    return false;

               continue;

 	  }

             }

             return false;

 	  // Updating node potentials

           }

 	  updater.update();

           // Augmenting along a shortest path from s to t.

 	  // Augment along a shortest path from s to t

           Capacity d = excess[s] < -excess[t] ? excess[s] : -excess[t];

 	  Capacity d = imbalance[s] < -imbalance[t] ?

           Node u = t;

 	    imbalance[s] : -imbalance[t];

           Edge e;

 	  ResNode u = t;

           if (d > delta) {

 	  ResEdge e;

             while ((e = pred[u]) != INVALID) {

 	  if (d > delta) {

               Capacity rc;

 	    while ((e = pred[u]) != INVALID) {

               if (u == graph.target(e)) {

 	      if (res_graph.rescap(e) < d) d = res_graph.rescap(e);

                 rc = res_cap[e];

 	      u = dres_graph.source(e);

                 u = graph.source(e);

 	    }

               } else {

 	  }

                 rc = flow[e];

 	  u = t;

                 u = graph.target(e);

 	  while ((e = pred[u]) != INVALID) {

               }

 	    res_graph.augment(e, d);

               if (rc < d) d = rc;

 	    u = dres_graph.source(e);

             }

 	  }

           }

 	  imbalance[s] -= d;

           u = t;

 	  imbalance[t] += d;

           while ((e = pred[u]) != INVALID) {

 	  if (imbalance[s] < delta) ++next_node;

             if (u == graph.target(e)) {

 	}

               flow[e] += d;

       }

               res_cap[e] -= d;

 #ifdef _DEBUG_ITER_

               u = graph.source(e);

       std::cout << "Capacity Scaling algorithm finished with running Dijkstra algorithm "

             } else {

 	<< dijk_num << " times." << std::endl;

               flow[e] -= d;

 #endif

               res_cap[e] += d;

               u = graph.target(e);

             }

           }

           excess[s] -= d;

           excess[t] += d;

           if (excess[s] < delta) ++next_node;

         }

         if (delta == 1) break;

         if (++phase_cnt > phase_num / 4) factor = 2;

         delta = delta <= factor ? 1 : delta / factor;

       }

 	for (EdgeIt e(graph); e != INVALID; ++e)

         for (EdgeIt e(graph); e != INVALID; ++e)

 	  flow[e] += (*lower)[e];

           flow[e] += (*lower)[e];

     bool start() {

     bool startWithoutScaling() {

       for (ResNodeIt n(res_graph); n != INVALID; ++n) {

       for (NodeIt n(graph); n != INVALID; ++n) {

 	if (imbalance[n] > 0) excess_nodes.push_back(n);

         if (excess[n] > 0) excess_nodes.push_back(n);

       ResNode s, t;

       Node s, t;

       while ( imbalance[excess_nodes[next_node]] > 0 ||

       while ( excess[excess_nodes[next_node]] > 0 ||

 	      ++next_node < excess_nodes.size() )

               ++next_node < excess_nodes.size() )

 	// Running Dijkstra

         // Running Dijkstra

 	s = excess_nodes[next_node];

         s = excess_nodes[next_node];

 	updater.init();

         if ((t = dijkstra.run(s, 1)) == INVALID)

 	dijkstra.init();

           return false;

 	dijkstra.addSource(s);

 	if ((t = dijkstra.start(has_deficit)) == INVALID)

         // Augmenting along a shortest path from s to t

 	  return false;

         Capacity d = excess[s] < -excess[t] ? excess[s] : -excess[t];

         Node u = t;

 	// Updating node potentials

         Edge e;

 	updater.update();

         while ((e = pred[u]) != INVALID) {

           Capacity rc;

 	// Augmenting along a shortest path from s to t

           if (u == graph.target(e)) {

 	Capacity delta = imbalance[s] < -imbalance[t] ?

             rc = res_cap[e];

 	  imbalance[s] : -imbalance[t];

             u = graph.source(e);

 	ResNode u = t;

           } else {

 	ResEdge e;

             rc = flow[e];

 	while ((e = pred[u]) != INVALID) {

             u = graph.target(e);

 	  if (res_graph.rescap(e) < delta) delta = res_graph.rescap(e);

           }

 	  u = res_graph.source(e);

           if (rc < d) d = rc;

 	}

         }

 	u = t;

         u = t;

 	while ((e = pred[u]) != INVALID) {

         while ((e = pred[u]) != INVALID) {

 	  res_graph.augment(e, delta);

           if (u == graph.target(e)) {

 	  u = res_graph.source(e);

             flow[e] += d;

 	}

             res_cap[e] -= d;

 	imbalance[s] -= delta;

             u = graph.source(e);

 	imbalance[t] += delta;

           } else {

             flow[e] -= d;

             res_cap[e] += d;

             u = graph.target(e);

           }

         }

         excess[s] -= d;

         excess[t] += d;

 	for (EdgeIt e(graph); e != INVALID; ++e)

         for (EdgeIt e(graph); e != INVALID; ++e)

 	  flow[e] += (*lower)[e];

           flow[e] += (*lower)[e];