author Alpar Juttner Wed, 25 Feb 2009 11:10:52 +0000 changeset 544 ccd2d3a3001e parent 543 924887566bf2 child 545 e72bacfea6b7
Cut iterators for GomoryHuTree + doc cleanup + bug fixes (#66)
 lemon/gomory_hu_tree.h file | annotate | diff | comparison | revisions test/gomory_hu_test.cc file | annotate | diff | comparison | revisions
1.1 --- a/lemon/gomory_hu_tree.h	Fri Feb 20 17:17:17 2009 +0100
1.2 +++ b/lemon/gomory_hu_tree.h	Wed Feb 25 11:10:52 2009 +0000
1.3 @@ -21,6 +21,7 @@
1.5  #include <limits>
1.7 +#include <lemon/core.h>
1.8  #include <lemon/preflow.h>
1.9  #include <lemon/concept_check.h>
1.10  #include <lemon/concepts/maps.h>
1.11 @@ -35,31 +36,40 @@
1.12    ///
1.13    /// \brief Gomory-Hu cut tree algorithm
1.14    ///
1.15 -  /// The Gomory-Hu tree is a tree on the nodeset of the digraph, but it
1.16 -  /// may contain arcs which are not in the original digraph. It helps
1.17 -  /// to calculate the minimum cut between all pairs of nodes, because
1.18 -  /// the minimum capacity arc on the tree path between two nodes has
1.19 -  /// the same weight as the minimum cut in the digraph between these
1.20 -  /// nodes. Moreover this arc separates the nodes to two parts which
1.21 -  /// determine this minimum cut.
1.22 +  /// The Gomory-Hu tree is a tree on the node set of the graph, but it
1.23 +  /// may contain edges which are not in the original digraph. It has the
1.24 +  /// property that the minimum capacity edge of the path between two nodes
1.25 +  /// in this tree has the same weight as the minimum cut in the digraph
1.26 +  /// between these nodes. Moreover the components obtained by removing
1.27 +  /// this edge from the tree determine the corresponding minimum cut.
1.28 +  ///
1.29 +  /// Therefore once this tree is computed, the minimum cut between any pair
1.30 +  /// of nodes can easily be obtained.
1.31    ///
1.32 -  /// The algorithm calculates \e n-1 distinict minimum cuts with
1.33 -  /// preflow algorithm, therefore the algorithm has
1.34 +  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
1.35 +  /// the \ref Preflow algorithm), therefore the algorithm has
1.36    /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
1.37 -  /// rooted Gomory-Hu tree, the structure of the tree and the weights
1.38 -  /// can be obtained with \c predNode() and \c predValue()
1.39 -  /// functions. The \c minCutValue() and \c minCutMap() calculates
1.40 +  /// rooted Gomory-Hu tree, its structure and the weights can be obtained
1.41 +  /// by \c predNode(), \c predValue() and \c rootDist().
1.42 +  ///
1.43 +  /// The members \c minCutMap() and \c minCutValue() calculate
1.44    /// the minimum cut and the minimum cut value between any two node
1.45 -  /// in the digraph.
1.46 -  template <typename _Graph,
1.47 -	    typename _Capacity = typename _Graph::template EdgeMap<int> >
1.48 +  /// in the digraph. You can also list (iterate on) the nodes and the
1.49 +  /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
1.50 +  ///
1.51 +  /// \tparam GR The undirected graph data structure the algorithm will run on
1.52 +  /// \tparam CAP type of the EdgeMap describing the Edge capacities.
1.53 +  /// it is typename GR::template EdgeMap<int> by default.
1.54 +  template <typename GR,
1.55 +	    typename CAP = typename GR::template EdgeMap<int>
1.56 +            >
1.57    class GomoryHuTree {
1.58    public:
1.60      /// The graph type
1.61 -    typedef _Graph Graph;
1.62 -    /// The capacity on edges
1.63 -    typedef _Capacity Capacity;
1.64 +    typedef GR Graph;
1.65 +    /// The type if the edge capacity map
1.66 +    typedef CAP Capacity;
1.67      /// The value type of capacities
1.68      typedef typename Capacity::Value Value;
1.70 @@ -104,7 +114,7 @@
1.71      /// \brief Constructor
1.72      ///
1.73      /// Constructor
1.74 -    /// \param graph The graph type.
1.75 +    /// \param graph The graph the algorithm will run on.
1.76      /// \param capacity The capacity map.
1.77      GomoryHuTree(const Graph& graph, const Capacity& capacity)
1.78        : _graph(graph), _capacity(capacity),
1.79 @@ -121,10 +131,10 @@
1.80        destroyStructures();
1.81      }
1.83 -    /// \brief Initializes the internal data structures.
1.84 -    ///
1.85 -    /// Initializes the internal data structures.
1.86 -    ///
1.87 +    // \brief Initialize the internal data structures.
1.88 +    //
1.89 +    // This function initializes the internal data structures.
1.90 +    //
1.91      void init() {
1.92        createStructures();
1.94 @@ -138,9 +148,12 @@
1.95      }
1.98 -    /// \brief Starts the algorithm
1.99 -    ///
1.100 -    /// Starts the algorithm.
1.101 +    // \brief Start the algorithm
1.102 +    //
1.103 +    // This function starts the algorithm.
1.104 +    //
1.105 +    // \pre \ref init() must be called before using this function.
1.106 +    //
1.107      void start() {
1.108        Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
1.110 @@ -185,40 +198,57 @@
1.114 -    /// \brief Runs the Gomory-Hu algorithm.
1.115 +    ///\name Execution Control
1.117 +    ///@{
1.119 +    /// \brief Run the Gomory-Hu algorithm.
1.120      ///
1.121 -    /// Runs the Gomory-Hu algorithm.
1.122 -    /// \note gh.run() is just a shortcut of the following code.
1.123 -    /// \code
1.124 -    ///   ght.init();
1.125 -    ///   ght.start();
1.126 -    /// \endcode
1.127 +    /// This function runs the Gomory-Hu algorithm.
1.128      void run() {
1.129        init();
1.130        start();
1.133 +    /// @}
1.135 -    /// \brief Returns the predecessor node in the Gomory-Hu tree.
1.136 +    ///\name Query Functions
1.137 +    ///The results of the algorithm can be obtained using these
1.138 +    ///functions.\n
1.139 +    ///The \ref run() "run()" should be called before using them.\n
1.142 +    ///@{
1.144 +    /// \brief Return the predecessor node in the Gomory-Hu tree.
1.145      ///
1.146 -    /// Returns the predecessor node in the Gomory-Hu tree. If the node is
1.147 +    /// This function returns the predecessor node in the Gomory-Hu tree.
1.148 +    /// If the node is
1.149      /// the root of the Gomory-Hu tree, then it returns \c INVALID.
1.150      Node predNode(const Node& node) {
1.151        return (*_pred)[node];
1.154 -    /// \brief Returns the weight of the predecessor arc in the
1.155 +    /// \brief Return the distance from the root node in the Gomory-Hu tree.
1.156 +    ///
1.157 +    /// This function returns the distance of \c node from the root node
1.158 +    /// in the Gomory-Hu tree.
1.159 +    int rootDist(const Node& node) {
1.160 +      return (*_order)[node];
1.161 +    }
1.163 +    /// \brief Return the weight of the predecessor edge in the
1.164      /// Gomory-Hu tree.
1.165      ///
1.166 -    /// Returns the weight of the predecessor arc in the Gomory-Hu
1.167 -    /// tree.  If the node is the root of the Gomory-Hu tree, the
1.168 -    /// result is undefined.
1.169 +    /// This function returns the weight of the predecessor edge in the
1.170 +    /// Gomory-Hu tree.  If the node is the root, the result is undefined.
1.171      Value predValue(const Node& node) {
1.172        return (*_weight)[node];
1.175 -    /// \brief Returns the minimum cut value between two nodes
1.176 +    /// \brief Return the minimum cut value between two nodes
1.177      ///
1.178 -    /// Returns the minimum cut value between two nodes. The
1.179 +    /// This function returns the minimum cut value between two nodes. The
1.180      /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.181      /// tree and calculates the minimum weight arc on the paths to
1.182      /// the ancestor.
1.183 @@ -228,41 +258,52 @@
1.185        while (sn != tn) {
1.186  	if ((*_order)[sn] < (*_order)[tn]) {
1.187 -	  if ((*_weight)[tn] < value) value = (*_weight)[tn];
1.188 +	  if ((*_weight)[tn] <= value) value = (*_weight)[tn];
1.189  	  tn = (*_pred)[tn];
1.190  	} else {
1.191 -	  if ((*_weight)[sn] < value) value = (*_weight)[sn];
1.192 +	  if ((*_weight)[sn] <= value) value = (*_weight)[sn];
1.193  	  sn = (*_pred)[sn];
1.196        return value;
1.199 -    /// \brief Returns the minimum cut between two nodes
1.200 +    /// \brief Return the minimum cut between two nodes
1.201      ///
1.202 -    /// Returns the minimum cut value between two nodes. The
1.203 -    /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.204 -    /// tree and calculates the minimum weight arc on the paths to
1.205 -    /// the ancestor. Then it sets all nodes to the cut determined by
1.206 -    /// this arc. The \c cutMap should be \ref concepts::ReadWriteMap
1.207 +    /// This function returns the minimum cut between the nodes \c s and \c t
1.208 +    /// the \r cutMap parameter by setting the nodes in the component of
1.209 +    /// \c \s to true and the other nodes to false.
1.210 +    ///
1.211 +    /// The \c cutMap should be \ref concepts::ReadWriteMap
1.213 +    ///
1.214 +    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
1.215      template <typename CutMap>
1.216 -    Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
1.217 +    Value minCutMap(const Node& s, ///< Base node
1.218 +                    const Node& t,
1.219 +                    ///< The node you want to separate from Node s.
1.220 +                    CutMap& cutMap
1.221 +                    ///< The cut will be return in this map.
1.222 +                    /// It must be a \c bool \ref concepts::ReadWriteMap
1.223 +                    /// "ReadWriteMap" on the graph nodes.
1.224 +                    ) const {
1.225        Node sn = s, tn = t;
1.227 +      bool s_root=false;
1.228        Node rn = INVALID;
1.229        Value value = std::numeric_limits<Value>::max();
1.231        while (sn != tn) {
1.232  	if ((*_order)[sn] < (*_order)[tn]) {
1.233 -	  if ((*_weight)[tn] < value) {
1.234 +	  if ((*_weight)[tn] <= value) {
1.235  	    rn = tn;
1.236 +            s_root = false;
1.237  	    value = (*_weight)[tn];
1.239  	  tn = (*_pred)[tn];
1.240  	} else {
1.241 -	  if ((*_weight)[sn] < value) {
1.242 +	  if ((*_weight)[sn] <= value) {
1.243  	    rn = sn;
1.244 +            s_root = true;
1.245  	    value = (*_weight)[sn];
1.247  	  sn = (*_pred)[sn];
1.248 @@ -271,13 +312,14 @@
1.250        typename Graph::template NodeMap<bool> reached(_graph, false);
1.251        reached.set(_root, true);
1.252 -      cutMap.set(_root, false);
1.253 +      cutMap.set(_root, !s_root);
1.254        reached.set(rn, true);
1.255 -      cutMap.set(rn, true);
1.256 +      cutMap.set(rn, s_root);
1.258 +      std::vector<Node> st;
1.259        for (NodeIt n(_graph); n != INVALID; ++n) {
1.260 -	std::vector<Node> st;
1.261 -	Node nn = n;
1.262 +	st.clear();
1.263 +        Node nn = n;
1.264  	while (!reached[nn]) {
1.265  	  st.push_back(nn);
1.266  	  nn = (*_pred)[nn];
1.267 @@ -291,6 +333,220 @@
1.268        return value;
1.271 +    ///@}
1.273 +    friend class MinCutNodeIt;
1.275 +    /// Iterate on the nodes of a minimum cut
1.277 +    /// This iterator class lists the nodes of a minimum cut found by
1.278 +    /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
1.279 +    /// and call its \ref GomoryHuTree::run() "run()" method.
1.280 +    ///
1.281 +    /// This example counts the nodes in the minimum cut separating \c s from
1.282 +    /// \c t.
1.283 +    /// \code
1.284 +    /// GomoruHuTree<Graph> gom(g, capacities);
1.285 +    /// gom.run();
1.286 +    /// int sum=0;
1.287 +    /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
1.288 +    /// \endcode
1.289 +    class MinCutNodeIt
1.290 +    {
1.291 +      bool _side;
1.292 +      typename Graph::NodeIt _node_it;
1.293 +      typename Graph::template NodeMap<bool> _cut;
1.294 +    public:
1.295 +      /// Constructor
1.297 +      /// Constructor
1.298 +      ///
1.299 +      MinCutNodeIt(GomoryHuTree const &gomory,
1.300 +                   ///< The GomoryHuTree class. You must call its
1.301 +                   ///  run() method
1.302 +                   ///  before initializing this iterator
1.303 +                   const Node& s, ///< Base node
1.304 +                   const Node& t,
1.305 +                   ///< The node you want to separate from Node s.
1.306 +                   bool side=true
1.307 +                   ///< If it is \c true (default) then the iterator lists
1.308 +                   ///  the nodes of the component containing \c s,
1.309 +                   ///  otherwise it lists the other component.
1.310 +                   /// \note As the minimum cut is not always unique,
1.311 +                   /// \code
1.312 +                   /// MinCutNodeIt(gomory, s, t, true);
1.313 +                   /// \endcode
1.314 +                   /// and
1.315 +                   /// \code
1.316 +                   /// MinCutNodeIt(gomory, t, s, false);
1.317 +                   /// \endcode
1.318 +                   /// does not necessarily give the same set of nodes.
1.319 +                   /// However it is ensured that
1.320 +                   /// \code
1.321 +                   /// MinCutNodeIt(gomory, s, t, true);
1.322 +                   /// \endcode
1.323 +                   /// and
1.324 +                   /// \code
1.325 +                   /// MinCutNodeIt(gomory, s, t, false);
1.326 +                   /// \endcode
1.327 +                   /// together list each node exactly once.
1.328 +                   )
1.329 +        : _side(side), _cut(gomory._graph)
1.330 +      {
1.331 +        gomory.minCutMap(s,t,_cut);
1.332 +        for(_node_it=typename Graph::NodeIt(gomory._graph);
1.333 +            _node_it!=INVALID && _cut[_node_it]!=_side;
1.334 +            ++_node_it) {}
1.335 +      }
1.336 +      /// Conversion to Node
1.338 +      /// Conversion to Node
1.339 +      ///
1.340 +      operator typename Graph::Node() const
1.341 +      {
1.342 +        return _node_it;
1.343 +      }
1.344 +      bool operator==(Invalid) { return _node_it==INVALID; }
1.345 +      bool operator!=(Invalid) { return _node_it!=INVALID; }
1.346 +      /// Next node
1.348 +      /// Next node
1.349 +      ///
1.350 +      MinCutNodeIt &operator++()
1.351 +      {
1.352 +        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
1.353 +        return *this;
1.354 +      }
1.355 +      /// Postfix incrementation
1.357 +      /// Postfix incrementation
1.358 +      ///
1.359 +      /// \warning This incrementation
1.360 +      /// returns a \c Node, not a \ref MinCutNodeIt, as one may
1.361 +      /// expect.
1.362 +      typename Graph::Node operator++(int)
1.363 +      {
1.364 +        typename Graph::Node n=*this;
1.365 +        ++(*this);
1.366 +        return n;
1.367 +      }
1.368 +    };
1.370 +    friend class MinCutEdgeIt;
1.372 +    /// Iterate on the edges of a minimum cut
1.374 +    /// This iterator class lists the edges of a minimum cut found by
1.375 +    /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
1.376 +    /// and call its \ref GomoryHuTree::run() "run()" method.
1.377 +    ///
1.378 +    /// This example computes the value of the minimum cut separating \c s from
1.379 +    /// \c t.
1.380 +    /// \code
1.381 +    /// GomoruHuTree<Graph> gom(g, capacities);
1.382 +    /// gom.run();
1.383 +    /// int value=0;
1.384 +    /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
1.385 +    ///   value+=capacities[e];
1.386 +    /// \endcode
1.387 +    /// the result will be the same as it is returned by
1.388 +    /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"
1.389 +    class MinCutEdgeIt
1.390 +    {
1.391 +      bool _side;
1.392 +      const Graph &_graph;
1.393 +      typename Graph::NodeIt _node_it;
1.394 +      typename Graph::OutArcIt _arc_it;
1.395 +      typename Graph::template NodeMap<bool> _cut;
1.396 +      void step()
1.397 +      {
1.398 +        ++_arc_it;
1.399 +        while(_node_it!=INVALID && _arc_it==INVALID)
1.400 +          {
1.401 +            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
1.402 +            if(_node_it!=INVALID)
1.403 +              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
1.404 +          }
1.405 +      }
1.407 +    public:
1.408 +      MinCutEdgeIt(GomoryHuTree const &gomory,
1.409 +                   ///< The GomoryHuTree class. You must call its
1.410 +                   ///  run() method
1.411 +                   ///  before initializing this iterator
1.412 +                   const Node& s,  ///< Base node
1.413 +                   const Node& t,
1.414 +                   ///< The node you want to separate from Node s.
1.415 +                   bool side=true
1.416 +                   ///< If it is \c true (default) then the listed arcs
1.417 +                   ///  will be oriented from the
1.418 +                   ///  the nodes of the component containing \c s,
1.419 +                   ///  otherwise they will be oriented in the opposite
1.420 +                   ///  direction.
1.421 +                   )
1.422 +        : _graph(gomory._graph), _cut(_graph)
1.423 +      {
1.424 +        gomory.minCutMap(s,t,_cut);
1.425 +        if(!side)
1.426 +          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
1.427 +            _cut[n]=!_cut[n];
1.429 +        for(_node_it=typename Graph::NodeIt(_graph);
1.430 +            _node_it!=INVALID && !_cut[_node_it];
1.431 +            ++_node_it) {}
1.432 +        _arc_it = _node_it!=INVALID ?
1.433 +          typename Graph::OutArcIt(_graph,_node_it) : INVALID;
1.434 +        while(_node_it!=INVALID && _arc_it == INVALID)
1.435 +          {
1.436 +            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
1.437 +            if(_node_it!=INVALID)
1.438 +              _arc_it= typename Graph::OutArcIt(_graph,_node_it);
1.439 +          }
1.440 +        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
1.441 +      }
1.442 +      /// Conversion to Arc
1.444 +      /// Conversion to Arc
1.445 +      ///
1.446 +      operator typename Graph::Arc() const
1.447 +      {
1.448 +        return _arc_it;
1.449 +      }
1.450 +      /// Conversion to Edge
1.452 +      /// Conversion to Edge
1.453 +      ///
1.454 +      operator typename Graph::Edge() const
1.455 +      {
1.456 +        return _arc_it;
1.457 +      }
1.458 +      bool operator==(Invalid) { return _node_it==INVALID; }
1.459 +      bool operator!=(Invalid) { return _node_it!=INVALID; }
1.460 +      /// Next edge
1.462 +      /// Next edge
1.463 +      ///
1.464 +      MinCutEdgeIt &operator++()
1.465 +      {
1.466 +        step();
1.467 +        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
1.468 +        return *this;
1.469 +      }
1.470 +      /// Postfix incrementation
1.472 +      /// Postfix incrementation
1.473 +      ///
1.474 +      /// \warning This incrementation
1.475 +      /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
1.476 +      /// expect.
1.477 +      typename Graph::Arc operator++(int)
1.478 +      {
1.479 +        typename Graph::Arc e=*this;
1.480 +        ++(*this);
1.481 +        return e;
1.482 +      }
1.483 +    };
1.485    };
2.1 --- a/test/gomory_hu_test.cc	Fri Feb 20 17:17:17 2009 +0100
2.2 +++ b/test/gomory_hu_test.cc	Wed Feb 25 11:10:52 2009 +0000
2.3 @@ -2,11 +2,7 @@
2.5  #include "test_tools.h"
2.6  #include <lemon/smart_graph.h>
2.9 -#include <lemon/lgf_writer.h>
2.10 -#include <lemon/dimacs.h>
2.11 -#include <lemon/time_measure.h>
2.12  #include <lemon/gomory_hu_tree.h>
2.13  #include <cstdlib>
2.15 @@ -77,6 +73,18 @@
2.16        check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
2.17        check(cm[u] != cm[v], "Wrong cut 3");
2.18        check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
2.19 +
2.20 +      int sum=0;
2.21 +      for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
2.22 +        sum+=capacity[a];
2.23 +      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
2.24 +
2.25 +      sum=0;
2.26 +      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
2.27 +        sum++;
2.28 +      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
2.29 +        sum++;
2.30 +      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
2.32      }
2.33    }