1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
50 |
50 |
51 /// \brief The type of the map that stores the flow values. |
51 /// \brief The type of the map that stores the flow values. |
52 /// |
52 /// |
53 /// The type of the map that stores the flow values. |
53 /// The type of the map that stores the flow values. |
54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
|
55 #ifdef DOXYGEN |
|
56 typedef GR::ArcMap<Value> FlowMap; |
|
57 #else |
55 typedef typename Digraph::template ArcMap<Value> FlowMap; |
58 typedef typename Digraph::template ArcMap<Value> FlowMap; |
|
59 #endif |
56 |
60 |
57 /// \brief Instantiates a FlowMap. |
61 /// \brief Instantiates a FlowMap. |
58 /// |
62 /// |
59 /// This function instantiates a \ref FlowMap. |
63 /// This function instantiates a \ref FlowMap. |
60 /// \param digraph The digraph for which we would like to define |
64 /// \param digraph The digraph for which we would like to define |
65 |
69 |
66 /// \brief The elevator type used by Preflow algorithm. |
70 /// \brief The elevator type used by Preflow algorithm. |
67 /// |
71 /// |
68 /// The elevator type used by Preflow algorithm. |
72 /// The elevator type used by Preflow algorithm. |
69 /// |
73 /// |
70 /// \sa Elevator |
74 /// \sa Elevator, LinkedElevator |
71 /// \sa LinkedElevator |
75 #ifdef DOXYGEN |
72 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator; |
76 typedef lemon::Elevator<GR, GR::Node> Elevator; |
|
77 #else |
|
78 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; |
|
79 #endif |
73 |
80 |
74 /// \brief Instantiates an Elevator. |
81 /// \brief Instantiates an Elevator. |
75 /// |
82 /// |
76 /// This function instantiates an \ref Elevator. |
83 /// This function instantiates an \ref Elevator. |
77 /// \param digraph The digraph for which we would like to define |
84 /// \param digraph The digraph for which we would like to define |
93 /// |
100 /// |
94 /// \brief %Preflow algorithm class. |
101 /// \brief %Preflow algorithm class. |
95 /// |
102 /// |
96 /// This class provides an implementation of Goldberg-Tarjan's \e preflow |
103 /// This class provides an implementation of Goldberg-Tarjan's \e preflow |
97 /// \e push-relabel algorithm producing a \ref max_flow |
104 /// \e push-relabel algorithm producing a \ref max_flow |
98 /// "flow of maximum value" in a digraph. |
105 /// "flow of maximum value" in a digraph \ref clrs01algorithms, |
|
106 /// \ref amo93networkflows, \ref goldberg88newapproach. |
99 /// The preflow algorithms are the fastest known maximum |
107 /// The preflow algorithms are the fastest known maximum |
100 /// flow algorithms. The current implementation use a mixture of the |
108 /// flow algorithms. The current implementation uses a mixture of the |
101 /// \e "highest label" and the \e "bound decrease" heuristics. |
109 /// \e "highest label" and the \e "bound decrease" heuristics. |
102 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. |
110 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. |
103 /// |
111 /// |
104 /// The algorithm consists of two phases. After the first phase |
112 /// The algorithm consists of two phases. After the first phase |
105 /// the maximum flow value and the minimum cut is obtained. The |
113 /// the maximum flow value and the minimum cut is obtained. The |
106 /// second phase constructs a feasible maximum flow on each arc. |
114 /// second phase constructs a feasible maximum flow on each arc. |
107 /// |
115 /// |
|
116 /// \warning This implementation cannot handle infinite or very large |
|
117 /// capacities (e.g. the maximum value of \c CAP::Value). |
|
118 /// |
108 /// \tparam GR The type of the digraph the algorithm runs on. |
119 /// \tparam GR The type of the digraph the algorithm runs on. |
109 /// \tparam CAP The type of the capacity map. The default map |
120 /// \tparam CAP The type of the capacity map. The default map |
110 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
121 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
|
122 /// \tparam TR The traits class that defines various types used by the |
|
123 /// algorithm. By default, it is \ref PreflowDefaultTraits |
|
124 /// "PreflowDefaultTraits<GR, CAP>". |
|
125 /// In most cases, this parameter should not be set directly, |
|
126 /// consider to use the named template parameters instead. |
111 #ifdef DOXYGEN |
127 #ifdef DOXYGEN |
112 template <typename GR, typename CAP, typename TR> |
128 template <typename GR, typename CAP, typename TR> |
113 #else |
129 #else |
114 template <typename GR, |
130 template <typename GR, |
115 typename CAP = typename GR::template ArcMap<int>, |
131 typename CAP = typename GR::template ArcMap<int>, |
255 /// \ref named-templ-param "Named parameter" for setting Elevator |
271 /// \ref named-templ-param "Named parameter" for setting Elevator |
256 /// type with automatic allocation. |
272 /// type with automatic allocation. |
257 /// The Elevator should have standard constructor interface to be |
273 /// The Elevator should have standard constructor interface to be |
258 /// able to automatically created by the algorithm (i.e. the |
274 /// able to automatically created by the algorithm (i.e. the |
259 /// digraph and the maximum level should be passed to it). |
275 /// digraph and the maximum level should be passed to it). |
260 /// However an external elevator object could also be passed to the |
276 /// However, an external elevator object could also be passed to the |
261 /// algorithm with the \ref elevator(Elevator&) "elevator()" function |
277 /// algorithm with the \ref elevator(Elevator&) "elevator()" function |
262 /// before calling \ref run() or \ref init(). |
278 /// before calling \ref run() or \ref init(). |
263 /// \sa SetElevator |
279 /// \sa SetElevator |
264 template <typename T> |
280 template <typename T> |
265 struct SetStandardElevator |
281 struct SetStandardElevator |
369 /// using this function. |
385 /// using this function. |
370 const Elevator& elevator() const { |
386 const Elevator& elevator() const { |
371 return *_level; |
387 return *_level; |
372 } |
388 } |
373 |
389 |
374 /// \brief Sets the tolerance used by algorithm. |
390 /// \brief Sets the tolerance used by the algorithm. |
375 /// |
391 /// |
376 /// Sets the tolerance used by algorithm. |
392 /// Sets the tolerance object used by the algorithm. |
|
393 /// \return <tt>(*this)</tt> |
377 Preflow& tolerance(const Tolerance& tolerance) { |
394 Preflow& tolerance(const Tolerance& tolerance) { |
378 _tolerance = tolerance; |
395 _tolerance = tolerance; |
379 return *this; |
396 return *this; |
380 } |
397 } |
381 |
398 |
382 /// \brief Returns a const reference to the tolerance. |
399 /// \brief Returns a const reference to the tolerance. |
383 /// |
400 /// |
384 /// Returns a const reference to the tolerance. |
401 /// Returns a const reference to the tolerance object used by |
|
402 /// the algorithm. |
385 const Tolerance& tolerance() const { |
403 const Tolerance& tolerance() const { |
386 return _tolerance; |
404 return _tolerance; |
387 } |
405 } |
388 |
406 |
389 /// \name Execution Control |
407 /// \name Execution Control |
390 /// The simplest way to execute the preflow algorithm is to use |
408 /// The simplest way to execute the preflow algorithm is to use |
391 /// \ref run() or \ref runMinCut().\n |
409 /// \ref run() or \ref runMinCut().\n |
392 /// If you need more control on the initial solution or the execution, |
410 /// If you need better control on the initial solution or the execution, |
393 /// first you have to call one of the \ref init() functions, then |
411 /// you have to call one of the \ref init() functions first, then |
394 /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). |
412 /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). |
395 |
413 |
396 ///@{ |
414 ///@{ |
397 |
415 |
398 /// \brief Initializes the internal data structures. |
416 /// \brief Initializes the internal data structures. |