lemon/hao_orlin.h
changeset 2228 f71b0f9a7c3a
parent 2225 bb3d5e6f9fcb
child 2273 507232469f5e
equal deleted inserted replaced
1:3acf1fd77c98 2:75b74513b308
    38 
    38 
    39 namespace lemon {
    39 namespace lemon {
    40 
    40 
    41   /// \ingroup flowalgs
    41   /// \ingroup flowalgs
    42   ///
    42   ///
    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.
    44   ///
    44   ///
    45   /// Hao-Orlin calculates the minimum cut in directed graphs. It
    45   /// Hao-Orlin calculates a minimum cut in a directed graph \f$
    46   /// separates the nodes of the graph into two disjoint sets, 
    46   /// D=(V,A) \f$. It takes a fixed node \f$ source \in V \f$ and consists
    47   /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum
    47   /// of two phases: in the first phase it determines a minimum cut
    48   /// cut if the summary of the edge capacities which source is in
    48   /// with \f$ source \f$ on the source-side (i.e. a set \f$ X\subsetneq V
    49   /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the
    49   /// \f$ with \f$ source \in X \f$ and minimal out-degree) and in the
    50   /// minimum.  The algorithm is a modified push-relabel preflow
    50   /// second phase it determines a minimum cut with \f$ source \f$ on the
    51   /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$
    51   /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X \f$
    52   /// time. The purpose of such algorithm is testing network
    52   /// and minimal out-degree). Obviously, the smaller of these two
    53   /// reliability. For sparse undirected graph you can use the
    53   /// cuts will be a minimum cut of \f$ D \f$. The algorithm is a
    54   /// algorithm of Nagamochi and Ibaraki which solves the undirected
    54   /// modified push-relabel preflow algorithm and our implementation
    55   /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the
    55   /// calculates the minimum cut in \f$ O(n^3) \f$ time (we use the
    56   /// MinCut algorithm class.
    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.
    57   ///
    62   ///
    58   /// \param _Graph is the graph type of the algorithm.
    63   /// \param _Graph is the graph type of the algorithm.
    59   /// \param _CapacityMap is an edge map of capacities which should
    64   /// \param _CapacityMap is an edge map of capacities which should
    60   /// be any numreric type. The default type is _Graph::EdgeMap<int>.
    65   /// be any numreric type. The default type is _Graph::EdgeMap<int>.
    61   /// \param _Tolerance is the handler of the inexact computation. The
    66   /// \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>.
    63   ///
    68   ///
    64   /// \author Attila Bernath and Balazs Dezso
    69   /// \author Attila Bernath and Balazs Dezso
    65 #ifdef DOXYGEN
    70 #ifdef DOXYGEN
    66   template <typename _Graph, typename _CapacityMap, typename _Tolerance>
    71   template <typename _Graph, typename _CapacityMap, typename _Tolerance>
    67 #else
    72 #else
   476 
   481 
   477     /// \brief Initializes the internal data structures.
   482     /// \brief Initializes the internal data structures.
   478     ///
   483     ///
   479     /// Initializes the internal data structures. It creates
   484     /// Initializes the internal data structures. It creates
   480     /// the maps, residual graph adaptor and some bucket structures
   485     /// 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
   482     /// algorithm's source.
   487     /// algorithm's source.
   483     void init(const Node& source) {
   488     void init(const Node& source) {
   484       _source = source;
   489       _source = source;
   485       _node_num = countNodes(*_graph);
   490       _node_num = countNodes(*_graph);
   486 
   491 
   524 
   529 
   525       _min_cut = std::numeric_limits<Value>::max();
   530       _min_cut = std::numeric_limits<Value>::max();
   526     }
   531     }
   527 
   532 
   528 
   533 
   529     /// \brief Calculates the minimum cut with the \c source node
   534     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   530     /// in the \f$ V_{out} \f$.
   535     /// source-side.
   531     ///
   536     ///
   532     /// Calculates the minimum cut with the \c source node
   537     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   533     /// in the \f$ V_{out} \f$.
   538     /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X
       
   539     /// \f$ and minimal out-degree).
   534     void calculateOut() {
   540     void calculateOut() {
   535       for (NodeIt it(*_graph); it != INVALID; ++it) {
   541       for (NodeIt it(*_graph); it != INVALID; ++it) {
   536         if (it != _source) {
   542         if (it != _source) {
   537           calculateOut(it);
   543           calculateOut(it);
   538           return;
   544           return;
   539         }
   545         }
   540       }
   546       }
   541     }
   547     }
   542 
   548 
   543     /// \brief Calculates the minimum cut with the \c source node
   549     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   544     /// in the \f$ V_{out} \f$.
   550     /// source-side.
   545     ///
   551     ///
   546     /// Calculates the minimum cut with the \c source node
   552     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   547     /// in the \f$ V_{out} \f$. The \c target is the initial target
   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
   548     /// for the push-relabel algorithm.
   555     /// for the push-relabel algorithm.
   549     void calculateOut(const Node& target) {
   556     void calculateOut(const Node& target) {
   550       findMinCut(target, true, *_out_res_graph, *_out_current_edge);
   557       findMinCut(target, true, *_out_res_graph, *_out_current_edge);
   551     }
   558     }
   552 
   559 
   553     /// \brief Calculates the minimum cut with the \c source node
   560     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   554     /// in the \f$ V_{in} \f$.
   561     /// sink-side.
   555     ///
   562     ///
   556     /// Calculates the minimum cut with the \c source node
   563     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   557     /// in the \f$ V_{in} \f$.
   564     /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X
       
   565     /// \f$ and minimal out-degree).
   558     void calculateIn() {
   566     void calculateIn() {
   559       for (NodeIt it(*_graph); it != INVALID; ++it) {
   567       for (NodeIt it(*_graph); it != INVALID; ++it) {
   560         if (it != _source) {
   568         if (it != _source) {
   561           calculateIn(it);
   569           calculateIn(it);
   562           return;
   570           return;
   563         }
   571         }
   564       }
   572       }
   565     }
   573     }
   566 
   574 
   567     /// \brief Calculates the minimum cut with the \c source node
   575     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   568     /// in the \f$ V_{in} \f$.
   576     /// sink-side.
   569     ///
   577     ///
   570     /// Calculates the minimum cut with the \c source node
   578     /// \brief Calculates a minimum cut with \f$ source \f$ on the
   571     /// in the \f$ V_{in} \f$. The \c target is the initial target
   579     /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin
   572     /// for the push-relabel algorithm.
   580     /// X \f$ and minimal out-degree).  The \c target is the initial
       
   581     /// target for the push-relabel algorithm.
   573     void calculateIn(const Node& target) {
   582     void calculateIn(const Node& target) {
   574       findMinCut(target, false, *_in_res_graph, *_in_current_edge);
   583       findMinCut(target, false, *_in_res_graph, *_in_current_edge);
   575     }
   584     }
   576 
   585 
   577     /// \brief Runs the algorithm.
   586     /// \brief Runs the algorithm.
   578     ///
   587     ///
   579     /// Runs the algorithm. It finds a proper \c source and \c target
   588     /// Runs the algorithm. It finds nodes \c source and \c target
   580     /// and then calls the \ref init(), \ref calculateOut() and \ref
   589     /// arbitrarily and then calls \ref init(), \ref calculateOut()
   581     /// calculateIn().
   590     /// and \ref calculateIn().
   582     void run() {
   591     void run() {
   583       init();
   592       init();
   584       for (NodeIt it(*_graph); it != INVALID; ++it) {
   593       for (NodeIt it(*_graph); it != INVALID; ++it) {
   585         if (it != _source) {
   594         if (it != _source) {
   586           calculateOut(it);
   595           calculateOut(it);
   590       }
   599       }
   591     }
   600     }
   592 
   601 
   593     /// \brief Runs the algorithm.
   602     /// \brief Runs the algorithm.
   594     ///
   603     ///
   595     /// Runs the algorithm. It finds a proper \c target and then calls
   604     /// Runs the algorithm. It uses the given \c source node, finds a
   596     /// the \ref init(), \ref calculateOut() and \ref calculateIn().
   605     /// proper \c target and then calls the \ref init(), \ref
       
   606     /// calculateOut() and \ref calculateIn().
   597     void run(const Node& s) {
   607     void run(const Node& s) {
   598       init(s);
   608       init(s);
   599       for (NodeIt it(*_graph); it != INVALID; ++it) {
   609       for (NodeIt it(*_graph); it != INVALID; ++it) {
   600         if (it != _source) {
   610         if (it != _source) {
   601           calculateOut(it);
   611           calculateOut(it);
   631     Value minCut() const {
   641     Value minCut() const {
   632       return _min_cut;
   642       return _min_cut;
   633     }
   643     }
   634 
   644 
   635 
   645 
   636     /// \brief Returns a minimum value cut.
   646     /// \brief Returns a minimum cut.
   637     ///
   647     ///
   638     /// Sets \c nodeMap to the characteristic vector of a minimum
   648     /// 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
   649     /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
   640     /// the nodes in \f$ V_{in} \f$ will be set false. 
   650     /// with minimal out-degree (i.e. \c nodeMap will be true exactly
   641     /// \pre nodeMap should be a bool-valued node-map.
   651     /// for the nodes of \f$ X \f$.  \pre nodeMap should be a
       
   652     /// bool-valued node-map.
   642     template <typename NodeMap>
   653     template <typename NodeMap>
   643     Value minCut(NodeMap& nodeMap) const {
   654     Value minCut(NodeMap& nodeMap) const {
   644       for (NodeIt it(*_graph); it != INVALID; ++it) {
   655       for (NodeIt it(*_graph); it != INVALID; ++it) {
   645 	nodeMap.set(it, (*_min_cut_map)[it]);
   656 	nodeMap.set(it, (*_min_cut_map)[it]);
   646       }
   657       }