1.1 --- a/lemon/hao_orlin.h Wed Apr 15 07:13:30 2009 +0100
1.2 +++ b/lemon/hao_orlin.h Wed Apr 15 09:37:51 2009 +0200
1.3 @@ -31,39 +31,41 @@
1.4 /// \ingroup min_cut
1.5 /// \brief Implementation of the Hao-Orlin algorithm.
1.6 ///
1.7 -/// Implementation of the Hao-Orlin algorithm class for testing network
1.8 -/// reliability.
1.9 +/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
1.10 +/// in a digraph.
1.11
1.12 namespace lemon {
1.13
1.14 /// \ingroup min_cut
1.15 ///
1.16 - /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
1.17 + /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
1.18 ///
1.19 - /// Hao-Orlin calculates a minimum cut in a directed graph
1.20 - /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and
1.21 + /// This class implements the Hao-Orlin algorithm for finding a minimum
1.22 + /// value cut in a directed graph \f$D=(V,A)\f$.
1.23 + /// It takes a fixed node \f$ source \in V \f$ and
1.24 /// consists of two phases: in the first phase it determines a
1.25 /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
1.26 - /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal
1.27 - /// out-degree) and in the second phase it determines a minimum cut
1.28 + /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing
1.29 + /// capacity) and in the second phase it determines a minimum cut
1.30 /// with \f$ source \f$ on the sink-side (i.e. a set
1.31 - /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal
1.32 - /// out-degree). Obviously, the smaller of these two cuts will be a
1.33 + /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing
1.34 + /// capacity). Obviously, the smaller of these two cuts will be a
1.35 /// minimum cut of \f$ D \f$. The algorithm is a modified
1.36 - /// push-relabel preflow algorithm and our implementation calculates
1.37 + /// preflow push-relabel algorithm. Our implementation calculates
1.38 /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
1.39 /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
1.40 - /// purpose of such algorithm is testing network reliability. For an
1.41 - /// undirected graph you can run just the first phase of the
1.42 - /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
1.43 - /// which solves the undirected problem in
1.44 - /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
1.45 - /// NagamochiIbaraki algorithm class.
1.46 + /// purpose of such algorithm is e.g. testing network reliability.
1.47 ///
1.48 - /// \param GR The digraph class the algorithm runs on.
1.49 - /// \param CAP An arc map of capacities which can be any numreric type.
1.50 - /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.51 - /// \param TOL Tolerance class for handling inexact computations. The
1.52 + /// For an undirected graph you can run just the first phase of the
1.53 + /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
1.54 + /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
1.55 + /// time. It is implemented in the NagamochiIbaraki algorithm class.
1.56 + ///
1.57 + /// \tparam GR The type of the digraph the algorithm runs on.
1.58 + /// \tparam CAP The type of the arc map containing the capacities,
1.59 + /// which can be any numreric type. The default map type is
1.60 + /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.61 + /// \tparam TOL Tolerance class for handling inexact computations. The
1.62 /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
1.63 #ifdef DOXYGEN
1.64 template <typename GR, typename CAP, typename TOL>
1.65 @@ -73,15 +75,20 @@
1.66 typename TOL = Tolerance<typename CAP::Value> >
1.67 #endif
1.68 class HaoOrlin {
1.69 + public:
1.70 +
1.71 + /// The digraph type of the algorithm
1.72 + typedef GR Digraph;
1.73 + /// The capacity map type of the algorithm
1.74 + typedef CAP CapacityMap;
1.75 + /// The tolerance type of the algorithm
1.76 + typedef TOL Tolerance;
1.77 +
1.78 private:
1.79
1.80 - typedef GR Digraph;
1.81 - typedef CAP CapacityMap;
1.82 - typedef TOL Tolerance;
1.83 -
1.84 typedef typename CapacityMap::Value Value;
1.85
1.86 - TEMPLATE_GRAPH_TYPEDEFS(Digraph);
1.87 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.88
1.89 const Digraph& _graph;
1.90 const CapacityMap* _capacity;
1.91 @@ -815,31 +822,32 @@
1.92
1.93 public:
1.94
1.95 - /// \name Execution control
1.96 + /// \name Execution Control
1.97 /// The simplest way to execute the algorithm is to use
1.98 /// one of the member functions called \ref run().
1.99 /// \n
1.100 - /// If you need more control on the execution,
1.101 - /// first you must call \ref init(), then the \ref calculateIn() or
1.102 - /// \ref calculateOut() functions.
1.103 + /// If you need better control on the execution,
1.104 + /// you have to call one of the \ref init() functions first, then
1.105 + /// \ref calculateOut() and/or \ref calculateIn().
1.106
1.107 /// @{
1.108
1.109 - /// \brief Initializes the internal data structures.
1.110 + /// \brief Initialize the internal data structures.
1.111 ///
1.112 - /// Initializes the internal data structures. It creates
1.113 - /// the maps, residual graph adaptors and some bucket structures
1.114 - /// for the algorithm.
1.115 + /// This function initializes the internal data structures. It creates
1.116 + /// the maps and some bucket structures for the algorithm.
1.117 + /// The first node is used as the source node for the push-relabel
1.118 + /// algorithm.
1.119 void init() {
1.120 init(NodeIt(_graph));
1.121 }
1.122
1.123 - /// \brief Initializes the internal data structures.
1.124 + /// \brief Initialize the internal data structures.
1.125 ///
1.126 - /// Initializes the internal data structures. It creates
1.127 - /// the maps, residual graph adaptor and some bucket structures
1.128 - /// for the algorithm. Node \c source is used as the push-relabel
1.129 - /// algorithm's source.
1.130 + /// This function initializes the internal data structures. It creates
1.131 + /// the maps and some bucket structures for the algorithm.
1.132 + /// The given node is used as the source node for the push-relabel
1.133 + /// algorithm.
1.134 void init(const Node& source) {
1.135 _source = source;
1.136
1.137 @@ -879,31 +887,35 @@
1.138 }
1.139
1.140
1.141 - /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.142 + /// \brief Calculate a minimum cut with \f$ source \f$ on the
1.143 /// source-side.
1.144 ///
1.145 - /// Calculates a minimum cut with \f$ source \f$ on the
1.146 + /// This function calculates a minimum cut with \f$ source \f$ on the
1.147 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
1.148 - /// \f$ source \in X \f$ and minimal out-degree).
1.149 + /// \f$ source \in X \f$ and minimal outgoing capacity).
1.150 + ///
1.151 + /// \pre \ref init() must be called before using this function.
1.152 void calculateOut() {
1.153 findMinCutOut();
1.154 }
1.155
1.156 - /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.157 - /// target-side.
1.158 + /// \brief Calculate a minimum cut with \f$ source \f$ on the
1.159 + /// sink-side.
1.160 ///
1.161 - /// Calculates a minimum cut with \f$ source \f$ on the
1.162 - /// target-side (i.e. a set \f$ X\subsetneq V \f$ with
1.163 - /// \f$ source \in X \f$ and minimal out-degree).
1.164 + /// This function calculates a minimum cut with \f$ source \f$ on the
1.165 + /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
1.166 + /// \f$ source \notin X \f$ and minimal outgoing capacity).
1.167 + ///
1.168 + /// \pre \ref init() must be called before using this function.
1.169 void calculateIn() {
1.170 findMinCutIn();
1.171 }
1.172
1.173
1.174 - /// \brief Runs the algorithm.
1.175 + /// \brief Run the algorithm.
1.176 ///
1.177 - /// Runs the algorithm. It finds nodes \c source and \c target
1.178 - /// arbitrarily and then calls \ref init(), \ref calculateOut()
1.179 + /// This function runs the algorithm. It finds nodes \c source and
1.180 + /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
1.181 /// and \ref calculateIn().
1.182 void run() {
1.183 init();
1.184 @@ -911,11 +923,11 @@
1.185 calculateIn();
1.186 }
1.187
1.188 - /// \brief Runs the algorithm.
1.189 + /// \brief Run the algorithm.
1.190 ///
1.191 - /// Runs the algorithm. It uses the given \c source node, finds a
1.192 - /// proper \c target and then calls the \ref init(), \ref
1.193 - /// calculateOut() and \ref calculateIn().
1.194 + /// This function runs the algorithm. It uses the given \c source node,
1.195 + /// finds a proper \c target node and then calls the \ref init(),
1.196 + /// \ref calculateOut() and \ref calculateIn().
1.197 void run(const Node& s) {
1.198 init(s);
1.199 calculateOut();
1.200 @@ -926,32 +938,41 @@
1.201
1.202 /// \name Query Functions
1.203 /// The result of the %HaoOrlin algorithm
1.204 - /// can be obtained using these functions.
1.205 - /// \n
1.206 - /// Before using these functions, either \ref run(), \ref
1.207 - /// calculateOut() or \ref calculateIn() must be called.
1.208 + /// can be obtained using these functions.\n
1.209 + /// \ref run(), \ref calculateOut() or \ref calculateIn()
1.210 + /// should be called before using them.
1.211
1.212 /// @{
1.213
1.214 - /// \brief Returns the value of the minimum value cut.
1.215 + /// \brief Return the value of the minimum cut.
1.216 ///
1.217 - /// Returns the value of the minimum value cut.
1.218 + /// This function returns the value of the minimum cut.
1.219 + ///
1.220 + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
1.221 + /// must be called before using this function.
1.222 Value minCutValue() const {
1.223 return _min_cut;
1.224 }
1.225
1.226
1.227 - /// \brief Returns a minimum cut.
1.228 + /// \brief Return a minimum cut.
1.229 ///
1.230 - /// Sets \c nodeMap to the characteristic vector of a minimum
1.231 - /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
1.232 - /// with minimal out-degree (i.e. \c nodeMap will be true exactly
1.233 - /// for the nodes of \f$ X \f$). \pre nodeMap should be a
1.234 - /// bool-valued node-map.
1.235 - template <typename NodeMap>
1.236 - Value minCutMap(NodeMap& nodeMap) const {
1.237 + /// This function sets \c cutMap to the characteristic vector of a
1.238 + /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
1.239 + /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
1.240 + /// for the nodes of \f$ X \f$).
1.241 + ///
1.242 + /// \param cutMap A \ref concepts::WriteMap "writable" node map with
1.243 + /// \c bool (or convertible) value type.
1.244 + ///
1.245 + /// \return The value of the minimum cut.
1.246 + ///
1.247 + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
1.248 + /// must be called before using this function.
1.249 + template <typename CutMap>
1.250 + Value minCutMap(CutMap& cutMap) const {
1.251 for (NodeIt it(_graph); it != INVALID; ++it) {
1.252 - nodeMap.set(it, (*_min_cut_map)[it]);
1.253 + cutMap.set(it, (*_min_cut_map)[it]);
1.254 }
1.255 return _min_cut;
1.256 }
1.257 @@ -960,7 +981,6 @@
1.258
1.259 }; //class HaoOrlin
1.260
1.261 -
1.262 } //namespace lemon
1.263
1.264 #endif //LEMON_HAO_ORLIN_H