1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> 2<HTML> 3<HEAD> 4<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1"> 5 <TITLE>Boost Graph Library: Maximum (Minimum) cycle ratio</TITLE> 6 <META NAME="CREATED" CONTENT="20061218;17562954"> 7 <META NAME="CHANGEDBY" CONTENT="Dmitry Bufistov"> 8 <META NAME="CHANGED" CONTENT="20070128;20552300"> 9 10 11 <!-- Copyright 2007 Technical University of Catalonia 12 13 Use, modification and distribution is subject to the Boost Software 14 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 15 http://www.boost.org/LICENSE_1_0.txt) 16 17 Authors: Dmitry Bufistov 18 Andrey Parfenov 19 --> 20 <!-- 21 <STYLE> 22 @page { size: 3.5cm 2.5cm } 23 TD P { color: #000000 } 24 H1 { color: #000000 } 25 P { color: #000000 } 26 PRE { color: #000000 } 27 H3 { color: #000000 } 28 BLOCKQUOTE { color: #000000 } 29 A:link { color: #0000ee } 30 A:visited { color: #551a8b } 31 </STYLE> 32 --> 33</HEAD> 34<BODY TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR"> 35<P><IMG SRC="../../..//boost.png" NAME="graphics1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0> 36</P> 37<H1><TT>[maximum|minimum]_cycle_ratio</TT></H1> 38<P> 39<PRE> 40template <typename Graph, typename VertexIndexMap, 41 typename EdgeWeight1, typename EdgeWeight2> 42dobule 43maximum_cycle_ratio(const Graph &g, VertexIndexMap vim, 44 EdgeWeight1 ewm, EdgeWeight2 ew2m, 45 std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0); 46 47template <typename FloatTraits, Graph, typename VertexIndexMap, 48 typename EdgeWeight1, typename EdgeWeight2> 49typename FloatTraits::float_type 50maximum_cycle_ratio(const Graph &g, VertexIndexMap vim, 51 EdgeWeight1 ewm, EdgeWeight2 ew2m, 52 std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0, 53 FloatTraits = FloatTraits()); 54 55template <typename Graph, typename VertexIndexMap, 56 typename EdgeWeight1, typename EdgeWeight2> 57dobule 58minimum_cycle_ratio(const Graph &g, VertexIndexMap vim, 59 EdgeWeight1 ewm, EdgeWeight2 ew2m, 60 std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0); 61 62template <typename FloatTraits, typename <A HREF="http://boost.org/libs/graph/doc/Graph.html">Graph</A>, typename VertexIndexMap, 63 typename EdgeWeight1, typename EdgeWeight2> 64typename FloatTraits::float_type 65minimum_cycle_ratio(const Graph &g, VertexIndexMap vim, 66 EdgeWeight1 ewm, EdgeWeight2 ew2m, 67 std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0, 68 FloatTraits = FloatTraits()); 69</PRE> 70</P> 71 72 73The <tt>maximum_cycle_ratio()</tt> function calculates the maximum cycle ratio of a 74weighted directed multigraph <I>G=(V,E,W1,W2)</I>, where <i>V</i> is a vertex set, 75<i>E</i> is an edge set, W1 and W2 are edge weight functions, W2 is nonnegative. 76As a multigraph, <i>G</i> can have multiple edges connecting a pair of vertices. 77</P> 78 79<P>Let every edge <I>e</I> has two weights <I>W1(e)</I> and <I>W2(e)</I>. 80Let <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> 81<P> 82<IMG SRC="figs/cr.jpg" ALT="Cycle ratio definition" BORDER=0> 83</P> 84 85The <I>maximum (minimum) cycle ratio</I> (mcr) is the maximum (minimum) cycle ratio 86of all cycles of the graph. A cycle is called <I>critical</I> if its ratio is equal 87to the <I>mcr</I>. The calculated maximum cycle ratio will be the return value 88of the function. The <tt>maximum_cycle_ratio()/minimum_cycle_ratio()</tt> returns 89<tt>-FloatTraits::infinity()/FloatTraits::infinity()</tt> if graph has no cycles. 90If the <i>pcc</i> parameter is not zero then one critical cycle will be written 91to the corresponding <tt>std::vector</tt> of edge descriptors. The edges in the 92vector stored in the way such that <tt>*pcc[0], *ppc[1], ..., *ppc[n]</tt> is a 93correct path. 94</P> 95<P> 96The algorithm is due to Howard's iteration policy algorithm, descibed in 97<A HREF="./cochet-terrasson98numerical.pdf">[1]</A>. 98Ali Dasdan, Sandy S. Irani and Rajesh K.Gupta in their paper 99<A HREF="./dasdan-dac99.pdf">Efficient Algorithms for Optimum Cycle Mean and Optimum Cost to Time Ratio 100Problems</A> state that this is the most efficient algorithm to the time being (1999).</P> 101 102<p> 103For the convenience, functions <tt>maximum_cycle_mean()</tt> and <tt>minimum_cycle_mean()</tt> 104are also provided. They have the following signatures: 105<pre> 106template <typename Graph, typename VertexIndexMap, 107 typename EdgeWeightMap, typename EdgeIndexMap> 108double 109maximum_cycle_mean(const Graph &g, VertexIndexMap vim, 110 EdgeWeightMap ewm, EdgeIndexMap eim, 111 std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0); 112template <typename FloatTraits, typename Graph, typename VertexIndexMap, 113 typename EdgeWeightMap, typename EdgeIndexMap> 114 115typename FloatTraits::float_type 116maximum_cycle_mean(const Graph &g, VertexIndexMap vim, 117 EdgeWeightMap ewm, EdgeIndexMap eim, 118 std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0, 119 FloatTraits = FloatTraits()); 120 121template <typename Graph, typename VertexIndexMap, 122 typename EdgeWeightMap, typename EdgeIndexMap> 123double 124minimum_cycle_mean(const Graph &g, VertexIndexMap vim, 125 EdgeWeightMap ewm, EdgeIndexMap eim, 126 std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0); 127template <typename FloatTraits, typename Graph, typename VertexIndexMap, 128 typename EdgeWeightMap, typename EdgeIndexMap> 129 130typename FloatTraits::float_type 131minimum_cycle_mean(const Graph &g, VertexIndexMap vim, 132 EdgeWeightMap ewm, EdgeIndexMap eim, 133 std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0, 134 FloatTraits = FloatTraits()); 135</pre> 136</p> 137 138<H3>Where Defined</H3> 139<P STYLE="background: transparent"><TT><A HREF="../../../boost/graph/howard_cycle_ratio.hpp">boost/graph/howard_cycle_ratio.hpp</A></TT> 140</P> 141<H3>Parameters</H3> 142<P>IN: <tt>FloatTraits</tt> </P> 143<blockquote> 144The <tt>FloatTrats</tt> encapsulates customizable limits-like information for 145floating point types. This type <i>must</i> provide an associated type, 146<tt>value_type</tt> for the floating point type. 147 148The default value is <tt>boost::mcr_float<></tt>which has the following 149definition:<br/> 150<pre> 151 template <typename Float = double> 152 struct mcr_float { 153 typedef Float value_type; 154 155 static Float infinity() 156 { return (std::numeric_limits<value_type>::max)(); } 157 158 static Float epsilon() 159 { return Float(-0.005); } 160 }; 161</pre> 162The value <tt>FloatTraits::epsilon()</tt> controls the "tolerance" of the 163algorithm. By increasing the absolute value of epsilon you may slightly decrease 164the execution time but there is a risk to skip a global optima. By decreasing 165the absolute value you may fall to the infinite loop. The best option is to 166leave this parameter unchanged. 167</blockquote> 168<P>IN: <tt>const Graph& g </tt> 169</P> 170<BLOCKQUOTE>A weighted directed multigraph. 171The graph's type must be a model of <A HREF="http://boost.org/libs/graph/doc/VertexListGraph.html">VertexListGraph</A> 172and <A HREF="http://boost.org/libs/graph/doc/IncidenceGraph.html">IncidenceGraph</A> 173</BLOCKQUOTE> 174<P>IN: <tt>VertexIndexMap vim</tt> 175</P> 176<BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the 177range [0, num_vertices(g)). 178</BLOCKQUOTE> 179<P>IN: <tt>EdgeWeight1 ew1m</t> 180</P> 181<BLOCKQUOTE> 182The W1 edge weight function. 183</BLOCKQUOTE> 184<P>IN: <tt>EdgeWeight2 ew2m</tt> 185</P> 186<BLOCKQUOTE> 187The W2 edge weight function. Should be nonnegative. The actual limitation of the 188algorithm is the positivity of the total weight of each directed cycle of the graph. 189</BLOCKQUOTE> 190<P> 191OUT: <tt>std::vector<typename boost::graph_traits<Graph>::edge_descriptor>* pcc</tt> 192</P> 193<BLOCKQUOTE> 194If non zero then one critical cycle will be stored in the std::vector. Default 195value is 0. 196</BLOCKQUOTE> 197<P> 198IN (only for maximum/minimal_cycle_mean()): <tt>EdgeIndexMap eim</tt> 199</P> 200<BLOCKQUOTE> 201Maps each edge of the graph to a unique integer in the range [0, num_edges(g)). 202</BLOCKQUOTE> 203<BLOCKQUOTE STYLE="margin-left: 0cm"> 204All property maps must be models of <A HREF="http://boost.org/libs/property_map/ReadablePropertyMap.html">Readable 205Property Map</A> 206</BLOCKQUOTE> 207 208<H3>Complexity</H3> 209<P>There is no known precise upper bound for the time complexity of the 210algorithm. Imperical time complexity is <I>O(|E|)</I>, where the constant tends to 211be pretty small (about 20-30). Space complexity is equal to <i>7*|V|</i> plus the 212space required to store a graph. 213</P> 214 215<H3>Example</H3> 216<P>The program in <A HREF="../example/cycle_ratio_example.cpp">libs/graph/example/cycle_ratio_example.cpp</A> 217generates a random graph and computes its maximum cycle ratio. 218</P> 219 220<HR> 221<TABLE CELLPADDING=2 CELLSPACING=2> 222 <TR VALIGN=TOP> 223 <TD> 224 <P>Copyright © 2006-2009</P> 225 </TD> 226 <TD> 227 <P><A HREF="https://web.archive.org/web/20081122083634/http://www.lsi.upc.edu/~dmitry">Dmitry 228 Bufistov</A>, Andrey Parfenov</P> 229 </TD> 230 </TR> 231</TABLE> 232<P><BR><BR> 233</P></HTML> 234
