COIN-OR::LEMON - Graph Library

Changeset 591:ccd2d3a3001e in lemon


Ignore:
Timestamp:
02/25/09 12:10:52 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
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.