Cut iterators for GomoryHuTree + doc cleanup + bug fixes (#66)
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 25 Feb 2009 11:10:52 +0000
changeset 591ccd2d3a3001e
parent 590 924887566bf2
child 592 e72bacfea6b7
Cut iterators for GomoryHuTree + doc cleanup + bug fixes (#66)
lemon/gomory_hu_tree.h
test/gomory_hu_test.cc
     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.4  
     1.5  #include <limits>
     1.6  
     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.59  
    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.69      
    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.82  
    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.93  
    1.94 @@ -138,9 +148,12 @@
    1.95      }
    1.96  
    1.97  
    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.109  
   1.110 @@ -185,40 +198,57 @@
   1.111        }
   1.112      }
   1.113  
   1.114 -    /// \brief Runs the Gomory-Hu algorithm.  
   1.115 +    ///\name Execution Control
   1.116 + 
   1.117 +    ///@{
   1.118 +
   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.131      }
   1.132 +    
   1.133 +    /// @}
   1.134  
   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.140 +    ///See also MinCutNodeIt and MinCutEdgeIt
   1.141 +
   1.142 +    ///@{
   1.143 +
   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.152      }
   1.153  
   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.162 +
   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.173      }
   1.174  
   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.184        
   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.194  	}
   1.195        }
   1.196        return value;
   1.197      }
   1.198  
   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.212      /// "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.226 -
   1.227 +      bool s_root=false;
   1.228        Node rn = INVALID;
   1.229        Value value = std::numeric_limits<Value>::max();
   1.230        
   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.238  	  }
   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.246  	  }
   1.247  	  sn = (*_pred)[sn];
   1.248 @@ -271,13 +312,14 @@
   1.249  
   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.257  
   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.269      }
   1.270  
   1.271 +    ///@}
   1.272 +
   1.273 +    friend class MinCutNodeIt;
   1.274 +
   1.275 +    /// Iterate on the nodes of a minimum cut
   1.276 +    
   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.296 +
   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.337 +
   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.347 +
   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.356 +
   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.369 +    
   1.370 +    friend class MinCutEdgeIt;
   1.371 +    
   1.372 +    /// Iterate on the edges of a minimum cut
   1.373 +    
   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.406 +      
   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.428 +
   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.443 +
   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.451 +
   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.461 +
   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.471 +      
   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.484 +
   1.485    };
   1.486  
   1.487  }
     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.4  
     2.5  #include "test_tools.h"
     2.6  #include <lemon/smart_graph.h>
     2.7 -#include <lemon/adaptors.h>
     2.8  #include <lemon/lgf_reader.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.14  
    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.31        
    2.32      }
    2.33    }