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(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 KarpMmcDefaultTraits<GR, CM>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead. |
|
| 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.
|
|
|
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)