LEMON/LEMON-official Changeset - r672:029a48052c67

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r672:029a48052c67

« 665:b95898

673:58357e »

r672:029a48052c67

Sun, 26 Apr 2009 16:44:53

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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.

0 2 0

default

2 files changed with 279 insertions and 206 deletions:

lemon/min_cost_arborescence.h

210

197

test/min_cost_arborescence_test.cc

↑ Collapse diff ↑

lemon/min_cost_arborescence.h

Show inline comments

@@ -15,140 +15,141 @@
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_MIN_COST_ARBORESCENCE_H
 		#define LEMON_MIN_COST_ARBORESCENCE_H
 		///\ingroup spantree
 		///\file
 		///\brief Minimum Cost Arborescence algorithm.
 		#include <vector>
 		#include <lemon/list_graph.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/assert.h>
 		namespace lemon {
 		  /// \brief Default traits class for MinCostArborescence class.
 		  ///
 		  /// 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{
 		    /// \brief The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc costs.
 		    ///
 		    /// 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;
 		    /// \brief The value type of the costs.
 		    ///
 		    /// The value type of the costs.
 		    typedef typename CostMap::Value Value;
 		    /// \brief The type of the map that stores which arcs are in the
 		    /// arborescence.
 		    ///
 		    /// 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;
 		    /// \brief Instantiates a \c ArborescenceMap.
 		    ///
 		    /// 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);
+		    }
 		    /// \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;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
 		    /// This function instantiates a \c PredMap.
 		    /// \param digraph The digraph to which we would like to define the
 		    /// \c PredMap.
 		    static PredMap *createPredMap(const Digraph &digraph){
 		      return new PredMap(digraph);
+		    }
 		  };
 		  /// \ingroup spantree
 		  ///
 		  /// \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>".
 		  /// \param TR Traits class to set various data types used
 		  /// 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 =
 		              MinCostArborescenceDefaultTraits<GR, CM> >
 		#else
 		  template <typename GR, typename CM, typedef TR>
 		#endif
 		  class MinCostArborescence {
 		  public:
-		    /// The traits.
+		    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
 		    /// of the algorithm.
 		    typedef TR Traits;
 		    /// The type of the underlying digraph.
 		    typedef typename Traits::Digraph Digraph;
 		    /// The type of the map that stores the arc costs.
 		    typedef typename Traits::CostMap CostMap;
 		    ///The type of the costs of the arcs.
 		    typedef typename Traits::Value Value;
 		    ///The type of the predecessor map.
 		    typedef typename Traits::PredMap PredMap;
 		    ///The type of the map that stores which arcs are in the arborescence.
 		    typedef typename Traits::ArborescenceMap ArborescenceMap;
 		    typedef MinCostArborescence Create;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    struct CostArc {
 		      Arc arc;
 		      Value value;
 		      CostArc() {}
@@ -374,283 +375,137 @@
 		            _pred->set(target, it);
 		            break;
 		          case Heap::IN_HEAP:
 		            if ((*_arc_order)[it] < (*_heap)[target]) {
 		              _heap->decrease(target, (*_arc_order)[it]);
 		              _pred->set(target, it);
+		            }
 		            break;
 		          case Heap::POST_HEAP:
 		            break;
+		          }
+		        }
 		        _arborescence->set((*_pred)[source], true);
+		      }
+		    }
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <class T>
-		    struct DefArborescenceMapTraits : public Traits {
+		    struct SetArborescenceMapTraits : public Traits {
 		      typedef T ArborescenceMap;
 		      static ArborescenceMap *createArborescenceMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ArborescenceMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \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> > {
 		    };
 		    /// @}
 		    /// \brief Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm will run on.
 		    /// \param cost The cost map used by the algorithm.
 		    MinCostArborescence(const Digraph& digraph, const CostMap& cost)
 		      : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
 		        _arborescence(0), local_arborescence(false),
 		        _arc_order(0), _node_order(0), _cost_arcs(0),
 		        _heap_cross_ref(0), _heap(0) {}
 		    /// \brief Destructor.
 		    ~MinCostArborescence() {
 		      destroyStructures();
+		    }
 		    /// \brief Sets the arborescence map.
 		    ///
 		    /// Sets the arborescence map.
 		    /// \return <tt>(*this)</tt>
 		    MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
 		      if (local_arborescence) {
 		        delete _arborescence;
+		      }
 		      local_arborescence = false;
 		      _arborescence = &m;
 		      return *this;
+		    }
-		    /// \brief Sets the arborescence map.
+		    /// \brief Sets the predecessor map.
 		    ///
-		    /// Sets the arborescence map.
+		    /// Sets the predecessor map.
 		    /// \return <tt>(*this)</tt>
 		    MinCostArborescence& predMap(PredMap& m) {
 		      if (local_pred) {
 		        delete _pred;
+		      }
 		      local_pred = false;
 		      _pred = &m;
 		      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
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \c run(...). \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init(), then you can add several
 		    /// source nodes with \ref addSource().
 		    /// Finally \ref start() will perform the arborescence
 		    /// computation.
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    ///
 		    void init() {
 		      createStructures();
 		      _heap->clear();
 		      for (NodeIt it(*_digraph); it != INVALID; ++it) {
 		        (*_cost_arcs)[it].arc = INVALID;
 		        (*_node_order)[it] = -3;
 		        (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
 		        _pred->set(it, INVALID);
+		      }
@@ -668,127 +523,285 @@
 		    void addSource(Node source) {
 		      std::vector<Node> nodes;
 		      nodes.push_back(source);
 		      while (!nodes.empty()) {
 		        Node node = nodes.back();
 		        nodes.pop_back();
 		        for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
 		          Node target = _digraph->target(it);
 		          if ((*_node_order)[target] == -3) {
 		            (*_node_order)[target] = -2;
 		            nodes.push_back(target);
 		            queue.push_back(target);
+		          }
+		        }
+		      }
 		      (*_node_order)[source] = -1;
+		    }
 		    /// \brief Processes the next node in the priority queue.
 		    ///
 		    /// Processes the next node in the priority queue.
 		    ///
 		    /// \return The processed node.
 		    ///
-		    /// \warning The queue must not be empty!
+		    /// \warning The queue must not be empty.
 		    Node processNextNode() {
 		      Node node = queue.back();
 		      queue.pop_back();
 		      if ((*_node_order)[node] == -2) {
 		        Arc arc = prepare(node);
 		        Node source = _digraph->source(arc);
 		        while ((*_node_order)[source] != -1) {
 		          if ((*_node_order)[source] >= 0) {
 		            arc = contract(source);
 		          } else {
 		            arc = prepare(source);
+		          }
 		          source = _digraph->source(arc);
+		        }
 		        finalize(arc);
 		        level_stack.clear();
+		      }
 		      return node;
+		    }
 		    /// \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();
+		    }
 		    /// \brief Returns \c false if there are nodes to be processed.
 		    ///
 		    /// Returns \c false if there are nodes to be processed.
 		    bool emptyQueue() const {
 		      return queue.empty();
+		    }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// \pre init() must be called and at least one node should be added
 		    /// with addSource() before using this function.
 		    ///
 		    ///\note mca.start() is just a shortcut of the following code.
 		    ///\code
 		    ///while (!mca.emptyQueue()) {
 		    ///  mca.processNextNode();
 		    ///}
 		    ///\endcode
 		    void start() {
 		      while (!emptyQueue()) {
 		        processNextNode();
+		      }
+		    }
 		    /// \brief Runs %MinCostArborescence algorithm from node \c s.
 		    ///
 		    /// This method runs the %MinCostArborescence algorithm from
 		    /// a root node \c s.
 		    ///
 		    /// \note mca.run(s) is just a shortcut of the following code.
 		    /// \code
 		    /// mca.init();
 		    /// mca.addSource(s);
 		    /// 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;
 		    };
 		    /// @}
 		  };
 		  /// \ingroup spantree
 		  ///
 		  /// \brief Function type interface for MinCostArborescence algorithm.
 		  ///
 		  /// 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
 		  template <typename Digraph, typename CostMap, typename ArborescenceMap>
 		  typename CostMap::Value minCostArborescence(const Digraph& digraph,
 		                                              const CostMap& cost,
 		                                              typename Digraph::Node source,
 		                                              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();
+		  }
+		}
 		#endif

test/min_cost_arborescence_test.cc

Show inline comments

@@ -3,144 +3,204 @@
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <iostream>
 		#include <set>
 		#include <vector>
 		#include <iterator>
 		#include <lemon/smart_graph.h>
 		#include <lemon/min_cost_arborescence.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/concepts/digraph.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace std;
 		const char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "7\n"
 		  "8\n"
 		  "9\n"
 		  "@arcs\n"
 		  "     label  cost\n"
 		  "1 8  0      107\n"
 		  "0 3  1      70\n"
 		  "2 1  2      46\n"
 		  "4 1  3      28\n"
 		  "4 4  4      91\n"
 		  "3 9  5      76\n"
 		  "9 8  6      61\n"
 		  "8 1  7      39\n"
 		  "9 8  8      74\n"
 		  "8 0  9      39\n"
 		  "4 3  10     45\n"
 		  "2 2  11     34\n"
 		  "0 1  12     100\n"
 		  "6 3  13     95\n"
 		  "4 1  14     22\n"
 		  "1 1  15     31\n"
 		  "7 2  16     51\n"
 		  "2 6  17     29\n"
 		  "8 3  18     115\n"
 		  "6 9  19     32\n"
 		  "1 1  20     60\n"
 		  "0 3  21     40\n"
 		  "@attributes\n"
 		  "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;
 		  DIGRAPH_TYPEDEFS(Digraph);
 		  typedef Digraph::ArcMap<double> CostMap;
 		  Digraph digraph;
 		  CostMap cost(digraph);
 		  Node source;
 		  std::istringstream is(test_lgf);
 		  digraphReader(digraph, is).
 		    arcMap("cost", cost).
 		    node("source", source).run();
 		  MinCostArborescence<Digraph, CostMap> mca(digraph, cost);
 		  mca.run(source);
 		  vector<pair<double, set<Node> > > dualSolution(mca.dualNum());
 		  for (int i = 0; i < mca.dualNum(); ++i) {
 		    dualSolution[i].first = mca.dualValue(i);
 		    for (MinCostArborescence<Digraph, CostMap>::DualIt it(mca, i);
 		         it != INVALID; ++it) {
 		      dualSolution[i].second.insert(it);
+		    }
+		  }
 		  for (ArcIt it(digraph); it != INVALID; ++it) {
 		    if (mca.reached(digraph.source(it))) {
 		      double sum = 0.0;
 		      for (int i = 0; i < int(dualSolution.size()); ++i) {
 		        if (dualSolution[i].second.find(digraph.target(it))
 		            != dualSolution[i].second.end() &&
 		            dualSolution[i].second.find(digraph.source(it))
 		            == dualSolution[i].second.end()) {
 		          sum += dualSolution[i].first;
+		        }
+		      }
 		      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.dualValue() == mca.arborescenceCost(), "Invalid dual solution");
-		  check(mca.reached(source), "INVALID ARBORESCENCE");
+		  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");
+		  }
 		  for (NodeIt n(digraph); n != INVALID; ++n) {
 		    if (!mca.reached(n)) continue;
 		    int cnt = 0;
 		    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;
+		}

0 comments (0 inline)

RhodeCode

Login to your account