Changeset 2463:19651a04d056 in lemon-0.x

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

Files:

• lemon/bipartite_matching.h (modified) (15 diffs)
• lemon/pr_bipartite_matching.h (modified) (11 diffs)
• test/bipartite_matching_test.cc (modified) (1 diff)

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.

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);

test/bipartite_matching_test.cc

@@ -137 +137 @@
 
   {
-    Graph::UEdgeMap<bool> mm(graph);
+    Graph::ANodeMap<UEdge> mm(graph);
 
     check(max_cardinality == maxBipartiteMatching(graph, mm),
           "WRONG MATCHING");
     
-    for (ANodeIt it(graph); it != INVALID; ++it) {
-      int num = 0;
-      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
-        if (mm[jt]) ++num;
+    for (BNodeIt it(graph); it != INVALID; ++it) {
+      int num = 0;
+      
+      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+        if (mm[graph.aNode(jt)] == jt) ++num;
+      }
+      check(num <= 1, "INVALID PRIMAL");
+    }
+  }
+
+  {
+    Graph::ANodeMap<UEdge> mm(graph);
+
+    check(max_cardinality == prBipartiteMatching(graph, mm),
+          "WRONG MATCHING");
+    
+    for (BNodeIt it(graph); it != INVALID; ++it) {
+      int num = 0;
+      
+      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+        if (mm[graph.aNode(jt)] == jt) ++num;
       }
       check(num <= 1, "INVALID PRIMAL");