KarpMmc
Declared in lemon/karp_mmc.h, in the group Minimum Mean Cycle Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename CM , typename TR >
class KarpMmc Implementation of Karp’s algorithm for finding a minimum mean cycle.
This class implements Karp’s algorithm for finding a directed cycle of minimum mean cost in a digraph [25], [10]. 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.
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().-
inline bool run()
Run the algorithm.
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).
Note
mmc.run()is just a shortcut of the following code.return( mmc.findCycleMean() && mmc.findCycle() );
- Returns:
trueif a directed cycle exists in the digraph.
-
inline bool findCycleMean()
Find the minimum cycle mean.
This function finds the minimum mean cost of the directed cycles in the digraph.
- Returns:
trueif a directed cycle exists in the digraph.
-
inline bool findCycle()
Find a minimum mean directed cycle.
This function finds a directed cycle of minimum mean cost in the digraph using the data computed by findCycleMean().
- Returns:
trueif a directed cycle exists in the digraph.- Pre:
findCycleMean() must be called before using this function.
Query Functions
The results of the algorithm can be obtained using these functions.
The algorithm should be executed before using them.
-
inline Cost cycleCost() const
Return the total cost of the found cycle.
This function returns the total cost of the found cycle.
- Pre:
run() or findCycleMean() must be called before using this function.
-
inline int cycleSize() const
Return the number of arcs on the found cycle.
This function returns the number of arcs on the found cycle.
- Pre:
run() or findCycleMean() must be called before using this function.
-
inline double cycleMean() const
Return the mean cost of the found cycle.
This function returns the mean cost of the found cycle.
Note
alg.cycleMean()divides the cost of the cycle, kept as aLargeCost, by cycleSize(); hence it is the same asstatic_cast< double >( alg.cycleCost() ) / alg.cycleSize()only when that cost fits inCost, to which cycleCost() converts it.- Pre:
run() or findCycleMean() must be called before using this function.
-
inline const Path & cycle() const
Return the found cycle.
This function returns a const reference to the path structure storing the found cycle.
- Pre:
run() or findCycle() must be called before using this function.
Public Types
-
typedef TR::LargeCost LargeCost
The large cost type.
The large cost type used for internal computations. By default, it is
longlongif theCosttype is integer, otherwise it isdouble.
-
typedef TR::Path Path
The path type of the found cycles. Using the default traits class, it is Path< Digraph >.
-
typedef TR Traits
The traits class of the algorithm.
Public Functions
-
inline KarpMmc( const Digraph & digraph , const CostMap & cost )
Constructor.
The constructor of the class.
- Parameters:
digraph – The digraph the algorithm runs on.
cost – The costs of the arcs.
-
inline ~KarpMmc()
Destructor.
-
inline KarpMmc & cycle( Path & path )
Set the path structure for storing the found cycle.
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)
Protected Functions
-
inline KarpMmc()