Changeset 1057:6a8a688eacf6 in lemon-main for lemon

Timestamp:

02/28/13 18:17:53 (11 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improve and fix API doc of EdmondsKarp? according to Preflow (#177)

File:

• lemon/edmonds_karp.h (modified) (21 diffs)

lemon/edmonds_karp.h

@@ -46 +46 @@
     typedef CAP CapacityMap;
 
-    /// \brief The type of the length of the arcs.
+    /// \brief The type of the flow values.
     typedef typename CapacityMap::Value Value;
 
-    /// \brief The map type that stores the flow values.
-    ///
-    /// The map type that stores the flow values. 
+    /// \brief The type of the map that stores the flow values.
+    ///
+    /// The type of the map that stores the flow values.
     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+#ifdef DOXYGEN
+    typedef GR::ArcMap<Value> FlowMap;
+#else
     typedef typename Digraph::template ArcMap<Value> FlowMap;
+#endif
 
     /// \brief Instantiates a FlowMap.
     ///
     /// This function instantiates a \ref FlowMap. 
-    /// \param digraph The digraph, to which we would like to define the flow map.
+    /// \param digraph The digraph for which we would like to define
+    /// the flow map.
     static FlowMap* createFlowMap(const Digraph& digraph) {
       return new FlowMap(digraph);
@@ -75 +80 @@
   ///
   /// This class provides an implementation of the \e Edmonds-Karp \e
-  /// algorithm producing a flow of maximum value in directed
-  /// digraphs. The Edmonds-Karp algorithm is slower than the Preflow
-  /// algorithm but it has an advantage of the step-by-step execution
+  /// algorithm producing a \ref max_flow "flow of maximum value" in a
+  /// digraph \ref clrs01algorithms, \ref amo93networkflows,
+  /// \ref edmondskarp72theoretical.
+  /// The Edmonds-Karp algorithm is slower than the Preflow
+  /// algorithm, but it has an advantage of the step-by-step execution
   /// control with feasible flow solutions. The \e source node, the \e
   /// target node, the \e capacity of the arcs and the \e starting \e
@@ -84 +91 @@
   ///
   /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
-  /// worst case.  Always try the preflow algorithm instead of this if
+  /// worst case. Always try the Preflow algorithm instead of this if
   /// you just want to compute the optimal flow.
   ///
-  /// \param GR The digraph type the algorithm runs on.
-  /// \param CAP The capacity map type.
-  /// \param TR Traits class to set various data types used by
-  /// the algorithm.  The default traits class is \ref
-  /// EdmondsKarpDefaultTraits.  See \ref EdmondsKarpDefaultTraits for the
-  /// documentation of a Edmonds-Karp traits class. 
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// \tparam CAP The type of the capacity map. The default map
+  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
+  /// "EdmondsKarpDefaultTraits<GR, CAP>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 
 #ifdef DOXYGEN
@@ -104 +113 @@
   public:
 
+    /// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm.
     typedef TR Traits;
+    /// The type of the digraph the algorithm runs on.
     typedef typename Traits::Digraph Digraph;
+    /// The type of the capacity map.
     typedef typename Traits::CapacityMap CapacityMap;
+    /// The type of the flow values.
     typedef typename Traits::Value Value; 
 
+    /// The type of the flow map.
     typedef typename Traits::FlowMap FlowMap;
+    /// The type of the tolerance.
     typedef typename Traits::Tolerance Tolerance;
 
@@ -161 +176 @@
       typedef T FlowMap;
       static FlowMap *createFlowMap(const Digraph&) {
-        LEMON_ASSERT(false,"Uninitialized parameter.");
+        LEMON_ASSERT(false, "FlowMap is not initialized");
         return 0;
       }
@@ -174 +189 @@
     struct DefFlowMap 
       : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
-      typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > 
+      typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
       Create;
     };
-
 
     /// @}
@@ -199 +213 @@
         _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
     {
-      LEMON_ASSERT(_source != _target,"Flow source and target are the same nodes.");
+      LEMON_ASSERT(_source != _target,
+                   "Flow source and target are the same nodes.");
     }
 
@@ -212 +227 @@
     ///
     /// Sets the capacity map.
-    /// \return \c (*this)
+    /// \return <tt>(*this)</tt>
     EdmondsKarp& capacityMap(const CapacityMap& map) {
       _capacity = &map;
@@ -221 +236 @@
     ///
     /// Sets the flow map.
-    /// \return \c (*this)
+    /// If you don't use this function before calling \ref run() or
+    /// \ref init(), an instance will be allocated automatically.
+    /// The destructor deallocates this automatically allocated map,
+    /// of course.
+    /// \return <tt>(*this)</tt>
     EdmondsKarp& flowMap(FlowMap& map) {
       if (_local_flow) {
@@ -231 +250 @@
     }
 
-    /// \brief Returns the flow map.
-    ///
-    /// \return The flow map.
-    const FlowMap& flowMap() const {
-      return *_flow;
-    }
-
     /// \brief Sets the source node.
     ///
     /// Sets the source node.
-    /// \return \c (*this)
+    /// \return <tt>(*this)</tt>
     EdmondsKarp& source(const Node& node) {
       _source = node;
@@ -250 +262 @@
     ///
     /// Sets the target node.
-    /// \return \c (*this)
+    /// \return <tt>(*this)</tt>
     EdmondsKarp& target(const Node& node) {
       _target = node;
@@ -259 +271 @@
     ///
     /// Sets the tolerance used by algorithm.
+    /// \return <tt>(*this)</tt>
     EdmondsKarp& tolerance(const Tolerance& tolerance) {
       _tolerance = tolerance;
@@ -264 +277 @@
     } 
 
-    /// \brief Returns the tolerance used by algorithm.
-    ///
-    /// Returns the tolerance used by algorithm.
+    /// \brief Returns a const reference to the tolerance.
+    ///
+    /// Returns a const reference to the tolerance object used by
+    /// the algorithm.
     const Tolerance& tolerance() const {
       return _tolerance;
@@ -272 +286 @@
 
     /// \name Execution control
-    /// The simplest way to execute the
-    /// algorithm is to use the \c run() member functions.
-    /// \n
-    /// If you need more control on initial solution or
-    /// execution then you have to call one \ref init() function and then
-    /// the start() or multiple times the \c augment() member function.  
+    /// The simplest way to execute the algorithm is to use \ref run().\n
+    /// If you need better control on the initial solution or the execution,
+    /// you have to call one of the \ref init() functions first, then
+    /// \ref start() or multiple times the \ref augment() function.
     
     ///@{
 
-    /// \brief Initializes the algorithm
-    /// 
-    /// Sets the flow to empty flow.
+    /// \brief Initializes the algorithm.
+    ///
+    /// Initializes the internal data structures and sets the initial
+    /// flow to zero on each arc.
     void init() {
       createStructures();
@@ -292 +305 @@
     }
     
-    /// \brief Initializes the algorithm
-    /// 
-    /// Initializes the flow to the \c flowMap. The \c flowMap should
-    /// contain a feasible flow, ie. in each node excluding the source
-    /// and the target the incoming flow should be equal to the
+    /// \brief Initializes the algorithm using the given flow map.
+    ///
+    /// Initializes the internal data structures and sets the initial
+    /// flow to the given \c flowMap. The \c flowMap should
+    /// contain a feasible flow, i.e. at each node excluding the source
+    /// and the target, the incoming flow should be equal to the
     /// outgoing flow.
     template <typename FlowMap>
@@ -313 +327 @@
     }
 
-    /// \brief Initializes the algorithm
-    /// 
-    /// Initializes the flow to the \c flowMap. The \c flowMap should
-    /// contain a feasible flow, ie. in each node excluding the source
-    /// and the target the incoming flow should be equal to the
-    /// outgoing flow.  
-    /// \return %False when the given flowMap does not contain
+    /// \brief Initializes the algorithm using the given flow map.
+    ///
+    /// Initializes the internal data structures and sets the initial
+    /// flow to the given \c flowMap. The \c flowMap should
+    /// contain a feasible flow, i.e. at each node excluding the source
+    /// and the target, the incoming flow should be equal to the
+    /// outgoing flow. 
+    /// \return \c false when the given \c flowMap does not contain a
     /// feasible flow.
     template <typename FlowMap>
@@ -355 +370 @@
     }
 
-    /// \brief Augment the solution on an arc shortest path.
+    /// \brief Augments the solution along a shortest path.
     /// 
-    /// Augment the solution on an arc shortest path. It searches an
-    /// arc shortest path between the source and the target
-    /// in the residual digraph by the bfs algoritm.
+    /// Augments the solution along a shortest path. This function searches a
+    /// shortest path between the source and the target
+    /// in the residual digraph by the Bfs algoritm.
     /// Then it increases the flow on this path with the minimal residual
-    /// capacity on the path. If there is no such path it gives back
+    /// capacity on the path. If there is no such path, it gives back
     /// false.
-    /// \return %False when the augmenting didn't success so the
+    /// \return \c false when the augmenting did not success, i.e. the
     /// current flow is a feasible and optimal solution.
     bool augment() {
@@ -440 +455 @@
     /// \brief Executes the algorithm
     ///
-    /// It runs augmenting phases until the optimal solution is reached. 
+    /// Executes the algorithm by performing augmenting phases until the
+    /// optimal solution is reached. 
+    /// \pre One of the \ref init() functions must be called before
+    /// using this function.
     void start() {
       while (augment()) {}
@@ -447 +465 @@
     /// \brief Runs the algorithm.
     /// 
-    /// It is just a shorthand for:
-    ///
+    /// Runs the Edmonds-Karp algorithm.
+    /// \note ek.run() is just a shortcut of the following code.
     ///\code 
     /// ek.init();
@@ -463 +481 @@
     /// The result of the Edmonds-Karp algorithm can be obtained using these
     /// functions.\n
-    /// Before the use of these functions,
-    /// either run() or start() must be called.
+    /// Either \ref run() or \ref start() should be called before using them.
     
     ///@{
@@ -470 +487 @@
     /// \brief Returns the value of the maximum flow.
     ///
-    /// Returns the value of the maximum flow by returning the excess
-    /// of the target node \c t.
-
+    /// Returns the value of the maximum flow found by the algorithm.
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
     Value flowValue() const {
       return _flow_value;
     }
 
-
-    /// \brief Returns the flow on the arc.
-    ///
-    /// Sets the \c flowMap to the flow on the arcs.
+    /// \brief Returns the flow value on the given arc.
+    ///
+    /// Returns the flow value on the given arc.
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
     Value flow(const Arc& arc) const {
       return (*_flow)[arc];
     }
 
-    /// \brief Returns true when the node is on the source side of minimum cut.
-    ///
-
-    /// Returns true when the node is on the source side of minimum
-    /// cut.
-
+    /// \brief Returns a const reference to the flow map.
+    ///
+    /// Returns a const reference to the arc map storing the found flow.
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
+    const FlowMap& flowMap() const {
+      return *_flow;
+    }
+
+    /// \brief Returns \c true when the node is on the source side of the
+    /// minimum cut.
+    ///
+    /// Returns true when the node is on the source side of the found
+    /// minimum cut.
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
     bool minCut(const Node& node) const {
       return ((*_pred)[node] != INVALID) or node == _source;
     }
 
-    /// \brief Returns a minimum value cut.
-    ///
-    /// Sets \c cutMap to the characteristic vector of a minimum value cut.
-
+    /// \brief Gives back a minimum value cut.
+    ///
+    /// Sets \c cutMap to the characteristic vector of a minimum value
+    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
+    /// node map with \c bool (or convertible) value type.
+    ///
+    /// \note This function calls \ref minCut() for each node, so it runs in
+    /// O(n) time.
+    ///
+    /// \pre Either \ref run() or \ref init() must be called before
+    /// using this function.
     template <typename CutMap>
     void minCutMap(CutMap& cutMap) const {