lemon/preflow.h
changeset 408 37054b67d807
parent 407 db3251947eba
child 437 6a2a33ad261b
     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 = &map;
   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  }