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