Changeset 606:c5fd2d996909 in lemon for lemon/preflow.h
 Timestamp:
 03/29/09 23:08:20 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/preflow.h
r525 r606 33 33 /// Default traits class of Preflow class. 34 34 /// \tparam GR Digraph type. 35 /// \tparam C MCapacity map type.36 template <typename GR, typename C M>35 /// \tparam CAP Capacity map type. 36 template <typename GR, typename CAP> 37 37 struct PreflowDefaultTraits { 38 38 … … 44 44 /// The type of the map that stores the arc capacities. 45 45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 46 typedef C MCapacityMap;46 typedef CAP CapacityMap; 47 47 48 48 /// \brief The type of the flow values. … … 95 95 /// 96 96 /// This class provides an implementation of GoldbergTarjan's \e preflow 97 /// \e pushrelabel algorithm producing a flow of maximum value in a 98 /// digraph. The preflow algorithms are the fastest known maximum 97 /// \e pushrelabel algorithm producing a \ref max_flow 98 /// "flow of maximum value" in a digraph. 99 /// The preflow algorithms are the fastest known maximum 99 100 /// flow algorithms. The current implementation use a mixture of the 100 101 /// \e "highest label" and the \e "bound decrease" heuristics. … … 106 107 /// 107 108 /// \tparam GR The type of the digraph the algorithm runs on. 108 /// \tparam C MThe type of the capacity map. The default map109 /// \tparam CAP The type of the capacity map. The default map 109 110 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 110 111 #ifdef DOXYGEN 111 template <typename GR, typename C M, typename TR>112 template <typename GR, typename CAP, typename TR> 112 113 #else 113 114 template <typename GR, 114 typename C M= typename GR::template ArcMap<int>,115 typename TR = PreflowDefaultTraits<GR, C M> >115 typename CAP = typename GR::template ArcMap<int>, 116 typename TR = PreflowDefaultTraits<GR, CAP> > 116 117 #endif 117 118 class Preflow { … … 195 196 ///@{ 196 197 197 template <typename _FlowMap>198 template <typename T> 198 199 struct SetFlowMapTraits : public Traits { 199 typedef _FlowMapFlowMap;200 typedef T FlowMap; 200 201 static FlowMap *createFlowMap(const Digraph&) { 201 202 LEMON_ASSERT(false, "FlowMap is not initialized"); … … 209 210 /// \ref namedtemplparam "Named parameter" for setting FlowMap 210 211 /// type. 211 template <typename _FlowMap>212 template <typename T> 212 213 struct SetFlowMap 213 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits< _FlowMap> > {214 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > { 214 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 220 struct SetElevatorTraits : public Traits { 220 typedef _ElevatorElevator;221 typedef T Elevator; 221 222 static Elevator *createElevator(const Digraph&, int) { 222 223 LEMON_ASSERT(false, "Elevator is not initialized"); … … 234 235 /// \ref run() or \ref init(). 235 236 /// \sa SetStandardElevator 236 template <typename _Elevator>237 template <typename T> 237 238 struct SetElevator 238 : public Preflow<Digraph, CapacityMap, SetElevatorTraits< _Elevator> > {239 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > { 239 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 245 struct SetStandardElevatorTraits : public Traits { 245 typedef _ElevatorElevator;246 typedef T Elevator; 246 247 static Elevator *createElevator(const Digraph& digraph, int max_level) { 247 248 return new Elevator(digraph, max_level); … … 261 262 /// before calling \ref run() or \ref init(). 262 263 /// \sa SetElevator 263 template <typename _Elevator>264 template <typename T> 264 265 struct SetStandardElevator 265 266 : public Preflow<Digraph, CapacityMap, 266 SetStandardElevatorTraits< _Elevator> > {267 SetStandardElevatorTraits<T> > { 267 268 typedef Preflow<Digraph, CapacityMap, 268 SetStandardElevatorTraits< _Elevator> > Create;269 SetStandardElevatorTraits<T> > Create; 269 270 }; 270 271 … … 947 948 /// 948 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 952 /// \pre Either \ref run() or \ref init() must be called before
Note: See TracChangeset
for help on using the changeset viewer.