Changeset 2058:0b1fc1566fdb in lemon-0.x for lemon/bipartite_matching.h

Timestamp:

04/18/06 09:01:55 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Refinements in bipartite matching algorithms

File:

• lemon/bipartite_matching.h (modified) (23 diffs)

lemon/bipartite_matching.h

@@ -329 +329 @@
     /// It just initalize the algorithm and then start it.
     void run() {
-      init();
+      greedyInit();
       start();
     }
@@ -350 +350 @@
     /// \return The size of the cover set.
     template <typename CoverMap>
-    int coverSet(CoverMap& covering) {
+    int coverSet(CoverMap& covering) const {
 
       typename Graph::template ANodeMap<bool> areached(*graph, false);
@@ -404 +404 @@
     /// \return The number of the matching edges.
     template <typename MatchingMap>
-    int quickMatching(MatchingMap& matching) {
+    int quickMatching(MatchingMap& matching) const {
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         if (anode_matching[it] != INVALID) {
@@ -418 +418 @@
     /// \return The number of the matching edges.
     template <typename MatchingMap>
-    int matching(MatchingMap& matching) {
+    int matching(MatchingMap& matching) const {
       for (UEdgeIt it(*graph); it != INVALID; ++it) {
         matching[it] = it == anode_matching[graph->aNode(it)];
@@ -429 +429 @@
     /// 
     /// It returns true if the given uedge is in the matching.
-    bool matchingEdge(const UEdge& edge) {
+    bool matchingEdge(const UEdge& edge) const {
       return anode_matching[graph->aNode(edge)] == edge;
     }
@@ -437 +437 @@
     /// Returns the matching edge from the node. If there is not such
     /// edge it gives back \c INVALID.
-    UEdge matchingEdge(const Node& node) {
+    UEdge matchingEdge(const Node& node) const {
       if (graph->aNode(node)) {
         return anode_matching[node];
@@ -463 +463 @@
   
   };
+
+  /// \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 undirected edge map which will be set to 
+  /// the matching.
+  /// \return The size of the matching.
+  template <typename BpUGraph, typename MatchingMap>
+  int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) {
+    MaxBipartiteMatching<BpUGraph> bpmatching(graph);
+    bpmatching.run();
+    bpmatching.matching(matching);
+    return bpmatching.matchingSize();
+  }
 
   /// \brief Default traits class for weighted bipartite matching algoritms.
@@ -702 +722 @@
         bnode_potential[it] = 0;
         for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
-          if (-(*weight)[jt] <= bnode_potential[it]) {
-            bnode_potential[it] = -(*weight)[jt];
+          if ((*weight)[jt] > bnode_potential[it]) {
+            bnode_potential[it] = (*weight)[jt];
           }
         }
@@ -754 +774 @@
           if (jt == anode_matching[anode]) continue;
           Node bnode = graph->bNode(jt);
-          Value bvalue = avalue + anode_potential[anode] - 
-            bnode_potential[bnode] - (*weight)[jt];
+          Value bvalue = avalue  - (*weight)[jt] +
+            anode_potential[anode] + bnode_potential[bnode];
           if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
             bdist[bnode] = bvalue;
@@ -779 +799 @@
           } else {
             if (bestNode == INVALID || 
-                - bvalue - bnode_potential[bnode] > bestValue) {
-              bestValue = - bvalue - bnode_potential[bnode];
+                bnode_potential[bnode] - bvalue > bestValue) {
+              bestValue = bnode_potential[bnode] - bvalue;
               bestNode = bnode;
             }
@@ -796 +816 @@
       for (BNodeIt it(*graph); it != INVALID; ++it) {
         if (bpred[it] != INVALID) {
-          bnode_potential[it] += bdist[it];
+          bnode_potential[it] -= bdist[it];
         } else {
-          bnode_potential[it] += bdistMax;
+          bnode_potential[it] -= bdistMax;
         }
       }
@@ -865 +885 @@
     /// \brief Gives back the potential in the NodeMap
     ///
-    /// Gives back the potential in the NodeMap. The potential
-    /// is feasible 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& potential) {
+    void potential(PotentialMap& potential) const {
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         potential[it] = anode_potential[it];
@@ -885 +905 @@
     /// \return The number of the matching edges.
     template <typename MatchingMap>
-    int quickMatching(MatchingMap& matching) {
+    int quickMatching(MatchingMap& matching) const {
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         if (anode_matching[it] != INVALID) {
@@ -899 +919 @@
     /// \return The number of the matching edges.
     template <typename MatchingMap>
-    int matching(MatchingMap& matching) {
+    int matching(MatchingMap& matching) const {
       for (UEdgeIt it(*graph); it != INVALID; ++it) {
         matching[it] = it == anode_matching[graph->aNode(it)];
@@ -910 +930 @@
     /// 
     /// It returns true if the given uedge is in the matching.
-    bool matchingEdge(const UEdge& edge) {
+    bool matchingEdge(const UEdge& edge) const {
       return anode_matching[graph->aNode(edge)] == edge;
     }
@@ -918 +938 @@
     /// Returns the matching edge from the node. If there is not such
     /// edge it gives back \c INVALID.
-    UEdge matchingEdge(const Node& node) {
+    UEdge matchingEdge(const Node& node) const {
       if (graph->aNode(node)) {
         return anode_matching[node];
@@ -982 +1002 @@
   
   };
+
+  /// \ingroup matching
+  ///
+  /// \brief Maximum weighted bipartite matching
+  ///
+  /// This function calculates the maximum weighted matching
+  /// in a bipartite graph. It gives back the matching in an undirected
+  /// edge map.
+  ///
+  /// \param graph The bipartite graph.
+  /// \param weight The undirected edge map which contains the weights.
+  /// \retval matching The undirected edge map which will be set to 
+  /// the matching.
+  /// \return The value of the matching.
+  template <typename BpUGraph, typename WeightMap, typename MatchingMap>
+  typename WeightMap::Value 
+  maxWeightedBipartiteMatching(const BpUGraph& graph, const WeightMap& weight,
+                               MatchingMap& matching) {
+    MaxWeightedBipartiteMatching<BpUGraph, WeightMap> 
+      bpmatching(graph, weight);
+    bpmatching.run();
+    bpmatching.matching(matching);
+    return bpmatching.matchingValue();
+  }
+
+  /// \ingroup matching
+  ///
+  /// \brief Maximum weighted maximum cardinality bipartite matching
+  ///
+  /// This function calculates the maximum weighted of the maximum cardinality
+  /// matchings of a bipartite graph. It gives back the matching in an 
+  /// undirected edge map.
+  ///
+  /// \param graph The bipartite graph.
+  /// \param weight The undirected edge map which contains the weights.
+  /// \retval matching The undirected edge map which will be set to 
+  /// the matching.
+  /// \return The value of the matching.
+  template <typename BpUGraph, typename WeightMap, typename MatchingMap>
+  typename WeightMap::Value 
+  maxWeightedMaxBipartiteMatching(const BpUGraph& graph, 
+                                  const WeightMap& weight,
+                                  MatchingMap& matching) {
+    MaxWeightedBipartiteMatching<BpUGraph, WeightMap> 
+      bpmatching(graph, weight);
+    bpmatching.run(true);
+    bpmatching.matching(matching);
+    return bpmatching.matchingValue();
+  }
 
   /// \brief Default traits class for minimum cost bipartite matching
@@ -1361 +1430 @@
     /// \brief Gives back the potential in the NodeMap
     ///
-    /// Gives back the potential in the NodeMap. The potential
-    /// is feasible if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
+    /// 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.
     template <typename PotentialMap>
-    void potential(PotentialMap& potential) {
+    void potential(PotentialMap& potential) const {
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         potential[it] = anode_potential[it];
@@ -1381 +1450 @@
     /// \return The number of the matching edges.
     template <typename MatchingMap>
-    int quickMatching(MatchingMap& matching) {
+    int quickMatching(MatchingMap& matching) const {
       for (ANodeIt it(*graph); it != INVALID; ++it) {
         if (anode_matching[it] != INVALID) {
@@ -1395 +1464 @@
     /// \return The number of the matching edges.
     template <typename MatchingMap>
-    int matching(MatchingMap& matching) {
+    int matching(MatchingMap& matching) const {
       for (UEdgeIt it(*graph); it != INVALID; ++it) {
         matching[it] = it == anode_matching[graph->aNode(it)];
@@ -1406 +1475 @@
     /// 
     /// It returns true if the given uedge is in the matching.
-    bool matchingEdge(const UEdge& edge) {
+    bool matchingEdge(const UEdge& edge) const {
       return anode_matching[graph->aNode(edge)] == edge;
     }
@@ -1414 +1483 @@
     /// Returns the matching edge from the node. If there is not such
     /// edge it gives back \c INVALID.
-    UEdge matchingEdge(const Node& node) {
+    UEdge matchingEdge(const Node& node) const {
       if (graph->aNode(node)) {
         return anode_matching[node];
@@ -1479 +1548 @@
   };
 
+  /// \ingroup matching
+  ///
+  /// \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.
+  ///
+  /// \param graph The bipartite graph.
+  /// \param cost The undirected edge map which contains the costs.
+  /// \retval matching The undirected edge map which will be set to 
+  /// the matching.
+  /// \return The cost of the matching.
+  template <typename BpUGraph, typename CostMap, typename MatchingMap>
+  typename CostMap::Value 
+  minCostMaxBipartiteMatching(const BpUGraph& graph, 
+                              const CostMap& cost,
+                              MatchingMap& matching) {
+    MinCostMaxBipartiteMatching<BpUGraph, CostMap> 
+      bpmatching(graph, cost);
+    bpmatching.run();
+    bpmatching.matching(matching);
+    return bpmatching.matchingCost();
+  }
+
 }