30 |
30 |
31 /// \brief Default traits class of Preflow class. |
31 /// \brief Default traits class of Preflow class. |
32 /// |
32 /// |
33 /// Default traits class of Preflow class. |
33 /// Default traits class of Preflow class. |
34 /// \tparam GR Digraph type. |
34 /// \tparam GR Digraph type. |
35 /// \tparam CM Capacity map type. |
35 /// \tparam CAP Capacity map type. |
36 template <typename GR, typename CM> |
36 template <typename GR, typename CAP> |
37 struct PreflowDefaultTraits { |
37 struct PreflowDefaultTraits { |
38 |
38 |
39 /// \brief The type of the digraph the algorithm runs on. |
39 /// \brief The type of the digraph the algorithm runs on. |
40 typedef GR Digraph; |
40 typedef GR Digraph; |
41 |
41 |
42 /// \brief The type of the map that stores the arc capacities. |
42 /// \brief The type of the map that stores the arc capacities. |
43 /// |
43 /// |
44 /// The type of the map that stores the arc capacities. |
44 /// The type of the map that stores the arc capacities. |
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
46 typedef CM CapacityMap; |
46 typedef CAP CapacityMap; |
47 |
47 |
48 /// \brief The type of the flow values. |
48 /// \brief The type of the flow values. |
49 typedef typename CapacityMap::Value Value; |
49 typedef typename CapacityMap::Value Value; |
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. |
92 /// \ingroup max_flow |
92 /// \ingroup max_flow |
93 /// |
93 /// |
94 /// \brief %Preflow algorithm class. |
94 /// \brief %Preflow algorithm class. |
95 /// |
95 /// |
96 /// This class provides an implementation of Goldberg-Tarjan's \e preflow |
96 /// This class provides an implementation of Goldberg-Tarjan's \e preflow |
97 /// \e push-relabel algorithm producing a flow of maximum value in a |
97 /// \e push-relabel algorithm producing a \ref max_flow |
98 /// digraph. The preflow algorithms are the fastest known maximum |
98 /// "flow of maximum value" in a digraph. |
|
99 /// The preflow algorithms are the fastest known maximum |
99 /// flow algorithms. The current implementation use a mixture of the |
100 /// flow algorithms. The current implementation use a mixture of the |
100 /// \e "highest label" and the \e "bound decrease" heuristics. |
101 /// \e "highest label" and the \e "bound decrease" heuristics. |
101 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. |
102 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. |
102 /// |
103 /// |
103 /// The algorithm consists of two phases. After the first phase |
104 /// The algorithm consists of two phases. After the first phase |
104 /// the maximum flow value and the minimum cut is obtained. The |
105 /// the maximum flow value and the minimum cut is obtained. The |
105 /// second phase constructs a feasible maximum flow on each arc. |
106 /// second phase constructs a feasible maximum flow on each arc. |
106 /// |
107 /// |
107 /// \tparam GR The type of the digraph the algorithm runs on. |
108 /// \tparam GR The type of the digraph the algorithm runs on. |
108 /// \tparam CM The type of the capacity map. The default map |
109 /// \tparam CAP The type of the capacity map. The default map |
109 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
110 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
110 #ifdef DOXYGEN |
111 #ifdef DOXYGEN |
111 template <typename GR, typename CM, typename TR> |
112 template <typename GR, typename CAP, typename TR> |
112 #else |
113 #else |
113 template <typename GR, |
114 template <typename GR, |
114 typename CM = typename GR::template ArcMap<int>, |
115 typename CAP = typename GR::template ArcMap<int>, |
115 typename TR = PreflowDefaultTraits<GR, CM> > |
116 typename TR = PreflowDefaultTraits<GR, CAP> > |
116 #endif |
117 #endif |
117 class Preflow { |
118 class Preflow { |
118 public: |
119 public: |
119 |
120 |
120 ///The \ref PreflowDefaultTraits "traits class" of the algorithm. |
121 ///The \ref PreflowDefaultTraits "traits class" of the algorithm. |
192 |
193 |
193 ///\name Named Template Parameters |
194 ///\name Named Template Parameters |
194 |
195 |
195 ///@{ |
196 ///@{ |
196 |
197 |
197 template <typename _FlowMap> |
198 template <typename T> |
198 struct SetFlowMapTraits : public Traits { |
199 struct SetFlowMapTraits : public Traits { |
199 typedef _FlowMap FlowMap; |
200 typedef T FlowMap; |
200 static FlowMap *createFlowMap(const Digraph&) { |
201 static FlowMap *createFlowMap(const Digraph&) { |
201 LEMON_ASSERT(false, "FlowMap is not initialized"); |
202 LEMON_ASSERT(false, "FlowMap is not initialized"); |
202 return 0; // ignore warnings |
203 return 0; // ignore warnings |
203 } |
204 } |
204 }; |
205 }; |
206 /// \brief \ref named-templ-param "Named parameter" for setting |
207 /// \brief \ref named-templ-param "Named parameter" for setting |
207 /// FlowMap type |
208 /// FlowMap type |
208 /// |
209 /// |
209 /// \ref named-templ-param "Named parameter" for setting FlowMap |
210 /// \ref named-templ-param "Named parameter" for setting FlowMap |
210 /// type. |
211 /// type. |
211 template <typename _FlowMap> |
212 template <typename T> |
212 struct SetFlowMap |
213 struct SetFlowMap |
213 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > { |
214 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > { |
214 typedef Preflow<Digraph, CapacityMap, |
215 typedef Preflow<Digraph, CapacityMap, |
215 SetFlowMapTraits<_FlowMap> > Create; |
216 SetFlowMapTraits<T> > Create; |
216 }; |
217 }; |
217 |
218 |
218 template <typename _Elevator> |
219 template <typename T> |
219 struct SetElevatorTraits : public Traits { |
220 struct SetElevatorTraits : public Traits { |
220 typedef _Elevator Elevator; |
221 typedef T Elevator; |
221 static Elevator *createElevator(const Digraph&, int) { |
222 static Elevator *createElevator(const Digraph&, int) { |
222 LEMON_ASSERT(false, "Elevator is not initialized"); |
223 LEMON_ASSERT(false, "Elevator is not initialized"); |
223 return 0; // ignore warnings |
224 return 0; // ignore warnings |
224 } |
225 } |
225 }; |
226 }; |
231 /// type. If this named parameter is used, then an external |
232 /// type. If this named parameter is used, then an external |
232 /// elevator object must be passed to the algorithm using the |
233 /// elevator object must be passed to the algorithm using the |
233 /// \ref elevator(Elevator&) "elevator()" function before calling |
234 /// \ref elevator(Elevator&) "elevator()" function before calling |
234 /// \ref run() or \ref init(). |
235 /// \ref run() or \ref init(). |
235 /// \sa SetStandardElevator |
236 /// \sa SetStandardElevator |
236 template <typename _Elevator> |
237 template <typename T> |
237 struct SetElevator |
238 struct SetElevator |
238 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > { |
239 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > { |
239 typedef Preflow<Digraph, CapacityMap, |
240 typedef Preflow<Digraph, CapacityMap, |
240 SetElevatorTraits<_Elevator> > Create; |
241 SetElevatorTraits<T> > Create; |
241 }; |
242 }; |
242 |
243 |
243 template <typename _Elevator> |
244 template <typename T> |
244 struct SetStandardElevatorTraits : public Traits { |
245 struct SetStandardElevatorTraits : public Traits { |
245 typedef _Elevator Elevator; |
246 typedef T Elevator; |
246 static Elevator *createElevator(const Digraph& digraph, int max_level) { |
247 static Elevator *createElevator(const Digraph& digraph, int max_level) { |
247 return new Elevator(digraph, max_level); |
248 return new Elevator(digraph, max_level); |
248 } |
249 } |
249 }; |
250 }; |
250 |
251 |
258 /// digraph and the maximum level should be passed to it). |
259 /// digraph and the maximum level should be passed to it). |
259 /// However an external elevator object could also be passed to the |
260 /// However an external elevator object could also be passed to the |
260 /// algorithm with the \ref elevator(Elevator&) "elevator()" function |
261 /// algorithm with the \ref elevator(Elevator&) "elevator()" function |
261 /// before calling \ref run() or \ref init(). |
262 /// before calling \ref run() or \ref init(). |
262 /// \sa SetElevator |
263 /// \sa SetElevator |
263 template <typename _Elevator> |
264 template <typename T> |
264 struct SetStandardElevator |
265 struct SetStandardElevator |
265 : public Preflow<Digraph, CapacityMap, |
266 : public Preflow<Digraph, CapacityMap, |
266 SetStandardElevatorTraits<_Elevator> > { |
267 SetStandardElevatorTraits<T> > { |
267 typedef Preflow<Digraph, CapacityMap, |
268 typedef Preflow<Digraph, CapacityMap, |
268 SetStandardElevatorTraits<_Elevator> > Create; |
269 SetStandardElevatorTraits<T> > Create; |
269 }; |
270 }; |
270 |
271 |
271 /// @} |
272 /// @} |
272 |
273 |
273 protected: |
274 protected: |
944 /// This method can be called both after running \ref startFirstPhase() |
945 /// This method can be called both after running \ref startFirstPhase() |
945 /// and \ref startSecondPhase(). The result after the second phase |
946 /// and \ref startSecondPhase(). The result after the second phase |
946 /// could be slightly different if inexact computation is used. |
947 /// could be slightly different if inexact computation is used. |
947 /// |
948 /// |
948 /// \note This function calls \ref minCut() for each node, so it runs in |
949 /// \note This function calls \ref minCut() for each node, so it runs in |
949 /// \f$O(n)\f$ time. |
950 /// O(n) time. |
950 /// |
951 /// |
951 /// \pre Either \ref run() or \ref init() must be called before |
952 /// \pre Either \ref run() or \ref init() must be called before |
952 /// using this function. |
953 /// using this function. |
953 template <typename CutMap> |
954 template <typename CutMap> |
954 void minCutMap(CutMap& cutMap) const { |
955 void minCutMap(CutMap& cutMap) const { |