HaoOrlin

Declared in lemon/hao_orlin.h, in the group Minimum Cut Algorithms; the same class on the Doxygen site.

template< typename GR , typename CAP , typename TOL >
class HaoOrlin

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 \(D=(V,A)\). It takes a fixed node \( source \in V \) and consists of two phases: in the first phase it determines a minimum cut with \( source \) on the source-side (i.e. a set \( X\subsetneq V \) with \( source \in X \) and minimal outgoing capacity) and in the second phase it determines a minimum cut with \( source \) on the sink-side (i.e. a set \( X\subsetneq V \) with \( source \notin X \) and minimal outgoing capacity). Obviously, the smaller of these two cuts will be a minimum cut of \( D \). The algorithm is a modified preflow push-relabel algorithm. Our implementation calculates the minimum cut in \( O(n^2\sqrt{m}) \) time (we use the highest-label rule), or in \(O(nm)\) 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 \( O( nm + n^2 \log n ) \) 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 >.

  • TOL – Tolerance class for handling inexact computations. The default tolerance type is Tolerance< CAP::Value >.

Execution Control

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().

inline void init()

Initialize the internal data structures.

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.

Pre:

The digraph has at least two nodes.

inline void init( const Node & source )

Initialize the internal data structures.

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.

Pre:

The digraph has at least two nodes, since a cut is a nonempty proper subset of them.

inline void calculateOut()

Calculate a minimum cut with \( source \) on the source-side.

This function calculates a minimum cut with \( source \) on the source-side (i.e. a set \( X\subsetneq V \) with \( source \in X \) and minimal outgoing capacity). It updates the stored cut if (and only if) the newly found one is better.

Pre:

init() must be called before using this function.

inline void calculateIn()

Calculate a minimum cut with \( source \) on the sink-side.

This function calculates a minimum cut with \( source \) on the sink-side (i.e. a set \( X\subsetneq V \) with \( source \notin X \) and minimal outgoing capacity). It updates the stored cut if (and only if) the newly found one is better.

Pre:

init() must be called before using this function.

inline void run()

Run the algorithm.

This function runs the algorithm. It chooses source node, then calls init(), calculateOut() and calculateIn().

inline void run( const Node & s )

Run the algorithm.

This function runs the algorithm. It calls init(), calculateOut() and calculateIn() with the given source node.

Query Functions

The result of the HaoOrlin algorithm can be obtained using these functions. run(), calculateOut() or calculateIn() should be called before using them.

inline Value minCutValue() const

Return the value of the minimum cut.

This function returns the value of the best cut found by the previously called run(), calculateOut() or calculateIn().

Pre:

run(), calculateOut() or calculateIn() must be called before using this function.

template< typename CutMap >
inline Value minCutMap( CutMap & cutMap ) const

Return a minimum cut.

This function gives the best cut found by the previously called run(), calculateOut() or calculateIn().

It sets cutMap to the characteristic vector of the found minimum value cut - a non-empty set \( X\subsetneq V \) of minimum outgoing capacity (i.e. cutMap will be true exactly for the nodes of \( X \)).

Parameters:

cutMap – A writable node map with bool (or convertible) value type.

Returns:

The value of the minimum cut.

Pre:

run(), calculateOut() or calculateIn() must be called before using this function.

Public Types

typedef GR Digraph

The digraph type of the algorithm.

typedef CAP CapacityMap

The capacity map type of the algorithm.

typedef TOL Tolerance

The tolerance type of the algorithm.

Public Functions

inline HaoOrlin(
const Digraph & graph,
const CapacityMap & capacity,
const Tolerance & tolerance = Tolerance()
)

Constructor.

Constructor of the algorithm class.

inline ~HaoOrlin()
inline HaoOrlin & tolerance( const Tolerance & tolerance )

Set the tolerance used by the algorithm.

This function sets the tolerance object used by the algorithm.

Returns:

(*this)

inline const Tolerance & tolerance() const

Returns a const reference to the tolerance.

This function returns a const reference to the tolerance object used by the algorithm.