/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2007

 * 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 <lemon/preflow.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

/// \ingroup min_cut

/// \file 

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

namespace lemon {

  /// \ingroup min_cut

  ///

  /// \brief Gomory-Hu cut tree algorithm

  ///

  /// The Gomory-Hu tree is a tree on the nodeset of the graph, but it

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

  /// to calculate the minimum cut between all pairs of nodes, because

  /// the minimum capacity edge on the tree path between two nodes has

  /// the same weight as the minimum cut in the graph between these

  /// nodes. Moreover this edge separates the nodes to two parts which

  /// determine this minimum cut.

  /// 

  /// The algorithm calculates \e n-1 distinict minimum cuts with

  /// preflow algorithm, therefore the algorithm has

  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a

  /// rooted Gomory-Hu tree, the structure of the tree and the weights

  /// can be obtained with \c predNode() and \c predValue()

  /// functions. The \c minCutValue() and \c minCutMap() calculates

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

  /// in the graph.

  template <typename _UGraph, 

	    typename _Capacity = typename _UGraph::template UEdgeMap<int> >

  class GomoryHuTree {

  public:

    /// The undirected graph type

    typedef _UGraph UGraph;

    /// The capacity on undirected edges

    typedef _Capacity Capacity;

    /// The value type of capacities

    typedef typename Capacity::Value Value;

  private:

    UGRAPH_TYPEDEFS(typename UGraph);

    const UGraph& _ugraph;

    const Capacity& _capacity;

    Node _root;

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

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

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

    void createStructures() {

      if (!_pred) {

	_pred = new typename UGraph::template NodeMap<Node>(_ugraph);

      }

      if (!_weight) {

	_weight = new typename UGraph::template NodeMap<Value>(_ugraph);

      }

      if (!_order) {

	_order = new typename UGraph::template NodeMap<int>(_ugraph);

      }

    }

    void destroyStructures() {

      if (_pred) {

	delete _pred;

      }

      if (_weight) {

	delete _weight;

      }

      if (_order) {

	delete _order;

      }

    }

  public:

    /// \brief Constructor

    ///

    /// Constructor

    /// \param ugraph The undirected graph type.

    /// \param capacity The capacity map.

    GomoryHuTree(const UGraph& ugraph, const Capacity& capacity) 

      : _ugraph(ugraph), _capacity(capacity),

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

    {

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

    }

    /// \brief Destructor

    ///

    /// Destructor

    ~GomoryHuTree() {

      destroyStructures();

    }

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures.

    ///

    void init() {

      createStructures();

      _root = NodeIt(_ugraph);

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

	_pred->set(n, _root);

	_order->set(n, -1);

      }

      _pred->set(_root, INVALID);

      _weight->set(_root, std::numeric_limits<Value>::max()); 

    }

    /// \brief Starts the algorithm

    ///

    /// Starts the algorithm.

    void start() {

      Preflow<UGraph, Capacity> fa(_ugraph, _capacity, _root, INVALID);

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

	if (n == _root) continue;

	Node pn = (*_pred)[n];

	fa.source(n);

	fa.target(pn);

	fa.runMinCut();

	_weight->set(n, fa.flowValue());

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

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

	    _pred->set(nn, n);

	  }

	}

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

	  _pred->set(n, (*_pred)[pn]);

	  _pred->set(pn, n);

	  _weight->set(n, (*_weight)[pn]);

	  _weight->set(pn, fa.flowValue());	

	}

      }

      _order->set(_root, 0);

      int index = 1;

      for (NodeIt n(_ugraph); 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->set(st.back(), index++);

	  st.pop_back();

	}

      }

    }

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

    ///

    /// Runs the Gomory-Hu algorithm.

    /// \note gh.run() is just a shortcut of the following code.

    /// \code

    ///   ght.init();

    ///   ght.start();

    /// \endcode

    void run() {

      init();

      start();

    }

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

    ///

    /// Returns the predecessor node in the Gomory-Hu tree. If the node is

    /// the root of the Gomory-Hu tree, then it returns \c INVALID.

    Node predNode(const Node& node) {

      return (*_pred)[node];

    }

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

    /// Gomory-Hu tree.

    ///

    /// Returns the weight of the predecessor edge in the Gomory-Hu

    /// tree.  If the node is the root of the Gomory-Hu tree, the

    /// result is undefined.

    Value predValue(const Node& node) {

      return (*_weight)[node];

    }

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

    ///

    /// Returns the minimum cut value between two nodes. The

    /// algorithm finds the nearest common ancestor in the Gomory-Hu

    /// tree and calculates the minimum weight edge on the paths to

    /// the ancestor.

    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 Returns the minimum cut between two nodes

    ///

    /// Returns the minimum cut value between two nodes. The

    /// algorithm finds the nearest common ancestor in the Gomory-Hu

    /// tree and calculates the minimum weight edge on the paths to

    /// the ancestor. Then it sets all nodes to the cut determined by

    /// this edge. The \c cutMap should be \ref concepts::ReadWriteMap

    /// "ReadWriteMap".

    template <typename CutMap>

    Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {

      Node sn = s, tn = t;

      Node rn = INVALID;

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

      while (sn != tn) {

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

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

	    rn = tn;

	    value = (*_weight)[tn];

	  }

	  tn = (*_pred)[tn];

	} else {

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

	    rn = sn;

	    value = (*_weight)[sn];

	  }

	  sn = (*_pred)[sn];

	}

      }

      typename UGraph::template NodeMap<bool> reached(_ugraph, false);

      reached.set(_root, true);

      cutMap.set(_root, false);

      reached.set(rn, true);

      cutMap.set(rn, true);

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

	std::vector<Node> st;

	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;

    }

  };

}

#endif