[maximum|minimum]_cycle_ratio

template <typename Graph, typename VertexIndexMap,
          typename EdgeWeight1, typename EdgeWeight2>
dobule
maximum_cycle_ratio(const Graph &g, VertexIndexMap vim,
                    EdgeWeight1 ewm, EdgeWeight2 ew2m,
                    std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0);

template <typename FloatTraits, Graph, typename VertexIndexMap,
          typename EdgeWeight1, typename EdgeWeight2>
typename FloatTraits::float_type
maximum_cycle_ratio(const Graph &g, VertexIndexMap vim,
                    EdgeWeight1 ewm, EdgeWeight2 ew2m,
                    std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0,
                    FloatTraits = FloatTraits());

template <typename Graph, typename VertexIndexMap,
          typename EdgeWeight1, typename EdgeWeight2>
dobule
minimum_cycle_ratio(const Graph &g, VertexIndexMap vim,
                    EdgeWeight1 ewm, EdgeWeight2 ew2m,
                    std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0);

template <typename FloatTraits, typename Graph, typename VertexIndexMap,
          typename EdgeWeight1, typename EdgeWeight2>
typename FloatTraits::float_type
minimum_cycle_ratio(const Graph &g, VertexIndexMap vim,
                    EdgeWeight1 ewm, EdgeWeight2 ew2m,
                    std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0,
                    FloatTraits = FloatTraits());

Let every edge e has two weights W1(e) and W2(e). Let c be a cycle of the graphg. Then, the cycle ratio, cr(c), is defined as:

The algorithm is due to Howard's iteration policy algorithm, descibed in [1]. Ali Dasdan, Sandy S. Irani and Rajesh K.Gupta in their paper Efficient Algorithms for Optimum Cycle Mean and Optimum Cost to Time Ratio Problemsstate that this is the most efficient algorithm to the time being (1999).

For the convenience, functions maximum_cycle_mean() and minimum_cycle_mean() are also provided. They have the following signatures:

template <typename Graph, typename VertexIndexMap,
          typename EdgeWeightMap, typename EdgeIndexMap>
double
maximum_cycle_mean(const Graph &g, VertexIndexMap vim,
                   EdgeWeightMap ewm, EdgeIndexMap eim,
                   std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0);
template <typename FloatTraits, typename Graph, typename VertexIndexMap,
          typename EdgeWeightMap, typename EdgeIndexMap>

typename FloatTraits::float_type
maximum_cycle_mean(const Graph &g, VertexIndexMap vim,
                   EdgeWeightMap ewm, EdgeIndexMap eim,
                   std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0,
                   FloatTraits = FloatTraits());

template <typename Graph, typename VertexIndexMap,
          typename EdgeWeightMap, typename EdgeIndexMap>
double
minimum_cycle_mean(const Graph &g, VertexIndexMap vim,
                   EdgeWeightMap ewm, EdgeIndexMap eim,
                   std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0);
template <typename FloatTraits, typename Graph, typename VertexIndexMap,
          typename EdgeWeightMap, typename EdgeIndexMap>

typename FloatTraits::float_type
minimum_cycle_mean(const Graph &g, VertexIndexMap vim,
                   EdgeWeightMap ewm, EdgeIndexMap eim,
                   std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0,
                   FloatTraits = FloatTraits());

Where Defined

boost/graph/howard_cycle_ratio.hpp

Parameters

IN: FloatTraits

The FloatTrats encapsulates customizable limits-like information for floating point types. This type must provide an associated type, value_type for the floating point type. The default value is boost::mcr_float<>which has the following definition:

 template <typename Float = double>
 struct mcr_float {
    typedef Float value_type;

    static Float infinity()
    { return (std::numeric_limits<value_type>::max)(); }

    static Float epsilon()
    { return Float(-0.005); }
  };

The value FloatTraits::epsilon() controls the "tolerance" of the algorithm. By increasing the absolute value of epsilon you may slightly decrease the execution time but there is a risk to skip a global optima. By decreasing the absolute value you may fall to the infinite loop. The best option is to leave this parameter unchanged.

IN: const Graph& g

A weighted directed multigraph. The graph's type must be a model of VertexListGraph and IncidenceGraph

IN: VertexIndexMap vim

Maps each vertex of the graph to a unique integer in the range [0, num_vertices(g)).

IN: EdgeWeight1 ew1m