COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/hao_orlin.h

    r581 r597  
    3232/// \brief Implementation of the Hao-Orlin algorithm.
    3333///
    34 /// Implementation of the Hao-Orlin algorithm class for testing network
    35 /// reliability.
     34/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
     35/// in a digraph.
    3636
    3737namespace lemon {
    … …  
    3939  /// \ingroup min_cut
    4040  ///
    41   /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
     41  /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
    4242  ///
    43   /// Hao-Orlin calculates a minimum cut in a directed graph
    44   /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and
     43  /// This class implements the Hao-Orlin algorithm for finding a minimum
     44  /// value cut in a directed graph \f$D=(V,A)\f$.
     45  /// It takes a fixed node \f$ source \in V \f$ and
    4546  /// consists of two phases: in the first phase it determines a
    4647  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
    47   /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal
    48   /// out-degree) and in the second phase it determines a minimum cut
     48  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing
     49  /// capacity) and in the second phase it determines a minimum cut
    4950  /// with \f$ source \f$ on the sink-side (i.e. a set
    50   /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal
    51   /// out-degree). Obviously, the smaller of these two cuts will be a
     51  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing
     52  /// capacity). Obviously, the smaller of these two cuts will be a
    5253  /// minimum cut of \f$ D \f$. The algorithm is a modified
    53   /// push-relabel preflow algorithm and our implementation calculates
     54  /// preflow push-relabel algorithm. Our implementation calculates
    5455  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
    5556  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    56   /// purpose of such algorithm is testing network reliability. For an
    57   /// undirected graph you can run just the first phase of the
    58   /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
    59   /// which solves the undirected problem in
    60   /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
    61   /// NagamochiIbaraki algorithm class.
     57  /// purpose of such algorithm is e.g. testing network reliability.
    6258  ///
    63   /// \param GR The digraph class the algorithm runs on.
    64   /// \param CAP An arc map of capacities which can be any numreric type.
    65   /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    66   /// \param TOL Tolerance class for handling inexact computations. The
     59  /// For an undirected graph you can run just the first phase of the
     60  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
     61  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
     62  /// time. It is implemented in the NagamochiIbaraki algorithm class.
     63  ///
     64  /// \tparam GR The type of the digraph the algorithm runs on.
     65  /// \tparam CAP The type of the arc map containing the capacities,
     66  /// which can be any numreric type. The default map type is
     67  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     68  /// \tparam TOL Tolerance class for handling inexact computations. The
    6769  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
    6870#ifdef DOXYGEN
    … …  
    7476#endif
    7577  class HaoOrlin {
     78  public:
     79   
     80    /// The digraph type of the algorithm
     81    typedef GR Digraph;
     82    /// The capacity map type of the algorithm
     83    typedef CAP CapacityMap;
     84    /// The tolerance type of the algorithm
     85    typedef TOL Tolerance;
     86
    7687  private:
    7788
    78     typedef GR Digraph;
    79     typedef CAP CapacityMap;
    80     typedef TOL Tolerance;
    81 
    8289    typedef typename CapacityMap::Value Value;
    8390
    84     TEMPLATE_GRAPH_TYPEDEFS(Digraph);
     91    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    8592
    8693    const Digraph& _graph;
    … …  
    220227      for (NodeIt n(_graph); n != INVALID; ++n) {
    221228        (*_excess)[n] = 0;
     229        (*_source_set)[n] = false;
    222230      }
    223231
    … …  
    519527      for (NodeIt n(_graph); n != INVALID; ++n) {
    520528        (*_excess)[n] = 0;
     529        (*_source_set)[n] = false;
    521530      }
    522531
    … …  
    816825  public:
    817826
    818     /// \name Execution control
     827    /// \name Execution Control
    819828    /// The simplest way to execute the algorithm is to use
    820829    /// one of the member functions called \ref run().
    821830    /// \n
    822     /// If you need more control on the execution,
    823     /// first you must call \ref init(), then the \ref calculateIn() or
    824     /// \ref calculateOut() functions.
     831    /// If you need better control on the execution,
     832    /// you have to call one of the \ref init() functions first, then
     833    /// \ref calculateOut() and/or \ref calculateIn().
    825834
    826835    /// @{
    827836
    828     /// \brief Initializes the internal data structures.
    829     ///
    830     /// Initializes the internal data structures. It creates
    831     /// the maps, residual graph adaptors and some bucket structures
    832     /// for the algorithm.
     837    /// \brief Initialize the internal data structures.
     838    ///
     839    /// This function initializes the internal data structures. It creates
     840    /// the maps and some bucket structures for the algorithm.
     841    /// The first node is used as the source node for the push-relabel
     842    /// algorithm.
    833843    void init() {
    834844      init(NodeIt(_graph));
    835845    }
    836846
    837     /// \brief Initializes the internal data structures.
    838     ///
    839     /// Initializes the internal data structures. It creates
    840     /// the maps, residual graph adaptor and some bucket structures
    841     /// for the algorithm. Node \c source  is used as the push-relabel
    842     /// algorithm's source.
     847    /// \brief Initialize the internal data structures.
     848    ///
     849    /// This function initializes the internal data structures. It creates
     850    /// the maps and some bucket structures for the algorithm.
     851    /// The given node is used as the source node for the push-relabel
     852    /// algorithm.
    843853    void init(const Node& source) {
    844854      _source = source;
    … …  
    880890
    881891
    882     /// \brief Calculates a minimum cut with \f$ source \f$ on the
     892    /// \brief Calculate a minimum cut with \f$ source \f$ on the
    883893    /// source-side.
    884894    ///
    885     /// Calculates a minimum cut with \f$ source \f$ on the
     895    /// This function calculates a minimum cut with \f$ source \f$ on the
    886896    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
    887     /// \f$ source \in X \f$ and minimal out-degree).
     897    /// \f$ source \in X \f$ and minimal outgoing capacity).
     898    ///
     899    /// \pre \ref init() must be called before using this function.
    888900    void calculateOut() {
    889901      findMinCutOut();
    890902    }
    891903
    892     /// \brief Calculates a minimum cut with \f$ source \f$ on the
    893     /// target-side.
    894     ///
    895     /// Calculates a minimum cut with \f$ source \f$ on the
    896     /// target-side (i.e. a set \f$ X\subsetneq V \f$ with
    897     /// \f$ source \in X \f$ and minimal out-degree).
     904    /// \brief Calculate a minimum cut with \f$ source \f$ on the
     905    /// sink-side.
     906    ///
     907    /// This function calculates a minimum cut with \f$ source \f$ on the
     908    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
     909    /// \f$ source \notin X \f$ and minimal outgoing capacity).
     910    ///
     911    /// \pre \ref init() must be called before using this function.
    898912    void calculateIn() {
    899913      findMinCutIn();
    … …  
    901915
    902916
    903     /// \brief Runs the algorithm.
    904     ///
    905     /// Runs the algorithm. It finds nodes \c source and \c target
    906     /// arbitrarily and then calls \ref init(), \ref calculateOut()
     917    /// \brief Run the algorithm.
     918    ///
     919    /// This function runs the algorithm. It finds nodes \c source and
     920    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
    907921    /// and \ref calculateIn().
    908922    void run() {
    … …  
    912926    }
    913927
    914     /// \brief Runs the algorithm.
    915     ///
    916     /// Runs the algorithm. It uses the given \c source node, finds a
    917     /// proper \c target and then calls the \ref init(), \ref
    918     /// calculateOut() and \ref calculateIn().
     928    /// \brief Run the algorithm.
     929    ///
     930    /// This function runs the algorithm. It uses the given \c source node,
     931    /// finds a proper \c target node and then calls the \ref init(),
     932    /// \ref calculateOut() and \ref calculateIn().
    919933    void run(const Node& s) {
    920934      init(s);
    … …  
    927941    /// \name Query Functions
    928942    /// The result of the %HaoOrlin algorithm
    929     /// can be obtained using these functions.
    930     /// \n
    931     /// Before using these functions, either \ref run(), \ref
    932     /// calculateOut() or \ref calculateIn() must be called.
     943    /// can be obtained using these functions.\n
     944    /// \ref run(), \ref calculateOut() or \ref calculateIn()
     945    /// should be called before using them.
    933946
    934947    /// @{
    935948
    936     /// \brief Returns the value of the minimum value cut.
    937     ///
    938     /// Returns the value of the minimum value cut.
     949    /// \brief Return the value of the minimum cut.
     950    ///
     951    /// This function returns the value of the minimum cut.
     952    ///
     953    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
     954    /// must be called before using this function.
    939955    Value minCutValue() const {
    940956      return _min_cut;
    … …  
    942958
    943959
    944     /// \brief Returns a minimum cut.
    945     ///
    946     /// Sets \c nodeMap to the characteristic vector of a minimum
    947     /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
    948     /// with minimal out-degree (i.e. \c nodeMap will be true exactly
    949     /// for the nodes of \f$ X \f$).  \pre nodeMap should be a
    950     /// bool-valued node-map.
    951     template <typename NodeMap>
    952     Value minCutMap(NodeMap& nodeMap) const {
     960    /// \brief Return a minimum cut.
     961    ///
     962    /// This function sets \c cutMap to the characteristic vector of a
     963    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
     964    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
     965    /// for the nodes of \f$ X \f$).
     966    ///
     967    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
     968    /// \c bool (or convertible) value type.
     969    ///
     970    /// \return The value of the minimum cut.
     971    ///
     972    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
     973    /// must be called before using this function.
     974    template <typename CutMap>
     975    Value minCutMap(CutMap& cutMap) const {
    953976      for (NodeIt it(_graph); it != INVALID; ++it) {
    954         nodeMap.set(it, (*_min_cut_map)[it]);
     977        cutMap.set(it, (*_min_cut_map)[it]);
    955978      }
    956979      return _min_cut;
    … …  
    961984  }; //class HaoOrlin
    962985
    963 
    964986} //namespace lemon
    965987
Note: See TracChangeset for help on using the changeset viewer.