# Changeset 637:b61354458b59 in lemon

Ignore:
Timestamp:
04/15/09 12:01:14 (11 years ago)
Branch:
default
Phase:
public
Message:

Imporvements for the matching algorithms (#264)

Files:
3 edited

Unmodified
Added
Removed
• ## doc/groups.dox

 r633 \brief Algorithms for finding matchings in graphs and bipartite graphs. This group contains algorithm objects and functions to calculate This group contains the algorithms for calculating matchings in graphs and bipartite graphs. The general matching problem is finding a subset of the arcs which does not shares common endpoints. finding a subset of the edges for which each node has at most one incident edge. There are several different algorithms for calculate matchings in
• ## lemon/max_matching.h

 r628 /// \ingroup matching /// /// \brief Edmonds' alternating forest maximum matching algorithm. /// \brief Maximum cardinality matching in general graphs /// /// This class implements Edmonds' alternating forest matching /// algorithm. The algorithm can be started from an arbitrary initial /// matching (the default is the empty one) /// This class implements Edmonds' alternating forest matching algorithm /// for finding a maximum cardinality matching in a general graph. /// It can be started from an arbitrary initial matching /// (the default is the empty one). /// /// The dual solution of the problem is a map of the nodes to /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c /// MATCHED/C showing the Gallai-Edmonds decomposition of the /// graph. The nodes in \c EVEN/D induce a graph with /// factor-critical components, the nodes in \c ODD/A form the /// barrier, and the nodes in \c MATCHED/C induce a graph having a /// perfect matching. The number of the factor-critical components /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D), /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph /// with factor-critical components, the nodes in \c ODD/A form the /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having /// a perfect matching. The number of the factor-critical components /// minus the number of barrier nodes is a lower bound on the /// unmatched nodes, and the matching is optimal if and only if this bound is /// tight. This decomposition can be attained by calling \c /// tight. This decomposition can be obtained by calling \c /// decomposition() after running the algorithm. /// /// \param GR The graph type the algorithm runs on. /// \tparam GR The graph type the algorithm runs on. template class MaxMatching { public: /// The graph type of the algorithm typedef GR Graph; typedef typename Graph::template NodeMap MatchingMap; ///\brief Indicates the Gallai-Edmonds decomposition of the graph. /// ///Indicates the Gallai-Edmonds decomposition of the graph. The ///nodes with Status \c EVEN/D induce a graph with factor-critical ///components, the nodes in \c ODD/A form the canonical barrier, ///and the nodes in \c MATCHED/C induce a graph having a perfect ///matching. ///\brief Status constants for Gallai-Edmonds decomposition. /// ///These constants are used for indicating the Gallai-Edmonds ///decomposition of a graph. The nodes with status \c EVEN (or \c D) ///induce a subgraph with factor-critical components, the nodes with ///status \c ODD (or \c A) form the canonical barrier, and the nodes ///with status \c MATCHED (or \c C) induce a subgraph having a ///perfect matching. enum Status { EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2 EVEN = 1,       ///< = 1. (\c D is an alias for \c EVEN.) D = 1, MATCHED = 0,    ///< = 0. (\c C is an alias for \c MATCHED.) C = 0, ODD = -1,       ///< = -1. (\c A is an alias for \c ODD.) A = -1, UNMATCHED = -2  ///< = -2. }; } void extendOnArc(const Arc& a) { Node base = _graph.source(a); } /// \name Execution control /// \name Execution Control /// The simplest way to execute the algorithm is to use the /// \c run() member function. /// \n /// If you need better control on the execution, you must call /// \ref init(), \ref greedyInit() or \ref matchingInit() /// functions first, then you can start the algorithm with the \ref /// startSparse() or startDense() functions. /// \c run() member function.\n /// If you need better control on the execution, you have to call /// one of the functions \ref init(), \ref greedyInit() or /// \ref matchingInit() first, then you can start the algorithm with /// \ref startSparse() or \ref startDense(). ///@{ /// \brief Sets the actual matching to the empty matching. /// /// Sets the actual matching to the empty matching. /// /// \brief Set the initial matching to the empty matching. /// /// This function sets the initial matching to the empty matching. void init() { createStructures(); } ///\brief Finds an initial matching in a greedy way /// ///It finds an initial matching in a greedy way. /// \brief Find an initial matching in a greedy way. /// /// This function finds an initial matching in a greedy way. void greedyInit() { createStructures(); /// \brief Initialize the matching from a map containing. /// /// Initialize the matching from a \c bool valued \c Edge map. This /// map must have the property that there are no two incident edges /// with true value, ie. it contains a matching. /// \brief Initialize the matching from a map. /// /// This function initializes the matching from a \c bool valued edge /// map. This map should have the property that there are no two incident /// edges with \c true value, i.e. it really contains a matching. /// \return \c true if the map contains a matching. template } /// \brief Starts Edmonds' algorithm /// /// If runs the original Edmonds' algorithm. /// \brief Start Edmonds' algorithm /// /// This function runs the original Edmonds' algorithm. /// /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be /// called before using this function. void startSparse() { for(NodeIt n(_graph); n != INVALID; ++n) { } /// \brief Starts Edmonds' algorithm. /// /// It runs Edmonds' algorithm with a heuristic of postponing /// \brief Start Edmonds' algorithm with a heuristic improvement /// for dense graphs /// /// This function runs Edmonds' algorithm with a heuristic of postponing /// shrinks, therefore resulting in a faster algorithm for dense graphs. /// /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be /// called before using this function. void startDense() { for(NodeIt n(_graph); n != INVALID; ++n) { /// \brief Runs Edmonds' algorithm /// /// Runs Edmonds' algorithm for sparse graphs (m<2*n) /// or Edmonds' algorithm with a heuristic of /// postponing shrinks for dense graphs. /// \brief Run Edmonds' algorithm /// /// This function runs Edmonds' algorithm. An additional heuristic of /// postponing shrinks is used for relatively dense graphs /// (for which m>=2*n holds). void run() { if (countEdges(_graph) < 2 * countNodes(_graph)) { /// @} /// \name Primal solution /// Functions to get the primal solution, ie. the matching. /// \name Primal Solution /// Functions to get the primal solution, i.e. the maximum matching. /// @{ ///\brief Returns the size of the current matching. /// ///Returns the size of the current matching. After \ref ///run() it returns the size of the maximum matching in the graph. /// \brief Return the size (cardinality) of the matching. /// /// This function returns the size (cardinality) of the current matching. /// After run() it returns the size of the maximum matching in the graph. int matchingSize() const { int size = 0; } /// \brief Returns true when the edge is in the matching. /// /// Returns true when the edge is in the matching. /// \brief Return \c true if the given edge is in the matching. /// /// This function returns \c true if the given edge is in the current /// matching. bool matching(const Edge& edge) const { return edge == (*_matching)[_graph.u(edge)]; } /// \brief Returns the matching edge incident to the given node. /// /// Returns the matching edge of a \c node in the actual matching or /// INVALID if the \c node is not covered by the actual matching. /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the /// given node in the current matching or \c INVALID if the node is /// not covered by the matching. Arc matching(const Node& n) const { return (*_matching)[n]; } ///\brief Returns the mate of a node in the actual matching. /// ///Returns the mate of a \c node in the actual matching or ///INVALID if the \c node is not covered by the actual matching. /// \brief Return the mate of the given node. /// /// This function returns the mate of the given node in the current /// matching or \c INVALID if the node is not covered by the matching. Node mate(const Node& n) const { return (*_matching)[n] != INVALID ? /// @} /// \name Dual solution /// Functions to get the dual solution, ie. the decomposition. /// \name Dual Solution /// Functions to get the dual solution, i.e. the Gallai-Edmonds /// decomposition. /// @{ /// \brief Returns the class of the node in the Edmonds-Gallai /// \brief Return the status of the given node in the Edmonds-Gallai /// decomposition. /// /// Returns the class of the node in the Edmonds-Gallai /// decomposition. /// This function returns the \ref Status "status" of the given node /// in the Edmonds-Gallai decomposition. Status decomposition(const Node& n) const { return (*_status)[n]; } /// \brief Returns true when the node is in the barrier. /// /// Returns true when the node is in the barrier. /// \brief Return \c true if the given node is in the barrier. /// /// This function returns \c true if the given node is in the barrier. bool barrier(const Node& n) const { return (*_status)[n] == ODD; /// \f$O(nm\log n)\f$ time complexity. /// /// The maximum weighted matching problem is to find undirected /// edges in the graph with maximum overall weight and no two of /// them shares their ends. The problem can be formulated with the /// following linear program. /// The maximum weighted matching problem is to find a subset of the /// edges in an undirected graph with maximum overall weight for which /// each node has at most one incident edge. /// It can be formulated with the following linear program. /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f] /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} /// optimality. The solution of the dual problem can be used to check /// the result of the algorithm. The dual linear problem is the /// following. /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)} z_B \ge w_{uv} \quad \forall uv\in E\f] */ \frac{\vert B \vert - 1}{2}z_B\f] */ /// /// The algorithm can be executed with \c run() or the \c init() and /// then the \c start() member functions. After it the matching can /// be asked with \c matching() or mate() functions. The dual /// solution can be get with \c nodeValue(), \c blossomNum() and \c /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt /// "BlossomIt" nested class, which is able to iterate on the nodes /// of a blossom. If the value type is integral then the dual /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". /// The algorithm can be executed with the run() function. /// After it the matching (the primal solution) and the dual solution /// can be obtained using the query functions and the /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, /// which is able to iterate on the nodes of a blossom. /// If the value type is integer, then the dual solution is multiplied /// by \ref MaxWeightedMatching::dualScale "4". /// /// \tparam GR The graph type the algorithm runs on. /// \tparam WM The type edge weight map. The default type is /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template #else template > #endif class MaxWeightedMatching { public: ///\e /// The graph type of the algorithm typedef GR Graph; ///\e /// The type of the edge weight map typedef WM WeightMap; ///\e /// The value type of the edge weights typedef typename WeightMap::Value Value; typedef typename Graph::template NodeMap MatchingMap; /// \brief Scaling factor for dual solution /// /// Scaling factor for dual solution, it is equal to 4 or 1 /// Scaling factor for dual solution. It is equal to 4 or 1 /// according to the value type. static const int dualScale = std::numeric_limits::is_integer ? 4 : 1; typedef typename Graph::template NodeMap MatchingMap; private: } /// \name Execution control /// \name Execution Control /// The simplest way to execute the algorithm is to use the /// \c run() member function. /// \ref run() member function. ///@{ /// \brief Initialize the algorithm /// /// Initialize the algorithm /// This function initializes the algorithm. void init() { createStructures(); } /// \brief Starts the algorithm /// /// Starts the algorithm /// \brief Start the algorithm /// /// This function starts the algorithm. /// /// \pre \ref init() must be called before using this function. void start() { enum OpType { } /// \brief Runs %MaxWeightedMatching algorithm. /// /// This method runs the %MaxWeightedMatching algorithm. /// \brief Run the algorithm. /// /// This method runs the \c %MaxWeightedMatching algorithm. /// /// \note mwm.run() is just a shortcut of the following code. /// @} /// \name Primal solution /// Functions to get the primal solution, ie. the matching. /// \name Primal Solution /// Functions to get the primal solution, i.e. the maximum weighted /// matching.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the weight of the matching. /// /// Returns the weight of the matching. /// \brief Return the weight of the matching. /// /// This function returns the weight of the found matching. /// /// \pre Either run() or start() must be called before using this function. Value matchingValue() const { Value sum = 0; } /// \brief Returns the cardinality of the matching. /// /// Returns the cardinality of the matching. /// \brief Return the size (cardinality) of the matching. /// /// This function returns the size (cardinality) of the found matching. /// /// \pre Either run() or start() must be called before using this function. int matchingSize() const { int num = 0; } /// \brief Returns true when the edge is in the matching. /// /// Returns true when the edge is in the matching. /// \brief Return \c true if the given edge is in the matching. /// /// This function returns \c true if the given edge is in the found /// matching. /// /// \pre Either run() or start() must be called before using this function. bool matching(const Edge& edge) const { return edge == (*_matching)[_graph.u(edge)]; } /// \brief Returns the incident matching arc. /// /// Returns the incident matching arc from given node. If the /// node is not matched then it gives back \c INVALID. /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the /// given node in the found matching or \c INVALID if the node is /// not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Arc matching(const Node& node) const { return (*_matching)[node]; } /// \brief Returns the mate of the node. /// /// Returns the adjancent node in a mathcing arc. If the node is /// not matched then it gives back \c INVALID. /// \brief Return the mate of the given node. /// /// This function returns the mate of the given node in the found /// matching or \c INVALID if the node is not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Node mate(const Node& node) const { return (*_matching)[node] != INVALID ? /// @} /// \name Dual solution /// Functions to get the dual solution. /// \name Dual Solution /// Functions to get the dual solution.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the value of the dual solution. /// /// Returns the value of the dual solution. It should be equal to /// the primal value scaled by \ref dualScale "dual scale". /// \brief Return the value of the dual solution. /// /// This function returns the value of the dual solution. /// It should be equal to the primal value scaled by \ref dualScale /// "dual scale". /// /// \pre Either run() or start() must be called before using this function. Value dualValue() const { Value sum = 0; } /// \brief Returns the value of the node. /// /// Returns the the value of the node. /// \brief Return the dual value (potential) of the given node. /// /// This function returns the dual value (potential) of the given node. /// /// \pre Either run() or start() must be called before using this function. Value nodeValue(const Node& n) const { return (*_node_potential)[n]; } /// \brief Returns the number of the blossoms in the basis. /// /// Returns the number of the blossoms in the basis. /// \brief Return the number of the blossoms in the basis. /// /// This function returns the number of the blossoms in the basis. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomNum() const { } /// \brief Returns the number of the nodes in the blossom. /// /// Returns the number of the nodes in the blossom. /// \brief Return the number of the nodes in the given blossom. /// /// This function returns the number of the nodes in the given blossom. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomSize(int k) const { return _blossom_potential[k].end - _blossom_potential[k].begin; } /// \brief Returns the value of the blossom. /// /// Returns the the value of the blossom. /// \see BlossomIt /// \brief Return the dual value (ptential) of the given blossom. /// /// This function returns the dual value (ptential) of the given blossom. /// /// \pre Either run() or start() must be called before using this function. Value blossomValue(int k) const { return _blossom_potential[k].value; } /// \brief Iterator for obtaining the nodes of the blossom. /// /// Iterator for obtaining the nodes of the blossom. This class /// provides a common lemon style iterator for listing a /// subset of the nodes. /// \brief Iterator for obtaining the nodes of a blossom. /// /// This class provides an iterator for obtaining the nodes of the /// given blossom. It lists a subset of the nodes. /// Before using this iterator, you must allocate a /// MaxWeightedMatching class and execute it. class BlossomIt { public: /// \brief Constructor. /// /// Constructor to get the nodes of the variable. /// Constructor to get the nodes of the given variable. /// /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or /// \ref MaxWeightedMatching::start() "algorithm.start()" must be /// called before initializing this iterator. BlossomIt(const MaxWeightedMatching& algorithm, int variable) : _algorithm(&algorithm) } /// \brief Conversion to node. /// \brief Conversion to \c Node. /// /// Conversion to node. /// Conversion to \c Node. operator Node() const { return _algorithm->_blossom_node_list[_index]; /// \f$O(nm\log n)\f$ time complexity. /// /// The maximum weighted matching problem is to find undirected /// edges in the graph with maximum overall weight and no two of /// them shares their ends and covers all nodes. The problem can be /// formulated with the following linear program. /// The maximum weighted perfect matching problem is to find a subset of /// the edges in an undirected graph with maximum overall weight for which /// each node has exactly one incident edge. /// It can be formulated with the following linear program. /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f] /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} /// optimality. The solution of the dual problem can be used to check /// the result of the algorithm. The dual linear problem is the /// following. /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge w_{uv} \quad \forall uv\in E\f] */ \frac{\vert B \vert - 1}{2}z_B\f] */ /// /// The algorithm can be executed with \c run() or the \c init() and /// then the \c start() member functions. After it the matching can /// be asked with \c matching() or mate() functions. The dual /// solution can be get with \c nodeValue(), \c blossomNum() and \c /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt /// "BlossomIt" nested class which is able to iterate on the nodes /// of a blossom. If the value type is integral then the dual /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". /// The algorithm can be executed with the run() function. /// After it the matching (the primal solution) and the dual solution /// can be obtained using the query functions and the /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, /// which is able to iterate on the nodes of a blossom. /// If the value type is integer, then the dual solution is multiplied /// by \ref MaxWeightedMatching::dualScale "4". /// /// \tparam GR The graph type the algorithm runs on. /// \tparam WM The type edge weight map. The default type is /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template #else template > #endif class MaxWeightedPerfectMatching { public: /// The graph type of the algorithm typedef GR Graph; /// The type of the edge weight map typedef WM WeightMap; /// The value type of the edge weights typedef typename WeightMap::Value Value; } /// \name Execution control /// \name Execution Control /// The simplest way to execute the algorithm is to use the /// \c run() member function. /// \ref run() member function. ///@{ /// \brief Initialize the algorithm /// /// Initialize the algorithm /// This function initializes the algorithm. void init() { createStructures(); } /// \brief Starts the algorithm /// /// Starts the algorithm /// \brief Start the algorithm /// /// This function starts the algorithm. /// /// \pre \ref init() must be called before using this function. bool start() { enum OpType { } /// \brief Runs %MaxWeightedPerfectMatching algorithm. /// /// This method runs the %MaxWeightedPerfectMatching algorithm. /// /// \note mwm.run() is just a shortcut of the following code. /// \brief Run the algorithm. /// /// This method runs the \c %MaxWeightedPerfectMatching algorithm. /// /// \note mwpm.run() is just a shortcut of the following code. /// \code ///   mwm.init(); ///   mwm.start(); ///   mwpm.init(); ///   mwpm.start(); /// \endcode bool run() { /// @} /// \name Primal solution /// Functions to get the primal solution, ie. the matching. /// \name Primal Solution /// Functions to get the primal solution, i.e. the maximum weighted /// perfect matching.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the matching value. /// /// Returns the matching value. /// \brief Return the weight of the matching. /// /// This function returns the weight of the found matching. /// /// \pre Either run() or start() must be called before using this function. Value matchingValue() const { Value sum = 0; } /// \brief Returns true when the edge is in the matching. /// /// Returns true when the edge is in the matching. /// \brief Return \c true if the given edge is in the matching. /// /// This function returns \c true if the given edge is in the found /// matching. /// /// \pre Either run() or start() must be called before using this function. bool matching(const Edge& edge) const { return static_cast((*_matching)[_graph.u(edge)]) == edge; } /// \brief Returns the incident matching edge. /// /// Returns the incident matching arc from given edge. /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the /// given node in the found matching or \c INVALID if the node is /// not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Arc matching(const Node& node) const { return (*_matching)[node]; } /// \brief Returns the mate of the node. /// /// Returns the adjancent node in a mathcing arc. /// \brief Return the mate of the given node. /// /// This function returns the mate of the given node in the found /// matching or \c INVALID if the node is not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Node mate(const Node& node) const { return _graph.target((*_matching)[node]); /// @} /// \name Dual solution /// Functions to get the dual solution. /// \name Dual Solution /// Functions to get the dual solution.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the value of the dual solution. /// /// Returns the value of the dual solution. It should be equal to /// the primal value scaled by \ref dualScale "dual scale". /// \brief Return the value of the dual solution. /// /// This function returns the value of the dual solution. /// It should be equal to the primal value scaled by \ref dualScale /// "dual scale". /// /// \pre Either run() or start() must be called before using this function. Value dualValue() const { Value sum = 0; } /// \brief Returns the value of the node. /// /// Returns the the value of the node. /// \brief Return the dual value (potential) of the given node. /// /// This function returns the dual value (potential) of the given node. /// /// \pre Either run() or start() must be called before using this function. Value nodeValue(const Node& n) const { return (*_node_potential)[n]; } /// \brief Returns the number of the blossoms in the basis. /// /// Returns the number of the blossoms in the basis. /// \brief Return the number of the blossoms in the basis. /// /// This function returns the number of the blossoms in the basis. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomNum() const { } /// \brief Returns the number of the nodes in the blossom. /// /// Returns the number of the nodes in the blossom. /// \brief Return the number of the nodes in the given blossom. /// /// This function returns the number of the nodes in the given blossom. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomSize(int k) const { return _blossom_potential[k].end - _blossom_potential[k].begin; } /// \brief Returns the value of the blossom. /// /// Returns the the value of the blossom. /// \see BlossomIt /// \brief Return the dual value (ptential) of the given blossom. /// /// This function returns the dual value (ptential) of the given blossom. /// /// \pre Either run() or start() must be called before using this function. Value blossomValue(int k) const { return _blossom_potential[k].value; } /// \brief Iterator for obtaining the nodes of the blossom. /// /// Iterator for obtaining the nodes of the blossom. This class /// provides a common lemon style iterator for listing a /// subset of the nodes. /// \brief Iterator for obtaining the nodes of a blossom. /// /// This class provides an iterator for obtaining the nodes of the /// given blossom. It lists a subset of the nodes. /// Before using this iterator, you must allocate a /// MaxWeightedPerfectMatching class and execute it. class BlossomIt { public: /// \brief Constructor. /// /// Constructor to get the nodes of the variable. /// Constructor to get the nodes of the given variable. /// /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" /// must be called before initializing this iterator. BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) : _algorithm(&algorithm) } /// \brief Conversion to node. /// \brief Conversion to \c Node. /// /// Conversion to node. /// Conversion to \c Node. operator Node() const { return _algorithm->_blossom_node_list[_index]; /// \brief Validity checking /// /// Checks whether the iterator is invalid. /// This function checks whether the iterator is invalid. bool operator==(Invalid) const { return _index == _last; } /// \brief Validity checking /// /// Checks whether the iterator is valid. /// This function checks whether the iterator is valid. bool operator!=(Invalid) const { return _index != _last; } }; } //END OF NAMESPACE LEMON
• ## test/max_matching_test.cc

 r463 #include #include #include #include #include #include #include #include #include #include #include "test_tools.h" }; void checkMaxMatchingCompile() { typedef concepts::Graph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; typedef Graph::EdgeMap MatMap; Graph g; Node n; Edge e; MatMap mat(g); MaxMatching mat_test(g); const MaxMatching& const_mat_test = mat_test; mat_test.init(); mat_test.greedyInit(); mat_test.matchingInit(mat); mat_test.startSparse(); mat_test.startDense(); mat_test.run(); const_mat_test.matchingSize(); const_mat_test.matching(e); const_mat_test.matching(n); const_mat_test.mate(n); MaxMatching::Status stat = const_mat_test.decomposition(n); const_mat_test.barrier(n); ignore_unused_variable_warning(stat); } void checkMaxWeightedMatchingCompile() { typedef concepts::Graph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; typedef Graph::EdgeMap WeightMap; Graph g; Node n; Edge e; WeightMap w(g); MaxWeightedMatching mat_test(g, w); const MaxWeightedMatching& const_mat_test = mat_test; mat_test.init(); mat_test.start(); mat_test.run(); const_mat_test.matchingValue(); const_mat_test.matchingSize(); const_mat_test.matching(e); const_mat_test.matching(n); const_mat_test.mate(n); int k = 0; const_mat_test.dualValue(); const_mat_test.nodeValue(n); const_mat_test.blossomNum(); const_mat_test.blossomSize(k); const_mat_test.blossomValue(k); } void checkMaxWeightedPerfectMatchingCompile() { typedef concepts::Graph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; typedef Graph::EdgeMap WeightMap; Graph g; Node n; Edge e; WeightMap w(g); MaxWeightedPerfectMatching mat_test(g, w); const MaxWeightedPerfectMatching& const_mat_test = mat_test; mat_test.init(); mat_test.start(); mat_test.run(); const_mat_test.matchingValue(); const_mat_test.matching(e); const_mat_test.matching(n); const_mat_test.mate(n); int k = 0; const_mat_test.dualValue(); const_mat_test.nodeValue(n); const_mat_test.blossomNum(); const_mat_test.blossomSize(k); const_mat_test.blossomValue(k); } void checkMatching(const SmartGraph& graph, const MaxMatching& mm) {
Note: See TracChangeset for help on using the changeset viewer.