lemon/min_cost_arborescence.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 24 Apr 2009 12:22:06 +0200
changeset 613 b1811c363299
parent 581 aa1804409f29
child 625 029a48052c67
permissions -rw-r--r--
Bug fix in NetworkSimplex (#234)
     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 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 meet 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 meet the \ref concepts::WriteMap
    62     /// "WriteMap" concept.  Initially it will be set to false on each
    63     /// arc. After it will set all arborescence arcs once.
    64     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    65 
    66     /// \brief Instantiates a \c ArborescenceMap.
    67     ///
    68     /// This function instantiates a \c ArborescenceMap.
    69     /// \param digraph is the graph, to which we would like to
    70     /// calculate the \c ArborescenceMap.
    71     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    72       return new ArborescenceMap(digraph);
    73     }
    74 
    75     /// \brief The type of the \c PredMap
    76     ///
    77     /// The type of the \c PredMap. It is a node map with an arc value type.
    78     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    79 
    80     /// \brief Instantiates a \c PredMap.
    81     ///
    82     /// This function instantiates a \c PredMap.
    83     /// \param digraph The digraph to which we would like to define the
    84     /// \c PredMap.
    85     static PredMap *createPredMap(const Digraph &digraph){
    86       return new PredMap(digraph);
    87     }
    88 
    89   };
    90 
    91   /// \ingroup spantree
    92   ///
    93   /// \brief Minimum Cost Arborescence algorithm class.
    94   ///
    95   /// This class provides an efficient implementation of
    96   /// Minimum Cost Arborescence algorithm. The arborescence is a tree
    97   /// 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
    99   /// the minimum cost subgraph which are union of arborescences with the
   100   /// 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).
   102   ///
   103   /// The algorithm provides also an optimal dual solution, therefore
   104   /// the optimality of the solution can be checked.
   105   ///
   106   /// \param GR The digraph type the algorithm runs on. The default value
   107   /// is \ref ListDigraph.
   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
   110   /// relatively time consuming process to compute the arc cost if
   111   /// it is necessary. The default map type is \ref
   112   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   113   /// \param TR Traits class to set various data types used
   114   /// by the algorithm. The default traits class is
   115   /// \ref MinCostArborescenceDefaultTraits
   116   /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
   117   /// MinCostArborescenceDefaultTraits for the documentation of a
   118   /// MinCostArborescence traits class.
   119 #ifndef DOXYGEN
   120   template <typename GR = ListDigraph,
   121             typename CM = typename GR::template ArcMap<int>,
   122             typename TR =
   123               MinCostArborescenceDefaultTraits<GR, CM> >
   124 #else
   125   template <typename GR, typename CM, typedef TR>
   126 #endif
   127   class MinCostArborescence {
   128   public:
   129 
   130     /// The traits.
   131     typedef TR Traits;
   132     /// The type of the underlying digraph.
   133     typedef typename Traits::Digraph Digraph;
   134     /// The type of the map that stores the arc costs.
   135     typedef typename Traits::CostMap CostMap;
   136     ///The type of the costs of the arcs.
   137     typedef typename Traits::Value Value;
   138     ///The type of the predecessor map.
   139     typedef typename Traits::PredMap PredMap;
   140     ///The type of the map that stores which arcs are in the arborescence.
   141     typedef typename Traits::ArborescenceMap ArborescenceMap;
   142 
   143     typedef MinCostArborescence Create;
   144 
   145   private:
   146 
   147     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   148 
   149     struct CostArc {
   150 
   151       Arc arc;
   152       Value value;
   153 
   154       CostArc() {}
   155       CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
   156 
   157     };
   158 
   159     const Digraph *_digraph;
   160     const CostMap *_cost;
   161 
   162     PredMap *_pred;
   163     bool local_pred;
   164 
   165     ArborescenceMap *_arborescence;
   166     bool local_arborescence;
   167 
   168     typedef typename Digraph::template ArcMap<int> ArcOrder;
   169     ArcOrder *_arc_order;
   170 
   171     typedef typename Digraph::template NodeMap<int> NodeOrder;
   172     NodeOrder *_node_order;
   173 
   174     typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
   175     CostArcMap *_cost_arcs;
   176 
   177     struct StackLevel {
   178 
   179       std::vector<CostArc> arcs;
   180       int node_level;
   181 
   182     };
   183 
   184     std::vector<StackLevel> level_stack;
   185     std::vector<Node> queue;
   186 
   187     typedef std::vector<typename Digraph::Node> DualNodeList;
   188 
   189     DualNodeList _dual_node_list;
   190 
   191     struct DualVariable {
   192       int begin, end;
   193       Value value;
   194 
   195       DualVariable(int _begin, int _end, Value _value)
   196         : begin(_begin), end(_end), value(_value) {}
   197 
   198     };
   199 
   200     typedef std::vector<DualVariable> DualVariables;
   201 
   202     DualVariables _dual_variables;
   203 
   204     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
   205 
   206     HeapCrossRef *_heap_cross_ref;
   207 
   208     typedef BinHeap<int, HeapCrossRef> Heap;
   209 
   210     Heap *_heap;
   211 
   212   protected:
   213 
   214     MinCostArborescence() {}
   215 
   216   private:
   217 
   218     void createStructures() {
   219       if (!_pred) {
   220         local_pred = true;
   221         _pred = Traits::createPredMap(*_digraph);
   222       }
   223       if (!_arborescence) {
   224         local_arborescence = true;
   225         _arborescence = Traits::createArborescenceMap(*_digraph);
   226       }
   227       if (!_arc_order) {
   228         _arc_order = new ArcOrder(*_digraph);
   229       }
   230       if (!_node_order) {
   231         _node_order = new NodeOrder(*_digraph);
   232       }
   233       if (!_cost_arcs) {
   234         _cost_arcs = new CostArcMap(*_digraph);
   235       }
   236       if (!_heap_cross_ref) {
   237         _heap_cross_ref = new HeapCrossRef(*_digraph, -1);
   238       }
   239       if (!_heap) {
   240         _heap = new Heap(*_heap_cross_ref);
   241       }
   242     }
   243 
   244     void destroyStructures() {
   245       if (local_arborescence) {
   246         delete _arborescence;
   247       }
   248       if (local_pred) {
   249         delete _pred;
   250       }
   251       if (_arc_order) {
   252         delete _arc_order;
   253       }
   254       if (_node_order) {
   255         delete _node_order;
   256       }
   257       if (_cost_arcs) {
   258         delete _cost_arcs;
   259       }
   260       if (_heap) {
   261         delete _heap;
   262       }
   263       if (_heap_cross_ref) {
   264         delete _heap_cross_ref;
   265       }
   266     }
   267 
   268     Arc prepare(Node node) {
   269       std::vector<Node> nodes;
   270       (*_node_order)[node] = _dual_node_list.size();
   271       StackLevel level;
   272       level.node_level = _dual_node_list.size();
   273       _dual_node_list.push_back(node);
   274       for (InArcIt it(*_digraph, node); it != INVALID; ++it) {
   275         Arc arc = it;
   276         Node source = _digraph->source(arc);
   277         Value value = (*_cost)[it];
   278         if (source == node || (*_node_order)[source] == -3) continue;
   279         if ((*_cost_arcs)[source].arc == INVALID) {
   280           (*_cost_arcs)[source].arc = arc;
   281           (*_cost_arcs)[source].value = value;
   282           nodes.push_back(source);
   283         } else {
   284           if ((*_cost_arcs)[source].value > value) {
   285             (*_cost_arcs)[source].arc = arc;
   286             (*_cost_arcs)[source].value = value;
   287           }
   288         }
   289       }
   290       CostArc minimum = (*_cost_arcs)[nodes[0]];
   291       for (int i = 1; i < int(nodes.size()); ++i) {
   292         if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
   293           minimum = (*_cost_arcs)[nodes[i]];
   294         }
   295       }
   296       (*_arc_order)[minimum.arc] = _dual_variables.size();
   297       DualVariable var(_dual_node_list.size() - 1,
   298                        _dual_node_list.size(), minimum.value);
   299       _dual_variables.push_back(var);
   300       for (int i = 0; i < int(nodes.size()); ++i) {
   301         (*_cost_arcs)[nodes[i]].value -= minimum.value;
   302         level.arcs.push_back((*_cost_arcs)[nodes[i]]);
   303         (*_cost_arcs)[nodes[i]].arc = INVALID;
   304       }
   305       level_stack.push_back(level);
   306       return minimum.arc;
   307     }
   308 
   309     Arc contract(Node node) {
   310       int node_bottom = bottom(node);
   311       std::vector<Node> nodes;
   312       while (!level_stack.empty() &&
   313              level_stack.back().node_level >= node_bottom) {
   314         for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
   315           Arc arc = level_stack.back().arcs[i].arc;
   316           Node source = _digraph->source(arc);
   317           Value value = level_stack.back().arcs[i].value;
   318           if ((*_node_order)[source] >= node_bottom) continue;
   319           if ((*_cost_arcs)[source].arc == INVALID) {
   320             (*_cost_arcs)[source].arc = arc;
   321             (*_cost_arcs)[source].value = value;
   322             nodes.push_back(source);
   323           } else {
   324             if ((*_cost_arcs)[source].value > value) {
   325               (*_cost_arcs)[source].arc = arc;
   326               (*_cost_arcs)[source].value = value;
   327             }
   328           }
   329         }
   330         level_stack.pop_back();
   331       }
   332       CostArc minimum = (*_cost_arcs)[nodes[0]];
   333       for (int i = 1; i < int(nodes.size()); ++i) {
   334         if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
   335           minimum = (*_cost_arcs)[nodes[i]];
   336         }
   337       }
   338       (*_arc_order)[minimum.arc] = _dual_variables.size();
   339       DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
   340       _dual_variables.push_back(var);
   341       StackLevel level;
   342       level.node_level = node_bottom;
   343       for (int i = 0; i < int(nodes.size()); ++i) {
   344         (*_cost_arcs)[nodes[i]].value -= minimum.value;
   345         level.arcs.push_back((*_cost_arcs)[nodes[i]]);
   346         (*_cost_arcs)[nodes[i]].arc = INVALID;
   347       }
   348       level_stack.push_back(level);
   349       return minimum.arc;
   350     }
   351 
   352     int bottom(Node node) {
   353       int k = level_stack.size() - 1;
   354       while (level_stack[k].node_level > (*_node_order)[node]) {
   355         --k;
   356       }
   357       return level_stack[k].node_level;
   358     }
   359 
   360     void finalize(Arc arc) {
   361       Node node = _digraph->target(arc);
   362       _heap->push(node, (*_arc_order)[arc]);
   363       _pred->set(node, arc);
   364       while (!_heap->empty()) {
   365         Node source = _heap->top();
   366         _heap->pop();
   367         (*_node_order)[source] = -1;
   368         for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
   369           if ((*_arc_order)[it] < 0) continue;
   370           Node target = _digraph->target(it);
   371           switch(_heap->state(target)) {
   372           case Heap::PRE_HEAP:
   373             _heap->push(target, (*_arc_order)[it]);
   374             _pred->set(target, it);
   375             break;
   376           case Heap::IN_HEAP:
   377             if ((*_arc_order)[it] < (*_heap)[target]) {
   378               _heap->decrease(target, (*_arc_order)[it]);
   379               _pred->set(target, it);
   380             }
   381             break;
   382           case Heap::POST_HEAP:
   383             break;
   384           }
   385         }
   386         _arborescence->set((*_pred)[source], true);
   387       }
   388     }
   389 
   390 
   391   public:
   392 
   393     /// \name Named Template Parameters
   394 
   395     /// @{
   396 
   397     template <class T>
   398     struct DefArborescenceMapTraits : public Traits {
   399       typedef T ArborescenceMap;
   400       static ArborescenceMap *createArborescenceMap(const Digraph &)
   401       {
   402         LEMON_ASSERT(false, "ArborescenceMap is not initialized");
   403         return 0; // ignore warnings
   404       }
   405     };
   406 
   407     /// \brief \ref named-templ-param "Named parameter" for
   408     /// setting ArborescenceMap type
   409     ///
   410     /// \ref named-templ-param "Named parameter" for setting
   411     /// ArborescenceMap type
   412     template <class T>
   413     struct DefArborescenceMap
   414       : public MinCostArborescence<Digraph, CostMap,
   415                                    DefArborescenceMapTraits<T> > {
   416     };
   417 
   418     template <class T>
   419     struct DefPredMapTraits : public Traits {
   420       typedef T PredMap;
   421       static PredMap *createPredMap(const Digraph &)
   422       {
   423         LEMON_ASSERT(false, "PredMap is not initialized");
   424       }
   425     };
   426 
   427     /// \brief \ref named-templ-param "Named parameter" for
   428     /// setting PredMap type
   429     ///
   430     /// \ref named-templ-param "Named parameter" for setting
   431     /// PredMap type
   432     template <class T>
   433     struct DefPredMap
   434       : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
   435     };
   436 
   437     /// @}
   438 
   439     /// \brief Constructor.
   440     ///
   441     /// \param digraph The digraph the algorithm will run on.
   442     /// \param cost The cost map used by the algorithm.
   443     MinCostArborescence(const Digraph& digraph, const CostMap& cost)
   444       : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
   445         _arborescence(0), local_arborescence(false),
   446         _arc_order(0), _node_order(0), _cost_arcs(0),
   447         _heap_cross_ref(0), _heap(0) {}
   448 
   449     /// \brief Destructor.
   450     ~MinCostArborescence() {
   451       destroyStructures();
   452     }
   453 
   454     /// \brief Sets the arborescence map.
   455     ///
   456     /// Sets the arborescence map.
   457     /// \return <tt>(*this)</tt>
   458     MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
   459       if (local_arborescence) {
   460         delete _arborescence;
   461       }
   462       local_arborescence = false;
   463       _arborescence = &m;
   464       return *this;
   465     }
   466 
   467     /// \brief Sets the arborescence map.
   468     ///
   469     /// Sets the arborescence map.
   470     /// \return <tt>(*this)</tt>
   471     MinCostArborescence& predMap(PredMap& m) {
   472       if (local_pred) {
   473         delete _pred;
   474       }
   475       local_pred = false;
   476       _pred = &m;
   477       return *this;
   478     }
   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 
   633     /// \name Execution Control
   634     /// The simplest way to execute the algorithm is to use
   635     /// one of the member functions called \c run(...). \n
   636     /// If you need more control on the execution,
   637     /// first you must call \ref init(), then you can add several
   638     /// source nodes with \ref addSource().
   639     /// Finally \ref start() will perform the arborescence
   640     /// computation.
   641 
   642     ///@{
   643 
   644     /// \brief Initializes the internal data structures.
   645     ///
   646     /// Initializes the internal data structures.
   647     ///
   648     void init() {
   649       createStructures();
   650       _heap->clear();
   651       for (NodeIt it(*_digraph); it != INVALID; ++it) {
   652         (*_cost_arcs)[it].arc = INVALID;
   653         (*_node_order)[it] = -3;
   654         (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
   655         _pred->set(it, INVALID);
   656       }
   657       for (ArcIt it(*_digraph); it != INVALID; ++it) {
   658         _arborescence->set(it, false);
   659         (*_arc_order)[it] = -1;
   660       }
   661       _dual_node_list.clear();
   662       _dual_variables.clear();
   663     }
   664 
   665     /// \brief Adds a new source node.
   666     ///
   667     /// Adds a new source node to the algorithm.
   668     void addSource(Node source) {
   669       std::vector<Node> nodes;
   670       nodes.push_back(source);
   671       while (!nodes.empty()) {
   672         Node node = nodes.back();
   673         nodes.pop_back();
   674         for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
   675           Node target = _digraph->target(it);
   676           if ((*_node_order)[target] == -3) {
   677             (*_node_order)[target] = -2;
   678             nodes.push_back(target);
   679             queue.push_back(target);
   680           }
   681         }
   682       }
   683       (*_node_order)[source] = -1;
   684     }
   685 
   686     /// \brief Processes the next node in the priority queue.
   687     ///
   688     /// Processes the next node in the priority queue.
   689     ///
   690     /// \return The processed node.
   691     ///
   692     /// \warning The queue must not be empty!
   693     Node processNextNode() {
   694       Node node = queue.back();
   695       queue.pop_back();
   696       if ((*_node_order)[node] == -2) {
   697         Arc arc = prepare(node);
   698         Node source = _digraph->source(arc);
   699         while ((*_node_order)[source] != -1) {
   700           if ((*_node_order)[source] >= 0) {
   701             arc = contract(source);
   702           } else {
   703             arc = prepare(source);
   704           }
   705           source = _digraph->source(arc);
   706         }
   707         finalize(arc);
   708         level_stack.clear();
   709       }
   710       return node;
   711     }
   712 
   713     /// \brief Returns the number of the nodes to be processed.
   714     ///
   715     /// Returns the number of the nodes to be processed.
   716     int queueSize() const {
   717       return queue.size();
   718     }
   719 
   720     /// \brief Returns \c false if there are nodes to be processed.
   721     ///
   722     /// Returns \c false if there are nodes to be processed.
   723     bool emptyQueue() const {
   724       return queue.empty();
   725     }
   726 
   727     /// \brief Executes the algorithm.
   728     ///
   729     /// Executes the algorithm.
   730     ///
   731     /// \pre init() must be called and at least one node should be added
   732     /// with addSource() before using this function.
   733     ///
   734     ///\note mca.start() is just a shortcut of the following code.
   735     ///\code
   736     ///while (!mca.emptyQueue()) {
   737     ///  mca.processNextNode();
   738     ///}
   739     ///\endcode
   740     void start() {
   741       while (!emptyQueue()) {
   742         processNextNode();
   743       }
   744     }
   745 
   746     /// \brief Runs %MinCostArborescence algorithm from node \c s.
   747     ///
   748     /// This method runs the %MinCostArborescence algorithm from
   749     /// a root node \c s.
   750     ///
   751     /// \note mca.run(s) is just a shortcut of the following code.
   752     /// \code
   753     /// mca.init();
   754     /// mca.addSource(s);
   755     /// mca.start();
   756     /// \endcode
   757     void run(Node node) {
   758       init();
   759       addSource(node);
   760       start();
   761     }
   762 
   763     ///@}
   764 
   765   };
   766 
   767   /// \ingroup spantree
   768   ///
   769   /// \brief Function type interface for MinCostArborescence algorithm.
   770   ///
   771   /// Function type interface for MinCostArborescence algorithm.
   772   /// \param digraph The Digraph that the algorithm runs on.
   773   /// \param cost The CostMap of the arcs.
   774   /// \param source The source of the arborescence.
   775   /// \retval arborescence The bool ArcMap which stores the arborescence.
   776   /// \return The cost of the arborescence.
   777   ///
   778   /// \sa MinCostArborescence
   779   template <typename Digraph, typename CostMap, typename ArborescenceMap>
   780   typename CostMap::Value minCostArborescence(const Digraph& digraph,
   781                                               const CostMap& cost,
   782                                               typename Digraph::Node source,
   783                                               ArborescenceMap& arborescence) {
   784     typename MinCostArborescence<Digraph, CostMap>
   785       ::template DefArborescenceMap<ArborescenceMap>
   786       ::Create mca(digraph, cost);
   787     mca.arborescenceMap(arborescence);
   788     mca.run(source);
   789     return mca.arborescenceValue();
   790   }
   791 
   792 }
   793 
   794 #endif