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: Find Flow Cost</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:find_flow_cost"> 19<TT>find_flow_cost</TT> 20</H1> 21 22<PRE> 23<i>// named parameter version</i> 24template <class <a href="./Graph.html">Graph</a>> 25typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type 26find_flow_cost(const Graph & g, 27 const bgl_named_params<P, T, R> & params = <i>all defaults</i>) 28 29<i>// non-named parameter version</i> 30template<class <a href="./Graph.html">Graph</a>, class Capacity, class ResidualCapacity, class Weight> 31typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type 32find_flow_cost(const Graph & g, Capacity capacity, ResidualCapacity residual_capacity, Weight weight) 33</PRE> 34 35<P> 36The <tt>find_flow_cost()</tt> function calculates the minimum cost maximum flow value of a network and given flow. See Section <a 37href="./graph_theory_review.html#sec:network-flow-algorithms">Network 38Flow Algorithms</a> for a description of maximum flow. 39The function calculates the cost from the flow values <i>f(u,v)</i> for <i>(u,v)</i> in 40<i>E</i>, which are passed in the form of the residual capacity 41<i>r(u,v) = c(u,v) - f(u,v)</i>. 42 43<p> 44In order to compute the min cost max flow use : 45<a href="./successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights()</tt></a> or 46<a href="./cycle_canceling.html"><tt>cycle_canceling()</tt></a>. 47 48<H3>Where Defined</H3> 49 50<P> 51<a href="../../../boost/graph/successive_shortest_path_nonnegative_weights.hpp"><TT>boost/graph/successive_shortest_path_nonnegative_weights.hpp</TT></a> 52 53<P> 54 55<h3>Parameters</h3> 56 57IN: <tt>const Graph& g</tt> 58<blockquote> 59 A directed graph. The 60 graph's type must be a model of <a 61 href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a> For each edge 62 <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also 63 be in the graph. 64</blockquote> 65<h3>Named Parameters</h3> 66 67 68IN: <tt>capacity_map(CapacityEdgeMap cap)</tt> 69<blockquote> 70 The edge capacity property map. The type must be a model of a 71 constant <a 72 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The 73 key type of the map must be the graph's edge descriptor type.<br> 74 <b>Default:</b> <tt>get(edge_capacity, g)</tt> 75</blockquote> 76 77IN: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt> 78<blockquote> 79 This maps edges to their residual capacity. The type must be a model 80 of a mutable <a 81 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property 82 Map</a>. The key type of the map must be the graph's edge descriptor 83 type.<br> 84 <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt> 85</blockquote> 86 87 88IN: <tt>weight_map(WeightMap w_map)</tt> 89<blockquote> 90 The weight or ``cost'' of each edge in the graph. 91 The type <tt>WeightMap</tt> must be a model of 92 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of 93 the graph needs to be usable as the key type for the weight 94 map. The value type for this map must be 95 the same as the value type of the distance map.<br> 96 <b>Default:</b> <tt>get(edge_weight, g)</tt><br> 97 98</blockquote> 99 100<h3>Complexity</h3> 101The complexity is <i> O(|E|)</i>, 102 103<h3>Example</h3> 104 105The function is used in the successive_shortest_path_nonnegative_weights example. The program in <a 106href="../example/successive_shortest_path_nonnegative_weights_example.cpp"><tt>example/successive_shortest_path_nonnegative_weights_example.cpp</tt></a>. 107 108<h3>See Also</h3> 109 110<a href="./cycle_canceling.html"><tt>cycle_canceling()</tt></a><br> 111<a href="./successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights()</tt></a>. 112 113<br> 114<HR> 115<TABLE> 116<TR valign=top> 117<TD nowrap>Copyright © 2013</TD><TD> 118Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos@mimuw.edu.pl">wygos at mimuw.edu.pl</A>) 119</TD></TR></TABLE> 120 121</BODY> 122</HTML> 123<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC 124 --> 125<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt 126 --> 127<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt 128 --> 129<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred 130 --> 131<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap 132 --> 133<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std 134 --> 135<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap 136 --> 137<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu 138p --> 139 140
