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 [hartmann93finding], [dasdan98minmeancycle]. 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
-
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 HartmannOrlinMmcDefaultTraits<GR, CM>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead. |
|
| HartmannOrlinMmc (const Digraph &digraph, const CostMap &cost) |
| Constructor.
|
|
| ~HartmannOrlinMmc () |
| Destructor.
|
|
HartmannOrlinMmc & | cycle (Path &path) |
| Set the path structure for storing the found cycle.
|
|
HartmannOrlinMmc & | tolerance (const Tolerance &tolerance) |
| Set the tolerance used by the algorithm.
|
|
const Tolerance & | tolerance () const |
| Return a const reference to the tolerance.
|
|
|
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.
|
|
|
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.
|
|
template<typename GR , typename CM , typename TR >
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)