/* -*- C++ -*-

 * lemon/hao_orlin.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2005 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 <queue>

#include <limits>

#include <lemon/maps.h>

#include <lemon/graph_utils.h>

#include <lemon/graph_adaptor.h>

#include <lemon/iterable_maps.h>

/// \file

/// \ingroup flowalgs

/// Implementation of the Hao-Orlin algorithms class for testing network 

/// reliability.

namespace lemon {

  /// \addtogroup flowalgs

  /// @{                                                   

  /// %Hao-Orlin algorithm for calculate minimum cut in directed graphs.

  ///

  /// Hao-Orlin calculates the minimum cut in directed graphs. It

  /// separates the nodes of the graph into two disjoint sets and the

  /// summary of the edge capacities go from the first set to the

  /// second set is the minimum.  The algorithm is a modified

  /// push-relabel preflow algorithm and it calculates the minimum cat

  /// in \f$ O(n^3) \f$ time. The purpose of such algorithm is testing

  /// network reliability. For sparse undirected graph you can use the

  /// algorithm of Nagamochi and Ibraki which solves the undirected

  /// problem in \f$ O(n^3) \f$ time. 

  ///

  /// \author Attila Bernath and Balazs Dezso

  template <typename _Graph,

	    typename _CapacityMap = typename _Graph::template EdgeMap<int>,

            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >

  class HaoOrlin {

  protected:

    typedef _Graph Graph;

    typedef _CapacityMap CapacityMap;

    typedef _Tolerance Tolerance;

    typedef typename CapacityMap::Value Value;

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::EdgeIt EdgeIt;

    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef typename Graph::InEdgeIt InEdgeIt;

    const Graph* _graph;

    const CapacityMap* _capacity;

    typedef typename Graph::template EdgeMap<Value> FlowMap;

    FlowMap* _preflow;

    Node _source, _target;

    int _node_num;

    typedef ResGraphAdaptor<const Graph, Value, CapacityMap, 

                            FlowMap, Tolerance> ResGraph;

    typedef typename ResGraph::Node ResNode;

    typedef typename ResGraph::NodeIt ResNodeIt;

    typedef typename ResGraph::EdgeIt ResEdgeIt;

    typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;

    typedef typename ResGraph::Edge ResEdge;

    typedef typename ResGraph::InEdgeIt ResInEdgeIt;

    ResGraph* _res_graph;

    typedef typename Graph::template NodeMap<ResEdge> CurrentArcMap;

    CurrentArcMap* _current_arc;  

    typedef IterableBoolMap<Graph, Node> WakeMap;

    WakeMap* _wake;

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

    DistMap* _dist;  

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

    ExcessMap* _excess;

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

    SourceSetMap* _source_set;

    std::vector<int> _level_size;

    int _highest_active;

    std::vector<std::list<Node> > _active_nodes;

    int _dormant_max;

    std::vector<std::list<Node> > _dormant;

    Value _min_cut;

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

    MinCutMap* _min_cut_map;

    Tolerance _tolerance;

  public: 

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

             const Tolerance& tolerance = Tolerance()) :

      _graph(&graph), _capacity(&capacity), 

      _preflow(0), _source(), _target(), _res_graph(0), _current_arc(0),

      _wake(0),_dist(0), _excess(0), _source_set(0), 

      _highest_active(), _active_nodes(), _dormant_max(), _dormant(), 

      _min_cut(), _min_cut_map(0), _tolerance(tolerance) {}

    ~HaoOrlin() {

      if (_res_graph) {

        delete _res_graph;

      }

      if (_min_cut_map) {

        delete _min_cut_map;

      } 

      if (_current_arc) {

        delete _current_arc;

      }

      if (_source_set) {

        delete _source_set;

      }

      if (_excess) {

        delete _excess;

      }

      if (_dist) {

        delete _dist;

      }

      if (_wake) {

        delete _wake;

      }

      if (_preflow) {

        delete _preflow;

      }

    }

  private:

    void relabel(Node i) {

      int k = (*_dist)[i];

      if (_level_size[k] == 1) {

	++_dormant_max;

	for (NodeIt it(*_graph); it != INVALID; ++it) {

	  if ((*_wake)[it] && (*_dist)[it] >= k) {

	    (*_wake)[it] = false;

	    _dormant[_dormant_max].push_front(it);

	    --_level_size[(*_dist)[it]];

	  }

	}

	--_highest_active;

      } else {

	ResOutEdgeIt e(*_res_graph, i);

	while (e != INVALID && !(*_wake)[_res_graph->target(e)]) {

	  ++e;

	}

	if (e == INVALID){

	  ++_dormant_max;

	  (*_wake)[i] = false;

	  _dormant[_dormant_max].push_front(i);

	  --_level_size[(*_dist)[i]];

	} else{	    

	  Node j = _res_graph->target(e);

	  int new_dist = (*_dist)[j];

	  ++e;

	  while (e != INVALID){

	    Node j = _res_graph->target(e);

	    if ((*_wake)[j] && new_dist > (*_dist)[j]) {

	      new_dist = (*_dist)[j];

            }

	    ++e;

	  }

	  --_level_size[(*_dist)[i]];

	  (*_dist)[i] = new_dist + 1;

	  _highest_active = (*_dist)[i];

	  _active_nodes[_highest_active].push_front(i);

	  ++_level_size[(*_dist)[i]];

	  _res_graph->firstOut((*_current_arc)[i], i);

	}

      }

    }

    bool selectNewSink(){

      Node old_target = _target;

      (*_wake)[_target] = false;

      --_level_size[(*_dist)[_target]];

      _dormant[0].push_front(_target);

      (*_source_set)[_target] = true;

      if ((int)_dormant[0].size() == _node_num){

        _dormant[0].clear();

	return false;

      }

      bool wake_was_empty = false;

      if(_wake->trueNum() == 0) {

	while (!_dormant[_dormant_max].empty()){

	  (*_wake)[_dormant[_dormant_max].front()] = true;

	  ++_level_size[(*_dist)[_dormant[_dormant_max].front()]];

	  _dormant[_dormant_max].pop_front();

	}

	--_dormant_max;

	wake_was_empty = true;

      }

      int min_dist = std::numeric_limits<int>::max();

      for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {

	if (min_dist > (*_dist)[it]){

	  _target = it;

	  min_dist = (*_dist)[it];

	}

      }

      if (wake_was_empty){

	for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {

          if (_tolerance.positive((*_excess)[it])) {

	    if ((*_wake)[it] && it != _target) {

	      _active_nodes[(*_dist)[it]].push_front(it);

            }

	    if (_highest_active < (*_dist)[it]) {

	      _highest_active = (*_dist)[it];		    

            }

	  }

	}

      }

      for (ResOutEdgeIt e(*_res_graph, old_target); e!=INVALID; ++e){

	if (!(*_source_set)[_res_graph->target(e)]){

	  push(e, _res_graph->rescap(e));

	}

      }

      return true;

    }

    Node findActiveNode() {

      while (_highest_active > 0 && _active_nodes[_highest_active].empty()){ 

	--_highest_active;

      }

      if( _highest_active > 0) {

       	Node n = _active_nodes[_highest_active].front();

	_active_nodes[_highest_active].pop_front();

	return n;

      } else {

	return INVALID;

      }

    }

    ResEdge findAdmissibleEdge(const Node& n){

      ResEdge e = (*_current_arc)[n];

      while (e != INVALID && 

             ((*_dist)[n] <= (*_dist)[_res_graph->target(e)] || 

              !(*_wake)[_res_graph->target(e)])) {

	_res_graph->nextOut(e);

      }

      if (e != INVALID) {

	(*_current_arc)[n] = e;	

	return e;

      } else {

	return INVALID;

      }

    }

    void push(ResEdge& e,const Value& delta){

      _res_graph->augment(e, delta);

      if (!_tolerance.positive(delta)) return;

      (*_excess)[_res_graph->source(e)] -= delta;

      Node a = _res_graph->target(e);

      if (!_tolerance.positive((*_excess)[a]) && (*_wake)[a] && a != _target) {

	_active_nodes[(*_dist)[a]].push_front(a);

	if (_highest_active < (*_dist)[a]) {

	  _highest_active = (*_dist)[a];

        }

      }

      (*_excess)[a] += delta;

    }

    Value cutValue() {

      Value value = 0;

      for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {

	for (InEdgeIt e(*_graph, it); e != INVALID; ++e) {

	  if (!(*_wake)[_graph->source(e)]){

	    value += (*_capacity)[e];

	  }	

	}

      }

      return value;

    }    

  public:

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures. It creates

    /// the maps, residual graph adaptor and some bucket structures

    /// for the algorithm. 

    void init() {

      init(NodeIt(*_graph));

    }

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures. It creates

    /// the maps, residual graph adaptor and some bucket structures

    /// for the algorithm. The \c source node is used as the push-relabel

    /// algorithm's source.

    void init(const Node& source) {

      _source = source;

      _node_num = countNodes(*_graph);

      _dormant.resize(_node_num);

      _level_size.resize(_node_num, 0);

      _active_nodes.resize(_node_num);

      if (!_preflow) {

        _preflow = new FlowMap(*_graph);

      }

      if (!_wake) {

        _wake = new WakeMap(*_graph);

      }

      if (!_dist) {

        _dist = new DistMap(*_graph);

      }

      if (!_excess) {

        _excess = new ExcessMap(*_graph);

      }

      if (!_source_set) {

        _source_set = new SourceSetMap(*_graph);

      }

      if (!_current_arc) {

        _current_arc = new CurrentArcMap(*_graph);

      }

      if (!_min_cut_map) {

        _min_cut_map = new MinCutMap(*_graph);

      }

      if (!_res_graph) {

        _res_graph = new ResGraph(*_graph, *_capacity, *_preflow);

      }

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

    }

    /// \brief Calculates the minimum cut with the \c source node

    /// in the first partition.

    ///

    /// Calculates the minimum cut with the \c source node

    /// in the first partition.

    void calculateOut() {

      for (NodeIt it(*_graph); it != INVALID; ++it) {

        if (it != _source) {

          calculateOut(it);

          return;

        }

      }

    }

    /// \brief Calculates the minimum cut with the \c source node

    /// in the first partition.

    ///

    /// Calculates the minimum cut with the \c source node

    /// in the first partition. The \c target is the initial target

    /// for the push-relabel algorithm.

    void calculateOut(const Node& target) {

      for (NodeIt it(*_graph); it != INVALID; ++it) {

        (*_wake)[it] = true;

        (*_dist)[it] = 1;

        (*_excess)[it] = 0;

        (*_source_set)[it] = false;

        _res_graph->firstOut((*_current_arc)[it], it);

      }

      _target = target;

      (*_dist)[target] = 0;

      for (ResOutEdgeIt it(*_res_graph, _source); it != INVALID; ++it) {

	push(it, _res_graph->rescap(it));

      }

      _dormant[0].push_front(_source);

      (*_source_set)[_source] = true;

      _dormant_max = 0;

      (*_wake)[_source]=false;

      _level_size[0] = 1;

      _level_size[1] = _node_num - 1;

      do {

	Node n;

	while ((n = findActiveNode()) != INVALID) {

	  ResEdge e;

	  while (_tolerance.positive((*_excess)[n]) && 

                 (e = findAdmissibleEdge(n)) != INVALID){

	    Value delta;

	    if ((*_excess)[n] < _res_graph->rescap(e)) {

	      delta = (*_excess)[n];

	    } else {

	      delta = _res_graph->rescap(e);

	      _res_graph->nextOut((*_current_arc)[n]);

	    }

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

	    _res_graph->augment(e, delta);

	    (*_excess)[_res_graph->source(e)] -= delta;

	    Node a = _res_graph->target(e);

	    if (!_tolerance.positive((*_excess)[a]) && a != _target) {

	      _active_nodes[(*_dist)[a]].push_front(a);

	    }

	    (*_excess)[a] += delta;

	  }

	  if (_tolerance.positive((*_excess)[n])) {

	    relabel(n);

          }

	}

	Value current_value = cutValue();

 	if (_min_cut > current_value){

	  for (NodeIt it(*_graph); it != INVALID; ++it) {

            _min_cut_map->set(it, !(*_wake)[it]);

	  }

	  _min_cut = current_value;

 	}

      } while (selectNewSink());

    }

    void calculateIn() {

      for (NodeIt it(*_graph); it != INVALID; ++it) {

        if (it != _source) {

          calculateIn(it);

          return;

        }

      }

    }

    void run() {

      init();

      for (NodeIt it(*_graph); it != INVALID; ++it) {

        if (it != _source) {

          startOut(it);

          //          startIn(it);

          return;

        }

      }

    }

    void run(const Node& s) {

      init(s);

      for (NodeIt it(*_graph); it != INVALID; ++it) {

        if (it != _source) {

          startOut(it);

          //          startIn(it);

          return;

        }

      }

    }

    void run(const Node& s, const Node& t) {

      init(s);

      startOut(t);

      startIn(t);

    }

    /// \brief Returns the value of the minimum value cut with node \c

    /// source on the source side.

    /// 

    /// Returns the value of the minimum value cut with node \c source

    /// on the source side. This function can be called after running

    /// \ref findMinCut.

    Value minCut() const {

      return _min_cut;

    }

    /// \brief Returns a minimum value cut.

    ///

    /// Sets \c nodeMap to the characteristic vector of a minimum

    /// value cut with node \c source on the source side. This

    /// function can be called after running \ref findMinCut.  

    /// \pre nodeMap should be a bool-valued node-map.

    template <typename NodeMap>

    Value minCut(NodeMap& nodeMap) const {

      for (NodeIt it(*_graph); it != INVALID; ++it) {

	nodeMap.set(it, (*_min_cut_map)[it]);

      }

      return minCut();

    }

  }; //class HaoOrlin 

} //namespace lemon

#endif //LEMON_HAO_ORLIN_H