LEMON/LEMON-main Changeset - r590:b61354458b59

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r590:b61354458b59

« 589:630c48

593:7ac52d »

r590:b61354458b59

Wed, 15 Apr 2009 12:01:14

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Imporvements for the matching algorithms (#264)

0 3 0

default

3 files changed with 393 insertions and 188 deletions:

doc/groups.dox

lemon/max_matching.h

285

185

test/max_matching_test.cc

105

↑ Collapse diff ↑

doc/groups.dox

Show inline comments

@@ -432,15 +432,16 @@
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\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
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or

lemon/max_matching.h

Show inline comments

@@ -34,48 +34,57 @@
 		///\brief Maximum matching algorithms in general graphs.
 		namespace lemon {
 		  /// \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 <typename GR>
 		  class MaxMatching {
 		  public:
 		    /// The graph type of the algorithm
 		    typedef GR Graph;
 		    typedef typename Graph::template NodeMap<typename Graph::Arc>
 		    MatchingMap;
-		    ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
+		    ///\brief Status constants for Gallai-Edmonds decomposition.
 		    ///
 		    ///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.
+		    ///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.
 		    };
 		    typedef typename Graph::template NodeMap<Status> StatusMap;
 		  private:
@@ -335,14 +344,12 @@
+		        }
+		      }
 		      (*_blossom_rep)[_blossom_set->find(nca)] = nca;
+		    }
 		    void extendOnArc(const Arc& a) {
 		      Node base = _graph.source(a);
 		      Node odd = _graph.target(a);
 		      (*_ear)[odd] = _graph.oppositeArc(a);
 		      Node even = _graph.target((*_matching)[odd]);
@@ -405,39 +412,36 @@
 		        _tree_set_index(0), _tree_set(0) {}
 		    ~MaxMatching() {
 		      destroyStructures();
+		    }
-		    /// \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.
+		    /// \brief Set the initial matching to the empty matching.
 		    ///
 		    /// Sets the actual matching to the empty matching.
 		    ///
 		    /// This function sets the initial matching to the empty matching.
 		    void init() {
 		      createStructures();
 		      for(NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_matching)[n] = INVALID;
 		        (*_status)[n] = UNMATCHED;
+		      }
+		    }
-		    ///\brief Finds an initial matching in a greedy way
+		    /// \brief Find an initial matching in a greedy way.
 		    ///
-		    ///It finds an initial matching in a greedy way.
+		    /// This function finds an initial matching in a greedy way.
 		    void greedyInit() {
 		      createStructures();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_matching)[n] = INVALID;
 		        (*_status)[n] = UNMATCHED;
+		      }
@@ -455,17 +459,17 @@
+		          }
+		        }
+		      }
+		    }
-		    /// \brief Initialize the matching from a map containing.
 		    /// \brief Initialize the matching from a map.
 		    ///
 		    /// 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.
+		    /// 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 <typename MatchingMap>
 		    bool matchingInit(const MatchingMap& matching) {
 		      createStructures();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
@@ -486,121 +490,131 @@
 		          (*_status)[v] = MATCHED;
+		        }
+		      }
 		      return true;
+		    }
-		    /// \brief Starts Edmonds' algorithm
+		    /// \brief Start Edmonds' algorithm
 		    ///
-		    /// If runs the original 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) {
 		        if ((*_status)[n] == UNMATCHED) {
 		          (*_blossom_rep)[_blossom_set->insert(n)] = n;
 		          _tree_set->insert(n);
 		          (*_status)[n] = EVEN;
 		          processSparse(n);
+		        }
+		      }
+		    }
-		    /// \brief Starts Edmonds' algorithm.
+		    /// \brief Start Edmonds' algorithm with a heuristic improvement
 		    /// for dense graphs
 		    ///
-		    /// It runs Edmonds' algorithm with a heuristic of postponing
+		    /// 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) {
 		        if ((*_status)[n] == UNMATCHED) {
 		          (*_blossom_rep)[_blossom_set->insert(n)] = n;
 		          _tree_set->insert(n);
 		          (*_status)[n] = EVEN;
 		          processDense(n);
+		        }
+		      }
+		    }
-		    /// \brief Runs Edmonds' algorithm
+		    /// \brief Run Edmonds' algorithm
 		    ///
 		    /// Runs Edmonds' algorithm for sparse graphs (<tt>m<2*n</tt>)
 		    /// or Edmonds' algorithm with a heuristic of
-		    /// postponing shrinks for dense graphs.
+		    /// 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();
 		      } else {
 		        init();
 		        startDense();
+		      }
+		    }
 		    /// @}
 		    /// \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.
+		    /// \brief Return the size (cardinality) of the matching.
 		    ///
 		    ///Returns the size of the current matching. After \ref
 		    ///run() it returns the size of the maximum matching in the graph.
 		    /// 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) {
 		          ++size;
+		        }
+		      }
 		      return size / 2;
+		    }
-		    /// \brief Returns true when the edge is in the matching.
+		    /// \brief Return \c true if the given edge is in the matching.
 		    ///
-		    /// Returns true when the 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.
+		    /// \brief Return the matching arc (or 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.
 		    /// 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.
+		    /// \brief Return the mate of the given node.
 		    ///
 		    ///Returns the mate of a \c node in the actual matching or
 		    ///INVALID if the \c node is not covered by the actual matching.
 		    /// 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, 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.
+		    /// \brief Return \c true if the given node is in the barrier.
 		    ///
-		    /// Returns true when the 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;
+		    }
 		    /// @}
@@ -612,16 +626,16 @@
 		  ///
 		  /// 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 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}
 		      \quad \forall B\in\mathcal{O}\f] */
 		  /// \f[x_e \ge 0\quad \forall e\in E\f]
 		  /// \f[\max \sum_{e\in E}x_ew_e\f]
 		  /// where \f$\delta(X)\f$ is the set of edges incident to a node in
@@ -629,49 +643,57 @@
 		  /// \f$X\f$ and \f$\mathcal{O}\f$ is the set of odd cardinality
 		  /// subsets of the nodes.
 		  ///
 		  /// The algorithm calculates an optimal matching and a proof of the
 		  /// 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] */
 		  /// \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 \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<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename WM>
 		#else
 		  template <typename GR,
 		            typename WM = typename GR::template EdgeMap<int> >
 		#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<typename Graph::Arc>
 		    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<Value>::is_integer ? 4 : 1;
 		    typedef typename Graph::template NodeMap<typename Graph::Arc>
 		    MatchingMap;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    typedef typename Graph::template NodeMap<Value> NodePotential;
 		    typedef std::vector<Node> BlossomNodeList;
@@ -1628,21 +1650,21 @@
 		        _delta_sum() {}
 		    ~MaxWeightedMatching() {
 		      destroyStructures();
+		    }
-		    /// \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();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
+		      }
@@ -1688,15 +1710,17 @@
 		          _delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot -
 		                            dualScale * _weight[e]) / 2);
+		        }
+		      }
+		    }
-		    /// \brief Starts the algorithm
+		    /// \brief Start the algorithm
 		    ///
-		    /// Starts the algorithm
+		    /// This function starts the algorithm.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    void start() {
 		      enum OpType {
 		        D1, D2, D3, D4
 		      };
 		      int unmatched = _node_num;
@@ -1773,15 +1797,15 @@
 		          break;
+		        }
+		      }
 		      extractMatching();
+		    }
-		    /// \brief Runs %MaxWeightedMatching algorithm.
+		    /// \brief Run the algorithm.
 		    ///
 		    /// This method runs the %MaxWeightedMatching algorithm.
+		    /// This method runs the \c %MaxWeightedMatching algorithm.
 		    ///
 		    /// \note mwm.run() is just a shortcut of the following code.
 		    /// \code
 		    ///   mwm.init();
 		    ///   mwm.start();
 		    /// \endcode
@@ -1789,141 +1813,173 @@
 		      init();
 		      start();
+		    }
 		    /// @}
 		    /// \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.
+		    /// \brief Return the weight of the matching.
 		    ///
-		    /// Returns 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;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_matching)[n] != INVALID) {
 		          sum += _weight[(*_matching)[n]];
+		        }
+		      }
 		      return sum /= 2;
+		    }
-		    /// \brief Returns the cardinality of the matching.
+		    /// \brief Return the size (cardinality) of the matching.
 		    ///
-		    /// Returns the 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;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_matching)[n] != INVALID) {
 		          ++num;
+		        }
+		      }
 		      return num /= 2;
+		    }
-		    /// \brief Returns true when the edge is in the matching.
+		    /// \brief Return \c true if the given edge is in the matching.
 		    ///
-		    /// Returns true when the 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.
+		    /// \brief Return the matching arc (or edge) incident to the given node.
 		    ///
 		    /// Returns the incident matching arc from given node. If the
 		    /// node is not matched then it gives back \c INVALID.
 		    /// 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.
+		    /// \brief Return the mate of the given node.
 		    ///
 		    /// Returns the adjancent node in a mathcing arc. If the node is
 		    /// not matched then it gives back \c INVALID.
 		    /// 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 ?
 		        _graph.target((*_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.
+		    /// \brief Return 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".
 		    /// 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;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        sum += nodeValue(n);
+		      }
 		      for (int i = 0; i < blossomNum(); ++i) {
 		        sum += blossomValue(i) * (blossomSize(i) / 2);
+		      }
 		      return sum;
+		    }
-		    /// \brief Returns the value of the node.
+		    /// \brief Return the dual value (potential) of the given node.
 		    ///
-		    /// Returns the the value of the 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.
+		    /// \brief Return the number of the blossoms in the basis.
 		    ///
-		    /// Returns 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 {
 		      return _blossom_potential.size();
+		    }
 		    /// \brief Returns the number of the nodes in the blossom.
 		    /// \brief Return the number of the nodes in the given blossom.
 		    ///
-		    /// Returns the number of the nodes in the 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.
+		    /// \brief Return the dual value (ptential) of the given blossom.
 		    ///
 		    /// Returns the the value of the blossom.
 		    /// \see BlossomIt
 		    /// 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.
+		    /// \brief Iterator for obtaining the nodes of a blossom.
 		    ///
 		    /// Iterator for obtaining the nodes of the blossom. This class
 		    /// provides a common lemon style iterator for listing a
-		    /// subset of the nodes.
+		    /// 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)
+		      {
 		        _index = _algorithm->_blossom_potential[variable].begin;
 		        _last = _algorithm->_blossom_potential[variable].end;
+		      }
-		      /// \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 Increment operator.
 		      ///
@@ -1959,16 +2015,16 @@
 		  ///
 		  /// 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 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}
 		      \quad \forall B\in\mathcal{O}\f] */
 		  /// \f[x_e \ge 0\quad \forall e\in E\f]
 		  /// \f[\max \sum_{e\in E}x_ew_e\f]
 		  /// where \f$\delta(X)\f$ is the set of edges incident to a node in
@@ -1976,33 +2032,44 @@
 		  /// \f$X\f$ and \f$\mathcal{O}\f$ is the set of odd cardinality
 		  /// subsets of the nodes.
 		  ///
 		  /// The algorithm calculates an optimal matching and a proof of the
 		  /// 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] */
 		  /// \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 \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<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename WM>
 		#else
 		  template <typename GR,
 		            typename WM = typename GR::template EdgeMap<int> >
 		#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;
 		    /// \brief Scaling factor for dual solution
 		    ///
 		    /// Scaling factor for dual solution, it is equal to 4 or 1
 		    /// according to the value type.
@@ -2815,21 +2882,21 @@
 		        _delta_sum() {}
 		    ~MaxWeightedPerfectMatching() {
 		      destroyStructures();
+		    }
-		    /// \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();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
+		      }
@@ -2871,15 +2938,17 @@
 		          _delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot -
 		                            dualScale * _weight[e]) / 2);
+		        }
+		      }
+		    }
-		    /// \brief Starts the algorithm
+		    /// \brief Start the algorithm
 		    ///
-		    /// Starts the algorithm
+		    /// This function starts the algorithm.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    bool start() {
 		      enum OpType {
 		        D2, D3, D4
 		      };
 		      int unmatched = _node_num;
@@ -2937,141 +3006,173 @@
+		        }
+		      }
 		      extractMatching();
 		      return true;
+		    }
-		    /// \brief Runs %MaxWeightedPerfectMatching algorithm.
+		    /// \brief Run the algorithm.
 		    ///
 		    /// This method runs the %MaxWeightedPerfectMatching algorithm.
+		    /// This method runs the \c %MaxWeightedPerfectMatching algorithm.
 		    ///
-		    /// \note mwm.run() is just a shortcut of the following code.
+		    /// \note mwpm.run() is just a shortcut of the following code.
 		    /// \code
 		    ///   mwm.init();
 		    ///   mwm.start();
 		    ///   mwpm.init();
 		    ///   mwpm.start();
 		    /// \endcode
 		    bool run() {
 		      init();
 		      return start();
+		    }
 		    /// @}
 		    /// \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.
+		    /// \brief Return the weight of the matching.
 		    ///
-		    /// Returns the matching value.
+		    /// 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;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_matching)[n] != INVALID) {
 		          sum += _weight[(*_matching)[n]];
+		        }
+		      }
 		      return sum /= 2;
+		    }
-		    /// \brief Returns true when the edge is in the matching.
+		    /// \brief Return \c true if the given edge is in the matching.
 		    ///
-		    /// Returns true when the 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 Returns the incident matching edge.
+		    /// \brief Return the matching arc (or edge) incident to the given node.
 		    ///
-		    /// Returns the incident matching arc from given edge.
+		    /// 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.
+		    /// \brief Return the mate of the given node.
 		    ///
-		    /// Returns the adjancent node in a mathcing arc.
+		    /// 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.
+		    /// \brief Return 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".
 		    /// 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;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        sum += nodeValue(n);
+		      }
 		      for (int i = 0; i < blossomNum(); ++i) {
 		        sum += blossomValue(i) * (blossomSize(i) / 2);
+		      }
 		      return sum;
+		    }
-		    /// \brief Returns the value of the node.
+		    /// \brief Return the dual value (potential) of the given node.
 		    ///
-		    /// Returns the the value of the 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.
+		    /// \brief Return the number of the blossoms in the basis.
 		    ///
-		    /// Returns 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 {
 		      return _blossom_potential.size();
+		    }
 		    /// \brief Returns the number of the nodes in the blossom.
 		    /// \brief Return the number of the nodes in the given blossom.
 		    ///
-		    /// Returns the number of the nodes in the 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.
+		    /// \brief Return the dual value (ptential) of the given blossom.
 		    ///
 		    /// Returns the the value of the blossom.
 		    /// \see BlossomIt
 		    /// 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.
+		    /// \brief Iterator for obtaining the nodes of a blossom.
 		    ///
 		    /// Iterator for obtaining the nodes of the blossom. This class
 		    /// provides a common lemon style iterator for listing a
-		    /// subset of the nodes.
+		    /// 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)
+		      {
 		        _index = _algorithm->_blossom_potential[variable].begin;
 		        _last = _algorithm->_blossom_potential[variable].end;
+		      }
-		      /// \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 Increment operator.
 		      ///
@@ -3080,28 +3181,27 @@
 		        ++_index;
 		        return *this;
+		      }
 		      /// \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; }
 		    private:
 		      const MaxWeightedPerfectMatching* _algorithm;
 		      int _last;
 		      int _index;
 		    };
 		    /// @}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif //LEMON_MAX_MATCHING_H

test/max_matching_test.cc

Show inline comments

@@ -17,18 +17,20 @@
 		 */
 		#include <iostream>
 		#include <sstream>
 		#include <vector>
 		#include <queue>
 		#include <lemon/math.h>
 		#include <cstdlib>
 		#include <lemon/max_matching.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/math.h>
 		#include "test_tools.h"
 		using namespace std;
 		using namespace lemon;
@@ -107,12 +109,114 @@
 		  "4 7  3      846\n"
 		  "7 2  4      981\n"
 		  "7 6  5      250\n"
 		  "5 2  6      539\n",
 		};
 		void checkMaxMatchingCompile()
+		{
 		  typedef concepts::Graph Graph;
 		  typedef Graph::Node Node;
 		  typedef Graph::Edge Edge;
 		  typedef Graph::EdgeMap<bool> MatMap;
 		  Graph g;
 		  Node n;
 		  Edge e;
 		  MatMap mat(g);
 		  MaxMatching<Graph> mat_test(g);
 		  const MaxMatching<Graph>&
 		    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<Graph>::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<int> WeightMap;
 		  Graph g;
 		  Node n;
 		  Edge e;
 		  WeightMap w(g);
 		  MaxWeightedMatching<Graph> mat_test(g, w);
 		  const MaxWeightedMatching<Graph>&
 		    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<int> WeightMap;
 		  Graph g;
 		  Node n;
 		  Edge e;
 		  WeightMap w(g);
 		  MaxWeightedPerfectMatching<Graph> mat_test(g, w);
 		  const MaxWeightedPerfectMatching<Graph>&
 		    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<SmartGraph>& mm) {
 		  int num = 0;
 		  IntNodeMap comp_index(graph);
 		  UnionFind<IntNodeMap> comp(comp_index);

0 comments (0 inline)

RhodeCode

Login to your account