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