Changes in lemon/min_cost_arborescence.h [672:029a48052c67:631:33c6b6e755cd] in lemon

File:

• lemon/min_cost_arborescence.h (modified) (17 diffs)

lemon/min_cost_arborescence.h

@@ -37 +37 @@
   /// Default traits class for MinCostArborescence class.
   /// \param GR Digraph type.
-  /// \param CM Type of the cost map.
+  /// \param CM Type of cost map.
   template <class GR, class CM>
   struct MinCostArborescenceDefaultTraits{
@@ -47 +47 @@
     ///
     /// The type of the map that stores the arc costs.
-    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
     typedef CM CostMap;
 
@@ -59 +59 @@
     ///
     /// The type of the map that stores which arcs are in the
-    /// arborescence.  It must conform to the \ref concepts::WriteMap
-    /// "WriteMap" concept, and its value type must be \c bool
-    /// (or convertible). Initially it will be set to \c false on each
-    /// arc, then it will be set on each arborescence arc once.
+    /// arborescence.  It must meet the \ref concepts::WriteMap
+    /// "WriteMap" concept.  Initially it will be set to false on each
+    /// arc. After it will set all arborescence arcs once.
     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
 
@@ -68 +67 @@
     ///
     /// This function instantiates a \c ArborescenceMap.
-    /// \param digraph The digraph to which we would like to calculate
-    /// the \c ArborescenceMap.
+    /// \param digraph is the graph, to which we would like to
+    /// calculate the \c ArborescenceMap.
     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
       return new ArborescenceMap(digraph);
@@ -76 +75 @@
     /// \brief The type of the \c PredMap
     ///
-    /// The type of the \c PredMap. It must confrom to the
-    /// \ref concepts::WriteMap "WriteMap" concept, and its value type
-    /// must be the \c Arc type of the digraph.
+    /// The type of the \c PredMap. It is a node map with an arc value type.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 
@@ -96 +93 @@
   /// \brief Minimum Cost Arborescence algorithm class.
   ///
-  /// This class provides an efficient implementation of the
+  /// This class provides an efficient implementation of
   /// Minimum Cost Arborescence algorithm. The arborescence is a tree
   /// which is directed from a given source node of the digraph. One or
-  /// more sources should be given to the algorithm and it will calculate
-  /// the minimum cost subgraph that is the union of arborescences with the
+  /// more sources should be given for the algorithm and it will calculate
+  /// the minimum cost subgraph which are union of arborescences with the
   /// given sources and spans all the nodes which are reachable from the
   /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
   ///
-  /// The algorithm also provides an optimal dual solution, therefore
+  /// The algorithm provides also an optimal dual solution, therefore
   /// the optimality of the solution can be checked.
   ///
-  /// \param GR The digraph type the algorithm runs on.
-  /// \param CM A read-only arc map storing the costs of the
+  /// \param GR The digraph type the algorithm runs on. The default value
+  /// is \ref ListDigraph.
+  /// \param CM This read-only ArcMap determines the costs of the
   /// arcs. It is read once for each arc, so the map may involve in
-  /// relatively time consuming process to compute the arc costs if
+  /// relatively time consuming process to compute the arc cost if
   /// it is necessary. The default map type is \ref
   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
@@ -116 +114 @@
   /// by the algorithm. The default traits class is
   /// \ref MinCostArborescenceDefaultTraits
-  /// "MinCostArborescenceDefaultTraits<GR, CM>".
+  /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
+  /// MinCostArborescenceDefaultTraits for the documentation of a
+  /// MinCostArborescence traits class.
 #ifndef DOXYGEN
-  template <typename GR,
+  template <typename GR = ListDigraph,
             typename CM = typename GR::template ArcMap<int>,
             typename TR =
@@ -128 +128 @@
   public:
 
-    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
-    /// of the algorithm. 
+    /// The traits.
     typedef TR Traits;
     /// The type of the underlying digraph.
@@ -397 +396 @@
 
     template <class T>
-    struct SetArborescenceMapTraits : public Traits {
+    struct DefArborescenceMapTraits : public Traits {
       typedef T ArborescenceMap;
       static ArborescenceMap *createArborescenceMap(const Digraph &)
@@ -407 +406 @@
 
     /// \brief \ref named-templ-param "Named parameter" for
-    /// setting \c ArborescenceMap type
+    /// setting ArborescenceMap type
     ///
     /// \ref named-templ-param "Named parameter" for setting
-    /// \c ArborescenceMap type.
-    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
-    /// and its value type must be \c bool (or convertible).
-    /// Initially it will be set to \c false on each arc,
-    /// then it will be set on each arborescence arc once.
+    /// ArborescenceMap type
     template <class T>
-    struct SetArborescenceMap
+    struct DefArborescenceMap
       : public MinCostArborescence<Digraph, CostMap,
-                                   SetArborescenceMapTraits<T> > {
+                                   DefArborescenceMapTraits<T> > {
     };
 
     template <class T>
-    struct SetPredMapTraits : public Traits {
+    struct DefPredMapTraits : public Traits {
       typedef T PredMap;
       static PredMap *createPredMap(const Digraph &)
       {
         LEMON_ASSERT(false, "PredMap is not initialized");
-        return 0; // ignore warnings
       }
     };
 
     /// \brief \ref named-templ-param "Named parameter" for
-    /// setting \c PredMap type
+    /// setting PredMap type
     ///
     /// \ref named-templ-param "Named parameter" for setting
-    /// \c PredMap type.
-    /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 
-    /// and its value type must be the \c Arc type of the digraph.
+    /// PredMap type
     template <class T>
-    struct SetPredMap
-      : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
+    struct DefPredMap
+      : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
     };
 
@@ -473 +465 @@
     }
 
-    /// \brief Sets the predecessor map.
-    ///
-    /// Sets the predecessor map.
+    /// \brief Sets the arborescence map.
+    ///
+    /// Sets the arborescence map.
     /// \return <tt>(*this)</tt>
     MinCostArborescence& predMap(PredMap& m) {
@@ -485 +477 @@
       return *this;
     }
+
+    /// \name Query Functions
+    /// The result of the %MinCostArborescence algorithm can be obtained
+    /// using these functions.\n
+    /// Before the use of these functions,
+    /// either run() or start() must be called.
+
+    /// @{
+
+    /// \brief Returns a reference to the arborescence map.
+    ///
+    /// Returns a reference to the arborescence map.
+    const ArborescenceMap& arborescenceMap() const {
+      return *_arborescence;
+    }
+
+    /// \brief Returns true if the arc is in the arborescence.
+    ///
+    /// Returns true if the arc is in the arborescence.
+    /// \param arc The arc of the digraph.
+    /// \pre \ref run() must be called before using this function.
+    bool arborescence(Arc arc) const {
+      return (*_pred)[_digraph->target(arc)] == arc;
+    }
+
+    /// \brief Returns a reference to the pred map.
+    ///
+    /// Returns a reference to the pred map.
+    const PredMap& predMap() const {
+      return *_pred;
+    }
+
+    /// \brief Returns the predecessor arc of the given node.
+    ///
+    /// Returns the predecessor arc of the given node.
+    Arc pred(Node node) const {
+      return (*_pred)[node];
+    }
+
+    /// \brief Returns the cost of the arborescence.
+    ///
+    /// Returns the cost of the arborescence.
+    Value arborescenceValue() const {
+      Value sum = 0;
+      for (ArcIt it(*_digraph); it != INVALID; ++it) {
+        if (arborescence(it)) {
+          sum += (*_cost)[it];
+        }
+      }
+      return sum;
+    }
+
+    /// \brief Indicates that a node is reachable from the sources.
+    ///
+    /// Indicates that a node is reachable from the sources.
+    bool reached(Node node) const {
+      return (*_node_order)[node] != -3;
+    }
+
+    /// \brief Indicates that a node is processed.
+    ///
+    /// Indicates that a node is processed. The arborescence path exists
+    /// from the source to the given node.
+    bool processed(Node node) const {
+      return (*_node_order)[node] == -1;
+    }
+
+    /// \brief Returns the number of the dual variables in basis.
+    ///
+    /// Returns the number of the dual variables in basis.
+    int dualNum() const {
+      return _dual_variables.size();
+    }
+
+    /// \brief Returns the value of the dual solution.
+    ///
+    /// Returns the value of the dual solution. It should be
+    /// equal to the arborescence value.
+    Value dualValue() const {
+      Value sum = 0;
+      for (int i = 0; i < int(_dual_variables.size()); ++i) {
+        sum += _dual_variables[i].value;
+      }
+      return sum;
+    }
+
+    /// \brief Returns the number of the nodes in the dual variable.
+    ///
+    /// Returns the number of the nodes in the dual variable.
+    int dualSize(int k) const {
+      return _dual_variables[k].end - _dual_variables[k].begin;
+    }
+
+    /// \brief Returns the value of the dual variable.
+    ///
+    /// Returns the the value of the dual variable.
+    const Value& dualValue(int k) const {
+      return _dual_variables[k].value;
+    }
+
+    /// \brief Lemon iterator for get a dual variable.
+    ///
+    /// Lemon iterator for get a dual variable. This class provides
+    /// a common style lemon iterator which gives back a subset of
+    /// the nodes.
+    class DualIt {
+    public:
+
+      /// \brief Constructor.
+      ///
+      /// Constructor for get the nodeset of the variable.
+      DualIt(const MinCostArborescence& algorithm, int variable)
+        : _algorithm(&algorithm)
+      {
+        _index = _algorithm->_dual_variables[variable].begin;
+        _last = _algorithm->_dual_variables[variable].end;
+      }
+
+      /// \brief Conversion to node.
+      ///
+      /// Conversion to node.
+      operator Node() const {
+        return _algorithm->_dual_node_list[_index];
+      }
+
+      /// \brief Increment operator.
+      ///
+      /// Increment operator.
+      DualIt& operator++() {
+        ++_index;
+        return *this;
+      }
+
+      /// \brief Validity checking
+      ///
+      /// Checks whether the iterator is invalid.
+      bool operator==(Invalid) const {
+        return _index == _last;
+      }
+
+      /// \brief Validity checking
+      ///
+      /// Checks whether the iterator is valid.
+      bool operator!=(Invalid) const {
+        return _index != _last;
+      }
+
+    private:
+      const MinCostArborescence* _algorithm;
+      int _index, _last;
+    };
+
+    /// @}
 
     /// \name Execution Control
@@ -545 +690 @@
     /// \return The processed node.
     ///
-    /// \warning The queue must not be empty.
+    /// \warning The queue must not be empty!
     Node processNextNode() {
       Node node = queue.back();
@@ -568 +713 @@
     /// \brief Returns the number of the nodes to be processed.
     ///
-    /// Returns the number of the nodes to be processed in the priority
-    /// queue.
+    /// Returns the number of the nodes to be processed.
     int queueSize() const {
       return queue.size();
@@ -611 +755 @@
     /// mca.start();
     /// \endcode
-    void run(Node s) {
+    void run(Node node) {
       init();
-      addSource(s);
+      addSource(node);
       start();
     }
 
     ///@}
-
-    /// \name Query Functions
-    /// The result of the %MinCostArborescence algorithm can be obtained
-    /// using these functions.\n
-    /// Either run() or start() must be called before using them.
-
-    /// @{
-
-    /// \brief Returns the cost of the arborescence.
-    ///
-    /// Returns the cost of the arborescence.
-    Value arborescenceCost() const {
-      Value sum = 0;
-      for (ArcIt it(*_digraph); it != INVALID; ++it) {
-        if (arborescence(it)) {
-          sum += (*_cost)[it];
-        }
-      }
-      return sum;
-    }
-
-    /// \brief Returns \c true if the arc is in the arborescence.
-    ///
-    /// Returns \c true if the given arc is in the arborescence.
-    /// \param arc An arc of the digraph.
-    /// \pre \ref run() must be called before using this function.
-    bool arborescence(Arc arc) const {
-      return (*_pred)[_digraph->target(arc)] == arc;
-    }
-
-    /// \brief Returns a const reference to the arborescence map.
-    ///
-    /// Returns a const reference to the arborescence map.
-    /// \pre \ref run() must be called before using this function.
-    const ArborescenceMap& arborescenceMap() const {
-      return *_arborescence;
-    }
-
-    /// \brief Returns the predecessor arc of the given node.
-    ///
-    /// Returns the predecessor arc of the given node.
-    /// \pre \ref run() must be called before using this function.
-    Arc pred(Node node) const {
-      return (*_pred)[node];
-    }
-
-    /// \brief Returns a const reference to the pred map.
-    ///
-    /// Returns a const reference to the pred map.
-    /// \pre \ref run() must be called before using this function.
-    const PredMap& predMap() const {
-      return *_pred;
-    }
-
-    /// \brief Indicates that a node is reachable from the sources.
-    ///
-    /// Indicates that a node is reachable from the sources.
-    bool reached(Node node) const {
-      return (*_node_order)[node] != -3;
-    }
-
-    /// \brief Indicates that a node is processed.
-    ///
-    /// Indicates that a node is processed. The arborescence path exists
-    /// from the source to the given node.
-    bool processed(Node node) const {
-      return (*_node_order)[node] == -1;
-    }
-
-    /// \brief Returns the number of the dual variables in basis.
-    ///
-    /// Returns the number of the dual variables in basis.
-    int dualNum() const {
-      return _dual_variables.size();
-    }
-
-    /// \brief Returns the value of the dual solution.
-    ///
-    /// Returns the value of the dual solution. It should be
-    /// equal to the arborescence value.
-    Value dualValue() const {
-      Value sum = 0;
-      for (int i = 0; i < int(_dual_variables.size()); ++i) {
-        sum += _dual_variables[i].value;
-      }
-      return sum;
-    }
-
-    /// \brief Returns the number of the nodes in the dual variable.
-    ///
-    /// Returns the number of the nodes in the dual variable.
-    int dualSize(int k) const {
-      return _dual_variables[k].end - _dual_variables[k].begin;
-    }
-
-    /// \brief Returns the value of the dual variable.
-    ///
-    /// Returns the the value of the dual variable.
-    Value dualValue(int k) const {
-      return _dual_variables[k].value;
-    }
-
-    /// \brief LEMON iterator for getting a dual variable.
-    ///
-    /// This class provides a common style LEMON iterator for getting a
-    /// dual variable of \ref MinCostArborescence algorithm.
-    /// It iterates over a subset of the nodes.
-    class DualIt {
-    public:
-
-      /// \brief Constructor.
-      ///
-      /// Constructor for getting the nodeset of the dual variable
-      /// of \ref MinCostArborescence algorithm.
-      DualIt(const MinCostArborescence& algorithm, int variable)
-        : _algorithm(&algorithm)
-      {
-        _index = _algorithm->_dual_variables[variable].begin;
-        _last = _algorithm->_dual_variables[variable].end;
-      }
-
-      /// \brief Conversion to \c Node.
-      ///
-      /// Conversion to \c Node.
-      operator Node() const {
-        return _algorithm->_dual_node_list[_index];
-      }
-
-      /// \brief Increment operator.
-      ///
-      /// Increment operator.
-      DualIt& operator++() {
-        ++_index;
-        return *this;
-      }
-
-      /// \brief Validity checking
-      ///
-      /// Checks whether the iterator is invalid.
-      bool operator==(Invalid) const {
-        return _index == _last;
-      }
-
-      /// \brief Validity checking
-      ///
-      /// Checks whether the iterator is valid.
-      bool operator!=(Invalid) const {
-        return _index != _last;
-      }
-
-    private:
-      const MinCostArborescence* _algorithm;
-      int _index, _last;
-    };
-
-    /// @}
 
   };
@@ -782 +770 @@
   ///
   /// Function type interface for MinCostArborescence algorithm.
-  /// \param digraph The digraph the algorithm runs on.
-  /// \param cost An arc map storing the costs.
-  /// \param source The source node of the arborescence.
-  /// \retval arborescence An arc map with \c bool (or convertible) value
-  /// type that stores the arborescence.
-  /// \return The total cost of the arborescence.
+  /// \param digraph The Digraph that the algorithm runs on.
+  /// \param cost The CostMap of the arcs.
+  /// \param source The source of the arborescence.
+  /// \retval arborescence The bool ArcMap which stores the arborescence.
+  /// \return The cost of the arborescence.
   ///
   /// \sa MinCostArborescence
@@ -796 +783 @@
                                               ArborescenceMap& arborescence) {
     typename MinCostArborescence<Digraph, CostMap>
-      ::template SetArborescenceMap<ArborescenceMap>
+      ::template DefArborescenceMap<ArborescenceMap>
       ::Create mca(digraph, cost);
     mca.arborescenceMap(arborescence);
     mca.run(source);
-    return mca.arborescenceCost();
+    return mca.arborescenceValue();
   }