author Peter Kovacs Wed, 04 Mar 2009 14:56:09 +0100 changeset 593 d6b40ebb2617 parent 592 e72bacfea6b7 child 594 d59dcc933e59
Doc improvements in GomoryHu (#66)
And make init() and start() private + bug fix in the test file.
 lemon/gomory_hu.h file | annotate | diff | comparison | revisions test/gomory_hu_test.cc file | annotate | diff | comparison | revisions
     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.107 +    ///\ref run() "run()" should be called before using them.\n
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.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.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) {