Changeset 2462:7a096a6bf53a in lemon-0.x

Timestamp:

08/11/07 18:34:41 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3300

Message:

Common interface for bipartite matchings
Some useful query function for push-relabel based matching

The naming should be rethink for these classes
for example: pr-ap prefix for push-relabel and augmenting path
algorithms

Files:

• lemon/Makefile.am (modified) (2 diffs)
• lemon/bipartite_matching.h (modified) (4 diffs)
• lemon/pr_bipartite_matching.h (moved) (moved from lemon/bp_matching.h) (17 diffs)
• test/bipartite_matching_test.cc (modified) (2 diffs)

lemon/Makefile.am

@@ -40 +40 @@
         lemon/bin_heap.h \
         lemon/bipartite_matching.h \
-        lemon/bp_matching.h \
         lemon/bpugraph_adaptor.h \
         lemon/bucket_heap.h \
@@ -104 +103 @@
         lemon/preflow.h \
         lemon/prim.h \
+        lemon/pr_bipartite_matching.h \
         lemon/radix_heap.h \
         lemon/radix_sort.h \

lemon/bipartite_matching.h

@@ -30 +30 @@
 ///\file
 ///\brief Maximum matching algorithms in bipartite graphs.
+///
+///\note The pr_bipartite_matching.h file also contains algorithms to
+///solve maximum cardinality bipartite matching problems.
 
 namespace lemon {
@@ -40 +43 @@
   /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time
   /// complexity.
+  ///
+  /// \note In several cases the push-relabel based algorithms have
+  /// better runtime performance than the augmenting path based ones. 
+  ///
+  /// \see PrBipartiteMatching
   template <typename BpUGraph>
   class MaxBipartiteMatching {
@@ -343 +351 @@
     ///@{
 
-    /// \brief Returns an minimum covering of the nodes.
+    /// \brief Set true all matching uedge in the map.
+    /// 
+    /// Set true all matching uedge in the map. It does not change the
+    /// value mapped to the other uedges.
+    /// \return The number of the matching edges.
+    template <typename MatchingMap>
+    int quickMatching(MatchingMap& mm) const {
+      for (ANodeIt it(*graph); it != INVALID; ++it) {
+        if (anode_matching[it] != INVALID) {
+          mm[anode_matching[it]] = true;
+        }
+      }
+      return matching_size;
+    }
+
+    /// \brief Set true all matching uedge in the map and the others to false.
+    /// 
+    /// Set true all matching uedge in the map and the others to false.
+    /// \return The number of the matching edges.
+    template <typename MatchingMap>
+    int matching(MatchingMap& mm) const {
+      for (UEdgeIt it(*graph); it != INVALID; ++it) {
+        mm[it] = it == anode_matching[graph->aNode(it)];
+      }
+      return matching_size;
+    }
+
+
+    /// \brief Return true if the given uedge is in the matching.
+    /// 
+    /// It returns true if the given uedge is in the matching.
+    bool matchingEdge(const UEdge& edge) const {
+      return anode_matching[graph->aNode(edge)] == edge;
+    }
+
+    /// \brief Returns the matching edge from the node.
+    /// 
+    /// Returns the matching edge from the node. If there is not such
+    /// edge it gives back \c INVALID.
+    UEdge matchingEdge(const Node& node) const {
+      if (graph->aNode(node)) {
+        return anode_matching[node];
+      } else {
+        return bnode_matching[node];
+      }
+    }
+
+    /// \brief Gives back the number of the matching edges.
+    ///
+    /// Gives back the number of the matching edges.
+    int matchingSize() const {
+      return matching_size;
+    }
+
+    /// \brief Returns a minimum covering of the nodes.
     ///
     /// The minimum covering set problem is the dual solution of the
-    /// maximum bipartite matching. It provides an solution for this
+    /// maximum bipartite matching. It provides a solution for this
     /// problem what is proof of the optimality of the matching.
     /// \return The size of the cover set.
@@ -398 +460 @@
     }
 
-    /// \brief Set true all matching uedge in the map.
-    /// 
-    /// Set true all matching uedge in the map. It does not change the
-    /// value mapped to the other uedges.
-    /// \return The number of the matching edges.
-    template <typename MatchingMap>
-    int quickMatching(MatchingMap& mm) const {
-      for (ANodeIt it(*graph); it != INVALID; ++it) {
-        if (anode_matching[it] != INVALID) {
-          mm[anode_matching[it]] = true;
-        }
-      }
-      return matching_size;
-    }
-
-    /// \brief Set true all matching uedge in the map and the others to false.
-    /// 
-    /// Set true all matching uedge in the map and the others to false.
-    /// \return The number of the matching edges.
-    template <typename MatchingMap>
-    int matching(MatchingMap& mm) const {
-      for (UEdgeIt it(*graph); it != INVALID; ++it) {
-        mm[it] = it == anode_matching[graph->aNode(it)];
-      }
-      return matching_size;
-    }
-
-
-    /// \brief Return true if the given uedge is in the matching.
-    /// 
-    /// It returns true if the given uedge is in the matching.
-    bool matchingEdge(const UEdge& edge) const {
-      return anode_matching[graph->aNode(edge)] == edge;
-    }
-
-    /// \brief Returns the matching edge from the node.
-    /// 
-    /// Returns the matching edge from the node. If there is not such
-    /// edge it gives back \c INVALID.
-    UEdge matchingEdge(const Node& node) const {
-      if (graph->aNode(node)) {
-        return anode_matching[node];
-      } else {
-        return bnode_matching[node];
-      }
-    }
-
-    /// \brief Gives back the number of the matching edges.
-    ///
-    /// Gives back the number of the matching edges.
-    int matchingSize() const {
-      return matching_size;
+    /// \brief Gives back a barrier on the A-nodes
+    
+    /// The barrier is s subset of the nodes on the same side of the
+    /// graph, which size minus its neighbours is exactly the
+    /// unmatched nodes on the A-side.  
+    /// \retval barrier A WriteMap on the ANodes with bool value.
+    template <typename BarrierMap>
+    void aBarrier(BarrierMap& barrier) const {
+
+      typename Graph::template ANodeMap<bool> areached(*graph, false);
+      typename Graph::template BNodeMap<bool> breached(*graph, false);
+      
+      std::vector<Node> queue;
+      for (ANodeIt it(*graph); it != INVALID; ++it) {
+        if (anode_matching[it] == INVALID) {
+          queue.push_back(it);
+        }
+      }
+
+      while (!queue.empty()) {
+        std::vector<Node> newqueue;
+        for (int i = 0; i < int(queue.size()); ++i) {
+          Node anode = queue[i];
+          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
+            Node bnode = graph->bNode(jt);
+            if (breached[bnode]) continue;
+            breached[bnode] = true;
+            if (bnode_matching[bnode] != INVALID) {
+              Node newanode = graph->aNode(bnode_matching[bnode]);
+              if (!areached[newanode]) {
+                areached[newanode] = true;
+                newqueue.push_back(newanode);
+              }
+            }
+          }
+        }
+        queue.swap(newqueue);
+      }
+
+      for (ANodeIt it(*graph); it != INVALID; ++it) {
+        barrier[it] = areached[it] || anode_matching[it] == INVALID;
+      }
+    }
+
+    /// \brief Gives back a barrier on the B-nodes
+    
+    /// The barrier is s subset of the nodes on the same side of the
+    /// graph, which size minus its neighbours is exactly the
+    /// unmatched nodes on the B-side.  
+    /// \retval barrier A WriteMap on the BNodes with bool value.
+    template <typename BarrierMap>
+    void bBarrier(BarrierMap& barrier) const {
+
+      typename Graph::template ANodeMap<bool> areached(*graph, false);
+      typename Graph::template BNodeMap<bool> breached(*graph, false);
+      
+      std::vector<Node> queue;
+      for (ANodeIt it(*graph); it != INVALID; ++it) {
+        if (anode_matching[it] == INVALID) {
+          queue.push_back(it);
+        }
+      }
+
+      while (!queue.empty()) {
+        std::vector<Node> newqueue;
+        for (int i = 0; i < int(queue.size()); ++i) {
+          Node anode = queue[i];
+          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
+            Node bnode = graph->bNode(jt);
+            if (breached[bnode]) continue;
+            breached[bnode] = true;
+            if (bnode_matching[bnode] != INVALID) {
+              Node newanode = graph->aNode(bnode_matching[bnode]);
+              if (!areached[newanode]) {
+                areached[newanode] = true;
+                newqueue.push_back(newanode);
+              }
+            }
+          }
+        }
+        queue.swap(newqueue);
+      }
+
+      for (BNodeIt it(*graph); it != INVALID; ++it) {
+        barrier[it] = !breached[it];
+      }
     }
 

lemon/pr_bipartite_matching.h

@@ -17 +17 @@
  */
 
-#ifndef LEMON_BP_MATCHING
-#define LEMON_BP_MATCHING
+#ifndef LEMON_PR_BIPARTITE_MATCHING
+#define LEMON_PR_BIPARTITE_MATCHING
 
 #include <lemon/graph_utils.h>
@@ -24 +24 @@
 #include <iostream>
 #include <queue>
-#include <lemon/counter.h>
 #include <lemon/elevator.h>
 
@@ -31 +30 @@
 ///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
 ///
-///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h
-///\todo (Re)move the XYZ_TYPEDEFS macros
 namespace lemon {
 
-#define BIPARTITE_TYPEDEFS(Graph)               \
-  GRAPH_TYPEDEFS(Graph)                         \
-    typedef Graph::ANodeIt ANodeIt;     \
-    typedef Graph::BNodeIt BNodeIt;
-
-#define UNDIRBIPARTITE_TYPEDEFS(Graph)          \
-  UNDIRGRAPH_TYPEDEFS(Graph)                    \
-    typedef Graph::ANodeIt ANodeIt;     \
-    typedef Graph::BNodeIt BNodeIt;
-
-  template<class Graph,
-           class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >
-  class BpMatching {
+  ///Max cardinality matching algorithm based on push-relabel principle
+
+  ///\ingroup matching
+  ///Bipartite Max Cardinality Matching algorithm. This class uses the
+  ///push-relabel principle which in several cases has better runtime
+  ///performance than the augmenting path solutions.
+  ///
+  ///\author Alpar Juttner
+  template<class Graph>
+  class PrBipartiteMatching {
     typedef typename Graph::Node Node;
     typedef typename Graph::ANodeIt ANodeIt;
     typedef typename Graph::BNodeIt BNodeIt;
     typedef typename Graph::UEdge UEdge;
+    typedef typename Graph::UEdgeIt UEdgeIt;
     typedef typename Graph::IncEdgeIt IncEdgeIt;
     
     const Graph &_g;
     int _node_num;
-    MT &_matching;
+    int _matching_size;
+    int _empty_level;
+    
+    typename Graph::template ANodeMap<typename Graph::UEdge> _matching;
     Elevator<Graph,typename Graph::BNode> _levels;
     typename Graph::template BNodeMap<int> _cov;
 
   public:
-    BpMatching(const Graph &g, MT &matching) :
+
+    PrBipartiteMatching(const Graph &g) :
       _g(g),
       _node_num(countBNodes(g)),
-      _matching(matching),
+      _matching(g),
       _levels(g,_node_num),
       _cov(g,0)
@@ -70 +69 @@
     }
     
-  private:
-    void init() 
-    {
-//     for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;
+    /// \name Execution control 
+    /// The simplest way to execute the algorithm is to use one of the
+    /// member functions called \c run(). \n
+    /// If you need more control on the execution, first
+    /// you must call \ref init() and then one variant of the start()
+    /// member. 
+
+    /// @{
+
+    ///Initialize the data structures
+
+    ///This function constructs a prematching first, which is a
+    ///regular matching on the A-side of the graph, but on the B-side
+    ///each node could cover more matching edges. After that, the
+    ///B-nodes which multiple matched, will be pushed into the lowest
+    ///level of the Elevator. The remaning B-nodes will be pushed to
+    ///the consequent levels respect to a Bfs on following graph: the
+    ///nodes are the B-nodes of the original bipartite graph and two
+    ///nodes are adjacent if a node can pass over a matching edge to
+    ///an other node. The source of the Bfs are the lowest level
+    ///nodes. Last, the reached B-nodes without covered matching edge
+    ///becomes active.
+    void init() {
+      _matching_size=0;
+      _empty_level=_node_num;
       for(ANodeIt n(_g);n!=INVALID;++n)
         if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
-          ++_cov[_g.oppositeNode(n,_matching[n])];
+          ++_cov[_g.bNode(_matching[n])];
 
       std::queue<Node> q;
@@ -110 +130 @@
           _levels.activate(n);
     }
-  public:
-    int run() 
-    {
-      init();
-
-      Node act;
-      Node bact=INVALID;
-      Node last_activated=INVALID;
-//       while((act=last_activated!=INVALID?
-//           last_activated:_levels.highestActive())
-//          !=INVALID)
-      while((act=_levels.highestActive())!=INVALID) {
-        last_activated=INVALID;
-        int actlevel=_levels[act];
-        
-        UEdge bedge=INVALID;
-        int nlevel=_node_num;
-        {
-          int nnlevel;
-          for(IncEdgeIt tbedge(_g,act);
-              tbedge!=INVALID && nlevel>=actlevel;
-              ++tbedge)
-            if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
-               nlevel)
-              {
-                nlevel=nnlevel;
-                bedge=tbedge;
-              }
-        }
-        if(nlevel<_node_num) {
-          if(nlevel>=actlevel)
-            _levels.liftHighestActiveTo(nlevel+1);
-//          _levels.liftTo(act,nlevel+1);
-          bact=_g.bNode(_matching[_g.aNode(bedge)]);
-          if(--_cov[bact]<1) {
-            _levels.activate(bact);
-            last_activated=bact;
-          }
-          _matching[_g.aNode(bedge)]=bedge;
-          _cov[act]=1;
-          _levels.deactivate(act);
-        }
-        else {
-          if(_node_num>actlevel) 
-            _levels.liftHighestActiveTo(_node_num);
-//          _levels.liftTo(act,_node_num);
-          _levels.deactivate(act); 
-        }
-
-        if(_levels.onLevel(actlevel)==0)
-          _levels.liftToTop(actlevel);
-      }
-      
-      int ret=_node_num;
-      for(ANodeIt n(_g);n!=INVALID;++n)
-        if(_matching[n]==INVALID) ret--;
-        else if (_cov[_g.bNode(_matching[n])]>1) {
-          _cov[_g.bNode(_matching[n])]--;
-          ret--;
-          _matching[n]=INVALID;
-        }
-      return ret;
-    }
-    
-    ///\returns -1 if there is a perfect matching, or an empty level
-    ///if it doesn't exists
-    int runPerfect() 
-    {
-      init();
-
+
+    ///Start the main phase of the algorithm
+    
+    ///This algorithm calculates the maximum matching with the
+    ///push-relabel principle. This function should be called just
+    ///after the init() function which already set the initial
+    ///prematching, the level function on the B-nodes and the active,
+    ///ie. unmatched B-nodes.
+    ///
+    ///The algorithm always takes highest active B-node, and it try to
+    ///find a B-node which is eligible to pass over one of it's
+    ///matching edge. This condition holds when the B-node is one
+    ///level lower, and the opposite node of it's matching edge is
+    ///adjacent to the highest active node. In this case the current
+    ///node steals the matching edge and becomes inactive. If there is
+    ///not eligible node then the highest active node should be lift
+    ///to the next proper level.
+    ///
+    ///The nodes should not lift higher than the number of the
+    ///B-nodes, if a node reach this level it remains unmatched. If
+    ///during the execution one level becomes empty the nodes above it
+    ///can be deactivated and lift to the highest level.
+    void start() {
       Node act;
       Node bact=INVALID;
@@ -220 +193 @@
 
         if(_levels.onLevel(actlevel)==0)
-          return actlevel;
-      }
-      return -1;
-    }
- 
-    template<class GT>
-    void aBarrier(GT &bar,int empty_level=-1) 
+          _levels.liftToTop(actlevel);
+      }
+      
+      _matching_size = _node_num;
+      for(ANodeIt n(_g);n!=INVALID;++n)
+        if(_matching[n]==INVALID) _matching_size--;
+        else if (_cov[_g.bNode(_matching[n])]>1) {
+          _cov[_g.bNode(_matching[n])]--;
+          _matching_size--;
+          _matching[n]=INVALID;
+        }
+    }
+
+    ///Start the algorithm to find a perfect matching
+
+    ///This function is close to identical to the simple start()
+    ///member function but it calculates just perfect matching.
+    ///However, the perfect property is only checked on the B-side of
+    ///the graph
+    ///
+    ///The main difference between the two function is the handling of
+    ///the empty levels. The simple start() function let the nodes
+    ///above the empty levels unmatched while this variant if it find
+    ///an empty level immediately terminates and gives back false
+    ///return value.
+    bool startPerfect() {
+      Node act;
+      Node bact=INVALID;
+      Node last_activated=INVALID;
+      while((act=_levels.highestActive())!=INVALID) {
+        last_activated=INVALID;
+        int actlevel=_levels[act];
+        
+        UEdge bedge=INVALID;
+        int nlevel=_node_num;
+        {
+          int nnlevel;
+          for(IncEdgeIt tbedge(_g,act);
+              tbedge!=INVALID && nlevel>=actlevel;
+              ++tbedge)
+            if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
+               nlevel)
+              {
+                nlevel=nnlevel;
+                bedge=tbedge;
+              }
+        }
+        if(nlevel<_node_num) {
+          if(nlevel>=actlevel)
+            _levels.liftHighestActiveTo(nlevel+1);
+          bact=_g.bNode(_matching[_g.aNode(bedge)]);
+          if(--_cov[bact]<1) {
+            _levels.activate(bact);
+            last_activated=bact;
+          }
+          _matching[_g.aNode(bedge)]=bedge;
+          _cov[act]=1;
+          _levels.deactivate(act);
+        }
+        else {
+          if(_node_num>actlevel) 
+            _levels.liftHighestActiveTo(_node_num);
+          _levels.deactivate(act); 
+        }
+
+        if(_levels.onLevel(actlevel)==0)
+          _empty_level=actlevel;
+          return false;
+      }
+      return true;
+    }
+  
+    ///Runs the algorithm
+    
+    ///Just a shortcut for the next code:
+    ///\code
+    /// init();
+    /// start();
+    ///\endcode
+    void run() {
+      init();
+      start();
+    }
+    
+    ///Runs the algorithm to find a perfect matching
+    
+    ///Just a shortcut for the next code:
+    ///\code
+    /// init();
+    /// startPerfect();
+    ///\endcode
+    ///
+    ///\note If the two nodesets of the graph have different size then
+    ///this algorithm checks the perfect property on the B-side.
+    bool runPerfect() {
+      init();
+      return startPerfect();
+    }
+
+    ///Runs the algorithm to find a perfect matching
+    
+    ///Just a shortcut for the next code:
+    ///\code
+    /// init();
+    /// startPerfect();
+    ///\endcode
+    ///
+    ///\note It checks that the size of the two nodesets are equal.
+    bool checkedRunPerfect() {
+      if (countANodes(_g) != _node_num) return false;
+      init();
+      return startPerfect();
+    }
+
+    ///@}
+
+    /// \name Query Functions
+    /// The result of the %Matching algorithm can be obtained using these
+    /// functions.\n
+    /// Before the use of these functions,
+    /// either run() or start() must be called.
+    ///@{
+
+    /// \brief Set true all matching uedge in the map.
+    /// 
+    /// Set true all matching uedge in the map. It does not change the
+    /// value mapped to the other uedges.
+    /// \return The number of the matching edges.
+    template <typename MatchingMap>
+    int quickMatching(MatchingMap& mm) const {
+      for (ANodeIt n(_g);n!=INVALID;++n) {
+        if (_matching[n]!=INVALID) mm.set(_matching[n],true);
+      }
+      return _matching_size;
+    }
+
+    ///\brief Set true all matching uedge in the map and the others to false.
+
+    ///Set true all matching uedge in the map and the others to false.
+    ///\return The number of the matching edges.
+    template<class MatchingMap>
+    int matching(MatchingMap& mm) const {
+      for (UEdgeIt e(_g);e!=INVALID;++e) {
+        mm.set(e,e==_matching[_g.aNode(e)]);
+      }
+      return _matching_size;
+    }
+
+
+    ///Returns true if the given uedge is in the matching.
+
+    ///It returns true if the given uedge is in the matching.
+    ///
+    bool matchingEdge(const UEdge& e) const {
+      return _matching[_g.aNode(e)]==e;
+    }
+
+    ///Returns the matching edge from the node.
+
+    ///Returns the matching edge from the node. If there is not such
+    ///edge it gives back \c INVALID.  
+    ///\note If the parameter node is a B-node then the running time is
+    ///propotional to the degree of the node.
+    UEdge matchingEdge(const Node& n) const {
+      if (_g.aNode(n)) {
+        return _matching[n];
+      } else {
+        for (IncEdgeIt e(_g,n);e!=INVALID;++e)
+          if (e==_matching[_g.aNode(e)]) return e;
+        return INVALID;
+      }
+    }
+
+    ///Gives back the number of the matching edges.
+
+    ///Gives back the number of the matching edges.
+    int matchingSize() const {
+      return _matching_size;
+    }
+
+    ///Gives back a barrier on the A-nodes
+    
+    ///The barrier is s subset of the nodes on the same side of the
+    ///graph. If we tried to find a perfect matching and it failed
+    ///then the barrier size will be greater than its neighbours. If
+    ///the maximum matching searched then the barrier size minus its
+    ///neighbours will be exactly the unmatched nodes on the A-side.
+    ///\retval bar A WriteMap on the ANodes with bool value.
+    template<class BarrierMap>
+    void aBarrier(BarrierMap &bar) const 
     {
-      if(empty_level==-1)
-        for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
       for(ANodeIt n(_g);n!=INVALID;++n)
-        bar[n] = _matching[n]==INVALID ||
-          _levels[_g.bNode(_matching[n])]<empty_level;  
+        bar.set(n,_matching[n]==INVALID ||
+          _levels[_g.bNode(_matching[n])]<_empty_level);  
     }  
-    template<class GT>
-    void bBarrier(GT &bar, int empty_level=-1) 
+
+    ///Gives back a barrier on the B-nodes
+    
+    ///The barrier is s subset of the nodes on the same side of the
+    ///graph. If we tried to find a perfect matching and it failed
+    ///then the barrier size will be greater than its neighbours. If
+    ///the maximum matching searched then the barrier size minus its
+    ///neighbours will be exactly the unmatched nodes on the B-side.
+    ///\retval bar A WriteMap on the BNodes with bool value.
+    template<class BarrierMap>
+    void bBarrier(BarrierMap &bar) const
     {
-      if(empty_level==-1)
-        for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
-      for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level);  
-    }  
-  
+      for(BNodeIt n(_g);n!=INVALID;++n) bar.set(n,_levels[n]>=_empty_level);  
+    }
+
+    ///Returns a minimum covering of the nodes.
+
+    ///The minimum covering set problem is the dual solution of the
+    ///maximum bipartite matching. It provides a solution for this
+    ///problem what is proof of the optimality of the matching.
+    ///\param covering NodeMap of bool values, the nodes of the cover
+    ///set will set true while the others false.  
+    ///\return The size of the cover set.
+    ///\note This function can be called just after the algorithm have
+    ///already found a matching. 
+    template<class CoverMap>
+    int coverSet(CoverMap& covering) const {
+      int ret=0;
+      for(BNodeIt n(_g);n!=INVALID;++n) {
+        if (_levels[n]<_empty_level) { covering.set(n,true); ++ret; }
+        else covering.set(n,false);
+      }
+      for(ANodeIt n(_g);n!=INVALID;++n) {
+        if (_matching[n]!=INVALID &&
+            _levels[_g.bNode(_matching[n])]>=_empty_level) 
+          { covering.set(n,true); ++ret; }
+        else covering.set(n,false);
+      }
+      return ret;
+    }
+
+
+    /// @}
+    
   };
   
@@ -256 +446 @@
   ///on the push-relabel principle.
   template<class Graph>
-  int maxBpMatching(const Graph &g)
+  int prBipartiteMatching(const Graph &g)
   {
-    typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
-    return maxBpMatching(g,matching);
+    PrBipartiteMatching<Graph> bpm(g);
+    return bpm.matchingSize();
   }
 
@@ -268 +458 @@
   ///in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
-  /// \ref INVALID if it is uncovered.
+  ///\retval matching A write UEdgeMap of value type \c bool.
+  /// The found edges will be returned in this map.
   ///\return The cardinality of the maximum matching.
   ///
@@ -278 +465 @@
   ///on the push-relabel principle.
   template<class Graph,class MT>
-  int maxBpMatching(const Graph &g,MT &matching) 
+  int prBipartiteMatching(const Graph &g,MT &matching) 
   {
-    return BpMatching<Graph,MT>(g,matching).run();
+    PrBipartiteMatching<Graph> bpm(g);
+    bpm.run();
+    bpm.matching(matching);
+    return bpm.matchingSize();
   }
 
@@ -289 +479 @@
   ///in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
-  /// \ref INVALID if it is uncovered.
+  ///\retval matching A write UEdgeMap of value type \c bool.
+  /// The found edges will be returned in this map.
   ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
   /// exactly once for each BNode. The nodes with \c true value represent
@@ -304 +491 @@
   ///on the push-relabel principle.
   template<class Graph,class MT, class GT>
-  int maxBpMatching(const Graph &g,MT &matching,GT &barrier) 
+  int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier) 
   {
-    BpMatching<Graph,MT> bpm(g,matching);
-    int ret=bpm.run();
-    bpm.barrier(barrier);
-    return ret;
+    PrBipartiteMatching<Graph> bpm(g);
+    bpm.run();
+    bpm.matching(matching);
+    bpm.bBarrier(barrier);
+    return bpm.matchingSize();
   }  
 
@@ -323 +511 @@
   ///on the push-relabel principle.
   template<class Graph>
-  bool perfectBpMatching(const Graph &g)
+  bool prPerfectBipartiteMatching(const Graph &g)
   {
-    typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
-    return perfectBpMatching(g,matching);
+    PrBipartiteMatching<Graph> bpm(g);
+    return bpm.runPerfect();
   }
 
@@ -334 +522 @@
   ///This function finds a perfect matching in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
-  /// The values are unspecified if the graph
+  ///\retval matching A write UEdgeMap of value type \c bool.
+  /// The found edges will be returned in this map.
+  /// The values are unchanged if the graph
   /// has no perfect matching.
   ///\return \c true iff \c g has a perfect matching.
@@ -345 +531 @@
   ///on the push-relabel principle.
   template<class Graph,class MT>
-  bool perfectBpMatching(const Graph &g,MT &matching) 
+  bool prPerfectBipartiteMatching(const Graph &g,MT &matching) 
   {
-    return BpMatching<Graph,MT>(g,matching).runPerfect()<0;
+    PrBipartiteMatching<Graph> bpm(g);
+    bool ret = bpm.runPerfect();
+    if (ret) bpm.matching(matching);
+    return ret;
   }
 
@@ -355 +544 @@
   ///This function finds a perfect matching in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
-  /// The values are unspecified if the graph
+  ///\retval matching A readwrite UEdgeMap of value type \c bool.
+  /// The found edges will be returned in this map.
+  /// The values are unchanged if the graph
   /// has no perfect matching.
   ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
@@ -365 +552 @@
   /// exactly once for each BNode. The nodes with \c true value represent
   /// a barrier, i.e. a subset \e B a of BNodes with the property that
-  /// the cardinality of \e B is greater than the numner of its neighbors.
+  /// the cardinality of \e B is greater than the number of its neighbors.
   ///\return \c true iff \c g has a perfect matching.
   ///
@@ -371 +558 @@
   ///on the push-relabel principle.
   template<class Graph,class MT, class GT>
-  int perfectBpMatching(const Graph &g,MT &matching,GT &barrier) 
+  int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) 
   {
-    BpMatching<Graph,MT> bpm(g,matching);
-    int ret=bpm.run();
-    if(ret>=0)
-      bpm.barrier(barrier,ret);
-    return ret<0;
+    PrBipartiteMatching<Graph> bpm(g);
+    bool ret=bpm.runPerfect();
+    if(ret)
+      bpm.matching(matching);
+    else
+      bpm.bBarrier(barrier);
+    return ret;
   }  
 }

test/bipartite_matching_test.cc

@@ -25 +25 @@
 #include <lemon/bpugraph_adaptor.h>
 #include <lemon/bipartite_matching.h>
+#include <lemon/pr_bipartite_matching.h>
 
 #include <lemon/graph_utils.h>
@@ -89 +90 @@
   {
     MaxBipartiteMatching<Graph> bpmatch(graph);
+
+    bpmatch.run();
+
+    Graph::UEdgeMap<bool> mm(graph);
+    Graph::NodeMap<bool> cs(graph);
+    
+    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
+    
+    for (UEdgeIt it(graph); it != INVALID; ++it) {
+      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
+    }
+    
+    for (ANodeIt it(graph); it != INVALID; ++it) {
+      int num = 0;
+      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+        if (mm[jt]) ++num;
+      }
+      check(num <= 1, "INVALID PRIMAL");
+    }
+    max_cardinality = bpmatch.matchingSize();
+  }
+
+  {
+    PrBipartiteMatching<Graph> bpmatch(graph);
 
     bpmatch.run();