Loading...
Searching...
No Matches
HaoOrlin< GR, CAP, TOL > Class Template Reference
Algorithms » Minimum Cut Algorithms

## Detailed Description

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>.
  TOL | Tolerance class for handling inexact computations. The default tolerance type is Tolerance<CAP::Value>.

`#include <lemon/hao_orlin.h>`

## 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 Member Functions

| HaoOrlin (const Digraph &graph, const CapacityMap &capacity, const Tolerance &tolerance=Tolerance())
| Constructor.
HaoOrlin & | tolerance (const Tolerance &tolerance)
| Set the tolerance used by the algorithm.
const Tolerance & | tolerance () const
| Returns a const reference to the tolerance.
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().
void | init ()
| Initialize the internal data structures.
void | init (const Node &source)
| Initialize the internal data structures.
void | calculateOut ()
| Calculate a minimum cut with on the source-side.
void | calculateIn ()
| Calculate a minimum cut with on the sink-side.
void | run ()
| Run the algorithm.
void | run (const Node &s)
| Run the algorithm.
Query Functions
The result of the HaoOrlin algorithm can be obtained using these functions. run(), calculateOut() or calculateIn() should be called before using them.
Value | minCutValue () const
| Return the value of the minimum cut.
template<typename CutMap>
Value | minCutMap (CutMap &cutMap) const
| Return a minimum cut.

## Constructor & Destructor Documentation

## HaoOrlin()

template<typename GR, typename CAP, typename TOL>

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

inline

Constructor of the algorithm class.

## Member Function Documentation

## tolerance() [1/2]

template<typename GR, typename CAP, typename TOL>

HaoOrlin & tolerance | ( | const Tolerance & | tolerance | ) |

inline

This function sets the tolerance object used by the algorithm.

Returns
  (*this)

## tolerance() [2/2]

template<typename GR, typename CAP, typename TOL>

const Tolerance & tolerance | ( |  | ) | const

inline

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

## init() [1/2]

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.

## init() [2/2]

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.

## calculateOut()

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.

Precondition
  init() must be called before using this function.

## calculateIn()

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.

Precondition
  init() must be called before using this function.

## run() [1/2]

template<typename GR, typename CAP, typename TOL>

void run | ( |  | ) |

inline

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

## run() [2/2]

template<typename GR, typename CAP, typename TOL>

void run | ( | const Node & | s | ) |

inline

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

## minCutValue()

template<typename GR, typename CAP, typename TOL>

Value minCutValue | ( |  | ) | const

inline

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

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

## minCutMap()

template<typename GR, typename CAP, typename TOL>
template<typename CutMap>

Value minCutMap | ( | CutMap & | cutMap | ) | const

inline

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

Returns
  The value of the minimum cut.

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