28 #include <limits> |
28 #include <limits> |
29 #include <lemon/core.h> |
29 #include <lemon/core.h> |
30 #include <lemon/bin_heap.h> |
30 #include <lemon/bin_heap.h> |
31 |
31 |
32 namespace lemon { |
32 namespace lemon { |
|
33 |
|
34 /// \brief Default traits class of CapacityScaling algorithm. |
|
35 /// |
|
36 /// Default traits class of CapacityScaling algorithm. |
|
37 /// \tparam GR Digraph type. |
|
38 /// \tparam V The value type used for flow amounts, capacity bounds |
|
39 /// and supply values. By default it is \c int. |
|
40 /// \tparam C The value type used for costs and potentials. |
|
41 /// By default it is the same as \c V. |
|
42 template <typename GR, typename V = int, typename C = V> |
|
43 struct CapacityScalingDefaultTraits |
|
44 { |
|
45 /// The type of the digraph |
|
46 typedef GR Digraph; |
|
47 /// The type of the flow amounts, capacity bounds and supply values |
|
48 typedef V Value; |
|
49 /// The type of the arc costs |
|
50 typedef C Cost; |
|
51 |
|
52 /// \brief The type of the heap used for internal Dijkstra computations. |
|
53 /// |
|
54 /// The type of the heap used for internal Dijkstra computations. |
|
55 /// It must conform to the \ref lemon::concepts::Heap "Heap" concept, |
|
56 /// its priority type must be \c Cost and its cross reference type |
|
57 /// must be \ref RangeMap "RangeMap<int>". |
|
58 typedef BinHeap<Cost, RangeMap<int> > Heap; |
|
59 }; |
33 |
60 |
34 /// \addtogroup min_cost_flow_algs |
61 /// \addtogroup min_cost_flow_algs |
35 /// @{ |
62 /// @{ |
36 |
63 |
37 /// \brief Implementation of the Capacity Scaling algorithm for |
64 /// \brief Implementation of the Capacity Scaling algorithm for |
55 /// |
82 /// |
56 /// \warning Both value types must be signed and all input data must |
83 /// \warning Both value types must be signed and all input data must |
57 /// be integer. |
84 /// be integer. |
58 /// \warning This algorithm does not support negative costs for such |
85 /// \warning This algorithm does not support negative costs for such |
59 /// arcs that have infinite upper bound. |
86 /// arcs that have infinite upper bound. |
60 template <typename GR, typename V = int, typename C = V> |
87 #ifdef DOXYGEN |
|
88 template <typename GR, typename V, typename C, typename TR> |
|
89 #else |
|
90 template < typename GR, typename V = int, typename C = V, |
|
91 typename TR = CapacityScalingDefaultTraits<GR, V, C> > |
|
92 #endif |
61 class CapacityScaling |
93 class CapacityScaling |
62 { |
94 { |
63 public: |
95 public: |
64 |
96 |
|
97 /// The type of the digraph |
|
98 typedef typename TR::Digraph Digraph; |
65 /// The type of the flow amounts, capacity bounds and supply values |
99 /// The type of the flow amounts, capacity bounds and supply values |
66 typedef V Value; |
100 typedef typename TR::Value Value; |
67 /// The type of the arc costs |
101 /// The type of the arc costs |
68 typedef C Cost; |
102 typedef typename TR::Cost Cost; |
|
103 |
|
104 /// The type of the heap used for internal Dijkstra computations |
|
105 typedef typename TR::Heap Heap; |
|
106 |
|
107 /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm |
|
108 typedef TR Traits; |
69 |
109 |
70 public: |
110 public: |
71 |
111 |
72 /// \brief Problem type constants for the \c run() function. |
112 /// \brief Problem type constants for the \c run() function. |
73 /// |
113 /// |
90 |
130 |
91 private: |
131 private: |
92 |
132 |
93 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
133 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
94 |
134 |
95 typedef std::vector<Arc> ArcVector; |
|
96 typedef std::vector<Node> NodeVector; |
|
97 typedef std::vector<int> IntVector; |
135 typedef std::vector<int> IntVector; |
98 typedef std::vector<bool> BoolVector; |
136 typedef std::vector<bool> BoolVector; |
99 typedef std::vector<Value> ValueVector; |
137 typedef std::vector<Value> ValueVector; |
100 typedef std::vector<Cost> CostVector; |
138 typedef std::vector<Cost> CostVector; |
101 |
139 |
153 // shortest paths in the residual network of the digraph with |
191 // shortest paths in the residual network of the digraph with |
154 // respect to the reduced arc costs and modifying the node |
192 // respect to the reduced arc costs and modifying the node |
155 // potentials according to the found distance labels. |
193 // potentials according to the found distance labels. |
156 class ResidualDijkstra |
194 class ResidualDijkstra |
157 { |
195 { |
158 typedef RangeMap<int> HeapCrossRef; |
|
159 typedef BinHeap<Cost, HeapCrossRef> Heap; |
|
160 |
|
161 private: |
196 private: |
162 |
197 |
163 int _node_num; |
198 int _node_num; |
164 const IntVector &_first_out; |
199 const IntVector &_first_out; |
165 const IntVector &_target; |
200 const IntVector &_target; |
180 _excess(cs._excess), _pi(cs._pi), _pred(cs._pred), |
215 _excess(cs._excess), _pi(cs._pi), _pred(cs._pred), |
181 _dist(cs._node_num) |
216 _dist(cs._node_num) |
182 {} |
217 {} |
183 |
218 |
184 int run(int s, Value delta = 1) { |
219 int run(int s, Value delta = 1) { |
185 HeapCrossRef heap_cross_ref(_node_num, Heap::PRE_HEAP); |
220 RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP); |
186 Heap heap(heap_cross_ref); |
221 Heap heap(heap_cross_ref); |
187 heap.push(s, 0); |
222 heap.push(s, 0); |
188 _pred[s] = -1; |
223 _pred[s] = -1; |
189 _proc_nodes.clear(); |
224 _proc_nodes.clear(); |
190 |
225 |
231 |
266 |
232 }; //class ResidualDijkstra |
267 }; //class ResidualDijkstra |
233 |
268 |
234 public: |
269 public: |
235 |
270 |
|
271 /// \name Named Template Parameters |
|
272 /// @{ |
|
273 |
|
274 template <typename T> |
|
275 struct SetHeapTraits : public Traits { |
|
276 typedef T Heap; |
|
277 }; |
|
278 |
|
279 /// \brief \ref named-templ-param "Named parameter" for setting |
|
280 /// \c Heap type. |
|
281 /// |
|
282 /// \ref named-templ-param "Named parameter" for setting \c Heap |
|
283 /// type, which is used for internal Dijkstra computations. |
|
284 /// It must conform to the \ref lemon::concepts::Heap "Heap" concept, |
|
285 /// its priority type must be \c Cost and its cross reference type |
|
286 /// must be \ref RangeMap "RangeMap<int>". |
|
287 template <typename T> |
|
288 struct SetHeap |
|
289 : public CapacityScaling<GR, V, C, SetHeapTraits<T> > { |
|
290 typedef CapacityScaling<GR, V, C, SetHeapTraits<T> > Create; |
|
291 }; |
|
292 |
|
293 /// @} |
|
294 |
|
295 public: |
|
296 |
236 /// \brief Constructor. |
297 /// \brief Constructor. |
237 /// |
298 /// |
238 /// The constructor of the class. |
299 /// The constructor of the class. |
239 /// |
300 /// |
240 /// \param graph The digraph the algorithm runs on. |
301 /// \param graph The digraph the algorithm runs on. |