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