ceph/src/boost/libs/graph/doc/howard_cycle_ratio.html

   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>
  40 template &lt;typename Graph, typename VertexIndexMap,
  41           typename EdgeWeight1, typename EdgeWeight2&gt;
  42 dobule
  43 maximum_cycle_ratio(const Graph &amp;g, VertexIndexMap vim,
  44                     EdgeWeight1 ewm, EdgeWeight2 ew2m,
  45                     std::vector&lt;typename boost::graph_traits&lt;Graph&gt;::edge_descriptor&gt; *pcc = 0);
  46
  47 template &lt;typename FloatTraits, Graph, typename VertexIndexMap,
  48           typename EdgeWeight1, typename EdgeWeight2&gt;
  49 typename FloatTraits::float_type
  50 maximum_cycle_ratio(const Graph &amp;g, VertexIndexMap vim,
  51                     EdgeWeight1 ewm, EdgeWeight2 ew2m,
  52                     std::vector&lt;typename boost::graph_traits&lt;Graph&gt;::edge_descriptor&gt; *pcc = 0,
  53                     FloatTraits = FloatTraits());
  54
  55 template &lt;typename Graph, typename VertexIndexMap,
  56           typename EdgeWeight1, typename EdgeWeight2&gt;
  57 dobule
  58 minimum_cycle_ratio(const Graph &amp;g, VertexIndexMap vim,
  59                     EdgeWeight1 ewm, EdgeWeight2 ew2m,
  60                     std::vector&lt;typename boost::graph_traits&lt;Graph&gt;::edge_descriptor&gt; *pcc = 0);
  61
  62 template &lt;typename FloatTraits, typename <A HREF="http://boost.org/libs/graph/doc/Graph.html">Graph</A>, typename VertexIndexMap,
  63           typename EdgeWeight1, typename EdgeWeight2&gt;
  64 typename FloatTraits::float_type
  65 minimum_cycle_ratio(const Graph &amp;g, VertexIndexMap vim,
  66                     EdgeWeight1 ewm, EdgeWeight2 ew2m,
  67                     std::vector&lt;typename boost::graph_traits&lt;Graph&gt;::edge_descriptor&gt; *pcc = 0,
  68                     FloatTraits = FloatTraits());
  69 </PRE>
  70 </P>
  71
  72
  73 The <tt>maximum_cycle_ratio()</tt> function calculates the maximum cycle ratio of a
  74 weighted 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.
  76 As 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>.
  80 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>
  81 <P>
  82 <IMG SRC="figs/cr.jpg" ALT="Cycle ratio definition" BORDER=0>
  83 </P>
  84
  85 The <I>maximum (minimum) cycle ratio</I> (mcr) is the maximum (minimum) cycle ratio
  86 of all cycles of the graph. A cycle is called <I>critical</I>  if its ratio is equal
  87 to the <I>mcr</I>. The calculated maximum cycle ratio will be the return value
  88 of the function. The <tt>maximum_cycle_ratio()/minimum_cycle_ratio()</tt> returns
  89 <tt>-FloatTraits::infinity()/FloatTraits::infinity()</tt> if graph has no cycles.
  90 If the <i>pcc</i> parameter is not zero then one critical cycle will be written
  91 to the corresponding <tt>std::vector</tt> of edge descriptors.  The edges in the
  92 vector stored in the way such that <tt>*pcc[0], *ppc[1], ..., *ppc[n]</tt> is a
  93 correct path.
  94 </P>
  95 <P>
  96 The algorithm is due to Howard's iteration policy algorithm, descibed in
  97 <A HREF="./cochet-terrasson98numerical.pdf">[1]</A>.
  98 Ali 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
 100 Problems</A>state that this is the most efficient algorithm to the time being (1999).</P>
 101
 102 <p>
 103 For the convenience, functions <tt>maximum_cycle_mean()</tt> and <tt>minimum_cycle_mean()</tt>
 104 are also provided. They have the following signatures:
 105 <pre>
 106 template &lt;typename Graph, typename VertexIndexMap,
 107           typename EdgeWeightMap, typename EdgeIndexMap&gt;
 108 double
 109 maximum_cycle_mean(const Graph &amp;g, VertexIndexMap vim,
 110                    EdgeWeightMap ewm, EdgeIndexMap eim,
 111                    std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt; *pcc = 0);
 112 template &lt;typename FloatTraits, typename Graph, typename VertexIndexMap,
 113           typename EdgeWeightMap, typename EdgeIndexMap&gt;
 114
 115 typename FloatTraits::float_type
 116 maximum_cycle_mean(const Graph &amp;g, VertexIndexMap vim,
 117                    EdgeWeightMap ewm, EdgeIndexMap eim,
 118                    std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt; *pcc = 0,
 119                    FloatTraits = FloatTraits());
 120
 121 template &lt;typename Graph, typename VertexIndexMap,
 122           typename EdgeWeightMap, typename EdgeIndexMap&gt;
 123 double
 124 minimum_cycle_mean(const Graph &amp;g, VertexIndexMap vim,
 125                    EdgeWeightMap ewm, EdgeIndexMap eim,
 126                    std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt; *pcc = 0);
 127 template &lt;typename FloatTraits, typename Graph, typename VertexIndexMap,
 128           typename EdgeWeightMap, typename EdgeIndexMap&gt;
 129
 130 typename FloatTraits::float_type
 131 minimum_cycle_mean(const Graph &amp;g, VertexIndexMap vim,
 132                    EdgeWeightMap ewm, EdgeIndexMap eim,
 133                    std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt; *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>
 144 The <tt>FloatTrats</tt> encapsulates customizable limits-like information for
 145 floating point types. This type <i>must</i> provide an associated type,
 146 <tt>value_type</tt> for the floating point type.
 147
 148 The default value is <tt>boost::mcr_float&lt;&gt;</tt>which has the following
 149 definition:<br/>
 150 <pre>
 151  template &lt;typename Float = double&gt;
 152  struct mcr_float {
 153     typedef Float value_type;
 154
 155     static Float infinity()
 156     { return (std::numeric_limits&lt;value_type&gt;::max)(); }
 157
 158     static Float epsilon()
 159     { return Float(-0.005); }
 160   };
 161 </pre>
 162 The value <tt>FloatTraits::epsilon()</tt> controls the "tolerance" of the
 163 algorithm. By increasing the absolute value of epsilon you may slightly decrease
 164 the execution time  but there is a risk to skip a global optima. By decreasing
 165 the absolute value you may fall to the infinite loop. The best option is to
 166 leave this parameter unchanged.
 167 </blockquote>
 168 <P>IN: <tt>const Graph&amp; g </tt>
 169 </P>
 170 <BLOCKQUOTE>A weighted directed multigraph.
 171 The graph's type must be a model of <A HREF="http://boost.org/libs/graph/doc/VertexListGraph.html">VertexListGraph</A>
 172 and <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
 177 range [0, num_vertices(g)).
 178 </BLOCKQUOTE>
 179 <P>IN: <tt>EdgeWeight1  ew1m</t>
 180 </P>
 181 <BLOCKQUOTE>
 182 The W1 edge weight function.
 183 </BLOCKQUOTE>
 184 <P>IN: <tt>EdgeWeight2 ew2m</tt>
 185 </P>
 186 <BLOCKQUOTE>
 187 The W2 edge weight function. Should be nonnegative. The actual limitation of the
 188 algorithm is the positivity of the total weight of each directed cycle of the graph.
 189 </BLOCKQUOTE>
 190 <P>
 191 OUT: <tt>std::vector&lt;typename boost::graph_traits&lt;Graph&gt;::edge_descriptor&gt;* pcc</tt>
 192 </P>
 193 <BLOCKQUOTE>
 194 If non zero then one critical cycle will be stored in the std::vector. Default
 195 value is 0.
 196 </BLOCKQUOTE>
 197 <P>
 198 IN (only for maximum/minimal_cycle_mean()): <tt>EdgeIndexMap eim</tt>
 199 </P>
 200 <BLOCKQUOTE>
 201 Maps each edge of the graph to a unique integer in the range [0, num_edges(g)).
 202 </BLOCKQUOTE>
 203 <BLOCKQUOTE STYLE="margin-left: 0cm">
 204 All property maps must be models of <A HREF="http://boost.org/libs/property_map/ReadablePropertyMap.html">Readable
 205 Property Map</A>
 206 </BLOCKQUOTE>
 207
 208 <H3>Complexity</H3>
 209 <P>There is no known precise upper bound for the time complexity of the
 210 algorithm. Imperical time complexity is <I>O(|E|)</I>, where the constant tends to
 211 be pretty small (about 20-30). Space complexity is equal to <i>7*|V|</i> plus the
 212 space 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>
 217 generates 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 &copy; 2006-2009</P>
 225         </TD>
 226         <TD>
 227             <P><A HREF="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>