COIN-OR::LEMON - Graph Library

Changeset 2058:0b1fc1566fdb in lemon-0.x


Ignore:
Timestamp:
04/18/06 09:01:55 (18 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

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/bipartite_matching.h

    r2051 r2058  
    329329    /// It just initalize the algorithm and then start it.
    330330    void run() {
    331       init();
     331      greedyInit();
    332332      start();
    333333    }
     
    350350    /// \return The size of the cover set.
    351351    template <typename CoverMap>
    352     int coverSet(CoverMap& covering) {
     352    int coverSet(CoverMap& covering) const {
    353353
    354354      typename Graph::template ANodeMap<bool> areached(*graph, false);
     
    404404    /// \return The number of the matching edges.
    405405    template <typename MatchingMap>
    406     int quickMatching(MatchingMap& matching) {
     406    int quickMatching(MatchingMap& matching) const {
    407407      for (ANodeIt it(*graph); it != INVALID; ++it) {
    408408        if (anode_matching[it] != INVALID) {
     
    418418    /// \return The number of the matching edges.
    419419    template <typename MatchingMap>
    420     int matching(MatchingMap& matching) {
     420    int matching(MatchingMap& matching) const {
    421421      for (UEdgeIt it(*graph); it != INVALID; ++it) {
    422422        matching[it] = it == anode_matching[graph->aNode(it)];
     
    429429    ///
    430430    /// It returns true if the given uedge is in the matching.
    431     bool matchingEdge(const UEdge& edge) {
     431    bool matchingEdge(const UEdge& edge) const {
    432432      return anode_matching[graph->aNode(edge)] == edge;
    433433    }
     
    437437    /// Returns the matching edge from the node. If there is not such
    438438    /// edge it gives back \c INVALID.
    439     UEdge matchingEdge(const Node& node) {
     439    UEdge matchingEdge(const Node& node) const {
    440440      if (graph->aNode(node)) {
    441441        return anode_matching[node];
     
    463463 
    464464  };
     465
     466  /// \ingroup matching
     467  ///
     468  /// \brief Maximum cardinality bipartite matching
     469  ///
     470  /// This function calculates the maximum cardinality matching
     471  /// in a bipartite graph. It gives back the matching in an undirected
     472  /// edge map.
     473  ///
     474  /// \param graph The bipartite graph.
     475  /// \retval matching The undirected edge map which will be set to
     476  /// the matching.
     477  /// \return The size of the matching.
     478  template <typename BpUGraph, typename MatchingMap>
     479  int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) {
     480    MaxBipartiteMatching<BpUGraph> bpmatching(graph);
     481    bpmatching.run();
     482    bpmatching.matching(matching);
     483    return bpmatching.matchingSize();
     484  }
    465485
    466486  /// \brief Default traits class for weighted bipartite matching algoritms.
     
    702722        bnode_potential[it] = 0;
    703723        for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
    704           if (-(*weight)[jt] <= bnode_potential[it]) {
    705             bnode_potential[it] = -(*weight)[jt];
     724          if ((*weight)[jt] > bnode_potential[it]) {
     725            bnode_potential[it] = (*weight)[jt];
    706726          }
    707727        }
     
    754774          if (jt == anode_matching[anode]) continue;
    755775          Node bnode = graph->bNode(jt);
    756           Value bvalue = avalue + anode_potential[anode] -
    757             bnode_potential[bnode] - (*weight)[jt];
     776          Value bvalue = avalue  - (*weight)[jt] +
     777            anode_potential[anode] + bnode_potential[bnode];
    758778          if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
    759779            bdist[bnode] = bvalue;
     
    779799          } else {
    780800            if (bestNode == INVALID ||
    781                 - bvalue - bnode_potential[bnode] > bestValue) {
    782               bestValue = - bvalue - bnode_potential[bnode];
     801                bnode_potential[bnode] - bvalue > bestValue) {
     802              bestValue = bnode_potential[bnode] - bvalue;
    783803              bestNode = bnode;
    784804            }
     
    796816      for (BNodeIt it(*graph); it != INVALID; ++it) {
    797817        if (bpred[it] != INVALID) {
    798           bnode_potential[it] += bdist[it];
     818          bnode_potential[it] -= bdist[it];
    799819        } else {
    800           bnode_potential[it] += bdistMax;
     820          bnode_potential[it] -= bdistMax;
    801821        }
    802822      }
     
    865885    /// \brief Gives back the potential in the NodeMap
    866886    ///
    867     /// Gives back the potential in the NodeMap. The potential
    868     /// is feasible if \f$ \pi(a) - \pi(b) - w(ab) = 0 \f$ for
    869     /// each matching edges and \f$ \pi(a) - \pi(b) - w(ab) \ge 0 \f$
    870     /// for each edges.
     887    /// Gives back the potential in the NodeMap. The matching is optimal
     888    /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
     889    /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
     890    /// for each edges. 
    871891    template <typename PotentialMap>
    872     void potential(PotentialMap& potential) {
     892    void potential(PotentialMap& potential) const {
    873893      for (ANodeIt it(*graph); it != INVALID; ++it) {
    874894        potential[it] = anode_potential[it];
     
    885905    /// \return The number of the matching edges.
    886906    template <typename MatchingMap>
    887     int quickMatching(MatchingMap& matching) {
     907    int quickMatching(MatchingMap& matching) const {
    888908      for (ANodeIt it(*graph); it != INVALID; ++it) {
    889909        if (anode_matching[it] != INVALID) {
     
    899919    /// \return The number of the matching edges.
    900920    template <typename MatchingMap>
    901     int matching(MatchingMap& matching) {
     921    int matching(MatchingMap& matching) const {
    902922      for (UEdgeIt it(*graph); it != INVALID; ++it) {
    903923        matching[it] = it == anode_matching[graph->aNode(it)];
     
    910930    ///
    911931    /// It returns true if the given uedge is in the matching.
    912     bool matchingEdge(const UEdge& edge) {
     932    bool matchingEdge(const UEdge& edge) const {
    913933      return anode_matching[graph->aNode(edge)] == edge;
    914934    }
     
    918938    /// Returns the matching edge from the node. If there is not such
    919939    /// edge it gives back \c INVALID.
    920     UEdge matchingEdge(const Node& node) {
     940    UEdge matchingEdge(const Node& node) const {
    921941      if (graph->aNode(node)) {
    922942        return anode_matching[node];
     
    9821002 
    9831003  };
     1004
     1005  /// \ingroup matching
     1006  ///
     1007  /// \brief Maximum weighted bipartite matching
     1008  ///
     1009  /// This function calculates the maximum weighted matching
     1010  /// in a bipartite graph. It gives back the matching in an undirected
     1011  /// edge map.
     1012  ///
     1013  /// \param graph The bipartite graph.
     1014  /// \param weight The undirected edge map which contains the weights.
     1015  /// \retval matching The undirected edge map which will be set to
     1016  /// the matching.
     1017  /// \return The value of the matching.
     1018  template <typename BpUGraph, typename WeightMap, typename MatchingMap>
     1019  typename WeightMap::Value
     1020  maxWeightedBipartiteMatching(const BpUGraph& graph, const WeightMap& weight,
     1021                               MatchingMap& matching) {
     1022    MaxWeightedBipartiteMatching<BpUGraph, WeightMap>
     1023      bpmatching(graph, weight);
     1024    bpmatching.run();
     1025    bpmatching.matching(matching);
     1026    return bpmatching.matchingValue();
     1027  }
     1028
     1029  /// \ingroup matching
     1030  ///
     1031  /// \brief Maximum weighted maximum cardinality bipartite matching
     1032  ///
     1033  /// This function calculates the maximum weighted of the maximum cardinality
     1034  /// matchings of a bipartite graph. It gives back the matching in an
     1035  /// undirected edge map.
     1036  ///
     1037  /// \param graph The bipartite graph.
     1038  /// \param weight The undirected edge map which contains the weights.
     1039  /// \retval matching The undirected edge map which will be set to
     1040  /// the matching.
     1041  /// \return The value of the matching.
     1042  template <typename BpUGraph, typename WeightMap, typename MatchingMap>
     1043  typename WeightMap::Value
     1044  maxWeightedMaxBipartiteMatching(const BpUGraph& graph,
     1045                                  const WeightMap& weight,
     1046                                  MatchingMap& matching) {
     1047    MaxWeightedBipartiteMatching<BpUGraph, WeightMap>
     1048      bpmatching(graph, weight);
     1049    bpmatching.run(true);
     1050    bpmatching.matching(matching);
     1051    return bpmatching.matchingValue();
     1052  }
    9841053
    9851054  /// \brief Default traits class for minimum cost bipartite matching
     
    13611430    /// \brief Gives back the potential in the NodeMap
    13621431    ///
    1363     /// Gives back the potential in the NodeMap. The potential
    1364     /// is feasible if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
     1432    /// Gives back the potential in the NodeMap. The potential is optimal with
     1433    /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
    13651434    /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$
    13661435    /// for each edges.
    13671436    template <typename PotentialMap>
    1368     void potential(PotentialMap& potential) {
     1437    void potential(PotentialMap& potential) const {
    13691438      for (ANodeIt it(*graph); it != INVALID; ++it) {
    13701439        potential[it] = anode_potential[it];
     
    13811450    /// \return The number of the matching edges.
    13821451    template <typename MatchingMap>
    1383     int quickMatching(MatchingMap& matching) {
     1452    int quickMatching(MatchingMap& matching) const {
    13841453      for (ANodeIt it(*graph); it != INVALID; ++it) {
    13851454        if (anode_matching[it] != INVALID) {
     
    13951464    /// \return The number of the matching edges.
    13961465    template <typename MatchingMap>
    1397     int matching(MatchingMap& matching) {
     1466    int matching(MatchingMap& matching) const {
    13981467      for (UEdgeIt it(*graph); it != INVALID; ++it) {
    13991468        matching[it] = it == anode_matching[graph->aNode(it)];
     
    14061475    ///
    14071476    /// It returns true if the given uedge is in the matching.
    1408     bool matchingEdge(const UEdge& edge) {
     1477    bool matchingEdge(const UEdge& edge) const {
    14091478      return anode_matching[graph->aNode(edge)] == edge;
    14101479    }
     
    14141483    /// Returns the matching edge from the node. If there is not such
    14151484    /// edge it gives back \c INVALID.
    1416     UEdge matchingEdge(const Node& node) {
     1485    UEdge matchingEdge(const Node& node) const {
    14171486      if (graph->aNode(node)) {
    14181487        return anode_matching[node];
     
    14791548  };
    14801549
     1550  /// \ingroup matching
     1551  ///
     1552  /// \brief Minimum cost maximum cardinality bipartite matching
     1553  ///
     1554  /// This function calculates the minimum cost matching of the maximum
     1555  /// cardinality matchings of a bipartite graph. It gives back the matching
     1556  /// in an undirected edge map.
     1557  ///
     1558  /// \param graph The bipartite graph.
     1559  /// \param cost The undirected edge map which contains the costs.
     1560  /// \retval matching The undirected edge map which will be set to
     1561  /// the matching.
     1562  /// \return The cost of the matching.
     1563  template <typename BpUGraph, typename CostMap, typename MatchingMap>
     1564  typename CostMap::Value
     1565  minCostMaxBipartiteMatching(const BpUGraph& graph,
     1566                              const CostMap& cost,
     1567                              MatchingMap& matching) {
     1568    MinCostMaxBipartiteMatching<BpUGraph, CostMap>
     1569      bpmatching(graph, cost);
     1570    bpmatching.run();
     1571    bpmatching.matching(matching);
     1572    return bpmatching.matchingCost();
     1573  }
     1574
    14811575}
    14821576
  • test/bipartite_matching_test.cc

    r2051 r2058  
    2424  vector<Node> aNodes;
    2525  vector<Node> bNodes;
    26   int n = argc > 1 ? atoi(argv[1]) : 100;
    27   int m = argc > 2 ? atoi(argv[2]) : 100;
     26  int n = argc > 1 ? atoi(argv[1]) : 10;
     27  int m = argc > 2 ? atoi(argv[2]) : 10;
    2828  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
    2929  int c = argc > 4 ? atoi(argv[4]) : 100;
     
    3434  int max_weight;
    3535  int max_cardinality_max_weight;
     36  int min_cost_matching;
    3637
    3738  for (int i = 0; i < n; ++i) {
     
    7273    }
    7374    max_cardinality = bpmatch.matchingSize();
     75  }
     76
     77  {
     78    Graph::UEdgeMap<bool> mm(graph);
     79
     80    check(max_cardinality == maxBipartiteMatching(graph, mm),
     81          "WRONG MATCHING");
     82   
     83    for (ANodeIt it(graph); it != INVALID; ++it) {
     84      int num = 0;
     85      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     86        if (mm[jt]) ++num;
     87      }
     88      check(num <= 1, "INVALID PRIMAL");
     89    }
    7490  }
    7591
     
    138154      for (UEdgeIt it(graph); it != INVALID; ++it) {
    139155        if (mm[it]) {
    140           check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
     156          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
    141157                "INVALID DUAL");
    142158        } else {
    143           check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
     159          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
    144160                "INVALID DUAL");
    145161        }
     
    160176
    161177  {
     178    Graph::UEdgeMap<bool> mm(graph);
     179
     180    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
     181          "WRONG MATCHING");
     182   
     183    for (ANodeIt it(graph); it != INVALID; ++it) {
     184      int num = 0;
     185      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     186        if (mm[jt]) ++num;
     187      }
     188      check(num <= 1, "INVALID PRIMAL");
     189    }
     190  }
     191
     192  {
    162193    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
    163194
     
    172203    for (UEdgeIt it(graph); it != INVALID; ++it) {
    173204      if (mm[it]) {
    174         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
     205        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
    175206              "INVALID DUAL");
    176207      } else {
    177         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
     208        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
    178209              "INVALID DUAL");
    179210      }
     
    203234    for (UEdgeIt it(graph); it != INVALID; ++it) {
    204235      if (mm[it]) {
    205         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
     236        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
    206237              "INVALID DUAL");
    207238      } else {
    208         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
     239        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
    209240              "INVALID DUAL");
    210241      }
     
    224255
    225256  {
    226     Graph::UEdgeMap<int> cost(graph);
    227 
    228     cost = subMap(constMap<UEdge>(c), weight);
     257    Graph::UEdgeMap<bool> mm(graph);
     258
     259    check(max_cardinality_max_weight ==
     260          maxWeightedMaxBipartiteMatching(graph, weight, mm),
     261          "WRONG MATCHING");
     262   
     263    for (ANodeIt it(graph); it != INVALID; ++it) {
     264      int num = 0;
     265      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     266        if (mm[jt]) ++num;
     267      }
     268      check(num <= 1, "INVALID PRIMAL");
     269    }
     270  }
     271
     272  Graph::UEdgeMap<int> cost(graph);
     273  cost = subMap(constMap<UEdge>(c), weight);
     274
     275  {
    229276
    230277    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
     
    256303    }
    257304
     305    min_cost_matching = bpmatch.matchingCost();
    258306    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
    259307    check(max_cardinality * c - max_cardinality_max_weight
     
    262310  }
    263311
     312  {
     313    Graph::UEdgeMap<bool> mm(graph);
     314
     315    check(min_cost_matching ==
     316          minCostMaxBipartiteMatching(graph, cost, mm),
     317          "WRONG MATCHING");
     318   
     319    for (ANodeIt it(graph); it != INVALID; ++it) {
     320      int num = 0;
     321      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     322        if (mm[jt]) ++num;
     323      }
     324      check(num <= 1, "INVALID PRIMAL");
     325    }
     326  }
     327
    264328  return 0;
    265329}
Note: See TracChangeset for help on using the changeset viewer.