Modify the interface of MinCostArborescence + improvements (#267)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 26 Apr 2009 16:44:53 +0200
changeset 672029a48052c67
parent 665 b95898314e09
child 673 58357e986a08
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.
lemon/min_cost_arborescence.h
test/min_cost_arborescence_test.cc
     1.1 --- a/lemon/min_cost_arborescence.h	Fri Apr 24 12:12:14 2009 +0100
     1.2 +++ b/lemon/min_cost_arborescence.h	Sun Apr 26 16:44:53 2009 +0200
     1.3 @@ -36,7 +36,7 @@
     1.4    ///
     1.5    /// Default traits class for MinCostArborescence class.
     1.6    /// \param GR Digraph type.
     1.7 -  /// \param CM Type of cost map.
     1.8 +  /// \param CM Type of the cost map.
     1.9    template <class GR, class CM>
    1.10    struct MinCostArborescenceDefaultTraits{
    1.11  
    1.12 @@ -46,7 +46,7 @@
    1.13      /// \brief The type of the map that stores the arc costs.
    1.14      ///
    1.15      /// The type of the map that stores the arc costs.
    1.16 -    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    1.17 +    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    1.18      typedef CM CostMap;
    1.19  
    1.20      /// \brief The value type of the costs.
    1.21 @@ -58,23 +58,26 @@
    1.22      /// arborescence.
    1.23      ///
    1.24      /// The type of the map that stores which arcs are in the
    1.25 -    /// arborescence.  It must meet the \ref concepts::WriteMap
    1.26 -    /// "WriteMap" concept.  Initially it will be set to false on each
    1.27 -    /// arc. After it will set all arborescence arcs once.
    1.28 +    /// arborescence.  It must conform to the \ref concepts::WriteMap
    1.29 +    /// "WriteMap" concept, and its value type must be \c bool
    1.30 +    /// (or convertible). Initially it will be set to \c false on each
    1.31 +    /// arc, then it will be set on each arborescence arc once.
    1.32      typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    1.33  
    1.34      /// \brief Instantiates a \c ArborescenceMap.
    1.35      ///
    1.36      /// This function instantiates a \c ArborescenceMap.
    1.37 -    /// \param digraph is the graph, to which we would like to
    1.38 -    /// calculate the \c ArborescenceMap.
    1.39 +    /// \param digraph The digraph to which we would like to calculate
    1.40 +    /// the \c ArborescenceMap.
    1.41      static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    1.42        return new ArborescenceMap(digraph);
    1.43      }
    1.44  
    1.45      /// \brief The type of the \c PredMap
    1.46      ///
    1.47 -    /// The type of the \c PredMap. It is a node map with an arc value type.
    1.48 +    /// The type of the \c PredMap. It must confrom to the
    1.49 +    /// \ref concepts::WriteMap "WriteMap" concept, and its value type
    1.50 +    /// must be the \c Arc type of the digraph.
    1.51      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    1.52  
    1.53      /// \brief Instantiates a \c PredMap.
    1.54 @@ -92,32 +95,29 @@
    1.55    ///
    1.56    /// \brief Minimum Cost Arborescence algorithm class.
    1.57    ///
    1.58 -  /// This class provides an efficient implementation of
    1.59 +  /// This class provides an efficient implementation of the
    1.60    /// Minimum Cost Arborescence algorithm. The arborescence is a tree
    1.61    /// which is directed from a given source node of the digraph. One or
    1.62 -  /// more sources should be given for the algorithm and it will calculate
    1.63 -  /// the minimum cost subgraph which are union of arborescences with the
    1.64 +  /// more sources should be given to the algorithm and it will calculate
    1.65 +  /// the minimum cost subgraph that is the union of arborescences with the
    1.66    /// given sources and spans all the nodes which are reachable from the
    1.67    /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
    1.68    ///
    1.69 -  /// The algorithm provides also an optimal dual solution, therefore
    1.70 +  /// The algorithm also provides an optimal dual solution, therefore
    1.71    /// the optimality of the solution can be checked.
    1.72    ///
    1.73 -  /// \param GR The digraph type the algorithm runs on. The default value
    1.74 -  /// is \ref ListDigraph.
    1.75 -  /// \param CM This read-only ArcMap determines the costs of the
    1.76 +  /// \param GR The digraph type the algorithm runs on.
    1.77 +  /// \param CM A read-only arc map storing the costs of the
    1.78    /// arcs. It is read once for each arc, so the map may involve in
    1.79 -  /// relatively time consuming process to compute the arc cost if
    1.80 +  /// relatively time consuming process to compute the arc costs if
    1.81    /// it is necessary. The default map type is \ref
    1.82    /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    1.83    /// \param TR Traits class to set various data types used
    1.84    /// by the algorithm. The default traits class is
    1.85    /// \ref MinCostArborescenceDefaultTraits
    1.86 -  /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
    1.87 -  /// MinCostArborescenceDefaultTraits for the documentation of a
    1.88 -  /// MinCostArborescence traits class.
    1.89 +  /// "MinCostArborescenceDefaultTraits<GR, CM>".
    1.90  #ifndef DOXYGEN
    1.91 -  template <typename GR = ListDigraph,
    1.92 +  template <typename GR,
    1.93              typename CM = typename GR::template ArcMap<int>,
    1.94              typename TR =
    1.95                MinCostArborescenceDefaultTraits<GR, CM> >
    1.96 @@ -127,7 +127,8 @@
    1.97    class MinCostArborescence {
    1.98    public:
    1.99  
   1.100 -    /// The traits.
   1.101 +    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
   1.102 +    /// of the algorithm. 
   1.103      typedef TR Traits;
   1.104      /// The type of the underlying digraph.
   1.105      typedef typename Traits::Digraph Digraph;
   1.106 @@ -395,7 +396,7 @@
   1.107      /// @{
   1.108  
   1.109      template <class T>
   1.110 -    struct DefArborescenceMapTraits : public Traits {
   1.111 +    struct SetArborescenceMapTraits : public Traits {
   1.112        typedef T ArborescenceMap;
   1.113        static ArborescenceMap *createArborescenceMap(const Digraph &)
   1.114        {
   1.115 @@ -405,33 +406,40 @@
   1.116      };
   1.117  
   1.118      /// \brief \ref named-templ-param "Named parameter" for
   1.119 -    /// setting ArborescenceMap type
   1.120 +    /// setting \c ArborescenceMap type
   1.121      ///
   1.122      /// \ref named-templ-param "Named parameter" for setting
   1.123 -    /// ArborescenceMap type
   1.124 +    /// \c ArborescenceMap type.
   1.125 +    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
   1.126 +    /// and its value type must be \c bool (or convertible).
   1.127 +    /// Initially it will be set to \c false on each arc,
   1.128 +    /// then it will be set on each arborescence arc once.
   1.129      template <class T>
   1.130 -    struct DefArborescenceMap
   1.131 +    struct SetArborescenceMap
   1.132        : public MinCostArborescence<Digraph, CostMap,
   1.133 -                                   DefArborescenceMapTraits<T> > {
   1.134 +                                   SetArborescenceMapTraits<T> > {
   1.135      };
   1.136  
   1.137      template <class T>
   1.138 -    struct DefPredMapTraits : public Traits {
   1.139 +    struct SetPredMapTraits : public Traits {
   1.140        typedef T PredMap;
   1.141        static PredMap *createPredMap(const Digraph &)
   1.142        {
   1.143          LEMON_ASSERT(false, "PredMap is not initialized");
   1.144 +        return 0; // ignore warnings
   1.145        }
   1.146      };
   1.147  
   1.148      /// \brief \ref named-templ-param "Named parameter" for
   1.149 -    /// setting PredMap type
   1.150 +    /// setting \c PredMap type
   1.151      ///
   1.152      /// \ref named-templ-param "Named parameter" for setting
   1.153 -    /// PredMap type
   1.154 +    /// \c PredMap type.
   1.155 +    /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 
   1.156 +    /// and its value type must be the \c Arc type of the digraph.
   1.157      template <class T>
   1.158 -    struct DefPredMap
   1.159 -      : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
   1.160 +    struct SetPredMap
   1.161 +      : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
   1.162      };
   1.163  
   1.164      /// @}
   1.165 @@ -464,9 +472,9 @@
   1.166        return *this;
   1.167      }
   1.168  
   1.169 -    /// \brief Sets the arborescence map.
   1.170 +    /// \brief Sets the predecessor map.
   1.171      ///
   1.172 -    /// Sets the arborescence map.
   1.173 +    /// Sets the predecessor map.
   1.174      /// \return <tt>(*this)</tt>
   1.175      MinCostArborescence& predMap(PredMap& m) {
   1.176        if (local_pred) {
   1.177 @@ -477,159 +485,6 @@
   1.178        return *this;
   1.179      }
   1.180  
   1.181 -    /// \name Query Functions
   1.182 -    /// The result of the %MinCostArborescence algorithm can be obtained
   1.183 -    /// using these functions.\n
   1.184 -    /// Before the use of these functions,
   1.185 -    /// either run() or start() must be called.
   1.186 -
   1.187 -    /// @{
   1.188 -
   1.189 -    /// \brief Returns a reference to the arborescence map.
   1.190 -    ///
   1.191 -    /// Returns a reference to the arborescence map.
   1.192 -    const ArborescenceMap& arborescenceMap() const {
   1.193 -      return *_arborescence;
   1.194 -    }
   1.195 -
   1.196 -    /// \brief Returns true if the arc is in the arborescence.
   1.197 -    ///
   1.198 -    /// Returns true if the arc is in the arborescence.
   1.199 -    /// \param arc The arc of the digraph.
   1.200 -    /// \pre \ref run() must be called before using this function.
   1.201 -    bool arborescence(Arc arc) const {
   1.202 -      return (*_pred)[_digraph->target(arc)] == arc;
   1.203 -    }
   1.204 -
   1.205 -    /// \brief Returns a reference to the pred map.
   1.206 -    ///
   1.207 -    /// Returns a reference to the pred map.
   1.208 -    const PredMap& predMap() const {
   1.209 -      return *_pred;
   1.210 -    }
   1.211 -
   1.212 -    /// \brief Returns the predecessor arc of the given node.
   1.213 -    ///
   1.214 -    /// Returns the predecessor arc of the given node.
   1.215 -    Arc pred(Node node) const {
   1.216 -      return (*_pred)[node];
   1.217 -    }
   1.218 -
   1.219 -    /// \brief Returns the cost of the arborescence.
   1.220 -    ///
   1.221 -    /// Returns the cost of the arborescence.
   1.222 -    Value arborescenceValue() const {
   1.223 -      Value sum = 0;
   1.224 -      for (ArcIt it(*_digraph); it != INVALID; ++it) {
   1.225 -        if (arborescence(it)) {
   1.226 -          sum += (*_cost)[it];
   1.227 -        }
   1.228 -      }
   1.229 -      return sum;
   1.230 -    }
   1.231 -
   1.232 -    /// \brief Indicates that a node is reachable from the sources.
   1.233 -    ///
   1.234 -    /// Indicates that a node is reachable from the sources.
   1.235 -    bool reached(Node node) const {
   1.236 -      return (*_node_order)[node] != -3;
   1.237 -    }
   1.238 -
   1.239 -    /// \brief Indicates that a node is processed.
   1.240 -    ///
   1.241 -    /// Indicates that a node is processed. The arborescence path exists
   1.242 -    /// from the source to the given node.
   1.243 -    bool processed(Node node) const {
   1.244 -      return (*_node_order)[node] == -1;
   1.245 -    }
   1.246 -
   1.247 -    /// \brief Returns the number of the dual variables in basis.
   1.248 -    ///
   1.249 -    /// Returns the number of the dual variables in basis.
   1.250 -    int dualNum() const {
   1.251 -      return _dual_variables.size();
   1.252 -    }
   1.253 -
   1.254 -    /// \brief Returns the value of the dual solution.
   1.255 -    ///
   1.256 -    /// Returns the value of the dual solution. It should be
   1.257 -    /// equal to the arborescence value.
   1.258 -    Value dualValue() const {
   1.259 -      Value sum = 0;
   1.260 -      for (int i = 0; i < int(_dual_variables.size()); ++i) {
   1.261 -        sum += _dual_variables[i].value;
   1.262 -      }
   1.263 -      return sum;
   1.264 -    }
   1.265 -
   1.266 -    /// \brief Returns the number of the nodes in the dual variable.
   1.267 -    ///
   1.268 -    /// Returns the number of the nodes in the dual variable.
   1.269 -    int dualSize(int k) const {
   1.270 -      return _dual_variables[k].end - _dual_variables[k].begin;
   1.271 -    }
   1.272 -
   1.273 -    /// \brief Returns the value of the dual variable.
   1.274 -    ///
   1.275 -    /// Returns the the value of the dual variable.
   1.276 -    const Value& dualValue(int k) const {
   1.277 -      return _dual_variables[k].value;
   1.278 -    }
   1.279 -
   1.280 -    /// \brief Lemon iterator for get a dual variable.
   1.281 -    ///
   1.282 -    /// Lemon iterator for get a dual variable. This class provides
   1.283 -    /// a common style lemon iterator which gives back a subset of
   1.284 -    /// the nodes.
   1.285 -    class DualIt {
   1.286 -    public:
   1.287 -
   1.288 -      /// \brief Constructor.
   1.289 -      ///
   1.290 -      /// Constructor for get the nodeset of the variable.
   1.291 -      DualIt(const MinCostArborescence& algorithm, int variable)
   1.292 -        : _algorithm(&algorithm)
   1.293 -      {
   1.294 -        _index = _algorithm->_dual_variables[variable].begin;
   1.295 -        _last = _algorithm->_dual_variables[variable].end;
   1.296 -      }
   1.297 -
   1.298 -      /// \brief Conversion to node.
   1.299 -      ///
   1.300 -      /// Conversion to node.
   1.301 -      operator Node() const {
   1.302 -        return _algorithm->_dual_node_list[_index];
   1.303 -      }
   1.304 -
   1.305 -      /// \brief Increment operator.
   1.306 -      ///
   1.307 -      /// Increment operator.
   1.308 -      DualIt& operator++() {
   1.309 -        ++_index;
   1.310 -        return *this;
   1.311 -      }
   1.312 -
   1.313 -      /// \brief Validity checking
   1.314 -      ///
   1.315 -      /// Checks whether the iterator is invalid.
   1.316 -      bool operator==(Invalid) const {
   1.317 -        return _index == _last;
   1.318 -      }
   1.319 -
   1.320 -      /// \brief Validity checking
   1.321 -      ///
   1.322 -      /// Checks whether the iterator is valid.
   1.323 -      bool operator!=(Invalid) const {
   1.324 -        return _index != _last;
   1.325 -      }
   1.326 -
   1.327 -    private:
   1.328 -      const MinCostArborescence* _algorithm;
   1.329 -      int _index, _last;
   1.330 -    };
   1.331 -
   1.332 -    /// @}
   1.333 -
   1.334      /// \name Execution Control
   1.335      /// The simplest way to execute the algorithm is to use
   1.336      /// one of the member functions called \c run(...). \n
   1.337 @@ -689,7 +544,7 @@
   1.338      ///
   1.339      /// \return The processed node.
   1.340      ///
   1.341 -    /// \warning The queue must not be empty!
   1.342 +    /// \warning The queue must not be empty.
   1.343      Node processNextNode() {
   1.344        Node node = queue.back();
   1.345        queue.pop_back();
   1.346 @@ -712,7 +567,8 @@
   1.347  
   1.348      /// \brief Returns the number of the nodes to be processed.
   1.349      ///
   1.350 -    /// Returns the number of the nodes to be processed.
   1.351 +    /// Returns the number of the nodes to be processed in the priority
   1.352 +    /// queue.
   1.353      int queueSize() const {
   1.354        return queue.size();
   1.355      }
   1.356 @@ -754,14 +610,170 @@
   1.357      /// mca.addSource(s);
   1.358      /// mca.start();
   1.359      /// \endcode
   1.360 -    void run(Node node) {
   1.361 +    void run(Node s) {
   1.362        init();
   1.363 -      addSource(node);
   1.364 +      addSource(s);
   1.365        start();
   1.366      }
   1.367  
   1.368      ///@}
   1.369  
   1.370 +    /// \name Query Functions
   1.371 +    /// The result of the %MinCostArborescence algorithm can be obtained
   1.372 +    /// using these functions.\n
   1.373 +    /// Either run() or start() must be called before using them.
   1.374 +
   1.375 +    /// @{
   1.376 +
   1.377 +    /// \brief Returns the cost of the arborescence.
   1.378 +    ///
   1.379 +    /// Returns the cost of the arborescence.
   1.380 +    Value arborescenceCost() const {
   1.381 +      Value sum = 0;
   1.382 +      for (ArcIt it(*_digraph); it != INVALID; ++it) {
   1.383 +        if (arborescence(it)) {
   1.384 +          sum += (*_cost)[it];
   1.385 +        }
   1.386 +      }
   1.387 +      return sum;
   1.388 +    }
   1.389 +
   1.390 +    /// \brief Returns \c true if the arc is in the arborescence.
   1.391 +    ///
   1.392 +    /// Returns \c true if the given arc is in the arborescence.
   1.393 +    /// \param arc An arc of the digraph.
   1.394 +    /// \pre \ref run() must be called before using this function.
   1.395 +    bool arborescence(Arc arc) const {
   1.396 +      return (*_pred)[_digraph->target(arc)] == arc;
   1.397 +    }
   1.398 +
   1.399 +    /// \brief Returns a const reference to the arborescence map.
   1.400 +    ///
   1.401 +    /// Returns a const reference to the arborescence map.
   1.402 +    /// \pre \ref run() must be called before using this function.
   1.403 +    const ArborescenceMap& arborescenceMap() const {
   1.404 +      return *_arborescence;
   1.405 +    }
   1.406 +
   1.407 +    /// \brief Returns the predecessor arc of the given node.
   1.408 +    ///
   1.409 +    /// Returns the predecessor arc of the given node.
   1.410 +    /// \pre \ref run() must be called before using this function.
   1.411 +    Arc pred(Node node) const {
   1.412 +      return (*_pred)[node];
   1.413 +    }
   1.414 +
   1.415 +    /// \brief Returns a const reference to the pred map.
   1.416 +    ///
   1.417 +    /// Returns a const reference to the pred map.
   1.418 +    /// \pre \ref run() must be called before using this function.
   1.419 +    const PredMap& predMap() const {
   1.420 +      return *_pred;
   1.421 +    }
   1.422 +
   1.423 +    /// \brief Indicates that a node is reachable from the sources.
   1.424 +    ///
   1.425 +    /// Indicates that a node is reachable from the sources.
   1.426 +    bool reached(Node node) const {
   1.427 +      return (*_node_order)[node] != -3;
   1.428 +    }
   1.429 +
   1.430 +    /// \brief Indicates that a node is processed.
   1.431 +    ///
   1.432 +    /// Indicates that a node is processed. The arborescence path exists
   1.433 +    /// from the source to the given node.
   1.434 +    bool processed(Node node) const {
   1.435 +      return (*_node_order)[node] == -1;
   1.436 +    }
   1.437 +
   1.438 +    /// \brief Returns the number of the dual variables in basis.
   1.439 +    ///
   1.440 +    /// Returns the number of the dual variables in basis.
   1.441 +    int dualNum() const {
   1.442 +      return _dual_variables.size();
   1.443 +    }
   1.444 +
   1.445 +    /// \brief Returns the value of the dual solution.
   1.446 +    ///
   1.447 +    /// Returns the value of the dual solution. It should be
   1.448 +    /// equal to the arborescence value.
   1.449 +    Value dualValue() const {
   1.450 +      Value sum = 0;
   1.451 +      for (int i = 0; i < int(_dual_variables.size()); ++i) {
   1.452 +        sum += _dual_variables[i].value;
   1.453 +      }
   1.454 +      return sum;
   1.455 +    }
   1.456 +
   1.457 +    /// \brief Returns the number of the nodes in the dual variable.
   1.458 +    ///
   1.459 +    /// Returns the number of the nodes in the dual variable.
   1.460 +    int dualSize(int k) const {
   1.461 +      return _dual_variables[k].end - _dual_variables[k].begin;
   1.462 +    }
   1.463 +
   1.464 +    /// \brief Returns the value of the dual variable.
   1.465 +    ///
   1.466 +    /// Returns the the value of the dual variable.
   1.467 +    Value dualValue(int k) const {
   1.468 +      return _dual_variables[k].value;
   1.469 +    }
   1.470 +
   1.471 +    /// \brief LEMON iterator for getting a dual variable.
   1.472 +    ///
   1.473 +    /// This class provides a common style LEMON iterator for getting a
   1.474 +    /// dual variable of \ref MinCostArborescence algorithm.
   1.475 +    /// It iterates over a subset of the nodes.
   1.476 +    class DualIt {
   1.477 +    public:
   1.478 +
   1.479 +      /// \brief Constructor.
   1.480 +      ///
   1.481 +      /// Constructor for getting the nodeset of the dual variable
   1.482 +      /// of \ref MinCostArborescence algorithm.
   1.483 +      DualIt(const MinCostArborescence& algorithm, int variable)
   1.484 +        : _algorithm(&algorithm)
   1.485 +      {
   1.486 +        _index = _algorithm->_dual_variables[variable].begin;
   1.487 +        _last = _algorithm->_dual_variables[variable].end;
   1.488 +      }
   1.489 +
   1.490 +      /// \brief Conversion to \c Node.
   1.491 +      ///
   1.492 +      /// Conversion to \c Node.
   1.493 +      operator Node() const {
   1.494 +        return _algorithm->_dual_node_list[_index];
   1.495 +      }
   1.496 +
   1.497 +      /// \brief Increment operator.
   1.498 +      ///
   1.499 +      /// Increment operator.
   1.500 +      DualIt& operator++() {
   1.501 +        ++_index;
   1.502 +        return *this;
   1.503 +      }
   1.504 +
   1.505 +      /// \brief Validity checking
   1.506 +      ///
   1.507 +      /// Checks whether the iterator is invalid.
   1.508 +      bool operator==(Invalid) const {
   1.509 +        return _index == _last;
   1.510 +      }
   1.511 +
   1.512 +      /// \brief Validity checking
   1.513 +      ///
   1.514 +      /// Checks whether the iterator is valid.
   1.515 +      bool operator!=(Invalid) const {
   1.516 +        return _index != _last;
   1.517 +      }
   1.518 +
   1.519 +    private:
   1.520 +      const MinCostArborescence* _algorithm;
   1.521 +      int _index, _last;
   1.522 +    };
   1.523 +
   1.524 +    /// @}
   1.525 +
   1.526    };
   1.527  
   1.528    /// \ingroup spantree
   1.529 @@ -769,11 +781,12 @@
   1.530    /// \brief Function type interface for MinCostArborescence algorithm.
   1.531    ///
   1.532    /// Function type interface for MinCostArborescence algorithm.
   1.533 -  /// \param digraph The Digraph that the algorithm runs on.
   1.534 -  /// \param cost The CostMap of the arcs.
   1.535 -  /// \param source The source of the arborescence.
   1.536 -  /// \retval arborescence The bool ArcMap which stores the arborescence.
   1.537 -  /// \return The cost of the arborescence.
   1.538 +  /// \param digraph The digraph the algorithm runs on.
   1.539 +  /// \param cost An arc map storing the costs.
   1.540 +  /// \param source The source node of the arborescence.
   1.541 +  /// \retval arborescence An arc map with \c bool (or convertible) value
   1.542 +  /// type that stores the arborescence.
   1.543 +  /// \return The total cost of the arborescence.
   1.544    ///
   1.545    /// \sa MinCostArborescence
   1.546    template <typename Digraph, typename CostMap, typename ArborescenceMap>
   1.547 @@ -782,11 +795,11 @@
   1.548                                                typename Digraph::Node source,
   1.549                                                ArborescenceMap& arborescence) {
   1.550      typename MinCostArborescence<Digraph, CostMap>
   1.551 -      ::template DefArborescenceMap<ArborescenceMap>
   1.552 +      ::template SetArborescenceMap<ArborescenceMap>
   1.553        ::Create mca(digraph, cost);
   1.554      mca.arborescenceMap(arborescence);
   1.555      mca.run(source);
   1.556 -    return mca.arborescenceValue();
   1.557 +    return mca.arborescenceCost();
   1.558    }
   1.559  
   1.560  }
     2.1 --- a/test/min_cost_arborescence_test.cc	Fri Apr 24 12:12:14 2009 +0100
     2.2 +++ b/test/min_cost_arborescence_test.cc	Sun Apr 26 16:44:53 2009 +0200
     2.3 @@ -24,6 +24,7 @@
     2.4  #include <lemon/smart_graph.h>
     2.5  #include <lemon/min_cost_arborescence.h>
     2.6  #include <lemon/lgf_reader.h>
     2.7 +#include <lemon/concepts/digraph.h>
     2.8  
     2.9  #include "test_tools.h"
    2.10  
    2.11 @@ -70,6 +71,65 @@
    2.12    "@attributes\n"
    2.13    "source 0\n";
    2.14  
    2.15 +
    2.16 +void checkMinCostArborescenceCompile()
    2.17 +{
    2.18 +  typedef double VType;
    2.19 +  typedef concepts::Digraph Digraph;
    2.20 +  typedef concepts::ReadMap<Digraph::Arc, VType> CostMap;
    2.21 +  typedef Digraph::Node Node;
    2.22 +  typedef Digraph::Arc Arc;
    2.23 +  typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap;
    2.24 +  typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap;
    2.25 +
    2.26 +  typedef MinCostArborescence<Digraph, CostMap>::
    2.27 +            SetArborescenceMap<ArbMap>::
    2.28 +            SetPredMap<PredMap>::Create MinCostArbType;
    2.29 +
    2.30 +  Digraph g;
    2.31 +  Node s, n;
    2.32 +  Arc e;
    2.33 +  VType c;
    2.34 +  bool b;
    2.35 +  int i;
    2.36 +  CostMap cost;
    2.37 +  ArbMap arb;
    2.38 +  PredMap pred;
    2.39 +
    2.40 +  MinCostArbType mcarb_test(g, cost);
    2.41 +  const MinCostArbType& const_mcarb_test = mcarb_test;
    2.42 +
    2.43 +  mcarb_test
    2.44 +    .arborescenceMap(arb)
    2.45 +    .predMap(pred)
    2.46 +    .run(s);
    2.47 +
    2.48 +  mcarb_test.init();
    2.49 +  mcarb_test.addSource(s);
    2.50 +  mcarb_test.start();
    2.51 +  n = mcarb_test.processNextNode();
    2.52 +  b = const_mcarb_test.emptyQueue();
    2.53 +  i = const_mcarb_test.queueSize();
    2.54 +  
    2.55 +  c = const_mcarb_test.arborescenceCost();
    2.56 +  b = const_mcarb_test.arborescence(e);
    2.57 +  e = const_mcarb_test.pred(n);
    2.58 +  const MinCostArbType::ArborescenceMap &am =
    2.59 +    const_mcarb_test.arborescenceMap();
    2.60 +  const MinCostArbType::PredMap &pm =
    2.61 +    const_mcarb_test.predMap();
    2.62 +  b = const_mcarb_test.reached(n);
    2.63 +  b = const_mcarb_test.processed(n);
    2.64 +  
    2.65 +  i = const_mcarb_test.dualNum();
    2.66 +  c = const_mcarb_test.dualValue();
    2.67 +  i = const_mcarb_test.dualSize(i);
    2.68 +  c = const_mcarb_test.dualValue(i);
    2.69 +  
    2.70 +  ignore_unused_variable_warning(am);
    2.71 +  ignore_unused_variable_warning(pm);
    2.72 +}
    2.73 +
    2.74  int main() {
    2.75    typedef SmartDigraph Digraph;
    2.76    DIGRAPH_TYPEDEFS(Digraph);
    2.77 @@ -110,19 +170,19 @@
    2.78          }
    2.79        }
    2.80        if (mca.arborescence(it)) {
    2.81 -        check(sum == cost[it], "INVALID DUAL");
    2.82 +        check(sum == cost[it], "Invalid dual solution");
    2.83        }
    2.84 -      check(sum <= cost[it], "INVALID DUAL");
    2.85 +      check(sum <= cost[it], "Invalid dual solution");
    2.86      }
    2.87    }
    2.88  
    2.89  
    2.90 -  check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
    2.91 +  check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution");
    2.92  
    2.93 -  check(mca.reached(source), "INVALID ARBORESCENCE");
    2.94 +  check(mca.reached(source), "Invalid arborescence");
    2.95    for (ArcIt a(digraph); a != INVALID; ++a) {
    2.96      check(!mca.reached(digraph.source(a)) ||
    2.97 -          mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
    2.98 +          mca.reached(digraph.target(a)), "Invalid arborescence");
    2.99    }
   2.100  
   2.101    for (NodeIt n(digraph); n != INVALID; ++n) {
   2.102 @@ -130,17 +190,17 @@
   2.103      int cnt = 0;
   2.104      for (InArcIt a(digraph, n); a != INVALID; ++a) {
   2.105        if (mca.arborescence(a)) {
   2.106 -        check(mca.pred(n) == a, "INVALID ARBORESCENCE");
   2.107 +        check(mca.pred(n) == a, "Invalid arborescence");
   2.108          ++cnt;
   2.109        }
   2.110      }
   2.111 -    check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
   2.112 +    check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence");
   2.113    }
   2.114  
   2.115    Digraph::ArcMap<bool> arborescence(digraph);
   2.116 -  check(mca.arborescenceValue() ==
   2.117 +  check(mca.arborescenceCost() ==
   2.118          minCostArborescence(digraph, cost, source, arborescence),
   2.119 -        "WRONG FUNCTION");
   2.120 +        "Wrong result of the function interface");
   2.121  
   2.122    return 0;
   2.123  }