Changeset 625:029a48052c67 in lemon-main

Timestamp:

04/26/09 16:44:53 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Modify the interface of MinCostArborescence? + improvements (#267)

• Rename arborescenceValue() to arborescenceCost().
• Rename DefXyz? template named paramaters to SetXyz?.
• Rearrange public functions (for better doc).
• Doc improvements.
• Extend the test file with interface checking.

Files:

• lemon/min_cost_arborescence.h (modified) (17 diffs)
• test/min_cost_arborescence_test.cc (modified) (4 diffs)

lemon/min_cost_arborescence.h

@@ -37 +37 @@
   /// Default traits class for MinCostArborescence class.
   /// \param GR Digraph type.
-  /// \param CM Type of cost map.
+  /// \param CM Type of the cost map.
   template <class GR, class CM>
   struct MinCostArborescenceDefaultTraits{
@@ -47 +47 @@
     ///
     /// The type of the map that stores the arc costs.
-    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+    /// It must conform to 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 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.
+    /// 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.
     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
 
@@ -67 +68 @@
     ///
     /// This function instantiates a \c ArborescenceMap.
-    /// \param digraph is the graph, to which we would like to
-    /// calculate the \c ArborescenceMap.
+    /// \param digraph The digraph to which we would like to calculate
+    /// the \c ArborescenceMap.
     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
       return new ArborescenceMap(digraph);
@@ -75 +76 @@
     /// \brief The type of the \c PredMap
     ///
-    /// The type of the \c PredMap. It is a node map with an arc value type.
+    /// 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.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 
@@ -93 +96 @@
   /// \brief Minimum Cost Arborescence algorithm class.
   ///
-  /// This class provides an efficient implementation of
+  /// This class provides an efficient implementation of the
   /// 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 for the algorithm and it will calculate
-  /// the minimum cost subgraph which are union of arborescences with the
+  /// more sources should be given to the algorithm and it will calculate
+  /// the minimum cost subgraph that is the 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 provides also an optimal dual solution, therefore
+  /// The algorithm also provides an optimal dual solution, therefore
   /// the optimality of the solution can be checked.
   ///
-  /// \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
+  /// \param GR The digraph type the algorithm runs on.
+  /// \param CM A read-only arc map storing 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 cost if
+  /// relatively time consuming process to compute the arc costs if
   /// it is necessary. The default map type is \ref
   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
@@ -114 +116 @@
   /// by the algorithm. The default traits class is
   /// \ref MinCostArborescenceDefaultTraits
-  /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
-  /// MinCostArborescenceDefaultTraits for the documentation of a
-  /// MinCostArborescence traits class.
+  /// "MinCostArborescenceDefaultTraits<GR, CM>".
 #ifndef DOXYGEN
-  template <typename GR = ListDigraph,
+  template <typename GR,
             typename CM = typename GR::template ArcMap<int>,
             typename TR =
@@ -128 +128 @@
   public:
 
-    /// The traits.
+    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
+    /// of the algorithm. 
     typedef TR Traits;
     /// The type of the underlying digraph.
@@ -396 +397 @@
 
     template <class T>
-    struct DefArborescenceMapTraits : public Traits {
+    struct SetArborescenceMapTraits : public Traits {
       typedef T ArborescenceMap;
       static ArborescenceMap *createArborescenceMap(const Digraph &)
@@ -406 +407 @@
 
     /// \brief \ref named-templ-param "Named parameter" for
-    /// setting ArborescenceMap type
+    /// setting \c ArborescenceMap type
     ///
     /// \ref named-templ-param "Named parameter" for setting
-    /// ArborescenceMap type
+    /// \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.
     template <class T>
-    struct DefArborescenceMap
+    struct SetArborescenceMap
       : public MinCostArborescence<Digraph, CostMap,
-                                   DefArborescenceMapTraits<T> > {
+                                   SetArborescenceMapTraits<T> > {
     };
 
     template <class T>
-    struct DefPredMapTraits : public Traits {
+    struct SetPredMapTraits : 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 PredMap type
+    /// setting \c PredMap type
     ///
     /// \ref named-templ-param "Named parameter" for setting
-    /// PredMap type
+    /// \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.
     template <class T>
-    struct DefPredMap
-      : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
+    struct SetPredMap
+      : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
     };
 
@@ -465 +473 @@
     }
 
-    /// \brief Sets the arborescence map.
-    ///
-    /// Sets the arborescence map.
+    /// \brief Sets the predecessor map.
+    ///
+    /// Sets the predecessor map.
     /// \return <tt>(*this)</tt>
     MinCostArborescence& predMap(PredMap& m) {
@@ -477 +485 @@
       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
@@ -690 +545 @@
     /// \return The processed node.
     ///
-    /// \warning The queue must not be empty!
+    /// \warning The queue must not be empty.
     Node processNextNode() {
       Node node = queue.back();
@@ -713 +568 @@
     /// \brief Returns the number of the nodes to be processed.
     ///
-    /// Returns the number of the nodes to be processed.
+    /// Returns the number of the nodes to be processed in the priority
+    /// queue.
     int queueSize() const {
       return queue.size();
@@ -755 +611 @@
     /// mca.start();
     /// \endcode
-    void run(Node node) {
+    void run(Node s) {
       init();
-      addSource(node);
+      addSource(s);
       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;
+    };
+
+    /// @}
 
   };
@@ -770 +782 @@
   ///
   /// Function type interface for MinCostArborescence algorithm.
-  /// \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.
+  /// \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.
   ///
   /// \sa MinCostArborescence
@@ -783 +796 @@
                                               ArborescenceMap& arborescence) {
     typename MinCostArborescence<Digraph, CostMap>
-      ::template DefArborescenceMap<ArborescenceMap>
+      ::template SetArborescenceMap<ArborescenceMap>
       ::Create mca(digraph, cost);
     mca.arborescenceMap(arborescence);
     mca.run(source);
-    return mca.arborescenceValue();
+    return mca.arborescenceCost();
   }
 

test/min_cost_arborescence_test.cc

@@ -25 +25 @@
 #include <lemon/min_cost_arborescence.h>
 #include <lemon/lgf_reader.h>
+#include <lemon/concepts/digraph.h>
 
 #include "test_tools.h"
@@ -71 +72 @@
   "source 0\n";
 
+
+void checkMinCostArborescenceCompile()
+{
+  typedef double VType;
+  typedef concepts::Digraph Digraph;
+  typedef concepts::ReadMap<Digraph::Arc, VType> CostMap;
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
+  typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap;
+  typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap;
+
+  typedef MinCostArborescence<Digraph, CostMap>::
+            SetArborescenceMap<ArbMap>::
+            SetPredMap<PredMap>::Create MinCostArbType;
+
+  Digraph g;
+  Node s, n;
+  Arc e;
+  VType c;
+  bool b;
+  int i;
+  CostMap cost;
+  ArbMap arb;
+  PredMap pred;
+
+  MinCostArbType mcarb_test(g, cost);
+  const MinCostArbType& const_mcarb_test = mcarb_test;
+
+  mcarb_test
+    .arborescenceMap(arb)
+    .predMap(pred)
+    .run(s);
+
+  mcarb_test.init();
+  mcarb_test.addSource(s);
+  mcarb_test.start();
+  n = mcarb_test.processNextNode();
+  b = const_mcarb_test.emptyQueue();
+  i = const_mcarb_test.queueSize();
+  
+  c = const_mcarb_test.arborescenceCost();
+  b = const_mcarb_test.arborescence(e);
+  e = const_mcarb_test.pred(n);
+  const MinCostArbType::ArborescenceMap &am =
+    const_mcarb_test.arborescenceMap();
+  const MinCostArbType::PredMap &pm =
+    const_mcarb_test.predMap();
+  b = const_mcarb_test.reached(n);
+  b = const_mcarb_test.processed(n);
+  
+  i = const_mcarb_test.dualNum();
+  c = const_mcarb_test.dualValue();
+  i = const_mcarb_test.dualSize(i);
+  c = const_mcarb_test.dualValue(i);
+  
+  ignore_unused_variable_warning(am);
+  ignore_unused_variable_warning(pm);
+}
+
 int main() {
   typedef SmartDigraph Digraph;
@@ -111 +171 @@
       }
       if (mca.arborescence(it)) {
-        check(sum == cost[it], "INVALID DUAL");
+        check(sum == cost[it], "Invalid dual solution");
       }
-      check(sum <= cost[it], "INVALID DUAL");
+      check(sum <= cost[it], "Invalid dual solution");
     }
   }
 
 
-  check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
-
-  check(mca.reached(source), "INVALID ARBORESCENCE");
+  check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution");
+
+  check(mca.reached(source), "Invalid arborescence");
   for (ArcIt a(digraph); a != INVALID; ++a) {
     check(!mca.reached(digraph.source(a)) ||
-          mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
+          mca.reached(digraph.target(a)), "Invalid arborescence");
   }
 
@@ -131 +191 @@
     for (InArcIt a(digraph, n); a != INVALID; ++a) {
       if (mca.arborescence(a)) {
-        check(mca.pred(n) == a, "INVALID ARBORESCENCE");
+        check(mca.pred(n) == a, "Invalid arborescence");
         ++cnt;
       }
     }
-    check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
+    check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence");
   }
 
   Digraph::ArcMap<bool> arborescence(digraph);
-  check(mca.arborescenceValue() ==
+  check(mca.arborescenceCost() ==
         minCostArborescence(digraph, cost, source, arborescence),
-        "WRONG FUNCTION");
+        "Wrong result of the function interface");
 
   return 0;