libs/graph/doc/push_relabel_max_flow.html

   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>
  25 template &lt;class Graph, class P, class T, class R&gt;
  26 typename property_traits&lt;CapacityEdgeMap&gt;::value_type
  27 push_relabel_max_flow(Graph&amp; g,
  28    typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
  29    typename graph_traits&lt;Graph&gt;::vertex_descriptor sink,
  30    const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
  31
  32 <i>// non-named parameter version</i>
  33 template &lt;class Graph,
  34           class CapacityEdgeMap, class ResidualCapacityEdgeMap,
  35           class ReverseEdgeMap, class VertexIndexMap&gt;
  36 typename property_traits&lt;CapacityEdgeMap&gt;::value_type
  37 push_relabel_max_flow(Graph&amp; g,
  38    typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
  39    typename graph_traits&lt;Graph&gt;::vertex_descriptor sink,
  40    CapacityEdgeMap cap, ResidualCapacityEdgeMap res,
  41    ReverseEdgeMap rev, VertexIndexMap index_map)
  42 </PRE>
  43
  44 <P>
  45 The <tt>push_relabel_max_flow()</tt> function calculates the maximum flow
  46 of a network. See Section <a
  47 href="./graph_theory_review.html#sec:network-flow-algorithms">Network
  48 Flow Algorithms</a> for a description of maximum flow.  The calculated
  49 maximum flow will be the return value of the function. The function
  50 also 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>
  55 There are several special requirements on the input graph and property
  56 map parameters for this algorithm. First, the directed graph
  57 <i>G=(V,E)</i> that represents the network must be augmented to
  58 include the reverse edge for every edge in <i>E</i>.  That is, the
  59 input graph should be <i>G<sub>in</sub> = (V,{E U
  60 E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
  61 must 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>
  65 to 0.
  66
  67 <p>
  68 This algorithm was developed by <a
  69 href="./bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a>.
  70
  71
  72 <H3>Complexity</H3>
  73
  74 The 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/preflow_push_max_flow.hpp</TT></a>
  81
  82 <P>
  83
  84 <h3>Parameters</h3>
  85
  86 IN: <tt>VertexListGraph&amp; 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
  95 IN: <tt>vertex_descriptor src</tt>
  96 <blockquote>
  97   The source vertex for the flow network graph.
  98 </blockquote>
  99
 100 IN: <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
 107 IN: <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
 116 OUT: <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
 125 IN: <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
 135 IN: <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>adjacenty_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
 152 This reads in an example maximum flow problem (a graph with edge
 153 capacities) from a file in the DIMACS format. The source for this
 154 example can be found in <a
 155 href="../example/max_flow.cpp"><tt>example/max_flow.cpp</tt></a>.
 156
 157 <pre>
 158 #include &lt;boost/config.hpp&gt;
 159 #include &lt;iostream&gt;
 160 #include &lt;string&gt;
 161 #include &lt;boost/graph/push_relabel_max_flow.hpp&gt;
 162 #include &lt;boost/graph/adjacency_list.hpp&gt;
 163 #include &lt;boost/graph/read_dimacs.hpp&gt;
 164
 165 int
 166 main()
 167 {
 168   using namespace boost;
 169
 170   typedef adjacency_list_traits&lt;vecS, vecS, directedS&gt; Traits;
 171   typedef adjacency_list&lt;vecS, vecS, directedS,
 172     property&lt;vertex_name_t, std::string&gt;,
 173     property&lt;edge_capacity_t, long,
 174       property&lt;edge_residual_capacity_t, long,
 175         property&lt;edge_reverse_t, Traits::edge_descriptor&gt; &gt; &gt;
 176   &gt; Graph;
 177
 178   Graph g;
 179   long flow;
 180
 181   property_map&lt;Graph, edge_capacity_t&gt;::type
 182     capacity = get(edge_capacity, g);
 183   property_map&lt;Graph, edge_reverse_t&gt;::type
 184     rev = get(edge_reverse, g);
 185   property_map&lt;Graph, edge_residual_capacity_t&gt;::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 &lt;&lt; "c  The total flow:" &lt;&lt; std::endl;
 194   std::cout &lt;&lt; "s " &lt;&lt; flow &lt;&lt; std::endl &lt;&lt; std::endl;
 195
 196   std::cout &lt;&lt; "c flow values:" &lt;&lt; std::endl;
 197   graph_traits&lt;Graph&gt;::vertex_iterator u_iter, u_end;
 198   graph_traits&lt;Graph&gt;::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] &gt; 0)
 202         std::cout &lt;&lt; "f " &lt;&lt; *u_iter &lt;&lt; " " &lt;&lt; target(*ei, g) &lt;&lt; " "
 203                   &lt;&lt; (capacity[*ei] - residual_capacity[*ei]) &lt;&lt; std::endl;
 204   return 0;
 205 }
 206 </pre>
 207 The output is:
 208 <pre>
 209 c  The total flow:
 210 s 4
 211
 212 c flow values:
 213 f 0 1 4
 214 f 1 2 4
 215 f 2 3 2
 216 f 2 4 2
 217 f 3 1 0
 218 f 3 6 2
 219 f 4 5 3
 220 f 5 6 0
 221 f 5 7 3
 222 f 6 4 1
 223 f 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 &copy; 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  -->