3 Copyright (c) Piotr Wygocki 2013
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)
10 <Title>Boost Graph Library: Cycle Canceling for Min Cost Max Flow
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><A NAME=
"sec:cycle_canceling">
19 <TT>cycle_canceling
</TT>
23 <i>// named parameter version
</i>
24 template
<class
<a href=
"./Graph.html">Graph
</a>, class P, class T, class R
>
27 const bgl_named_params
<P, T, R
> & params =
<i>all defaults
</i>)
29 <i>// non-named parameter version
</i>
30 template
<class
<a href=
"./Graph.html">Graph
</a>, class Pred, class Distance, class Reversed, class ResidualCapacity, class Weight
>
31 void cycle_canceling(const Graph
& g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, Pred pred, Distance distance)
35 The
<tt>cycle_canceling()
</tt> function calculates the minimum cost flow of a network with given flow. See Section
<a
36 href=
"./graph_theory_review.html#sec:network-flow-algorithms">Network
37 Flow Algorithms
</a> for a description of maximum flow.
38 For given flow values
<i> f(u,v)
</i> function minimizes flow cost in such a way, that for each
<i>v in V
</i> the
39 <i> sum
<sub> u in V
</sub> f(v,u)
</i> is preserved. Particularly if the input flow was the maximum flow, the function produces min cost max flow.
42 The function calculates the flow values
<i>f(u,v)
</i> for all
<i>(u,v)
</i> in
43 <i>E
</i>, which are returned in the form of the residual capacity
44 <i>r(u,v) = c(u,v) - f(u,v)
</i>.
47 There are several special requirements on the input graph and property
48 map parameters for this algorithm. First, the directed graph
49 <i>G=(V,E)
</i> that represents the network must be augmented to
50 include the reverse edge for every edge in
<i>E
</i>. That is, the
51 input graph should be
<i>G
<sub>in
</sub> = (V,{E U
52 E
<sup>T
</sup>})
</i>. The
<tt>ReverseEdgeMap
</tt> argument
<tt>rev
</tt>
53 must map each edge in the original graph to its reverse edge, that is
54 <i>(u,v) -
> (v,u)
</i> for all
<i>(u,v)
</i> in
<i>E
</i>.
55 The
<tt>WeightMap
</tt> has to map each edge from
<i>E
<sup>T
</sup></i> to
<i>-weight
</i> of its reversed edge.
56 Note that edges from
<i>E
</i> can have negative weights.
58 If weights in the graph are nonnegative, the
59 <a href=
"./successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights()
</tt></a>
60 might be better choice for min cost max flow.
63 The algorithm is described in
<a
64 href=
"./bibliography.html#ahuja93:_network_flows">Network Flows
</a>.
67 In each round algorithm augments the negative cycle (in terms of weight) in the residual graph.
68 If there is no negative cycle in the network, the cost is optimized.
71 Note that, although we mention capacity in the problem description, the actual algorithm doesn't have to now it.
74 In order to find the cost of the result flow use:
75 <a href=
"./find_flow_cost.html"><tt>find_flow_cost()
</tt></a>.
78 <H3>Where Defined
</H3>
81 <a href=
"../../../boost/graph/successive_shortest_path_nonnegative_weights.hpp"><TT>boost/graph/successive_shortest_path_nonnegative_weights.hpp
</TT></a>
87 IN:
<tt>Graph
& g
</tt>
90 graph's type must be a model of
<a
91 href=
"./VertexListGraph.html">VertexListGraph
</a> and
<a href=
"./IncidenceGraph.html">IncidenceGraph
</a> For each edge
92 <i>(u,v)
</i> in the graph, the reverse edge
<i>(v,u)
</i> must also
96 <h3>Named Parameters
</h3>
99 IN/OUT:
<tt>residual_capacity_map(ResidualCapacityEdgeMap res)
</tt>
101 This maps edges to their residual capacity. The type must be a model
103 href=
"../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
104 Map
</a>. The key type of the map must be the graph's edge descriptor
106 <b>Default:
</b> <tt>get(edge_residual_capacity, g)
</tt>
109 IN:
<tt>reverse_edge_map(ReverseEdgeMap rev)
</tt>
111 An edge property map that maps every edge
<i>(u,v)
</i> in the graph
112 to the reverse edge
<i>(v,u)
</i>. The map must be a model of
113 constant
<a href=
"../../property_map/doc/LvaluePropertyMap.html">Lvalue
114 Property Map
</a>. The key type of the map must be the graph's edge
116 <b>Default:
</b> <tt>get(edge_reverse, g)
</tt>
119 IN:
<tt>weight_map(WeightMap w)
</tt>
121 The weight (also know as ``length'' or ``cost'') of each edge in the
122 graph. The
<tt>WeightMap
</tt> type must be a model of
<a
123 href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property
124 Map
</a>. The key type for this property map must be the edge
125 descriptor of the graph. The value type for the weight map must be
126 <i>Addable
</i> with the distance map's value type.
<br>
127 <b>Default:
</b> <tt>get(edge_weight, g)
</tt><br>
130 UTIL:
<tt>predecessor_map(PredEdgeMap pred)
</tt>
132 Use by the algorithm to store augmenting paths. The map must be a
134 href=
"../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map
</a>.
135 The key type must be the graph's vertex descriptor type and the
136 value type must be the graph's edge descriptor type.
<br>
138 <b>Default:
</b> an
<a
139 href=
"../../property_map/doc/iterator_property_map.html">
140 <tt>iterator_property_map
</tt></a> created from a
<tt>std::vector
</tt>
141 of edge descriptors of size
<tt>num_vertices(g)
</tt> and
142 using the
<tt>i_map
</tt> for the index map.
145 UTIL:
<tt>distance_map(DistanceMap d_map)
</tt>
147 The shortest path weight from the source vertex
<tt>s
</tt> to each
148 vertex in the graph
<tt>g
</tt> is recorded in this property map. The
149 shortest path weight is the sum of the edge weights along the
150 shortest path. The type
<tt>DistanceMap
</tt> must be a model of
<a
151 href=
"../../property_map/doc/ReadWritePropertyMap.html">Read/Write
152 Property Map
</a>. The vertex descriptor type of the graph needs to
153 be usable as the key type of the distance map.
156 href=
"../../property_map/doc/iterator_property_map.html">
157 <tt>iterator_property_map
</tt></a> created from a
158 <tt>std::vector
</tt> of the
<tt>WeightMap
</tt>'s value type of size
159 <tt>num_vertices(g)
</tt> and using the
<tt>i_map
</tt> for the index
164 IN:
<tt>vertex_index_map(VertexIndexMap i_map)
</tt>
166 Maps each vertex of the graph to a unique integer in the range
167 <tt>[
0, num_vertices(g))
</tt>. This property map is only needed
168 if the default for the distance or predecessor map is used.
169 The vertex index map must be a model of
<a
170 href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property
171 Map
</a>. The key type of the map must be the graph's vertex
173 <b>Default:
</b> <tt>get(vertex_index, g)
</tt>
174 Note: if you use this default, make sure your graph has
175 an internal
<tt>vertex_index
</tt> property. For example,
176 <tt>adjacency_list
</tt> with
<tt>VertexList=listS
</tt> does
177 not have an internal
<tt>vertex_index
</tt> property.
181 In the integer capacity and weight case, if
<i>C
</i> is the initial cost of the flow, then the complexity is
<i> O(C * |V| * |E|)
</i>,
182 where
<i>O(|E|* |V|)
</i> is the complexity of the bellman ford shortest paths algorithm and
<i>C
</i> is upper bound on number of iteration.
183 In many real world cases number of iterations is much smaller than
<i>C
</i>.
189 href=
"../example/cycle_canceling_example.cpp"><tt>example/cycle_canceling_example.cpp
</tt></a>.
194 <a href=
"./successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights()
</tt></a><br>
195 <a href=
"./find_flow_cost.html"><tt>find_flow_cost()
</tt></a>.
201 <TD nowrap
>Copyright
© 2013</TD><TD>
202 Piotr Wygocki, University of Warsaw (
<A HREF=
"mailto:wygos@mimuw.edu.pl">wygos at mimuw.edu.pl
</A>)
207 <!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
209 <!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
211 <!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
213 <!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
215 <!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
217 <!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
219 <!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
221 <!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu