deba@490: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@490:  *
deba@490:  * This file is a part of LEMON, a generic C++ optimization library.
deba@490:  *
deba@490:  * Copyright (C) 2003-2008
deba@490:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@490:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@490:  *
deba@490:  * Permission to use, modify and distribute this software is granted
deba@490:  * provided that this copyright notice appears in all copies. For
deba@490:  * precise terms see the accompanying LICENSE file.
deba@490:  *
deba@490:  * This software is provided "AS IS" with no warranty of any kind,
deba@490:  * express or implied, and with no claim as to its suitability for any
deba@490:  * purpose.
deba@490:  *
deba@490:  */
deba@490: 
deba@490: #ifndef LEMON_MIN_COST_ARBORESCENCE_H
deba@490: #define LEMON_MIN_COST_ARBORESCENCE_H
deba@490: 
deba@490: ///\ingroup spantree
deba@490: ///\file
deba@490: ///\brief Minimum Cost Arborescence algorithm.
deba@490: 
deba@490: #include <vector>
deba@490: 
deba@490: #include <lemon/list_graph.h>
deba@490: #include <lemon/bin_heap.h>
deba@490: #include <lemon/assert.h>
deba@490: 
deba@490: namespace lemon {
deba@490: 
deba@490: 
deba@490:   /// \brief Default traits class for MinCostArborescence class.
deba@490:   ///
deba@490:   /// Default traits class for MinCostArborescence class.
kpeter@559:   /// \param GR Digraph type.
kpeter@625:   /// \param CM Type of the cost map.
kpeter@559:   template <class GR, class CM>
deba@490:   struct MinCostArborescenceDefaultTraits{
deba@490: 
deba@490:     /// \brief The digraph type the algorithm runs on.
kpeter@559:     typedef GR Digraph;
deba@490: 
deba@490:     /// \brief The type of the map that stores the arc costs.
deba@490:     ///
deba@490:     /// The type of the map that stores the arc costs.
kpeter@625:     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
kpeter@559:     typedef CM CostMap;
deba@490: 
deba@490:     /// \brief The value type of the costs.
deba@490:     ///
deba@490:     /// The value type of the costs.
deba@490:     typedef typename CostMap::Value Value;
deba@490: 
deba@490:     /// \brief The type of the map that stores which arcs are in the
deba@490:     /// arborescence.
deba@490:     ///
deba@490:     /// The type of the map that stores which arcs are in the
kpeter@625:     /// arborescence.  It must conform to the \ref concepts::WriteMap
kpeter@625:     /// "WriteMap" concept, and its value type must be \c bool
kpeter@625:     /// (or convertible). Initially it will be set to \c false on each
kpeter@625:     /// arc, then it will be set on each arborescence arc once.
deba@490:     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
deba@490: 
kpeter@559:     /// \brief Instantiates a \c ArborescenceMap.
deba@490:     ///
kpeter@559:     /// This function instantiates a \c ArborescenceMap.
kpeter@625:     /// \param digraph The digraph to which we would like to calculate
kpeter@625:     /// the \c ArborescenceMap.
deba@490:     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
deba@490:       return new ArborescenceMap(digraph);
deba@490:     }
deba@490: 
kpeter@559:     /// \brief The type of the \c PredMap
deba@490:     ///
kpeter@625:     /// The type of the \c PredMap. It must confrom to the
kpeter@625:     /// \ref concepts::WriteMap "WriteMap" concept, and its value type
kpeter@625:     /// must be the \c Arc type of the digraph.
deba@490:     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
deba@490: 
kpeter@559:     /// \brief Instantiates a \c PredMap.
deba@490:     ///
kpeter@559:     /// This function instantiates a \c PredMap.
kpeter@559:     /// \param digraph The digraph to which we would like to define the
kpeter@559:     /// \c PredMap.
deba@490:     static PredMap *createPredMap(const Digraph &digraph){
deba@490:       return new PredMap(digraph);
deba@490:     }
deba@490: 
deba@490:   };
deba@490: 
deba@490:   /// \ingroup spantree
deba@490:   ///
kpeter@584:   /// \brief Minimum Cost Arborescence algorithm class.
deba@490:   ///
kpeter@625:   /// This class provides an efficient implementation of the
kpeter@584:   /// Minimum Cost Arborescence algorithm. The arborescence is a tree
deba@490:   /// which is directed from a given source node of the digraph. One or
kpeter@625:   /// more sources should be given to the algorithm and it will calculate
kpeter@625:   /// the minimum cost subgraph that is the union of arborescences with the
deba@490:   /// given sources and spans all the nodes which are reachable from the
kpeter@559:   /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
deba@490:   ///
kpeter@625:   /// The algorithm also provides an optimal dual solution, therefore
deba@490:   /// the optimality of the solution can be checked.
deba@490:   ///
kpeter@625:   /// \param GR The digraph type the algorithm runs on.
kpeter@625:   /// \param CM A read-only arc map storing the costs of the
deba@490:   /// arcs. It is read once for each arc, so the map may involve in
kpeter@625:   /// relatively time consuming process to compute the arc costs if
deba@490:   /// it is necessary. The default map type is \ref
deba@490:   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
kpeter@559:   /// \param TR Traits class to set various data types used
deba@490:   /// by the algorithm. The default traits class is
deba@490:   /// \ref MinCostArborescenceDefaultTraits
kpeter@625:   /// "MinCostArborescenceDefaultTraits<GR, CM>".
deba@490: #ifndef DOXYGEN
kpeter@625:   template <typename GR,
kpeter@559:             typename CM = typename GR::template ArcMap<int>,
kpeter@559:             typename TR =
kpeter@559:               MinCostArborescenceDefaultTraits<GR, CM> >
deba@490: #else
kpeter@559:   template <typename GR, typename CM, typedef TR>
deba@490: #endif
deba@490:   class MinCostArborescence {
deba@490:   public:
deba@490: 
kpeter@625:     /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
kpeter@625:     /// of the algorithm. 
kpeter@559:     typedef TR Traits;
deba@490:     /// The type of the underlying digraph.
deba@490:     typedef typename Traits::Digraph Digraph;
deba@490:     /// The type of the map that stores the arc costs.
deba@490:     typedef typename Traits::CostMap CostMap;
deba@490:     ///The type of the costs of the arcs.
deba@490:     typedef typename Traits::Value Value;
deba@490:     ///The type of the predecessor map.
deba@490:     typedef typename Traits::PredMap PredMap;
deba@490:     ///The type of the map that stores which arcs are in the arborescence.
deba@490:     typedef typename Traits::ArborescenceMap ArborescenceMap;
deba@490: 
deba@490:     typedef MinCostArborescence Create;
deba@490: 
deba@490:   private:
deba@490: 
deba@490:     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
deba@490: 
deba@490:     struct CostArc {
deba@490: 
deba@490:       Arc arc;
deba@490:       Value value;
deba@490: 
deba@490:       CostArc() {}
deba@490:       CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
deba@490: 
deba@490:     };
deba@490: 
deba@490:     const Digraph *_digraph;
deba@490:     const CostMap *_cost;
deba@490: 
deba@490:     PredMap *_pred;
deba@490:     bool local_pred;
deba@490: 
deba@490:     ArborescenceMap *_arborescence;
deba@490:     bool local_arborescence;
deba@490: 
deba@490:     typedef typename Digraph::template ArcMap<int> ArcOrder;
deba@490:     ArcOrder *_arc_order;
deba@490: 
deba@490:     typedef typename Digraph::template NodeMap<int> NodeOrder;
deba@490:     NodeOrder *_node_order;
deba@490: 
deba@490:     typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
deba@490:     CostArcMap *_cost_arcs;
deba@490: 
deba@490:     struct StackLevel {
deba@490: 
deba@490:       std::vector<CostArc> arcs;
deba@490:       int node_level;
deba@490: 
deba@490:     };
deba@490: 
deba@490:     std::vector<StackLevel> level_stack;
deba@490:     std::vector<Node> queue;
deba@490: 
deba@490:     typedef std::vector<typename Digraph::Node> DualNodeList;
deba@490: 
deba@490:     DualNodeList _dual_node_list;
deba@490: 
deba@490:     struct DualVariable {
deba@490:       int begin, end;
deba@490:       Value value;
deba@490: 
deba@490:       DualVariable(int _begin, int _end, Value _value)
deba@490:         : begin(_begin), end(_end), value(_value) {}
deba@490: 
deba@490:     };
deba@490: 
deba@490:     typedef std::vector<DualVariable> DualVariables;
deba@490: 
deba@490:     DualVariables _dual_variables;
deba@490: 
deba@490:     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
deba@490: 
deba@490:     HeapCrossRef *_heap_cross_ref;
deba@490: 
deba@490:     typedef BinHeap<int, HeapCrossRef> Heap;
deba@490: 
deba@490:     Heap *_heap;
deba@490: 
deba@490:   protected:
deba@490: 
deba@490:     MinCostArborescence() {}
deba@490: 
deba@490:   private:
deba@490: 
deba@490:     void createStructures() {
deba@490:       if (!_pred) {
deba@490:         local_pred = true;
deba@490:         _pred = Traits::createPredMap(*_digraph);
deba@490:       }
deba@490:       if (!_arborescence) {
deba@490:         local_arborescence = true;
deba@490:         _arborescence = Traits::createArborescenceMap(*_digraph);
deba@490:       }
deba@490:       if (!_arc_order) {
deba@490:         _arc_order = new ArcOrder(*_digraph);
deba@490:       }
deba@490:       if (!_node_order) {
deba@490:         _node_order = new NodeOrder(*_digraph);
deba@490:       }
deba@490:       if (!_cost_arcs) {
deba@490:         _cost_arcs = new CostArcMap(*_digraph);
deba@490:       }
deba@490:       if (!_heap_cross_ref) {
deba@490:         _heap_cross_ref = new HeapCrossRef(*_digraph, -1);
deba@490:       }
deba@490:       if (!_heap) {
deba@490:         _heap = new Heap(*_heap_cross_ref);
deba@490:       }
deba@490:     }
deba@490: 
deba@490:     void destroyStructures() {
deba@490:       if (local_arborescence) {
deba@490:         delete _arborescence;
deba@490:       }
deba@490:       if (local_pred) {
deba@490:         delete _pred;
deba@490:       }
deba@490:       if (_arc_order) {
deba@490:         delete _arc_order;
deba@490:       }
deba@490:       if (_node_order) {
deba@490:         delete _node_order;
deba@490:       }
deba@490:       if (_cost_arcs) {
deba@490:         delete _cost_arcs;
deba@490:       }
deba@490:       if (_heap) {
deba@490:         delete _heap;
deba@490:       }
deba@490:       if (_heap_cross_ref) {
deba@490:         delete _heap_cross_ref;
deba@490:       }
deba@490:     }
deba@490: 
deba@490:     Arc prepare(Node node) {
deba@490:       std::vector<Node> nodes;
deba@490:       (*_node_order)[node] = _dual_node_list.size();
deba@490:       StackLevel level;
deba@490:       level.node_level = _dual_node_list.size();
deba@490:       _dual_node_list.push_back(node);
deba@490:       for (InArcIt it(*_digraph, node); it != INVALID; ++it) {
deba@490:         Arc arc = it;
deba@490:         Node source = _digraph->source(arc);
deba@490:         Value value = (*_cost)[it];
deba@490:         if (source == node || (*_node_order)[source] == -3) continue;
deba@490:         if ((*_cost_arcs)[source].arc == INVALID) {
deba@490:           (*_cost_arcs)[source].arc = arc;
deba@490:           (*_cost_arcs)[source].value = value;
deba@490:           nodes.push_back(source);
deba@490:         } else {
deba@490:           if ((*_cost_arcs)[source].value > value) {
deba@490:             (*_cost_arcs)[source].arc = arc;
deba@490:             (*_cost_arcs)[source].value = value;
deba@490:           }
deba@490:         }
deba@490:       }
deba@490:       CostArc minimum = (*_cost_arcs)[nodes[0]];
deba@490:       for (int i = 1; i < int(nodes.size()); ++i) {
deba@490:         if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
deba@490:           minimum = (*_cost_arcs)[nodes[i]];
deba@490:         }
deba@490:       }
kpeter@581:       (*_arc_order)[minimum.arc] = _dual_variables.size();
deba@490:       DualVariable var(_dual_node_list.size() - 1,
deba@490:                        _dual_node_list.size(), minimum.value);
deba@490:       _dual_variables.push_back(var);
deba@490:       for (int i = 0; i < int(nodes.size()); ++i) {
deba@490:         (*_cost_arcs)[nodes[i]].value -= minimum.value;
deba@490:         level.arcs.push_back((*_cost_arcs)[nodes[i]]);
deba@490:         (*_cost_arcs)[nodes[i]].arc = INVALID;
deba@490:       }
deba@490:       level_stack.push_back(level);
deba@490:       return minimum.arc;
deba@490:     }
deba@490: 
deba@490:     Arc contract(Node node) {
deba@490:       int node_bottom = bottom(node);
deba@490:       std::vector<Node> nodes;
deba@490:       while (!level_stack.empty() &&
deba@490:              level_stack.back().node_level >= node_bottom) {
deba@490:         for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
deba@490:           Arc arc = level_stack.back().arcs[i].arc;
deba@490:           Node source = _digraph->source(arc);
deba@490:           Value value = level_stack.back().arcs[i].value;
deba@490:           if ((*_node_order)[source] >= node_bottom) continue;
deba@490:           if ((*_cost_arcs)[source].arc == INVALID) {
deba@490:             (*_cost_arcs)[source].arc = arc;
deba@490:             (*_cost_arcs)[source].value = value;
deba@490:             nodes.push_back(source);
deba@490:           } else {
deba@490:             if ((*_cost_arcs)[source].value > value) {
deba@490:               (*_cost_arcs)[source].arc = arc;
deba@490:               (*_cost_arcs)[source].value = value;
deba@490:             }
deba@490:           }
deba@490:         }
deba@490:         level_stack.pop_back();
deba@490:       }
deba@490:       CostArc minimum = (*_cost_arcs)[nodes[0]];
deba@490:       for (int i = 1; i < int(nodes.size()); ++i) {
deba@490:         if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
deba@490:           minimum = (*_cost_arcs)[nodes[i]];
deba@490:         }
deba@490:       }
kpeter@581:       (*_arc_order)[minimum.arc] = _dual_variables.size();
deba@490:       DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
deba@490:       _dual_variables.push_back(var);
deba@490:       StackLevel level;
deba@490:       level.node_level = node_bottom;
deba@490:       for (int i = 0; i < int(nodes.size()); ++i) {
deba@490:         (*_cost_arcs)[nodes[i]].value -= minimum.value;
deba@490:         level.arcs.push_back((*_cost_arcs)[nodes[i]]);
deba@490:         (*_cost_arcs)[nodes[i]].arc = INVALID;
deba@490:       }
deba@490:       level_stack.push_back(level);
deba@490:       return minimum.arc;
deba@490:     }
deba@490: 
deba@490:     int bottom(Node node) {
deba@490:       int k = level_stack.size() - 1;
deba@490:       while (level_stack[k].node_level > (*_node_order)[node]) {
deba@490:         --k;
deba@490:       }
deba@490:       return level_stack[k].node_level;
deba@490:     }
deba@490: 
deba@490:     void finalize(Arc arc) {
deba@490:       Node node = _digraph->target(arc);
deba@490:       _heap->push(node, (*_arc_order)[arc]);
deba@490:       _pred->set(node, arc);
deba@490:       while (!_heap->empty()) {
deba@490:         Node source = _heap->top();
deba@490:         _heap->pop();
kpeter@581:         (*_node_order)[source] = -1;
deba@490:         for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
deba@490:           if ((*_arc_order)[it] < 0) continue;
deba@490:           Node target = _digraph->target(it);
deba@490:           switch(_heap->state(target)) {
deba@490:           case Heap::PRE_HEAP:
deba@490:             _heap->push(target, (*_arc_order)[it]);
deba@490:             _pred->set(target, it);
deba@490:             break;
deba@490:           case Heap::IN_HEAP:
deba@490:             if ((*_arc_order)[it] < (*_heap)[target]) {
deba@490:               _heap->decrease(target, (*_arc_order)[it]);
deba@490:               _pred->set(target, it);
deba@490:             }
deba@490:             break;
deba@490:           case Heap::POST_HEAP:
deba@490:             break;
deba@490:           }
deba@490:         }
deba@490:         _arborescence->set((*_pred)[source], true);
deba@490:       }
deba@490:     }
deba@490: 
deba@490: 
deba@490:   public:
deba@490: 
kpeter@584:     /// \name Named Template Parameters
deba@490: 
deba@490:     /// @{
deba@490: 
deba@490:     template <class T>
kpeter@625:     struct SetArborescenceMapTraits : public Traits {
deba@490:       typedef T ArborescenceMap;
deba@490:       static ArborescenceMap *createArborescenceMap(const Digraph &)
deba@490:       {
deba@490:         LEMON_ASSERT(false, "ArborescenceMap is not initialized");
deba@490:         return 0; // ignore warnings
deba@490:       }
deba@490:     };
deba@490: 
deba@490:     /// \brief \ref named-templ-param "Named parameter" for
kpeter@625:     /// setting \c ArborescenceMap type
deba@490:     ///
deba@490:     /// \ref named-templ-param "Named parameter" for setting
kpeter@625:     /// \c ArborescenceMap type.
kpeter@625:     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
kpeter@625:     /// and its value type must be \c bool (or convertible).
kpeter@625:     /// Initially it will be set to \c false on each arc,
kpeter@625:     /// then it will be set on each arborescence arc once.
deba@490:     template <class T>
kpeter@625:     struct SetArborescenceMap
deba@490:       : public MinCostArborescence<Digraph, CostMap,
kpeter@625:                                    SetArborescenceMapTraits<T> > {
deba@490:     };
deba@490: 
deba@490:     template <class T>
kpeter@625:     struct SetPredMapTraits : public Traits {
deba@490:       typedef T PredMap;
deba@490:       static PredMap *createPredMap(const Digraph &)
deba@490:       {
deba@490:         LEMON_ASSERT(false, "PredMap is not initialized");
kpeter@625:         return 0; // ignore warnings
deba@490:       }
deba@490:     };
deba@490: 
deba@490:     /// \brief \ref named-templ-param "Named parameter" for
kpeter@625:     /// setting \c PredMap type
deba@490:     ///
deba@490:     /// \ref named-templ-param "Named parameter" for setting
kpeter@625:     /// \c PredMap type.
kpeter@625:     /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 
kpeter@625:     /// and its value type must be the \c Arc type of the digraph.
deba@490:     template <class T>
kpeter@625:     struct SetPredMap
kpeter@625:       : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
deba@490:     };
deba@490: 
deba@490:     /// @}
deba@490: 
deba@490:     /// \brief Constructor.
deba@490:     ///
kpeter@559:     /// \param digraph The digraph the algorithm will run on.
kpeter@559:     /// \param cost The cost map used by the algorithm.
deba@490:     MinCostArborescence(const Digraph& digraph, const CostMap& cost)
deba@490:       : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
deba@490:         _arborescence(0), local_arborescence(false),
deba@490:         _arc_order(0), _node_order(0), _cost_arcs(0),
deba@490:         _heap_cross_ref(0), _heap(0) {}
deba@490: 
deba@490:     /// \brief Destructor.
deba@490:     ~MinCostArborescence() {
deba@490:       destroyStructures();
deba@490:     }
deba@490: 
deba@490:     /// \brief Sets the arborescence map.
deba@490:     ///
deba@490:     /// Sets the arborescence map.
kpeter@559:     /// \return <tt>(*this)</tt>
deba@490:     MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
deba@490:       if (local_arborescence) {
deba@490:         delete _arborescence;
deba@490:       }
deba@490:       local_arborescence = false;
deba@490:       _arborescence = &m;
deba@490:       return *this;
deba@490:     }
deba@490: 
kpeter@625:     /// \brief Sets the predecessor map.
deba@490:     ///
kpeter@625:     /// Sets the predecessor map.
kpeter@559:     /// \return <tt>(*this)</tt>
deba@490:     MinCostArborescence& predMap(PredMap& m) {
deba@490:       if (local_pred) {
deba@490:         delete _pred;
deba@490:       }
deba@490:       local_pred = false;
deba@490:       _pred = &m;
deba@490:       return *this;
deba@490:     }
deba@490: 
kpeter@584:     /// \name Execution Control
deba@490:     /// The simplest way to execute the algorithm is to use
deba@490:     /// one of the member functions called \c run(...). \n
kpeter@713:     /// If you need better control on the execution,
kpeter@713:     /// you have to call \ref init() first, then you can add several
deba@490:     /// source nodes with \ref addSource().
deba@490:     /// Finally \ref start() will perform the arborescence
deba@490:     /// computation.
deba@490: 
deba@490:     ///@{
deba@490: 
deba@490:     /// \brief Initializes the internal data structures.
deba@490:     ///
deba@490:     /// Initializes the internal data structures.
deba@490:     ///
deba@490:     void init() {
deba@490:       createStructures();
deba@490:       _heap->clear();
deba@490:       for (NodeIt it(*_digraph); it != INVALID; ++it) {
deba@490:         (*_cost_arcs)[it].arc = INVALID;
kpeter@581:         (*_node_order)[it] = -3;
kpeter@581:         (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
deba@490:         _pred->set(it, INVALID);
deba@490:       }
deba@490:       for (ArcIt it(*_digraph); it != INVALID; ++it) {
deba@490:         _arborescence->set(it, false);
kpeter@581:         (*_arc_order)[it] = -1;
deba@490:       }
deba@490:       _dual_node_list.clear();
deba@490:       _dual_variables.clear();
deba@490:     }
deba@490: 
deba@490:     /// \brief Adds a new source node.
deba@490:     ///
deba@490:     /// Adds a new source node to the algorithm.
deba@490:     void addSource(Node source) {
deba@490:       std::vector<Node> nodes;
deba@490:       nodes.push_back(source);
deba@490:       while (!nodes.empty()) {
deba@490:         Node node = nodes.back();
deba@490:         nodes.pop_back();
deba@490:         for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
deba@490:           Node target = _digraph->target(it);
deba@490:           if ((*_node_order)[target] == -3) {
deba@490:             (*_node_order)[target] = -2;
deba@490:             nodes.push_back(target);
deba@490:             queue.push_back(target);
deba@490:           }
deba@490:         }
deba@490:       }
deba@490:       (*_node_order)[source] = -1;
deba@490:     }
deba@490: 
deba@490:     /// \brief Processes the next node in the priority queue.
deba@490:     ///
deba@490:     /// Processes the next node in the priority queue.
deba@490:     ///
deba@490:     /// \return The processed node.
deba@490:     ///
kpeter@625:     /// \warning The queue must not be empty.
deba@490:     Node processNextNode() {
deba@490:       Node node = queue.back();
deba@490:       queue.pop_back();
deba@490:       if ((*_node_order)[node] == -2) {
deba@490:         Arc arc = prepare(node);
deba@490:         Node source = _digraph->source(arc);
deba@490:         while ((*_node_order)[source] != -1) {
deba@490:           if ((*_node_order)[source] >= 0) {
deba@490:             arc = contract(source);
deba@490:           } else {
deba@490:             arc = prepare(source);
deba@490:           }
deba@490:           source = _digraph->source(arc);
deba@490:         }
deba@490:         finalize(arc);
deba@490:         level_stack.clear();
deba@490:       }
deba@490:       return node;
deba@490:     }
deba@490: 
deba@490:     /// \brief Returns the number of the nodes to be processed.
deba@490:     ///
kpeter@625:     /// Returns the number of the nodes to be processed in the priority
kpeter@625:     /// queue.
deba@490:     int queueSize() const {
deba@490:       return queue.size();
deba@490:     }
deba@490: 
deba@490:     /// \brief Returns \c false if there are nodes to be processed.
deba@490:     ///
deba@490:     /// Returns \c false if there are nodes to be processed.
deba@490:     bool emptyQueue() const {
deba@490:       return queue.empty();
deba@490:     }
deba@490: 
deba@490:     /// \brief Executes the algorithm.
deba@490:     ///
deba@490:     /// Executes the algorithm.
deba@490:     ///
deba@490:     /// \pre init() must be called and at least one node should be added
deba@490:     /// with addSource() before using this function.
deba@490:     ///
deba@490:     ///\note mca.start() is just a shortcut of the following code.
deba@490:     ///\code
deba@490:     ///while (!mca.emptyQueue()) {
deba@490:     ///  mca.processNextNode();
deba@490:     ///}
deba@490:     ///\endcode
deba@490:     void start() {
deba@490:       while (!emptyQueue()) {
deba@490:         processNextNode();
deba@490:       }
deba@490:     }
deba@490: 
deba@490:     /// \brief Runs %MinCostArborescence algorithm from node \c s.
deba@490:     ///
deba@490:     /// This method runs the %MinCostArborescence algorithm from
deba@490:     /// a root node \c s.
deba@490:     ///
deba@490:     /// \note mca.run(s) is just a shortcut of the following code.
deba@490:     /// \code
deba@490:     /// mca.init();
deba@490:     /// mca.addSource(s);
deba@490:     /// mca.start();
deba@490:     /// \endcode
kpeter@625:     void run(Node s) {
deba@490:       init();
kpeter@625:       addSource(s);
deba@490:       start();
deba@490:     }
deba@490: 
deba@490:     ///@}
deba@490: 
kpeter@625:     /// \name Query Functions
kpeter@625:     /// The result of the %MinCostArborescence algorithm can be obtained
kpeter@625:     /// using these functions.\n
kpeter@625:     /// Either run() or start() must be called before using them.
kpeter@625: 
kpeter@625:     /// @{
kpeter@625: 
kpeter@625:     /// \brief Returns the cost of the arborescence.
kpeter@625:     ///
kpeter@625:     /// Returns the cost of the arborescence.
kpeter@625:     Value arborescenceCost() const {
kpeter@625:       Value sum = 0;
kpeter@625:       for (ArcIt it(*_digraph); it != INVALID; ++it) {
kpeter@625:         if (arborescence(it)) {
kpeter@625:           sum += (*_cost)[it];
kpeter@625:         }
kpeter@625:       }
kpeter@625:       return sum;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns \c true if the arc is in the arborescence.
kpeter@625:     ///
kpeter@625:     /// Returns \c true if the given arc is in the arborescence.
kpeter@625:     /// \param arc An arc of the digraph.
kpeter@625:     /// \pre \ref run() must be called before using this function.
kpeter@625:     bool arborescence(Arc arc) const {
kpeter@625:       return (*_pred)[_digraph->target(arc)] == arc;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns a const reference to the arborescence map.
kpeter@625:     ///
kpeter@625:     /// Returns a const reference to the arborescence map.
kpeter@625:     /// \pre \ref run() must be called before using this function.
kpeter@625:     const ArborescenceMap& arborescenceMap() const {
kpeter@625:       return *_arborescence;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns the predecessor arc of the given node.
kpeter@625:     ///
kpeter@625:     /// Returns the predecessor arc of the given node.
kpeter@625:     /// \pre \ref run() must be called before using this function.
kpeter@625:     Arc pred(Node node) const {
kpeter@625:       return (*_pred)[node];
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns a const reference to the pred map.
kpeter@625:     ///
kpeter@625:     /// Returns a const reference to the pred map.
kpeter@625:     /// \pre \ref run() must be called before using this function.
kpeter@625:     const PredMap& predMap() const {
kpeter@625:       return *_pred;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Indicates that a node is reachable from the sources.
kpeter@625:     ///
kpeter@625:     /// Indicates that a node is reachable from the sources.
kpeter@625:     bool reached(Node node) const {
kpeter@625:       return (*_node_order)[node] != -3;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Indicates that a node is processed.
kpeter@625:     ///
kpeter@625:     /// Indicates that a node is processed. The arborescence path exists
kpeter@625:     /// from the source to the given node.
kpeter@625:     bool processed(Node node) const {
kpeter@625:       return (*_node_order)[node] == -1;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns the number of the dual variables in basis.
kpeter@625:     ///
kpeter@625:     /// Returns the number of the dual variables in basis.
kpeter@625:     int dualNum() const {
kpeter@625:       return _dual_variables.size();
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns the value of the dual solution.
kpeter@625:     ///
kpeter@625:     /// Returns the value of the dual solution. It should be
kpeter@625:     /// equal to the arborescence value.
kpeter@625:     Value dualValue() const {
kpeter@625:       Value sum = 0;
kpeter@625:       for (int i = 0; i < int(_dual_variables.size()); ++i) {
kpeter@625:         sum += _dual_variables[i].value;
kpeter@625:       }
kpeter@625:       return sum;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns the number of the nodes in the dual variable.
kpeter@625:     ///
kpeter@625:     /// Returns the number of the nodes in the dual variable.
kpeter@625:     int dualSize(int k) const {
kpeter@625:       return _dual_variables[k].end - _dual_variables[k].begin;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief Returns the value of the dual variable.
kpeter@625:     ///
kpeter@625:     /// Returns the the value of the dual variable.
kpeter@625:     Value dualValue(int k) const {
kpeter@625:       return _dual_variables[k].value;
kpeter@625:     }
kpeter@625: 
kpeter@625:     /// \brief LEMON iterator for getting a dual variable.
kpeter@625:     ///
kpeter@625:     /// This class provides a common style LEMON iterator for getting a
kpeter@625:     /// dual variable of \ref MinCostArborescence algorithm.
kpeter@625:     /// It iterates over a subset of the nodes.
kpeter@625:     class DualIt {
kpeter@625:     public:
kpeter@625: 
kpeter@625:       /// \brief Constructor.
kpeter@625:       ///
kpeter@625:       /// Constructor for getting the nodeset of the dual variable
kpeter@625:       /// of \ref MinCostArborescence algorithm.
kpeter@625:       DualIt(const MinCostArborescence& algorithm, int variable)
kpeter@625:         : _algorithm(&algorithm)
kpeter@625:       {
kpeter@625:         _index = _algorithm->_dual_variables[variable].begin;
kpeter@625:         _last = _algorithm->_dual_variables[variable].end;
kpeter@625:       }
kpeter@625: 
kpeter@625:       /// \brief Conversion to \c Node.
kpeter@625:       ///
kpeter@625:       /// Conversion to \c Node.
kpeter@625:       operator Node() const {
kpeter@625:         return _algorithm->_dual_node_list[_index];
kpeter@625:       }
kpeter@625: 
kpeter@625:       /// \brief Increment operator.
kpeter@625:       ///
kpeter@625:       /// Increment operator.
kpeter@625:       DualIt& operator++() {
kpeter@625:         ++_index;
kpeter@625:         return *this;
kpeter@625:       }
kpeter@625: 
kpeter@625:       /// \brief Validity checking
kpeter@625:       ///
kpeter@625:       /// Checks whether the iterator is invalid.
kpeter@625:       bool operator==(Invalid) const {
kpeter@625:         return _index == _last;
kpeter@625:       }
kpeter@625: 
kpeter@625:       /// \brief Validity checking
kpeter@625:       ///
kpeter@625:       /// Checks whether the iterator is valid.
kpeter@625:       bool operator!=(Invalid) const {
kpeter@625:         return _index != _last;
kpeter@625:       }
kpeter@625: 
kpeter@625:     private:
kpeter@625:       const MinCostArborescence* _algorithm;
kpeter@625:       int _index, _last;
kpeter@625:     };
kpeter@625: 
kpeter@625:     /// @}
kpeter@625: 
deba@490:   };
deba@490: 
deba@490:   /// \ingroup spantree
deba@490:   ///
deba@490:   /// \brief Function type interface for MinCostArborescence algorithm.
deba@490:   ///
deba@490:   /// Function type interface for MinCostArborescence algorithm.
kpeter@625:   /// \param digraph The digraph the algorithm runs on.
kpeter@625:   /// \param cost An arc map storing the costs.
kpeter@625:   /// \param source The source node of the arborescence.
kpeter@625:   /// \retval arborescence An arc map with \c bool (or convertible) value
kpeter@625:   /// type that stores the arborescence.
kpeter@625:   /// \return The total cost of the arborescence.
deba@490:   ///
deba@490:   /// \sa MinCostArborescence
deba@490:   template <typename Digraph, typename CostMap, typename ArborescenceMap>
deba@490:   typename CostMap::Value minCostArborescence(const Digraph& digraph,
deba@490:                                               const CostMap& cost,
deba@490:                                               typename Digraph::Node source,
deba@490:                                               ArborescenceMap& arborescence) {
deba@490:     typename MinCostArborescence<Digraph, CostMap>
kpeter@625:       ::template SetArborescenceMap<ArborescenceMap>
deba@490:       ::Create mca(digraph, cost);
deba@490:     mca.arborescenceMap(arborescence);
deba@490:     mca.run(source);
kpeter@625:     return mca.arborescenceCost();
deba@490:   }
deba@490: 
deba@490: }
deba@490: 
deba@490: #endif