RhodeCode

#else

  template <typename GR,

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

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

#endif

  class HaoOrlin {

  public:

    /// The digraph type of the algorithm

    typedef GR Digraph;

    /// The capacity map type of the algorithm

    typedef CAP CapacityMap;

    /// The tolerance type of the algorithm

    typedef TOL Tolerance;

  private:

    typedef typename CapacityMap::Value Value;

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    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;

        (*_source_set)[n] = false;

      }

      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);