lemon-main: comparison lemon/gomory

equal deleted inserted replaced

-:72803c0e12f5
+:02c9547e1525
 /// 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 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.
 ///
 /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
-/// the \ref Preflow algorithm), therefore the algorithm has
+/// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
-/// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
+/// time complexity. It calculates a rooted Gomory-Hu tree.
-/// rooted Gomory-Hu tree, its structure and the weights can be obtained
+/// The structure of the tree and the edge weights can be
-/// by \c predNode(), \c predValue() and \c rootDist().
+/// obtained using \c predNode(), \c predValue() and \c rootDist().
-///
+/// The functions \c minCutMap() and \c minCutValue() calculate
-/// The members \c minCutMap() and \c minCutValue() calculate
 /// 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 type of the undirected graph the algorithm runs on.
-/// \tparam CAP The type of the edge map describing the edge capacities.
+/// \tparam CAP The type of the edge map containing the capacities.
-/// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
+/// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR,
 	    typename CAP>
 #else
 template <typename GR,
 	    typename CAP = typename GR::template EdgeMap<int> >
 #endif
 class GomoryHu {
 public:
-/// The graph type
+/// The graph type of the algorithm
 typedef GR Graph;
-/// The type of the edge capacity map
+/// The capacity map type of the algorithm
 typedef CAP Capacity;
 /// The value type of capacities
 typedef typename Capacity::Value Value;
 private:
 public:
 /// \brief Constructor
 ///
-/// Constructor
+/// Constructor.
 /// \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)
 }
 /// \brief Destructor
 ///
-/// Destructor
+/// Destructor.
 ~GomoryHu() {
 destroyStructures();
 }
 private:
 /// @}
 ///\name Query Functions
 ///The results of the algorithm can be obtained using these
 ///functions.\n
-///\ref run() "run()" should be called before using them.\n
+///\ref run() should be called before using them.\n
 ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
 ///@{
 /// \brief Return the predecessor node in the Gomory-Hu tree.
 ///
-/// This function returns the predecessor node in the Gomory-Hu tree.
+/// This function returns the predecessor node of the given node
-/// If the node is
+/// in the Gomory-Hu tree.
-/// the root of the Gomory-Hu tree, then it returns \c INVALID.
+/// If \c node is the root of the tree, then it returns \c INVALID.
-Node predNode(const Node& node) {
+///
+/// \pre \ref run() must be called before using this function.
+Node predNode(const Node& node) const {
 return (*_pred)[node];
-}
-/// \brief Return the distance from the root node in the Gomory-Hu tree.
-///
-/// This function returns the distance of \c node from the root node
-/// in the Gomory-Hu tree.
-int rootDist(const Node& node) {
-return (*_order)[node];
 }
 /// \brief Return the weight of the predecessor edge in the
 /// Gomory-Hu tree.
 ///
-/// This function returns the weight of the predecessor edge in the
+/// This function returns the weight of the predecessor edge of the
-/// Gomory-Hu tree.  If the node is the root, the result is undefined.
+/// given node in the Gomory-Hu tree.
-Value predValue(const Node& node) {
+/// If \c node is the root of the tree, the result is undefined.
+///
+/// \pre \ref run() must be called before using this function.
+Value predValue(const Node& node) const {
 return (*_weight)[node];
 }
+/// \brief Return the distance from the root node in the Gomory-Hu tree.
+///
+/// This function returns the distance of the given node from the root
+/// node in the Gomory-Hu tree.
+///
+/// \pre \ref run() must be called before using this function.
+int rootDist(const Node& node) const {
+return (*_order)[node];
+}
 /// \brief Return the minimum cut value between two nodes
 ///
-/// This function returns the minimum cut value between two nodes. The
+/// This function returns the minimum cut value between the nodes
-/// algorithm finds the nearest common ancestor in the Gomory-Hu
+/// \c s and \c t.
-/// tree and calculates the minimum weight edge on the paths to
+/// It finds the nearest common ancestor of the given nodes in the
-/// the ancestor.
+/// Gomory-Hu tree and calculates the minimum weight edge on the
+/// paths to the ancestor.
+///
+/// \pre \ref run() must be called before using this function.
 Value minCutValue(const Node& s, const Node& t) const {
 Node sn = s, tn = t;
 Value value = std::numeric_limits<Value>::max();
 while (sn != tn) {
 ///
 /// This function returns the minimum cut between the nodes \c s and \c t
 /// 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.
 ///
-/// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
+/// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
+///
+/// \param s The base node.
+/// \param t The node you want to separate from node \c s.
+/// \param cutMap The cut will be returned in this map.
+/// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
+/// "ReadWriteMap" on the graph nodes.
+///
+/// \return The value of the minimum cut between \c s and \c t.
+///
+/// \pre \ref run() must be called before using this function.
 template <typename CutMap>
-Value minCutMap(const Node& s, ///< The base node.
+Value minCutMap(const Node& s, ///<
 const Node& t,
-///< The node you want to separate from node \c s.
+///<
 CutMap& cutMap
-///< 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;
 Node rn = INVALID;
 Value value = std::numeric_limits<Value>::max();
 friend class MinCutNodeIt;
 /// Iterate on the nodes of a minimum cut
 /// This iterator class lists the nodes of a minimum cut found by
-/// GomoryHu. Before using it, you must allocate a GomoryHu class,
+/// GomoryHu. Before using it, you must allocate a GomoryHu class
 /// and call its \ref GomoryHu::run() "run()" method.
 ///
 /// This example counts the nodes in the minimum cut separating \c s from
 /// \c t.
 /// \code
 friend class MinCutEdgeIt;
 /// Iterate on the edges of a minimum cut
 /// This iterator class lists the edges of a minimum cut found by
-/// GomoryHu. Before using it, you must allocate a GomoryHu class,
+/// GomoryHu. Before using it, you must allocate a GomoryHu class
 /// and call its \ref GomoryHu::run() "run()" method.
 ///
 /// This example computes the value of the minimum cut separating \c s from
 /// \c t.
 /// \code
 /// gom.run();
 /// int value=0;
 /// 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
+/// The result will be the same as the value returned by
-/// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
+/// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
 class MinCutEdgeIt
 {
 bool _side;
 const Graph &_graph;
 typename Graph::NodeIt _node_it;
 _arc_it=typename Graph::OutArcIt(_graph,_node_it);
 }
 }
 public:
+/// Constructor
+/// Constructor.
+///
 MinCutEdgeIt(GomoryHu const &gomory,
 ///< The GomoryHu class. You must call its
 ///  run() method
 ///  before initializing this iterator.
 const Node& s,  ///< The base node.
 const Node& t,
 ///< 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,
+///  nodes of the component containing \c s,
 ///  otherwise they will be oriented in the opposite
 ///  direction.
 )
 : _graph(gomory._graph), _cut(_graph)
 {

changeset 790	1870cfd14fb6
parent 581	aa1804409f29
child 713	4ac30454f1c1