KarpMmc< GR, CM, TR > Class Template Reference

Detailed Description

template<typename GR, typename CM, typename TR>
class lemon::KarpMmc< GR, CM, TR >

This class implements Karp's algorithm for finding a directed cycle of minimum mean cost in a digraph [karp78characterization], [dasdan98minmeancycle]. It runs in time O(nm) and uses space O(n²+m).

Template Parameters

GR	The type of the digraph the algorithm runs on.
CM	The type of the cost map. The default map type is GR::ArcMap<int>.
TR	The traits class that defines various types used by the algorithm. By default, it is KarpMmcDefaultTraits<GR, CM>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.

#include <lemon/karp_mmc.h>

Classes
struct	SetLargeCost
	Named parameter for setting LargeCost type. More...
struct	SetPath
	Named parameter for setting Path type. More...

Public Types
typedef TR::Digraph	Digraph
	The type of the digraph.
typedef TR::CostMap	CostMap
	The type of the cost map.
typedef TR::Cost	Cost
	The type of the arc costs.
typedef TR::LargeCost	LargeCost
	The large cost type.
typedef TR::Tolerance	Tolerance
	The tolerance type.
typedef TR::Path	Path
	The path type of the found cycles.
typedef TR	Traits
	The traits class of the algorithm.

Public Member Functions
	KarpMmc (const Digraph &digraph, const CostMap &cost)
	Constructor.
	~KarpMmc ()
	Destructor.
KarpMmc &	cycle (Path &path)
	Set the path structure for storing the found cycle.
KarpMmc &	tolerance (const Tolerance &tolerance)
	Set the tolerance used by the algorithm.
const Tolerance &	tolerance () const
	Return a const reference to the tolerance.
Execution control
The simplest way to execute the algorithm is to call the run() function. If you only need the minimum mean cost, you may call findCycleMean().
bool	run ()
	Run the algorithm.
bool	findCycleMean ()
	Find the minimum cycle mean.
bool	findCycle ()
	Find a minimum mean directed cycle.
Query Functions
The results of the algorithm can be obtained using these functions. The algorithm should be executed before using them.
Cost	cycleCost () const
	Return the total cost of the found cycle.
int	cycleSize () const
	Return the number of arcs on the found cycle.
double	cycleMean () const
	Return the mean cost of the found cycle.
const Path &	cycle () const
	Return the found cycle.

Member Typedef Documentation

LargeCost

template<typename GR , typename CM , typename TR >

typedef TR::LargeCost LargeCost

The large cost type used for internal computations. By default, it is long long if the Cost type is integer, otherwise it is double.

Path

template<typename GR , typename CM , typename TR >

typedef TR::Path Path

The path type of the found cycles. Using the default traits class, it is Path<Digraph>.

Constructor & Destructor Documentation

KarpMmc()

template<typename GR , typename CM , typename TR >

KarpMmc ( const Digraph &  digraph, const CostMap &  cost  )

inline

The constructor of the class.

Parameters

digraph	The digraph the algorithm runs on.
cost	The costs of the arcs.

Member Function Documentation

cycle() [1/2]

template<typename GR , typename CM , typename TR >

KarpMmc & cycle ( Path &  path )

inline

This function sets an external path structure for storing the found cycle.

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

Note

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

Returns

(*this)

tolerance() [1/2]

template<typename GR , typename CM , typename TR >

KarpMmc & tolerance ( const Tolerance &  tolerance )

inline

This function sets the tolerance object used by the algorithm.

Returns

(*this)

tolerance() [2/2]

template<typename GR , typename CM , typename TR >

const Tolerance & tolerance ( ) const

inline

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

run()

template<typename GR , typename CM , typename TR >

bool run ( )

inline

This function runs the algorithm. It can be called more than once (e.g. if the underlying digraph and/or the arc costs have been modified).

Returns

true if a directed cycle exists in the digraph.

Note

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

return mmc.findCycleMean() && mmc.findCycle();

findCycleMean()

template<typename GR , typename CM , typename TR >

bool findCycleMean ( )

inline

This function finds the minimum mean cost of the directed cycles in the digraph.

Returns

true if a directed cycle exists in the digraph.

findCycle()

template<typename GR , typename CM , typename TR >

bool findCycle ( )

inline

This function finds a directed cycle of minimum mean cost in the digraph using the data computed by findCycleMean().

Returns

true if a directed cycle exists in the digraph.

Precondition

findCycleMean() must be called before using this function.

cycleCost()

template<typename GR , typename CM , typename TR >

Cost cycleCost ( ) const

inline

This function returns the total cost of the found cycle.

Precondition

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

cycleSize()

template<typename GR , typename CM , typename TR >

int cycleSize ( ) const

inline

This function returns the number of arcs on the found cycle.

Precondition

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

cycleMean()

template<typename GR , typename CM , typename TR >

double cycleMean ( ) const

inline

This function returns the mean cost of the found cycle.

Note

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

return static_cast<double>(alg.cycleCost()) / alg.cycleSize();

Precondition

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

cycle() [2/2]

template<typename GR , typename CM , typename TR >

const Path & cycle ( ) const

inline

This function returns a const reference to the path structure storing the found cycle.

Precondition

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