Changeset 2463:19651a04d056 in lemon-0.x for lemon/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/bipartite_matching.h (modified) (15 diffs)

lemon/bipartite_matching.h

@@ -360 +360 @@
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         if (anode_matching[it] != INVALID) {
-          mm[anode_matching[it]] = true;
+          mm.set(anode_matching[it], true);
         }
       }
@@ -373 +373 @@
     int matching(MatchingMap& mm) const {
       for (UEdgeIt it(*graph); it != INVALID; ++it) {
-        mm[it] = it == anode_matching[graph->aNode(it)];
+        mm.set(it, it == anode_matching[graph->aNode(it)]);
       }
       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 it(*graph); it != INVALID; ++it) {
+        mm.set(it, anode_matching[it]);
+      }
+      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 it(*graph); it != INVALID; ++it) {
+        mm.set(it, bnode_matching[it]);
+      }
+      return matching_size;
+    }
 
     /// \brief Return true if the given uedge is in the matching.
@@ -446 +471 @@
       int size = 0;
       for (ANodeIt it(*graph); it != INVALID; ++it) {
-        covering[it] = !areached[it] && anode_matching[it] != INVALID;
+        covering.set(it, !areached[it] && anode_matching[it] != INVALID);
         if (!areached[it] && anode_matching[it] != INVALID) {
           ++size;
@@ -452 +477 @@
       }
       for (BNodeIt it(*graph); it != INVALID; ++it) {
-        covering[it] = breached[it];
+        covering.set(it, breached[it]);
         if (breached[it]) {
           ++size;
@@ -500 +525 @@
 
       for (ANodeIt it(*graph); it != INVALID; ++it) {
-        barrier[it] = areached[it] || anode_matching[it] == INVALID;
+        barrier.set(it, areached[it] || anode_matching[it] == INVALID);
       }
     }
@@ -544 +569 @@
 
       for (BNodeIt it(*graph); it != INVALID; ++it) {
-        barrier[it] = !breached[it];
+        barrier.set(it, !breached[it]);
       }
     }
@@ -569 +594 @@
   ///
   /// \param graph The bipartite graph.
-  /// \retval matching The undirected edge map which will be set to 
-  /// the matching.
+  /// \return The size of the matching.
+  template <typename BpUGraph>
+  int maxBipartiteMatching(const BpUGraph& graph) {
+    MaxBipartiteMatching<BpUGraph> bpmatching(graph);
+    bpmatching.run();
+    return bpmatching.matchingSize();
+  }
+
+  /// \ingroup matching
+  ///
+  /// \brief Maximum cardinality bipartite matching
+  ///
+  /// This function calculates the maximum cardinality matching
+  /// in a bipartite graph. It gives back the matching in an undirected
+  /// edge map.
+  ///
+  /// \param graph The bipartite graph.
+  /// \retval matching The ANodeMap of UEdges which will be set to covered
+  /// matching undirected edge.
   /// \return The size of the matching.
   template <typename BpUGraph, typename MatchingMap>
@@ -576 +618 @@
     MaxBipartiteMatching<BpUGraph> bpmatching(graph);
     bpmatching.run();
-    bpmatching.matching(matching);
+    bpmatching.aMatching(matching);
+    return bpmatching.matchingSize();
+  }
+
+  /// \ingroup matching
+  ///
+  /// \brief Maximum cardinality bipartite matching
+  ///
+  /// This function calculates the maximum cardinality matching
+  /// in a bipartite graph. It gives back the matching in an undirected
+  /// edge map.
+  ///
+  /// \param graph The bipartite graph.
+  /// \retval matching The ANodeMap of UEdges which will be set to covered
+  /// matching undirected edge.
+  /// \retval barrier The BNodeMap of bools which will be set to a barrier
+  /// of the BNode-set.
+  /// \return The size of the matching.
+  template <typename BpUGraph, typename MatchingMap, typename BarrierMap>
+  int maxBipartiteMatching(const BpUGraph& graph, 
+                           MatchingMap& matching, BarrierMap& barrier) {
+    MaxBipartiteMatching<BpUGraph> bpmatching(graph);
+    bpmatching.run();
+    bpmatching.aMatching(matching);
+    bpmatching.bBarrier(barrier);
     return bpmatching.matchingSize();
   }
@@ -988 +1054 @@
     void potential(PotentialMap& pt) const {
       for (ANodeIt it(*graph); it != INVALID; ++it) {
-        pt[it] = anode_potential[it];
+        pt.set(it, anode_potential[it]);
       }
       for (BNodeIt it(*graph); it != INVALID; ++it) {
-        pt[it] = bnode_potential[it];
+        pt.set(it, bnode_potential[it]);
       }
     }
@@ -1004 +1070 @@
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         if (anode_matching[it] != INVALID) {
-          mm[anode_matching[it]] = true;
+          mm.set(anode_matching[it], true);
         }
       }
@@ -1017 +1083 @@
     int matching(MatchingMap& mm) const {
       for (UEdgeIt it(*graph); it != INVALID; ++it) {
-        mm[it] = it == anode_matching[graph->aNode(it)];
+        mm.set(it, it == anode_matching[graph->aNode(it)]);
+      }
+      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 it(*graph); it != INVALID; ++it) {
+        mm.set(it, anode_matching[it]);
+      }
+      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 it(*graph); it != INVALID; ++it) {
+        mm.set(it, bnode_matching[it]);
       }
       return matching_size;
@@ -1534 +1626 @@
     /// \brief Gives back the potential in the NodeMap
     ///
-    /// Gives back the potential in the NodeMap. The potential is optimal with 
-    /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
-    /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$
-    /// for each edges.
+    /// Gives back the potential in the NodeMap. The matching is optimal
+    /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
+    /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
+    /// for each edges. 
     template <typename PotentialMap>
     void potential(PotentialMap& pt) const {
       for (ANodeIt it(*graph); it != INVALID; ++it) {
-        pt[it] = anode_potential[it];
+        pt.set(it, anode_potential[it]);
       }
       for (BNodeIt it(*graph); it != INVALID; ++it) {
-        pt[it] = bnode_potential[it];
+        pt.set(it, bnode_potential[it]);
       }
     }
@@ -1557 +1649 @@
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         if (anode_matching[it] != INVALID) {
-          mm[anode_matching[it]] = true;
+          mm.set(anode_matching[it], true);
         }
       }
@@ -1570 +1662 @@
     int matching(MatchingMap& mm) const {
       for (UEdgeIt it(*graph); it != INVALID; ++it) {
-        mm[it] = it == anode_matching[graph->aNode(it)];
+        mm.set(it, it == anode_matching[graph->aNode(it)]);
       }
       return matching_size;
     }
 
+    /// \brief 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 it(*graph); it != INVALID; ++it) {
+        mm.set(it, anode_matching[it]);
+      }
+      return matching_size;
+    }
+
+    /// \brief 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 it(*graph); it != INVALID; ++it) {
+        mm.set(it, bnode_matching[it]);
+      }
+      return matching_size;
+    }
 
     /// \brief Return true if the given uedge is in the matching.
@@ -1656 +1773 @@
   /// \brief Minimum cost maximum cardinality bipartite matching
   ///
-  /// This function calculates the minimum cost matching of the maximum 
-  /// cardinality matchings of a bipartite graph. It gives back the matching 
-  /// in an undirected edge map.
+  /// This function calculates the maximum cardinality matching with
+  /// minimum cost of a bipartite graph. It gives back the matching in
+  /// an undirected edge map.
   ///
   /// \param graph The bipartite graph.