RhodeCode

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_GOMORY_HU_TREE_H

#define LEMON_GOMORY_HU_TREE_H

#include <limits>

#include <lemon/core.h>

#include <lemon/preflow.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

/// \ingroup min_cut

/// \file 

/// \brief Gomory-Hu cut tree in graphs.

namespace lemon {

  /// \ingroup min_cut

  ///

  /// \brief Gomory-Hu cut tree algorithm

  ///

  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it

  /// may contain edges which are not in the original graph. It has the

  /// property that the minimum capacity edge of the path between two nodes 

  /// in this tree has the same weight as the minimum cut in the graph

  /// between these nodes. Moreover the components obtained by removing

  /// this edge from the tree determine the corresponding minimum cut.

  /// Therefore once this tree is computed, the minimum cut between any pair

  /// of nodes can easily be obtained.

  /// 

  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with

  /// the minimum cut and the minimum cut value between any two nodes

  /// in the graph. You can also list (iterate on) the nodes and the

  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.

  ///

  /// \tparam GR The type of the undirected graph the algorithm runs on.

#ifdef DOXYGEN

  template <typename GR,

	    typename CAP>

#else

  template <typename GR,

	    typename CAP = typename GR::template EdgeMap<int> >

#endif

  class GomoryHu {

  public:

    typedef GR Graph;

    typedef CAP Capacity;

    /// The value type of capacities

    typedef typename Capacity::Value Value;

  private:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    const Graph& _graph;

    const Capacity& _capacity;

    Node _root;

    typename Graph::template NodeMap<Node>* _pred;

    typename Graph::template NodeMap<Value>* _weight;

    typename Graph::template NodeMap<int>* _order;

    void createStructures() {

      if (!_pred) {

	_pred = new typename Graph::template NodeMap<Node>(_graph);

      }

      if (!_weight) {

	_weight = new typename Graph::template NodeMap<Value>(_graph);

      }

      if (!_order) {

	_order = new typename Graph::template NodeMap<int>(_graph);

      }

    }

    void destroyStructures() {

      if (_pred) {

	delete _pred;

      }

      if (_weight) {

	delete _weight;

      }

      if (_order) {

	delete _order;

      }

    }

  public:

    /// \brief Constructor

    ///

    /// \param graph The undirected graph the algorithm runs on.

    /// \param capacity The edge capacity map.

    GomoryHu(const Graph& graph, const Capacity& capacity) 

      : _graph(graph), _capacity(capacity),

	_pred(0), _weight(0), _order(0) 

    {

      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();

    }

    /// \brief Destructor

    ///

    ~GomoryHu() {

      destroyStructures();

    }

  private:

    // Initialize the internal data structures

    void init() {

      createStructures();

      _root = NodeIt(_graph);

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

        (*_pred)[n] = _root;

        (*_order)[n] = -1;

      }

      (*_pred)[_root] = INVALID;

      (*_weight)[_root] = std::numeric_limits<Value>::max(); 

    }

    // Start the algorithm

    void start() {

      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);

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

	if (n == _root) continue;

	Node pn = (*_pred)[n];

	fa.source(n);

	fa.target(pn);

	fa.runMinCut();

	(*_weight)[n] = fa.flowValue();

	for (NodeIt nn(_graph); nn != INVALID; ++nn) {

	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {

	    (*_pred)[nn] = n;

	  }

	}

	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {

	  (*_pred)[n] = (*_pred)[pn];

	  (*_pred)[pn] = n;

	  (*_weight)[n] = (*_weight)[pn];

	  (*_weight)[pn] = fa.flowValue();

	}

      }

      (*_order)[_root] = 0;

      int index = 1;

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

	std::vector<Node> st;

	Node nn = n;

	while ((*_order)[nn] == -1) {

	  st.push_back(nn);

	  nn = (*_pred)[nn];

	}

	while (!st.empty()) {

	  (*_order)[st.back()] = index++;

	  st.pop_back();

	}

      }

    }

  public:

    ///\name Execution Control

    ///@{

    /// \brief Run the Gomory-Hu algorithm.

    ///

    /// This function runs the Gomory-Hu algorithm.

    void run() {

      init();

      start();

    }

    /// @}

    ///\name Query Functions

    ///The results of the algorithm can be obtained using these

    ///functions.\n

    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.

    ///@{

    /// \brief Return the predecessor node in the Gomory-Hu tree.

    ///

      return (*_pred)[node];

    }

    /// \brief Return the weight of the predecessor edge in the

    /// Gomory-Hu tree.

    ///

      return (*_weight)[node];

    }

    /// \brief Return the minimum cut value between two nodes

    ///

    Value minCutValue(const Node& s, const Node& t) const {

      Node sn = s, tn = t;

      Value value = std::numeric_limits<Value>::max();

      while (sn != tn) {

	if ((*_order)[sn] < (*_order)[tn]) {

	  if ((*_weight)[tn] <= value) value = (*_weight)[tn];

	  tn = (*_pred)[tn];

	} else {

	  if ((*_weight)[sn] <= value) value = (*_weight)[sn];

	  sn = (*_pred)[sn];

	}

      }

      return value;

    }

    /// \brief Return the minimum cut between two nodes

    ///

    /// This function returns the minimum cut between the nodes \c s and \c t

    /// in the \c cutMap parameter by setting the nodes in the component of

    /// \c s to \c true and the other nodes to \c false.

    ///

    template <typename CutMap>

                    const Node& t,

                    CutMap& cutMap

                    ) const {

      Node sn = s, tn = t;

      bool s_root=false;

      Node rn = INVALID;

      Value value = std::numeric_limits<Value>::max();

      while (sn != tn) {

	if ((*_order)[sn] < (*_order)[tn]) {

	  if ((*_weight)[tn] <= value) {

	    rn = tn;

            s_root = false;

	    value = (*_weight)[tn];

	  }

	  tn = (*_pred)[tn];

	} else {

	  if ((*_weight)[sn] <= value) {

	    rn = sn;

            s_root = true;

	    value = (*_weight)[sn];

	  }

	  sn = (*_pred)[sn];

	}

      }

      typename Graph::template NodeMap<bool> reached(_graph, false);

      reached[_root] = true;

      cutMap.set(_root, !s_root);

      reached[rn] = true;

      cutMap.set(rn, s_root);

      std::vector<Node> st;

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

	st.clear();

        Node nn = n;

	while (!reached[nn]) {

	  st.push_back(nn);

	  nn = (*_pred)[nn];

	}

	while (!st.empty()) {

	  cutMap.set(st.back(), cutMap[nn]);

	  st.pop_back();

	}

      }

      return value;

    }

    ///@}

    friend class MinCutNodeIt;

    /// Iterate on the nodes of a minimum cut

    /// This iterator class lists the nodes of a minimum cut found by

    /// and call its \ref GomoryHu::run() "run()" method.

    ///

    /// This example counts the nodes in the minimum cut separating \c s from

    /// \c t.

    /// \code

    /// GomoruHu<Graph> gom(g, capacities);

    /// gom.run();

    /// int cnt=0;

    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;

    /// \endcode

    class MinCutNodeIt

    {

      bool _side;

      typename Graph::NodeIt _node_it;

      typename Graph::template NodeMap<bool> _cut;

    public:

      /// Constructor

      /// Constructor.

      ///

      MinCutNodeIt(GomoryHu const &gomory,

                   ///< The GomoryHu class. You must call its

                   ///  run() method

                   ///  before initializing this iterator.

                   const Node& s, ///< The base node.

                   const Node& t,

                   ///< The node you want to separate from node \c s.

                   bool side=true

                   ///< If it is \c true (default) then the iterator lists

                   ///  the nodes of the component containing \c s,

                   ///  otherwise it lists the other component.

                   /// \note As the minimum cut is not always unique,

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

                   /// \endcode

                   /// and

                   /// \code

                   /// MinCutNodeIt(gomory, t, s, false);

                   /// \endcode

                   /// does not necessarily give the same set of nodes.

                   /// However it is ensured that

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

                   /// \endcode

                   /// and

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, false);

                   /// \endcode

                   /// together list each node exactly once.

                   )

        : _side(side), _cut(gomory._graph)

      {

        gomory.minCutMap(s,t,_cut);

        for(_node_it=typename Graph::NodeIt(gomory._graph);

            _node_it!=INVALID && _cut[_node_it]!=_side;

            ++_node_it) {}

      }

      /// Conversion to \c Node

      /// Conversion to \c Node.

      ///

      operator typename Graph::Node() const

      {

        return _node_it;

      }

      bool operator==(Invalid) { return _node_it==INVALID; }

      bool operator!=(Invalid) { return _node_it!=INVALID; }

      /// Next node

      /// Next node.

      ///

      MinCutNodeIt &operator++()

      {

        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}

        return *this;

      }

      /// Postfix incrementation

      /// Postfix incrementation.

      ///

      /// \warning This incrementation

      /// returns a \c Node, not a \c MinCutNodeIt, as one may

      /// expect.

      typename Graph::Node operator++(int)

      {

        typename Graph::Node n=*this;

        ++(*this);

        return n;

      }

    };

    friend class MinCutEdgeIt;

    /// Iterate on the edges of a minimum cut

    /// This iterator class lists the edges of a minimum cut found by

    /// and call its \ref GomoryHu::run() "run()" method.

    ///

    /// This example computes the value of the minimum cut separating \c s from

    /// \c t.

    /// \code

    /// GomoruHu<Graph> gom(g, capacities);

    /// gom.run();

    /// int value=0;

    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)

    ///   value+=capacities[e];

    /// \endcode

    class MinCutEdgeIt

    {

      bool _side;

      const Graph &_graph;

      typename Graph::NodeIt _node_it;

      typename Graph::OutArcIt _arc_it;

      typename Graph::template NodeMap<bool> _cut;

      void step()

      {

        ++_arc_it;

        while(_node_it!=INVALID && _arc_it==INVALID)

          {

            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}

            if(_node_it!=INVALID)

              _arc_it=typename Graph::OutArcIt(_graph,_node_it);

          }

      }

    public:

      MinCutEdgeIt(GomoryHu const &gomory,

                   ///< The GomoryHu class. You must call its

                   ///  run() method

                   ///  before initializing this iterator.

                   const Node& s,  ///< The base node.

                   const Node& t,

                   ///< The node you want to separate from node \c s.

                   bool side=true

                   ///< If it is \c true (default) then the listed arcs

                   ///  will be oriented from the

                   ///  otherwise they will be oriented in the opposite

                   ///  direction.

                   )

        : _graph(gomory._graph), _cut(_graph)

      {

        gomory.minCutMap(s,t,_cut);

        if(!side)

          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)

            _cut[n]=!_cut[n];

        for(_node_it=typename Graph::NodeIt(_graph);

            _node_it!=INVALID && !_cut[_node_it];

            ++_node_it) {}

        _arc_it = _node_it!=INVALID ?

          typename Graph::OutArcIt(_graph,_node_it) : INVALID;

        while(_node_it!=INVALID && _arc_it == INVALID)

          {

            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}

            if(_node_it!=INVALID)

              _arc_it= typename Graph::OutArcIt(_graph,_node_it);

          }

        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();

      }

      /// Conversion to \c Arc

      /// Conversion to \c Arc.

      ///

      operator typename Graph::Arc() const

      {

        return _arc_it;

      }

      /// Conversion to \c Edge

      /// Conversion to \c Edge.

      ///

      operator typename Graph::Edge() const

      {

        return _arc_it;

      }

      bool operator==(Invalid) { return _node_it==INVALID; }

      bool operator!=(Invalid) { return _node_it!=INVALID; }

      /// Next edge

      /// Next edge.

      ///

      MinCutEdgeIt &operator++()

      {

        step();

        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();

        return *this;

      }

      /// Postfix incrementation

      /// Postfix incrementation.

      ///

      /// \warning This incrementation

      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.

      typename Graph::Arc operator++(int)

      {

        typename Graph::Arc e=*this;

        ++(*this);

        return e;

      }

    };

  };

}

#endif

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_HAO_ORLIN_H

#define LEMON_HAO_ORLIN_H

#include <vector>

#include <list>

#include <limits>

#include <lemon/maps.h>

#include <lemon/core.h>

#include <lemon/tolerance.h>

/// \file

/// \ingroup min_cut

/// \brief Implementation of the Hao-Orlin algorithm.

///

namespace lemon {

  /// \ingroup min_cut

  ///

  ///

  /// consists of two phases: in the first phase it determines a

  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set

  /// with \f$ source \f$ on the sink-side (i.e. a set

  /// minimum cut of \f$ D \f$. The algorithm is a modified

  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the

  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The

  ///

  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".

#ifdef DOXYGEN

  template <typename GR, typename CAP, typename TOL>

#else

  template <typename GR,

            typename CAP = typename GR::template ArcMap<int>,

            typename TOL = Tolerance<typename CAP::Value> >

#endif

  class HaoOrlin {

  private:

    typedef typename CapacityMap::Value Value;

    const Digraph& _graph;

    const CapacityMap* _capacity;

    typedef typename Digraph::template ArcMap<Value> FlowMap;

    FlowMap* _flow;

    Node _source;

    int _node_num;

    // Bucketing structure

    std::vector<Node> _first, _last;

    typename Digraph::template NodeMap<Node>* _next;

    typename Digraph::template NodeMap<Node>* _prev;

    typename Digraph::template NodeMap<bool>* _active;

    typename Digraph::template NodeMap<int>* _bucket;

    std::vector<bool> _dormant;

    std::list<std::list<int> > _sets;

    std::list<int>::iterator _highest;

    typedef typename Digraph::template NodeMap<Value> ExcessMap;

    ExcessMap* _excess;

    typedef typename Digraph::template NodeMap<bool> SourceSetMap;

    SourceSetMap* _source_set;

    Value _min_cut;

    typedef typename Digraph::template NodeMap<bool> MinCutMap;

    MinCutMap* _min_cut_map;

    Tolerance _tolerance;

  public:

    /// \brief Constructor

    ///

    /// Constructor of the algorithm class.

    HaoOrlin(const Digraph& graph, const CapacityMap& capacity,

             const Tolerance& tolerance = Tolerance()) :

      _graph(graph), _capacity(&capacity), _flow(0), _source(),

      _node_num(), _first(), _last(), _next(0), _prev(0),

      _active(0), _bucket(0), _dormant(), _sets(), _highest(),

      _excess(0), _source_set(0), _min_cut(), _min_cut_map(0),

      _tolerance(tolerance) {}

    ~HaoOrlin() {

      if (_min_cut_map) {

        delete _min_cut_map;

      }

      if (_source_set) {

        delete _source_set;

      }

      if (_excess) {

        delete _excess;

      }

      if (_next) {

        delete _next;

      }

      if (_prev) {

        delete _prev;

      }

      if (_active) {

        delete _active;

      }

      if (_bucket) {

        delete _bucket;

      }

      if (_flow) {

        delete _flow;

      }

    }

  private:

    void activate(const Node& i) {

      (*_active)[i] = true;

      int bucket = (*_bucket)[i];

      if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;

      //unlace

      (*_next)[(*_prev)[i]] = (*_next)[i];

      if ((*_next)[i] != INVALID) {

        (*_prev)[(*_next)[i]] = (*_prev)[i];

      } else {

        _last[bucket] = (*_prev)[i];

      }

      //lace

      (*_next)[i] = _first[bucket];

      (*_prev)[_first[bucket]] = i;

      (*_prev)[i] = INVALID;

      _first[bucket] = i;

    }

    void deactivate(const Node& i) {

      (*_active)[i] = false;

      int bucket = (*_bucket)[i];

      if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return;

      //unlace

      (*_prev)[(*_next)[i]] = (*_prev)[i];

      if ((*_prev)[i] != INVALID) {

        (*_next)[(*_prev)[i]] = (*_next)[i];

      } else {

        _first[bucket] = (*_next)[i];

      }

      //lace

      (*_prev)[i] = _last[bucket];

      (*_next)[_last[bucket]] = i;

      (*_next)[i] = INVALID;

      _last[bucket] = i;

    }

    void addItem(const Node& i, int bucket) {

      (*_bucket)[i] = bucket;

      if (_last[bucket] != INVALID) {

        (*_prev)[i] = _last[bucket];

        (*_next)[_last[bucket]] = i;

        (*_next)[i] = INVALID;

        _last[bucket] = i;

      } else {

        (*_prev)[i] = INVALID;

        _first[bucket] = i;

        (*_next)[i] = INVALID;

        _last[bucket] = i;

      }

    }

    void findMinCutOut() {

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

        (*_excess)[n] = 0;

      }

      for (ArcIt a(_graph); a != INVALID; ++a) {

        (*_flow)[a] = 0;

      }

      int bucket_num = 0;

      std::vector<Node> queue(_node_num);

      int qfirst = 0, qlast = 0, qsep = 0;

      {

        typename Digraph::template NodeMap<bool> reached(_graph, false);

        reached[_source] = true;

        bool first_set = true;

        for (NodeIt t(_graph); t != INVALID; ++t) {

          if (reached[t]) continue;

          _sets.push_front(std::list<int>());

          queue[qlast++] = t;

          reached[t] = true;

          while (qfirst != qlast) {

            if (qsep == qfirst) {

              ++bucket_num;

              _sets.front().push_front(bucket_num);

              _dormant[bucket_num] = !first_set;

              _first[bucket_num] = _last[bucket_num] = INVALID;

              qsep = qlast;

            }

            Node n = queue[qfirst++];

            addItem(n, bucket_num);

            for (InArcIt a(_graph, n); a != INVALID; ++a) {

              Node u = _graph.source(a);

              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {

                reached[u] = true;

                queue[qlast++] = u;

              }

            }

          }

          first_set = false;

        }

        ++bucket_num;

        (*_bucket)[_source] = 0;

        _dormant[0] = true;

      }

      (*_source_set)[_source] = true;

      Node target = _last[_sets.back().back()];

      {

        for (OutArcIt a(_graph, _source); a != INVALID; ++a) {

          if (_tolerance.positive((*_capacity)[a])) {

            Node u = _graph.target(a);

            (*_flow)[a] = (*_capacity)[a];

            (*_excess)[u] += (*_capacity)[a];

            if (!(*_active)[u] && u != _source) {

              activate(u);

            }

          }

        }

        if ((*_active)[target]) {

          deactivate(target);

        }

        _highest = _sets.back().begin();

        while (_highest != _sets.back().end() &&

               !(*_active)[_first[*_highest]]) {

          ++_highest;

        }

      }

      while (true) {

        while (_highest != _sets.back().end()) {

          Node n = _first[*_highest];

          Value excess = (*_excess)[n];

          int next_bucket = _node_num;

          int under_bucket;

          if (++std::list<int>::iterator(_highest) == _sets.back().end()) {

            under_bucket = -1;

          } else {

            under_bucket = *(++std::list<int>::iterator(_highest));

          }

          for (OutArcIt a(_graph, n); a != INVALID; ++a) {

            Node v = _graph.target(a);

            if (_dormant[(*_bucket)[v]]) continue;

            Value rem = (*_capacity)[a] - (*_flow)[a];

            if (!_tolerance.positive(rem)) continue;

            if ((*_bucket)[v] == under_bucket) {

              if (!(*_active)[v] && v != target) {

                activate(v);

              }

              if (!_tolerance.less(rem, excess)) {

                (*_flow)[a] += excess;

                (*_excess)[v] += excess;

                excess = 0;

                goto no_more_push;

              } else {

                excess -= rem;

                (*_excess)[v] += rem;

                (*_flow)[a] = (*_capacity)[a];

              }

            } else if (next_bucket > (*_bucket)[v]) {

              next_bucket = (*_bucket)[v];

            }

          }

          for (InArcIt a(_graph, n); a != INVALID; ++a) {

            Node v = _graph.source(a);

            if (_dormant[(*_bucket)[v]]) continue;

            Value rem = (*_flow)[a];

            if (!_tolerance.positive(rem)) continue;

            if ((*_bucket)[v] == under_bucket) {

              if (!(*_active)[v] && v != target) {

                activate(v);

              }

              if (!_tolerance.less(rem, excess)) {

                (*_flow)[a] -= excess;

                (*_excess)[v] += excess;

                excess = 0;

                goto no_more_push;

              } else {

                excess -= rem;

                (*_excess)[v] += rem;

                (*_flow)[a] = 0;

              }

            } else if (next_bucket > (*_bucket)[v]) {

              next_bucket = (*_bucket)[v];

            }

          }

        no_more_push:

          (*_excess)[n] = excess;

          if (excess != 0) {

            if ((*_next)[n] == INVALID) {

              typename std::list<std::list<int> >::iterator new_set =

                _sets.insert(--_sets.end(), std::list<int>());

              new_set->splice(new_set->end(), _sets.back(),

                              _sets.back().begin(), ++_highest);

              for (std::list<int>::iterator it = new_set->begin();

                   it != new_set->end(); ++it) {

                _dormant[*it] = true;

              }

              while (_highest != _sets.back().end() &&

                     !(*_active)[_first[*_highest]]) {

                ++_highest;

              }

            } else if (next_bucket == _node_num) {

              _first[(*_bucket)[n]] = (*_next)[n];

              (*_prev)[(*_next)[n]] = INVALID;

              std::list<std::list<int> >::iterator new_set =

                _sets.insert(--_sets.end(), std::list<int>());

              new_set->push_front(bucket_num);

              (*_bucket)[n] = bucket_num;

              _first[bucket_num] = _last[bucket_num] = n;

              (*_next)[n] = INVALID;

              (*_prev)[n] = INVALID;

              _dormant[bucket_num] = true;

              ++bucket_num;

              while (_highest != _sets.back().end() &&

                     !(*_active)[_first[*_highest]]) {

                ++_highest;

              }

            } else {

              _first[*_highest] = (*_next)[n];

              (*_prev)[(*_next)[n]] = INVALID;

              while (next_bucket != *_highest) {

                --_highest;

              }

              if (_highest == _sets.back().begin()) {

                _sets.back().push_front(bucket_num);

                _dormant[bucket_num] = false;

                _first[bucket_num] = _last[bucket_num] = INVALID;

                ++bucket_num;

              }

              --_highest;

              (*_bucket)[n] = *_highest;

              (*_next)[n] = _first[*_highest];

              if (_first[*_highest] != INVALID) {

                (*_prev)[_first[*_highest]] = n;

              } else {

                _last[*_highest] = n;

              }

              _first[*_highest] = n;

            }

          } else {

            deactivate(n);

            if (!(*_active)[_first[*_highest]]) {

              ++_highest;

              if (_highest != _sets.back().end() &&

                  !(*_active)[_first[*_highest]]) {

                _highest = _sets.back().end();

              }

            }

          }

        }

        if ((*_excess)[target] < _min_cut) {

          _min_cut = (*_excess)[target];

          for (NodeIt i(_graph); i != INVALID; ++i) {

            (*_min_cut_map)[i] = true;

          }

          for (std::list<int>::iterator it = _sets.back().begin();

               it != _sets.back().end(); ++it) {

            Node n = _first[*it];

            while (n != INVALID) {

              (*_min_cut_map)[n] = false;

              n = (*_next)[n];

            }

          }

        }

        {

          Node new_target;

          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {

            if ((*_next)[target] == INVALID) {

              _last[(*_bucket)[target]] = (*_prev)[target];

              new_target = (*_prev)[target];

            } else {

              (*_prev)[(*_next)[target]] = (*_prev)[target];

              new_target = (*_next)[target];

            }

            if ((*_prev)[target] == INVALID) {

              _first[(*_bucket)[target]] = (*_next)[target];