<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML> <HEAD> <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1"> <TITLE>Boost Graph Library: Maximum (Minimum) cycle ratio</TITLE> <META NAME="CREATED" CONTENT="20061218;17562954"> <META NAME="CHANGEDBY" CONTENT="Dmitry Bufistov"> <META NAME="CHANGED" CONTENT="20070128;20552300"> <!-- Copyright 2007 Technical University of Catalonia Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) Authors: Dmitry Bufistov Andrey Parfenov --> <!-- <STYLE> @page { size: 3.5cm 2.5cm } TD P { color: #000000 } H1 { color: #000000 } P { color: #000000 } PRE { color: #000000 } H3 { color: #000000 } BLOCKQUOTE { color: #000000 } A:link { color: #0000ee } A:visited { color: #551a8b } </STYLE> --> </HEAD> <BODY TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR"> <P><IMG SRC="../../..//boost.png" NAME="graphics1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0> </P> <H1><TT>[maximum|minimum]_cycle_ratio</TT></H1> <P> <PRE> 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 <A HREF="http://boost.org/libs/graph/doc/Graph.html">Graph</A>, 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()); </PRE> </P> The <tt>maximum_cycle_ratio()</tt> function calculates the maximum cycle ratio of a weighted directed multigraph <I>G=(V,E,W1,W2)</I>, where <i>V</i> is a vertex set, <i>E</i> is an edge set, W1 and W2 are edge weight functions, W2 is nonnegative. As a multigraph, <i>G</i> can have multiple edges connecting a pair of vertices. </P> <P>Let every edge <I>e</I> has two weights <I>W1(e)</I> and <I>W2(e)</I>. Let <I>c</I> be a cycle of the graph<I>g</I>. Then, the <i>cycle ratio</i>, <I>cr(c)</I>, is defined as:</P> <P> <IMG SRC="figs/cr.jpg" ALT="Cycle ratio definition" BORDER=0> </P> The <I>maximum (minimum) cycle ratio</I> (mcr) is the maximum (minimum) cycle ratio of all cycles of the graph. A cycle is called <I>critical</I> if its ratio is equal to the <I>mcr</I>. The calculated maximum cycle ratio will be the return value of the function. The <tt>maximum_cycle_ratio()/minimum_cycle_ratio()</tt> returns <tt>-FloatTraits::infinity()/FloatTraits::infinity()</tt> if graph has no cycles. If the <i>pcc</i> parameter is not zero then one critical cycle will be written to the corresponding <tt>std::vector</tt> of edge descriptors. The edges in the vector stored in the way such that <tt>*pcc[0], *ppc[1], ..., *ppc[n]</tt> is a correct path. </P> <P> The algorithm is due to Howard's iteration policy algorithm, descibed in <A HREF="./cochet-terrasson98numerical.pdf">[1]</A>. Ali Dasdan, Sandy S. Irani and Rajesh K.Gupta in their paper <A HREF="./dasdan-dac99.pdf">Efficient Algorithms for Optimum Cycle Mean and Optimum Cost to Time Ratio Problems</A>state that this is the most efficient algorithm to the time being (1999).</P> <p> For the convenience, functions <tt>maximum_cycle_mean()</tt> and <tt>minimum_cycle_mean()</tt> are also provided. They have the following signatures: <pre> 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()); </pre> </p> <H3>Where Defined</H3> <P STYLE="background: transparent"><TT><A HREF="../../../boost/graph/howard_cycle_ratio.hpp">boost/graph/howard_cycle_ratio.hpp</A></TT> </P> <H3>Parameters</H3> <P>IN: <tt>FloatTraits</tt> </P> <blockquote> The <tt>FloatTrats</tt> encapsulates customizable limits-like information for floating point types. This type <i>must</i> provide an associated type, <tt>value_type</tt> for the floating point type. The default value is <tt>boost::mcr_float<></tt>which has the following definition:<br/> <pre> 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); } }; </pre> The value <tt>FloatTraits::epsilon()</tt> 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. </blockquote> <P>IN: <tt>const Graph& g </tt> </P> <BLOCKQUOTE>A weighted directed multigraph. The graph's type must be a model of <A HREF="http://boost.org/libs/graph/doc/VertexListGraph.html">VertexListGraph</A> and <A HREF="http://boost.org/libs/graph/doc/IncidenceGraph.html">IncidenceGraph</A> </BLOCKQUOTE> <P>IN: <tt>VertexIndexMap vim</tt> </P> <BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the range [0, num_vertices(g)). </BLOCKQUOTE> <P>IN: <tt>EdgeWeight1 ew1m</t> </P> <BLOCKQUOTE> The W1 edge weight function. </BLOCKQUOTE> <P>IN: <tt>EdgeWeight2 ew2m</tt> </P> <BLOCKQUOTE> 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. </BLOCKQUOTE> <P> OUT: <tt>std::vector<typename boost::graph_traits<Graph>::edge_descriptor>* pcc</tt> </P> <BLOCKQUOTE> If non zero then one critical cycle will be stored in the std::vector. Default value is 0. </BLOCKQUOTE> <P> IN (only for maximum/minimal_cycle_mean()): <tt>EdgeIndexMap eim</tt> </P> <BLOCKQUOTE> Maps each edge of the graph to a unique integer in the range [0, num_edges(g)). </BLOCKQUOTE> <BLOCKQUOTE STYLE="margin-left: 0cm"> All property maps must be models of <A HREF="http://boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</A> </BLOCKQUOTE> <H3>Complexity</H3> <P>There is no known precise upper bound for the time complexity of the algorithm. Imperical time complexity is <I>O(|E|)</I>, where the constant tends to be pretty small (about 20-30). Space complexity is equal to <i>7*|V|</i> plus the space required to store a graph. </P> <H3>Example</H3> <P>The program in <A HREF="../example/cycle_ratio_example.cpp">libs/graph/example/cycle_ratio_example.cpp</A> generates a random graph and computes its maximum cycle ratio. </P> <HR> <TABLE CELLPADDING=2 CELLSPACING=2> <TR VALIGN=TOP> <TD> <P>Copyright © 2006-2009</P> </TD> <TD> <P><A HREF="http://www.lsi.upc.edu/~dmitry">Dmitry Bufistov</A>, Andrey Parfenov</P> </TD> </TR> </TABLE> <P><BR><BR> </P></HTML>