lemon/hao_orlin.h
changeset 1055 05b34170866b
parent 877 141f9c0db4a3
child 1092 dceba191c00d
equal deleted inserted replaced
9:6ab23b8eb3da 10:eb1df81281c5
    51   /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing
    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
    52   /// capacity). Obviously, the smaller of these two cuts will be a
    53   /// minimum cut of \f$ D \f$. The algorithm is a modified
    53   /// minimum cut of \f$ D \f$. The algorithm is a modified
    54   /// preflow push-relabel algorithm. Our implementation calculates
    54   /// preflow push-relabel algorithm. Our implementation calculates
    55   /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
    55   /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
    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. A notable
    57   /// purpose of such algorithm is e.g. testing network reliability.
    57   /// use of this algorithm is 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.
   910     /// source-side.
   910     /// source-side.
   911     ///
   911     ///
   912     /// This function calculates a minimum cut with \f$ source \f$ on the
   912     /// This function calculates a minimum cut with \f$ source \f$ on the
   913     /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
   913     /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
   914     /// \f$ source \in X \f$ and minimal outgoing capacity).
   914     /// \f$ source \in X \f$ and minimal outgoing capacity).
       
   915     /// It updates the stored cut if (and only if) the newly found one
       
   916     /// is better.
   915     ///
   917     ///
   916     /// \pre \ref init() must be called before using this function.
   918     /// \pre \ref init() must be called before using this function.
   917     void calculateOut() {
   919     void calculateOut() {
   918       findMinCutOut();
   920       findMinCutOut();
   919     }
   921     }
   922     /// sink-side.
   924     /// sink-side.
   923     ///
   925     ///
   924     /// This function calculates a minimum cut with \f$ source \f$ on the
   926     /// This function calculates a minimum cut with \f$ source \f$ on the
   925     /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
   927     /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
   926     /// \f$ source \notin X \f$ and minimal outgoing capacity).
   928     /// \f$ source \notin X \f$ and minimal outgoing capacity).
       
   929     /// It updates the stored cut if (and only if) the newly found one
       
   930     /// is better.
   927     ///
   931     ///
   928     /// \pre \ref init() must be called before using this function.
   932     /// \pre \ref init() must be called before using this function.
   929     void calculateIn() {
   933     void calculateIn() {
   930       findMinCutIn();
   934       findMinCutIn();
   931     }
   935     }
   932 
   936 
   933 
   937 
   934     /// \brief Run the algorithm.
   938     /// \brief Run the algorithm.
   935     ///
   939     ///
   936     /// This function runs the algorithm. It finds nodes \c source and
   940     /// This function runs the algorithm. It chooses source node,
   937     /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
   941     /// then calls \ref init(), \ref calculateOut()
   938     /// and \ref calculateIn().
   942     /// and \ref calculateIn().
   939     void run() {
   943     void run() {
   940       init();
   944       init();
   941       calculateOut();
   945       calculateOut();
   942       calculateIn();
   946       calculateIn();
   943     }
   947     }
   944 
   948 
   945     /// \brief Run the algorithm.
   949     /// \brief Run the algorithm.
   946     ///
   950     ///
   947     /// This function runs the algorithm. It uses the given \c source node,
   951     /// This function runs the algorithm. It calls \ref init(),
   948     /// finds a proper \c target node and then calls the \ref init(),
   952     /// \ref calculateOut() and \ref calculateIn() with the given
   949     /// \ref calculateOut() and \ref calculateIn().
   953     /// source node.
   950     void run(const Node& s) {
   954     void run(const Node& s) {
   951       init(s);
   955       init(s);
   952       calculateOut();
   956       calculateOut();
   953       calculateIn();
   957       calculateIn();
   954     }
   958     }
   963 
   967 
   964     /// @{
   968     /// @{
   965 
   969 
   966     /// \brief Return the value of the minimum cut.
   970     /// \brief Return the value of the minimum cut.
   967     ///
   971     ///
   968     /// This function returns the value of the minimum cut.
   972     /// This function returns the value of the best cut found by the
       
   973     /// previously called \ref run(), \ref calculateOut() or \ref
       
   974     /// calculateIn().
   969     ///
   975     ///
   970     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
   976     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
   971     /// must be called before using this function.
   977     /// must be called before using this function.
   972     Value minCutValue() const {
   978     Value minCutValue() const {
   973       return _min_cut;
   979       return _min_cut;
   974     }
   980     }
   975 
   981 
   976 
   982 
   977     /// \brief Return a minimum cut.
   983     /// \brief Return a minimum cut.
   978     ///
   984     ///
   979     /// This function sets \c cutMap to the characteristic vector of a
   985     /// This function gives the best cut found by the
   980     /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
   986     /// previously called \ref run(), \ref calculateOut() or \ref
   981     /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
   987     /// calculateIn().
       
   988     ///
       
   989     /// It sets \c cutMap to the characteristic vector of the found
       
   990     /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
       
   991     /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
   982     /// for the nodes of \f$ X \f$).
   992     /// for the nodes of \f$ X \f$).
   983     ///
   993     ///
   984     /// \param cutMap A \ref concepts::WriteMap "writable" node map with
   994     /// \param cutMap A \ref concepts::WriteMap "writable" node map with
   985     /// \c bool (or convertible) value type.
   995     /// \c bool (or convertible) value type.
   986     ///
   996     ///