1.1 --- a/lemon/hao_orlin.h Mon Oct 02 12:09:32 2006 +0000
1.2 +++ b/lemon/hao_orlin.h Mon Oct 02 14:41:53 2006 +0000
1.3 @@ -40,26 +40,31 @@
1.4
1.5 /// \ingroup flowalgs
1.6 ///
1.7 - /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs.
1.8 + /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
1.9 ///
1.10 - /// Hao-Orlin calculates the minimum cut in directed graphs. It
1.11 - /// separates the nodes of the graph into two disjoint sets,
1.12 - /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum
1.13 - /// cut if the summary of the edge capacities which source is in
1.14 - /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the
1.15 - /// minimum. The algorithm is a modified push-relabel preflow
1.16 - /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$
1.17 - /// time. The purpose of such algorithm is testing network
1.18 - /// reliability. For sparse undirected graph you can use the
1.19 - /// algorithm of Nagamochi and Ibaraki which solves the undirected
1.20 - /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the
1.21 - /// MinCut algorithm class.
1.22 + /// Hao-Orlin calculates a minimum cut in a directed graph \f$
1.23 + /// D=(V,A) \f$. It takes a fixed node \f$ source \in V \f$ and consists
1.24 + /// of two phases: in the first phase it determines a minimum cut
1.25 + /// with \f$ source \f$ on the source-side (i.e. a set \f$ X\subsetneq V
1.26 + /// \f$ with \f$ source \in X \f$ and minimal out-degree) and in the
1.27 + /// second phase it determines a minimum cut with \f$ source \f$ on the
1.28 + /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X \f$
1.29 + /// and minimal out-degree). Obviously, the smaller of these two
1.30 + /// cuts will be a minimum cut of \f$ D \f$. The algorithm is a
1.31 + /// modified push-relabel preflow algorithm and our implementation
1.32 + /// calculates the minimum cut in \f$ O(n^3) \f$ time (we use the
1.33 + /// highest-label rule). The purpose of such an algorithm is testing
1.34 + /// network reliability. For an undirected graph with \f$ n \f$
1.35 + /// nodes and \f$ e \f$ edges you can use the algorithm of Nagamochi
1.36 + /// and Ibaraki which solves the undirected problem in \f$ O(ne +
1.37 + /// n^2 \log(n)) \f$ time: it is implemented in the MinCut algorithm
1.38 + /// class.
1.39 ///
1.40 /// \param _Graph is the graph type of the algorithm.
1.41 /// \param _CapacityMap is an edge map of capacities which should
1.42 /// be any numreric type. The default type is _Graph::EdgeMap<int>.
1.43 /// \param _Tolerance is the handler of the inexact computation. The
1.44 - /// default type for it is Tolerance<typename CapacityMap::Value>.
1.45 + /// default type for this is Tolerance<typename CapacityMap::Value>.
1.46 ///
1.47 /// \author Attila Bernath and Balazs Dezso
1.48 #ifdef DOXYGEN
1.49 @@ -478,7 +483,7 @@
1.50 ///
1.51 /// Initializes the internal data structures. It creates
1.52 /// the maps, residual graph adaptor and some bucket structures
1.53 - /// for the algorithm. The \c source node is used as the push-relabel
1.54 + /// for the algorithm. Node \c source is used as the push-relabel
1.55 /// algorithm's source.
1.56 void init(const Node& source) {
1.57 _source = source;
1.58 @@ -526,11 +531,12 @@
1.59 }
1.60
1.61
1.62 - /// \brief Calculates the minimum cut with the \c source node
1.63 - /// in the \f$ V_{out} \f$.
1.64 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.65 + /// source-side.
1.66 ///
1.67 - /// Calculates the minimum cut with the \c source node
1.68 - /// in the \f$ V_{out} \f$.
1.69 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.70 + /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X
1.71 + /// \f$ and minimal out-degree).
1.72 void calculateOut() {
1.73 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.74 if (it != _source) {
1.75 @@ -540,21 +546,23 @@
1.76 }
1.77 }
1.78
1.79 - /// \brief Calculates the minimum cut with the \c source node
1.80 - /// in the \f$ V_{out} \f$.
1.81 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.82 + /// source-side.
1.83 ///
1.84 - /// Calculates the minimum cut with the \c source node
1.85 - /// in the \f$ V_{out} \f$. The \c target is the initial target
1.86 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.87 + /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X
1.88 + /// \f$ and minimal out-degree). The \c target is the initial target
1.89 /// for the push-relabel algorithm.
1.90 void calculateOut(const Node& target) {
1.91 findMinCut(target, true, *_out_res_graph, *_out_current_edge);
1.92 }
1.93
1.94 - /// \brief Calculates the minimum cut with the \c source node
1.95 - /// in the \f$ V_{in} \f$.
1.96 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.97 + /// sink-side.
1.98 ///
1.99 - /// Calculates the minimum cut with the \c source node
1.100 - /// in the \f$ V_{in} \f$.
1.101 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.102 + /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X
1.103 + /// \f$ and minimal out-degree).
1.104 void calculateIn() {
1.105 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.106 if (it != _source) {
1.107 @@ -564,21 +572,22 @@
1.108 }
1.109 }
1.110
1.111 - /// \brief Calculates the minimum cut with the \c source node
1.112 - /// in the \f$ V_{in} \f$.
1.113 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.114 + /// sink-side.
1.115 ///
1.116 - /// Calculates the minimum cut with the \c source node
1.117 - /// in the \f$ V_{in} \f$. The \c target is the initial target
1.118 - /// for the push-relabel algorithm.
1.119 + /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.120 + /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin
1.121 + /// X \f$ and minimal out-degree). The \c target is the initial
1.122 + /// target for the push-relabel algorithm.
1.123 void calculateIn(const Node& target) {
1.124 findMinCut(target, false, *_in_res_graph, *_in_current_edge);
1.125 }
1.126
1.127 /// \brief Runs the algorithm.
1.128 ///
1.129 - /// Runs the algorithm. It finds a proper \c source and \c target
1.130 - /// and then calls the \ref init(), \ref calculateOut() and \ref
1.131 - /// calculateIn().
1.132 + /// Runs the algorithm. It finds nodes \c source and \c target
1.133 + /// arbitrarily and then calls \ref init(), \ref calculateOut()
1.134 + /// and \ref calculateIn().
1.135 void run() {
1.136 init();
1.137 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.138 @@ -592,8 +601,9 @@
1.139
1.140 /// \brief Runs the algorithm.
1.141 ///
1.142 - /// Runs the algorithm. It finds a proper \c target and then calls
1.143 - /// the \ref init(), \ref calculateOut() and \ref calculateIn().
1.144 + /// Runs the algorithm. It uses the given \c source node, finds a
1.145 + /// proper \c target and then calls the \ref init(), \ref
1.146 + /// calculateOut() and \ref calculateIn().
1.147 void run(const Node& s) {
1.148 init(s);
1.149 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.150 @@ -633,12 +643,13 @@
1.151 }
1.152
1.153
1.154 - /// \brief Returns a minimum value cut.
1.155 + /// \brief Returns a minimum cut.
1.156 ///
1.157 /// Sets \c nodeMap to the characteristic vector of a minimum
1.158 - /// value cut. The nodes in \f$ V_{out} \f$ will be set true and
1.159 - /// the nodes in \f$ V_{in} \f$ will be set false.
1.160 - /// \pre nodeMap should be a bool-valued node-map.
1.161 + /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
1.162 + /// with minimal out-degree (i.e. \c nodeMap will be true exactly
1.163 + /// for the nodes of \f$ X \f$. \pre nodeMap should be a
1.164 + /// bool-valued node-map.
1.165 template <typename NodeMap>
1.166 Value minCut(NodeMap& nodeMap) const {
1.167 for (NodeIt it(*_graph); it != INVALID; ++it) {