All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
List of all members | Classes | Public Types | Public Member Functions
HartmannOrlinMmc< GR, CM, TR > Class Template Reference

Detailed Description

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

This class implements the Hartmann-Orlin algorithm for finding a directed cycle of minimum mean cost in a digraph [20], [9]. This method is based on Karp's original algorithm, but applies an early termination scheme. It makes the algorithm significantly faster for some problem instances, but slower for others. The algorithm runs in time O(nm) and uses space O(n2+m).

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

#include <lemon/hartmann_orlin_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

 HartmannOrlinMmc (const Digraph &digraph, const CostMap &cost)
 Constructor.
 
 ~HartmannOrlinMmc ()
 Destructor.
 
HartmannOrlinMmccycle (Path &path)
 Set the path structure for storing the found cycle.
 
HartmannOrlinMmctolerance (const Tolerance &tolerance)
 Set the tolerance used by the algorithm.
 
const Tolerancetolerance () 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 Pathcycle () const
 Return the found cycle.
 

Member Typedef Documentation

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.

typedef TR::Path Path

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

Constructor & Destructor Documentation

HartmannOrlinMmc ( const Digraph digraph,
const CostMap cost 
)
inline

The constructor of the class.

Parameters
digraphThe digraph the algorithm runs on.
costThe costs of the arcs.

Member Function Documentation

HartmannOrlinMmc& 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)
HartmannOrlinMmc& tolerance ( const Tolerance tolerance)
inline

This function sets the tolerance object used by the algorithm.

Returns
(*this)
const Tolerance& tolerance ( ) const
inline

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

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();
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.
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.
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.
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.
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.
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.