1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 2000 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: Push-Relabel Maximum 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:push_relabel_max_flow"> 19<TT>push_relabel_max_flow</TT> 20</H1> 21 22<P> 23<PRE> 24<i>// named parameter version</i> 25template <class Graph, class P, class T, class R> 26typename property_traits<CapacityEdgeMap>::value_type 27push_relabel_max_flow(Graph& g, 28 typename graph_traits<Graph>::vertex_descriptor src, 29 typename graph_traits<Graph>::vertex_descriptor sink, 30 const bgl_named_params<P, T, R>& params = <i>all defaults</i>) 31 32<i>// non-named parameter version</i> 33template <class Graph, 34 class CapacityEdgeMap, class ResidualCapacityEdgeMap, 35 class ReverseEdgeMap, class VertexIndexMap> 36typename property_traits<CapacityEdgeMap>::value_type 37push_relabel_max_flow(Graph& g, 38 typename graph_traits<Graph>::vertex_descriptor src, 39 typename graph_traits<Graph>::vertex_descriptor sink, 40 CapacityEdgeMap cap, ResidualCapacityEdgeMap res, 41 ReverseEdgeMap rev, VertexIndexMap index_map) 42</PRE> 43 44<P> 45The <tt>push_relabel_max_flow()</tt> function calculates the maximum flow 46of a network. See Section <a 47href="./graph_theory_review.html#sec:network-flow-algorithms">Network 48Flow Algorithms</a> for a description of maximum flow. The calculated 49maximum flow will be the return value of the function. The function 50also calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in 51<i>E</i>, which are returned in the form of the residual capacity 52<i>r(u,v) = c(u,v) - f(u,v)</i>. 53 54<p> 55There are several special requirements on the input graph and property 56map parameters for this algorithm. First, the directed graph 57<i>G=(V,E)</i> that represents the network must be augmented to 58include the reverse edge for every edge in <i>E</i>. That is, the 59input graph should be <i>G<sub>in</sub> = (V,{E U 60E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt> 61must map each edge in the original graph to its reverse edge, that is 62<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The 63<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in 64<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i> 65to 0. 66 67<p> 68This algorithm was developed by <a 69href="./bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a>. 70 71 72<H3>Complexity</H3> 73 74The time complexity is <i>O(V<sup>3</sup>)</i>. 75 76 77<H3>Where Defined</H3> 78 79<P> 80<a href="../../../boost/graph/push_relabel_max_flow.hpp"><TT>boost/graph/push_relabel_max_flow.hpp</TT></a> 81 82<P> 83 84<h3>Parameters</h3> 85 86IN: <tt>VertexListGraph& g</tt> 87<blockquote> 88 A directed graph. The 89 graph's type must be a model of <a 90 href="./VertexListGraph.html">Vertex List Graph</a>. For each edge 91 <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also 92 be in the graph. 93</blockquote> 94 95IN: <tt>vertex_descriptor src</tt> 96<blockquote> 97 The source vertex for the flow network graph. 98</blockquote> 99 100IN: <tt>vertex_descriptor sink</tt> 101<blockquote> 102 The sink vertex for the flow network graph. 103</blockquote> 104 105<h3>Named Parameters</h3> 106 107IN: <tt>capacity_map(EdgeCapacityMap cap)</tt> 108<blockquote> 109 The edge capacity property map. The type must be a model of a 110 constant <a 111 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The 112 key type of the map must be the graph's edge descriptor type.<br> 113 <b>Default:</b> <tt>get(edge_capacity, g)</tt> 114</blockquote> 115 116OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt> 117<blockquote> 118 The edge residual capacity property map. The type must be a model of 119 a mutable <a 120 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The 121 key type of the map must be the graph's edge descriptor type.<br> 122 <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt> 123</blockquote> 124 125IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt> 126<blockquote> 127 An edge property map that maps every edge <i>(u,v)</i> in the graph 128 to the reverse edge <i>(v,u)</i>. The map must be a model of 129 constant <a 130 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The 131 key type of the map must be the graph's edge descriptor type.<br> 132 <b>Default:</b> <tt>get(edge_reverse, g)</tt> 133</blockquote> 134 135IN: <tt>vertex_index_map(VertexIndexMap index_map)</tt> 136<blockquote> 137 Maps each vertex of the graph to a unique integer in the range 138 <tt>[0, num_vertices(g))</tt>. The map must be a model of constant <a 139 href="../../property_map/doc/LvaluePropertyMap.html">LvaluePropertyMap</a>. The 140 key type of the map must be the graph's vertex descriptor type.<br> 141 <b>Default:</b> <tt>get(vertex_index, g)</tt> 142 Note: if you use this default, make sure your graph has 143 an internal <tt>vertex_index</tt> property. For example, 144 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 145 not have an internal <tt>vertex_index</tt> property. 146 <br> 147</blockquote> 148 149 150<h3>Example</h3> 151 152This reads in an example maximum flow problem (a graph with edge 153capacities) from a file in the DIMACS format. The source for this 154example can be found in <a 155href="../example/max_flow.cpp"><tt>example/max_flow.cpp</tt></a>. 156 157<pre> 158#include <boost/config.hpp> 159#include <iostream> 160#include <string> 161#include <boost/graph/push_relabel_max_flow.hpp> 162#include <boost/graph/adjacency_list.hpp> 163#include <boost/graph/read_dimacs.hpp> 164 165int 166main() 167{ 168 using namespace boost; 169 170 typedef adjacency_list_traits<vecS, vecS, directedS> Traits; 171 typedef adjacency_list<vecS, vecS, directedS, 172 property<vertex_name_t, std::string>, 173 property<edge_capacity_t, long, 174 property<edge_residual_capacity_t, long, 175 property<edge_reverse_t, Traits::edge_descriptor> > > 176 > Graph; 177 178 Graph g; 179 long flow; 180 181 property_map<Graph, edge_capacity_t>::type 182 capacity = get(edge_capacity, g); 183 property_map<Graph, edge_reverse_t>::type 184 rev = get(edge_reverse, g); 185 property_map<Graph, edge_residual_capacity_t>::type 186 residual_capacity = get(edge_residual_capacity, g); 187 188 Traits::vertex_descriptor s, t; 189 read_dimacs_max_flow(g, capacity, rev, s, t); 190 191 flow = push_relabel_max_flow(g, s, t); 192 193 std::cout << "c The total flow:" << std::endl; 194 std::cout << "s " << flow << std::endl << std::endl; 195 196 std::cout << "c flow values:" << std::endl; 197 graph_traits<Graph>::vertex_iterator u_iter, u_end; 198 graph_traits<Graph>::out_edge_iterator ei, e_end; 199 for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) 200 for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) 201 if (capacity[*ei] > 0) 202 std::cout << "f " << *u_iter << " " << target(*ei, g) << " " 203 << (capacity[*ei] - residual_capacity[*ei]) << std::endl; 204 return 0; 205} 206</pre> 207The output is: 208<pre> 209c The total flow: 210s 4 211 212c flow values: 213f 0 1 4 214f 1 2 4 215f 2 3 2 216f 2 4 2 217f 3 1 0 218f 3 6 2 219f 4 5 3 220f 5 6 0 221f 5 7 3 222f 6 4 1 223f 6 7 1 224</pre> 225 226<h3>See Also</h3> 227 228<a href="./edmonds_karp_max_flow.html"><tt>edmonds_karp_max_flow()</tt></a><br> 229<a href="./boykov_kolmogorov_max_flow.html"><tt>boykov_kolmogorov_max_flow()</tt></a>. 230 231<br> 232<HR> 233<TABLE> 234<TR valign=top> 235<TD nowrap>Copyright © 2000-2001</TD><TD> 236<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) 237</TD></TR></TABLE> 238 239</BODY> 240</HTML> 241<!-- LocalWords: HTML Siek BGCOLOR ffffff ee VLINK ALINK ff IMG SRC preflow 242 --> 243<!-- LocalWords: gif ALT BR sec TT DIV CELLPADDING TR TD PRE lt 244 --> 245<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt 246 --> 247<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred 248 --> 249<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap 250 --> 251<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std 252 --> 253<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap 254 --> 255<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu 256 --> 257
