diff --git a/lemon/min_cost_arborescence.h b/lemon/min_cost_arborescence.h --- a/lemon/min_cost_arborescence.h +++ b/lemon/min_cost_arborescence.h @@ -36,7 +36,7 @@ /// /// Default traits class for MinCostArborescence class. /// \param GR Digraph type. - /// \param CM Type of cost map. + /// \param CM Type of the cost map. template struct MinCostArborescenceDefaultTraits{ @@ -46,7 +46,7 @@ /// \brief The type of the map that stores the arc costs. /// /// The type of the map that stores the arc costs. - /// It must meet the \ref concepts::ReadMap "ReadMap" concept. + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef CM CostMap; /// \brief The value type of the costs. @@ -58,23 +58,26 @@ /// arborescence. /// /// The type of the map that stores which arcs are in the - /// arborescence. It must meet the \ref concepts::WriteMap - /// "WriteMap" concept. Initially it will be set to false on each - /// arc. After it will set all arborescence arcs once. + /// arborescence. It must conform to the \ref concepts::WriteMap + /// "WriteMap" concept, and its value type must be \c bool + /// (or convertible). Initially it will be set to \c false on each + /// arc, then it will be set on each arborescence arc once. typedef typename Digraph::template ArcMap ArborescenceMap; /// \brief Instantiates a \c ArborescenceMap. /// /// This function instantiates a \c ArborescenceMap. - /// \param digraph is the graph, to which we would like to - /// calculate the \c ArborescenceMap. + /// \param digraph The digraph to which we would like to calculate + /// the \c ArborescenceMap. static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ return new ArborescenceMap(digraph); } /// \brief The type of the \c PredMap /// - /// The type of the \c PredMap. It is a node map with an arc value type. + /// The type of the \c PredMap. It must confrom to the + /// \ref concepts::WriteMap "WriteMap" concept, and its value type + /// must be the \c Arc type of the digraph. typedef typename Digraph::template NodeMap PredMap; /// \brief Instantiates a \c PredMap. @@ -92,32 +95,29 @@ /// /// \brief Minimum Cost Arborescence algorithm class. /// - /// This class provides an efficient implementation of + /// This class provides an efficient implementation of the /// Minimum Cost Arborescence algorithm. The arborescence is a tree /// which is directed from a given source node of the digraph. One or - /// more sources should be given for the algorithm and it will calculate - /// the minimum cost subgraph which are union of arborescences with the + /// more sources should be given to the algorithm and it will calculate + /// the minimum cost subgraph that is the union of arborescences with the /// given sources and spans all the nodes which are reachable from the /// sources. The time complexity of the algorithm is O(n2+e). /// - /// The algorithm provides also an optimal dual solution, therefore + /// The algorithm also provides an optimal dual solution, therefore /// the optimality of the solution can be checked. /// - /// \param GR The digraph type the algorithm runs on. The default value - /// is \ref ListDigraph. - /// \param CM This read-only ArcMap determines the costs of the + /// \param GR The digraph type the algorithm runs on. + /// \param CM A read-only arc map storing the costs of the /// arcs. It is read once for each arc, so the map may involve in - /// relatively time consuming process to compute the arc cost if + /// relatively time consuming process to compute the arc costs if /// it is necessary. The default map type is \ref /// concepts::Digraph::ArcMap "Digraph::ArcMap". /// \param TR Traits class to set various data types used /// by the algorithm. The default traits class is /// \ref MinCostArborescenceDefaultTraits - /// "MinCostArborescenceDefaultTraits". See \ref - /// MinCostArborescenceDefaultTraits for the documentation of a - /// MinCostArborescence traits class. + /// "MinCostArborescenceDefaultTraits". #ifndef DOXYGEN - template , typename TR = MinCostArborescenceDefaultTraits > @@ -127,7 +127,8 @@ class MinCostArborescence { public: - /// The traits. + /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" + /// of the algorithm. typedef TR Traits; /// The type of the underlying digraph. typedef typename Traits::Digraph Digraph; @@ -395,7 +396,7 @@ /// @{ template - struct DefArborescenceMapTraits : public Traits { + struct SetArborescenceMapTraits : public Traits { typedef T ArborescenceMap; static ArborescenceMap *createArborescenceMap(const Digraph &) { @@ -405,33 +406,40 @@ }; /// \brief \ref named-templ-param "Named parameter" for - /// setting ArborescenceMap type + /// setting \c ArborescenceMap type /// /// \ref named-templ-param "Named parameter" for setting - /// ArborescenceMap type + /// \c ArborescenceMap type. + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept, + /// and its value type must be \c bool (or convertible). + /// Initially it will be set to \c false on each arc, + /// then it will be set on each arborescence arc once. template - struct DefArborescenceMap + struct SetArborescenceMap : public MinCostArborescence > { + SetArborescenceMapTraits > { }; template - struct DefPredMapTraits : public Traits { + struct SetPredMapTraits : public Traits { typedef T PredMap; static PredMap *createPredMap(const Digraph &) { LEMON_ASSERT(false, "PredMap is not initialized"); + return 0; // ignore warnings } }; /// \brief \ref named-templ-param "Named parameter" for - /// setting PredMap type + /// setting \c PredMap type /// /// \ref named-templ-param "Named parameter" for setting - /// PredMap type + /// \c PredMap type. + /// It must meet the \ref concepts::WriteMap "WriteMap" concept, + /// and its value type must be the \c Arc type of the digraph. template - struct DefPredMap - : public MinCostArborescence > { + struct SetPredMap + : public MinCostArborescence > { }; /// @} @@ -464,9 +472,9 @@ return *this; } - /// \brief Sets the arborescence map. + /// \brief Sets the predecessor map. /// - /// Sets the arborescence map. + /// Sets the predecessor map. /// \return (*this) MinCostArborescence& predMap(PredMap& m) { if (local_pred) { @@ -477,159 +485,6 @@ return *this; } - /// \name Query Functions - /// The result of the %MinCostArborescence algorithm can be obtained - /// using these functions.\n - /// Before the use of these functions, - /// either run() or start() must be called. - - /// @{ - - /// \brief Returns a reference to the arborescence map. - /// - /// Returns a reference to the arborescence map. - const ArborescenceMap& arborescenceMap() const { - return *_arborescence; - } - - /// \brief Returns true if the arc is in the arborescence. - /// - /// Returns true if the arc is in the arborescence. - /// \param arc The arc of the digraph. - /// \pre \ref run() must be called before using this function. - bool arborescence(Arc arc) const { - return (*_pred)[_digraph->target(arc)] == arc; - } - - /// \brief Returns a reference to the pred map. - /// - /// Returns a reference to the pred map. - const PredMap& predMap() const { - return *_pred; - } - - /// \brief Returns the predecessor arc of the given node. - /// - /// Returns the predecessor arc of the given node. - Arc pred(Node node) const { - return (*_pred)[node]; - } - - /// \brief Returns the cost of the arborescence. - /// - /// Returns the cost of the arborescence. - Value arborescenceValue() const { - Value sum = 0; - for (ArcIt it(*_digraph); it != INVALID; ++it) { - if (arborescence(it)) { - sum += (*_cost)[it]; - } - } - return sum; - } - - /// \brief Indicates that a node is reachable from the sources. - /// - /// Indicates that a node is reachable from the sources. - bool reached(Node node) const { - return (*_node_order)[node] != -3; - } - - /// \brief Indicates that a node is processed. - /// - /// Indicates that a node is processed. The arborescence path exists - /// from the source to the given node. - bool processed(Node node) const { - return (*_node_order)[node] == -1; - } - - /// \brief Returns the number of the dual variables in basis. - /// - /// Returns the number of the dual variables in basis. - int dualNum() const { - return _dual_variables.size(); - } - - /// \brief Returns the value of the dual solution. - /// - /// Returns the value of the dual solution. It should be - /// equal to the arborescence value. - Value dualValue() const { - Value sum = 0; - for (int i = 0; i < int(_dual_variables.size()); ++i) { - sum += _dual_variables[i].value; - } - return sum; - } - - /// \brief Returns the number of the nodes in the dual variable. - /// - /// Returns the number of the nodes in the dual variable. - int dualSize(int k) const { - return _dual_variables[k].end - _dual_variables[k].begin; - } - - /// \brief Returns the value of the dual variable. - /// - /// Returns the the value of the dual variable. - const Value& dualValue(int k) const { - return _dual_variables[k].value; - } - - /// \brief Lemon iterator for get a dual variable. - /// - /// Lemon iterator for get a dual variable. This class provides - /// a common style lemon iterator which gives back a subset of - /// the nodes. - class DualIt { - public: - - /// \brief Constructor. - /// - /// Constructor for get the nodeset of the variable. - DualIt(const MinCostArborescence& algorithm, int variable) - : _algorithm(&algorithm) - { - _index = _algorithm->_dual_variables[variable].begin; - _last = _algorithm->_dual_variables[variable].end; - } - - /// \brief Conversion to node. - /// - /// Conversion to node. - operator Node() const { - return _algorithm->_dual_node_list[_index]; - } - - /// \brief Increment operator. - /// - /// Increment operator. - DualIt& operator++() { - ++_index; - return *this; - } - - /// \brief Validity checking - /// - /// Checks whether the iterator is invalid. - bool operator==(Invalid) const { - return _index == _last; - } - - /// \brief Validity checking - /// - /// Checks whether the iterator is valid. - bool operator!=(Invalid) const { - return _index != _last; - } - - private: - const MinCostArborescence* _algorithm; - int _index, _last; - }; - - /// @} - /// \name Execution Control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). \n @@ -689,7 +544,7 @@ /// /// \return The processed node. /// - /// \warning The queue must not be empty! + /// \warning The queue must not be empty. Node processNextNode() { Node node = queue.back(); queue.pop_back(); @@ -712,7 +567,8 @@ /// \brief Returns the number of the nodes to be processed. /// - /// Returns the number of the nodes to be processed. + /// Returns the number of the nodes to be processed in the priority + /// queue. int queueSize() const { return queue.size(); } @@ -754,14 +610,170 @@ /// mca.addSource(s); /// mca.start(); /// \endcode - void run(Node node) { + void run(Node s) { init(); - addSource(node); + addSource(s); start(); } ///@} + /// \name Query Functions + /// The result of the %MinCostArborescence algorithm can be obtained + /// using these functions.\n + /// Either run() or start() must be called before using them. + + /// @{ + + /// \brief Returns the cost of the arborescence. + /// + /// Returns the cost of the arborescence. + Value arborescenceCost() const { + Value sum = 0; + for (ArcIt it(*_digraph); it != INVALID; ++it) { + if (arborescence(it)) { + sum += (*_cost)[it]; + } + } + return sum; + } + + /// \brief Returns \c true if the arc is in the arborescence. + /// + /// Returns \c true if the given arc is in the arborescence. + /// \param arc An arc of the digraph. + /// \pre \ref run() must be called before using this function. + bool arborescence(Arc arc) const { + return (*_pred)[_digraph->target(arc)] == arc; + } + + /// \brief Returns a const reference to the arborescence map. + /// + /// Returns a const reference to the arborescence map. + /// \pre \ref run() must be called before using this function. + const ArborescenceMap& arborescenceMap() const { + return *_arborescence; + } + + /// \brief Returns the predecessor arc of the given node. + /// + /// Returns the predecessor arc of the given node. + /// \pre \ref run() must be called before using this function. + Arc pred(Node node) const { + return (*_pred)[node]; + } + + /// \brief Returns a const reference to the pred map. + /// + /// Returns a const reference to the pred map. + /// \pre \ref run() must be called before using this function. + const PredMap& predMap() const { + return *_pred; + } + + /// \brief Indicates that a node is reachable from the sources. + /// + /// Indicates that a node is reachable from the sources. + bool reached(Node node) const { + return (*_node_order)[node] != -3; + } + + /// \brief Indicates that a node is processed. + /// + /// Indicates that a node is processed. The arborescence path exists + /// from the source to the given node. + bool processed(Node node) const { + return (*_node_order)[node] == -1; + } + + /// \brief Returns the number of the dual variables in basis. + /// + /// Returns the number of the dual variables in basis. + int dualNum() const { + return _dual_variables.size(); + } + + /// \brief Returns the value of the dual solution. + /// + /// Returns the value of the dual solution. It should be + /// equal to the arborescence value. + Value dualValue() const { + Value sum = 0; + for (int i = 0; i < int(_dual_variables.size()); ++i) { + sum += _dual_variables[i].value; + } + return sum; + } + + /// \brief Returns the number of the nodes in the dual variable. + /// + /// Returns the number of the nodes in the dual variable. + int dualSize(int k) const { + return _dual_variables[k].end - _dual_variables[k].begin; + } + + /// \brief Returns the value of the dual variable. + /// + /// Returns the the value of the dual variable. + Value dualValue(int k) const { + return _dual_variables[k].value; + } + + /// \brief LEMON iterator for getting a dual variable. + /// + /// This class provides a common style LEMON iterator for getting a + /// dual variable of \ref MinCostArborescence algorithm. + /// It iterates over a subset of the nodes. + class DualIt { + public: + + /// \brief Constructor. + /// + /// Constructor for getting the nodeset of the dual variable + /// of \ref MinCostArborescence algorithm. + DualIt(const MinCostArborescence& algorithm, int variable) + : _algorithm(&algorithm) + { + _index = _algorithm->_dual_variables[variable].begin; + _last = _algorithm->_dual_variables[variable].end; + } + + /// \brief Conversion to \c Node. + /// + /// Conversion to \c Node. + operator Node() const { + return _algorithm->_dual_node_list[_index]; + } + + /// \brief Increment operator. + /// + /// Increment operator. + DualIt& operator++() { + ++_index; + return *this; + } + + /// \brief Validity checking + /// + /// Checks whether the iterator is invalid. + bool operator==(Invalid) const { + return _index == _last; + } + + /// \brief Validity checking + /// + /// Checks whether the iterator is valid. + bool operator!=(Invalid) const { + return _index != _last; + } + + private: + const MinCostArborescence* _algorithm; + int _index, _last; + }; + + /// @} + }; /// \ingroup spantree @@ -769,11 +781,12 @@ /// \brief Function type interface for MinCostArborescence algorithm. /// /// Function type interface for MinCostArborescence algorithm. - /// \param digraph The Digraph that the algorithm runs on. - /// \param cost The CostMap of the arcs. - /// \param source The source of the arborescence. - /// \retval arborescence The bool ArcMap which stores the arborescence. - /// \return The cost of the arborescence. + /// \param digraph The digraph the algorithm runs on. + /// \param cost An arc map storing the costs. + /// \param source The source node of the arborescence. + /// \retval arborescence An arc map with \c bool (or convertible) value + /// type that stores the arborescence. + /// \return The total cost of the arborescence. /// /// \sa MinCostArborescence template @@ -782,11 +795,11 @@ typename Digraph::Node source, ArborescenceMap& arborescence) { typename MinCostArborescence - ::template DefArborescenceMap + ::template SetArborescenceMap ::Create mca(digraph, cost); mca.arborescenceMap(arborescence); mca.run(source); - return mca.arborescenceValue(); + return mca.arborescenceCost(); } } diff --git a/test/min_cost_arborescence_test.cc b/test/min_cost_arborescence_test.cc --- a/test/min_cost_arborescence_test.cc +++ b/test/min_cost_arborescence_test.cc @@ -24,6 +24,7 @@ #include #include #include +#include #include "test_tools.h" @@ -70,6 +71,65 @@ "@attributes\n" "source 0\n"; + +void checkMinCostArborescenceCompile() +{ + typedef double VType; + typedef concepts::Digraph Digraph; + typedef concepts::ReadMap CostMap; + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; + typedef concepts::WriteMap ArbMap; + typedef concepts::ReadWriteMap PredMap; + + typedef MinCostArborescence:: + SetArborescenceMap:: + SetPredMap::Create MinCostArbType; + + Digraph g; + Node s, n; + Arc e; + VType c; + bool b; + int i; + CostMap cost; + ArbMap arb; + PredMap pred; + + MinCostArbType mcarb_test(g, cost); + const MinCostArbType& const_mcarb_test = mcarb_test; + + mcarb_test + .arborescenceMap(arb) + .predMap(pred) + .run(s); + + mcarb_test.init(); + mcarb_test.addSource(s); + mcarb_test.start(); + n = mcarb_test.processNextNode(); + b = const_mcarb_test.emptyQueue(); + i = const_mcarb_test.queueSize(); + + c = const_mcarb_test.arborescenceCost(); + b = const_mcarb_test.arborescence(e); + e = const_mcarb_test.pred(n); + const MinCostArbType::ArborescenceMap &am = + const_mcarb_test.arborescenceMap(); + const MinCostArbType::PredMap &pm = + const_mcarb_test.predMap(); + b = const_mcarb_test.reached(n); + b = const_mcarb_test.processed(n); + + i = const_mcarb_test.dualNum(); + c = const_mcarb_test.dualValue(); + i = const_mcarb_test.dualSize(i); + c = const_mcarb_test.dualValue(i); + + ignore_unused_variable_warning(am); + ignore_unused_variable_warning(pm); +} + int main() { typedef SmartDigraph Digraph; DIGRAPH_TYPEDEFS(Digraph); @@ -110,19 +170,19 @@ } } if (mca.arborescence(it)) { - check(sum == cost[it], "INVALID DUAL"); + check(sum == cost[it], "Invalid dual solution"); } - check(sum <= cost[it], "INVALID DUAL"); + check(sum <= cost[it], "Invalid dual solution"); } } - check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL"); + check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution"); - check(mca.reached(source), "INVALID ARBORESCENCE"); + check(mca.reached(source), "Invalid arborescence"); for (ArcIt a(digraph); a != INVALID; ++a) { check(!mca.reached(digraph.source(a)) || - mca.reached(digraph.target(a)), "INVALID ARBORESCENCE"); + mca.reached(digraph.target(a)), "Invalid arborescence"); } for (NodeIt n(digraph); n != INVALID; ++n) { @@ -130,17 +190,17 @@ int cnt = 0; for (InArcIt a(digraph, n); a != INVALID; ++a) { if (mca.arborescence(a)) { - check(mca.pred(n) == a, "INVALID ARBORESCENCE"); + check(mca.pred(n) == a, "Invalid arborescence"); ++cnt; } } - check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE"); + check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence"); } Digraph::ArcMap arborescence(digraph); - check(mca.arborescenceValue() == + check(mca.arborescenceCost() == minCostArborescence(digraph, cost, source, arborescence), - "WRONG FUNCTION"); + "Wrong result of the function interface"); return 0; }