1.1 --- a/lemon/preflow.h Sun Nov 30 00:48:07 2008 +0100
1.2 +++ b/lemon/preflow.h Sun Nov 30 00:50:31 2008 +0100
1.3 @@ -31,13 +31,13 @@
1.4 /// \brief Default traits class of Preflow class.
1.5 ///
1.6 /// Default traits class of Preflow class.
1.7 - /// \param _Graph Digraph type.
1.8 - /// \param _CapacityMap Type of capacity map.
1.9 - template <typename _Graph, typename _CapacityMap>
1.10 + /// \tparam _Digraph Digraph type.
1.11 + /// \tparam _CapacityMap Capacity map type.
1.12 + template <typename _Digraph, typename _CapacityMap>
1.13 struct PreflowDefaultTraits {
1.14
1.15 - /// \brief The digraph type the algorithm runs on.
1.16 - typedef _Graph Digraph;
1.17 + /// \brief The type of the digraph the algorithm runs on.
1.18 + typedef _Digraph Digraph;
1.19
1.20 /// \brief The type of the map that stores the arc capacities.
1.21 ///
1.22 @@ -45,12 +45,12 @@
1.23 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.24 typedef _CapacityMap CapacityMap;
1.25
1.26 - /// \brief The type of the length of the arcs.
1.27 + /// \brief The type of the flow values.
1.28 typedef typename CapacityMap::Value Value;
1.29
1.30 - /// \brief The map type that stores the flow values.
1.31 + /// \brief The type of the map that stores the flow values.
1.32 ///
1.33 - /// The map type that stores the flow values.
1.34 + /// The type of the map that stores the flow values.
1.35 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.36 typedef typename Digraph::template ArcMap<Value> FlowMap;
1.37
1.38 @@ -63,7 +63,7 @@
1.39 return new FlowMap(digraph);
1.40 }
1.41
1.42 - /// \brief The eleavator type used by Preflow algorithm.
1.43 + /// \brief The elevator type used by Preflow algorithm.
1.44 ///
1.45 /// The elevator type used by Preflow algorithm.
1.46 ///
1.47 @@ -73,7 +73,7 @@
1.48
1.49 /// \brief Instantiates an Elevator.
1.50 ///
1.51 - /// This function instantiates a \ref Elevator.
1.52 + /// This function instantiates an \ref Elevator.
1.53 /// \param digraph The digraph, to which we would like to define
1.54 /// the elevator.
1.55 /// \param max_level The maximum level of the elevator.
1.56 @@ -91,44 +91,46 @@
1.57
1.58 /// \ingroup max_flow
1.59 ///
1.60 - /// \brief %Preflow algorithms class.
1.61 + /// \brief %Preflow algorithm class.
1.62 ///
1.63 - /// This class provides an implementation of the Goldberg's \e
1.64 - /// preflow \e algorithm producing a flow of maximum value in a
1.65 - /// digraph. The preflow algorithms are the fastest known max
1.66 + /// This class provides an implementation of Goldberg-Tarjan's \e preflow
1.67 + /// \e push-relabel algorithm producing a flow of maximum value in a
1.68 + /// digraph. The preflow algorithms are the fastest known maximum
1.69 /// flow algorithms. The current implementation use a mixture of the
1.70 /// \e "highest label" and the \e "bound decrease" heuristics.
1.71 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
1.72 ///
1.73 - /// The algorithm consists from two phases. After the first phase
1.74 - /// the maximal flow value and the minimum cut can be obtained. The
1.75 - /// second phase constructs the feasible maximum flow on each arc.
1.76 + /// The algorithm consists of two phases. After the first phase
1.77 + /// the maximum flow value and the minimum cut is obtained. The
1.78 + /// second phase constructs a feasible maximum flow on each arc.
1.79 ///
1.80 - /// \param _Graph The digraph type the algorithm runs on.
1.81 - /// \param _CapacityMap The flow map type.
1.82 - /// \param _Traits Traits class to set various data types used by
1.83 - /// the algorithm. The default traits class is \ref
1.84 - /// PreflowDefaultTraits. See \ref PreflowDefaultTraits for the
1.85 - /// documentation of a %Preflow traits class.
1.86 - ///
1.87 - ///\author Jacint Szabo and Balazs Dezso
1.88 + /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.89 + /// \tparam _CapacityMap The type of the capacity map. The default map
1.90 + /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
1.91 #ifdef DOXYGEN
1.92 - template <typename _Graph, typename _CapacityMap, typename _Traits>
1.93 + template <typename _Digraph, typename _CapacityMap, typename _Traits>
1.94 #else
1.95 - template <typename _Graph,
1.96 - typename _CapacityMap = typename _Graph::template ArcMap<int>,
1.97 - typename _Traits = PreflowDefaultTraits<_Graph, _CapacityMap> >
1.98 + template <typename _Digraph,
1.99 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.100 + typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
1.101 #endif
1.102 class Preflow {
1.103 public:
1.104
1.105 + ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
1.106 typedef _Traits Traits;
1.107 + ///The type of the digraph the algorithm runs on.
1.108 typedef typename Traits::Digraph Digraph;
1.109 + ///The type of the capacity map.
1.110 typedef typename Traits::CapacityMap CapacityMap;
1.111 + ///The type of the flow values.
1.112 typedef typename Traits::Value Value;
1.113
1.114 + ///The type of the flow map.
1.115 typedef typename Traits::FlowMap FlowMap;
1.116 + ///The type of the elevator.
1.117 typedef typename Traits::Elevator Elevator;
1.118 + ///The type of the tolerance.
1.119 typedef typename Traits::Tolerance Tolerance;
1.120
1.121 private:
1.122 @@ -188,7 +190,7 @@
1.123
1.124 typedef Preflow Create;
1.125
1.126 - ///\name Named template parameters
1.127 + ///\name Named Template Parameters
1.128
1.129 ///@{
1.130
1.131 @@ -205,7 +207,7 @@
1.132 /// FlowMap type
1.133 ///
1.134 /// \ref named-templ-param "Named parameter" for setting FlowMap
1.135 - /// type
1.136 + /// type.
1.137 template <typename _FlowMap>
1.138 struct SetFlowMap
1.139 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
1.140 @@ -226,7 +228,11 @@
1.141 /// Elevator type
1.142 ///
1.143 /// \ref named-templ-param "Named parameter" for setting Elevator
1.144 - /// type
1.145 + /// type. If this named parameter is used, then an external
1.146 + /// elevator object must be passed to the algorithm using the
1.147 + /// \ref elevator(Elevator&) "elevator()" function before calling
1.148 + /// \ref run() or \ref init().
1.149 + /// \sa SetStandardElevator
1.150 template <typename _Elevator>
1.151 struct SetElevator
1.152 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
1.153 @@ -243,11 +249,17 @@
1.154 };
1.155
1.156 /// \brief \ref named-templ-param "Named parameter" for setting
1.157 - /// Elevator type
1.158 + /// Elevator type with automatic allocation
1.159 ///
1.160 /// \ref named-templ-param "Named parameter" for setting Elevator
1.161 - /// type. The Elevator should be standard constructor interface, ie.
1.162 - /// the digraph and the maximum level should be passed to it.
1.163 + /// type with automatic allocation.
1.164 + /// The Elevator should have standard constructor interface to be
1.165 + /// able to automatically created by the algorithm (i.e. the
1.166 + /// digraph and the maximum level should be passed to it).
1.167 + /// However an external elevator object could also be passed to the
1.168 + /// algorithm with the \ref elevator(Elevator&) "elevator()" function
1.169 + /// before calling \ref run() or \ref init().
1.170 + /// \sa SetElevator
1.171 template <typename _Elevator>
1.172 struct SetStandardElevator
1.173 : public Preflow<Digraph, CapacityMap,
1.174 @@ -273,14 +285,14 @@
1.175 /// \param source The source node.
1.176 /// \param target The target node.
1.177 Preflow(const Digraph& digraph, const CapacityMap& capacity,
1.178 - Node source, Node target)
1.179 + Node source, Node target)
1.180 : _graph(digraph), _capacity(&capacity),
1.181 _node_num(0), _source(source), _target(target),
1.182 _flow(0), _local_flow(false),
1.183 _level(0), _local_level(false),
1.184 _excess(0), _tolerance(), _phase() {}
1.185
1.186 - /// \brief Destrcutor.
1.187 + /// \brief Destructor.
1.188 ///
1.189 /// Destructor.
1.190 ~Preflow() {
1.191 @@ -290,7 +302,7 @@
1.192 /// \brief Sets the capacity map.
1.193 ///
1.194 /// Sets the capacity map.
1.195 - /// \return \c (*this)
1.196 + /// \return <tt>(*this)</tt>
1.197 Preflow& capacityMap(const CapacityMap& map) {
1.198 _capacity = ↦
1.199 return *this;
1.200 @@ -299,7 +311,11 @@
1.201 /// \brief Sets the flow map.
1.202 ///
1.203 /// Sets the flow map.
1.204 - /// \return \c (*this)
1.205 + /// If you don't use this function before calling \ref run() or
1.206 + /// \ref init(), an instance will be allocated automatically.
1.207 + /// The destructor deallocates this automatically allocated map,
1.208 + /// of course.
1.209 + /// \return <tt>(*this)</tt>
1.210 Preflow& flowMap(FlowMap& map) {
1.211 if (_local_flow) {
1.212 delete _flow;
1.213 @@ -309,17 +325,32 @@
1.214 return *this;
1.215 }
1.216
1.217 - /// \brief Returns the flow map.
1.218 + /// \brief Sets the source node.
1.219 ///
1.220 - /// \return The flow map.
1.221 - const FlowMap& flowMap() {
1.222 - return *_flow;
1.223 + /// Sets the source node.
1.224 + /// \return <tt>(*this)</tt>
1.225 + Preflow& source(const Node& node) {
1.226 + _source = node;
1.227 + return *this;
1.228 }
1.229
1.230 - /// \brief Sets the elevator.
1.231 + /// \brief Sets the target node.
1.232 ///
1.233 - /// Sets the elevator.
1.234 - /// \return \c (*this)
1.235 + /// Sets the target node.
1.236 + /// \return <tt>(*this)</tt>
1.237 + Preflow& target(const Node& node) {
1.238 + _target = node;
1.239 + return *this;
1.240 + }
1.241 +
1.242 + /// \brief Sets the elevator used by algorithm.
1.243 + ///
1.244 + /// Sets the elevator used by algorithm.
1.245 + /// If you don't use this function before calling \ref run() or
1.246 + /// \ref init(), an instance will be allocated automatically.
1.247 + /// The destructor deallocates this automatically allocated elevator,
1.248 + /// of course.
1.249 + /// \return <tt>(*this)</tt>
1.250 Preflow& elevator(Elevator& elevator) {
1.251 if (_local_level) {
1.252 delete _level;
1.253 @@ -329,31 +360,16 @@
1.254 return *this;
1.255 }
1.256
1.257 - /// \brief Returns the elevator.
1.258 + /// \brief Returns a const reference to the elevator.
1.259 ///
1.260 - /// \return The elevator.
1.261 + /// Returns a const reference to the elevator.
1.262 + ///
1.263 + /// \pre Either \ref run() or \ref init() must be called before
1.264 + /// using this function.
1.265 const Elevator& elevator() {
1.266 return *_level;
1.267 }
1.268
1.269 - /// \brief Sets the source node.
1.270 - ///
1.271 - /// Sets the source node.
1.272 - /// \return \c (*this)
1.273 - Preflow& source(const Node& node) {
1.274 - _source = node;
1.275 - return *this;
1.276 - }
1.277 -
1.278 - /// \brief Sets the target node.
1.279 - ///
1.280 - /// Sets the target node.
1.281 - /// \return \c (*this)
1.282 - Preflow& target(const Node& node) {
1.283 - _target = node;
1.284 - return *this;
1.285 - }
1.286 -
1.287 /// \brief Sets the tolerance used by algorithm.
1.288 ///
1.289 /// Sets the tolerance used by algorithm.
1.290 @@ -362,27 +378,26 @@
1.291 return *this;
1.292 }
1.293
1.294 - /// \brief Returns the tolerance used by algorithm.
1.295 + /// \brief Returns a const reference to the tolerance.
1.296 ///
1.297 - /// Returns the tolerance used by algorithm.
1.298 + /// Returns a const reference to the tolerance.
1.299 const Tolerance& tolerance() const {
1.300 return tolerance;
1.301 }
1.302
1.303 - /// \name Execution control The simplest way to execute the
1.304 - /// algorithm is to use one of the member functions called \c
1.305 - /// run().
1.306 - /// \n
1.307 - /// If you need more control on initial solution or
1.308 - /// execution then you have to call one \ref init() function and then
1.309 - /// the startFirstPhase() and if you need the startSecondPhase().
1.310 + /// \name Execution Control
1.311 + /// The simplest way to execute the preflow algorithm is to use
1.312 + /// \ref run() or \ref runMinCut().\n
1.313 + /// If you need more control on the initial solution or the execution,
1.314 + /// first you have to call one of the \ref init() functions, then
1.315 + /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
1.316
1.317 ///@{
1.318
1.319 /// \brief Initializes the internal data structures.
1.320 ///
1.321 - /// Initializes the internal data structures.
1.322 - ///
1.323 + /// Initializes the internal data structures and sets the initial
1.324 + /// flow to zero on each arc.
1.325 void init() {
1.326 createStructures();
1.327
1.328 @@ -436,14 +451,15 @@
1.329 }
1.330 }
1.331
1.332 - /// \brief Initializes the internal data structures.
1.333 + /// \brief Initializes the internal data structures using the
1.334 + /// given flow map.
1.335 ///
1.336 /// Initializes the internal data structures and sets the initial
1.337 /// flow to the given \c flowMap. The \c flowMap should contain a
1.338 - /// flow or at least a preflow, ie. in each node excluding the
1.339 - /// target the incoming flow should greater or equal to the
1.340 + /// flow or at least a preflow, i.e. at each node excluding the
1.341 + /// source node the incoming flow should greater or equal to the
1.342 /// outgoing flow.
1.343 - /// \return %False when the given \c flowMap is not a preflow.
1.344 + /// \return \c false if the given \c flowMap is not a preflow.
1.345 template <typename FlowMap>
1.346 bool init(const FlowMap& flowMap) {
1.347 createStructures();
1.348 @@ -536,7 +552,8 @@
1.349 /// maximum flow is not yet obtained. So after calling this method
1.350 /// \ref flowValue() returns the value of a maximum flow and \ref
1.351 /// minCut() returns a minimum cut.
1.352 - /// \pre One of the \ref init() functions should be called.
1.353 + /// \pre One of the \ref init() functions must be called before
1.354 + /// using this function.
1.355 void startFirstPhase() {
1.356 _phase = true;
1.357
1.358 @@ -702,12 +719,12 @@
1.359 /// \brief Starts the second phase of the preflow algorithm.
1.360 ///
1.361 /// The preflow algorithm consists of two phases, this method runs
1.362 - /// the second phase. After calling \ref init() and \ref
1.363 - /// startFirstPhase() and then \ref startSecondPhase(), \ref
1.364 - /// flowMap() return a maximum flow, \ref flowValue() returns the
1.365 + /// the second phase. After calling one of the \ref init() functions
1.366 + /// and \ref startFirstPhase() and then \ref startSecondPhase(),
1.367 + /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
1.368 /// value of a maximum flow, \ref minCut() returns a minimum cut
1.369 - /// \pre The \ref init() and startFirstPhase() functions should be
1.370 - /// called before.
1.371 + /// \pre One of the \ref init() functions and \ref startFirstPhase()
1.372 + /// must be called before using this function.
1.373 void startSecondPhase() {
1.374 _phase = false;
1.375
1.376 @@ -863,38 +880,76 @@
1.377 /// @}
1.378
1.379 /// \name Query Functions
1.380 - /// The result of the %Preflow algorithm can be obtained using these
1.381 + /// The results of the preflow algorithm can be obtained using these
1.382 /// functions.\n
1.383 - /// Before the use of these functions,
1.384 - /// either run() or start() must be called.
1.385 + /// Either one of the \ref run() "run*()" functions or one of the
1.386 + /// \ref startFirstPhase() "start*()" functions should be called
1.387 + /// before using them.
1.388
1.389 ///@{
1.390
1.391 /// \brief Returns the value of the maximum flow.
1.392 ///
1.393 /// Returns the value of the maximum flow by returning the excess
1.394 - /// of the target node \c t. This value equals to the value of
1.395 - /// the maximum flow already after the first phase.
1.396 + /// of the target node. This value equals to the value of
1.397 + /// the maximum flow already after the first phase of the algorithm.
1.398 + ///
1.399 + /// \pre Either \ref run() or \ref init() must be called before
1.400 + /// using this function.
1.401 Value flowValue() const {
1.402 return (*_excess)[_target];
1.403 }
1.404
1.405 - /// \brief Returns true when the node is on the source side of minimum cut.
1.406 + /// \brief Returns the flow on the given arc.
1.407 ///
1.408 - /// Returns true when the node is on the source side of minimum
1.409 - /// cut. This method can be called both after running \ref
1.410 + /// Returns the flow on the given arc. This method can
1.411 + /// be called after the second phase of the algorithm.
1.412 + ///
1.413 + /// \pre Either \ref run() or \ref init() must be called before
1.414 + /// using this function.
1.415 + Value flow(const Arc& arc) const {
1.416 + return (*_flow)[arc];
1.417 + }
1.418 +
1.419 + /// \brief Returns a const reference to the flow map.
1.420 + ///
1.421 + /// Returns a const reference to the arc map storing the found flow.
1.422 + /// This method can be called after the second phase of the algorithm.
1.423 + ///
1.424 + /// \pre Either \ref run() or \ref init() must be called before
1.425 + /// using this function.
1.426 + const FlowMap& flowMap() {
1.427 + return *_flow;
1.428 + }
1.429 +
1.430 + /// \brief Returns \c true when the node is on the source side of the
1.431 + /// minimum cut.
1.432 + ///
1.433 + /// Returns true when the node is on the source side of the found
1.434 + /// minimum cut. This method can be called both after running \ref
1.435 /// startFirstPhase() and \ref startSecondPhase().
1.436 + ///
1.437 + /// \pre Either \ref run() or \ref init() must be called before
1.438 + /// using this function.
1.439 bool minCut(const Node& node) const {
1.440 return ((*_level)[node] == _level->maxLevel()) == _phase;
1.441 }
1.442
1.443 - /// \brief Returns a minimum value cut.
1.444 + /// \brief Gives back a minimum value cut.
1.445 ///
1.446 - /// Sets the \c cutMap to the characteristic vector of a minimum value
1.447 - /// cut. This method can be called both after running \ref
1.448 - /// startFirstPhase() and \ref startSecondPhase(). The result after second
1.449 - /// phase could be changed slightly if inexact computation is used.
1.450 - /// \pre The \c cutMap should be a bool-valued node-map.
1.451 + /// Sets \c cutMap to the characteristic vector of a minimum value
1.452 + /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
1.453 + /// node map with \c bool (or convertible) value type.
1.454 + ///
1.455 + /// This method can be called both after running \ref startFirstPhase()
1.456 + /// and \ref startSecondPhase(). The result after the second phase
1.457 + /// could be slightly different if inexact computation is used.
1.458 + ///
1.459 + /// \note This function calls \ref minCut() for each node, so it runs in
1.460 + /// \f$O(n)\f$ time.
1.461 + ///
1.462 + /// \pre Either \ref run() or \ref init() must be called before
1.463 + /// using this function.
1.464 template <typename CutMap>
1.465 void minCutMap(CutMap& cutMap) const {
1.466 for (NodeIt n(_graph); n != INVALID; ++n) {
1.467 @@ -902,14 +957,6 @@
1.468 }
1.469 }
1.470
1.471 - /// \brief Returns the flow on the arc.
1.472 - ///
1.473 - /// Sets the \c flowMap to the flow on the arcs. This method can
1.474 - /// be called after the second phase of algorithm.
1.475 - Value flow(const Arc& arc) const {
1.476 - return (*_flow)[arc];
1.477 - }
1.478 -
1.479 /// @}
1.480 };
1.481 }