lemon-1.1: comparison lemon/matching.h

equal deleted inserted replaced

-:979645abf089
+:dcc78936a7ef
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2009
+* Copyright (C) 2003-2011
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 ///
 /// \brief Maximum cardinality matching in general graphs
 ///
 /// This class implements Edmonds' alternating forest matching algorithm
 /// for finding a maximum cardinality matching in a general undirected 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
 /// \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
 typedef typename Graph::template NodeMap<typename Graph::Arc>
 MatchingMap;
 ///\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,       ///< = 1. (\c D is an alias for \c EVEN.)
 D = 1,
 MATCHED = 0,    ///< = 0. (\c C is an alias for \c MATCHED.)
 processSparse(n);
 }
 }
 }
 /// \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.
 ///
 }
 /// \brief Run Edmonds' algorithm
 ///
 /// This function runs Edmonds' algorithm. An additional heuristic of
 /// postponing shrinks is used for relatively dense graphs
 /// (for which <tt>m>=2*n</tt> holds).
 void run() {
 if (countEdges(_graph) < 2 * countNodes(_graph)) {
 greedyInit();
 startSparse();
 /// @{
 /// \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;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 return size / 2;
 }
 /// \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 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];
 }
 return *_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 ?
 _graph.target((*_matching)[n]) : INVALID;
 }
 /// @}
 /// \name Dual Solution
 /// Functions to get the dual solution, i.e. the Gallai-Edmonds
 /// decomposition.
 /// @{
 /// \brief Return the status of the given node in the Edmonds-Gallai
 /// This class provides an efficient implementation of Edmond's
 /// maximum weighted matching algorithm. The implementation is based
 /// on extensive use of priority queues and provides
 /// \f$O(nm\log n)\f$ time complexity.
 ///
 /// 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}
 \quad \forall B\in\mathcal{O}\f] */
 /// \f[y_u \ge 0 \quad \forall u \in V\f]
 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
 \frac{\vert B \vert - 1}{2}z_B\f] */
 ///
 /// 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 undirected graph type the algorithm runs on.
 /// \tparam WM The type edge weight map. The default type is
 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR, typename WM>
 #else
 template <typename GR,
 }
 for (int i = 0; i < _blossom_num; ++i) {
 (*_delta2_index)[i] = _delta2->PRE_HEAP;
 (*_delta4_index)[i] = _delta4->PRE_HEAP;
 }
 _delta1->clear();
 _delta2->clear();
 _delta3->clear();
 _delta4->clear();
 _blossom_set->clear();
 }
 /// @}
 /// \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.
 /// @{
 return num /= 2;
 }
 /// \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 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];
 return *_matching;
 }
 /// \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 ?
 /// @{
 /// \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;
 return _blossom_potential[k].value;
 }
 /// \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 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)
 {
 _index = _algorithm->_blossom_potential[variable].begin;
 /// This class provides an efficient implementation of Edmond's
 /// maximum weighted perfect matching algorithm. The implementation
 /// is based on extensive use of priority queues and provides
 /// \f$O(nm\log n)\f$ time complexity.
 ///
 /// 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}
 \quad \forall B\in\mathcal{O}\f] */
 w_{uv} \quad \forall uv\in E\f] */
 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
 \frac{\vert B \vert - 1}{2}z_B\f] */
 ///
 /// 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 undirected graph type the algorithm runs on.
 /// \tparam WM The type edge weight map. The default type is
 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR, typename WM>
 #else
 template <typename GR,
 }
 /// @}
 /// \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.
 /// @{
 return sum /= 2;
 }
 /// \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<const Edge&>((*_matching)[_graph.u(edge)]) == 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];
 return *_matching;
 }
 /// \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]);
 /// @{
 /// \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;
 return _blossom_potential[k].value;
 }
 /// \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 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)
 {
 _index = _algorithm->_blossom_potential[variable].begin;

branch	1.1
changeset 769	74e2dac774c8
parent 722	5b926cc36a4b