# Changeset 1081:f1398882a928 in lemon for lemon/hao_orlin.h

Ignore:
Timestamp:
08/08/11 12:36:16 (9 years ago)
Branch:
1.1
Phase:
public
Tags:
r1.1.4
Message:

Unify sources

File:
1 edited

### Legend:

Unmodified
 r644 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \brief Implementation of the Hao-Orlin algorithm. /// /// Implementation of the Hao-Orlin algorithm for finding a minimum cut /// Implementation of the Hao-Orlin algorithm for finding a minimum cut /// in a digraph. /// /// This class implements the Hao-Orlin algorithm for finding a minimum /// value cut in a directed graph \f$D=(V,A)\f$. /// value cut in a directed graph \f$D=(V,A)\f$. /// It takes a fixed node \f$source \in V \f$ and /// consists of two phases: in the first phase it determines a /// For an undirected graph you can run just the first phase of the /// algorithm or you can use the algorithm of Nagamochi and Ibaraki, /// which solves the undirected problem in \f$O(nm + n^2 \log n) \f$ /// which solves the undirected problem in \f$O(nm + n^2 \log n) \f$ /// time. It is implemented in the NagamochiIbaraki algorithm class. /// class HaoOrlin { public: /// The digraph type of the algorithm typedef GR Digraph; /// /// This function initializes the internal data structures. It creates /// the maps and some bucket structures for the algorithm. /// the maps and some bucket structures for the algorithm. /// The given node is used as the source node for the push-relabel /// algorithm. /// \brief Run the algorithm. /// /// This function runs the algorithm. It uses the given \c source node, /// This function runs the algorithm. It uses the given \c source node, /// finds a proper \c target node and then calls the \ref init(), /// \ref calculateOut() and \ref calculateIn(). /// The result of the %HaoOrlin algorithm /// can be obtained using these functions.\n /// \ref run(), \ref calculateOut() or \ref calculateIn() /// \ref run(), \ref calculateOut() or \ref calculateIn() /// should be called before using them. /// This function returns the value of the minimum cut. /// /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// must be called before using this function. Value minCutValue() const { /// \return The value of the minimum cut. /// /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// must be called before using this function. template