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