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: Successive Shortest Path 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:successive_shortest_path_nonnegative_weights"> 19<TT>successive_shortest_path_nonnegative_weights</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 successive_shortest_path_nonnegative_weights( 26 Graph &g, 27 typename graph_traits<Graph>::vertex_descriptor s, 28 typename graph_traits<Graph>::vertex_descriptor t, 29 const bgl_named_params<P, T, R> & params = <i>all defaults</i>) 30 31<i>// non-named parameter version</i> 32template <class <a href="./Graph.html">Graph</a>, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex> 33void successive_shortest_path_nonnegative_weights( 34 const Graph & g, 35 typename graph_traits<Graph>::vertex_descriptor s, 36 typename graph_traits<Graph>::vertex_descriptor t, 37 Capacity capacity, 38 ResidualCapacity residual_capacity, 39 Weight weight, 40 Reversed rev, 41 VertexIndex index, 42 Pred pred, 43 Distance distance, 44 Distance2 distance_prev) 45</PRE> 46 47<P> 48The <tt>successive_shortest_path_nonnegative_weights()</tt> function calculates the minimum cost maximum flow of a network. See Section <a 49href="./graph_theory_review.html#sec:network-flow-algorithms">Network 50Flow Algorithms</a> for a description of maximum flow. 51 The function calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in 52<i>E</i>, which are returned in the form of the residual capacity 53<i>r(u,v) = c(u,v) - f(u,v)</i>. 54 55<p> 56There are several special requirements on the input graph and property 57map parameters for this algorithm. First, the directed graph 58<i>G=(V,E)</i> that represents the network must be augmented to 59include the reverse edge for every edge in <i>E</i>. That is, the 60input graph should be <i>G<sub>in</sub> = (V,{E U 61E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt> 62must map each edge in the original graph to its reverse edge, that is 63<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The 64<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in 65<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i> 66to 0. The <tt>WeightMap</tt> has to map each edge from <i>E</i> to nonnegative number, and each edge from <i>E<sup>T</sup></i> to <i>-weight</i> of its reversed edge. 67 68<p> 69The algorithm is described in <a 70href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>. 71 72<p> 73This algorithm starts with empty flow and in each round augments the shortest path (in terms of weight) in the residual graph. 74 75<p> 76In order to find the cost of the result flow use: 77<a href="./find_flow_cost.html"><tt>find_flow_cost()</tt></a>. 78 79<H3>Where Defined</H3> 80 81<P> 82<a href="../../../boost/graph/successive_shortest_path_nonnegative_weights.hpp"><TT>boost/graph/successive_shortest_path_nonnegative_weights.hpp</TT></a> 83 84<P> 85 86<h3>Parameters</h3> 87 88IN: <tt>Graph& g</tt> 89<blockquote> 90 A directed graph. The 91 graph's type must be a model of <a 92 href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a> For each edge 93 <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also 94 be in the graph. 95</blockquote> 96 97IN: <tt>vertex_descriptor s</tt> 98<blockquote> 99 The source vertex for the flow network graph. 100</blockquote> 101 102IN: <tt>vertex_descriptor t</tt> 103<blockquote> 104 The sink vertex for the flow network graph. 105</blockquote> 106 107<h3>Named Parameters</h3> 108 109 110IN: <tt>capacity_map(CapacityEdgeMap cap)</tt> 111<blockquote> 112 The edge capacity property map. The type must be a model of a 113 constant <a 114 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The 115 key type of the map must be the graph's edge descriptor type.<br> 116 <b>Default:</b> <tt>get(edge_capacity, g)</tt> 117</blockquote> 118 119OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt> 120<blockquote> 121 This maps edges to their residual capacity. The type must be a model 122 of a mutable <a 123 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property 124 Map</a>. The key type of the map must be the graph's edge descriptor 125 type.<br> 126 <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt> 127</blockquote> 128 129IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt> 130<blockquote> 131 An edge property map that maps every edge <i>(u,v)</i> in the graph 132 to the reverse edge <i>(v,u)</i>. The map must be a model of 133 constant <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue 134 Property Map</a>. The key type of the map must be the graph's edge 135 descriptor type.<br> 136 <b>Default:</b> <tt>get(edge_reverse, g)</tt> 137</blockquote> 138 139IN: <tt>weight_map(WeightMap w_map)</tt> 140<blockquote> 141 The weight or ``cost'' of each edge in the graph. The weights 142 must all be non-negative, and the algorithm will throw a 143 <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> 144 exception if one of the edges is negative. 145 The type <tt>WeightMap</tt> must be a model of 146 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of 147 the graph needs to be usable as the key type for the weight 148 map. The value type for this map must be 149 the same as the value type of the distance map.<br> 150 <b>Default:</b> <tt>get(edge_weight, g)</tt><br> 151 152</blockquote> 153 154UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt> 155<blockquote> 156 Use by the algorithm to store augmenting paths. The map must be a 157 model of mutable <a 158 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. 159 The key type must be the graph's vertex descriptor type and the 160 value type must be the graph's edge descriptor type.<br> 161 162 <b>Default:</b> an <a 163 href="../../property_map/doc/iterator_property_map.html"> 164 <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt> 165 of edge descriptors of size <tt>num_vertices(g)</tt> and 166 using the <tt>i_map</tt> for the index map. 167</blockquote> 168 169UTIL: <tt>distance_map(DistanceMap d_map)</tt> 170<blockquote> 171 The shortest path weight from the source vertex <tt>s</tt> to each 172 vertex in the graph <tt>g</tt> is recorded in this property map. The 173 shortest path weight is the sum of the edge weights along the 174 shortest path. The type <tt>DistanceMap</tt> must be a model of <a 175 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 176 Property Map</a>. The vertex descriptor type of the graph needs to 177 be usable as the key type of the distance map. 178 179 <b>Default:</b> <a 180 href="../../property_map/doc/iterator_property_map.html"> 181 <tt>iterator_property_map</tt></a> created from a 182 <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size 183 <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index 184 map.<br> 185 186</blockquote> 187 188UTIL: <tt>distance_map2(DistanceMap2 d_map2)</tt> 189<blockquote> 190 The shortest path computation in iteration nr <i>k</i> uses distances computed in iteration <i>k</i>. 191 The type <tt>DistanceMap2</tt> must be a model of <a 192 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 193 Property Map</a>. The vertex descriptor type of the graph needs to 194 be usable as the key type of the distance map. 195 196 <b>Default:</b> <a 197 href="../../property_map/doc/iterator_property_map.html"> 198 <tt>iterator_property_map</tt></a> created from a 199 <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size 200 <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index 201 map.<br> 202 203</blockquote> 204 205IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 206<blockquote> 207 Maps each vertex of the graph to a unique integer in the range 208 <tt>[0, num_vertices(g))</tt>. This property map is only needed 209 if the default for the distance or distance2 or predecessor map is used. 210 The vertex index map must be a model of <a 211 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 212 Map</a>. The key type of the map must be the graph's vertex 213 descriptor type.<br> 214 <b>Default:</b> <tt>get(vertex_index, g)</tt> 215 Note: if you use this default, make sure your graph has 216 an internal <tt>vertex_index</tt> property. For example, 217 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 218 not have an internal <tt>vertex_index</tt> property. 219</blockquote> 220 221 222<h3>Complexity</h3> 223In the integer capacity case, if <i>U</i> is the value of the max flow, then the complexity is <i> O(U * (|E| + |V|*log|V|))</i>, 224where <i>O(|E| + |V|*log|V|)</i> is the complexity of the dijkstra algorithm and <i>U</i> is upper bound on number of iteration. 225In many real world cases number of iterations is much smaller than <i>U</i>. 226 227 228<h3>Example</h3> 229 230The program in <a 231href="../example/successive_shortest_path_nonnegative_weights_example.cpp"><tt>example/successive_shortest_path_nonnegative_weights_example.cpp</tt></a>. 232 233<h3>See Also</h3> 234 235<a href="./cycle_canceling.html"><tt>cycle_canceling()</tt></a><br> 236<a href="./find_flow_cost.html"><tt>find_flow_cost()</tt></a>. 237 238<br> 239<HR> 240<TABLE> 241<TR valign=top> 242<TD nowrap>Copyright © 2013</TD><TD> 243Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos@mimuw.edu.pl">wygos at mimuw.edu.pl</A>) 244</TD></TR></TABLE> 245 246</BODY> 247</HTML> 248<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC 249 --> 250<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt 251 --> 252<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt 253 --> 254<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred 255 --> 256<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap 257 --> 258<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std 259 --> 260<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap 261 --> 262<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu 263p --> 264 265
