deba@2528: /* -*- C++ -*-
deba@2528:  *
deba@2528:  * This file is a part of LEMON, a generic C++ optimization library
deba@2528:  *
deba@2528:  * Copyright (C) 2003-2007
deba@2528:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2528:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2528:  *
deba@2528:  * Permission to use, modify and distribute this software is granted
deba@2528:  * provided that this copyright notice appears in all copies. For
deba@2528:  * precise terms see the accompanying LICENSE file.
deba@2528:  *
deba@2528:  * This software is provided "AS IS" with no warranty of any kind,
deba@2528:  * express or implied, and with no claim as to its suitability for any
deba@2528:  * purpose.
deba@2528:  *
deba@2528:  */
deba@2528: 
deba@2528: #ifndef LEMON_GOMORY_HU_TREE_H
deba@2528: #define LEMON_GOMORY_HU_TREE_H
deba@2528: 
deba@2528: #include <lemon/preflow.h>
deba@2528: #include <lemon/concept_check.h>
deba@2528: #include <lemon/concepts/maps.h>
deba@2528: 
deba@2528: /// \ingroup min_cut
deba@2528: /// \file 
deba@2528: /// \brief Gomory-Hu cut tree in undirected graphs.
deba@2528: 
deba@2528: namespace lemon {
deba@2528: 
deba@2528:   /// \ingroup min_cut
deba@2528:   ///
deba@2528:   /// \brief Gomory-Hu cut tree algorithm
deba@2528:   ///
deba@2528:   /// The Gomory-Hu tree is a tree on the nodeset of the graph, but it
deba@2528:   /// may contain edges which are not in the original graph. It helps
deba@2528:   /// to calculate the minimum cut between all pairs of nodes, because
deba@2528:   /// the minimum capacity edge on the tree path between two nodes has
deba@2528:   /// the same weight as the minimum cut in the graph between these
deba@2528:   /// nodes. Moreover this edge separates the nodes to two parts which
deba@2528:   /// determine this minimum cut.
deba@2528:   /// 
deba@2528:   /// The algorithm calculates \e n-1 distinict minimum cuts with
deba@2528:   /// preflow algorithm, therefore the algorithm has
deba@2528:   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
deba@2528:   /// rooted Gomory-Hu tree, the structure of the tree and the weights
deba@2528:   /// can be obtained with \c predNode() and \c predValue()
deba@2528:   /// functions. The \c minCutValue() and \c minCutMap() calculates
deba@2528:   /// the minimum cut and the minimum cut value between any two node
deba@2528:   /// in the graph.
deba@2528:   template <typename _UGraph, 
deba@2528: 	    typename _Capacity = typename _UGraph::template UEdgeMap<int> >
deba@2528:   class GomoryHuTree {
deba@2528:   public:
deba@2528: 
deba@2528:     /// The undirected graph type
deba@2528:     typedef _UGraph UGraph;
deba@2528:     /// The capacity on undirected edges
deba@2528:     typedef _Capacity Capacity;
deba@2528:     /// The value type of capacities
deba@2528:     typedef typename Capacity::Value Value;
deba@2528:     
deba@2528:   private:
deba@2528: 
deba@2528:     UGRAPH_TYPEDEFS(typename UGraph);
deba@2528: 
deba@2528:     const UGraph& _ugraph;
deba@2528:     const Capacity& _capacity;
deba@2528: 
deba@2528:     Node _root;
deba@2528:     typename UGraph::template NodeMap<Node>* _pred;
deba@2528:     typename UGraph::template NodeMap<Value>* _weight;
deba@2528:     typename UGraph::template NodeMap<int>* _order;
deba@2528: 
deba@2528:     void createStructures() {
deba@2528:       if (!_pred) {
deba@2528: 	_pred = new typename UGraph::template NodeMap<Node>(_ugraph);
deba@2528:       }
deba@2528:       if (!_weight) {
deba@2528: 	_weight = new typename UGraph::template NodeMap<Value>(_ugraph);
deba@2528:       }
deba@2528:       if (!_order) {
deba@2528: 	_order = new typename UGraph::template NodeMap<int>(_ugraph);
deba@2528:       }
deba@2528:     }
deba@2528: 
deba@2528:     void destroyStructures() {
deba@2528:       if (_pred) {
deba@2528: 	delete _pred;
deba@2528:       }
deba@2528:       if (_weight) {
deba@2528: 	delete _weight;
deba@2528:       }
deba@2528:       if (_order) {
deba@2528: 	delete _order;
deba@2528:       }
deba@2528:     }
deba@2528:   
deba@2528:   public:
deba@2528: 
deba@2528:     /// \brief Constructor
deba@2528:     ///
deba@2528:     /// Constructor
deba@2528:     /// \param ugraph The undirected graph type.
deba@2528:     /// \param capacity The capacity map.
deba@2528:     GomoryHuTree(const UGraph& ugraph, const Capacity& capacity) 
deba@2528:       : _ugraph(ugraph), _capacity(capacity),
deba@2528: 	_pred(0), _weight(0), _order(0) 
deba@2528:     {
deba@2528:       checkConcept<concepts::ReadMap<UEdge, Value>, Capacity>();
deba@2528:     }
deba@2528: 
deba@2528: 
deba@2528:     /// \brief Destructor
deba@2528:     ///
deba@2528:     /// Destructor
deba@2528:     ~GomoryHuTree() {
deba@2528:       destroyStructures();
deba@2528:     }
deba@2528: 
deba@2528:     /// \brief Initializes the internal data structures.
deba@2528:     ///
deba@2528:     /// Initializes the internal data structures.
deba@2528:     ///
deba@2528:     void init() {
deba@2528:       createStructures();
deba@2528: 
deba@2528:       _root = NodeIt(_ugraph);
deba@2528:       for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: 	_pred->set(n, _root);
deba@2528: 	_order->set(n, -1);
deba@2528:       }
deba@2528:       _pred->set(_root, INVALID);
deba@2528:       _weight->set(_root, std::numeric_limits<Value>::max()); 
deba@2528:     }
deba@2528: 
deba@2528: 
deba@2528:     /// \brief Starts the algorithm
deba@2528:     ///
deba@2528:     /// Starts the algorithm.
deba@2528:     void start() {
deba@2528:       Preflow<UGraph, Capacity> fa(_ugraph, _capacity, _root, INVALID);
deba@2528: 
deba@2528:       for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: 	if (n == _root) continue;
deba@2528: 
deba@2528: 	Node pn = (*_pred)[n];
deba@2528: 	fa.source(n);
deba@2528: 	fa.target(pn);
deba@2528: 
deba@2528: 	fa.runMinCut();
deba@2528: 
deba@2528: 	_weight->set(n, fa.flowValue());
deba@2528: 
deba@2528: 	for (NodeIt nn(_ugraph); nn != INVALID; ++nn) {
deba@2528: 	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
deba@2528: 	    _pred->set(nn, n);
deba@2528: 	  }
deba@2528: 	}
deba@2528: 	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
deba@2528: 	  _pred->set(n, (*_pred)[pn]);
deba@2528: 	  _pred->set(pn, n);
deba@2528: 	  _weight->set(n, (*_weight)[pn]);
deba@2528: 	  _weight->set(pn, fa.flowValue());	
deba@2528: 	}
deba@2528:       }
deba@2528: 
deba@2528:       _order->set(_root, 0);
deba@2528:       int index = 1;
deba@2528: 
deba@2528:       for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: 	std::vector<Node> st;
deba@2528: 	Node nn = n;
deba@2528: 	while ((*_order)[nn] == -1) {
deba@2528: 	  st.push_back(nn);
deba@2528: 	  nn = (*_pred)[nn];
deba@2528: 	}
deba@2528: 	while (!st.empty()) {
deba@2528: 	  _order->set(st.back(), index++);
deba@2528: 	  st.pop_back();
deba@2528: 	}
deba@2528:       }
deba@2528:     }
deba@2528: 
deba@2528:     /// \brief Runs the Gomory-Hu algorithm.  
deba@2528:     ///
deba@2528:     /// Runs the Gomory-Hu algorithm.
deba@2528:     /// \note gh.run() is just a shortcut of the following code.
deba@2528:     /// \code
deba@2528:     ///   ght.init();
deba@2528:     ///   ght.start();
deba@2528:     /// \endcode
deba@2528:     void run() {
deba@2528:       init();
deba@2528:       start();
deba@2528:     }
deba@2528: 
deba@2528:     /// \brief Returns the predecessor node in the Gomory-Hu tree.
deba@2528:     ///
deba@2528:     /// Returns the predecessor node in the Gomory-Hu tree. If the node is
deba@2528:     /// the root of the Gomory-Hu tree, then it returns \c INVALID.
deba@2528:     Node predNode(const Node& node) {
deba@2528:       return (*_pred)[node];
deba@2528:     }
deba@2528: 
deba@2528:     /// \brief Returns the weight of the predecessor edge in the
deba@2528:     /// Gomory-Hu tree.
deba@2528:     ///
deba@2528:     /// Returns the weight of the predecessor edge in the Gomory-Hu
deba@2528:     /// tree.  If the node is the root of the Gomory-Hu tree, the
deba@2528:     /// result is undefined.
deba@2528:     Value predValue(const Node& node) {
deba@2528:       return (*_weight)[node];
deba@2528:     }
deba@2528: 
deba@2528:     /// \brief Returns the minimum cut value between two nodes
deba@2528:     ///
deba@2528:     /// Returns the minimum cut value between two nodes. The
deba@2528:     /// algorithm finds the nearest common ancestor in the Gomory-Hu
deba@2528:     /// tree and calculates the minimum weight edge on the paths to
deba@2528:     /// the ancestor.
deba@2528:     Value minCutValue(const Node& s, const Node& t) const {
deba@2528:       Node sn = s, tn = t;
deba@2528:       Value value = std::numeric_limits<Value>::max();
deba@2528:       
deba@2528:       while (sn != tn) {
deba@2528: 	if ((*_order)[sn] < (*_order)[tn]) {
deba@2528: 	  if ((*_weight)[tn] < value) value = (*_weight)[tn];
deba@2528: 	  tn = (*_pred)[tn];
deba@2528: 	} else {
deba@2528: 	  if ((*_weight)[sn] < value) value = (*_weight)[sn];
deba@2528: 	  sn = (*_pred)[sn];
deba@2528: 	}
deba@2528:       }
deba@2528:       return value;
deba@2528:     }
deba@2528: 
deba@2528:     /// \brief Returns the minimum cut between two nodes
deba@2528:     ///
deba@2528:     /// Returns the minimum cut value between two nodes. The
deba@2528:     /// algorithm finds the nearest common ancestor in the Gomory-Hu
deba@2528:     /// tree and calculates the minimum weight edge on the paths to
deba@2528:     /// the ancestor. Then it sets all nodes to the cut determined by
deba@2528:     /// this edge. The \c cutMap should be \ref concepts::ReadWriteMap
deba@2528:     /// "ReadWriteMap".
deba@2528:     template <typename CutMap>
deba@2528:     Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
deba@2528:       Node sn = s, tn = t;
deba@2528: 
deba@2528:       Node rn = INVALID;
deba@2528:       Value value = std::numeric_limits<Value>::max();
deba@2528:       
deba@2528:       while (sn != tn) {
deba@2528: 	if ((*_order)[sn] < (*_order)[tn]) {
deba@2528: 	  if ((*_weight)[tn] < value) {
deba@2528: 	    rn = tn;
deba@2528: 	    value = (*_weight)[tn];
deba@2528: 	  }
deba@2528: 	  tn = (*_pred)[tn];
deba@2528: 	} else {
deba@2528: 	  if ((*_weight)[sn] < value) {
deba@2528: 	    rn = sn;
deba@2528: 	    value = (*_weight)[sn];
deba@2528: 	  }
deba@2528: 	  sn = (*_pred)[sn];
deba@2528: 	}
deba@2528:       }
deba@2528: 
deba@2528:       typename UGraph::template NodeMap<bool> reached(_ugraph, false);
deba@2528:       reached.set(_root, true);
deba@2528:       cutMap.set(_root, false);
deba@2528:       reached.set(rn, true);
deba@2528:       cutMap.set(rn, true);
deba@2528: 
deba@2528:       for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: 	std::vector<Node> st;
deba@2528: 	Node nn = n;
deba@2528: 	while (!reached[nn]) {
deba@2528: 	  st.push_back(nn);
deba@2528: 	  nn = (*_pred)[nn];
deba@2528: 	}
deba@2528: 	while (!st.empty()) {
deba@2528: 	  cutMap.set(st.back(), cutMap[nn]);
deba@2528: 	  st.pop_back();
deba@2528: 	}
deba@2528:       }
deba@2528:       
deba@2528:       return value;
deba@2528:     }
deba@2528: 
deba@2528:   };
deba@2528: 
deba@2528: }
deba@2528: 
deba@2528: #endif