alpar@877: /* -*- mode: C++; indent-tabs-mode: nil; -*- tapolcai@543: * alpar@877: * This file is a part of LEMON, a generic C++ optimization library. tapolcai@543: * alpar@1092: * Copyright (C) 2003-2013 tapolcai@543: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport tapolcai@543: * (Egervary Research Group on Combinatorial Optimization, EGRES). tapolcai@543: * tapolcai@543: * Permission to use, modify and distribute this software is granted tapolcai@543: * provided that this copyright notice appears in all copies. For tapolcai@543: * precise terms see the accompanying LICENSE file. tapolcai@543: * tapolcai@543: * This software is provided "AS IS" with no warranty of any kind, tapolcai@543: * express or implied, and with no claim as to its suitability for any tapolcai@543: * purpose. tapolcai@543: * tapolcai@543: */ tapolcai@543: tapolcai@543: #ifndef LEMON_GOMORY_HU_TREE_H tapolcai@543: #define LEMON_GOMORY_HU_TREE_H tapolcai@543: tapolcai@543: #include tapolcai@543: alpar@544: #include tapolcai@543: #include tapolcai@543: #include tapolcai@543: #include tapolcai@543: tapolcai@543: /// \ingroup min_cut alpar@877: /// \file tapolcai@543: /// \brief Gomory-Hu cut tree in graphs. tapolcai@543: tapolcai@543: namespace lemon { tapolcai@543: tapolcai@543: /// \ingroup min_cut tapolcai@543: /// tapolcai@543: /// \brief Gomory-Hu cut tree algorithm tapolcai@543: /// kpeter@546: /// The Gomory-Hu tree is a tree on the node set of a given graph, but it kpeter@546: /// may contain edges which are not in the original graph. It has the alpar@877: /// property that the minimum capacity edge of the path between two nodes kpeter@546: /// in this tree has the same weight as the minimum cut in the graph alpar@544: /// between these nodes. Moreover the components obtained by removing alpar@544: /// this edge from the tree determine the corresponding minimum cut. alpar@544: /// Therefore once this tree is computed, the minimum cut between any pair alpar@544: /// of nodes can easily be obtained. alpar@877: /// alpar@544: /// The algorithm calculates \e n-1 distinct minimum cuts (currently with kpeter@1080: /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{m})\f$ overall kpeter@596: /// time complexity. It calculates a rooted Gomory-Hu tree. kpeter@596: /// The structure of the tree and the edge weights can be kpeter@596: /// obtained using \c predNode(), \c predValue() and \c rootDist(). kpeter@596: /// The functions \c minCutMap() and \c minCutValue() calculate kpeter@546: /// the minimum cut and the minimum cut value between any two nodes kpeter@546: /// in the graph. You can also list (iterate on) the nodes and the kpeter@546: /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt. alpar@544: /// kpeter@546: /// \tparam GR The type of the undirected graph the algorithm runs on. kpeter@596: /// \tparam CAP The type of the edge map containing the capacities. kpeter@596: /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap". kpeter@546: #ifdef DOXYGEN alpar@544: template kpeter@546: #else kpeter@546: template > kpeter@546: #endif alpar@545: class GomoryHu { tapolcai@543: public: tapolcai@543: kpeter@596: /// The graph type of the algorithm alpar@544: typedef GR Graph; kpeter@596: /// The capacity map type of the algorithm alpar@544: typedef CAP Capacity; tapolcai@543: /// The value type of capacities tapolcai@543: typedef typename Capacity::Value Value; alpar@877: tapolcai@543: private: tapolcai@543: tapolcai@543: TEMPLATE_GRAPH_TYPEDEFS(Graph); tapolcai@543: tapolcai@543: const Graph& _graph; tapolcai@543: const Capacity& _capacity; tapolcai@543: tapolcai@543: Node _root; tapolcai@543: typename Graph::template NodeMap* _pred; tapolcai@543: typename Graph::template NodeMap* _weight; tapolcai@543: typename Graph::template NodeMap* _order; tapolcai@543: tapolcai@543: void createStructures() { tapolcai@543: if (!_pred) { alpar@877: _pred = new typename Graph::template NodeMap(_graph); tapolcai@543: } tapolcai@543: if (!_weight) { alpar@877: _weight = new typename Graph::template NodeMap(_graph); tapolcai@543: } tapolcai@543: if (!_order) { alpar@877: _order = new typename Graph::template NodeMap(_graph); tapolcai@543: } tapolcai@543: } tapolcai@543: tapolcai@543: void destroyStructures() { tapolcai@543: if (_pred) { alpar@877: delete _pred; tapolcai@543: } tapolcai@543: if (_weight) { alpar@877: delete _weight; tapolcai@543: } tapolcai@543: if (_order) { alpar@877: delete _order; tapolcai@543: } tapolcai@543: } alpar@877: tapolcai@543: public: tapolcai@543: tapolcai@543: /// \brief Constructor tapolcai@543: /// kpeter@596: /// Constructor. kpeter@546: /// \param graph The undirected graph the algorithm runs on. kpeter@546: /// \param capacity The edge capacity map. alpar@877: GomoryHu(const Graph& graph, const Capacity& capacity) tapolcai@543: : _graph(graph), _capacity(capacity), alpar@877: _pred(0), _weight(0), _order(0) tapolcai@543: { tapolcai@543: checkConcept, Capacity>(); tapolcai@543: } tapolcai@543: tapolcai@543: tapolcai@543: /// \brief Destructor tapolcai@543: /// kpeter@596: /// Destructor. alpar@545: ~GomoryHu() { tapolcai@543: destroyStructures(); tapolcai@543: } tapolcai@543: kpeter@546: private: alpar@877: kpeter@546: // Initialize the internal data structures tapolcai@543: void init() { tapolcai@543: createStructures(); tapolcai@543: tapolcai@543: _root = NodeIt(_graph); tapolcai@543: for (NodeIt n(_graph); n != INVALID; ++n) { kpeter@581: (*_pred)[n] = _root; kpeter@581: (*_order)[n] = -1; tapolcai@543: } kpeter@581: (*_pred)[_root] = INVALID; alpar@877: (*_weight)[_root] = std::numeric_limits::max(); tapolcai@543: } tapolcai@543: tapolcai@543: kpeter@546: // Start the algorithm tapolcai@543: void start() { tapolcai@543: Preflow fa(_graph, _capacity, _root, INVALID); tapolcai@543: tapolcai@543: for (NodeIt n(_graph); n != INVALID; ++n) { alpar@877: if (n == _root) continue; tapolcai@543: alpar@877: Node pn = (*_pred)[n]; alpar@877: fa.source(n); alpar@877: fa.target(pn); tapolcai@543: alpar@877: fa.runMinCut(); tapolcai@543: alpar@877: (*_weight)[n] = fa.flowValue(); tapolcai@543: alpar@877: for (NodeIt nn(_graph); nn != INVALID; ++nn) { alpar@877: if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { alpar@877: (*_pred)[nn] = n; alpar@877: } alpar@877: } alpar@877: if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { alpar@877: (*_pred)[n] = (*_pred)[pn]; alpar@877: (*_pred)[pn] = n; alpar@877: (*_weight)[n] = (*_weight)[pn]; alpar@877: (*_weight)[pn] = fa.flowValue(); alpar@877: } tapolcai@543: } tapolcai@543: kpeter@581: (*_order)[_root] = 0; tapolcai@543: int index = 1; tapolcai@543: tapolcai@543: for (NodeIt n(_graph); n != INVALID; ++n) { alpar@877: std::vector st; alpar@877: Node nn = n; alpar@877: while ((*_order)[nn] == -1) { alpar@877: st.push_back(nn); alpar@877: nn = (*_pred)[nn]; alpar@877: } alpar@877: while (!st.empty()) { alpar@877: (*_order)[st.back()] = index++; alpar@877: st.pop_back(); alpar@877: } tapolcai@543: } tapolcai@543: } tapolcai@543: kpeter@546: public: kpeter@546: alpar@544: ///\name Execution Control alpar@877: alpar@544: ///@{ alpar@544: alpar@544: /// \brief Run the Gomory-Hu algorithm. tapolcai@543: /// alpar@544: /// This function runs the Gomory-Hu algorithm. tapolcai@543: void run() { tapolcai@543: init(); tapolcai@543: start(); tapolcai@543: } alpar@877: alpar@544: /// @} tapolcai@543: alpar@544: ///\name Query Functions alpar@544: ///The results of the algorithm can be obtained using these alpar@544: ///functions.\n kpeter@596: ///\ref run() should be called before using them.\n kpeter@546: ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt. alpar@544: alpar@544: ///@{ alpar@544: alpar@544: /// \brief Return the predecessor node in the Gomory-Hu tree. tapolcai@543: /// kpeter@596: /// This function returns the predecessor node of the given node kpeter@596: /// in the Gomory-Hu tree. kpeter@596: /// If \c node is the root of the tree, then it returns \c INVALID. kpeter@596: /// kpeter@596: /// \pre \ref run() must be called before using this function. kpeter@596: Node predNode(const Node& node) const { tapolcai@543: return (*_pred)[node]; tapolcai@543: } tapolcai@543: alpar@544: /// \brief Return the weight of the predecessor edge in the tapolcai@543: /// Gomory-Hu tree. tapolcai@543: /// alpar@877: /// This function returns the weight of the predecessor edge of the kpeter@596: /// given node in the Gomory-Hu tree. kpeter@596: /// If \c node is the root of the tree, the result is undefined. kpeter@596: /// kpeter@596: /// \pre \ref run() must be called before using this function. kpeter@596: Value predValue(const Node& node) const { tapolcai@543: return (*_weight)[node]; tapolcai@543: } tapolcai@543: kpeter@596: /// \brief Return the distance from the root node in the Gomory-Hu tree. kpeter@596: /// kpeter@596: /// This function returns the distance of the given node from the root kpeter@596: /// node in the Gomory-Hu tree. kpeter@596: /// kpeter@596: /// \pre \ref run() must be called before using this function. kpeter@596: int rootDist(const Node& node) const { kpeter@596: return (*_order)[node]; kpeter@596: } kpeter@596: alpar@544: /// \brief Return the minimum cut value between two nodes tapolcai@543: /// kpeter@596: /// This function returns the minimum cut value between the nodes alpar@877: /// \c s and \c t. kpeter@596: /// It finds the nearest common ancestor of the given nodes in the kpeter@596: /// Gomory-Hu tree and calculates the minimum weight edge on the kpeter@596: /// paths to the ancestor. kpeter@596: /// kpeter@596: /// \pre \ref run() must be called before using this function. tapolcai@543: Value minCutValue(const Node& s, const Node& t) const { tapolcai@543: Node sn = s, tn = t; tapolcai@543: Value value = std::numeric_limits::max(); alpar@877: tapolcai@543: while (sn != tn) { alpar@877: if ((*_order)[sn] < (*_order)[tn]) { alpar@877: if ((*_weight)[tn] <= value) value = (*_weight)[tn]; alpar@877: tn = (*_pred)[tn]; alpar@877: } else { alpar@877: if ((*_weight)[sn] <= value) value = (*_weight)[sn]; alpar@877: sn = (*_pred)[sn]; alpar@877: } tapolcai@543: } tapolcai@543: return value; tapolcai@543: } tapolcai@543: alpar@544: /// \brief Return the minimum cut between two nodes tapolcai@543: /// alpar@544: /// This function returns the minimum cut between the nodes \c s and \c t kpeter@546: /// in the \c cutMap parameter by setting the nodes in the component of kpeter@546: /// \c s to \c true and the other nodes to \c false. alpar@544: /// kpeter@596: /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt. kpeter@596: /// kpeter@596: /// \param s The base node. kpeter@596: /// \param t The node you want to separate from node \c s. kpeter@596: /// \param cutMap The cut will be returned in this map. kpeter@596: /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap kpeter@596: /// "ReadWriteMap" on the graph nodes. kpeter@596: /// kpeter@596: /// \return The value of the minimum cut between \c s and \c t. kpeter@596: /// kpeter@596: /// \pre \ref run() must be called before using this function. tapolcai@543: template kpeter@786: Value minCutMap(const Node& s, alpar@544: const Node& t, alpar@544: CutMap& cutMap alpar@544: ) const { tapolcai@543: Node sn = s, tn = t; alpar@544: bool s_root=false; tapolcai@543: Node rn = INVALID; tapolcai@543: Value value = std::numeric_limits::max(); alpar@877: tapolcai@543: while (sn != tn) { alpar@877: if ((*_order)[sn] < (*_order)[tn]) { alpar@877: if ((*_weight)[tn] <= value) { alpar@877: rn = tn; alpar@544: s_root = false; alpar@877: value = (*_weight)[tn]; alpar@877: } alpar@877: tn = (*_pred)[tn]; alpar@877: } else { alpar@877: if ((*_weight)[sn] <= value) { alpar@877: rn = sn; alpar@544: s_root = true; alpar@877: value = (*_weight)[sn]; alpar@877: } alpar@877: sn = (*_pred)[sn]; alpar@877: } tapolcai@543: } tapolcai@543: tapolcai@543: typename Graph::template NodeMap reached(_graph, false); kpeter@581: reached[_root] = true; alpar@544: cutMap.set(_root, !s_root); kpeter@581: reached[rn] = true; alpar@544: cutMap.set(rn, s_root); tapolcai@543: alpar@544: std::vector st; tapolcai@543: for (NodeIt n(_graph); n != INVALID; ++n) { alpar@877: st.clear(); alpar@544: Node nn = n; alpar@877: while (!reached[nn]) { alpar@877: st.push_back(nn); alpar@877: nn = (*_pred)[nn]; alpar@877: } alpar@877: while (!st.empty()) { alpar@877: cutMap.set(st.back(), cutMap[nn]); alpar@877: st.pop_back(); alpar@877: } tapolcai@543: } alpar@877: tapolcai@543: return value; tapolcai@543: } tapolcai@543: alpar@544: ///@} alpar@544: alpar@544: friend class MinCutNodeIt; alpar@544: alpar@544: /// Iterate on the nodes of a minimum cut alpar@877: alpar@544: /// This iterator class lists the nodes of a minimum cut found by kpeter@596: /// GomoryHu. Before using it, you must allocate a GomoryHu class alpar@545: /// and call its \ref GomoryHu::run() "run()" method. alpar@544: /// alpar@544: /// This example counts the nodes in the minimum cut separating \c s from alpar@544: /// \c t. alpar@544: /// \code kpeter@713: /// GomoryHu gom(g, capacities); alpar@544: /// gom.run(); kpeter@546: /// int cnt=0; kpeter@713: /// for(GomoryHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; alpar@544: /// \endcode alpar@544: class MinCutNodeIt alpar@544: { alpar@544: bool _side; alpar@544: typename Graph::NodeIt _node_it; alpar@544: typename Graph::template NodeMap _cut; alpar@544: public: alpar@544: /// Constructor alpar@544: kpeter@546: /// Constructor. alpar@544: /// alpar@545: MinCutNodeIt(GomoryHu const &gomory, alpar@545: ///< The GomoryHu class. You must call its alpar@544: /// run() method kpeter@546: /// before initializing this iterator. kpeter@546: const Node& s, ///< The base node. alpar@544: const Node& t, kpeter@546: ///< The node you want to separate from node \c s. alpar@544: bool side=true alpar@544: ///< If it is \c true (default) then the iterator lists alpar@544: /// the nodes of the component containing \c s, alpar@544: /// otherwise it lists the other component. alpar@544: /// \note As the minimum cut is not always unique, alpar@544: /// \code alpar@544: /// MinCutNodeIt(gomory, s, t, true); alpar@544: /// \endcode alpar@544: /// and alpar@544: /// \code alpar@544: /// MinCutNodeIt(gomory, t, s, false); alpar@544: /// \endcode alpar@544: /// does not necessarily give the same set of nodes. kpeter@786: /// However, it is ensured that alpar@544: /// \code alpar@544: /// MinCutNodeIt(gomory, s, t, true); alpar@544: /// \endcode alpar@544: /// and alpar@544: /// \code alpar@544: /// MinCutNodeIt(gomory, s, t, false); alpar@544: /// \endcode alpar@544: /// together list each node exactly once. alpar@544: ) alpar@544: : _side(side), _cut(gomory._graph) alpar@544: { alpar@544: gomory.minCutMap(s,t,_cut); alpar@544: for(_node_it=typename Graph::NodeIt(gomory._graph); alpar@544: _node_it!=INVALID && _cut[_node_it]!=_side; alpar@544: ++_node_it) {} alpar@544: } kpeter@546: /// Conversion to \c Node alpar@544: kpeter@546: /// Conversion to \c Node. alpar@544: /// alpar@544: operator typename Graph::Node() const alpar@544: { alpar@544: return _node_it; alpar@544: } alpar@544: bool operator==(Invalid) { return _node_it==INVALID; } alpar@544: bool operator!=(Invalid) { return _node_it!=INVALID; } alpar@544: /// Next node alpar@544: kpeter@546: /// Next node. alpar@544: /// alpar@544: MinCutNodeIt &operator++() alpar@544: { alpar@544: for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {} alpar@544: return *this; alpar@544: } alpar@544: /// Postfix incrementation alpar@544: kpeter@546: /// Postfix incrementation. alpar@544: /// alpar@544: /// \warning This incrementation kpeter@546: /// returns a \c Node, not a \c MinCutNodeIt, as one may alpar@544: /// expect. alpar@544: typename Graph::Node operator++(int) alpar@544: { alpar@544: typename Graph::Node n=*this; alpar@544: ++(*this); alpar@544: return n; alpar@544: } alpar@544: }; alpar@877: alpar@544: friend class MinCutEdgeIt; alpar@877: alpar@544: /// Iterate on the edges of a minimum cut alpar@877: alpar@544: /// This iterator class lists the edges of a minimum cut found by kpeter@596: /// GomoryHu. Before using it, you must allocate a GomoryHu class alpar@545: /// and call its \ref GomoryHu::run() "run()" method. alpar@544: /// alpar@544: /// This example computes the value of the minimum cut separating \c s from alpar@544: /// \c t. alpar@544: /// \code kpeter@713: /// GomoryHu gom(g, capacities); alpar@544: /// gom.run(); alpar@544: /// int value=0; kpeter@713: /// for(GomoryHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) alpar@544: /// value+=capacities[e]; alpar@544: /// \endcode kpeter@596: /// The result will be the same as the value returned by kpeter@596: /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)". alpar@544: class MinCutEdgeIt alpar@544: { alpar@544: bool _side; alpar@544: const Graph &_graph; alpar@544: typename Graph::NodeIt _node_it; alpar@544: typename Graph::OutArcIt _arc_it; alpar@544: typename Graph::template NodeMap _cut; alpar@544: void step() alpar@544: { alpar@544: ++_arc_it; alpar@544: while(_node_it!=INVALID && _arc_it==INVALID) alpar@544: { alpar@544: for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {} alpar@544: if(_node_it!=INVALID) alpar@544: _arc_it=typename Graph::OutArcIt(_graph,_node_it); alpar@544: } alpar@544: } alpar@877: alpar@544: public: kpeter@596: /// Constructor kpeter@596: kpeter@596: /// Constructor. kpeter@596: /// alpar@545: MinCutEdgeIt(GomoryHu const &gomory, alpar@545: ///< The GomoryHu class. You must call its alpar@544: /// run() method kpeter@546: /// before initializing this iterator. kpeter@546: const Node& s, ///< The base node. alpar@544: const Node& t, kpeter@546: ///< The node you want to separate from node \c s. alpar@544: bool side=true alpar@544: ///< If it is \c true (default) then the listed arcs alpar@544: /// will be oriented from the kpeter@596: /// nodes of the component containing \c s, alpar@544: /// otherwise they will be oriented in the opposite alpar@544: /// direction. alpar@544: ) alpar@544: : _graph(gomory._graph), _cut(_graph) alpar@544: { alpar@544: gomory.minCutMap(s,t,_cut); alpar@544: if(!side) alpar@544: for(typename Graph::NodeIt n(_graph);n!=INVALID;++n) alpar@544: _cut[n]=!_cut[n]; alpar@544: alpar@544: for(_node_it=typename Graph::NodeIt(_graph); alpar@544: _node_it!=INVALID && !_cut[_node_it]; alpar@544: ++_node_it) {} alpar@544: _arc_it = _node_it!=INVALID ? alpar@544: typename Graph::OutArcIt(_graph,_node_it) : INVALID; alpar@544: while(_node_it!=INVALID && _arc_it == INVALID) alpar@544: { alpar@544: for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {} alpar@544: if(_node_it!=INVALID) alpar@544: _arc_it= typename Graph::OutArcIt(_graph,_node_it); alpar@544: } alpar@544: while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); alpar@544: } kpeter@546: /// Conversion to \c Arc alpar@544: kpeter@546: /// Conversion to \c Arc. alpar@544: /// alpar@544: operator typename Graph::Arc() const alpar@544: { alpar@544: return _arc_it; alpar@544: } kpeter@546: /// Conversion to \c Edge alpar@544: kpeter@546: /// Conversion to \c Edge. alpar@544: /// alpar@544: operator typename Graph::Edge() const alpar@544: { alpar@544: return _arc_it; alpar@544: } alpar@544: bool operator==(Invalid) { return _node_it==INVALID; } alpar@544: bool operator!=(Invalid) { return _node_it!=INVALID; } alpar@544: /// Next edge alpar@544: kpeter@546: /// Next edge. alpar@544: /// alpar@544: MinCutEdgeIt &operator++() alpar@544: { alpar@544: step(); alpar@544: while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); alpar@544: return *this; alpar@544: } alpar@544: /// Postfix incrementation alpar@877: kpeter@546: /// Postfix incrementation. alpar@544: /// alpar@544: /// \warning This incrementation kpeter@546: /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect. alpar@544: typename Graph::Arc operator++(int) alpar@544: { alpar@544: typename Graph::Arc e=*this; alpar@544: ++(*this); alpar@544: return e; alpar@544: } alpar@544: }; alpar@544: tapolcai@543: }; tapolcai@543: tapolcai@543: } tapolcai@543: tapolcai@543: #endif