GoldbergTarjan< _Graph, _CapacityMap, _Traits > Class Template Reference
[Maximum Flow algorithms]

---

Detailed Description

template<typename _Graph, typename _CapacityMap, typename _Traits>
class lemon::GoldbergTarjan< _Graph, _CapacityMap, _Traits >

This class provides an implementation of the GoldbergTarjan algorithm producing a flow of maximum value in a directed graph. The GoldbergTarjan algorithm is a theoretical improvement of the Goldberg's preflow algorithm by using the dynamic tree data structure of Sleator and Tarjan.

The original preflow algorithm with highest label heuristic has or with FIFO heuristic has time complexity. The current algorithm improved this complexity to . The algorithm builds limited size dynamic trees on the residual graph, which can be used to make multilevel push operations and gives a better bound on the number of non-saturating pushes.

Parameters:

	Graph	The directed graph type the algorithm runs on.
	CapacityMap	The capacity map type.
	_Traits	Traits class to set various data types used by the algorithm. The default traits class is GoldbergTarjanDefaultTraits. See GoldbergTarjanDefaultTraits for the documentation of a Goldberg-Tarjan traits class.

Author:

Tamas Hamori and Balazs Dezso

#include <lemon/goldberg_tarjan.h>

List of all members.

Named template parameters
	GoldbergTarjan ()
	GoldbergTarjan (const Graph &graph, const CapacityMap &capacity, Node source, Node target)
	The constructor of the class.
	~GoldbergTarjan ()
	Destrcutor.
GoldbergTarjan &	capacityMap (const CapacityMap &map)
	Sets the capacity map.
GoldbergTarjan &	flowMap (FlowMap &map)
	Sets the flow map.
const FlowMap &	flowMap ()
	Returns the flow map.
GoldbergTarjan &	elevator (Elevator &elevator)
	Sets the elevator.
const Elevator &	elevator ()
	Returns the elevator.
GoldbergTarjan &	source (const Node &node)
	Sets the source node.
GoldbergTarjan &	target (const Node &node)
	Sets the target node.
GoldbergTarjan &	tolerance (const Tolerance &tolerance) const
const Tolerance &	tolerance () const
void	createStructures ()
void	destroyStructures ()
bool	sendOut (Node n, Value &excess)
bool	sendIn (Node n, Value &excess)
void	cutChildren (Node n)
void	extractTrees ()
Classes
struct	DefElevator
struct	DefFlowMap
struct	DefStandardElevator
	Named parameter for setting Elevator type More...
class	InvalidArgument
	Exception for the case when s=t. More...
Public Member Functions
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 initial solution or execution then you have to call one init() function and then the startFirstPhase() and if you need the startSecondPhase().
void	init ()
void	startFirstPhase ()
	Starts the first phase of the preflow algorithm.
void	startSecondPhase ()
	Starts the second phase of the preflow algorithm.
void	run ()
	Runs the Goldberg-Tarjan algorithm.
void	runMinCut ()
	Runs the Goldberg-Tarjan algorithm to compute the minimum cut.
Query Functions
The result of the Goldberg-Tarjan algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called.
Value	flowValue () const
	Returns the value of the maximum flow.
bool	minCut (const Node &node) const
	Returns true when the node is on the source side of minimum cut.
template<typename CutMap >
void	minCutMap (CutMap &cutMap) const
	Returns a minimum value cut.
Value	flow (const Edge &edge) const
	Returns the flow on the edge.

---

Constructor & Destructor Documentation

GoldbergTarjan	(	const Graph &	graph,
		const CapacityMap &	capacity,
		Node	source,
		Node	target
	)			[inline]

The constructor of the class.

Parameters:

	graph	The directed graph the algorithm runs on.
	capacity	The capacity of the edges.
	source	The source node.
	target	The target node. Except the graph, all of these parameters can be reset by calling source, target, capacityMap and flowMap, resp.

~GoldbergTarjan

(

)

[inline]

Destructor.

---

Member Function Documentation

GoldbergTarjan& capacityMap

(

const CapacityMap &

map

)

[inline]

Sets the capacity map.

Returns:

(*this)

GoldbergTarjan& flowMap

(

FlowMap &

map

)

[inline]

Sets the flow map.

Returns:

(*this)

const FlowMap& flowMap

(

)

[inline]

Returns:

The flow map.

GoldbergTarjan& elevator

(

Elevator &

elevator

)

[inline]

Sets the elevator.

Returns:

(*this)

const Elevator& elevator

(

)

[inline]

Returns:

The elevator.

GoldbergTarjan& source

(

const Node &

node

)

[inline]

Sets the source node.

Returns:

(*this)

GoldbergTarjan& target

(

const Node &

node

)

[inline]

Sets the target node.

Returns:

(*this)

GoldbergTarjan& tolerance

(

const Tolerance &

tolerance

)

const [inline]

Sets the tolerance used by algorithm.

const Tolerance& tolerance

(

)

const [inline]

Returns the tolerance used by algorithm.

void init

(

)

[inline]

Initializes the internal data structures.

void startFirstPhase

(

)

[inline]

The preflow algorithm consists of two phases, this method runs the first phase. After the first phase the maximum flow value and a minimum value cut can already be computed, although a maximum flow is not yet obtained. So after calling this method flowValue() returns the value of a maximum flow and minCut() returns a minimum cut.

Precondition:

One of the init() functions should be called.

void startSecondPhase

(

)

[inline]

The preflow algorithm consists of two phases, this method runs the second phase. After calling init() and startFirstPhase() and then startSecondPhase(), flowMap() return a maximum flow, flowValue() returns the value of a maximum flow, minCut() returns a minimum cut

Precondition:

The init() and startFirstPhase() functions should be called before.

void run

(

)

[inline]

Runs the Goldberg-Tarjan algorithm.

Note:

pf.run() is just a shortcut of the following code.

   pf.init();
   pf.startFirstPhase();
   pf.startSecondPhase();

void runMinCut

(

)

[inline]

Runs the Goldberg-Tarjan algorithm to compute the minimum cut.

Note:

pf.runMinCut() is just a shortcut of the following code.

   pf.init();
   pf.startFirstPhase();

Value flowValue

(

)

const [inline]

Returns the value of the maximum flow by returning the excess of the target node t. This value equals to the value of the maximum flow already after the first phase.

bool minCut

(

const Node &

node

)

const [inline]

Returns true when the node is on the source side of minimum cut. This method can be called both after running startFirstPhase() and startSecondPhase().

void minCutMap

(

CutMap &

cutMap

)

const [inline]

Sets the cutMap to the characteristic vector of a minimum value cut. This method can be called both after running startFirstPhase() and startSecondPhase(). The result after second phase could be changed slightly if inexact computation is used.

Precondition:

The cutMap should be a bool-valued node-map.

Value flow

(

const Edge &

edge

)

const [inline]

Sets the flowMap to the flow on the edges. This method can be called after the second phase of algorithm.