template<typename GR, typename CAP, typename TOL>
class lemon::HaoOrlin< GR, CAP, TOL >
This class implements the Hao-Orlin algorithm for finding a minimum value cut in a directed graph . It takes a fixed node and consists of two phases: in the first phase it determines a minimum cut with on the source-side (i.e. a set with and minimal outgoing capacity) and in the second phase it determines a minimum cut with on the sink-side (i.e. a set with and minimal outgoing capacity). Obviously, the smaller of these two cuts will be a minimum cut of . The algorithm is a modified preflow push-relabel algorithm. Our implementation calculates the minimum cut in time (we use the highest-label rule), or in for unit capacities. A notable use of this algorithm is testing network reliability.
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 time. It is implemented in the NagamochiIbaraki algorithm class.
Template Parameters
GR
The type of the digraph the algorithm runs on.
CAP
The type of the arc map containing the capacities, which can be any numreric type. The default map type is GR::ArcMap<int>.
The simplest way to execute the algorithm is to use one of the member functions called run().
If you need better control on the execution, you have to call one of the init() functions first, then calculateOut() and/or calculateIn().
template<typename GR , typename CAP , typename TOL >
void init
(
)
inline
This function initializes the internal data structures. It creates the maps and some bucket structures for the algorithm. The first node is used as the source node for the push-relabel algorithm.
template<typename GR , typename CAP , typename TOL >
void init
(
const Node &
source
)
inline
This function initializes the internal data structures. It creates the maps and some bucket structures for the algorithm. The given node is used as the source node for the push-relabel algorithm.
template<typename GR , typename CAP , typename TOL >
void calculateOut
(
)
inline
This function calculates a minimum cut with on the source-side (i.e. a set with and minimal outgoing capacity). It updates the stored cut if (and only if) the newly found one is better.
template<typename GR , typename CAP , typename TOL >
void calculateIn
(
)
inline
This function calculates a minimum cut with on the sink-side (i.e. a set with and minimal outgoing capacity). It updates the stored cut if (and only if) the newly found one is better.
It sets cutMap to the characteristic vector of the found minimum value cut - a non-empty set of minimum outgoing capacity (i.e. cutMap will be true exactly for the nodes of ).
Parameters
cutMap
A writable node map with bool (or convertible) value type.