COIN-OR::LEMON - Graph Library

Changeset 2228:f71b0f9a7c3a in lemon-0.x


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

Improved documentation.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/hao_orlin.h

    r2225 r2228  
    4141  /// \ingroup flowalgs
    4242  ///
    43   /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs.
     43  /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
    4444  ///
    45   /// Hao-Orlin calculates the minimum cut in directed graphs. It
    46   /// separates the nodes of the graph into two disjoint sets,
    47   /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum
    48   /// cut if the summary of the edge capacities which source is in
    49   /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the
    50   /// minimum.  The algorithm is a modified push-relabel preflow
    51   /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$
    52   /// time. The purpose of such algorithm is testing network
    53   /// reliability. For sparse undirected graph you can use the
    54   /// algorithm of Nagamochi and Ibaraki which solves the undirected
    55   /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the
    56   /// MinCut algorithm class.
     45  /// Hao-Orlin calculates a minimum cut in a directed graph \f$
     46  /// D=(V,A) \f$. It takes a fixed node \f$ source \in V \f$ and consists
     47  /// of two phases: in the first phase it determines a minimum cut
     48  /// with \f$ source \f$ on the source-side (i.e. a set \f$ X\subsetneq V
     49  /// \f$ with \f$ source \in X \f$ and minimal out-degree) and in the
     50  /// second phase it determines a minimum cut with \f$ source \f$ on the
     51  /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X \f$
     52  /// and minimal out-degree). Obviously, the smaller of these two
     53  /// cuts will be a minimum cut of \f$ D \f$. The algorithm is a
     54  /// modified push-relabel preflow algorithm and our implementation
     55  /// calculates the minimum cut in \f$ O(n^3) \f$ time (we use the
     56  /// highest-label rule). The purpose of such an algorithm is testing
     57  /// network reliability. For an undirected graph with \f$ n \f$
     58  /// nodes and \f$ e \f$ edges you can use the algorithm of Nagamochi
     59  /// and Ibaraki which solves the undirected problem in \f$ O(ne +
     60  /// n^2 \log(n)) \f$ time: it is implemented in the MinCut algorithm
     61  /// class.
    5762  ///
    5863  /// \param _Graph is the graph type of the algorithm.
     
    6065  /// be any numreric type. The default type is _Graph::EdgeMap<int>.
    6166  /// \param _Tolerance is the handler of the inexact computation. The
    62   /// default type for it is Tolerance<typename CapacityMap::Value>.
     67  /// default type for this is Tolerance<typename CapacityMap::Value>.
    6368  ///
    6469  /// \author Attila Bernath and Balazs Dezso
     
    479484    /// Initializes the internal data structures. It creates
    480485    /// the maps, residual graph adaptor and some bucket structures
    481     /// for the algorithm. The \c source node is used as the push-relabel
     486    /// for the algorithm. Node \c source is used as the push-relabel
    482487    /// algorithm's source.
    483488    void init(const Node& source) {
     
    527532
    528533
    529     /// \brief Calculates the minimum cut with the \c source node
    530     /// in the \f$ V_{out} \f$.
    531     ///
    532     /// Calculates the minimum cut with the \c source node
    533     /// in the \f$ V_{out} \f$.
     534    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     535    /// source-side.
     536    ///
     537    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     538    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X
     539    /// \f$ and minimal out-degree).
    534540    void calculateOut() {
    535541      for (NodeIt it(*_graph); it != INVALID; ++it) {
     
    541547    }
    542548
    543     /// \brief Calculates the minimum cut with the \c source node
    544     /// in the \f$ V_{out} \f$.
    545     ///
    546     /// Calculates the minimum cut with the \c source node
    547     /// in the \f$ V_{out} \f$. The \c target is the initial target
     549    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     550    /// source-side.
     551    ///
     552    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     553    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X
     554    /// \f$ and minimal out-degree). The \c target is the initial target
    548555    /// for the push-relabel algorithm.
    549556    void calculateOut(const Node& target) {
     
    551558    }
    552559
    553     /// \brief Calculates the minimum cut with the \c source node
    554     /// in the \f$ V_{in} \f$.
    555     ///
    556     /// Calculates the minimum cut with the \c source node
    557     /// in the \f$ V_{in} \f$.
     560    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     561    /// sink-side.
     562    ///
     563    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     564    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X
     565    /// \f$ and minimal out-degree).
    558566    void calculateIn() {
    559567      for (NodeIt it(*_graph); it != INVALID; ++it) {
     
    565573    }
    566574
    567     /// \brief Calculates the minimum cut with the \c source node
    568     /// in the \f$ V_{in} \f$.
    569     ///
    570     /// Calculates the minimum cut with the \c source node
    571     /// in the \f$ V_{in} \f$. The \c target is the initial target
    572     /// for the push-relabel algorithm.
     575    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     576    /// sink-side.
     577    ///
     578    /// \brief Calculates a minimum cut with \f$ source \f$ on the
     579    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin
     580    /// X \f$ and minimal out-degree).  The \c target is the initial
     581    /// target for the push-relabel algorithm.
    573582    void calculateIn(const Node& target) {
    574583      findMinCut(target, false, *_in_res_graph, *_in_current_edge);
     
    577586    /// \brief Runs the algorithm.
    578587    ///
    579     /// Runs the algorithm. It finds a proper \c source and \c target
    580     /// and then calls the \ref init(), \ref calculateOut() and \ref
    581     /// calculateIn().
     588    /// Runs the algorithm. It finds nodes \c source and \c target
     589    /// arbitrarily and then calls \ref init(), \ref calculateOut()
     590    /// and \ref calculateIn().
    582591    void run() {
    583592      init();
     
    593602    /// \brief Runs the algorithm.
    594603    ///
    595     /// Runs the algorithm. It finds a proper \c target and then calls
    596     /// the \ref init(), \ref calculateOut() and \ref calculateIn().
     604    /// Runs the algorithm. It uses the given \c source node, finds a
     605    /// proper \c target and then calls the \ref init(), \ref
     606    /// calculateOut() and \ref calculateIn().
    597607    void run(const Node& s) {
    598608      init(s);
     
    634644
    635645
    636     /// \brief Returns a minimum value cut.
     646    /// \brief Returns a minimum cut.
    637647    ///
    638648    /// Sets \c nodeMap to the characteristic vector of a minimum
    639     /// value cut. The nodes in \f$ V_{out} \f$ will be set true and
    640     /// the nodes in \f$ V_{in} \f$ will be set false.
    641     /// \pre nodeMap should be a bool-valued node-map.
     649    /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
     650    /// with minimal out-degree (i.e. \c nodeMap will be true exactly
     651    /// for the nodes of \f$ X \f$.  \pre nodeMap should be a
     652    /// bool-valued node-map.
    642653    template <typename NodeMap>
    643654    Value minCut(NodeMap& nodeMap) const {
Note: See TracChangeset for help on using the changeset viewer.