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> 24template <class <a href="./Graph.html">Graph</a>, class P, class T, class R> 25void cycle_canceling( 26 Graph &g, 27 const bgl_named_params<P, T, R> & params = <i>all defaults</i>) 28 29<i>// non-named parameter version</i> 30template <class <a href="./Graph.html">Graph</a>, class Pred, class Distance, class Reversed, class ResidualCapacity, class Weight> 31void cycle_canceling(const Graph & g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, Pred pred, Distance distance) 32</PRE> 33 34<P> 35The <tt>cycle_canceling()</tt> function calculates the minimum cost flow of a network with given flow. See Section <a 36href="./graph_theory_review.html#sec:network-flow-algorithms">Network 37Flow Algorithms</a> for a description of maximum flow. 38For 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> 47There are several special requirements on the input graph and property 48map parameters for this algorithm. First, the directed graph 49<i>G=(V,E)</i> that represents the network must be augmented to 50include the reverse edge for every edge in <i>E</i>. That is, the 51input graph should be <i>G<sub>in</sub> = (V,{E U 52E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt> 53must 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>. 55The <tt>WeightMap</tt> has to map each edge from <i>E<sup>T</sup></i> to <i>-weight</i> of its reversed edge. 56Note that edges from <i>E</i> can have negative weights. 57<p> 58If weights in the graph are nonnegative, the 59<a href="./successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights()</tt></a> 60might be better choice for min cost max flow. 61 62<p> 63The algorithm is described in <a 64href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>. 65 66<p> 67In each round algorithm augments the negative cycle (in terms of weight) in the residual graph. 68If there is no negative cycle in the network, the cost is optimized. 69 70<p> 71Note that, although we mention capacity in the problem description, the actual algorithm doesn't have to now it. 72 73<p> 74In 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 87IN: <tt>Graph& 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 99IN/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 109IN: <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 119IN: <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 130UTIL: <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 145UTIL: <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 164IN: <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> 181In 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>, 182where <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. 183In many real world cases number of iterations is much smaller than <i>C</i>. 184 185 186<h3>Example</h3> 187 188The program in <a 189href="../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 © 2013</TD><TD> 202Piotr 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 222p --> 223 224
