deba@501: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@501: * deba@501: * This file is a part of LEMON, a generic C++ optimization library. deba@501: * alpar@877: * Copyright (C) 2003-2010 deba@501: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@501: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@501: * deba@501: * Permission to use, modify and distribute this software is granted deba@501: * provided that this copyright notice appears in all copies. For deba@501: * precise terms see the accompanying LICENSE file. deba@501: * deba@501: * This software is provided "AS IS" with no warranty of any kind, deba@501: * express or implied, and with no claim as to its suitability for any deba@501: * purpose. deba@501: * deba@501: */ deba@501: deba@501: #ifndef LEMON_MIN_COST_ARBORESCENCE_H deba@501: #define LEMON_MIN_COST_ARBORESCENCE_H deba@501: deba@501: ///\ingroup spantree deba@501: ///\file deba@501: ///\brief Minimum Cost Arborescence algorithm. deba@501: deba@501: #include deba@501: deba@501: #include deba@501: #include deba@501: #include deba@501: deba@501: namespace lemon { deba@501: deba@501: deba@501: /// \brief Default traits class for MinCostArborescence class. deba@501: /// deba@501: /// Default traits class for MinCostArborescence class. kpeter@559: /// \param GR Digraph type. kpeter@625: /// \param CM Type of the cost map. kpeter@559: template deba@501: struct MinCostArborescenceDefaultTraits{ deba@501: deba@501: /// \brief The digraph type the algorithm runs on. kpeter@559: typedef GR Digraph; deba@501: deba@501: /// \brief The type of the map that stores the arc costs. deba@501: /// deba@501: /// 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@501: deba@501: /// \brief The value type of the costs. deba@501: /// deba@501: /// The value type of the costs. deba@501: typedef typename CostMap::Value Value; deba@501: deba@501: /// \brief The type of the map that stores which arcs are in the deba@501: /// arborescence. deba@501: /// deba@501: /// 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@501: typedef typename Digraph::template ArcMap ArborescenceMap; deba@501: kpeter@559: /// \brief Instantiates a \c ArborescenceMap. deba@501: /// 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@501: static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ deba@501: return new ArborescenceMap(digraph); deba@501: } deba@501: kpeter@559: /// \brief The type of the \c PredMap deba@501: /// 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@501: typedef typename Digraph::template NodeMap PredMap; deba@501: kpeter@559: /// \brief Instantiates a \c PredMap. deba@501: /// 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@501: static PredMap *createPredMap(const Digraph &digraph){ deba@501: return new PredMap(digraph); deba@501: } deba@501: deba@501: }; deba@501: deba@501: /// \ingroup spantree deba@501: /// kpeter@584: /// \brief Minimum Cost Arborescence algorithm class. deba@501: /// kpeter@625: /// This class provides an efficient implementation of the kpeter@584: /// Minimum Cost Arborescence algorithm. The arborescence is a tree deba@501: /// 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@501: /// given sources and spans all the nodes which are reachable from the kpeter@1080: /// sources. The time complexity of the algorithm is O(n2+m). deba@501: /// kpeter@625: /// The algorithm also provides an optimal dual solution, therefore deba@501: /// the optimality of the solution can be checked. deba@501: /// 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@501: /// 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@501: /// it is necessary. The default map type is \ref deba@501: /// concepts::Digraph::ArcMap "Digraph::ArcMap". kpeter@825: /// \tparam TR The traits class that defines various types used by the kpeter@825: /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits kpeter@625: /// "MinCostArborescenceDefaultTraits". kpeter@825: /// In most cases, this parameter should not be set directly, kpeter@825: /// consider to use the named template parameters instead. deba@501: #ifndef DOXYGEN kpeter@625: template , kpeter@559: typename TR = kpeter@559: MinCostArborescenceDefaultTraits > deba@501: #else kpeter@825: template deba@501: #endif deba@501: class MinCostArborescence { deba@501: public: deba@501: alpar@1074: /// \brief The \ref lemon::MinCostArborescenceDefaultTraits "traits class" alpar@877: /// of the algorithm. kpeter@559: typedef TR Traits; deba@501: /// The type of the underlying digraph. deba@501: typedef typename Traits::Digraph Digraph; deba@501: /// The type of the map that stores the arc costs. deba@501: typedef typename Traits::CostMap CostMap; deba@501: ///The type of the costs of the arcs. deba@501: typedef typename Traits::Value Value; deba@501: ///The type of the predecessor map. deba@501: typedef typename Traits::PredMap PredMap; deba@501: ///The type of the map that stores which arcs are in the arborescence. deba@501: typedef typename Traits::ArborescenceMap ArborescenceMap; deba@501: deba@501: typedef MinCostArborescence Create; deba@501: deba@501: private: deba@501: deba@501: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); deba@501: deba@501: struct CostArc { deba@501: deba@501: Arc arc; deba@501: Value value; deba@501: deba@501: CostArc() {} deba@501: CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {} deba@501: deba@501: }; deba@501: deba@501: const Digraph *_digraph; deba@501: const CostMap *_cost; deba@501: deba@501: PredMap *_pred; deba@501: bool local_pred; deba@501: deba@501: ArborescenceMap *_arborescence; deba@501: bool local_arborescence; deba@501: deba@501: typedef typename Digraph::template ArcMap ArcOrder; deba@501: ArcOrder *_arc_order; deba@501: deba@501: typedef typename Digraph::template NodeMap NodeOrder; deba@501: NodeOrder *_node_order; deba@501: deba@501: typedef typename Digraph::template NodeMap CostArcMap; deba@501: CostArcMap *_cost_arcs; deba@501: deba@501: struct StackLevel { deba@501: deba@501: std::vector arcs; deba@501: int node_level; deba@501: deba@501: }; deba@501: deba@501: std::vector level_stack; deba@501: std::vector queue; deba@501: deba@501: typedef std::vector DualNodeList; deba@501: deba@501: DualNodeList _dual_node_list; deba@501: deba@501: struct DualVariable { deba@501: int begin, end; deba@501: Value value; deba@501: deba@501: DualVariable(int _begin, int _end, Value _value) deba@501: : begin(_begin), end(_end), value(_value) {} deba@501: deba@501: }; deba@501: deba@501: typedef std::vector DualVariables; deba@501: deba@501: DualVariables _dual_variables; deba@501: deba@501: typedef typename Digraph::template NodeMap HeapCrossRef; deba@501: deba@501: HeapCrossRef *_heap_cross_ref; deba@501: deba@501: typedef BinHeap Heap; deba@501: deba@501: Heap *_heap; deba@501: deba@501: protected: deba@501: deba@501: MinCostArborescence() {} deba@501: deba@501: private: deba@501: deba@501: void createStructures() { deba@501: if (!_pred) { deba@501: local_pred = true; deba@501: _pred = Traits::createPredMap(*_digraph); deba@501: } deba@501: if (!_arborescence) { deba@501: local_arborescence = true; deba@501: _arborescence = Traits::createArborescenceMap(*_digraph); deba@501: } deba@501: if (!_arc_order) { deba@501: _arc_order = new ArcOrder(*_digraph); deba@501: } deba@501: if (!_node_order) { deba@501: _node_order = new NodeOrder(*_digraph); deba@501: } deba@501: if (!_cost_arcs) { deba@501: _cost_arcs = new CostArcMap(*_digraph); deba@501: } deba@501: if (!_heap_cross_ref) { deba@501: _heap_cross_ref = new HeapCrossRef(*_digraph, -1); deba@501: } deba@501: if (!_heap) { deba@501: _heap = new Heap(*_heap_cross_ref); deba@501: } deba@501: } deba@501: deba@501: void destroyStructures() { deba@501: if (local_arborescence) { deba@501: delete _arborescence; deba@501: } deba@501: if (local_pred) { deba@501: delete _pred; deba@501: } deba@501: if (_arc_order) { deba@501: delete _arc_order; deba@501: } deba@501: if (_node_order) { deba@501: delete _node_order; deba@501: } deba@501: if (_cost_arcs) { deba@501: delete _cost_arcs; deba@501: } deba@501: if (_heap) { deba@501: delete _heap; deba@501: } deba@501: if (_heap_cross_ref) { deba@501: delete _heap_cross_ref; deba@501: } deba@501: } deba@501: deba@501: Arc prepare(Node node) { deba@501: std::vector nodes; deba@501: (*_node_order)[node] = _dual_node_list.size(); deba@501: StackLevel level; deba@501: level.node_level = _dual_node_list.size(); deba@501: _dual_node_list.push_back(node); deba@501: for (InArcIt it(*_digraph, node); it != INVALID; ++it) { deba@501: Arc arc = it; deba@501: Node source = _digraph->source(arc); deba@501: Value value = (*_cost)[it]; deba@501: if (source == node || (*_node_order)[source] == -3) continue; deba@501: if ((*_cost_arcs)[source].arc == INVALID) { deba@501: (*_cost_arcs)[source].arc = arc; deba@501: (*_cost_arcs)[source].value = value; deba@501: nodes.push_back(source); deba@501: } else { deba@501: if ((*_cost_arcs)[source].value > value) { deba@501: (*_cost_arcs)[source].arc = arc; deba@501: (*_cost_arcs)[source].value = value; deba@501: } deba@501: } deba@501: } deba@501: CostArc minimum = (*_cost_arcs)[nodes[0]]; deba@501: for (int i = 1; i < int(nodes.size()); ++i) { deba@501: if ((*_cost_arcs)[nodes[i]].value < minimum.value) { deba@501: minimum = (*_cost_arcs)[nodes[i]]; deba@501: } deba@501: } kpeter@581: (*_arc_order)[minimum.arc] = _dual_variables.size(); deba@501: DualVariable var(_dual_node_list.size() - 1, deba@501: _dual_node_list.size(), minimum.value); deba@501: _dual_variables.push_back(var); deba@501: for (int i = 0; i < int(nodes.size()); ++i) { deba@501: (*_cost_arcs)[nodes[i]].value -= minimum.value; deba@501: level.arcs.push_back((*_cost_arcs)[nodes[i]]); deba@501: (*_cost_arcs)[nodes[i]].arc = INVALID; deba@501: } deba@501: level_stack.push_back(level); deba@501: return minimum.arc; deba@501: } deba@501: deba@501: Arc contract(Node node) { deba@501: int node_bottom = bottom(node); deba@501: std::vector nodes; deba@501: while (!level_stack.empty() && deba@501: level_stack.back().node_level >= node_bottom) { deba@501: for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) { deba@501: Arc arc = level_stack.back().arcs[i].arc; deba@501: Node source = _digraph->source(arc); deba@501: Value value = level_stack.back().arcs[i].value; deba@501: if ((*_node_order)[source] >= node_bottom) continue; deba@501: if ((*_cost_arcs)[source].arc == INVALID) { deba@501: (*_cost_arcs)[source].arc = arc; deba@501: (*_cost_arcs)[source].value = value; deba@501: nodes.push_back(source); deba@501: } else { deba@501: if ((*_cost_arcs)[source].value > value) { deba@501: (*_cost_arcs)[source].arc = arc; deba@501: (*_cost_arcs)[source].value = value; deba@501: } deba@501: } deba@501: } deba@501: level_stack.pop_back(); deba@501: } deba@501: CostArc minimum = (*_cost_arcs)[nodes[0]]; deba@501: for (int i = 1; i < int(nodes.size()); ++i) { deba@501: if ((*_cost_arcs)[nodes[i]].value < minimum.value) { deba@501: minimum = (*_cost_arcs)[nodes[i]]; deba@501: } deba@501: } kpeter@581: (*_arc_order)[minimum.arc] = _dual_variables.size(); deba@501: DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); deba@501: _dual_variables.push_back(var); deba@501: StackLevel level; deba@501: level.node_level = node_bottom; deba@501: for (int i = 0; i < int(nodes.size()); ++i) { deba@501: (*_cost_arcs)[nodes[i]].value -= minimum.value; deba@501: level.arcs.push_back((*_cost_arcs)[nodes[i]]); deba@501: (*_cost_arcs)[nodes[i]].arc = INVALID; deba@501: } deba@501: level_stack.push_back(level); deba@501: return minimum.arc; deba@501: } deba@501: deba@501: int bottom(Node node) { deba@501: int k = level_stack.size() - 1; deba@501: while (level_stack[k].node_level > (*_node_order)[node]) { deba@501: --k; deba@501: } deba@501: return level_stack[k].node_level; deba@501: } deba@501: deba@501: void finalize(Arc arc) { deba@501: Node node = _digraph->target(arc); deba@501: _heap->push(node, (*_arc_order)[arc]); deba@501: _pred->set(node, arc); deba@501: while (!_heap->empty()) { deba@501: Node source = _heap->top(); deba@501: _heap->pop(); kpeter@581: (*_node_order)[source] = -1; deba@501: for (OutArcIt it(*_digraph, source); it != INVALID; ++it) { deba@501: if ((*_arc_order)[it] < 0) continue; deba@501: Node target = _digraph->target(it); deba@501: switch(_heap->state(target)) { deba@501: case Heap::PRE_HEAP: deba@501: _heap->push(target, (*_arc_order)[it]); deba@501: _pred->set(target, it); deba@501: break; deba@501: case Heap::IN_HEAP: deba@501: if ((*_arc_order)[it] < (*_heap)[target]) { deba@501: _heap->decrease(target, (*_arc_order)[it]); deba@501: _pred->set(target, it); deba@501: } deba@501: break; deba@501: case Heap::POST_HEAP: deba@501: break; deba@501: } deba@501: } deba@501: _arborescence->set((*_pred)[source], true); deba@501: } deba@501: } deba@501: deba@501: deba@501: public: deba@501: kpeter@584: /// \name Named Template Parameters deba@501: deba@501: /// @{ deba@501: deba@501: template kpeter@625: struct SetArborescenceMapTraits : public Traits { deba@501: typedef T ArborescenceMap; deba@501: static ArborescenceMap *createArborescenceMap(const Digraph &) deba@501: { deba@501: LEMON_ASSERT(false, "ArborescenceMap is not initialized"); deba@501: return 0; // ignore warnings deba@501: } deba@501: }; deba@501: deba@501: /// \brief \ref named-templ-param "Named parameter" for kpeter@625: /// setting \c ArborescenceMap type deba@501: /// deba@501: /// \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@501: template kpeter@625: struct SetArborescenceMap deba@501: : public MinCostArborescence > { deba@501: }; deba@501: deba@501: template kpeter@625: struct SetPredMapTraits : public Traits { deba@501: typedef T PredMap; deba@501: static PredMap *createPredMap(const Digraph &) deba@501: { deba@501: LEMON_ASSERT(false, "PredMap is not initialized"); kpeter@625: return 0; // ignore warnings deba@501: } deba@501: }; deba@501: deba@501: /// \brief \ref named-templ-param "Named parameter" for kpeter@625: /// setting \c PredMap type deba@501: /// deba@501: /// \ref named-templ-param "Named parameter" for setting kpeter@625: /// \c PredMap type. alpar@877: /// 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@501: template kpeter@625: struct SetPredMap kpeter@625: : public MinCostArborescence > { deba@501: }; deba@501: deba@501: /// @} deba@501: deba@501: /// \brief Constructor. deba@501: /// kpeter@559: /// \param digraph The digraph the algorithm will run on. kpeter@559: /// \param cost The cost map used by the algorithm. deba@501: MinCostArborescence(const Digraph& digraph, const CostMap& cost) deba@501: : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false), deba@501: _arborescence(0), local_arborescence(false), deba@501: _arc_order(0), _node_order(0), _cost_arcs(0), deba@501: _heap_cross_ref(0), _heap(0) {} deba@501: deba@501: /// \brief Destructor. deba@501: ~MinCostArborescence() { deba@501: destroyStructures(); deba@501: } deba@501: deba@501: /// \brief Sets the arborescence map. deba@501: /// deba@501: /// Sets the arborescence map. kpeter@559: /// \return (*this) deba@501: MinCostArborescence& arborescenceMap(ArborescenceMap& m) { deba@501: if (local_arborescence) { deba@501: delete _arborescence; deba@501: } deba@501: local_arborescence = false; deba@501: _arborescence = &m; deba@501: return *this; deba@501: } deba@501: kpeter@625: /// \brief Sets the predecessor map. deba@501: /// kpeter@625: /// Sets the predecessor map. kpeter@559: /// \return (*this) deba@501: MinCostArborescence& predMap(PredMap& m) { deba@501: if (local_pred) { deba@501: delete _pred; deba@501: } deba@501: local_pred = false; deba@501: _pred = &m; deba@501: return *this; deba@501: } deba@501: kpeter@584: /// \name Execution Control deba@501: /// The simplest way to execute the algorithm is to use deba@501: /// 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@501: /// source nodes with \ref addSource(). deba@501: /// Finally \ref start() will perform the arborescence deba@501: /// computation. deba@501: deba@501: ///@{ deba@501: deba@501: /// \brief Initializes the internal data structures. deba@501: /// deba@501: /// Initializes the internal data structures. deba@501: /// deba@501: void init() { deba@501: createStructures(); deba@501: _heap->clear(); deba@501: for (NodeIt it(*_digraph); it != INVALID; ++it) { deba@501: (*_cost_arcs)[it].arc = INVALID; kpeter@581: (*_node_order)[it] = -3; kpeter@581: (*_heap_cross_ref)[it] = Heap::PRE_HEAP; deba@501: _pred->set(it, INVALID); deba@501: } deba@501: for (ArcIt it(*_digraph); it != INVALID; ++it) { deba@501: _arborescence->set(it, false); kpeter@581: (*_arc_order)[it] = -1; deba@501: } deba@501: _dual_node_list.clear(); deba@501: _dual_variables.clear(); deba@501: } deba@501: deba@501: /// \brief Adds a new source node. deba@501: /// deba@501: /// Adds a new source node to the algorithm. deba@501: void addSource(Node source) { deba@501: std::vector nodes; deba@501: nodes.push_back(source); deba@501: while (!nodes.empty()) { deba@501: Node node = nodes.back(); deba@501: nodes.pop_back(); deba@501: for (OutArcIt it(*_digraph, node); it != INVALID; ++it) { deba@501: Node target = _digraph->target(it); deba@501: if ((*_node_order)[target] == -3) { deba@501: (*_node_order)[target] = -2; deba@501: nodes.push_back(target); deba@501: queue.push_back(target); deba@501: } deba@501: } deba@501: } deba@501: (*_node_order)[source] = -1; deba@501: } deba@501: deba@501: /// \brief Processes the next node in the priority queue. deba@501: /// deba@501: /// Processes the next node in the priority queue. deba@501: /// deba@501: /// \return The processed node. deba@501: /// kpeter@625: /// \warning The queue must not be empty. deba@501: Node processNextNode() { deba@501: Node node = queue.back(); deba@501: queue.pop_back(); deba@501: if ((*_node_order)[node] == -2) { deba@501: Arc arc = prepare(node); deba@501: Node source = _digraph->source(arc); deba@501: while ((*_node_order)[source] != -1) { deba@501: if ((*_node_order)[source] >= 0) { deba@501: arc = contract(source); deba@501: } else { deba@501: arc = prepare(source); deba@501: } deba@501: source = _digraph->source(arc); deba@501: } deba@501: finalize(arc); deba@501: level_stack.clear(); deba@501: } deba@501: return node; deba@501: } deba@501: deba@501: /// \brief Returns the number of the nodes to be processed. deba@501: /// kpeter@625: /// Returns the number of the nodes to be processed in the priority kpeter@625: /// queue. deba@501: int queueSize() const { deba@501: return queue.size(); deba@501: } deba@501: deba@501: /// \brief Returns \c false if there are nodes to be processed. deba@501: /// deba@501: /// Returns \c false if there are nodes to be processed. deba@501: bool emptyQueue() const { deba@501: return queue.empty(); deba@501: } deba@501: deba@501: /// \brief Executes the algorithm. deba@501: /// deba@501: /// Executes the algorithm. deba@501: /// deba@501: /// \pre init() must be called and at least one node should be added deba@501: /// with addSource() before using this function. deba@501: /// deba@501: ///\note mca.start() is just a shortcut of the following code. deba@501: ///\code deba@501: ///while (!mca.emptyQueue()) { deba@501: /// mca.processNextNode(); deba@501: ///} deba@501: ///\endcode deba@501: void start() { deba@501: while (!emptyQueue()) { deba@501: processNextNode(); deba@501: } deba@501: } deba@501: deba@501: /// \brief Runs %MinCostArborescence algorithm from node \c s. deba@501: /// deba@501: /// This method runs the %MinCostArborescence algorithm from deba@501: /// a root node \c s. deba@501: /// deba@501: /// \note mca.run(s) is just a shortcut of the following code. deba@501: /// \code deba@501: /// mca.init(); deba@501: /// mca.addSource(s); deba@501: /// mca.start(); deba@501: /// \endcode kpeter@625: void run(Node s) { deba@501: init(); kpeter@625: addSource(s); deba@501: start(); deba@501: } deba@501: deba@501: ///@} deba@501: 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@501: }; deba@501: deba@501: /// \ingroup spantree deba@501: /// deba@501: /// \brief Function type interface for MinCostArborescence algorithm. deba@501: /// deba@501: /// 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@501: /// deba@501: /// \sa MinCostArborescence deba@501: template deba@501: typename CostMap::Value minCostArborescence(const Digraph& digraph, deba@501: const CostMap& cost, deba@501: typename Digraph::Node source, deba@501: ArborescenceMap& arborescence) { deba@501: typename MinCostArborescence kpeter@625: ::template SetArborescenceMap deba@501: ::Create mca(digraph, cost); deba@501: mca.arborescenceMap(arborescence); deba@501: mca.run(source); kpeter@625: return mca.arborescenceCost(); deba@501: } deba@501: deba@501: } deba@501: deba@501: #endif