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.
deba@490: /// \param _Digraph Digraph type.
deba@490: /// \param _CostMap Type of cost map.
deba@490: template <class _Digraph, class _CostMap>
deba@490: struct MinCostArborescenceDefaultTraits{
deba@490:
deba@490: /// \brief The digraph type the algorithm runs on.
deba@490: typedef _Digraph 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.
deba@490: /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
deba@490: typedef _CostMap 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
deba@490: /// arborescence. It must meet the \ref concepts::WriteMap
deba@490: /// "WriteMap" concept. Initially it will be set to false on each
deba@490: /// arc. After it will set all arborescence arcs once.
deba@490: typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
deba@490:
deba@490: /// \brief Instantiates a ArborescenceMap.
deba@490: ///
deba@490: /// This function instantiates a \ref ArborescenceMap.
deba@490: /// \param digraph is the graph, to which we would like to
deba@490: /// calculate the ArborescenceMap.
deba@490: static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
deba@490: return new ArborescenceMap(digraph);
deba@490: }
deba@490:
deba@490: /// \brief The type of the PredMap
deba@490: ///
deba@490: /// The type of the PredMap. It is a node map with an arc value type.
deba@490: typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
deba@490:
deba@490: /// \brief Instantiates a PredMap.
deba@490: ///
deba@490: /// This function instantiates a \ref PredMap.
deba@490: /// \param _digraph is the digraph, to which we would like to define the
deba@490: /// 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: ///
deba@490: /// \brief %MinCostArborescence algorithm class.
deba@490: ///
deba@490: /// This class provides an efficient implementation of
deba@490: /// %MinCostArborescence algorithm. The arborescence is a tree
deba@490: /// which is directed from a given source node of the digraph. One or
deba@490: /// more sources should be given for the algorithm and it will calculate
deba@490: /// the minimum cost subgraph which are union of arborescences with the
deba@490: /// given sources and spans all the nodes which are reachable from the
deba@490: /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
deba@490: ///
deba@490: /// The algorithm provides also an optimal dual solution, therefore
deba@490: /// the optimality of the solution can be checked.
deba@490: ///
deba@490: /// \param _Digraph The digraph type the algorithm runs on. The default value
deba@490: /// is \ref ListDigraph.
deba@490: /// \param _CostMap This read-only ArcMap determines the costs of the
deba@490: /// arcs. It is read once for each arc, so the map may involve in
deba@490: /// relatively time consuming process to compute the arc cost if
deba@490: /// it is necessary. The default map type is \ref
deba@490: /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
deba@490: /// \param _Traits Traits class to set various data types used
deba@490: /// by the algorithm. The default traits class is
deba@490: /// \ref MinCostArborescenceDefaultTraits
deba@490: /// "MinCostArborescenceDefaultTraits<_Digraph, _CostMap>". See \ref
deba@490: /// MinCostArborescenceDefaultTraits for the documentation of a
deba@490: /// MinCostArborescence traits class.
deba@490: ///
deba@490: /// \author Balazs Dezso
deba@490: #ifndef DOXYGEN
deba@490: template <typename _Digraph = ListDigraph,
deba@490: typename _CostMap = typename _Digraph::template ArcMap<int>,
deba@490: typename _Traits =
deba@490: MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >
deba@490: #else
deba@490: template <typename _Digraph, typename _CostMap, typedef _Traits>
deba@490: #endif
deba@490: class MinCostArborescence {
deba@490: public:
deba@490:
deba@490: /// The traits.
deba@490: typedef _Traits 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: }
deba@490: _arc_order->set(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: }
deba@490: _arc_order->set(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();
deba@490: _node_order->set(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:
deba@490: /// \name Named template parameters
deba@490:
deba@490: /// @{
deba@490:
deba@490: template <class T>
deba@490: struct DefArborescenceMapTraits : 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
deba@490: /// setting ArborescenceMap type
deba@490: ///
deba@490: /// \ref named-templ-param "Named parameter" for setting
deba@490: /// ArborescenceMap type
deba@490: template <class T>
deba@490: struct DefArborescenceMap
deba@490: : public MinCostArborescence<Digraph, CostMap,
deba@490: DefArborescenceMapTraits<T> > {
deba@490: };
deba@490:
deba@490: template <class T>
deba@490: struct DefPredMapTraits : 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");
deba@490: }
deba@490: };
deba@490:
deba@490: /// \brief \ref named-templ-param "Named parameter" for
deba@490: /// setting PredMap type
deba@490: ///
deba@490: /// \ref named-templ-param "Named parameter" for setting
deba@490: /// PredMap type
deba@490: template <class T>
deba@490: struct DefPredMap
deba@490: : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
deba@490: };
deba@490:
deba@490: /// @}
deba@490:
deba@490: /// \brief Constructor.
deba@490: ///
deba@490: /// \param _digraph The digraph the algorithm will run on.
deba@490: /// \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.
deba@490: /// \return \c (*this)
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:
deba@490: /// \brief Sets the arborescence map.
deba@490: ///
deba@490: /// Sets the arborescence map.
deba@490: /// \return \c (*this)
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:
deba@490: /// \name Query Functions
deba@490: /// The result of the %MinCostArborescence algorithm can be obtained
deba@490: /// using these functions.\n
deba@490: /// Before the use of these functions,
deba@490: /// either run() or start() must be called.
deba@490:
deba@490: /// @{
deba@490:
deba@490: /// \brief Returns a reference to the arborescence map.
deba@490: ///
deba@490: /// Returns a reference to the arborescence map.
deba@490: const ArborescenceMap& arborescenceMap() const {
deba@490: return *_arborescence;
deba@490: }
deba@490:
deba@490: /// \brief Returns true if the arc is in the arborescence.
deba@490: ///
deba@490: /// Returns true if the arc is in the arborescence.
deba@490: /// \param arc The arc of the digraph.
deba@490: /// \pre \ref run() must be called before using this function.
deba@490: bool arborescence(Arc arc) const {
deba@490: return (*_pred)[_digraph->target(arc)] == arc;
deba@490: }
deba@490:
deba@490: /// \brief Returns a reference to the pred map.
deba@490: ///
deba@490: /// Returns a reference to the pred map.
deba@490: const PredMap& predMap() const {
deba@490: return *_pred;
deba@490: }
deba@490:
deba@490: /// \brief Returns the predecessor arc of the given node.
deba@490: ///
deba@490: /// Returns the predecessor arc of the given node.
deba@490: Arc pred(Node node) const {
deba@490: return (*_pred)[node];
deba@490: }
deba@490:
deba@490: /// \brief Returns the cost of the arborescence.
deba@490: ///
deba@490: /// Returns the cost of the arborescence.
deba@490: Value arborescenceValue() const {
deba@490: Value sum = 0;
deba@490: for (ArcIt it(*_digraph); it != INVALID; ++it) {
deba@490: if (arborescence(it)) {
deba@490: sum += (*_cost)[it];
deba@490: }
deba@490: }
deba@490: return sum;
deba@490: }
deba@490:
deba@490: /// \brief Indicates that a node is reachable from the sources.
deba@490: ///
deba@490: /// Indicates that a node is reachable from the sources.
deba@490: bool reached(Node node) const {
deba@490: return (*_node_order)[node] != -3;
deba@490: }
deba@490:
deba@490: /// \brief Indicates that a node is processed.
deba@490: ///
deba@490: /// Indicates that a node is processed. The arborescence path exists
deba@490: /// from the source to the given node.
deba@490: bool processed(Node node) const {
deba@490: return (*_node_order)[node] == -1;
deba@490: }
deba@490:
deba@490: /// \brief Returns the number of the dual variables in basis.
deba@490: ///
deba@490: /// Returns the number of the dual variables in basis.
deba@490: int dualNum() const {
deba@490: return _dual_variables.size();
deba@490: }
deba@490:
deba@490: /// \brief Returns the value of the dual solution.
deba@490: ///
deba@490: /// Returns the value of the dual solution. It should be
deba@490: /// equal to the arborescence value.
deba@490: Value dualValue() const {
deba@490: Value sum = 0;
deba@490: for (int i = 0; i < int(_dual_variables.size()); ++i) {
deba@490: sum += _dual_variables[i].value;
deba@490: }
deba@490: return sum;
deba@490: }
deba@490:
deba@490: /// \brief Returns the number of the nodes in the dual variable.
deba@490: ///
deba@490: /// Returns the number of the nodes in the dual variable.
deba@490: int dualSize(int k) const {
deba@490: return _dual_variables[k].end - _dual_variables[k].begin;
deba@490: }
deba@490:
deba@490: /// \brief Returns the value of the dual variable.
deba@490: ///
deba@490: /// Returns the the value of the dual variable.
deba@490: const Value& dualValue(int k) const {
deba@490: return _dual_variables[k].value;
deba@490: }
deba@490:
deba@490: /// \brief Lemon iterator for get a dual variable.
deba@490: ///
deba@490: /// Lemon iterator for get a dual variable. This class provides
deba@490: /// a common style lemon iterator which gives back a subset of
deba@490: /// the nodes.
deba@490: class DualIt {
deba@490: public:
deba@490:
deba@490: /// \brief Constructor.
deba@490: ///
deba@490: /// Constructor for get the nodeset of the variable.
deba@490: DualIt(const MinCostArborescence& algorithm, int variable)
deba@490: : _algorithm(&algorithm)
deba@490: {
deba@490: _index = _algorithm->_dual_variables[variable].begin;
deba@490: _last = _algorithm->_dual_variables[variable].end;
deba@490: }
deba@490:
deba@490: /// \brief Conversion to node.
deba@490: ///
deba@490: /// Conversion to node.
deba@490: operator Node() const {
deba@490: return _algorithm->_dual_node_list[_index];
deba@490: }
deba@490:
deba@490: /// \brief Increment operator.
deba@490: ///
deba@490: /// Increment operator.
deba@490: DualIt& operator++() {
deba@490: ++_index;
deba@490: return *this;
deba@490: }
deba@490:
deba@490: /// \brief Validity checking
deba@490: ///
deba@490: /// Checks whether the iterator is invalid.
deba@490: bool operator==(Invalid) const {
deba@490: return _index == _last;
deba@490: }
deba@490:
deba@490: /// \brief Validity checking
deba@490: ///
deba@490: /// Checks whether the iterator is valid.
deba@490: bool operator!=(Invalid) const {
deba@490: return _index != _last;
deba@490: }
deba@490:
deba@490: private:
deba@490: const MinCostArborescence* _algorithm;
deba@490: int _index, _last;
deba@490: };
deba@490:
deba@490: /// @}
deba@490:
deba@490: /// \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
deba@490: /// If you need more control on the execution,
deba@490: /// first you must call \ref init(), 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;
deba@490: _node_order->set(it, -3);
deba@490: _heap_cross_ref->set(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);
deba@490: _arc_order->set(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: ///
deba@490: /// \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: ///
deba@490: /// Returns the number of the nodes to be processed.
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
deba@490: void run(Node node) {
deba@490: init();
deba@490: addSource(node);
deba@490: start();
deba@490: }
deba@490:
deba@490: ///@}
deba@490:
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.
deba@490: /// \param digraph The Digraph that the algorithm runs on.
deba@490: /// \param cost The CostMap of the arcs.
deba@490: /// \param source The source of the arborescence.
deba@490: /// \retval arborescence The bool ArcMap which stores the arborescence.
deba@490: /// \return The 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>
deba@490: ::template DefArborescenceMap<ArborescenceMap>
deba@490: ::Create mca(digraph, cost);
deba@490: mca.arborescenceMap(arborescence);
deba@490: mca.run(source);
deba@490: return mca.arborescenceValue();
deba@490: }
deba@490:
deba@490: }
deba@490:
deba@490: #endif