Improve and fix API doc of EdmondsKarp according to Preflow (#177)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 28 Feb 2013 18:17:53 +0100
changeset 10576a8a688eacf6
parent 1056 92a884824429
child 1058 2f00ef323c2e
Improve and fix API doc of EdmondsKarp according to Preflow (#177)
lemon/edmonds_karp.h
     1.1 --- a/lemon/edmonds_karp.h	Tue Nov 30 20:21:52 2010 +0100
     1.2 +++ b/lemon/edmonds_karp.h	Thu Feb 28 18:17:53 2013 +0100
     1.3 @@ -45,19 +45,24 @@
     1.4      /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
     1.5      typedef CAP CapacityMap;
     1.6  
     1.7 -    /// \brief The type of the length of the arcs.
     1.8 +    /// \brief The type of the flow values.
     1.9      typedef typename CapacityMap::Value Value;
    1.10  
    1.11 -    /// \brief The map type that stores the flow values.
    1.12 +    /// \brief The type of the map that stores the flow values.
    1.13      ///
    1.14 -    /// The map type that stores the flow values. 
    1.15 +    /// The type of the map that stores the flow values.
    1.16      /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.17 +#ifdef DOXYGEN
    1.18 +    typedef GR::ArcMap<Value> FlowMap;
    1.19 +#else
    1.20      typedef typename Digraph::template ArcMap<Value> FlowMap;
    1.21 +#endif
    1.22  
    1.23      /// \brief Instantiates a FlowMap.
    1.24      ///
    1.25      /// This function instantiates a \ref FlowMap. 
    1.26 -    /// \param digraph The digraph, to which we would like to define the flow map.
    1.27 +    /// \param digraph The digraph for which we would like to define
    1.28 +    /// the flow map.
    1.29      static FlowMap* createFlowMap(const Digraph& digraph) {
    1.30        return new FlowMap(digraph);
    1.31      }
    1.32 @@ -74,24 +79,28 @@
    1.33    /// \brief Edmonds-Karp algorithms class.
    1.34    ///
    1.35    /// This class provides an implementation of the \e Edmonds-Karp \e
    1.36 -  /// algorithm producing a flow of maximum value in directed
    1.37 -  /// digraphs. The Edmonds-Karp algorithm is slower than the Preflow
    1.38 -  /// algorithm but it has an advantage of the step-by-step execution
    1.39 +  /// algorithm producing a \ref max_flow "flow of maximum value" in a
    1.40 +  /// digraph \ref clrs01algorithms, \ref amo93networkflows,
    1.41 +  /// \ref edmondskarp72theoretical.
    1.42 +  /// The Edmonds-Karp algorithm is slower than the Preflow
    1.43 +  /// algorithm, but it has an advantage of the step-by-step execution
    1.44    /// control with feasible flow solutions. The \e source node, the \e
    1.45    /// target node, the \e capacity of the arcs and the \e starting \e
    1.46    /// flow value of the arcs should be passed to the algorithm
    1.47    /// through the constructor.
    1.48    ///
    1.49    /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
    1.50 -  /// worst case.  Always try the preflow algorithm instead of this if
    1.51 +  /// worst case. Always try the Preflow algorithm instead of this if
    1.52    /// you just want to compute the optimal flow.
    1.53    ///
    1.54 -  /// \param GR The digraph type the algorithm runs on.
    1.55 -  /// \param CAP The capacity map type.
    1.56 -  /// \param TR Traits class to set various data types used by
    1.57 -  /// the algorithm.  The default traits class is \ref
    1.58 -  /// EdmondsKarpDefaultTraits.  See \ref EdmondsKarpDefaultTraits for the
    1.59 -  /// documentation of a Edmonds-Karp traits class. 
    1.60 +  /// \tparam GR The type of the digraph the algorithm runs on.
    1.61 +  /// \tparam CAP The type of the capacity map. The default map
    1.62 +  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 
    1.63 +  /// \tparam TR The traits class that defines various types used by the
    1.64 +  /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
    1.65 +  /// "EdmondsKarpDefaultTraits<GR, CAP>".
    1.66 +  /// In most cases, this parameter should not be set directly,
    1.67 +  /// consider to use the named template parameters instead.
    1.68  
    1.69  #ifdef DOXYGEN
    1.70    template <typename GR, typename CAP, typename TR>
    1.71 @@ -103,12 +112,18 @@
    1.72    class EdmondsKarp {
    1.73    public:
    1.74  
    1.75 +    /// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm.
    1.76      typedef TR Traits;
    1.77 +    /// The type of the digraph the algorithm runs on.
    1.78      typedef typename Traits::Digraph Digraph;
    1.79 +    /// The type of the capacity map.
    1.80      typedef typename Traits::CapacityMap CapacityMap;
    1.81 +    /// The type of the flow values.
    1.82      typedef typename Traits::Value Value; 
    1.83  
    1.84 +    /// The type of the flow map.
    1.85      typedef typename Traits::FlowMap FlowMap;
    1.86 +    /// The type of the tolerance.
    1.87      typedef typename Traits::Tolerance Tolerance;
    1.88  
    1.89    private:
    1.90 @@ -160,7 +175,7 @@
    1.91      struct DefFlowMapTraits : public Traits {
    1.92        typedef T FlowMap;
    1.93        static FlowMap *createFlowMap(const Digraph&) {
    1.94 -	LEMON_ASSERT(false,"Uninitialized parameter.");
    1.95 +	LEMON_ASSERT(false, "FlowMap is not initialized");
    1.96          return 0;
    1.97        }
    1.98      };
    1.99 @@ -173,11 +188,10 @@
   1.100      template <typename T>
   1.101      struct DefFlowMap 
   1.102        : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
   1.103 -      typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > 
   1.104 +      typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
   1.105        Create;
   1.106      };
   1.107  
   1.108 -
   1.109      /// @}
   1.110  
   1.111    protected:
   1.112 @@ -198,7 +212,8 @@
   1.113        : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
   1.114  	_flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
   1.115      {
   1.116 -      LEMON_ASSERT(_source != _target,"Flow source and target are the same nodes.");
   1.117 +      LEMON_ASSERT(_source != _target,
   1.118 +                   "Flow source and target are the same nodes.");
   1.119      }
   1.120  
   1.121      /// \brief Destructor.
   1.122 @@ -211,7 +226,7 @@
   1.123      /// \brief Sets the capacity map.
   1.124      ///
   1.125      /// Sets the capacity map.
   1.126 -    /// \return \c (*this)
   1.127 +    /// \return <tt>(*this)</tt>
   1.128      EdmondsKarp& capacityMap(const CapacityMap& map) {
   1.129        _capacity = &map;
   1.130        return *this;
   1.131 @@ -220,7 +235,11 @@
   1.132      /// \brief Sets the flow map.
   1.133      ///
   1.134      /// Sets the flow map.
   1.135 -    /// \return \c (*this)
   1.136 +    /// If you don't use this function before calling \ref run() or
   1.137 +    /// \ref init(), an instance will be allocated automatically.
   1.138 +    /// The destructor deallocates this automatically allocated map,
   1.139 +    /// of course.
   1.140 +    /// \return <tt>(*this)</tt>
   1.141      EdmondsKarp& flowMap(FlowMap& map) {
   1.142        if (_local_flow) {
   1.143  	delete _flow;
   1.144 @@ -230,17 +249,10 @@
   1.145        return *this;
   1.146      }
   1.147  
   1.148 -    /// \brief Returns the flow map.
   1.149 -    ///
   1.150 -    /// \return The flow map.
   1.151 -    const FlowMap& flowMap() const {
   1.152 -      return *_flow;
   1.153 -    }
   1.154 -
   1.155      /// \brief Sets the source node.
   1.156      ///
   1.157      /// Sets the source node.
   1.158 -    /// \return \c (*this)
   1.159 +    /// \return <tt>(*this)</tt>
   1.160      EdmondsKarp& source(const Node& node) {
   1.161        _source = node;
   1.162        return *this;
   1.163 @@ -249,7 +261,7 @@
   1.164      /// \brief Sets the target node.
   1.165      ///
   1.166      /// Sets the target node.
   1.167 -    /// \return \c (*this)
   1.168 +    /// \return <tt>(*this)</tt>
   1.169      EdmondsKarp& target(const Node& node) {
   1.170        _target = node;
   1.171        return *this;
   1.172 @@ -258,31 +270,32 @@
   1.173      /// \brief Sets the tolerance used by algorithm.
   1.174      ///
   1.175      /// Sets the tolerance used by algorithm.
   1.176 +    /// \return <tt>(*this)</tt>
   1.177      EdmondsKarp& tolerance(const Tolerance& tolerance) {
   1.178        _tolerance = tolerance;
   1.179        return *this;
   1.180      } 
   1.181  
   1.182 -    /// \brief Returns the tolerance used by algorithm.
   1.183 +    /// \brief Returns a const reference to the tolerance.
   1.184      ///
   1.185 -    /// Returns the tolerance used by algorithm.
   1.186 +    /// Returns a const reference to the tolerance object used by
   1.187 +    /// the algorithm.
   1.188      const Tolerance& tolerance() const {
   1.189        return _tolerance;
   1.190      } 
   1.191  
   1.192      /// \name Execution control
   1.193 -    /// The simplest way to execute the
   1.194 -    /// algorithm is to use the \c run() member functions.
   1.195 -    /// \n
   1.196 -    /// If you need more control on initial solution or
   1.197 -    /// execution then you have to call one \ref init() function and then
   1.198 -    /// the start() or multiple times the \c augment() member function.  
   1.199 +    /// The simplest way to execute the algorithm is to use \ref run().\n
   1.200 +    /// If you need better control on the initial solution or the execution,
   1.201 +    /// you have to call one of the \ref init() functions first, then
   1.202 +    /// \ref start() or multiple times the \ref augment() function.
   1.203      
   1.204      ///@{
   1.205  
   1.206 -    /// \brief Initializes the algorithm
   1.207 -    /// 
   1.208 -    /// Sets the flow to empty flow.
   1.209 +    /// \brief Initializes the algorithm.
   1.210 +    ///
   1.211 +    /// Initializes the internal data structures and sets the initial
   1.212 +    /// flow to zero on each arc.
   1.213      void init() {
   1.214        createStructures();
   1.215        for (ArcIt it(_graph); it != INVALID; ++it) {
   1.216 @@ -291,11 +304,12 @@
   1.217        _flow_value = 0;
   1.218      }
   1.219      
   1.220 -    /// \brief Initializes the algorithm
   1.221 -    /// 
   1.222 -    /// Initializes the flow to the \c flowMap. The \c flowMap should
   1.223 -    /// contain a feasible flow, ie. in each node excluding the source
   1.224 -    /// and the target the incoming flow should be equal to the
   1.225 +    /// \brief Initializes the algorithm using the given flow map.
   1.226 +    ///
   1.227 +    /// Initializes the internal data structures and sets the initial
   1.228 +    /// flow to the given \c flowMap. The \c flowMap should
   1.229 +    /// contain a feasible flow, i.e. at each node excluding the source
   1.230 +    /// and the target, the incoming flow should be equal to the
   1.231      /// outgoing flow.
   1.232      template <typename FlowMap>
   1.233      void flowInit(const FlowMap& flowMap) {
   1.234 @@ -312,13 +326,14 @@
   1.235        }
   1.236      }
   1.237  
   1.238 -    /// \brief Initializes the algorithm
   1.239 -    /// 
   1.240 -    /// Initializes the flow to the \c flowMap. The \c flowMap should
   1.241 -    /// contain a feasible flow, ie. in each node excluding the source
   1.242 -    /// and the target the incoming flow should be equal to the
   1.243 -    /// outgoing flow.  
   1.244 -    /// \return %False when the given flowMap does not contain
   1.245 +    /// \brief Initializes the algorithm using the given flow map.
   1.246 +    ///
   1.247 +    /// Initializes the internal data structures and sets the initial
   1.248 +    /// flow to the given \c flowMap. The \c flowMap should
   1.249 +    /// contain a feasible flow, i.e. at each node excluding the source
   1.250 +    /// and the target, the incoming flow should be equal to the
   1.251 +    /// outgoing flow. 
   1.252 +    /// \return \c false when the given \c flowMap does not contain a
   1.253      /// feasible flow.
   1.254      template <typename FlowMap>
   1.255      bool checkedFlowInit(const FlowMap& flowMap) {
   1.256 @@ -354,15 +369,15 @@
   1.257        return true;
   1.258      }
   1.259  
   1.260 -    /// \brief Augment the solution on an arc shortest path.
   1.261 +    /// \brief Augments the solution along a shortest path.
   1.262      /// 
   1.263 -    /// Augment the solution on an arc shortest path. It searches an
   1.264 -    /// arc shortest path between the source and the target
   1.265 -    /// in the residual digraph by the bfs algoritm.
   1.266 +    /// Augments the solution along a shortest path. This function searches a
   1.267 +    /// shortest path between the source and the target
   1.268 +    /// in the residual digraph by the Bfs algoritm.
   1.269      /// Then it increases the flow on this path with the minimal residual
   1.270 -    /// capacity on the path. If there is no such path it gives back
   1.271 +    /// capacity on the path. If there is no such path, it gives back
   1.272      /// false.
   1.273 -    /// \return %False when the augmenting didn't success so the
   1.274 +    /// \return \c false when the augmenting did not success, i.e. the
   1.275      /// current flow is a feasible and optimal solution.
   1.276      bool augment() {
   1.277        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.278 @@ -439,15 +454,18 @@
   1.279  
   1.280      /// \brief Executes the algorithm
   1.281      ///
   1.282 -    /// It runs augmenting phases until the optimal solution is reached. 
   1.283 +    /// Executes the algorithm by performing augmenting phases until the
   1.284 +    /// optimal solution is reached. 
   1.285 +    /// \pre One of the \ref init() functions must be called before
   1.286 +    /// using this function.
   1.287      void start() {
   1.288        while (augment()) {}
   1.289      }
   1.290  
   1.291      /// \brief Runs the algorithm.
   1.292      /// 
   1.293 -    /// It is just a shorthand for:
   1.294 -    ///
   1.295 +    /// Runs the Edmonds-Karp algorithm.
   1.296 +    /// \note ek.run() is just a shortcut of the following code.
   1.297      ///\code 
   1.298      /// ek.init();
   1.299      /// ek.start();
   1.300 @@ -462,42 +480,63 @@
   1.301      /// \name Query Functions
   1.302      /// The result of the Edmonds-Karp algorithm can be obtained using these
   1.303      /// functions.\n
   1.304 -    /// Before the use of these functions,
   1.305 -    /// either run() or start() must be called.
   1.306 +    /// Either \ref run() or \ref start() should be called before using them.
   1.307      
   1.308      ///@{
   1.309  
   1.310      /// \brief Returns the value of the maximum flow.
   1.311      ///
   1.312 -    /// Returns the value of the maximum flow by returning the excess
   1.313 -    /// of the target node \c t.
   1.314 -
   1.315 +    /// Returns the value of the maximum flow found by the algorithm.
   1.316 +    ///
   1.317 +    /// \pre Either \ref run() or \ref init() must be called before
   1.318 +    /// using this function.
   1.319      Value flowValue() const {
   1.320        return _flow_value;
   1.321      }
   1.322  
   1.323 -
   1.324 -    /// \brief Returns the flow on the arc.
   1.325 +    /// \brief Returns the flow value on the given arc.
   1.326      ///
   1.327 -    /// Sets the \c flowMap to the flow on the arcs.
   1.328 +    /// Returns the flow value on the given arc.
   1.329 +    ///
   1.330 +    /// \pre Either \ref run() or \ref init() must be called before
   1.331 +    /// using this function.
   1.332      Value flow(const Arc& arc) const {
   1.333        return (*_flow)[arc];
   1.334      }
   1.335  
   1.336 -    /// \brief Returns true when the node is on the source side of minimum cut.
   1.337 +    /// \brief Returns a const reference to the flow map.
   1.338      ///
   1.339 +    /// Returns a const reference to the arc map storing the found flow.
   1.340 +    ///
   1.341 +    /// \pre Either \ref run() or \ref init() must be called before
   1.342 +    /// using this function.
   1.343 +    const FlowMap& flowMap() const {
   1.344 +      return *_flow;
   1.345 +    }
   1.346  
   1.347 -    /// Returns true when the node is on the source side of minimum
   1.348 -    /// cut.
   1.349 -
   1.350 +    /// \brief Returns \c true when the node is on the source side of the
   1.351 +    /// minimum cut.
   1.352 +    ///
   1.353 +    /// Returns true when the node is on the source side of the found
   1.354 +    /// minimum cut.
   1.355 +    ///
   1.356 +    /// \pre Either \ref run() or \ref init() must be called before
   1.357 +    /// using this function.
   1.358      bool minCut(const Node& node) const {
   1.359        return ((*_pred)[node] != INVALID) or node == _source;
   1.360      }
   1.361  
   1.362 -    /// \brief Returns a minimum value cut.
   1.363 +    /// \brief Gives back a minimum value cut.
   1.364      ///
   1.365 -    /// Sets \c cutMap to the characteristic vector of a minimum value cut.
   1.366 -
   1.367 +    /// Sets \c cutMap to the characteristic vector of a minimum value
   1.368 +    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
   1.369 +    /// node map with \c bool (or convertible) value type.
   1.370 +    ///
   1.371 +    /// \note This function calls \ref minCut() for each node, so it runs in
   1.372 +    /// O(n) time.
   1.373 +    ///
   1.374 +    /// \pre Either \ref run() or \ref init() must be called before
   1.375 +    /// using this function.
   1.376      template <typename CutMap>
   1.377      void minCutMap(CutMap& cutMap) const {
   1.378        for (NodeIt n(_graph); n != INVALID; ++n) {