[ceph.git] / ceph / src / boost / libs / graph / doc / successive_shortest_path_nonnegative_weights.html

<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 -->
Commit	Line	Data
7c673cae FG	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>
	24	template <class <a href="./Graph.html">Graph</a>, class P, class T, class R>
	25	void 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>
	32	template <class <a href="./Graph.html">Graph</a>, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex>
	33	void 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>
	48	The <tt>successive_shortest_path_nonnegative_weights()</tt> function calculates the minimum cost maximum flow of a network. See Section <a
	49	href="./graph_theory_review.html#sec:network-flow-algorithms">Network
	50	Flow 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>
	56	There are several special requirements on the input graph and property
	57	map parameters for this algorithm. First, the directed graph
	58	<i>G=(V,E)</i> that represents the network must be augmented to
	59	include the reverse edge for every edge in <i>E</i>. That is, the
	60	input graph should be <i>G<sub>in</sub> = (V,{E U
	61	E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
	62	must 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>
66	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.
67
68	<p>
69	The algorithm is described in <a
70	href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
71
72	<p>
73	This algorithm starts with empty flow and in each round augments the shortest path (in terms of weight) in the residual graph.
74
75	<p>
76	In 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
88	IN: <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
97	IN: <tt>vertex_descriptor s</tt>
98	<blockquote>
99	The source vertex for the flow network graph.
100	</blockquote>
101
102	IN: <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
110	IN: <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
119	OUT: <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
129	IN: <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
139	IN: <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
154	UTIL: <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
169	UTIL: <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
188	UTIL: <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
205	IN: <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>
223	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>,
224	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.
225	In many real world cases number of iterations is much smaller than <i>U</i>.
226
227
228	<h3>Example</h3>
229
230	The program in <a
231	href="../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>
243	Piotr 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
263	p -->
264