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

   1 <HTML>
   2 <!--
   3      Copyright (c) Piotr Wygocki 2013
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Boost Graph Library: Cycle Canceling for  Min Cost Max Flow</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18 <H1><A NAME="sec:cycle_canceling">
  19 <TT>cycle_canceling</TT>
  20 </H1>
  21
  22 <PRE>
  23 <i>// named parameter version</i>
  24 template &lt;class <a href="./Graph.html">Graph</a>, class P, class T, class R&gt;
  25 void cycle_canceling(
  26         Graph &amp;g,
  27         const bgl_named_params&lt;P, T, R&gt; &amp; params  = <i>all defaults</i>)
  28
  29 <i>// non-named parameter version</i>
  30 template &lt;class <a href="./Graph.html">Graph</a>, class Pred, class Distance, class Reversed, class ResidualCapacity, class Weight&gt;
  31 void cycle_canceling(const Graph &amp; g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, Pred pred, Distance distance)
  32 </PRE>
  33
  34 <P>
  35 The <tt>cycle_canceling()</tt> function calculates the minimum cost flow of a network with given flow. See Section <a
  36 href="./graph_theory_review.html#sec:network-flow-algorithms">Network
  37 Flow Algorithms</a> for a description of maximum flow.
  38 For given flow values <i> f(u,v)</i>  function minimizes flow cost in such a way, that for each <i>v in V</i> the
  39  <i> sum<sub> u in V</sub>  f(v,u) </i> is preserved. Particularly if the input flow was the maximum flow, the function produces min cost max flow.
  40
  41
  42  The function calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
  43 <i>E</i>, which are returned in the form of the residual capacity
  44 <i>r(u,v) = c(u,v) - f(u,v)</i>.
  45
  46 <p>
  47 There are several special requirements on the input graph and property
  48 map parameters for this algorithm. First, the directed graph
  49 <i>G=(V,E)</i> that represents the network must be augmented to
  50 include the reverse edge for every edge in <i>E</i>.  That is, the
  51 input graph should be <i>G<sub>in</sub> = (V,{E U
  52 E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
  53 must map each edge in the original graph to its reverse edge, that is
  54 <i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>.
  55 The <tt>WeightMap</tt> has to map each edge from <i>E<sup>T</sup></i> to <i>-weight</i> of its reversed edge.
  56 Note that edges from <i>E</i> can have negative weights.
  57 <p>
  58 If weights in the graph are nonnegative, the
  59 <a href="./successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights()</tt></a>
  60 might be better choice for min cost max flow.
  61
  62 <p>
  63 The algorithm is described in <a
  64 href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
  65
  66 <p>
  67 In each round algorithm augments the negative cycle (in terms of weight) in the residual graph.
  68 If there is no negative cycle in the network, the cost is optimized.
  69
  70 <p>
  71 Note that, although we mention capacity in the problem description, the actual algorithm doesn't have to now it.
  72
  73 <p>
  74 In order to find the cost of the result flow use:
  75 <a href="./find_flow_cost.html"><tt>find_flow_cost()</tt></a>.
  76
  77
  78 <H3>Where Defined</H3>
  79
  80 <P>
  81 <a href="../../../boost/graph/successive_shortest_path_nonnegative_weights.hpp"><TT>boost/graph/successive_shortest_path_nonnegative_weights.hpp</TT></a>
  82
  83 <P>
  84
  85 <h3>Parameters</h3>
  86
  87 IN: <tt>Graph&amp; g</tt>
  88 <blockquote>
  89   A directed graph. The
  90   graph's type must be a model of <a
  91   href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a> For each edge
  92   <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
  93   be in the graph.
  94 </blockquote>
  95
  96 <h3>Named Parameters</h3>
  97
  98
  99 IN/OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
 100 <blockquote>
 101   This maps edges to their residual capacity. The type must be a model
 102   of a mutable <a
 103   href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 104   Map</a>. The key type of the map must be the graph's edge descriptor
 105   type.<br>
 106   <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
 107 </blockquote>
 108
 109 IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
 110 <blockquote>
 111   An edge property map that maps every edge <i>(u,v)</i> in the graph
 112   to the reverse edge <i>(v,u)</i>. The map must be a model of
 113   constant <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue
 114   Property Map</a>. The key type of the map must be the graph's edge
 115   descriptor type.<br>
 116   <b>Default:</b> <tt>get(edge_reverse, g)</tt>
 117 </blockquote>
 118
 119 IN: <tt>weight_map(WeightMap w)</tt>
 120 <blockquote>
 121   The weight (also know as ``length'' or ``cost'') of each edge in the
 122   graph.  The <tt>WeightMap</tt> type must be a model of <a
 123   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 124   Map</a>.  The key type for this property map must be the edge
 125   descriptor of the graph.  The value type for the weight map must be
 126   <i>Addable</i> with the distance map's value type. <br>
 127   <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
 128 </blockquote>
 129
 130 UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
 131 <blockquote>
 132   Use by the algorithm to store augmenting paths. The map must be a
 133   model of mutable <a
 134   href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>.
 135   The key type must be the graph's vertex descriptor type and the
 136   value type must be the graph's edge descriptor type.<br>
 137
 138   <b>Default:</b> an <a
 139   href="../../property_map/doc/iterator_property_map.html">
 140   <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
 141   of edge descriptors of size <tt>num_vertices(g)</tt> and
 142   using the <tt>i_map</tt> for the index map.
 143 </blockquote>
 144
 145 UTIL: <tt>distance_map(DistanceMap d_map)</tt>
 146 <blockquote>
 147   The shortest path weight from the source vertex <tt>s</tt> to each
 148   vertex in the graph <tt>g</tt> is recorded in this property map. The
 149   shortest path weight is the sum of the edge weights along the
 150   shortest path.  The type <tt>DistanceMap</tt> must be a model of <a
 151   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 152   Property Map</a>. The vertex descriptor type of the graph needs to
 153   be usable as the key type of the distance map.
 154
 155   <b>Default:</b> <a
 156   href="../../property_map/doc/iterator_property_map.html">
 157   <tt>iterator_property_map</tt></a> created from a
 158   <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
 159   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
 160   map.<br>
 161
 162 </blockquote>
 163
 164 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 165 <blockquote>
 166   Maps each vertex of the graph to a unique integer in the range
 167   <tt>[0, num_vertices(g))</tt>. This property map is only needed
 168   if the default for the distance or predecessor map is used.
 169   The vertex index map must be a model of <a
 170   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 171   Map</a>. The key type of the map must be the graph's vertex
 172   descriptor type.<br>
 173   <b>Default:</b> <tt>get(vertex_index, g)</tt>
 174     Note: if you use this default, make sure your graph has
 175     an internal <tt>vertex_index</tt> property. For example,
 176     <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
 177     not have an internal <tt>vertex_index</tt> property.
 178 </blockquote>
 179
 180 <h3>Complexity</h3>
 181 In the integer capacity and weight case, if <i>C</i> is the initial cost of the flow, then the complexity is <i> O(C * |V| * |E|)</i>,
 182 where <i>O(|E|* |V|)</i> is the complexity of the bellman ford shortest paths algorithm and <i>C</i> is upper bound on number of iteration.
 183 In many real world cases number of iterations is much smaller than <i>C</i>.
 184
 185
 186 <h3>Example</h3>
 187
 188 The program in <a
 189 href="../example/cycle_canceling_example.cpp"><tt>example/cycle_canceling_example.cpp</tt></a>.
 190
 191
 192 <h3>See Also</h3>
 193
 194 <a href="./successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights()</tt></a><br>
 195 <a href="./find_flow_cost.html"><tt>find_flow_cost()</tt></a>.
 196
 197 <br>
 198 <HR>
 199 <TABLE>
 200 <TR valign=top>
 201 <TD nowrap>Copyright &copy; 2013</TD><TD>
 202 Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos@mimuw.edu.pl">wygos at mimuw.edu.pl</A>)
 203 </TD></TR></TABLE>
 204
 205 </BODY>
 206 </HTML>
 207 <!--  LocalWords:  HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
 208  -->
 209 <!--  LocalWords:  gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
 210  -->
 211 <!--  LocalWords:  typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
 212  -->
 213 <!--  LocalWords:  ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
 214  -->
 215 <!--  LocalWords:  PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
 216  -->
 217 <!--  LocalWords:  num ColorValue DIMACS cpp pre config iostream dimacs int std
 218  -->
 219 <!--  LocalWords:  namespace vecS directedS cout endl iter ei HR valign nowrap
 220  -->
 221 <!--  LocalWords:  jeremy siek htm Univ mailto jsiek lsc edu
 222 p -->
 223