lemon/min_cost_arborescence.h
changeset 766 97744b6dabf8
parent 584 33c6b6e755cd
child 713 4ac30454f1c1
equal deleted inserted replaced
3:92f4e8a63dcc 4:4fbe5ce76d8b
    34 
    34 
    35   /// \brief Default traits class for MinCostArborescence class.
    35   /// \brief Default traits class for MinCostArborescence class.
    36   ///
    36   ///
    37   /// Default traits class for MinCostArborescence class.
    37   /// Default traits class for MinCostArborescence class.
    38   /// \param GR Digraph type.
    38   /// \param GR Digraph type.
    39   /// \param CM Type of cost map.
    39   /// \param CM Type of the cost map.
    40   template <class GR, class CM>
    40   template <class GR, class CM>
    41   struct MinCostArborescenceDefaultTraits{
    41   struct MinCostArborescenceDefaultTraits{
    42 
    42 
    43     /// \brief The digraph type the algorithm runs on.
    43     /// \brief The digraph type the algorithm runs on.
    44     typedef GR Digraph;
    44     typedef GR Digraph;
    45 
    45 
    46     /// \brief The type of the map that stores the arc costs.
    46     /// \brief The type of the map that stores the arc costs.
    47     ///
    47     ///
    48     /// The type of the map that stores the arc costs.
    48     /// The type of the map that stores the arc costs.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    49     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef CM CostMap;
    50     typedef CM CostMap;
    51 
    51 
    52     /// \brief The value type of the costs.
    52     /// \brief The value type of the costs.
    53     ///
    53     ///
    54     /// The value type of the costs.
    54     /// The value type of the costs.
    56 
    56 
    57     /// \brief The type of the map that stores which arcs are in the
    57     /// \brief The type of the map that stores which arcs are in the
    58     /// arborescence.
    58     /// arborescence.
    59     ///
    59     ///
    60     /// The type of the map that stores which arcs are in the
    60     /// The type of the map that stores which arcs are in the
    61     /// arborescence.  It must meet the \ref concepts::WriteMap
    61     /// arborescence.  It must conform to the \ref concepts::WriteMap
    62     /// "WriteMap" concept.  Initially it will be set to false on each
    62     /// "WriteMap" concept, and its value type must be \c bool
    63     /// arc. After it will set all arborescence arcs once.
    63     /// (or convertible). Initially it will be set to \c false on each
       
    64     /// arc, then it will be set on each arborescence arc once.
    64     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    65     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    65 
    66 
    66     /// \brief Instantiates a \c ArborescenceMap.
    67     /// \brief Instantiates a \c ArborescenceMap.
    67     ///
    68     ///
    68     /// This function instantiates a \c ArborescenceMap.
    69     /// This function instantiates a \c ArborescenceMap.
    69     /// \param digraph is the graph, to which we would like to
    70     /// \param digraph The digraph to which we would like to calculate
    70     /// calculate the \c ArborescenceMap.
    71     /// the \c ArborescenceMap.
    71     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    72     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    72       return new ArborescenceMap(digraph);
    73       return new ArborescenceMap(digraph);
    73     }
    74     }
    74 
    75 
    75     /// \brief The type of the \c PredMap
    76     /// \brief The type of the \c PredMap
    76     ///
    77     ///
    77     /// The type of the \c PredMap. It is a node map with an arc value type.
    78     /// The type of the \c PredMap. It must confrom to the
       
    79     /// \ref concepts::WriteMap "WriteMap" concept, and its value type
       
    80     /// must be the \c Arc type of the digraph.
    78     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    81     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    79 
    82 
    80     /// \brief Instantiates a \c PredMap.
    83     /// \brief Instantiates a \c PredMap.
    81     ///
    84     ///
    82     /// This function instantiates a \c PredMap.
    85     /// This function instantiates a \c PredMap.
    90 
    93 
    91   /// \ingroup spantree
    94   /// \ingroup spantree
    92   ///
    95   ///
    93   /// \brief Minimum Cost Arborescence algorithm class.
    96   /// \brief Minimum Cost Arborescence algorithm class.
    94   ///
    97   ///
    95   /// This class provides an efficient implementation of
    98   /// This class provides an efficient implementation of the
    96   /// Minimum Cost Arborescence algorithm. The arborescence is a tree
    99   /// Minimum Cost Arborescence algorithm. The arborescence is a tree
    97   /// which is directed from a given source node of the digraph. One or
   100   /// which is directed from a given source node of the digraph. One or
    98   /// more sources should be given for the algorithm and it will calculate
   101   /// more sources should be given to the algorithm and it will calculate
    99   /// the minimum cost subgraph which are union of arborescences with the
   102   /// the minimum cost subgraph that is the union of arborescences with the
   100   /// given sources and spans all the nodes which are reachable from the
   103   /// given sources and spans all the nodes which are reachable from the
   101   /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
   104   /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
   102   ///
   105   ///
   103   /// The algorithm provides also an optimal dual solution, therefore
   106   /// The algorithm also provides an optimal dual solution, therefore
   104   /// the optimality of the solution can be checked.
   107   /// the optimality of the solution can be checked.
   105   ///
   108   ///
   106   /// \param GR The digraph type the algorithm runs on. The default value
   109   /// \param GR The digraph type the algorithm runs on.
   107   /// is \ref ListDigraph.
   110   /// \param CM A read-only arc map storing the costs of the
   108   /// \param CM This read-only ArcMap determines the costs of the
       
   109   /// arcs. It is read once for each arc, so the map may involve in
   111   /// arcs. It is read once for each arc, so the map may involve in
   110   /// relatively time consuming process to compute the arc cost if
   112   /// relatively time consuming process to compute the arc costs if
   111   /// it is necessary. The default map type is \ref
   113   /// it is necessary. The default map type is \ref
   112   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   114   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   113   /// \param TR Traits class to set various data types used
   115   /// \param TR Traits class to set various data types used
   114   /// by the algorithm. The default traits class is
   116   /// by the algorithm. The default traits class is
   115   /// \ref MinCostArborescenceDefaultTraits
   117   /// \ref MinCostArborescenceDefaultTraits
   116   /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
   118   /// "MinCostArborescenceDefaultTraits<GR, CM>".
   117   /// MinCostArborescenceDefaultTraits for the documentation of a
       
   118   /// MinCostArborescence traits class.
       
   119 #ifndef DOXYGEN
   119 #ifndef DOXYGEN
   120   template <typename GR = ListDigraph,
   120   template <typename GR,
   121             typename CM = typename GR::template ArcMap<int>,
   121             typename CM = typename GR::template ArcMap<int>,
   122             typename TR =
   122             typename TR =
   123               MinCostArborescenceDefaultTraits<GR, CM> >
   123               MinCostArborescenceDefaultTraits<GR, CM> >
   124 #else
   124 #else
   125   template <typename GR, typename CM, typedef TR>
   125   template <typename GR, typename CM, typedef TR>
   126 #endif
   126 #endif
   127   class MinCostArborescence {
   127   class MinCostArborescence {
   128   public:
   128   public:
   129 
   129 
   130     /// The traits.
   130     /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
       
   131     /// of the algorithm. 
   131     typedef TR Traits;
   132     typedef TR Traits;
   132     /// The type of the underlying digraph.
   133     /// The type of the underlying digraph.
   133     typedef typename Traits::Digraph Digraph;
   134     typedef typename Traits::Digraph Digraph;
   134     /// The type of the map that stores the arc costs.
   135     /// The type of the map that stores the arc costs.
   135     typedef typename Traits::CostMap CostMap;
   136     typedef typename Traits::CostMap CostMap;
   393     /// \name Named Template Parameters
   394     /// \name Named Template Parameters
   394 
   395 
   395     /// @{
   396     /// @{
   396 
   397 
   397     template <class T>
   398     template <class T>
   398     struct DefArborescenceMapTraits : public Traits {
   399     struct SetArborescenceMapTraits : public Traits {
   399       typedef T ArborescenceMap;
   400       typedef T ArborescenceMap;
   400       static ArborescenceMap *createArborescenceMap(const Digraph &)
   401       static ArborescenceMap *createArborescenceMap(const Digraph &)
   401       {
   402       {
   402         LEMON_ASSERT(false, "ArborescenceMap is not initialized");
   403         LEMON_ASSERT(false, "ArborescenceMap is not initialized");
   403         return 0; // ignore warnings
   404         return 0; // ignore warnings
   404       }
   405       }
   405     };
   406     };
   406 
   407 
   407     /// \brief \ref named-templ-param "Named parameter" for
   408     /// \brief \ref named-templ-param "Named parameter" for
   408     /// setting ArborescenceMap type
   409     /// setting \c ArborescenceMap type
   409     ///
   410     ///
   410     /// \ref named-templ-param "Named parameter" for setting
   411     /// \ref named-templ-param "Named parameter" for setting
   411     /// ArborescenceMap type
   412     /// \c ArborescenceMap type.
       
   413     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
       
   414     /// and its value type must be \c bool (or convertible).
       
   415     /// Initially it will be set to \c false on each arc,
       
   416     /// then it will be set on each arborescence arc once.
   412     template <class T>
   417     template <class T>
   413     struct DefArborescenceMap
   418     struct SetArborescenceMap
   414       : public MinCostArborescence<Digraph, CostMap,
   419       : public MinCostArborescence<Digraph, CostMap,
   415                                    DefArborescenceMapTraits<T> > {
   420                                    SetArborescenceMapTraits<T> > {
   416     };
   421     };
   417 
   422 
   418     template <class T>
   423     template <class T>
   419     struct DefPredMapTraits : public Traits {
   424     struct SetPredMapTraits : public Traits {
   420       typedef T PredMap;
   425       typedef T PredMap;
   421       static PredMap *createPredMap(const Digraph &)
   426       static PredMap *createPredMap(const Digraph &)
   422       {
   427       {
   423         LEMON_ASSERT(false, "PredMap is not initialized");
   428         LEMON_ASSERT(false, "PredMap is not initialized");
       
   429         return 0; // ignore warnings
   424       }
   430       }
   425     };
   431     };
   426 
   432 
   427     /// \brief \ref named-templ-param "Named parameter" for
   433     /// \brief \ref named-templ-param "Named parameter" for
   428     /// setting PredMap type
   434     /// setting \c PredMap type
   429     ///
   435     ///
   430     /// \ref named-templ-param "Named parameter" for setting
   436     /// \ref named-templ-param "Named parameter" for setting
   431     /// PredMap type
   437     /// \c PredMap type.
       
   438     /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 
       
   439     /// and its value type must be the \c Arc type of the digraph.
   432     template <class T>
   440     template <class T>
   433     struct DefPredMap
   441     struct SetPredMap
   434       : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
   442       : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
   435     };
   443     };
   436 
   444 
   437     /// @}
   445     /// @}
   438 
   446 
   439     /// \brief Constructor.
   447     /// \brief Constructor.
   462       local_arborescence = false;
   470       local_arborescence = false;
   463       _arborescence = &m;
   471       _arborescence = &m;
   464       return *this;
   472       return *this;
   465     }
   473     }
   466 
   474 
   467     /// \brief Sets the arborescence map.
   475     /// \brief Sets the predecessor map.
   468     ///
   476     ///
   469     /// Sets the arborescence map.
   477     /// Sets the predecessor map.
   470     /// \return <tt>(*this)</tt>
   478     /// \return <tt>(*this)</tt>
   471     MinCostArborescence& predMap(PredMap& m) {
   479     MinCostArborescence& predMap(PredMap& m) {
   472       if (local_pred) {
   480       if (local_pred) {
   473         delete _pred;
   481         delete _pred;
   474       }
   482       }
   475       local_pred = false;
   483       local_pred = false;
   476       _pred = &m;
   484       _pred = &m;
   477       return *this;
   485       return *this;
   478     }
   486     }
   479 
       
   480     /// \name Query Functions
       
   481     /// The result of the %MinCostArborescence algorithm can be obtained
       
   482     /// using these functions.\n
       
   483     /// Before the use of these functions,
       
   484     /// either run() or start() must be called.
       
   485 
       
   486     /// @{
       
   487 
       
   488     /// \brief Returns a reference to the arborescence map.
       
   489     ///
       
   490     /// Returns a reference to the arborescence map.
       
   491     const ArborescenceMap& arborescenceMap() const {
       
   492       return *_arborescence;
       
   493     }
       
   494 
       
   495     /// \brief Returns true if the arc is in the arborescence.
       
   496     ///
       
   497     /// Returns true if the arc is in the arborescence.
       
   498     /// \param arc The arc of the digraph.
       
   499     /// \pre \ref run() must be called before using this function.
       
   500     bool arborescence(Arc arc) const {
       
   501       return (*_pred)[_digraph->target(arc)] == arc;
       
   502     }
       
   503 
       
   504     /// \brief Returns a reference to the pred map.
       
   505     ///
       
   506     /// Returns a reference to the pred map.
       
   507     const PredMap& predMap() const {
       
   508       return *_pred;
       
   509     }
       
   510 
       
   511     /// \brief Returns the predecessor arc of the given node.
       
   512     ///
       
   513     /// Returns the predecessor arc of the given node.
       
   514     Arc pred(Node node) const {
       
   515       return (*_pred)[node];
       
   516     }
       
   517 
       
   518     /// \brief Returns the cost of the arborescence.
       
   519     ///
       
   520     /// Returns the cost of the arborescence.
       
   521     Value arborescenceValue() const {
       
   522       Value sum = 0;
       
   523       for (ArcIt it(*_digraph); it != INVALID; ++it) {
       
   524         if (arborescence(it)) {
       
   525           sum += (*_cost)[it];
       
   526         }
       
   527       }
       
   528       return sum;
       
   529     }
       
   530 
       
   531     /// \brief Indicates that a node is reachable from the sources.
       
   532     ///
       
   533     /// Indicates that a node is reachable from the sources.
       
   534     bool reached(Node node) const {
       
   535       return (*_node_order)[node] != -3;
       
   536     }
       
   537 
       
   538     /// \brief Indicates that a node is processed.
       
   539     ///
       
   540     /// Indicates that a node is processed. The arborescence path exists
       
   541     /// from the source to the given node.
       
   542     bool processed(Node node) const {
       
   543       return (*_node_order)[node] == -1;
       
   544     }
       
   545 
       
   546     /// \brief Returns the number of the dual variables in basis.
       
   547     ///
       
   548     /// Returns the number of the dual variables in basis.
       
   549     int dualNum() const {
       
   550       return _dual_variables.size();
       
   551     }
       
   552 
       
   553     /// \brief Returns the value of the dual solution.
       
   554     ///
       
   555     /// Returns the value of the dual solution. It should be
       
   556     /// equal to the arborescence value.
       
   557     Value dualValue() const {
       
   558       Value sum = 0;
       
   559       for (int i = 0; i < int(_dual_variables.size()); ++i) {
       
   560         sum += _dual_variables[i].value;
       
   561       }
       
   562       return sum;
       
   563     }
       
   564 
       
   565     /// \brief Returns the number of the nodes in the dual variable.
       
   566     ///
       
   567     /// Returns the number of the nodes in the dual variable.
       
   568     int dualSize(int k) const {
       
   569       return _dual_variables[k].end - _dual_variables[k].begin;
       
   570     }
       
   571 
       
   572     /// \brief Returns the value of the dual variable.
       
   573     ///
       
   574     /// Returns the the value of the dual variable.
       
   575     const Value& dualValue(int k) const {
       
   576       return _dual_variables[k].value;
       
   577     }
       
   578 
       
   579     /// \brief Lemon iterator for get a dual variable.
       
   580     ///
       
   581     /// Lemon iterator for get a dual variable. This class provides
       
   582     /// a common style lemon iterator which gives back a subset of
       
   583     /// the nodes.
       
   584     class DualIt {
       
   585     public:
       
   586 
       
   587       /// \brief Constructor.
       
   588       ///
       
   589       /// Constructor for get the nodeset of the variable.
       
   590       DualIt(const MinCostArborescence& algorithm, int variable)
       
   591         : _algorithm(&algorithm)
       
   592       {
       
   593         _index = _algorithm->_dual_variables[variable].begin;
       
   594         _last = _algorithm->_dual_variables[variable].end;
       
   595       }
       
   596 
       
   597       /// \brief Conversion to node.
       
   598       ///
       
   599       /// Conversion to node.
       
   600       operator Node() const {
       
   601         return _algorithm->_dual_node_list[_index];
       
   602       }
       
   603 
       
   604       /// \brief Increment operator.
       
   605       ///
       
   606       /// Increment operator.
       
   607       DualIt& operator++() {
       
   608         ++_index;
       
   609         return *this;
       
   610       }
       
   611 
       
   612       /// \brief Validity checking
       
   613       ///
       
   614       /// Checks whether the iterator is invalid.
       
   615       bool operator==(Invalid) const {
       
   616         return _index == _last;
       
   617       }
       
   618 
       
   619       /// \brief Validity checking
       
   620       ///
       
   621       /// Checks whether the iterator is valid.
       
   622       bool operator!=(Invalid) const {
       
   623         return _index != _last;
       
   624       }
       
   625 
       
   626     private:
       
   627       const MinCostArborescence* _algorithm;
       
   628       int _index, _last;
       
   629     };
       
   630 
       
   631     /// @}
       
   632 
   487 
   633     /// \name Execution Control
   488     /// \name Execution Control
   634     /// The simplest way to execute the algorithm is to use
   489     /// The simplest way to execute the algorithm is to use
   635     /// one of the member functions called \c run(...). \n
   490     /// one of the member functions called \c run(...). \n
   636     /// If you need more control on the execution,
   491     /// If you need more control on the execution,
   687     ///
   542     ///
   688     /// Processes the next node in the priority queue.
   543     /// Processes the next node in the priority queue.
   689     ///
   544     ///
   690     /// \return The processed node.
   545     /// \return The processed node.
   691     ///
   546     ///
   692     /// \warning The queue must not be empty!
   547     /// \warning The queue must not be empty.
   693     Node processNextNode() {
   548     Node processNextNode() {
   694       Node node = queue.back();
   549       Node node = queue.back();
   695       queue.pop_back();
   550       queue.pop_back();
   696       if ((*_node_order)[node] == -2) {
   551       if ((*_node_order)[node] == -2) {
   697         Arc arc = prepare(node);
   552         Arc arc = prepare(node);
   710       return node;
   565       return node;
   711     }
   566     }
   712 
   567 
   713     /// \brief Returns the number of the nodes to be processed.
   568     /// \brief Returns the number of the nodes to be processed.
   714     ///
   569     ///
   715     /// Returns the number of the nodes to be processed.
   570     /// Returns the number of the nodes to be processed in the priority
       
   571     /// queue.
   716     int queueSize() const {
   572     int queueSize() const {
   717       return queue.size();
   573       return queue.size();
   718     }
   574     }
   719 
   575 
   720     /// \brief Returns \c false if there are nodes to be processed.
   576     /// \brief Returns \c false if there are nodes to be processed.
   752     /// \code
   608     /// \code
   753     /// mca.init();
   609     /// mca.init();
   754     /// mca.addSource(s);
   610     /// mca.addSource(s);
   755     /// mca.start();
   611     /// mca.start();
   756     /// \endcode
   612     /// \endcode
   757     void run(Node node) {
   613     void run(Node s) {
   758       init();
   614       init();
   759       addSource(node);
   615       addSource(s);
   760       start();
   616       start();
   761     }
   617     }
   762 
   618 
   763     ///@}
   619     ///@}
       
   620 
       
   621     /// \name Query Functions
       
   622     /// The result of the %MinCostArborescence algorithm can be obtained
       
   623     /// using these functions.\n
       
   624     /// Either run() or start() must be called before using them.
       
   625 
       
   626     /// @{
       
   627 
       
   628     /// \brief Returns the cost of the arborescence.
       
   629     ///
       
   630     /// Returns the cost of the arborescence.
       
   631     Value arborescenceCost() const {
       
   632       Value sum = 0;
       
   633       for (ArcIt it(*_digraph); it != INVALID; ++it) {
       
   634         if (arborescence(it)) {
       
   635           sum += (*_cost)[it];
       
   636         }
       
   637       }
       
   638       return sum;
       
   639     }
       
   640 
       
   641     /// \brief Returns \c true if the arc is in the arborescence.
       
   642     ///
       
   643     /// Returns \c true if the given arc is in the arborescence.
       
   644     /// \param arc An arc of the digraph.
       
   645     /// \pre \ref run() must be called before using this function.
       
   646     bool arborescence(Arc arc) const {
       
   647       return (*_pred)[_digraph->target(arc)] == arc;
       
   648     }
       
   649 
       
   650     /// \brief Returns a const reference to the arborescence map.
       
   651     ///
       
   652     /// Returns a const reference to the arborescence map.
       
   653     /// \pre \ref run() must be called before using this function.
       
   654     const ArborescenceMap& arborescenceMap() const {
       
   655       return *_arborescence;
       
   656     }
       
   657 
       
   658     /// \brief Returns the predecessor arc of the given node.
       
   659     ///
       
   660     /// Returns the predecessor arc of the given node.
       
   661     /// \pre \ref run() must be called before using this function.
       
   662     Arc pred(Node node) const {
       
   663       return (*_pred)[node];
       
   664     }
       
   665 
       
   666     /// \brief Returns a const reference to the pred map.
       
   667     ///
       
   668     /// Returns a const reference to the pred map.
       
   669     /// \pre \ref run() must be called before using this function.
       
   670     const PredMap& predMap() const {
       
   671       return *_pred;
       
   672     }
       
   673 
       
   674     /// \brief Indicates that a node is reachable from the sources.
       
   675     ///
       
   676     /// Indicates that a node is reachable from the sources.
       
   677     bool reached(Node node) const {
       
   678       return (*_node_order)[node] != -3;
       
   679     }
       
   680 
       
   681     /// \brief Indicates that a node is processed.
       
   682     ///
       
   683     /// Indicates that a node is processed. The arborescence path exists
       
   684     /// from the source to the given node.
       
   685     bool processed(Node node) const {
       
   686       return (*_node_order)[node] == -1;
       
   687     }
       
   688 
       
   689     /// \brief Returns the number of the dual variables in basis.
       
   690     ///
       
   691     /// Returns the number of the dual variables in basis.
       
   692     int dualNum() const {
       
   693       return _dual_variables.size();
       
   694     }
       
   695 
       
   696     /// \brief Returns the value of the dual solution.
       
   697     ///
       
   698     /// Returns the value of the dual solution. It should be
       
   699     /// equal to the arborescence value.
       
   700     Value dualValue() const {
       
   701       Value sum = 0;
       
   702       for (int i = 0; i < int(_dual_variables.size()); ++i) {
       
   703         sum += _dual_variables[i].value;
       
   704       }
       
   705       return sum;
       
   706     }
       
   707 
       
   708     /// \brief Returns the number of the nodes in the dual variable.
       
   709     ///
       
   710     /// Returns the number of the nodes in the dual variable.
       
   711     int dualSize(int k) const {
       
   712       return _dual_variables[k].end - _dual_variables[k].begin;
       
   713     }
       
   714 
       
   715     /// \brief Returns the value of the dual variable.
       
   716     ///
       
   717     /// Returns the the value of the dual variable.
       
   718     Value dualValue(int k) const {
       
   719       return _dual_variables[k].value;
       
   720     }
       
   721 
       
   722     /// \brief LEMON iterator for getting a dual variable.
       
   723     ///
       
   724     /// This class provides a common style LEMON iterator for getting a
       
   725     /// dual variable of \ref MinCostArborescence algorithm.
       
   726     /// It iterates over a subset of the nodes.
       
   727     class DualIt {
       
   728     public:
       
   729 
       
   730       /// \brief Constructor.
       
   731       ///
       
   732       /// Constructor for getting the nodeset of the dual variable
       
   733       /// of \ref MinCostArborescence algorithm.
       
   734       DualIt(const MinCostArborescence& algorithm, int variable)
       
   735         : _algorithm(&algorithm)
       
   736       {
       
   737         _index = _algorithm->_dual_variables[variable].begin;
       
   738         _last = _algorithm->_dual_variables[variable].end;
       
   739       }
       
   740 
       
   741       /// \brief Conversion to \c Node.
       
   742       ///
       
   743       /// Conversion to \c Node.
       
   744       operator Node() const {
       
   745         return _algorithm->_dual_node_list[_index];
       
   746       }
       
   747 
       
   748       /// \brief Increment operator.
       
   749       ///
       
   750       /// Increment operator.
       
   751       DualIt& operator++() {
       
   752         ++_index;
       
   753         return *this;
       
   754       }
       
   755 
       
   756       /// \brief Validity checking
       
   757       ///
       
   758       /// Checks whether the iterator is invalid.
       
   759       bool operator==(Invalid) const {
       
   760         return _index == _last;
       
   761       }
       
   762 
       
   763       /// \brief Validity checking
       
   764       ///
       
   765       /// Checks whether the iterator is valid.
       
   766       bool operator!=(Invalid) const {
       
   767         return _index != _last;
       
   768       }
       
   769 
       
   770     private:
       
   771       const MinCostArborescence* _algorithm;
       
   772       int _index, _last;
       
   773     };
       
   774 
       
   775     /// @}
   764 
   776 
   765   };
   777   };
   766 
   778 
   767   /// \ingroup spantree
   779   /// \ingroup spantree
   768   ///
   780   ///
   769   /// \brief Function type interface for MinCostArborescence algorithm.
   781   /// \brief Function type interface for MinCostArborescence algorithm.
   770   ///
   782   ///
   771   /// Function type interface for MinCostArborescence algorithm.
   783   /// Function type interface for MinCostArborescence algorithm.
   772   /// \param digraph The Digraph that the algorithm runs on.
   784   /// \param digraph The digraph the algorithm runs on.
   773   /// \param cost The CostMap of the arcs.
   785   /// \param cost An arc map storing the costs.
   774   /// \param source The source of the arborescence.
   786   /// \param source The source node of the arborescence.
   775   /// \retval arborescence The bool ArcMap which stores the arborescence.
   787   /// \retval arborescence An arc map with \c bool (or convertible) value
   776   /// \return The cost of the arborescence.
   788   /// type that stores the arborescence.
       
   789   /// \return The total cost of the arborescence.
   777   ///
   790   ///
   778   /// \sa MinCostArborescence
   791   /// \sa MinCostArborescence
   779   template <typename Digraph, typename CostMap, typename ArborescenceMap>
   792   template <typename Digraph, typename CostMap, typename ArborescenceMap>
   780   typename CostMap::Value minCostArborescence(const Digraph& digraph,
   793   typename CostMap::Value minCostArborescence(const Digraph& digraph,
   781                                               const CostMap& cost,
   794                                               const CostMap& cost,
   782                                               typename Digraph::Node source,
   795                                               typename Digraph::Node source,
   783                                               ArborescenceMap& arborescence) {
   796                                               ArborescenceMap& arborescence) {
   784     typename MinCostArborescence<Digraph, CostMap>
   797     typename MinCostArborescence<Digraph, CostMap>
   785       ::template DefArborescenceMap<ArborescenceMap>
   798       ::template SetArborescenceMap<ArborescenceMap>
   786       ::Create mca(digraph, cost);
   799       ::Create mca(digraph, cost);
   787     mca.arborescenceMap(arborescence);
   800     mca.arborescenceMap(arborescence);
   788     mca.run(source);
   801     mca.run(source);
   789     return mca.arborescenceValue();
   802     return mca.arborescenceCost();
   790   }
   803   }
   791 
   804 
   792 }
   805 }
   793 
   806 
   794 #endif
   807 #endif