COIN-OR::LEMON - Graph Library

Changeset 2058:0b1fc1566fdb in lemon-0.x for lemon


Ignore:
Timestamp:
04/18/06 09:01:55 (14 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:
1 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
Note: See TracChangeset for help on using the changeset viewer.