HaoOrlin< _Graph, _CapacityMap, _Tolerance > Class Template Reference
[Minimum Cut algorithms]

Detailed Description

template<typename _Graph, typename _CapacityMap, typename _Tolerance>
class lemon::HaoOrlin< _Graph, _CapacityMap, _Tolerance >

Hao-Orlin calculates a minimum 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 out-degree) 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 out-degree). Obviously, the smaller of these two cuts will be a minimum cut of $ D $

. The algorithm is a modified push-relabel preflow algorithm and 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. The purpose of such 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.

Parameters:

	_Graph	is the graph type of the algorithm.
	_CapacityMap	is an edge map of capacities which should be any numreric type. The default type is _Graph::EdgeMap<int>.
	_Tolerance	is the handler of the inexact computation. The default type for this is Tolerance<typename CapacityMap::Value>.

Author:: Attila Bernath and Balazs Dezso

#include <lemon/hao_orlin.h>

List of all members.

Public Member Functions

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

Constructor.

Execution control

The simplest way to execute the algorithm is to use one of the member functions called run(...).
If you need more control on the execution, first you must call init(), then the calculateIn() or calculateIn() functions.

void init ()

Initializes the internal data structures.

void init (const Node &source)

Initializes the internal data structures.

void calculateOut ()

Calculates a minimum cut with $ source $ on the source-side.

void calculateIn ()

Calculates a minimum cut with on the target-side.

void run ()

Runs the algorithm.

void run (const Node &s)

Runs the algorithm.

Query Functions

The result of the HaoOrlin algorithm can be obtained using these functions.
Before using these functions, either run(), calculateOut() or calculateIn() must be called.

Value minCut () const

template<typename NodeMap >

Value minCut (NodeMap &nodeMap) const

Returns a minimum cut.

Constructor & Destructor Documentation

HaoOrlin	(	const Graph &	graph,
		const CapacityMap &	capacity,
		const Tolerance &	tolerance = `Tolerance()`
	)			`[inline]`

Constructor of the algorithm class.

Member Function Documentation

void init ( ) [inline]

Initializes the internal data structures. It creates the maps, residual graph adaptors and some bucket structures for the algorithm.

void init ( const Node & source ) [inline]

Initializes the internal data structures. It creates the maps, residual graph adaptor and some bucket structures for the algorithm. Node source is used as the push-relabel algorithm's source.

void calculateOut ( ) [inline]

Calculates a minimum cut with $ source $ on the source-side (i.e. a set $X\subsetneq V$ with $source /// \in X$ and minimal out-degree).

void calculateIn ( ) [inline]

Calculates a minimum cut with $ source $ on the target-side (i.e. a set $X\subsetneq V$ with $source /// \in X$ and minimal out-degree).

void run ( ) [inline]

Runs the algorithm. It finds nodes source and target arbitrarily and then calls init(), calculateOut() and calculateIn().

void run ( const Node & s ) [inline]

Runs the algorithm. It uses the given source node, finds a proper target and then calls the init(), calculateOut() and calculateIn().

Value minCut ( ) const [inline]

Returns the value of the minimum value cut.

Value minCut ( NodeMap & nodeMap ) const [inline]

Sets nodeMap to the characteristic vector of a minimum value cut: it will give a nonempty set $X\subsetneq V$ with minimal out-degree (i.e. nodeMap will be true exactly for the nodes of $ X $ ).

Precondition:: nodeMap should be a bool-valued node-map.


Public Member Functions
	HaoOrlin (const Graph &graph, const CapacityMap &capacity, const Tolerance &tolerance=Tolerance())
	Constructor.
Execution control
The simplest way to execute the algorithm is to use one of the member functions called `run`(...). If you need more control on the execution, first you must call init(), then the calculateIn() or calculateIn() functions.
void	init ()
	Initializes the internal data structures.
void	init (const Node &source)
	Initializes the internal data structures.
void	calculateOut ()
	Calculates a minimum cut with on the source-side.
void	calculateIn ()
	Calculates a minimum cut with on the target-side.
void	run ()
	Runs the algorithm.
void	run (const Node &s)
	Runs the algorithm.
Query Functions
The result of the HaoOrlin algorithm can be obtained using these functions. Before using these functions, either run(), calculateOut() or calculateIn() must be called.
Value	minCut () const
template<typename NodeMap >
Value	minCut (NodeMap &nodeMap) const
	Returns a minimum cut.

HaoOrlin< _Graph, _CapacityMap, _Tolerance > Class Template Reference [Minimum Cut algorithms]

Detailed Description

template<typename _Graph, typename _CapacityMap, typename _Tolerance> class lemon::HaoOrlin< _Graph, _CapacityMap, _Tolerance >

Public Member Functions

Constructor & Destructor Documentation

Member Function Documentation

HaoOrlin< _Graph, _CapacityMap, _Tolerance > Class Template Reference
[Minimum Cut algorithms]

template<typename _Graph, typename _CapacityMap, typename _Tolerance>
class lemon::HaoOrlin< _Graph, _CapacityMap, _Tolerance >