/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

 /// \file

 /// \file

 /// \ingroup min_cut

 /// \ingroup min_cut

 /// \brief Implementation of the Hao-Orlin algorithm.

 /// \brief Implementation of the Hao-Orlin algorithm.

 ///

 ///

 /// in a digraph.

 /// in a digraph.

 namespace lemon {

 namespace lemon {

   /// \ingroup min_cut

   /// \ingroup min_cut

   ///

   ///

   /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.

   /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.

   ///

   ///

   /// This class implements the Hao-Orlin algorithm for finding a minimum

   /// This class implements the Hao-Orlin algorithm for finding a minimum

   /// It takes a fixed node \f$ source \in V \f$ and

   /// It takes a fixed node \f$ source \in V \f$ and

   /// consists of two phases: in the first phase it determines a

   /// 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

   /// 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 outgoing

   /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing

   /// capacity) and in the second phase it determines a minimum cut

   /// capacity) and in the second phase it determines a minimum cut

   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The

   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The

   /// purpose of such algorithm is e.g. testing network reliability.

   /// purpose of such algorithm is e.g. testing network reliability.

   ///

   ///

   /// For an undirected graph you can run just the first phase of the

   /// For an undirected graph you can run just the first phase of the

   /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,

   /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,

   /// time. It is implemented in the NagamochiIbaraki algorithm class.

   /// time. It is implemented in the NagamochiIbaraki algorithm class.

   ///

   ///

   /// \tparam GR The type of the digraph the algorithm runs on.

   /// \tparam GR The type of the digraph the algorithm runs on.

   /// \tparam CAP The type of the arc map containing the capacities,

   /// \tparam CAP The type of the arc map containing the capacities,

   /// which can be any numreric type. The default map type is

   /// which can be any numreric type. The default map type is

             typename CAP = typename GR::template ArcMap<int>,

             typename CAP = typename GR::template ArcMap<int>,

             typename TOL = Tolerance<typename CAP::Value> >

             typename TOL = Tolerance<typename CAP::Value> >

 #endif

 #endif

   class HaoOrlin {

   class HaoOrlin {

   public:

   public:

     /// The digraph type of the algorithm

     /// The digraph type of the algorithm

     typedef GR Digraph;

     typedef GR Digraph;

     /// The capacity map type of the algorithm

     /// The capacity map type of the algorithm

     typedef CAP CapacityMap;

     typedef CAP CapacityMap;

     /// The tolerance type of the algorithm

     /// The tolerance type of the algorithm

     }

     }

     /// \brief Initialize the internal data structures.

     /// \brief Initialize the internal data structures.

     ///

     ///

     /// This function initializes the internal data structures. It creates

     /// This function initializes the internal data structures. It creates

     /// The given node is used as the source node for the push-relabel

     /// The given node is used as the source node for the push-relabel

     /// algorithm.

     /// algorithm.

     void init(const Node& source) {

     void init(const Node& source) {

       _source = source;

       _source = source;

       calculateIn();

       calculateIn();

     }

     }

     /// \brief Run the algorithm.

     /// \brief Run the algorithm.

     ///

     ///

     /// finds a proper \c target node and then calls the \ref init(),

     /// finds a proper \c target node and then calls the \ref init(),

     /// \ref calculateOut() and \ref calculateIn().

     /// \ref calculateOut() and \ref calculateIn().

     void run(const Node& s) {

     void run(const Node& s) {

       init(s);

       init(s);

       calculateOut();

       calculateOut();

     /// @}

     /// @}

     /// \name Query Functions

     /// \name Query Functions

     /// The result of the %HaoOrlin algorithm

     /// The result of the %HaoOrlin algorithm

     /// can be obtained using these functions.\n

     /// can be obtained using these functions.\n

     /// should be called before using them.

     /// should be called before using them.

     /// @{

     /// @{

     /// \brief Return the value of the minimum cut.

     /// \brief Return the value of the minimum cut.

     ///

     ///

     /// This function returns the value of the minimum cut.

     /// This function returns the value of the minimum cut.

     ///

     ///

     /// must be called before using this function.

     /// must be called before using this function.

     Value minCutValue() const {

     Value minCutValue() const {

       return _min_cut;

       return _min_cut;

     }

     }

     /// \param cutMap A \ref concepts::WriteMap "writable" node map with

     /// \param cutMap A \ref concepts::WriteMap "writable" node map with

     /// \c bool (or convertible) value type.

     /// \c bool (or convertible) value type.

     ///

     ///

     /// \return The value of the minimum cut.

     /// \return The value of the minimum cut.

     ///

     ///

     /// must be called before using this function.

     /// must be called before using this function.

     template <typename CutMap>

     template <typename CutMap>

     Value minCutMap(CutMap& cutMap) const {

     Value minCutMap(CutMap& cutMap) const {

       for (NodeIt it(_graph); it != INVALID; ++it) {

       for (NodeIt it(_graph); it != INVALID; ++it) {

         cutMap.set(it, (*_min_cut_map)[it]);

         cutMap.set(it, (*_min_cut_map)[it]);