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;