COIN-OR::LEMON - Graph Library

Changeset 2463:19651a04d056 in lemon-0.x for lemon


Ignore:
Timestamp:
08/21/07 15:22:21 (12 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

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/bipartite_matching.h

    r2462 r2463  
    360360      for (ANodeIt it(*graph); it != INVALID; ++it) {
    361361        if (anode_matching[it] != INVALID) {
    362           mm[anode_matching[it]] = true;
     362          mm.set(anode_matching[it], true);
    363363        }
    364364      }
     
    373373    int matching(MatchingMap& mm) const {
    374374      for (UEdgeIt it(*graph); it != INVALID; ++it) {
    375         mm[it] = it == anode_matching[graph->aNode(it)];
     375        mm.set(it, it == anode_matching[graph->aNode(it)]);
    376376      }
    377377      return matching_size;
    378378    }
    379379
     380    ///Gives back the matching in an ANodeMap.
     381
     382    ///Gives back the matching in an ANodeMap. The parameter should
     383    ///be a write ANodeMap of UEdge values.
     384    ///\return The number of the matching edges.
     385    template<class MatchingMap>
     386    int aMatching(MatchingMap& mm) const {
     387      for (ANodeIt it(*graph); it != INVALID; ++it) {
     388        mm.set(it, anode_matching[it]);
     389      }
     390      return matching_size;
     391    }
     392
     393    ///Gives back the matching in a BNodeMap.
     394
     395    ///Gives back the matching in a BNodeMap. The parameter should
     396    ///be a write BNodeMap of UEdge values.
     397    ///\return The number of the matching edges.
     398    template<class MatchingMap>
     399    int bMatching(MatchingMap& mm) const {
     400      for (BNodeIt it(*graph); it != INVALID; ++it) {
     401        mm.set(it, bnode_matching[it]);
     402      }
     403      return matching_size;
     404    }
    380405
    381406    /// \brief Return true if the given uedge is in the matching.
     
    446471      int size = 0;
    447472      for (ANodeIt it(*graph); it != INVALID; ++it) {
    448         covering[it] = !areached[it] && anode_matching[it] != INVALID;
     473        covering.set(it, !areached[it] && anode_matching[it] != INVALID);
    449474        if (!areached[it] && anode_matching[it] != INVALID) {
    450475          ++size;
     
    452477      }
    453478      for (BNodeIt it(*graph); it != INVALID; ++it) {
    454         covering[it] = breached[it];
     479        covering.set(it, breached[it]);
    455480        if (breached[it]) {
    456481          ++size;
     
    500525
    501526      for (ANodeIt it(*graph); it != INVALID; ++it) {
    502         barrier[it] = areached[it] || anode_matching[it] == INVALID;
     527        barrier.set(it, areached[it] || anode_matching[it] == INVALID);
    503528      }
    504529    }
     
    544569
    545570      for (BNodeIt it(*graph); it != INVALID; ++it) {
    546         barrier[it] = !breached[it];
     571        barrier.set(it, !breached[it]);
    547572      }
    548573    }
     
    569594  ///
    570595  /// \param graph The bipartite graph.
    571   /// \retval matching The undirected edge map which will be set to
    572   /// the matching.
     596  /// \return The size of the matching.
     597  template <typename BpUGraph>
     598  int maxBipartiteMatching(const BpUGraph& graph) {
     599    MaxBipartiteMatching<BpUGraph> bpmatching(graph);
     600    bpmatching.run();
     601    return bpmatching.matchingSize();
     602  }
     603
     604  /// \ingroup matching
     605  ///
     606  /// \brief Maximum cardinality bipartite matching
     607  ///
     608  /// This function calculates the maximum cardinality matching
     609  /// in a bipartite graph. It gives back the matching in an undirected
     610  /// edge map.
     611  ///
     612  /// \param graph The bipartite graph.
     613  /// \retval matching The ANodeMap of UEdges which will be set to covered
     614  /// matching undirected edge.
    573615  /// \return The size of the matching.
    574616  template <typename BpUGraph, typename MatchingMap>
     
    576618    MaxBipartiteMatching<BpUGraph> bpmatching(graph);
    577619    bpmatching.run();
    578     bpmatching.matching(matching);
     620    bpmatching.aMatching(matching);
     621    return bpmatching.matchingSize();
     622  }
     623
     624  /// \ingroup matching
     625  ///
     626  /// \brief Maximum cardinality bipartite matching
     627  ///
     628  /// This function calculates the maximum cardinality matching
     629  /// in a bipartite graph. It gives back the matching in an undirected
     630  /// edge map.
     631  ///
     632  /// \param graph The bipartite graph.
     633  /// \retval matching The ANodeMap of UEdges which will be set to covered
     634  /// matching undirected edge.
     635  /// \retval barrier The BNodeMap of bools which will be set to a barrier
     636  /// of the BNode-set.
     637  /// \return The size of the matching.
     638  template <typename BpUGraph, typename MatchingMap, typename BarrierMap>
     639  int maxBipartiteMatching(const BpUGraph& graph,
     640                           MatchingMap& matching, BarrierMap& barrier) {
     641    MaxBipartiteMatching<BpUGraph> bpmatching(graph);
     642    bpmatching.run();
     643    bpmatching.aMatching(matching);
     644    bpmatching.bBarrier(barrier);
    579645    return bpmatching.matchingSize();
    580646  }
     
    9881054    void potential(PotentialMap& pt) const {
    9891055      for (ANodeIt it(*graph); it != INVALID; ++it) {
    990         pt[it] = anode_potential[it];
     1056        pt.set(it, anode_potential[it]);
    9911057      }
    9921058      for (BNodeIt it(*graph); it != INVALID; ++it) {
    993         pt[it] = bnode_potential[it];
     1059        pt.set(it, bnode_potential[it]);
    9941060      }
    9951061    }
     
    10041070      for (ANodeIt it(*graph); it != INVALID; ++it) {
    10051071        if (anode_matching[it] != INVALID) {
    1006           mm[anode_matching[it]] = true;
     1072          mm.set(anode_matching[it], true);
    10071073        }
    10081074      }
     
    10171083    int matching(MatchingMap& mm) const {
    10181084      for (UEdgeIt it(*graph); it != INVALID; ++it) {
    1019         mm[it] = it == anode_matching[graph->aNode(it)];
     1085        mm.set(it, it == anode_matching[graph->aNode(it)]);
     1086      }
     1087      return matching_size;
     1088    }
     1089
     1090    ///Gives back the matching in an ANodeMap.
     1091
     1092    ///Gives back the matching in an ANodeMap. The parameter should
     1093    ///be a write ANodeMap of UEdge values.
     1094    ///\return The number of the matching edges.
     1095    template<class MatchingMap>
     1096    int aMatching(MatchingMap& mm) const {
     1097      for (ANodeIt it(*graph); it != INVALID; ++it) {
     1098        mm.set(it, anode_matching[it]);
     1099      }
     1100      return matching_size;
     1101    }
     1102
     1103    ///Gives back the matching in a BNodeMap.
     1104
     1105    ///Gives back the matching in a BNodeMap. The parameter should
     1106    ///be a write BNodeMap of UEdge values.
     1107    ///\return The number of the matching edges.
     1108    template<class MatchingMap>
     1109    int bMatching(MatchingMap& mm) const {
     1110      for (BNodeIt it(*graph); it != INVALID; ++it) {
     1111        mm.set(it, bnode_matching[it]);
    10201112      }
    10211113      return matching_size;
     
    15341626    /// \brief Gives back the potential in the NodeMap
    15351627    ///
    1536     /// Gives back the potential in the NodeMap. The potential is optimal with
    1537     /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
    1538     /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$
    1539     /// for each edges.
     1628    /// Gives back the potential in the NodeMap. The matching is optimal
     1629    /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
     1630    /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
     1631    /// for each edges. 
    15401632    template <typename PotentialMap>
    15411633    void potential(PotentialMap& pt) const {
    15421634      for (ANodeIt it(*graph); it != INVALID; ++it) {
    1543         pt[it] = anode_potential[it];
     1635        pt.set(it, anode_potential[it]);
    15441636      }
    15451637      for (BNodeIt it(*graph); it != INVALID; ++it) {
    1546         pt[it] = bnode_potential[it];
     1638        pt.set(it, bnode_potential[it]);
    15471639      }
    15481640    }
     
    15571649      for (ANodeIt it(*graph); it != INVALID; ++it) {
    15581650        if (anode_matching[it] != INVALID) {
    1559           mm[anode_matching[it]] = true;
     1651          mm.set(anode_matching[it], true);
    15601652        }
    15611653      }
     
    15701662    int matching(MatchingMap& mm) const {
    15711663      for (UEdgeIt it(*graph); it != INVALID; ++it) {
    1572         mm[it] = it == anode_matching[graph->aNode(it)];
     1664        mm.set(it, it == anode_matching[graph->aNode(it)]);
    15731665      }
    15741666      return matching_size;
    15751667    }
    15761668
     1669    /// \brief Gives back the matching in an ANodeMap.
     1670    ///
     1671    /// Gives back the matching in an ANodeMap. The parameter should
     1672    /// be a write ANodeMap of UEdge values.
     1673    /// \return The number of the matching edges.
     1674    template<class MatchingMap>
     1675    int aMatching(MatchingMap& mm) const {
     1676      for (ANodeIt it(*graph); it != INVALID; ++it) {
     1677        mm.set(it, anode_matching[it]);
     1678      }
     1679      return matching_size;
     1680    }
     1681
     1682    /// \brief Gives back the matching in a BNodeMap.
     1683    ///
     1684    /// Gives back the matching in a BNodeMap. The parameter should
     1685    /// be a write BNodeMap of UEdge values.
     1686    /// \return The number of the matching edges.
     1687    template<class MatchingMap>
     1688    int bMatching(MatchingMap& mm) const {
     1689      for (BNodeIt it(*graph); it != INVALID; ++it) {
     1690        mm.set(it, bnode_matching[it]);
     1691      }
     1692      return matching_size;
     1693    }
    15771694
    15781695    /// \brief Return true if the given uedge is in the matching.
     
    16561773  /// \brief Minimum cost maximum cardinality bipartite matching
    16571774  ///
    1658   /// This function calculates the minimum cost matching of the maximum
    1659   /// cardinality matchings of a bipartite graph. It gives back the matching
    1660   /// in an undirected edge map.
     1775  /// This function calculates the maximum cardinality matching with
     1776  /// minimum cost of a bipartite graph. It gives back the matching in
     1777  /// an undirected edge map.
    16611778  ///
    16621779  /// \param graph The bipartite graph.
  • lemon/pr_bipartite_matching.h

    r2462 r2463  
    316316    ///@{
    317317
    318     /// \brief Set true all matching uedge in the map.
    319     ///
    320     /// Set true all matching uedge in the map. It does not change the
    321     /// value mapped to the other uedges.
    322     /// \return The number of the matching edges.
     318    ///Set true all matching uedge in the map.
     319
     320    ///Set true all matching uedge in the map. It does not change the
     321    ///value mapped to the other uedges.
     322    ///\return The number of the matching edges.
    323323    template <typename MatchingMap>
    324324    int quickMatching(MatchingMap& mm) const {
     
    329329    }
    330330
    331     ///\brief Set true all matching uedge in the map and the others to false.
     331    ///Set true all matching uedge in the map and the others to false.
    332332
    333333    ///Set true all matching uedge in the map and the others to false.
     
    337337      for (UEdgeIt e(_g);e!=INVALID;++e) {
    338338        mm.set(e,e==_matching[_g.aNode(e)]);
     339      }
     340      return _matching_size;
     341    }
     342
     343    ///Gives back the matching in an ANodeMap.
     344
     345    ///Gives back the matching in an ANodeMap. The parameter should
     346    ///be a write ANodeMap of UEdge values.
     347    ///\return The number of the matching edges.
     348    template<class MatchingMap>
     349    int aMatching(MatchingMap& mm) const {
     350      for (ANodeIt n(_g);n!=INVALID;++n) {
     351        mm.set(n,_matching[n]);
     352      }
     353      return _matching_size;
     354    }
     355
     356    ///Gives back the matching in a BNodeMap.
     357
     358    ///Gives back the matching in a BNodeMap. The parameter should
     359    ///be a write BNodeMap of UEdge values.
     360    ///\return The number of the matching edges.
     361    template<class MatchingMap>
     362    int bMatching(MatchingMap& mm) const {
     363      for (BNodeIt n(_g);n!=INVALID;++n) {
     364        mm.set(n,INVALID);
     365      }
     366      for (ANodeIt n(_g);n!=INVALID;++n) {
     367        if (_matching[n]!=INVALID)
     368          mm.set(_g.bNode(_matching[n]),_matching[n]);
    339369      }
    340370      return _matching_size;
     
    458488  ///in a bipartite graph \c g.
    459489  ///\param g An undirected bipartite graph.
    460   ///\retval matching A write UEdgeMap of value type \c bool.
    461   /// The found edges will be returned in this map.
     490  ///\retval matching A write ANodeMap of value type \c UEdge.
     491  /// The found edges will be returned in this map,
     492  /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
     493  /// that covers the node \c n.
    462494  ///\return The cardinality of the maximum matching.
    463495  ///
     
    469501    PrBipartiteMatching<Graph> bpm(g);
    470502    bpm.run();
    471     bpm.matching(matching);
     503    bpm.aMatching(matching);
    472504    return bpm.matchingSize();
    473505  }
     
    479511  ///in a bipartite graph \c g.
    480512  ///\param g An undirected bipartite graph.
    481   ///\retval matching A write UEdgeMap of value type \c bool.
    482   /// The found edges will be returned in this map.
     513  ///\retval matching A write ANodeMap of value type \c UEdge.
     514  /// The found edges will be returned in this map,
     515  /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
     516  /// that covers the node \c n.
    483517  ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
    484518  /// exactly once for each BNode. The nodes with \c true value represent
     
    495529    PrBipartiteMatching<Graph> bpm(g);
    496530    bpm.run();
    497     bpm.matching(matching);
     531    bpm.aMatching(matching);
    498532    bpm.bBarrier(barrier);
    499533    return bpm.matchingSize();
     
    522556  ///This function finds a perfect matching in a bipartite graph \c g.
    523557  ///\param g An undirected bipartite graph.
    524   ///\retval matching A write UEdgeMap of value type \c bool.
    525   /// The found edges will be returned in this map.
     558  ///\retval matching A write ANodeMap of value type \c UEdge.
     559  /// The found edges will be returned in this map,
     560  /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
     561  /// that covers the node \c n.
    526562  /// The values are unchanged if the graph
    527563  /// has no perfect matching.
     
    534570  {
    535571    PrBipartiteMatching<Graph> bpm(g);
    536     bool ret = bpm.runPerfect();
    537     if (ret) bpm.matching(matching);
     572    bool ret = bpm.checkedRunPerfect();
     573    if (ret) bpm.aMatching(matching);
    538574    return ret;
    539575  }
     
    544580  ///This function finds a perfect matching in a bipartite graph \c g.
    545581  ///\param g An undirected bipartite graph.
    546   ///\retval matching A readwrite UEdgeMap of value type \c bool.
    547   /// The found edges will be returned in this map.
     582  ///\retval matching A write ANodeMap of value type \c UEdge.
     583  /// The found edges will be returned in this map,
     584  /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
     585  /// that covers the node \c n.
    548586  /// The values are unchanged if the graph
    549587  /// has no perfect matching.
     
    558596  ///on the push-relabel principle.
    559597  template<class Graph,class MT, class GT>
    560   int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
     598  bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
    561599  {
    562600    PrBipartiteMatching<Graph> bpm(g);
    563     bool ret=bpm.runPerfect();
     601    bool ret=bpm.checkedRunPerfect();
    564602    if(ret)
    565       bpm.matching(matching);
     603      bpm.aMatching(matching);
    566604    else
    567605      bpm.bBarrier(barrier);
Note: See TracChangeset for help on using the changeset viewer.