Changeset 2463:19651a04d056 in lemon-0.x for lemon/pr_bipartite_matching.h

Timestamp:

08/21/07 15:22:21 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Query functions: aMatching and bMatching
Modified algorithm function interfaces
ANodeMap<UEdge> matching map
BNodeMap<bool> barrier map

Consistency between augmenting path and push-relabel algorithm

File:

• lemon/pr_bipartite_matching.h (modified) (11 diffs)

lemon/pr_bipartite_matching.h

@@ -316 +316 @@
     ///@{
 
-    /// \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.
+    ///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 {
@@ -329 +329 @@
     }
 
-    ///\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.
 
     ///Set true all matching uedge in the map and the others to false.
@@ -337 +337 @@
       for (UEdgeIt e(_g);e!=INVALID;++e) {
         mm.set(e,e==_matching[_g.aNode(e)]);
+      }
+      return _matching_size;
+    }
+
+    ///Gives back the matching in an ANodeMap.
+
+    ///Gives back the matching in an ANodeMap. The parameter should
+    ///be a write ANodeMap of UEdge values.
+    ///\return The number of the matching edges.
+    template<class MatchingMap>
+    int aMatching(MatchingMap& mm) const {
+      for (ANodeIt n(_g);n!=INVALID;++n) {
+        mm.set(n,_matching[n]);
+      }
+      return _matching_size;
+    }
+
+    ///Gives back the matching in a BNodeMap.
+
+    ///Gives back the matching in a BNodeMap. The parameter should
+    ///be a write BNodeMap of UEdge values.
+    ///\return The number of the matching edges.
+    template<class MatchingMap>
+    int bMatching(MatchingMap& mm) const {
+      for (BNodeIt n(_g);n!=INVALID;++n) {
+        mm.set(n,INVALID);
+      }
+      for (ANodeIt n(_g);n!=INVALID;++n) {
+        if (_matching[n]!=INVALID)
+          mm.set(_g.bNode(_matching[n]),_matching[n]);
       }
       return _matching_size;
@@ -458 +488 @@
   ///in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A write UEdgeMap of value type \c bool.
-  /// The found edges will be returned in this map.
+  ///\retval matching A write ANodeMap of value type \c UEdge.
+  /// 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.
   ///\return The cardinality of the maximum matching.
   ///
@@ -469 +501 @@
     PrBipartiteMatching<Graph> bpm(g);
     bpm.run();
-    bpm.matching(matching);
+    bpm.aMatching(matching);
     return bpm.matchingSize();
   }
@@ -479 +511 @@
   ///in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A write UEdgeMap of value type \c bool.
-  /// The found edges will be returned in this map.
+  ///\retval matching A write ANodeMap of value type \c UEdge.
+  /// 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.
   ///\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
@@ -495 +529 @@
     PrBipartiteMatching<Graph> bpm(g);
     bpm.run();
-    bpm.matching(matching);
+    bpm.aMatching(matching);
     bpm.bBarrier(barrier);
     return bpm.matchingSize();
@@ -522 +556 @@
   ///This function finds a perfect matching in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A write UEdgeMap of value type \c bool.
-  /// The found edges will be returned in this map.
+  ///\retval matching A write ANodeMap of value type \c UEdge.
+  /// 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 unchanged if the graph
   /// has no perfect matching.
@@ -534 +570 @@
   {
     PrBipartiteMatching<Graph> bpm(g);
-    bool ret = bpm.runPerfect();
-    if (ret) bpm.matching(matching);
+    bool ret = bpm.checkedRunPerfect();
+    if (ret) bpm.aMatching(matching);
     return ret;
   }
@@ -544 +580 @@
   ///This function finds a perfect matching in a bipartite graph \c g.
   ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite UEdgeMap of value type \c bool.
-  /// The found edges will be returned in this map.
+  ///\retval matching A write ANodeMap of value type \c UEdge.
+  /// 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 unchanged if the graph
   /// has no perfect matching.
@@ -558 +596 @@
   ///on the push-relabel principle.
   template<class Graph,class MT, class GT>
-  int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) 
+  bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) 
   {
     PrBipartiteMatching<Graph> bpm(g);
-    bool ret=bpm.runPerfect();
+    bool ret=bpm.checkedRunPerfect();
     if(ret)
-      bpm.matching(matching);
+      bpm.aMatching(matching);
     else
       bpm.bBarrier(barrier);