HowardMmc

Declared in lemon/howard_mmc.h, in the group Minimum Mean Cycle Algorithms; the same class on the Doxygen site.

template< typename GR , typename CM , typename TR >
class HowardMmc

Implementation of Howard’s algorithm for finding a minimum mean cycle.

This class implements Howard’s policy iteration algorithm for finding a directed cycle of minimum mean cost in a digraph [10], [11]. 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.

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 HowardMmcDefaultTraits< 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:

true if a directed cycle exists in the digraph.

inline TerminationCause findCycleMean( int limit = (std::numeric_limits< int >::max)() )

Find the minimum cycle mean (or an upper bound).

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.

Parameters:

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.

Returns:

The termination cause of the search process. For more information, see TerminationCause.

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:

true if 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 a LargeCost, by cycleSize(); hence it is the same as static_cast< double >( alg.cycleCost() ) / alg.cycleSize() only when that cost fits in Cost, 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.

inline int componentCycleNum() const

Return the number of the cycles of the components.

Howard’s policy iteration runs on each strongly connected component of the digraph in turn, and ends there with a policy whose cycle is one of minimum mean cost of the component (Dasdan, 2004): this function returns the number of the components that have a cycle, whose cycles, one for each, are pairwise node-disjoint [see componentCycle()]. They are those of minimum mean in their components only if findCycleMean() was not stopped by its limit on the iterations.

Pre:

run() or findCycleMean() must be called before using this function.

inline Cost componentCycleCost( int i ) const

Return the total cost of the cycle of the i-th component.

Pre:

run() or findCycleMean() must be called before using this function [see componentCycleNum()].

inline int componentCycleSize( int i ) const

Return the number of arcs on the cycle of the i-th component.

Pre:

run() or findCycleMean() must be called before using this function [see componentCycleNum()].

template< typename P >
inline void componentCycle( int i , P & path ) const

Append the cycle of the i-th component to a path.

Pre:

run() or findCycleMean() must be called before using this function [see componentCycleNum()].

Public Types

enum TerminationCause

Constants for the causes of search termination.

Enum type containing constants for the different causes of search termination. The findCycleMean() function returns one of these values.

Values:

enumerator NO_CYCLE

No directed cycle can be found in the digraph.

enumerator OPTIMAL

Optimal solution (minimum cycle mean) is found.

enumerator ITERATION_LIMIT

The iteration count limit is reached.

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.

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::Tolerance Tolerance

The tolerance type.

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 HowardMmc( 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 ~HowardMmc()

Destructor.

inline HowardMmc & 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 addBack() function of the given path structure.

Returns:

(*this)

inline HowardMmc & tolerance( const Tolerance & tolerance )

Set the tolerance used by the algorithm.

This function sets the tolerance object used by the algorithm.

Returns:

(*this)

inline const Tolerance & tolerance() const

Return a const reference to the tolerance.

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

Protected Functions

inline HowardMmc()
template< typename T >
struct SetLargeCostTraits : public Traits

Public Types

typedef T LargeCost
typedef lemon::Tolerance< T > Tolerance
template< typename T >
struct SetLargeCost : public HowardMmc< GR , CM , SetLargeCostTraits< T > >

Named parameter for setting LargeCost type. It is used for internal computations in the algorithm.

Public Types

typedef HowardMmc< GR , CM , SetLargeCostTraits< T > > Create
template< typename T >
struct SetPathTraits : public Traits

Public Types

typedef T Path
template< typename T >
struct SetPath : public HowardMmc< GR , CM , SetPathTraits< T > >

Named parameter for setting Path type.

Named parameter for setting the Path type of the found cycles. It must conform to the Path concept and it must have an addBack() function.

Public Types

typedef HowardMmc< GR , CM , SetPathTraits< T > > Create