COIN-OR::LEMON - Graph Library

Changeset 591:ccd2d3a3001e in lemon


Ignore:
Timestamp:
02/25/09 12:10:52 (9 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Message:

Cut iterators for GomoryHuTree? + doc cleanup + bug fixes (#66)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/gomory_hu_tree.h

    r590 r591  
    2222#include <limits> 
    2323 
     24#include <lemon/core.h> 
    2425#include <lemon/preflow.h> 
    2526#include <lemon/concept_check.h> 
     
    3637  /// \brief Gomory-Hu cut tree algorithm 
    3738  /// 
    38   /// The Gomory-Hu tree is a tree on the nodeset of the digraph, but it 
    39   /// may contain arcs which are not in the original digraph. It helps 
    40   /// to calculate the minimum cut between all pairs of nodes, because 
    41   /// the minimum capacity arc on the tree path between two nodes has 
    42   /// the same weight as the minimum cut in the digraph between these 
    43   /// nodes. Moreover this arc separates the nodes to two parts which 
    44   /// determine this minimum cut. 
     39  /// The Gomory-Hu tree is a tree on the node set of the graph, but it 
     40  /// may contain edges which are not in the original digraph. It has the 
     41  /// property that the minimum capacity edge of the path between two nodes  
     42  /// in this tree has the same weight as the minimum cut in the digraph 
     43  /// between these nodes. Moreover the components obtained by removing 
     44  /// this edge from the tree determine the corresponding minimum cut. 
     45  /// 
     46  /// Therefore once this tree is computed, the minimum cut between any pair 
     47  /// of nodes can easily be obtained. 
    4548  ///  
    46   /// The algorithm calculates \e n-1 distinict minimum cuts with 
    47   /// preflow algorithm, therefore the algorithm has 
     49  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with 
     50  /// the \ref Preflow algorithm), therefore the algorithm has 
    4851  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a 
    49   /// rooted Gomory-Hu tree, the structure of the tree and the weights 
    50   /// can be obtained with \c predNode() and \c predValue() 
    51   /// functions. The \c minCutValue() and \c minCutMap() calculates 
     52  /// rooted Gomory-Hu tree, its structure and the weights can be obtained 
     53  /// by \c predNode(), \c predValue() and \c rootDist(). 
     54  ///  
     55  /// The members \c minCutMap() and \c minCutValue() calculate 
    5256  /// the minimum cut and the minimum cut value between any two node 
    53   /// in the digraph. 
    54   template <typename _Graph,  
    55             typename _Capacity = typename _Graph::template EdgeMap<int> > 
     57  /// in the digraph. You can also list (iterate on) the nodes and the 
     58  /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt. 
     59  /// 
     60  /// \tparam GR The undirected graph data structure the algorithm will run on 
     61  /// \tparam CAP type of the EdgeMap describing the Edge capacities. 
     62  /// it is typename GR::template EdgeMap<int> by default. 
     63  template <typename GR, 
     64            typename CAP = typename GR::template EdgeMap<int> 
     65            > 
    5666  class GomoryHuTree { 
    5767  public: 
    5868 
    5969    /// The graph type 
    60     typedef _Graph Graph; 
    61     /// The capacity on edges 
    62     typedef _Capacity Capacity; 
     70    typedef GR Graph; 
     71    /// The type if the edge capacity map 
     72    typedef CAP Capacity; 
    6373    /// The value type of capacities 
    6474    typedef typename Capacity::Value Value; 
     
    105115    /// 
    106116    /// Constructor 
    107     /// \param graph The graph type. 
     117    /// \param graph The graph the algorithm will run on. 
    108118    /// \param capacity The capacity map. 
    109119    GomoryHuTree(const Graph& graph, const Capacity& capacity)  
     
    122132    } 
    123133 
    124     /// \brief Initializes the internal data structures. 
    125     /// 
    126     /// Initializes the internal data structures. 
    127     /// 
     134    // \brief Initialize the internal data structures. 
     135    // 
     136    // This function initializes the internal data structures. 
     137    // 
    128138    void init() { 
    129139      createStructures(); 
     
    139149 
    140150 
    141     /// \brief Starts the algorithm 
    142     /// 
    143     /// Starts the algorithm. 
     151    // \brief Start the algorithm 
     152    // 
     153    // This function starts the algorithm. 
     154    // 
     155    // \pre \ref init() must be called before using this function. 
     156    // 
    144157    void start() { 
    145158      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID); 
     
    186199    } 
    187200 
    188     /// \brief Runs the Gomory-Hu algorithm.   
    189     /// 
    190     /// Runs the Gomory-Hu algorithm. 
    191     /// \note gh.run() is just a shortcut of the following code. 
    192     /// \code 
    193     ///   ght.init(); 
    194     ///   ght.start(); 
    195     /// \endcode 
     201    ///\name Execution Control 
     202  
     203    ///@{ 
     204 
     205    /// \brief Run the Gomory-Hu algorithm. 
     206    /// 
     207    /// This function runs the Gomory-Hu algorithm. 
    196208    void run() { 
    197209      init(); 
    198210      start(); 
    199211    } 
    200  
    201     /// \brief Returns the predecessor node in the Gomory-Hu tree. 
    202     /// 
    203     /// Returns the predecessor node in the Gomory-Hu tree. If the node is 
     212     
     213    /// @} 
     214 
     215    ///\name Query Functions 
     216    ///The results of the algorithm can be obtained using these 
     217    ///functions.\n 
     218    ///The \ref run() "run()" should be called before using them.\n 
     219    ///See also MinCutNodeIt and MinCutEdgeIt 
     220 
     221    ///@{ 
     222 
     223    /// \brief Return the predecessor node in the Gomory-Hu tree. 
     224    /// 
     225    /// This function returns the predecessor node in the Gomory-Hu tree. 
     226    /// If the node is 
    204227    /// the root of the Gomory-Hu tree, then it returns \c INVALID. 
    205228    Node predNode(const Node& node) { 
     
    207230    } 
    208231 
    209     /// \brief Returns the weight of the predecessor arc in the 
     232    /// \brief Return the distance from the root node in the Gomory-Hu tree. 
     233    /// 
     234    /// This function returns the distance of \c node from the root node 
     235    /// in the Gomory-Hu tree. 
     236    int rootDist(const Node& node) { 
     237      return (*_order)[node]; 
     238    } 
     239 
     240    /// \brief Return the weight of the predecessor edge in the 
    210241    /// Gomory-Hu tree. 
    211242    /// 
    212     /// Returns the weight of the predecessor arc in the Gomory-Hu 
    213     /// tree.  If the node is the root of the Gomory-Hu tree, the 
    214     /// result is undefined. 
     243    /// This function returns the weight of the predecessor edge in the 
     244    /// Gomory-Hu tree.  If the node is the root, the result is undefined. 
    215245    Value predValue(const Node& node) { 
    216246      return (*_weight)[node]; 
    217247    } 
    218248 
    219     /// \brief Returns the minimum cut value between two nodes 
    220     /// 
    221     /// Returns the minimum cut value between two nodes. The 
     249    /// \brief Return the minimum cut value between two nodes 
     250    /// 
     251    /// This function returns the minimum cut value between two nodes. The 
    222252    /// algorithm finds the nearest common ancestor in the Gomory-Hu 
    223253    /// tree and calculates the minimum weight arc on the paths to 
     
    229259      while (sn != tn) { 
    230260        if ((*_order)[sn] < (*_order)[tn]) { 
    231           if ((*_weight)[tn] < value) value = (*_weight)[tn]; 
     261          if ((*_weight)[tn] <= value) value = (*_weight)[tn]; 
    232262          tn = (*_pred)[tn]; 
    233263        } else { 
    234           if ((*_weight)[sn] < value) value = (*_weight)[sn]; 
     264          if ((*_weight)[sn] <= value) value = (*_weight)[sn]; 
    235265          sn = (*_pred)[sn]; 
    236266        } 
     
    239269    } 
    240270 
    241     /// \brief Returns the minimum cut between two nodes 
    242     /// 
    243     /// Returns the minimum cut value between two nodes. The 
    244     /// algorithm finds the nearest common ancestor in the Gomory-Hu 
    245     /// tree and calculates the minimum weight arc on the paths to 
    246     /// the ancestor. Then it sets all nodes to the cut determined by 
    247     /// this arc. The \c cutMap should be \ref concepts::ReadWriteMap 
     271    /// \brief Return the minimum cut between two nodes 
     272    /// 
     273    /// This function returns the minimum cut between the nodes \c s and \c t 
     274    /// the \r cutMap parameter by setting the nodes in the component of 
     275    /// \c \s to true and the other nodes to false. 
     276    /// 
     277    /// The \c cutMap should be \ref concepts::ReadWriteMap 
    248278    /// "ReadWriteMap". 
     279    /// 
     280    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt 
    249281    template <typename CutMap> 
    250     Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const { 
     282    Value minCutMap(const Node& s, ///< Base node 
     283                    const Node& t, 
     284                    ///< The node you want to separate from Node s. 
     285                    CutMap& cutMap 
     286                    ///< The cut will be return in this map. 
     287                    /// It must be a \c bool \ref concepts::ReadWriteMap 
     288                    /// "ReadWriteMap" on the graph nodes. 
     289                    ) const { 
    251290      Node sn = s, tn = t; 
    252  
     291      bool s_root=false; 
    253292      Node rn = INVALID; 
    254293      Value value = std::numeric_limits<Value>::max(); 
     
    256295      while (sn != tn) { 
    257296        if ((*_order)[sn] < (*_order)[tn]) { 
    258           if ((*_weight)[tn] < value) { 
     297          if ((*_weight)[tn] <= value) { 
    259298            rn = tn; 
     299            s_root = false; 
    260300            value = (*_weight)[tn]; 
    261301          } 
    262302          tn = (*_pred)[tn]; 
    263303        } else { 
    264           if ((*_weight)[sn] < value) { 
     304          if ((*_weight)[sn] <= value) { 
    265305            rn = sn; 
     306            s_root = true; 
    266307            value = (*_weight)[sn]; 
    267308          } 
     
    272313      typename Graph::template NodeMap<bool> reached(_graph, false); 
    273314      reached.set(_root, true); 
    274       cutMap.set(_root, false); 
     315      cutMap.set(_root, !s_root); 
    275316      reached.set(rn, true); 
    276       cutMap.set(rn, true); 
    277  
     317      cutMap.set(rn, s_root); 
     318 
     319      std::vector<Node> st; 
    278320      for (NodeIt n(_graph); n != INVALID; ++n) { 
    279         std::vector<Node> st; 
    280         Node nn = n; 
     321        st.clear(); 
     322        Node nn = n; 
    281323        while (!reached[nn]) { 
    282324          st.push_back(nn); 
     
    292334    } 
    293335 
     336    ///@} 
     337 
     338    friend class MinCutNodeIt; 
     339 
     340    /// Iterate on the nodes of a minimum cut 
     341     
     342    /// This iterator class lists the nodes of a minimum cut found by 
     343    /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class, 
     344    /// and call its \ref GomoryHuTree::run() "run()" method. 
     345    /// 
     346    /// This example counts the nodes in the minimum cut separating \c s from 
     347    /// \c t. 
     348    /// \code 
     349    /// GomoruHuTree<Graph> gom(g, capacities); 
     350    /// gom.run(); 
     351    /// int sum=0; 
     352    /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum; 
     353    /// \endcode 
     354    class MinCutNodeIt 
     355    { 
     356      bool _side; 
     357      typename Graph::NodeIt _node_it; 
     358      typename Graph::template NodeMap<bool> _cut; 
     359    public: 
     360      /// Constructor 
     361 
     362      /// Constructor 
     363      /// 
     364      MinCutNodeIt(GomoryHuTree const &gomory, 
     365                   ///< The GomoryHuTree class. You must call its 
     366                   ///  run() method 
     367                   ///  before initializing this iterator 
     368                   const Node& s, ///< Base node 
     369                   const Node& t, 
     370                   ///< The node you want to separate from Node s. 
     371                   bool side=true 
     372                   ///< If it is \c true (default) then the iterator lists 
     373                   ///  the nodes of the component containing \c s, 
     374                   ///  otherwise it lists the other component. 
     375                   /// \note As the minimum cut is not always unique, 
     376                   /// \code 
     377                   /// MinCutNodeIt(gomory, s, t, true); 
     378                   /// \endcode 
     379                   /// and 
     380                   /// \code 
     381                   /// MinCutNodeIt(gomory, t, s, false); 
     382                   /// \endcode 
     383                   /// does not necessarily give the same set of nodes. 
     384                   /// However it is ensured that 
     385                   /// \code 
     386                   /// MinCutNodeIt(gomory, s, t, true); 
     387                   /// \endcode 
     388                   /// and 
     389                   /// \code 
     390                   /// MinCutNodeIt(gomory, s, t, false); 
     391                   /// \endcode 
     392                   /// together list each node exactly once. 
     393                   ) 
     394        : _side(side), _cut(gomory._graph) 
     395      { 
     396        gomory.minCutMap(s,t,_cut); 
     397        for(_node_it=typename Graph::NodeIt(gomory._graph); 
     398            _node_it!=INVALID && _cut[_node_it]!=_side; 
     399            ++_node_it) {} 
     400      } 
     401      /// Conversion to Node 
     402 
     403      /// Conversion to Node 
     404      /// 
     405      operator typename Graph::Node() const 
     406      { 
     407        return _node_it; 
     408      } 
     409      bool operator==(Invalid) { return _node_it==INVALID; } 
     410      bool operator!=(Invalid) { return _node_it!=INVALID; } 
     411      /// Next node 
     412 
     413      /// Next node 
     414      /// 
     415      MinCutNodeIt &operator++() 
     416      { 
     417        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {} 
     418        return *this; 
     419      } 
     420      /// Postfix incrementation 
     421 
     422      /// Postfix incrementation 
     423      /// 
     424      /// \warning This incrementation 
     425      /// returns a \c Node, not a \ref MinCutNodeIt, as one may 
     426      /// expect. 
     427      typename Graph::Node operator++(int) 
     428      { 
     429        typename Graph::Node n=*this; 
     430        ++(*this); 
     431        return n; 
     432      } 
     433    }; 
     434     
     435    friend class MinCutEdgeIt; 
     436     
     437    /// Iterate on the edges of a minimum cut 
     438     
     439    /// This iterator class lists the edges of a minimum cut found by 
     440    /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class, 
     441    /// and call its \ref GomoryHuTree::run() "run()" method. 
     442    /// 
     443    /// This example computes the value of the minimum cut separating \c s from 
     444    /// \c t. 
     445    /// \code 
     446    /// GomoruHuTree<Graph> gom(g, capacities); 
     447    /// gom.run(); 
     448    /// int value=0; 
     449    /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e) 
     450    ///   value+=capacities[e]; 
     451    /// \endcode 
     452    /// the result will be the same as it is returned by 
     453    /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)" 
     454    class MinCutEdgeIt 
     455    { 
     456      bool _side; 
     457      const Graph &_graph; 
     458      typename Graph::NodeIt _node_it; 
     459      typename Graph::OutArcIt _arc_it; 
     460      typename Graph::template NodeMap<bool> _cut; 
     461      void step() 
     462      { 
     463        ++_arc_it; 
     464        while(_node_it!=INVALID && _arc_it==INVALID) 
     465          { 
     466            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {} 
     467            if(_node_it!=INVALID) 
     468              _arc_it=typename Graph::OutArcIt(_graph,_node_it); 
     469          } 
     470      } 
     471       
     472    public: 
     473      MinCutEdgeIt(GomoryHuTree const &gomory, 
     474                   ///< The GomoryHuTree class. You must call its 
     475                   ///  run() method 
     476                   ///  before initializing this iterator 
     477                   const Node& s,  ///< Base node 
     478                   const Node& t, 
     479                   ///< The node you want to separate from Node s. 
     480                   bool side=true 
     481                   ///< If it is \c true (default) then the listed arcs 
     482                   ///  will be oriented from the 
     483                   ///  the nodes of the component containing \c s, 
     484                   ///  otherwise they will be oriented in the opposite 
     485                   ///  direction. 
     486                   ) 
     487        : _graph(gomory._graph), _cut(_graph) 
     488      { 
     489        gomory.minCutMap(s,t,_cut); 
     490        if(!side) 
     491          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n) 
     492            _cut[n]=!_cut[n]; 
     493 
     494        for(_node_it=typename Graph::NodeIt(_graph); 
     495            _node_it!=INVALID && !_cut[_node_it]; 
     496            ++_node_it) {} 
     497        _arc_it = _node_it!=INVALID ? 
     498          typename Graph::OutArcIt(_graph,_node_it) : INVALID; 
     499        while(_node_it!=INVALID && _arc_it == INVALID) 
     500          { 
     501            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {} 
     502            if(_node_it!=INVALID) 
     503              _arc_it= typename Graph::OutArcIt(_graph,_node_it); 
     504          } 
     505        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); 
     506      } 
     507      /// Conversion to Arc 
     508 
     509      /// Conversion to Arc 
     510      /// 
     511      operator typename Graph::Arc() const 
     512      { 
     513        return _arc_it; 
     514      } 
     515      /// Conversion to Edge 
     516 
     517      /// Conversion to Edge 
     518      /// 
     519      operator typename Graph::Edge() const 
     520      { 
     521        return _arc_it; 
     522      } 
     523      bool operator==(Invalid) { return _node_it==INVALID; } 
     524      bool operator!=(Invalid) { return _node_it!=INVALID; } 
     525      /// Next edge 
     526 
     527      /// Next edge 
     528      /// 
     529      MinCutEdgeIt &operator++() 
     530      { 
     531        step(); 
     532        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); 
     533        return *this; 
     534      } 
     535      /// Postfix incrementation 
     536       
     537      /// Postfix incrementation 
     538      /// 
     539      /// \warning This incrementation 
     540      /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may 
     541      /// expect. 
     542      typename Graph::Arc operator++(int) 
     543      { 
     544        typename Graph::Arc e=*this; 
     545        ++(*this); 
     546        return e; 
     547      } 
     548    }; 
     549 
    294550  }; 
    295551 
  • test/gomory_hu_test.cc

    r590 r591  
    33#include "test_tools.h" 
    44#include <lemon/smart_graph.h> 
    5 #include <lemon/adaptors.h> 
    65#include <lemon/lgf_reader.h> 
    7 #include <lemon/lgf_writer.h> 
    8 #include <lemon/dimacs.h> 
    9 #include <lemon/time_measure.h> 
    106#include <lemon/gomory_hu_tree.h> 
    117#include <cstdlib> 
     
    7874      check(cm[u] != cm[v], "Wrong cut 3"); 
    7975      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2"); 
     76 
     77      int sum=0; 
     78      for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) 
     79        sum+=capacity[a];  
     80      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); 
     81 
     82      sum=0; 
     83      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) 
     84        sum++; 
     85      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) 
     86        sum++; 
     87      check(sum == countNodes(graph), "Problem with MinCutNodeIt"); 
    8088       
    8189    } 
Note: See TracChangeset for help on using the changeset viewer.