HaoOrlin< GR, CAP, TOL > Class Template Reference

---

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. The purpose of such algorithm is e.g. 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>

List of all members.

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.
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	(	const Digraph &	graph,
		const CapacityMap &	capacity,
		const Tolerance &	tolerance = Tolerance()
	)		[inline]

Constructor of the algorithm class.

---

Member Function Documentation

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.

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.

void calculateOut

(

)

[inline]

This function calculates a minimum cut with on the source-side (i.e. a set with and minimal outgoing capacity).

Precondition:

init() must be called before using this function.

void calculateIn

(

)

[inline]

This function calculates a minimum cut with on the sink-side (i.e. a set with and minimal outgoing capacity).

Precondition:

init() must be called before using this function.

void run

(

)

[inline]

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

void run

(

const Node &

s

)

[inline]

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

Value minCutValue

(

)

const [inline]

This function returns the value of the minimum cut.

Precondition:

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

Value minCutMap

(

CutMap &

cutMap

)

const [inline]

This function sets cutMap to the characteristic vector of a minimum value cut: it will give a non-empty set with minimal 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.