# Changeset 2228:f71b0f9a7c3a in lemon-0.x for lemon/hao_orlin.h

Ignore:
Timestamp:
10/02/06 16:41:53 (13 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2968
Message:

Improved documentation.

File:
1 edited

### Legend:

Unmodified
 r2225 /// \ingroup flowalgs /// /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs. /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs. /// /// Hao-Orlin calculates the minimum cut in directed graphs. It /// separates the nodes of the graph into two disjoint sets, /// \f$V_{out} \f$ and \f$V_{in} \f$. This separation is the minimum /// cut if the summary of the edge capacities which source is in /// \f$V_{out} \f$ and the target is in \f$V_{in} \f$ is the /// minimum.  The algorithm is a modified push-relabel preflow /// algorithm and it calculates the minimum cut in \f$O(n^3) \f$ /// time. The purpose of such algorithm is testing network /// reliability. For sparse undirected graph you can use the /// algorithm of Nagamochi and Ibaraki which solves the undirected /// problem in \f$O(ne + n^2 \log(n)) \f$ time and it is implemented in the /// MinCut algorithm class. /// Hao-Orlin calculates a minimum cut in a directed graph \f$/// D=(V,A) \f$. It takes a fixed node \f$source \in V \f$ and consists /// of two phases: in the first phase it determines a minimum cut /// with \f$source \f$ on the source-side (i.e. a set \f$X\subsetneq V /// \f$ with \f$source \in X \f$ and minimal out-degree) and in the /// second phase it determines a minimum cut with \f$source \f$ on the /// sink-side (i.e. a set \f$X\subsetneq V \f$ with \f$source \notin X \f$ /// and minimal out-degree). Obviously, the smaller of these two /// cuts will be a minimum cut of \f$D \f$. The algorithm is a /// modified push-relabel preflow algorithm and our implementation /// calculates the minimum cut in \f$O(n^3) \f$ time (we use the /// highest-label rule). The purpose of such an algorithm is testing /// network reliability. For an undirected graph with \f$n \f$ /// nodes and \f$e \f$ edges you can use the algorithm of Nagamochi /// and Ibaraki which solves the undirected problem in \f$O(ne + /// n^2 \log(n)) \f$ time: it is implemented in the MinCut algorithm /// class. /// /// \param _Graph is the graph type of the algorithm. /// be any numreric type. The default type is _Graph::EdgeMap. /// \param _Tolerance is the handler of the inexact computation. The /// default type for it is Tolerance. /// default type for this is Tolerance. /// /// \author Attila Bernath and Balazs Dezso /// Initializes the internal data structures. It creates /// the maps, residual graph adaptor and some bucket structures /// for the algorithm. The \c source node is used as the push-relabel /// for the algorithm. Node \c source is used as the push-relabel /// algorithm's source. void init(const Node& source) { /// \brief Calculates the minimum cut with the \c source node /// in the \f$V_{out} \f$. /// /// Calculates the minimum cut with the \c source node /// in the \f$V_{out} \f$. /// \brief Calculates a minimum cut with \f$source \f$ on the /// source-side. /// /// \brief Calculates a minimum cut with \f$source \f$ on the /// source-side (i.e. a set \f$X\subsetneq V \f$ with \f$source \in X /// \f$ and minimal out-degree). void calculateOut() { for (NodeIt it(*_graph); it != INVALID; ++it) { } /// \brief Calculates the minimum cut with the \c source node /// in the \f$V_{out} \f$. /// /// Calculates the minimum cut with the \c source node /// in the \f$V_{out} \f$. The \c target is the initial target /// \brief Calculates a minimum cut with \f$source \f$ on the /// source-side. /// /// \brief Calculates a minimum cut with \f$source \f$ on the /// source-side (i.e. a set \f$X\subsetneq V \f$ with \f$source \in X /// \f$ and minimal out-degree). The \c target is the initial target /// for the push-relabel algorithm. void calculateOut(const Node& target) { } /// \brief Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. /// /// Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. /// \brief Calculates a minimum cut with \f$source \f$ on the /// sink-side. /// /// \brief Calculates a minimum cut with \f$source \f$ on the /// sink-side (i.e. a set \f$X\subsetneq V \f$ with \f$source \notin X /// \f$ and minimal out-degree). void calculateIn() { for (NodeIt it(*_graph); it != INVALID; ++it) { } /// \brief Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. /// /// Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. The \c target is the initial target /// for the push-relabel algorithm. /// \brief Calculates a minimum cut with \f$source \f$ on the /// sink-side. /// /// \brief Calculates a minimum cut with \f$source \f$ on the /// sink-side (i.e. a set \f$X\subsetneq V \f$ with \f$source \notin /// X \f$ and minimal out-degree).  The \c target is the initial /// target for the push-relabel algorithm. void calculateIn(const Node& target) { findMinCut(target, false, *_in_res_graph, *_in_current_edge); /// \brief Runs the algorithm. /// /// Runs the algorithm. It finds a proper \c source and \c target /// and then calls the \ref init(), \ref calculateOut() and \ref /// calculateIn(). /// Runs the algorithm. It finds nodes \c source and \c target /// arbitrarily and then calls \ref init(), \ref calculateOut() /// and \ref calculateIn(). void run() { init(); /// \brief Runs the algorithm. /// /// Runs the algorithm. It finds a proper \c target and then calls /// the \ref init(), \ref calculateOut() and \ref calculateIn(). /// Runs the algorithm. It uses the given \c source node, finds a /// proper \c target and then calls the \ref init(), \ref /// calculateOut() and \ref calculateIn(). void run(const Node& s) { init(s); /// \brief Returns a minimum value cut. /// \brief Returns a minimum cut. /// /// Sets \c nodeMap to the characteristic vector of a minimum /// value cut. The nodes in \f$V_{out} \f$ will be set true and /// the nodes in \f$V_{in} \f$ will be set false. /// \pre nodeMap should be a bool-valued node-map. /// value cut: it will give a nonempty set \f$X\subsetneq V \f$ /// with minimal out-degree (i.e. \c nodeMap will be true exactly /// for the nodes of \f$X \f$.  \pre nodeMap should be a /// bool-valued node-map. template Value minCut(NodeMap& nodeMap) const {