lemon-main: comparison lemon/gomory

equal deleted inserted replaced

-:3d1f90a60bc6
+:25aa2f18c735
 /// \ingroup min_cut
 ///
 /// \brief Gomory-Hu cut tree algorithm
 ///
-/// The Gomory-Hu tree is a tree on the node set of the graph, but it
+/// 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 digraph. It has the
+/// 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.
 ///
 /// Therefore once this tree is computed, the minimum cut between any pair
 /// of nodes can easily be obtained.
 /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
 /// rooted Gomory-Hu tree, its structure and the weights can be obtained
 /// 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
+/// the minimum cut and the minimum cut value between any two nodes
-/// in the digraph. You can also list (iterate on) the nodes and the
+/// in the graph. You can also list (iterate on) the nodes and the
-/// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
+/// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
 ///
-/// \tparam GR The undirected graph data structure the algorithm will run on
+/// \tparam GR The type of the undirected graph the algorithm runs on.
-/// \tparam CAP type of the EdgeMap describing the Edge capacities.
+/// \tparam CAP The type of the edge map describing the edge capacities.
-/// it is typename GR::template EdgeMap<int> by default.
+/// 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;
 private:
 public:
 /// \brief Constructor
 ///
 /// Constructor
-/// \param graph The graph the algorithm will run on.
+/// \param graph The undirected graph the algorithm runs on.
-/// \param capacity The capacity map.
+/// \param capacity The edge capacity map.
 GomoryHu(const Graph& graph, const Capacity& capacity)
 : _graph(graph), _capacity(capacity),
 	_pred(0), _weight(0), _order(0)
 {
 checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
 /// Destructor
 ~GomoryHu() {
 destroyStructures();
 }
-// \brief Initialize the internal data structures.
+private:
-//
-// This function initializes the internal data structures.
+// Initialize the internal data structures
-//
 void init() {
 createStructures();
 _root = NodeIt(_graph);
 for (NodeIt n(_graph); n != INVALID; ++n) {
 _pred->set(_root, INVALID);
 _weight->set(_root, std::numeric_limits<Value>::max());
 }
-// \brief Start the algorithm
+// Start the algorithm
-//
-// This function starts the algorithm.
-//
-// \pre \ref init() must be called before using this function.
-//
 void start() {
 Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
 for (NodeIt n(_graph); n != INVALID; ++n) {
 	if (n == _root) continue;
 	  st.pop_back();
 	}
 }
 }
+public:
 ///\name Execution Control
 ///@{
 /// \brief Run the Gomory-Hu algorithm.
 /// @}
 ///\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
+///\ref run() "run()" should be called before using them.\n
-///See also MinCutNodeIt and MinCutEdgeIt
+///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
 ///@{
 /// \brief Return the predecessor node in the Gomory-Hu tree.
 ///
 /// \brief Return the minimum cut value between two nodes
 ///
 /// 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;
 Value value = std::numeric_limits<Value>::max();
 }
 /// \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
+/// in the \c cutMap parameter by setting the nodes in the component of
-/// \c \s to true and the other nodes to false.
+/// \c s to \c true and the other nodes to \c false.
 ///
-/// The \c cutMap should be \ref concepts::ReadWriteMap
+/// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
-/// "ReadWriteMap".
-///
-/// 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.
+///< The cut will be returned in this map.
-/// It must be a \c bool \ref concepts::ReadWriteMap
+/// It must be a \c bool (or convertible)
-/// "ReadWriteMap" on the graph nodes.
+/// \ref concepts::ReadWriteMap "ReadWriteMap"
+/// on the graph nodes.
 ) const {
 Node sn = s, tn = t;
 bool s_root=false;
 Node rn = INVALID;
 Value value = std::numeric_limits<Value>::max();
 /// This example counts the nodes in the minimum cut separating \c s from
 /// \c t.
 /// \code
 /// GomoruHu<Graph> gom(g, capacities);
 /// gom.run();
-/// int sum=0;
+/// int cnt=0;
-/// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
+/// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
 /// \endcode
 class MinCutNodeIt
 {
 bool _side;
 typename Graph::NodeIt _node_it;
 typename Graph::template NodeMap<bool> _cut;
 public:
 /// Constructor
-/// Constructor
+/// Constructor.
 ///
 MinCutNodeIt(GomoryHu const &gomory,
 ///< The GomoryHu class. You must call its
 ///  run() method
-///  before initializing this iterator
+///  before initializing this iterator.
-const Node& s, ///< Base node
+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,
 ///  otherwise it lists the other component.
 /// \note As the minimum cut is not always unique,
 gomory.minCutMap(s,t,_cut);
 for(_node_it=typename Graph::NodeIt(gomory._graph);
 _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
 {
 return _node_it;
 }
 bool operator==(Invalid) { return _node_it==INVALID; }
 bool operator!=(Invalid) { return _node_it!=INVALID; }
 /// Next node
-/// Next node
+/// Next node.
 ///
 MinCutNodeIt &operator++()
 {
 for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
 return *this;
 }
 /// 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)
 {
 typename Graph::Node n=*this;
 ++(*this);
 /// \c t.
 /// \code
 /// 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;
 const Graph &_graph;
 typename Graph::NodeIt _node_it;
 public:
 MinCutEdgeIt(GomoryHu const &gomory,
 ///< The GomoryHu class. You must call its
 ///  run() method
-///  before initializing this iterator
+///  before initializing this iterator.
-const Node& s,  ///< Base node
+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
 ///  the nodes of the component containing \c s,
 ///  otherwise they will be oriented in the opposite
 if(_node_it!=INVALID)
 _arc_it= typename Graph::OutArcIt(_graph,_node_it);
 }
 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
 {
 return _arc_it;
 }
 bool operator==(Invalid) { return _node_it==INVALID; }
 bool operator!=(Invalid) { return _node_it!=INVALID; }
 /// Next edge
-/// Next edge
+/// Next edge.
 ///
 MinCutEdgeIt &operator++()
 {
 step();
 while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
 return *this;
 }
 /// Postfix incrementation
-/// Postfix incrementation
+/// Postfix incrementation.
 ///
 /// \warning This incrementation
-/// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
+/// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
-/// expect.
 typename Graph::Arc operator++(int)
 {
 typename Graph::Arc e=*this;
 ++(*this);
 return e;

changeset 555	b779c4dc7496
parent 545	e72bacfea6b7
child 581	aa1804409f29