123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233 |
- <!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="https://web.archive.org/web/20081122083634/http://www.lsi.upc.edu/~dmitry">Dmitry
- Bufistov</A>, Andrey Parfenov</P>
- </TD>
- </TR>
- </TABLE>
- <P><BR><BR>
- </P></HTML>
|