# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1236174969 -3600
# Node ID d6b40ebb26175685ef0bea3cd3a8c01212ba9b5e
# Parent e72bacfea6b78fd9d84df2128824bc027f6e5afa
Doc improvements in GomoryHu (#66)
And make init() and start() private + bug fix in the test file.
diff -r e72bacfea6b7 -r d6b40ebb2617 lemon/gomory_hu.h
--- a/lemon/gomory_hu.h Wed Feb 25 11:10:57 2009 +0000
+++ b/lemon/gomory_hu.h Wed Mar 04 14:56:09 2009 +0100
@@ -36,10 +36,10 @@
///
/// \brief Gomory-Hu cut tree algorithm
///
- /// The Gomory-Hu tree is a tree on the node set of the graph, but it
- /// may contain edges which are not in the original digraph. It has the
+ /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
+ /// may contain edges which are not in the original graph. It has the
/// property that the minimum capacity edge of the path between two nodes
- /// in this tree has the same weight as the minimum cut in the digraph
+ /// in this tree has the same weight as the minimum cut in the graph
/// between these nodes. Moreover the components obtained by removing
/// this edge from the tree determine the corresponding minimum cut.
///
@@ -53,22 +53,26 @@
/// by \c predNode(), \c predValue() and \c rootDist().
///
/// The members \c minCutMap() and \c minCutValue() calculate
- /// the minimum cut and the minimum cut value between any two node
- /// in the digraph. You can also list (iterate on) the nodes and the
- /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
+ /// the minimum cut and the minimum cut value between any two nodes
+ /// in the graph. You can also list (iterate on) the nodes and the
+ /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
///
- /// \tparam GR The undirected graph data structure the algorithm will run on
- /// \tparam CAP type of the EdgeMap describing the Edge capacities.
- /// it is typename GR::template EdgeMap<int> by default.
+ /// \tparam GR The type of the undirected graph the algorithm runs on.
+ /// \tparam CAP The type of the edge map describing the edge capacities.
+ /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
+#ifdef DOXYGEN
template <typename GR,
- typename CAP = typename GR::template EdgeMap<int>
- >
+ typename CAP>
+#else
+ template <typename GR,
+ typename CAP = typename GR::template EdgeMap<int> >
+#endif
class GomoryHu {
public:
/// The graph type
typedef GR Graph;
- /// The type if the edge capacity map
+ /// The type of the edge capacity map
typedef CAP Capacity;
/// The value type of capacities
typedef typename Capacity::Value Value;
@@ -114,8 +118,8 @@
/// \brief Constructor
///
/// Constructor
- /// \param graph The graph the algorithm will run on.
- /// \param capacity The capacity map.
+ /// \param graph The undirected graph the algorithm runs on.
+ /// \param capacity The edge capacity map.
GomoryHu(const Graph& graph, const Capacity& capacity)
: _graph(graph), _capacity(capacity),
_pred(0), _weight(0), _order(0)
@@ -131,10 +135,9 @@
destroyStructures();
}
- // \brief Initialize the internal data structures.
- //
- // This function initializes the internal data structures.
- //
+ private:
+
+ // Initialize the internal data structures
void init() {
createStructures();
@@ -148,12 +151,7 @@
}
- // \brief Start the algorithm
- //
- // This function starts the algorithm.
- //
- // \pre \ref init() must be called before using this function.
- //
+ // Start the algorithm
void start() {
Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
@@ -198,6 +196,8 @@
}
}
+ public:
+
///\name Execution Control
///@{
@@ -215,8 +215,8 @@
///\name Query Functions
///The results of the algorithm can be obtained using these
///functions.\n
- ///The \ref run() "run()" should be called before using them.\n
- ///See also MinCutNodeIt and MinCutEdgeIt
+ ///\ref run() "run()" should be called before using them.\n
+ ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
///@{
@@ -250,7 +250,7 @@
///
/// This function returns the minimum cut value between two nodes. The
/// algorithm finds the nearest common ancestor in the Gomory-Hu
- /// tree and calculates the minimum weight arc on the paths to
+ /// tree and calculates the minimum weight edge on the paths to
/// the ancestor.
Value minCutValue(const Node& s, const Node& t) const {
Node sn = s, tn = t;
@@ -271,21 +271,19 @@
/// \brief Return the minimum cut between two nodes
///
/// This function returns the minimum cut between the nodes \c s and \c t
- /// the \r cutMap parameter by setting the nodes in the component of
- /// \c \s to true and the other nodes to false.
+ /// in the \c cutMap parameter by setting the nodes in the component of
+ /// \c s to \c true and the other nodes to \c false.
///
- /// The \c cutMap should be \ref concepts::ReadWriteMap
- /// "ReadWriteMap".
- ///
- /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
+ /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
template <typename CutMap>
- Value minCutMap(const Node& s, ///< Base node
+ Value minCutMap(const Node& s, ///< The base node.
const Node& t,
- ///< The node you want to separate from Node s.
+ ///< The node you want to separate from node \c s.
CutMap& cutMap
- ///< The cut will be return in this map.
- /// It must be a \c bool \ref concepts::ReadWriteMap
- /// "ReadWriteMap" on the graph nodes.
+ ///< The cut will be returned in this map.
+ /// It must be a \c bool (or convertible)
+ /// \ref concepts::ReadWriteMap "ReadWriteMap"
+ /// on the graph nodes.
) const {
Node sn = s, tn = t;
bool s_root=false;
@@ -348,8 +346,8 @@
/// \code
/// GomoruHu<Graph> gom(g, capacities);
/// gom.run();
- /// int sum=0;
- /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
+ /// int cnt=0;
+ /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
/// \endcode
class MinCutNodeIt
{
@@ -359,15 +357,15 @@
public:
/// Constructor
- /// Constructor
+ /// Constructor.
///
MinCutNodeIt(GomoryHu const &gomory,
///< The GomoryHu class. You must call its
/// run() method
- /// before initializing this iterator
- const Node& s, ///< Base node
+ /// before initializing this iterator.
+ const Node& s, ///< The base node.
const Node& t,
- ///< The node you want to separate from Node s.
+ ///< The node you want to separate from node \c s.
bool side=true
///< If it is \c true (default) then the iterator lists
/// the nodes of the component containing \c s,
@@ -398,9 +396,9 @@
_node_it!=INVALID && _cut[_node_it]!=_side;
++_node_it) {}
}
- /// Conversion to Node
+ /// Conversion to \c Node
- /// Conversion to Node
+ /// Conversion to \c Node.
///
operator typename Graph::Node() const
{
@@ -410,7 +408,7 @@
bool operator!=(Invalid) { return _node_it!=INVALID; }
/// Next node
- /// Next node
+ /// Next node.
///
MinCutNodeIt &operator++()
{
@@ -419,10 +417,10 @@
}
/// Postfix incrementation
- /// Postfix incrementation
+ /// Postfix incrementation.
///
/// \warning This incrementation
- /// returns a \c Node, not a \ref MinCutNodeIt, as one may
+ /// returns a \c Node, not a \c MinCutNodeIt, as one may
/// expect.
typename Graph::Node operator++(int)
{
@@ -446,11 +444,11 @@
/// GomoruHu<Graph> gom(g, capacities);
/// gom.run();
/// int value=0;
- /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
+ /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
/// value+=capacities[e];
/// \endcode
/// the result will be the same as it is returned by
- /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)"
+ /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
class MinCutEdgeIt
{
bool _side;
@@ -473,10 +471,10 @@
MinCutEdgeIt(GomoryHu const &gomory,
///< The GomoryHu class. You must call its
/// run() method
- /// before initializing this iterator
- const Node& s, ///< Base node
+ /// before initializing this iterator.
+ const Node& s, ///< The base node.
const Node& t,
- ///< The node you want to separate from Node s.
+ ///< The node you want to separate from node \c s.
bool side=true
///< If it is \c true (default) then the listed arcs
/// will be oriented from the
@@ -504,17 +502,17 @@
}
while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
}
- /// Conversion to Arc
+ /// Conversion to \c Arc
- /// Conversion to Arc
+ /// Conversion to \c Arc.
///
operator typename Graph::Arc() const
{
return _arc_it;
}
- /// Conversion to Edge
+ /// Conversion to \c Edge
- /// Conversion to Edge
+ /// Conversion to \c Edge.
///
operator typename Graph::Edge() const
{
@@ -524,7 +522,7 @@
bool operator!=(Invalid) { return _node_it!=INVALID; }
/// Next edge
- /// Next edge
+ /// Next edge.
///
MinCutEdgeIt &operator++()
{
@@ -534,11 +532,10 @@
}
/// Postfix incrementation
- /// Postfix incrementation
+ /// Postfix incrementation.
///
/// \warning This incrementation
- /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
- /// expect.
+ /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
typename Graph::Arc operator++(int)
{
typename Graph::Arc e=*this;
diff -r e72bacfea6b7 -r d6b40ebb2617 test/gomory_hu_test.cc
--- a/test/gomory_hu_test.cc Wed Feb 25 11:10:57 2009 +0000
+++ b/test/gomory_hu_test.cc Wed Mar 04 14:56:09 2009 +0100
@@ -61,7 +61,6 @@
edgeMap("capacity", capacity).run();
GomoryHu<Graph> ght(graph, capacity);
- ght.init();
ght.run();
for (NodeIt u(graph); u != INVALID; ++u) {