Doc improvements in GomoryHu (#66)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 04 Mar 2009 14:56:09 +0100 (2009-03-04)
changeset 546d6b40ebb2617
parent 545 e72bacfea6b7
child 547 d59dcc933e59
Doc improvements in GomoryHu (#66)
And make init() and start() private + bug fix in the test file.
lemon/gomory_hu.h
test/gomory_hu_test.cc
     1.1 --- a/lemon/gomory_hu.h	Wed Feb 25 11:10:57 2009 +0000
     1.2 +++ b/lemon/gomory_hu.h	Wed Mar 04 14:56:09 2009 +0100
     1.3 @@ -36,10 +36,10 @@
     1.4    ///
     1.5    /// \brief Gomory-Hu cut tree algorithm
     1.6    ///
     1.7 -  /// The Gomory-Hu tree is a tree on the node set of the graph, but it
     1.8 -  /// may contain edges which are not in the original digraph. It has the
     1.9 +  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
    1.10 +  /// may contain edges which are not in the original graph. It has the
    1.11    /// property that the minimum capacity edge of the path between two nodes 
    1.12 -  /// in this tree has the same weight as the minimum cut in the digraph
    1.13 +  /// in this tree has the same weight as the minimum cut in the graph
    1.14    /// between these nodes. Moreover the components obtained by removing
    1.15    /// this edge from the tree determine the corresponding minimum cut.
    1.16    ///
    1.17 @@ -53,22 +53,26 @@
    1.18    /// by \c predNode(), \c predValue() and \c rootDist().
    1.19    /// 
    1.20    /// The members \c minCutMap() and \c minCutValue() calculate
    1.21 -  /// the minimum cut and the minimum cut value between any two node
    1.22 -  /// in the digraph. You can also list (iterate on) the nodes and the
    1.23 -  /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
    1.24 +  /// the minimum cut and the minimum cut value between any two nodes
    1.25 +  /// in the graph. You can also list (iterate on) the nodes and the
    1.26 +  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
    1.27    ///
    1.28 -  /// \tparam GR The undirected graph data structure the algorithm will run on
    1.29 -  /// \tparam CAP type of the EdgeMap describing the Edge capacities.
    1.30 -  /// it is typename GR::template EdgeMap<int> by default.
    1.31 +  /// \tparam GR The type of the undirected graph the algorithm runs on.
    1.32 +  /// \tparam CAP The type of the edge map describing the edge capacities.
    1.33 +  /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
    1.34 +#ifdef DOXYGEN
    1.35    template <typename GR,
    1.36 -	    typename CAP = typename GR::template EdgeMap<int>
    1.37 -            >
    1.38 +	    typename CAP>
    1.39 +#else
    1.40 +  template <typename GR,
    1.41 +	    typename CAP = typename GR::template EdgeMap<int> >
    1.42 +#endif
    1.43    class GomoryHu {
    1.44    public:
    1.45  
    1.46      /// The graph type
    1.47      typedef GR Graph;
    1.48 -    /// The type if the edge capacity map
    1.49 +    /// The type of the edge capacity map
    1.50      typedef CAP Capacity;
    1.51      /// The value type of capacities
    1.52      typedef typename Capacity::Value Value;
    1.53 @@ -114,8 +118,8 @@
    1.54      /// \brief Constructor
    1.55      ///
    1.56      /// Constructor
    1.57 -    /// \param graph The graph the algorithm will run on.
    1.58 -    /// \param capacity The capacity map.
    1.59 +    /// \param graph The undirected graph the algorithm runs on.
    1.60 +    /// \param capacity The edge capacity map.
    1.61      GomoryHu(const Graph& graph, const Capacity& capacity) 
    1.62        : _graph(graph), _capacity(capacity),
    1.63  	_pred(0), _weight(0), _order(0) 
    1.64 @@ -131,10 +135,9 @@
    1.65        destroyStructures();
    1.66      }
    1.67  
    1.68 -    // \brief Initialize the internal data structures.
    1.69 -    //
    1.70 -    // This function initializes the internal data structures.
    1.71 -    //
    1.72 +  private:
    1.73 +  
    1.74 +    // Initialize the internal data structures
    1.75      void init() {
    1.76        createStructures();
    1.77  
    1.78 @@ -148,12 +151,7 @@
    1.79      }
    1.80  
    1.81  
    1.82 -    // \brief Start the algorithm
    1.83 -    //
    1.84 -    // This function starts the algorithm.
    1.85 -    //
    1.86 -    // \pre \ref init() must be called before using this function.
    1.87 -    //
    1.88 +    // Start the algorithm
    1.89      void start() {
    1.90        Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
    1.91  
    1.92 @@ -198,6 +196,8 @@
    1.93        }
    1.94      }
    1.95  
    1.96 +  public:
    1.97 +
    1.98      ///\name Execution Control
    1.99   
   1.100      ///@{
   1.101 @@ -215,8 +215,8 @@
   1.102      ///\name Query Functions
   1.103      ///The results of the algorithm can be obtained using these
   1.104      ///functions.\n
   1.105 -    ///The \ref run() "run()" should be called before using them.\n
   1.106 -    ///See also MinCutNodeIt and MinCutEdgeIt
   1.107 +    ///\ref run() "run()" should be called before using them.\n
   1.108 +    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
   1.109  
   1.110      ///@{
   1.111  
   1.112 @@ -250,7 +250,7 @@
   1.113      ///
   1.114      /// This function returns the minimum cut value between two nodes. The
   1.115      /// algorithm finds the nearest common ancestor in the Gomory-Hu
   1.116 -    /// tree and calculates the minimum weight arc on the paths to
   1.117 +    /// tree and calculates the minimum weight edge on the paths to
   1.118      /// the ancestor.
   1.119      Value minCutValue(const Node& s, const Node& t) const {
   1.120        Node sn = s, tn = t;
   1.121 @@ -271,21 +271,19 @@
   1.122      /// \brief Return the minimum cut between two nodes
   1.123      ///
   1.124      /// This function returns the minimum cut between the nodes \c s and \c t
   1.125 -    /// the \r cutMap parameter by setting the nodes in the component of
   1.126 -    /// \c \s to true and the other nodes to false.
   1.127 +    /// in the \c cutMap parameter by setting the nodes in the component of
   1.128 +    /// \c s to \c true and the other nodes to \c false.
   1.129      ///
   1.130 -    /// The \c cutMap should be \ref concepts::ReadWriteMap
   1.131 -    /// "ReadWriteMap".
   1.132 -    ///
   1.133 -    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
   1.134 +    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
   1.135      template <typename CutMap>
   1.136 -    Value minCutMap(const Node& s, ///< Base node
   1.137 +    Value minCutMap(const Node& s, ///< The base node.
   1.138                      const Node& t,
   1.139 -                    ///< The node you want to separate from Node s.
   1.140 +                    ///< The node you want to separate from node \c s.
   1.141                      CutMap& cutMap
   1.142 -                    ///< The cut will be return in this map.
   1.143 -                    /// It must be a \c bool \ref concepts::ReadWriteMap
   1.144 -                    /// "ReadWriteMap" on the graph nodes.
   1.145 +                    ///< The cut will be returned in this map.
   1.146 +                    /// It must be a \c bool (or convertible) 
   1.147 +                    /// \ref concepts::ReadWriteMap "ReadWriteMap"
   1.148 +                    /// on the graph nodes.
   1.149                      ) const {
   1.150        Node sn = s, tn = t;
   1.151        bool s_root=false;
   1.152 @@ -348,8 +346,8 @@
   1.153      /// \code
   1.154      /// GomoruHu<Graph> gom(g, capacities);
   1.155      /// gom.run();
   1.156 -    /// int sum=0;
   1.157 -    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
   1.158 +    /// int cnt=0;
   1.159 +    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
   1.160      /// \endcode
   1.161      class MinCutNodeIt
   1.162      {
   1.163 @@ -359,15 +357,15 @@
   1.164      public:
   1.165        /// Constructor
   1.166  
   1.167 -      /// Constructor
   1.168 +      /// Constructor.
   1.169        ///
   1.170        MinCutNodeIt(GomoryHu const &gomory,
   1.171                     ///< The GomoryHu class. You must call its
   1.172                     ///  run() method
   1.173 -                   ///  before initializing this iterator
   1.174 -                   const Node& s, ///< Base node
   1.175 +                   ///  before initializing this iterator.
   1.176 +                   const Node& s, ///< The base node.
   1.177                     const Node& t,
   1.178 -                   ///< The node you want to separate from Node s.
   1.179 +                   ///< The node you want to separate from node \c s.
   1.180                     bool side=true
   1.181                     ///< If it is \c true (default) then the iterator lists
   1.182                     ///  the nodes of the component containing \c s,
   1.183 @@ -398,9 +396,9 @@
   1.184              _node_it!=INVALID && _cut[_node_it]!=_side;
   1.185              ++_node_it) {}
   1.186        }
   1.187 -      /// Conversion to Node
   1.188 +      /// Conversion to \c Node
   1.189  
   1.190 -      /// Conversion to Node
   1.191 +      /// Conversion to \c Node.
   1.192        ///
   1.193        operator typename Graph::Node() const
   1.194        {
   1.195 @@ -410,7 +408,7 @@
   1.196        bool operator!=(Invalid) { return _node_it!=INVALID; }
   1.197        /// Next node
   1.198  
   1.199 -      /// Next node
   1.200 +      /// Next node.
   1.201        ///
   1.202        MinCutNodeIt &operator++()
   1.203        {
   1.204 @@ -419,10 +417,10 @@
   1.205        }
   1.206        /// Postfix incrementation
   1.207  
   1.208 -      /// Postfix incrementation
   1.209 +      /// Postfix incrementation.
   1.210        ///
   1.211        /// \warning This incrementation
   1.212 -      /// returns a \c Node, not a \ref MinCutNodeIt, as one may
   1.213 +      /// returns a \c Node, not a \c MinCutNodeIt, as one may
   1.214        /// expect.
   1.215        typename Graph::Node operator++(int)
   1.216        {
   1.217 @@ -446,11 +444,11 @@
   1.218      /// GomoruHu<Graph> gom(g, capacities);
   1.219      /// gom.run();
   1.220      /// int value=0;
   1.221 -    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
   1.222 +    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
   1.223      ///   value+=capacities[e];
   1.224      /// \endcode
   1.225      /// the result will be the same as it is returned by
   1.226 -    /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)"
   1.227 +    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
   1.228      class MinCutEdgeIt
   1.229      {
   1.230        bool _side;
   1.231 @@ -473,10 +471,10 @@
   1.232        MinCutEdgeIt(GomoryHu const &gomory,
   1.233                     ///< The GomoryHu class. You must call its
   1.234                     ///  run() method
   1.235 -                   ///  before initializing this iterator
   1.236 -                   const Node& s,  ///< Base node
   1.237 +                   ///  before initializing this iterator.
   1.238 +                   const Node& s,  ///< The base node.
   1.239                     const Node& t,
   1.240 -                   ///< The node you want to separate from Node s.
   1.241 +                   ///< The node you want to separate from node \c s.
   1.242                     bool side=true
   1.243                     ///< If it is \c true (default) then the listed arcs
   1.244                     ///  will be oriented from the
   1.245 @@ -504,17 +502,17 @@
   1.246            }
   1.247          while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
   1.248        }
   1.249 -      /// Conversion to Arc
   1.250 +      /// Conversion to \c Arc
   1.251  
   1.252 -      /// Conversion to Arc
   1.253 +      /// Conversion to \c Arc.
   1.254        ///
   1.255        operator typename Graph::Arc() const
   1.256        {
   1.257          return _arc_it;
   1.258        }
   1.259 -      /// Conversion to Edge
   1.260 +      /// Conversion to \c Edge
   1.261  
   1.262 -      /// Conversion to Edge
   1.263 +      /// Conversion to \c Edge.
   1.264        ///
   1.265        operator typename Graph::Edge() const
   1.266        {
   1.267 @@ -524,7 +522,7 @@
   1.268        bool operator!=(Invalid) { return _node_it!=INVALID; }
   1.269        /// Next edge
   1.270  
   1.271 -      /// Next edge
   1.272 +      /// Next edge.
   1.273        ///
   1.274        MinCutEdgeIt &operator++()
   1.275        {
   1.276 @@ -534,11 +532,10 @@
   1.277        }
   1.278        /// Postfix incrementation
   1.279        
   1.280 -      /// Postfix incrementation
   1.281 +      /// Postfix incrementation.
   1.282        ///
   1.283        /// \warning This incrementation
   1.284 -      /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
   1.285 -      /// expect.
   1.286 +      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
   1.287        typename Graph::Arc operator++(int)
   1.288        {
   1.289          typename Graph::Arc e=*this;
     2.1 --- a/test/gomory_hu_test.cc	Wed Feb 25 11:10:57 2009 +0000
     2.2 +++ b/test/gomory_hu_test.cc	Wed Mar 04 14:56:09 2009 +0100
     2.3 @@ -61,7 +61,6 @@
     2.4      edgeMap("capacity", capacity).run();
     2.5  
     2.6    GomoryHu<Graph> ght(graph, capacity);
     2.7 -  ght.init();
     2.8    ght.run();
     2.9  
    2.10    for (NodeIt u(graph); u != INVALID; ++u) {