This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

[maximum|minimum]_cycle_ratio

Calculates the maximum or minimum cycle ratio of a weighted directed multigraph using Howard’s iteration policy algorithm.

Complexity: Empirical O(|E|); space O(7|V|) plus graph storage
Defined in: <boost/graph/howard_cycle_ratio.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/howard_cycle_ratio.hpp>
#include <iostream>
#include <vector>

// Two bundled edge fields replace the nested
// `property<edge_weight_t, double, property<edge_weight2_t, double>>`.
struct Edge { double weight, transit; };

using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS, no_property, Edge>;

int main() {
    Graph g(3);
    // Cycle: 0->1->2->0 with weights 3,1,2 and transit times 1,1,1
    add_edge(0, 1, Edge{3.0, 1.0}, g);
    add_edge(1, 2, Edge{1.0, 1.0}, g);
    add_edge(2, 0, Edge{2.0, 1.0}, g);
    add_edge(0, 2, Edge{10.0, 1.0}, g);

    std::vector<graph_traits<Graph>::edge_descriptor> cycle;
    double mcr = minimum_cycle_ratio(g,
        get(vertex_index, g),
        get(&Edge::weight, g),
        get(&Edge::transit, g), &cycle);

    std::cout << "Minimum cycle ratio: " << mcr << "\n";
    std::cout << "Cycle length: " << cycle.size() << " edges\n";
}
Minimum cycle ratio: 2
Cycle length: 3 edges

(1) maximum_cycle_ratio (default FloatTraits)

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

IN

const Graph& g

A weighted directed multigraph. The graph type must be a model of Vertex List Graph and Incidence Graph.

IN

VertexIndexMap vim

Maps each vertex of the graph to a unique integer in the range [0, num_vertices(g)). Must be a model of Readable Property Map.

IN

EdgeWeight1 ewm

The W1 edge weight function. Must be a model of Readable Property Map.

IN

EdgeWeight2 ew2m

The W2 edge weight function. Should be nonnegative. The actual limitation of the algorithm is the positivity of the total weight of each directed cycle of the graph. Must be a model of Readable Property Map.

OUT

std::vector<typename boost::graph_traits<Graph>::edge_descriptor>* pcc

If non-zero then one critical cycle will be stored in the std::vector. Default: 0

(2) maximum_cycle_ratio (custom FloatTraits)

template <typename FloatTraits, typename 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());
Direction Parameter Description

IN

FloatTraits

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:

[source,cpp] ~~ 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 type must be a model of Vertex List Graph and Incidence Graph.

IN

VertexIndexMap vim

Maps each vertex of the graph to a unique integer in the range [0, num_vertices(g)). Must be a model of Readable Property Map.

IN

EdgeWeight1 ewm

The W1 edge weight function. Must be a model of Readable Property Map.

IN

EdgeWeight2 ew2m

The W2 edge weight function. Should be nonnegative. The actual limitation of the algorithm is the positivity of the total weight of each directed cycle of the graph. Must be a model of Readable Property Map.

OUT

std::vector<typename boost::graph_traits<Graph>::edge_descriptor>* pcc

If non-zero then one critical cycle will be stored in the std::vector. Default: 0

(3) minimum_cycle_ratio (default FloatTraits)

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

Same parameters as (1).

(4) minimum_cycle_ratio (custom FloatTraits)

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());

Same parameters as (2).

(5) maximum_cycle_mean (default FloatTraits)

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);
Direction Parameter Description

IN

const Graph& g

A weighted directed multigraph. The graph type must be a model of Vertex List Graph and Incidence Graph.

IN

VertexIndexMap vim

Maps each vertex of the graph to a unique integer in the range [0, num_vertices(g)). Must be a model of Readable Property Map.

IN

EdgeWeightMap ewm

The edge weight function. Must be a model of Readable Property Map.

IN

EdgeIndexMap eim

Maps each edge of the graph to a unique integer in the range [0, num_edges(g)). Must be a model of Readable Property Map.

OUT

std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc

If non-zero then one critical cycle will be stored in the std::vector. Default: 0

(6) maximum_cycle_mean (custom FloatTraits)

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());

Same parameters as (5), plus the FloatTraits template parameter described in (2).

(7) minimum_cycle_mean (default 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);

Same parameters as (5).

(8) minimum_cycle_mean (custom FloatTraits)

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());

Same parameters as (5), plus the FloatTraits template parameter described in (2).

Description

The maximum_cycle_ratio() function calculates the maximum cycle ratio of a weighted directed multigraph G=(V,E,W1,W2), where V is a vertex set, E is an edge set, W1 and W2 are edge weight functions, W2 is nonnegative. As a multigraph, G can have multiple edges connecting a pair of vertices.

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

Cycle ratio definition

The maximum (minimum) cycle ratio (mcr) is the maximum (minimum) cycle ratio of all cycles of the graph. A cycle is called critical if its ratio is equal to the mcr. The maximum_cycle_ratio()/minimum_cycle_ratio() returns -FloatTraits::infinity()/FloatTraits::infinity() if graph has no cycles. If the pcc parameter is not zero then one critical cycle will be written to the corresponding std::vector of edge descriptors. The edges in the vector stored in the way such that *pcc[0], *ppc[1], …​, *ppc[n] is a correct path.

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

For convenience, functions maximum_cycle_mean() and minimum_cycle_mean() are also provided. These take an EdgeIndexMap instead of the two separate edge weight maps (EdgeWeight1 and EdgeWeight2).

Returns

The calculated maximum (or minimum) cycle ratio. Returns -FloatTraits::infinity() (for maximum_cycle_ratio) or FloatTraits::infinity() (for minimum_cycle_ratio) if the graph has no cycles.

The program in libs/graph/example/cycle_ratio_example.cpp generates a random graph and computes its maximum cycle ratio.

Edit this Page