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 deba@2528: #include deba@2528: #include 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 > 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* _pred; deba@2528: typename UGraph::template NodeMap* _weight; deba@2528: typename UGraph::template NodeMap* _order; deba@2528: deba@2528: void createStructures() { deba@2528: if (!_pred) { deba@2528: _pred = new typename UGraph::template NodeMap(_ugraph); deba@2528: } deba@2528: if (!_weight) { deba@2528: _weight = new typename UGraph::template NodeMap(_ugraph); deba@2528: } deba@2528: if (!_order) { deba@2528: _order = new typename UGraph::template NodeMap(_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, 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::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 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 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::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 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::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 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 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