devn00b
/
EQ2EMu


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264
							<HTML>
<!--
     Copyright (c) Piotr Wygocki 2013
    
     Distributed under the Boost Software License, Version 1.0.
     (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
  -->
<Head>
<Title>Boost Graph Library: Successive Shortest Path for  Min Cost Max Flow</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
        ALINK="#ff0000"> 
<IMG SRC="../../../boost.png" 
     ALT="C++ Boost" width="277" height="86"> 

<BR Clear>

<H1><A NAME="sec:successive_shortest_path_nonnegative_weights">
<TT>successive_shortest_path_nonnegative_weights</TT>
</H1>

<PRE>
<i>// named parameter version</i>
template &lt;class <a href="./Graph.html">Graph</a>, class P, class T, class R&gt;
void successive_shortest_path_nonnegative_weights(
        Graph &amp;g, 
        typename graph_traits&lt;Graph&gt;::vertex_descriptor s, 
        typename graph_traits&lt;Graph&gt;::vertex_descriptor t,
        const bgl_named_params&lt;P, T, R&gt; &amp; params  = <i>all defaults</i>)

<i>// non-named parameter version</i>
template &lt;class <a href="./Graph.html">Graph</a>, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex&gt;
void successive_shortest_path_nonnegative_weights(
        const Graph &amp; g, 
        typename graph_traits&lt;Graph&gt;::vertex_descriptor s, 
        typename graph_traits&lt;Graph&gt;::vertex_descriptor t,
        Capacity capacity,
        ResidualCapacity residual_capacity,
        Weight weight, 
        Reversed rev,
        VertexIndex index,
        Pred pred, 
        Distance distance,
        Distance2 distance_prev) 
</PRE>

<P>
The <tt>successive_shortest_path_nonnegative_weights()</tt> function calculates the minimum cost maximum flow of a network. See Section <a
href="./graph_theory_review.html#sec:network-flow-algorithms">Network
Flow Algorithms</a> for a description of maximum flow.  
 The function calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
<i>E</i>, which are returned in the form of the residual capacity
<i>r(u,v) = c(u,v) - f(u,v)</i>. 

<p>
There are several special requirements on the input graph and property
map parameters for this algorithm. First, the directed graph
<i>G=(V,E)</i> that represents the network must be augmented to
include the reverse edge for every edge in <i>E</i>.  That is, the
input graph should be <i>G<sub>in</sub> = (V,{E U
E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
must map each edge in the original graph to its reverse edge, that is
<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
to 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.

<p>
The algorithm is described in <a
href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.

<p>
This algorithm starts with empty flow and in each round augments the shortest path (in terms of weight) in the residual graph.

<p> 
In order to find the cost of the result flow use:
<a href="./find_flow_cost.html"><tt>find_flow_cost()</tt></a>.

<H3>Where Defined</H3>

<P>
<a href="../../../boost/graph/successive_shortest_path_nonnegative_weights.hpp"><TT>boost/graph/successive_shortest_path_nonnegative_weights.hpp</TT></a>

<P>

<h3>Parameters</h3>

IN: <tt>Graph&amp; g</tt>
<blockquote>
  A directed graph. The
  graph's type must be a model of <a
  href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a> For each edge
  <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
  be in the graph.
</blockquote>

IN: <tt>vertex_descriptor s</tt>
<blockquote>
  The source vertex for the flow network graph.
</blockquote>
  
IN: <tt>vertex_descriptor t</tt>
<blockquote>
  The sink vertex for the flow network graph.
</blockquote>
  
<h3>Named Parameters</h3>


IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
<blockquote>
  The edge capacity property map. The type must be a model of a
  constant <a
  href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The
  key type of the map must be the graph's edge descriptor type.<br>
  <b>Default:</b> <tt>get(edge_capacity, g)</tt>
</blockquote>
  
OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
<blockquote>
  This maps edges to their residual capacity. The type must be a model
  of a mutable <a
  href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
  Map</a>. The key type of the map must be the graph's edge descriptor
  type.<br>
  <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
</blockquote>

IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
<blockquote>
  An edge property map that maps every edge <i>(u,v)</i> in the graph
  to the reverse edge <i>(v,u)</i>. The map must be a model of
  constant <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue
  Property Map</a>. The key type of the map must be the graph's edge
  descriptor type.<br>
  <b>Default:</b> <tt>get(edge_reverse, g)</tt>
</blockquote>

IN: <tt>weight_map(WeightMap w_map)</tt>   
<blockquote>
  The weight or ``cost'' of each edge in the graph. The weights
  must all be non-negative, and the algorithm will throw a
  <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> 
  exception if one of the edges is negative.
  The type <tt>WeightMap</tt> must be a model of
  <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of
  the graph needs to be usable as the key type for the weight
  map. The value type for this map must be
  the same as the value type of the distance map.<br>
  <b>Default:</b>  <tt>get(edge_weight, g)</tt><br>

</blockquote>

UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
<blockquote>
  Use by the algorithm to store augmenting paths. The map must be a
  model of mutable <a
  href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>.
  The key type must be the graph's vertex descriptor type and the
  value type must be the graph's edge descriptor type.<br>

  <b>Default:</b> an <a
  href="../../property_map/doc/iterator_property_map.html">
  <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
  of edge descriptors of size <tt>num_vertices(g)</tt> and
  using the <tt>i_map</tt> for the index map.
</blockquote>

UTIL: <tt>distance_map(DistanceMap d_map)</tt> 
<blockquote>
  The shortest path weight from the source vertex <tt>s</tt> to each
  vertex in the graph <tt>g</tt> is recorded in this property map. The
  shortest path weight is the sum of the edge weights along the
  shortest path.  The type <tt>DistanceMap</tt> must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  Property Map</a>. The vertex descriptor type of the graph needs to
  be usable as the key type of the distance map. 

  <b>Default:</b> <a
  href="../../property_map/doc/iterator_property_map.html">
  <tt>iterator_property_map</tt></a> created from a
  <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
  <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
  map.<br>

</blockquote>

UTIL: <tt>distance_map2(DistanceMap2 d_map2)</tt> 
<blockquote>
  The shortest path computation in iteration nr <i>k</i> uses distances computed in iteration <i>k</i>.
  The type <tt>DistanceMap2</tt> must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  Property Map</a>. The vertex descriptor type of the graph needs to
  be usable as the key type of the distance map. 

  <b>Default:</b> <a
  href="../../property_map/doc/iterator_property_map.html">
  <tt>iterator_property_map</tt></a> created from a
  <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
  <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
  map.<br>

</blockquote>

IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
<blockquote>
  Maps each vertex of the graph to a unique integer in the range
  <tt>[0, num_vertices(g))</tt>. This property map is only needed
  if the default for the distance or distance2 or predecessor map is used.
  The vertex index map must be a model of <a
  href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
  Map</a>. The key type of the map must be the graph's vertex
  descriptor type.<br>
  <b>Default:</b> <tt>get(vertex_index, g)</tt>
    Note: if you use this default, make sure your graph has
    an internal <tt>vertex_index</tt> property. For example,
    <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
    not have an internal <tt>vertex_index</tt> property.
</blockquote>


<h3>Complexity</h3>
In 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>, 
where <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.
In many real world cases number of iterations is much smaller than <i>U</i>.


<h3>Example</h3>

The program in <a
href="../example/successive_shortest_path_nonnegative_weights_example.cpp"><tt>example/successive_shortest_path_nonnegative_weights_example.cpp</tt></a>.

<h3>See Also</h3>

<a href="./cycle_canceling.html"><tt>cycle_canceling()</tt></a><br>
<a href="./find_flow_cost.html"><tt>find_flow_cost()</tt></a>.

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2013</TD><TD>
Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos@mimuw.edu.pl">wygos at mimuw.edu.pl</A>)
</TD></TR></TABLE>

</BODY>
</HTML> 
<!--  LocalWords:  HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
 -->
<!--  LocalWords:  gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
 -->
<!--  LocalWords:  typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
 -->
<!--  LocalWords:  ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
 -->
<!--  LocalWords:  PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
 -->
<!--  LocalWords:  num ColorValue DIMACS cpp pre config iostream dimacs int std
 -->
<!--  LocalWords:  namespace vecS directedS cout endl iter ei HR valign nowrap
 -->
<!--  LocalWords:  jeremy siek htm Univ mailto jsiek lsc edu
p -->