MinMeanCycle< Graph, LengthMap > Class Template Reference
[Shortest Path algorithms]

---

Detailed Description

template<typename Graph, typename LengthMap = typename Graph::template EdgeMap<int>>
class lemon::MinMeanCycle< Graph, LengthMap >

MinMeanCycle implements Howard's algorithm for finding a minimum mean directed cycle.

Template Parameters:

	Graph	The directed graph type the algorithm runs on.
	LengthMap	The type of the length (cost) map.

Warning:

LengthMap::Value must be convertible to double.

Author:

Peter Kovacs

#include <lemon/min_mean_cycle.h>

List of all members.

Public Member Functions
	MinMeanCycle (const Graph &graph, const LengthMap &length)
	The constructor of the class.
	~MinMeanCycle ()
	The destructor of the class.
MinMeanCycle &	cyclePath (Path &path)
	Sets the path structure for storing the found cycle.
Execution control
The simplest way to execute the algorithm is to call the run() function. If you only need the minimum mean value, you may call init() and findMinMean(). If you would like to run the algorithm again (e.g. the underlaying graph and/or the edge costs were modified), you may not create a new instance of the class, rather call reset(), findMinMean(), and findCycle() instead.
bool	run ()
	Runs the algorithm.
void	init ()
	Initializes the internal data structures.
void	reset ()
	Resets the internal data structures.
bool	findMinMean ()
	Finds the minimum cycle mean length in the graph.
bool	findCycle ()
	Finds a critical (minimum mean) directed cycle.
Query Functions
The result of the algorithm can be obtained using these functions. The algorithm should be executed before using them.
Length	cycleLength () const
	Returns the total length of the found cycle.
int	cycleEdgeNum () const
	Returns the number of edges on the found cycle.
double	cycleMean () const
	Returns the mean length of the found cycle.
const Path &	cycle () const
	Returns a const reference to the path structure storing the found cycle.

---

Constructor & Destructor Documentation

MinMeanCycle	(	const Graph &	graph,
		const LengthMap &	length
	)			[inline]

The constructor of the class.

Parameters:

	graph	The directed graph the algorithm runs on.
	length	The length (cost) of the edges.

---

Member Function Documentation

MinMeanCycle& cyclePath

(

Path &

path

)

[inline]

Sets an external path structure for storing the found cycle.

If you don't call this function before calling run() or init(), it will allocate a local path structure. The destuctor deallocates this automatically allocated map, of course.

Note:

The algorithm calls only the addBack() function of the given path structure.

Returns:

(*this)

See also:

cycle()

bool run

(

)

[inline]

Runs the algorithm.

Returns:

Returns true if a directed cycle exists in the graph.

Note:

Apart from the return value, mmc.run() is just a shortcut of the following code.

   mmc.init();
   mmc.findMinMean();
   mmc.findCycle();

void init

(

)

[inline]

Initializes the internal data structures.

See also:

reset()

void reset

(

)

[inline]

Resets the internal data structures so that findMinMean() and findCycle() can be called again (e.g. when the underlaying graph has been modified).

See also:

init()

bool findMinMean

(

)

[inline]

Computes all the required data and finds the minimum cycle mean length in the graph.

Returns:

Returns true if a directed cycle exists in the graph.

Precondition:

init() must be called before using this function.

bool findCycle

(

)

[inline]

Finds a critical (minimum mean) directed cycle using the data computed in the findMinMean() function.

Returns:

Returns true if a directed cycle exists in the graph.

Precondition:

init() and findMinMean() must be called before using this function.

Length cycleLength

(

)

const [inline]

Returns the total length of the found cycle.

Precondition:

run() or findMinMean() must be called before using this function.

int cycleEdgeNum

(

)

const [inline]

Returns the number of edges on the found cycle.

Precondition:

run() or findMinMean() must be called before using this function.

double cycleMean

(

)

const [inline]

Returns the mean length of the found cycle.

Precondition:

run() or findMinMean() must be called before using this function.

Note:

mmc.cycleMean() is just a shortcut of the following code.

   return double(mmc.cycleLength()) / mmc.cycleEdgeNum();

const Path& cycle

(

)

const [inline]

Returns a const reference to the path structure storing the found cycle.

Precondition:

run() or findCycle() must be called before using this function.

See also:

cyclePath()