lemon/min_cost_arborescence.h
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 17 Feb 2010 23:10:36 +0100
changeset 836 c841ae1aca29
parent 713 4ac30454f1c1
child 877 141f9c0db4a3
permissions -rw-r--r--
Modify the header of scripts/bib2dox.py (#184)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_MIN_COST_ARBORESCENCE_H
    20 #define LEMON_MIN_COST_ARBORESCENCE_H
    21 
    22 ///\ingroup spantree
    23 ///\file
    24 ///\brief Minimum Cost Arborescence algorithm.
    25 
    26 #include <vector>
    27 
    28 #include <lemon/list_graph.h>
    29 #include <lemon/bin_heap.h>
    30 #include <lemon/assert.h>
    31 
    32 namespace lemon {
    33 
    34 
    35   /// \brief Default traits class for MinCostArborescence class.
    36   ///
    37   /// Default traits class for MinCostArborescence class.
    38   /// \param GR Digraph type.
    39   /// \param CM Type of the cost map.
    40   template <class GR, class CM>
    41   struct MinCostArborescenceDefaultTraits{
    42 
    43     /// \brief The digraph type the algorithm runs on.
    44     typedef GR Digraph;
    45 
    46     /// \brief The type of the map that stores the arc costs.
    47     ///
    48     /// The type of the map that stores the arc costs.
    49     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef CM CostMap;
    51 
    52     /// \brief The value type of the costs.
    53     ///
    54     /// The value type of the costs.
    55     typedef typename CostMap::Value Value;
    56 
    57     /// \brief The type of the map that stores which arcs are in the
    58     /// arborescence.
    59     ///
    60     /// The type of the map that stores which arcs are in the
    61     /// arborescence.  It must conform to the \ref concepts::WriteMap
    62     /// "WriteMap" concept, and its value type must be \c bool
    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.
    65     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    66 
    67     /// \brief Instantiates a \c ArborescenceMap.
    68     ///
    69     /// This function instantiates a \c ArborescenceMap.
    70     /// \param digraph The digraph to which we would like to calculate
    71     /// the \c ArborescenceMap.
    72     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    73       return new ArborescenceMap(digraph);
    74     }
    75 
    76     /// \brief The type of the \c PredMap
    77     ///
    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.
    81     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    82 
    83     /// \brief Instantiates a \c PredMap.
    84     ///
    85     /// This function instantiates a \c PredMap.
    86     /// \param digraph The digraph to which we would like to define the
    87     /// \c PredMap.
    88     static PredMap *createPredMap(const Digraph &digraph){
    89       return new PredMap(digraph);
    90     }
    91 
    92   };
    93 
    94   /// \ingroup spantree
    95   ///
    96   /// \brief Minimum Cost Arborescence algorithm class.
    97   ///
    98   /// This class provides an efficient implementation of the
    99   /// Minimum Cost Arborescence algorithm. The arborescence is a tree
   100   /// which is directed from a given source node of the digraph. One or
   101   /// more sources should be given to the algorithm and it will calculate
   102   /// the minimum cost subgraph that is the union of arborescences with the
   103   /// given sources and spans all the nodes which are reachable from the
   104   /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
   105   ///
   106   /// The algorithm also provides an optimal dual solution, therefore
   107   /// the optimality of the solution can be checked.
   108   ///
   109   /// \param GR The digraph type the algorithm runs on.
   110   /// \param CM A read-only arc map storing the costs of the
   111   /// arcs. It is read once for each arc, so the map may involve in
   112   /// relatively time consuming process to compute the arc costs if
   113   /// it is necessary. The default map type is \ref
   114   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   115   /// \tparam TR The traits class that defines various types used by the
   116   /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
   117   /// "MinCostArborescenceDefaultTraits<GR, CM>".
   118   /// In most cases, this parameter should not be set directly,
   119   /// consider to use the named template parameters instead.
   120 #ifndef DOXYGEN
   121   template <typename GR,
   122             typename CM = typename GR::template ArcMap<int>,
   123             typename TR =
   124               MinCostArborescenceDefaultTraits<GR, CM> >
   125 #else
   126   template <typename GR, typename CM, typename TR>
   127 #endif
   128   class MinCostArborescence {
   129   public:
   130 
   131     /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
   132     /// of the algorithm. 
   133     typedef TR Traits;
   134     /// The type of the underlying digraph.
   135     typedef typename Traits::Digraph Digraph;
   136     /// The type of the map that stores the arc costs.
   137     typedef typename Traits::CostMap CostMap;
   138     ///The type of the costs of the arcs.
   139     typedef typename Traits::Value Value;
   140     ///The type of the predecessor map.
   141     typedef typename Traits::PredMap PredMap;
   142     ///The type of the map that stores which arcs are in the arborescence.
   143     typedef typename Traits::ArborescenceMap ArborescenceMap;
   144 
   145     typedef MinCostArborescence Create;
   146 
   147   private:
   148 
   149     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   150 
   151     struct CostArc {
   152 
   153       Arc arc;
   154       Value value;
   155 
   156       CostArc() {}
   157       CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
   158 
   159     };
   160 
   161     const Digraph *_digraph;
   162     const CostMap *_cost;
   163 
   164     PredMap *_pred;
   165     bool local_pred;
   166 
   167     ArborescenceMap *_arborescence;
   168     bool local_arborescence;
   169 
   170     typedef typename Digraph::template ArcMap<int> ArcOrder;
   171     ArcOrder *_arc_order;
   172 
   173     typedef typename Digraph::template NodeMap<int> NodeOrder;
   174     NodeOrder *_node_order;
   175 
   176     typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
   177     CostArcMap *_cost_arcs;
   178 
   179     struct StackLevel {
   180 
   181       std::vector<CostArc> arcs;
   182       int node_level;
   183 
   184     };
   185 
   186     std::vector<StackLevel> level_stack;
   187     std::vector<Node> queue;
   188 
   189     typedef std::vector<typename Digraph::Node> DualNodeList;
   190 
   191     DualNodeList _dual_node_list;
   192 
   193     struct DualVariable {
   194       int begin, end;
   195       Value value;
   196 
   197       DualVariable(int _begin, int _end, Value _value)
   198         : begin(_begin), end(_end), value(_value) {}
   199 
   200     };
   201 
   202     typedef std::vector<DualVariable> DualVariables;
   203 
   204     DualVariables _dual_variables;
   205 
   206     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
   207 
   208     HeapCrossRef *_heap_cross_ref;
   209 
   210     typedef BinHeap<int, HeapCrossRef> Heap;
   211 
   212     Heap *_heap;
   213 
   214   protected:
   215 
   216     MinCostArborescence() {}
   217 
   218   private:
   219 
   220     void createStructures() {
   221       if (!_pred) {
   222         local_pred = true;
   223         _pred = Traits::createPredMap(*_digraph);
   224       }
   225       if (!_arborescence) {
   226         local_arborescence = true;
   227         _arborescence = Traits::createArborescenceMap(*_digraph);
   228       }
   229       if (!_arc_order) {
   230         _arc_order = new ArcOrder(*_digraph);
   231       }
   232       if (!_node_order) {
   233         _node_order = new NodeOrder(*_digraph);
   234       }
   235       if (!_cost_arcs) {
   236         _cost_arcs = new CostArcMap(*_digraph);
   237       }
   238       if (!_heap_cross_ref) {
   239         _heap_cross_ref = new HeapCrossRef(*_digraph, -1);
   240       }
   241       if (!_heap) {
   242         _heap = new Heap(*_heap_cross_ref);
   243       }
   244     }
   245 
   246     void destroyStructures() {
   247       if (local_arborescence) {
   248         delete _arborescence;
   249       }
   250       if (local_pred) {
   251         delete _pred;
   252       }
   253       if (_arc_order) {
   254         delete _arc_order;
   255       }
   256       if (_node_order) {
   257         delete _node_order;
   258       }
   259       if (_cost_arcs) {
   260         delete _cost_arcs;
   261       }
   262       if (_heap) {
   263         delete _heap;
   264       }
   265       if (_heap_cross_ref) {
   266         delete _heap_cross_ref;
   267       }
   268     }
   269 
   270     Arc prepare(Node node) {
   271       std::vector<Node> nodes;
   272       (*_node_order)[node] = _dual_node_list.size();
   273       StackLevel level;
   274       level.node_level = _dual_node_list.size();
   275       _dual_node_list.push_back(node);
   276       for (InArcIt it(*_digraph, node); it != INVALID; ++it) {
   277         Arc arc = it;
   278         Node source = _digraph->source(arc);
   279         Value value = (*_cost)[it];
   280         if (source == node || (*_node_order)[source] == -3) continue;
   281         if ((*_cost_arcs)[source].arc == INVALID) {
   282           (*_cost_arcs)[source].arc = arc;
   283           (*_cost_arcs)[source].value = value;
   284           nodes.push_back(source);
   285         } else {
   286           if ((*_cost_arcs)[source].value > value) {
   287             (*_cost_arcs)[source].arc = arc;
   288             (*_cost_arcs)[source].value = value;
   289           }
   290         }
   291       }
   292       CostArc minimum = (*_cost_arcs)[nodes[0]];
   293       for (int i = 1; i < int(nodes.size()); ++i) {
   294         if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
   295           minimum = (*_cost_arcs)[nodes[i]];
   296         }
   297       }
   298       (*_arc_order)[minimum.arc] = _dual_variables.size();
   299       DualVariable var(_dual_node_list.size() - 1,
   300                        _dual_node_list.size(), minimum.value);
   301       _dual_variables.push_back(var);
   302       for (int i = 0; i < int(nodes.size()); ++i) {
   303         (*_cost_arcs)[nodes[i]].value -= minimum.value;
   304         level.arcs.push_back((*_cost_arcs)[nodes[i]]);
   305         (*_cost_arcs)[nodes[i]].arc = INVALID;
   306       }
   307       level_stack.push_back(level);
   308       return minimum.arc;
   309     }
   310 
   311     Arc contract(Node node) {
   312       int node_bottom = bottom(node);
   313       std::vector<Node> nodes;
   314       while (!level_stack.empty() &&
   315              level_stack.back().node_level >= node_bottom) {
   316         for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
   317           Arc arc = level_stack.back().arcs[i].arc;
   318           Node source = _digraph->source(arc);
   319           Value value = level_stack.back().arcs[i].value;
   320           if ((*_node_order)[source] >= node_bottom) continue;
   321           if ((*_cost_arcs)[source].arc == INVALID) {
   322             (*_cost_arcs)[source].arc = arc;
   323             (*_cost_arcs)[source].value = value;
   324             nodes.push_back(source);
   325           } else {
   326             if ((*_cost_arcs)[source].value > value) {
   327               (*_cost_arcs)[source].arc = arc;
   328               (*_cost_arcs)[source].value = value;
   329             }
   330           }
   331         }
   332         level_stack.pop_back();
   333       }
   334       CostArc minimum = (*_cost_arcs)[nodes[0]];
   335       for (int i = 1; i < int(nodes.size()); ++i) {
   336         if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
   337           minimum = (*_cost_arcs)[nodes[i]];
   338         }
   339       }
   340       (*_arc_order)[minimum.arc] = _dual_variables.size();
   341       DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
   342       _dual_variables.push_back(var);
   343       StackLevel level;
   344       level.node_level = node_bottom;
   345       for (int i = 0; i < int(nodes.size()); ++i) {
   346         (*_cost_arcs)[nodes[i]].value -= minimum.value;
   347         level.arcs.push_back((*_cost_arcs)[nodes[i]]);
   348         (*_cost_arcs)[nodes[i]].arc = INVALID;
   349       }
   350       level_stack.push_back(level);
   351       return minimum.arc;
   352     }
   353 
   354     int bottom(Node node) {
   355       int k = level_stack.size() - 1;
   356       while (level_stack[k].node_level > (*_node_order)[node]) {
   357         --k;
   358       }
   359       return level_stack[k].node_level;
   360     }
   361 
   362     void finalize(Arc arc) {
   363       Node node = _digraph->target(arc);
   364       _heap->push(node, (*_arc_order)[arc]);
   365       _pred->set(node, arc);
   366       while (!_heap->empty()) {
   367         Node source = _heap->top();
   368         _heap->pop();
   369         (*_node_order)[source] = -1;
   370         for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
   371           if ((*_arc_order)[it] < 0) continue;
   372           Node target = _digraph->target(it);
   373           switch(_heap->state(target)) {
   374           case Heap::PRE_HEAP:
   375             _heap->push(target, (*_arc_order)[it]);
   376             _pred->set(target, it);
   377             break;
   378           case Heap::IN_HEAP:
   379             if ((*_arc_order)[it] < (*_heap)[target]) {
   380               _heap->decrease(target, (*_arc_order)[it]);
   381               _pred->set(target, it);
   382             }
   383             break;
   384           case Heap::POST_HEAP:
   385             break;
   386           }
   387         }
   388         _arborescence->set((*_pred)[source], true);
   389       }
   390     }
   391 
   392 
   393   public:
   394 
   395     /// \name Named Template Parameters
   396 
   397     /// @{
   398 
   399     template <class T>
   400     struct SetArborescenceMapTraits : public Traits {
   401       typedef T ArborescenceMap;
   402       static ArborescenceMap *createArborescenceMap(const Digraph &)
   403       {
   404         LEMON_ASSERT(false, "ArborescenceMap is not initialized");
   405         return 0; // ignore warnings
   406       }
   407     };
   408 
   409     /// \brief \ref named-templ-param "Named parameter" for
   410     /// setting \c ArborescenceMap type
   411     ///
   412     /// \ref named-templ-param "Named parameter" for setting
   413     /// \c ArborescenceMap type.
   414     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
   415     /// and its value type must be \c bool (or convertible).
   416     /// Initially it will be set to \c false on each arc,
   417     /// then it will be set on each arborescence arc once.
   418     template <class T>
   419     struct SetArborescenceMap
   420       : public MinCostArborescence<Digraph, CostMap,
   421                                    SetArborescenceMapTraits<T> > {
   422     };
   423 
   424     template <class T>
   425     struct SetPredMapTraits : public Traits {
   426       typedef T PredMap;
   427       static PredMap *createPredMap(const Digraph &)
   428       {
   429         LEMON_ASSERT(false, "PredMap is not initialized");
   430         return 0; // ignore warnings
   431       }
   432     };
   433 
   434     /// \brief \ref named-templ-param "Named parameter" for
   435     /// setting \c PredMap type
   436     ///
   437     /// \ref named-templ-param "Named parameter" for setting
   438     /// \c PredMap type.
   439     /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 
   440     /// and its value type must be the \c Arc type of the digraph.
   441     template <class T>
   442     struct SetPredMap
   443       : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
   444     };
   445 
   446     /// @}
   447 
   448     /// \brief Constructor.
   449     ///
   450     /// \param digraph The digraph the algorithm will run on.
   451     /// \param cost The cost map used by the algorithm.
   452     MinCostArborescence(const Digraph& digraph, const CostMap& cost)
   453       : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
   454         _arborescence(0), local_arborescence(false),
   455         _arc_order(0), _node_order(0), _cost_arcs(0),
   456         _heap_cross_ref(0), _heap(0) {}
   457 
   458     /// \brief Destructor.
   459     ~MinCostArborescence() {
   460       destroyStructures();
   461     }
   462 
   463     /// \brief Sets the arborescence map.
   464     ///
   465     /// Sets the arborescence map.
   466     /// \return <tt>(*this)</tt>
   467     MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
   468       if (local_arborescence) {
   469         delete _arborescence;
   470       }
   471       local_arborescence = false;
   472       _arborescence = &m;
   473       return *this;
   474     }
   475 
   476     /// \brief Sets the predecessor map.
   477     ///
   478     /// Sets the predecessor map.
   479     /// \return <tt>(*this)</tt>
   480     MinCostArborescence& predMap(PredMap& m) {
   481       if (local_pred) {
   482         delete _pred;
   483       }
   484       local_pred = false;
   485       _pred = &m;
   486       return *this;
   487     }
   488 
   489     /// \name Execution Control
   490     /// The simplest way to execute the algorithm is to use
   491     /// one of the member functions called \c run(...). \n
   492     /// If you need better control on the execution,
   493     /// you have to call \ref init() first, then you can add several
   494     /// source nodes with \ref addSource().
   495     /// Finally \ref start() will perform the arborescence
   496     /// computation.
   497 
   498     ///@{
   499 
   500     /// \brief Initializes the internal data structures.
   501     ///
   502     /// Initializes the internal data structures.
   503     ///
   504     void init() {
   505       createStructures();
   506       _heap->clear();
   507       for (NodeIt it(*_digraph); it != INVALID; ++it) {
   508         (*_cost_arcs)[it].arc = INVALID;
   509         (*_node_order)[it] = -3;
   510         (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
   511         _pred->set(it, INVALID);
   512       }
   513       for (ArcIt it(*_digraph); it != INVALID; ++it) {
   514         _arborescence->set(it, false);
   515         (*_arc_order)[it] = -1;
   516       }
   517       _dual_node_list.clear();
   518       _dual_variables.clear();
   519     }
   520 
   521     /// \brief Adds a new source node.
   522     ///
   523     /// Adds a new source node to the algorithm.
   524     void addSource(Node source) {
   525       std::vector<Node> nodes;
   526       nodes.push_back(source);
   527       while (!nodes.empty()) {
   528         Node node = nodes.back();
   529         nodes.pop_back();
   530         for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
   531           Node target = _digraph->target(it);
   532           if ((*_node_order)[target] == -3) {
   533             (*_node_order)[target] = -2;
   534             nodes.push_back(target);
   535             queue.push_back(target);
   536           }
   537         }
   538       }
   539       (*_node_order)[source] = -1;
   540     }
   541 
   542     /// \brief Processes the next node in the priority queue.
   543     ///
   544     /// Processes the next node in the priority queue.
   545     ///
   546     /// \return The processed node.
   547     ///
   548     /// \warning The queue must not be empty.
   549     Node processNextNode() {
   550       Node node = queue.back();
   551       queue.pop_back();
   552       if ((*_node_order)[node] == -2) {
   553         Arc arc = prepare(node);
   554         Node source = _digraph->source(arc);
   555         while ((*_node_order)[source] != -1) {
   556           if ((*_node_order)[source] >= 0) {
   557             arc = contract(source);
   558           } else {
   559             arc = prepare(source);
   560           }
   561           source = _digraph->source(arc);
   562         }
   563         finalize(arc);
   564         level_stack.clear();
   565       }
   566       return node;
   567     }
   568 
   569     /// \brief Returns the number of the nodes to be processed.
   570     ///
   571     /// Returns the number of the nodes to be processed in the priority
   572     /// queue.
   573     int queueSize() const {
   574       return queue.size();
   575     }
   576 
   577     /// \brief Returns \c false if there are nodes to be processed.
   578     ///
   579     /// Returns \c false if there are nodes to be processed.
   580     bool emptyQueue() const {
   581       return queue.empty();
   582     }
   583 
   584     /// \brief Executes the algorithm.
   585     ///
   586     /// Executes the algorithm.
   587     ///
   588     /// \pre init() must be called and at least one node should be added
   589     /// with addSource() before using this function.
   590     ///
   591     ///\note mca.start() is just a shortcut of the following code.
   592     ///\code
   593     ///while (!mca.emptyQueue()) {
   594     ///  mca.processNextNode();
   595     ///}
   596     ///\endcode
   597     void start() {
   598       while (!emptyQueue()) {
   599         processNextNode();
   600       }
   601     }
   602 
   603     /// \brief Runs %MinCostArborescence algorithm from node \c s.
   604     ///
   605     /// This method runs the %MinCostArborescence algorithm from
   606     /// a root node \c s.
   607     ///
   608     /// \note mca.run(s) is just a shortcut of the following code.
   609     /// \code
   610     /// mca.init();
   611     /// mca.addSource(s);
   612     /// mca.start();
   613     /// \endcode
   614     void run(Node s) {
   615       init();
   616       addSource(s);
   617       start();
   618     }
   619 
   620     ///@}
   621 
   622     /// \name Query Functions
   623     /// The result of the %MinCostArborescence algorithm can be obtained
   624     /// using these functions.\n
   625     /// Either run() or start() must be called before using them.
   626 
   627     /// @{
   628 
   629     /// \brief Returns the cost of the arborescence.
   630     ///
   631     /// Returns the cost of the arborescence.
   632     Value arborescenceCost() const {
   633       Value sum = 0;
   634       for (ArcIt it(*_digraph); it != INVALID; ++it) {
   635         if (arborescence(it)) {
   636           sum += (*_cost)[it];
   637         }
   638       }
   639       return sum;
   640     }
   641 
   642     /// \brief Returns \c true if the arc is in the arborescence.
   643     ///
   644     /// Returns \c true if the given arc is in the arborescence.
   645     /// \param arc An arc of the digraph.
   646     /// \pre \ref run() must be called before using this function.
   647     bool arborescence(Arc arc) const {
   648       return (*_pred)[_digraph->target(arc)] == arc;
   649     }
   650 
   651     /// \brief Returns a const reference to the arborescence map.
   652     ///
   653     /// Returns a const reference to the arborescence map.
   654     /// \pre \ref run() must be called before using this function.
   655     const ArborescenceMap& arborescenceMap() const {
   656       return *_arborescence;
   657     }
   658 
   659     /// \brief Returns the predecessor arc of the given node.
   660     ///
   661     /// Returns the predecessor arc of the given node.
   662     /// \pre \ref run() must be called before using this function.
   663     Arc pred(Node node) const {
   664       return (*_pred)[node];
   665     }
   666 
   667     /// \brief Returns a const reference to the pred map.
   668     ///
   669     /// Returns a const reference to the pred map.
   670     /// \pre \ref run() must be called before using this function.
   671     const PredMap& predMap() const {
   672       return *_pred;
   673     }
   674 
   675     /// \brief Indicates that a node is reachable from the sources.
   676     ///
   677     /// Indicates that a node is reachable from the sources.
   678     bool reached(Node node) const {
   679       return (*_node_order)[node] != -3;
   680     }
   681 
   682     /// \brief Indicates that a node is processed.
   683     ///
   684     /// Indicates that a node is processed. The arborescence path exists
   685     /// from the source to the given node.
   686     bool processed(Node node) const {
   687       return (*_node_order)[node] == -1;
   688     }
   689 
   690     /// \brief Returns the number of the dual variables in basis.
   691     ///
   692     /// Returns the number of the dual variables in basis.
   693     int dualNum() const {
   694       return _dual_variables.size();
   695     }
   696 
   697     /// \brief Returns the value of the dual solution.
   698     ///
   699     /// Returns the value of the dual solution. It should be
   700     /// equal to the arborescence value.
   701     Value dualValue() const {
   702       Value sum = 0;
   703       for (int i = 0; i < int(_dual_variables.size()); ++i) {
   704         sum += _dual_variables[i].value;
   705       }
   706       return sum;
   707     }
   708 
   709     /// \brief Returns the number of the nodes in the dual variable.
   710     ///
   711     /// Returns the number of the nodes in the dual variable.
   712     int dualSize(int k) const {
   713       return _dual_variables[k].end - _dual_variables[k].begin;
   714     }
   715 
   716     /// \brief Returns the value of the dual variable.
   717     ///
   718     /// Returns the the value of the dual variable.
   719     Value dualValue(int k) const {
   720       return _dual_variables[k].value;
   721     }
   722 
   723     /// \brief LEMON iterator for getting a dual variable.
   724     ///
   725     /// This class provides a common style LEMON iterator for getting a
   726     /// dual variable of \ref MinCostArborescence algorithm.
   727     /// It iterates over a subset of the nodes.
   728     class DualIt {
   729     public:
   730 
   731       /// \brief Constructor.
   732       ///
   733       /// Constructor for getting the nodeset of the dual variable
   734       /// of \ref MinCostArborescence algorithm.
   735       DualIt(const MinCostArborescence& algorithm, int variable)
   736         : _algorithm(&algorithm)
   737       {
   738         _index = _algorithm->_dual_variables[variable].begin;
   739         _last = _algorithm->_dual_variables[variable].end;
   740       }
   741 
   742       /// \brief Conversion to \c Node.
   743       ///
   744       /// Conversion to \c Node.
   745       operator Node() const {
   746         return _algorithm->_dual_node_list[_index];
   747       }
   748 
   749       /// \brief Increment operator.
   750       ///
   751       /// Increment operator.
   752       DualIt& operator++() {
   753         ++_index;
   754         return *this;
   755       }
   756 
   757       /// \brief Validity checking
   758       ///
   759       /// Checks whether the iterator is invalid.
   760       bool operator==(Invalid) const {
   761         return _index == _last;
   762       }
   763 
   764       /// \brief Validity checking
   765       ///
   766       /// Checks whether the iterator is valid.
   767       bool operator!=(Invalid) const {
   768         return _index != _last;
   769       }
   770 
   771     private:
   772       const MinCostArborescence* _algorithm;
   773       int _index, _last;
   774     };
   775 
   776     /// @}
   777 
   778   };
   779 
   780   /// \ingroup spantree
   781   ///
   782   /// \brief Function type interface for MinCostArborescence algorithm.
   783   ///
   784   /// Function type interface for MinCostArborescence algorithm.
   785   /// \param digraph The digraph the algorithm runs on.
   786   /// \param cost An arc map storing the costs.
   787   /// \param source The source node of the arborescence.
   788   /// \retval arborescence An arc map with \c bool (or convertible) value
   789   /// type that stores the arborescence.
   790   /// \return The total cost of the arborescence.
   791   ///
   792   /// \sa MinCostArborescence
   793   template <typename Digraph, typename CostMap, typename ArborescenceMap>
   794   typename CostMap::Value minCostArborescence(const Digraph& digraph,
   795                                               const CostMap& cost,
   796                                               typename Digraph::Node source,
   797                                               ArborescenceMap& arborescence) {
   798     typename MinCostArborescence<Digraph, CostMap>
   799       ::template SetArborescenceMap<ArborescenceMap>
   800       ::Create mca(digraph, cost);
   801     mca.arborescenceMap(arborescence);
   802     mca.run(source);
   803     return mca.arborescenceCost();
   804   }
   805 
   806 }
   807 
   808 #endif