deba@2017: /* -*- C++ -*- deba@2017: * deba@2017: * This file is a part of LEMON, a generic C++ optimization library deba@2017: * alpar@2553: * Copyright (C) 2003-2008 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 deba@2017: deba@2017: #include deba@2025: #include 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 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. alpar@2260: /// It must meet the \ref concepts::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. alpar@2260: /// It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@2259: /// Initially it will be set to false on each edge. After it deba@2025: /// will set all arborescence edges once. deba@2017: typedef typename Graph::template EdgeMap 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 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 alpar@2260: /// concepts::Graph::EdgeMap "Graph::EdgeMap". 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 , deba@2017: typename _Traits = deba@2017: MinCostArborescenceDefaultTraits<_Graph, _CostMap> > deba@2017: #else deba@2017: template 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: alpar@2151: virtual const char* what() const throw() { 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 EdgeOrder; deba@2025: EdgeOrder *_edge_order; deba@2025: deba@2025: typedef typename Graph::template NodeMap NodeOrder; deba@2025: NodeOrder *_node_order; deba@2017: deba@2017: typedef typename Graph::template NodeMap CostEdgeMap; deba@2017: CostEdgeMap *_cost_edges; deba@2017: deba@2017: struct StackLevel { deba@2017: deba@2017: std::vector edges; deba@2017: int node_level; deba@2017: deba@2017: }; deba@2017: deba@2017: std::vector level_stack; deba@2017: std::vector queue; deba@2017: deba@2025: typedef std::vector 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 DualVariables; deba@2025: deba@2025: DualVariables _dual_variables; deba@2025: deba@2025: typedef typename Graph::template NodeMap HeapCrossRef; deba@2025: deba@2025: HeapCrossRef *_heap_cross_ref; deba@2025: mqrelly@2263: typedef BinHeap 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 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 deba@2017: struct DefArborescenceMap deba@2017: : public MinCostArborescence > { deba@2017: typedef MinCostArborescence > Create; deba@2017: }; deba@2025: deba@2025: template 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 deba@2025: struct DefPredMap deba@2025: : public MinCostArborescence > { deba@2025: typedef MinCostArborescence > 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@2385: 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@2385: return static_cast(*this) == static_cast(it); deba@2025: } deba@2025: bool operator!=(const DualIt& it) const { deba@2385: return static_cast(*this) != static_cast(it); deba@2025: } deba@2025: bool operator<(const DualIt& it) const { deba@2385: return static_cast(*this) < static_cast(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@2385: _pred->set(it, INVALID); 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 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@2624: if (_edge_order) { deba@2025: delete _edge_order; deba@2025: } deba@2025: if (_node_order) { deba@2025: delete _node_order; deba@2017: } deba@2624: if (_cost_edges) { deba@2017: delete _cost_edges; deba@2017: } deba@2624: if (_heap) { deba@2025: delete _heap; deba@2025: } deba@2624: 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 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@2385: 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@2385: 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 nodes; deba@2017: while (!level_stack.empty() && deba@2017: level_stack.back().node_level >= node_bottom) { deba@2385: 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@2385: 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@2385: 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 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 deba@2017: ::template DefArborescenceMap 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