This class implements Howard's policy iteration algorithm for finding a directed cycle of minimum mean cost in a digraph [9], [10]. This class provides the most efficient algorithm for the minimum mean cycle problem, though the best known theoretical bound on its running time is exponential.
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 HowardMmcDefaultTraits<GR, CM>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead. |
#include <lemon/howard_mmc.h>
Classes | |
struct | SetLargeCost |
Named parameter for setting LargeCost type. More... | |
struct | SetPath |
Named parameter for setting Path type. More... | |
Public Types | |
enum | TerminationCause { NO_CYCLE = 0, OPTIMAL = 1, ITERATION_LIMIT } |
Constants for the causes of search termination. More... | |
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. More... | |
typedef TR::Tolerance | Tolerance |
The tolerance type. | |
typedef TR::Path | Path |
The path type of the found cycles. More... | |
typedef TR | Traits |
The traits class of the algorithm. | |
Public Member Functions | |
HowardMmc (const Digraph &digraph, const CostMap &cost) | |
Constructor. More... | |
~HowardMmc () | |
Destructor. | |
HowardMmc & | cycle (Path &path) |
Set the path structure for storing the found cycle. More... | |
HowardMmc & | tolerance (const Tolerance &tolerance) |
Set the tolerance used by the algorithm. More... | |
const Tolerance & | tolerance () const |
Return a const reference to the tolerance. More... | |
Execution control | |
The simplest way to execute the algorithm is to call the run() function. | |
bool | run () |
Run the algorithm. More... | |
TerminationCause | findCycleMean (int limit=std::numeric_limits< int >::max()) |
Find the minimum cycle mean (or an upper bound). More... | |
bool | findCycle () |
Find a minimum mean directed cycle. More... | |
Query Functions | |
The results of the algorithm can be obtained using these functions. | |
Cost | cycleCost () const |
Return the total cost of the found cycle. More... | |
int | cycleSize () const |
Return the number of arcs on the found cycle. More... | |
double | cycleMean () const |
Return the mean cost of the found cycle. More... | |
const Path & | cycle () const |
Return the found cycle. More... | |
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>.
enum TerminationCause |
Enum type containing constants for the different causes of search termination. The findCycleMean() function returns one of these values.
Enumerator | |
---|---|
NO_CYCLE |
No directed cycle can be found in the digraph. |
OPTIMAL |
Optimal solution (minimum cycle mean) is found. |
ITERATION_LIMIT |
The iteration count limit is reached. |
The constructor of the class.
digraph | The digraph the algorithm runs on. |
cost | The costs of the arcs. |
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.
(*this)
This function sets the tolerance object used by the algorithm.
(*this)
|
inline |
This function returns a const reference to the tolerance object used by the algorithm.
|
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).
true
if a directed cycle exists in the digraph.mmc.run()
is just a shortcut of the following code.
|
inline |
This function finds the minimum mean cost of the directed cycles in the digraph (or an upper bound for it).
By default, the function finds the exact minimum cycle mean, but an optional limit can also be specified for the number of iterations performed during the search process. The return value indicates if the optimal solution is found or the iteration limit is reached. In the latter case, an approximate solution is provided, which corresponds to a directed cycle whose mean cost is relatively small, but not necessarily minimal.
limit | The maximum allowed number of iterations during the search process. Its default value implies that the algorithm runs until it finds the exact optimal solution. |
|
inline |
This function finds a directed cycle of minimum mean cost in the digraph using the data computed by findCycleMean().
true
if a directed cycle exists in the digraph.
|
inline |
This function returns the total cost of the found cycle.
|
inline |
This function returns the number of arcs on the found cycle.
|
inline |
This function returns the mean cost of the found cycle.
alg.cycleMean()
is just a shortcut of the following code.
|
inline |
This function returns a const reference to the path structure storing the found cycle.