lemon/hao_orlin.h
changeset 893 d395358592df
parent 860 930ddeafdb20
child 915 234d635ad721
equal deleted inserted replaced
8:4f44244994d6 9:6ab23b8eb3da
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    29 
    29 
    30 /// \file
    30 /// \file
    31 /// \ingroup min_cut
    31 /// \ingroup min_cut
    32 /// \brief Implementation of the Hao-Orlin algorithm.
    32 /// \brief Implementation of the Hao-Orlin algorithm.
    33 ///
    33 ///
    34 /// Implementation of the Hao-Orlin algorithm for finding a minimum cut 
    34 /// Implementation of the Hao-Orlin algorithm for finding a minimum cut
    35 /// in a digraph.
    35 /// in a digraph.
    36 
    36 
    37 namespace lemon {
    37 namespace lemon {
    38 
    38 
    39   /// \ingroup min_cut
    39   /// \ingroup min_cut
    40   ///
    40   ///
    41   /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
    41   /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
    42   ///
    42   ///
    43   /// This class implements the Hao-Orlin algorithm for finding a minimum
    43   /// This class implements the Hao-Orlin algorithm for finding a minimum
    44   /// value cut in a directed graph \f$D=(V,A)\f$. 
    44   /// value cut in a directed graph \f$D=(V,A)\f$.
    45   /// It takes a fixed node \f$ source \in V \f$ and
    45   /// It takes a fixed node \f$ source \in V \f$ and
    46   /// consists of two phases: in the first phase it determines a
    46   /// consists of two phases: in the first phase it determines a
    47   /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
    47   /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
    48   /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing
    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
    49   /// capacity) and in the second phase it determines a minimum cut
    56   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    56   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    57   /// purpose of such algorithm is e.g. testing network reliability.
    57   /// purpose of such algorithm is e.g. testing network reliability.
    58   ///
    58   ///
    59   /// For an undirected graph you can run just the first phase of 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,
    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$ 
    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.
    62   /// time. It is implemented in the NagamochiIbaraki algorithm class.
    63   ///
    63   ///
    64   /// \tparam GR The type of the digraph the algorithm runs on.
    64   /// \tparam GR The type of the digraph the algorithm runs on.
    65   /// \tparam CAP The type of the arc map containing the capacities,
    65   /// \tparam CAP The type of the arc map containing the capacities,
    66   /// which can be any numreric type. The default map type is
    66   /// which can be any numreric type. The default map type is
    74             typename CAP = typename GR::template ArcMap<int>,
    74             typename CAP = typename GR::template ArcMap<int>,
    75             typename TOL = Tolerance<typename CAP::Value> >
    75             typename TOL = Tolerance<typename CAP::Value> >
    76 #endif
    76 #endif
    77   class HaoOrlin {
    77   class HaoOrlin {
    78   public:
    78   public:
    79    
    79 
    80     /// The digraph type of the algorithm
    80     /// The digraph type of the algorithm
    81     typedef GR Digraph;
    81     typedef GR Digraph;
    82     /// The capacity map type of the algorithm
    82     /// The capacity map type of the algorithm
    83     typedef CAP CapacityMap;
    83     typedef CAP CapacityMap;
    84     /// The tolerance type of the algorithm
    84     /// The tolerance type of the algorithm
   862     }
   862     }
   863 
   863 
   864     /// \brief Initialize the internal data structures.
   864     /// \brief Initialize the internal data structures.
   865     ///
   865     ///
   866     /// This function initializes the internal data structures. It creates
   866     /// This function initializes the internal data structures. It creates
   867     /// the maps and some bucket structures for the algorithm. 
   867     /// the maps and some bucket structures for the algorithm.
   868     /// The given node is used as the source node for the push-relabel
   868     /// The given node is used as the source node for the push-relabel
   869     /// algorithm.
   869     /// algorithm.
   870     void init(const Node& source) {
   870     void init(const Node& source) {
   871       _source = source;
   871       _source = source;
   872 
   872 
   942       calculateIn();
   942       calculateIn();
   943     }
   943     }
   944 
   944 
   945     /// \brief Run the algorithm.
   945     /// \brief Run the algorithm.
   946     ///
   946     ///
   947     /// This function runs the algorithm. It uses the given \c source node, 
   947     /// This function runs the algorithm. It uses the given \c source node,
   948     /// finds a proper \c target node and then calls the \ref init(),
   948     /// finds a proper \c target node and then calls the \ref init(),
   949     /// \ref calculateOut() and \ref calculateIn().
   949     /// \ref calculateOut() and \ref calculateIn().
   950     void run(const Node& s) {
   950     void run(const Node& s) {
   951       init(s);
   951       init(s);
   952       calculateOut();
   952       calculateOut();
   956     /// @}
   956     /// @}
   957 
   957 
   958     /// \name Query Functions
   958     /// \name Query Functions
   959     /// The result of the %HaoOrlin algorithm
   959     /// The result of the %HaoOrlin algorithm
   960     /// can be obtained using these functions.\n
   960     /// can be obtained using these functions.\n
   961     /// \ref run(), \ref calculateOut() or \ref calculateIn() 
   961     /// \ref run(), \ref calculateOut() or \ref calculateIn()
   962     /// should be called before using them.
   962     /// should be called before using them.
   963 
   963 
   964     /// @{
   964     /// @{
   965 
   965 
   966     /// \brief Return the value of the minimum cut.
   966     /// \brief Return the value of the minimum cut.
   967     ///
   967     ///
   968     /// This function returns the value of the minimum cut.
   968     /// This function returns the value of the minimum cut.
   969     ///
   969     ///
   970     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
   970     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
   971     /// must be called before using this function.
   971     /// must be called before using this function.
   972     Value minCutValue() const {
   972     Value minCutValue() const {
   973       return _min_cut;
   973       return _min_cut;
   974     }
   974     }
   975 
   975 
   984     /// \param cutMap A \ref concepts::WriteMap "writable" node map with
   984     /// \param cutMap A \ref concepts::WriteMap "writable" node map with
   985     /// \c bool (or convertible) value type.
   985     /// \c bool (or convertible) value type.
   986     ///
   986     ///
   987     /// \return The value of the minimum cut.
   987     /// \return The value of the minimum cut.
   988     ///
   988     ///
   989     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
   989     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
   990     /// must be called before using this function.
   990     /// must be called before using this function.
   991     template <typename CutMap>
   991     template <typename CutMap>
   992     Value minCutMap(CutMap& cutMap) const {
   992     Value minCutMap(CutMap& cutMap) const {
   993       for (NodeIt it(_graph); it != INVALID; ++it) {
   993       for (NodeIt it(_graph); it != INVALID; ++it) {
   994         cutMap.set(it, (*_min_cut_map)[it]);
   994         cutMap.set(it, (*_min_cut_map)[it]);