1.1 --- a/lemon/hao_orlin.h Fri Aug 09 11:07:27 2013 +0200
1.2 +++ b/lemon/hao_orlin.h Sun Aug 11 15:28:12 2013 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -31,7 +31,7 @@
1.13 /// \ingroup min_cut
1.14 /// \brief Implementation of the Hao-Orlin algorithm.
1.15 ///
1.16 -/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
1.17 +/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
1.18 /// in a digraph.
1.19
1.20 namespace lemon {
1.21 @@ -41,7 +41,7 @@
1.22 /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
1.23 ///
1.24 /// This class implements the Hao-Orlin algorithm for finding a minimum
1.25 - /// value cut in a directed graph \f$D=(V,A)\f$.
1.26 + /// value cut in a directed graph \f$D=(V,A)\f$.
1.27 /// It takes a fixed node \f$ source \in V \f$ and
1.28 /// consists of two phases: in the first phase it determines a
1.29 /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
1.30 @@ -58,7 +58,7 @@
1.31 ///
1.32 /// For an undirected graph you can run just the first phase of the
1.33 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
1.34 - /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
1.35 + /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
1.36 /// time. It is implemented in the NagamochiIbaraki algorithm class.
1.37 ///
1.38 /// \tparam GR The type of the digraph the algorithm runs on.
1.39 @@ -76,7 +76,7 @@
1.40 #endif
1.41 class HaoOrlin {
1.42 public:
1.43 -
1.44 +
1.45 /// The digraph type of the algorithm
1.46 typedef GR Digraph;
1.47 /// The capacity map type of the algorithm
1.48 @@ -165,6 +165,23 @@
1.49 }
1.50 }
1.51
1.52 + /// \brief Set the tolerance used by the algorithm.
1.53 + ///
1.54 + /// This function sets the tolerance object used by the algorithm.
1.55 + /// \return <tt>(*this)</tt>
1.56 + HaoOrlin& tolerance(const Tolerance& tolerance) {
1.57 + _tolerance = tolerance;
1.58 + return *this;
1.59 + }
1.60 +
1.61 + /// \brief Returns a const reference to the tolerance.
1.62 + ///
1.63 + /// This function returns a const reference to the tolerance object
1.64 + /// used by the algorithm.
1.65 + const Tolerance& tolerance() const {
1.66 + return _tolerance;
1.67 + }
1.68 +
1.69 private:
1.70
1.71 void activate(const Node& i) {
1.72 @@ -847,7 +864,7 @@
1.73 /// \brief Initialize the internal data structures.
1.74 ///
1.75 /// This function initializes the internal data structures. It creates
1.76 - /// the maps and some bucket structures for the algorithm.
1.77 + /// the maps and some bucket structures for the algorithm.
1.78 /// The given node is used as the source node for the push-relabel
1.79 /// algorithm.
1.80 void init(const Node& source) {
1.81 @@ -927,7 +944,7 @@
1.82
1.83 /// \brief Run the algorithm.
1.84 ///
1.85 - /// This function runs the algorithm. It uses the given \c source node,
1.86 + /// This function runs the algorithm. It uses the given \c source node,
1.87 /// finds a proper \c target node and then calls the \ref init(),
1.88 /// \ref calculateOut() and \ref calculateIn().
1.89 void run(const Node& s) {
1.90 @@ -941,7 +958,7 @@
1.91 /// \name Query Functions
1.92 /// The result of the %HaoOrlin algorithm
1.93 /// can be obtained using these functions.\n
1.94 - /// \ref run(), \ref calculateOut() or \ref calculateIn()
1.95 + /// \ref run(), \ref calculateOut() or \ref calculateIn()
1.96 /// should be called before using them.
1.97
1.98 /// @{
1.99 @@ -950,7 +967,7 @@
1.100 ///
1.101 /// This function returns the value of the minimum cut.
1.102 ///
1.103 - /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
1.104 + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
1.105 /// must be called before using this function.
1.106 Value minCutValue() const {
1.107 return _min_cut;
1.108 @@ -969,7 +986,7 @@
1.109 ///
1.110 /// \return The value of the minimum cut.
1.111 ///
1.112 - /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
1.113 + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
1.114 /// must be called before using this function.
1.115 template <typename CutMap>
1.116 Value minCutMap(CutMap& cutMap) const {