COIN-OR::LEMON - Graph Library

Changeset 2462:7a096a6bf53a in lemon-0.x


Ignore:
Timestamp:
08/11/07 18:34:41 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3300
Message:

Common interface for bipartite matchings
Some useful query function for push-relabel based matching

The naming should be rethink for these classes
for example: pr-ap prefix for push-relabel and augmenting path
algorithms

Files:
3 edited
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r2440 r2462  
    4040        lemon/bin_heap.h \
    4141        lemon/bipartite_matching.h \
    42         lemon/bp_matching.h \
    4342        lemon/bpugraph_adaptor.h \
    4443        lemon/bucket_heap.h \
     
    104103        lemon/preflow.h \
    105104        lemon/prim.h \
     105        lemon/pr_bipartite_matching.h \
    106106        lemon/radix_heap.h \
    107107        lemon/radix_sort.h \
  • lemon/bipartite_matching.h

    r2391 r2462  
    3030///\file
    3131///\brief Maximum matching algorithms in bipartite graphs.
     32///
     33///\note The pr_bipartite_matching.h file also contains algorithms to
     34///solve maximum cardinality bipartite matching problems.
    3235
    3336namespace lemon {
     
    4043  /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time
    4144  /// complexity.
     45  ///
     46  /// \note In several cases the push-relabel based algorithms have
     47  /// better runtime performance than the augmenting path based ones.
     48  ///
     49  /// \see PrBipartiteMatching
    4250  template <typename BpUGraph>
    4351  class MaxBipartiteMatching {
     
    343351    ///@{
    344352
    345     /// \brief Returns an minimum covering of the nodes.
     353    /// \brief Set true all matching uedge in the map.
     354    ///
     355    /// Set true all matching uedge in the map. It does not change the
     356    /// value mapped to the other uedges.
     357    /// \return The number of the matching edges.
     358    template <typename MatchingMap>
     359    int quickMatching(MatchingMap& mm) const {
     360      for (ANodeIt it(*graph); it != INVALID; ++it) {
     361        if (anode_matching[it] != INVALID) {
     362          mm[anode_matching[it]] = true;
     363        }
     364      }
     365      return matching_size;
     366    }
     367
     368    /// \brief Set true all matching uedge in the map and the others to false.
     369    ///
     370    /// Set true all matching uedge in the map and the others to false.
     371    /// \return The number of the matching edges.
     372    template <typename MatchingMap>
     373    int matching(MatchingMap& mm) const {
     374      for (UEdgeIt it(*graph); it != INVALID; ++it) {
     375        mm[it] = it == anode_matching[graph->aNode(it)];
     376      }
     377      return matching_size;
     378    }
     379
     380
     381    /// \brief Return true if the given uedge is in the matching.
     382    ///
     383    /// It returns true if the given uedge is in the matching.
     384    bool matchingEdge(const UEdge& edge) const {
     385      return anode_matching[graph->aNode(edge)] == edge;
     386    }
     387
     388    /// \brief Returns the matching edge from the node.
     389    ///
     390    /// Returns the matching edge from the node. If there is not such
     391    /// edge it gives back \c INVALID.
     392    UEdge matchingEdge(const Node& node) const {
     393      if (graph->aNode(node)) {
     394        return anode_matching[node];
     395      } else {
     396        return bnode_matching[node];
     397      }
     398    }
     399
     400    /// \brief Gives back the number of the matching edges.
     401    ///
     402    /// Gives back the number of the matching edges.
     403    int matchingSize() const {
     404      return matching_size;
     405    }
     406
     407    /// \brief Returns a minimum covering of the nodes.
    346408    ///
    347409    /// The minimum covering set problem is the dual solution of the
    348     /// maximum bipartite matching. It provides an solution for this
     410    /// maximum bipartite matching. It provides a solution for this
    349411    /// problem what is proof of the optimality of the matching.
    350412    /// \return The size of the cover set.
     
    398460    }
    399461
    400     /// \brief Set true all matching uedge in the map.
    401     ///
    402     /// Set true all matching uedge in the map. It does not change the
    403     /// value mapped to the other uedges.
    404     /// \return The number of the matching edges.
    405     template <typename MatchingMap>
    406     int quickMatching(MatchingMap& mm) const {
    407       for (ANodeIt it(*graph); it != INVALID; ++it) {
    408         if (anode_matching[it] != INVALID) {
    409           mm[anode_matching[it]] = true;
    410         }
    411       }
    412       return matching_size;
    413     }
    414 
    415     /// \brief Set true all matching uedge in the map and the others to false.
    416     ///
    417     /// Set true all matching uedge in the map and the others to false.
    418     /// \return The number of the matching edges.
    419     template <typename MatchingMap>
    420     int matching(MatchingMap& mm) const {
    421       for (UEdgeIt it(*graph); it != INVALID; ++it) {
    422         mm[it] = it == anode_matching[graph->aNode(it)];
    423       }
    424       return matching_size;
    425     }
    426 
    427 
    428     /// \brief Return true if the given uedge is in the matching.
    429     ///
    430     /// It returns true if the given uedge is in the matching.
    431     bool matchingEdge(const UEdge& edge) const {
    432       return anode_matching[graph->aNode(edge)] == edge;
    433     }
    434 
    435     /// \brief Returns the matching edge from the node.
    436     ///
    437     /// Returns the matching edge from the node. If there is not such
    438     /// edge it gives back \c INVALID.
    439     UEdge matchingEdge(const Node& node) const {
    440       if (graph->aNode(node)) {
    441         return anode_matching[node];
    442       } else {
    443         return bnode_matching[node];
    444       }
    445     }
    446 
    447     /// \brief Gives back the number of the matching edges.
    448     ///
    449     /// Gives back the number of the matching edges.
    450     int matchingSize() const {
    451       return matching_size;
     462    /// \brief Gives back a barrier on the A-nodes
     463   
     464    /// The barrier is s subset of the nodes on the same side of the
     465    /// graph, which size minus its neighbours is exactly the
     466    /// unmatched nodes on the A-side. 
     467    /// \retval barrier A WriteMap on the ANodes with bool value.
     468    template <typename BarrierMap>
     469    void aBarrier(BarrierMap& barrier) const {
     470
     471      typename Graph::template ANodeMap<bool> areached(*graph, false);
     472      typename Graph::template BNodeMap<bool> breached(*graph, false);
     473     
     474      std::vector<Node> queue;
     475      for (ANodeIt it(*graph); it != INVALID; ++it) {
     476        if (anode_matching[it] == INVALID) {
     477          queue.push_back(it);
     478        }
     479      }
     480
     481      while (!queue.empty()) {
     482        std::vector<Node> newqueue;
     483        for (int i = 0; i < int(queue.size()); ++i) {
     484          Node anode = queue[i];
     485          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
     486            Node bnode = graph->bNode(jt);
     487            if (breached[bnode]) continue;
     488            breached[bnode] = true;
     489            if (bnode_matching[bnode] != INVALID) {
     490              Node newanode = graph->aNode(bnode_matching[bnode]);
     491              if (!areached[newanode]) {
     492                areached[newanode] = true;
     493                newqueue.push_back(newanode);
     494              }
     495            }
     496          }
     497        }
     498        queue.swap(newqueue);
     499      }
     500
     501      for (ANodeIt it(*graph); it != INVALID; ++it) {
     502        barrier[it] = areached[it] || anode_matching[it] == INVALID;
     503      }
     504    }
     505
     506    /// \brief Gives back a barrier on the B-nodes
     507   
     508    /// The barrier is s subset of the nodes on the same side of the
     509    /// graph, which size minus its neighbours is exactly the
     510    /// unmatched nodes on the B-side. 
     511    /// \retval barrier A WriteMap on the BNodes with bool value.
     512    template <typename BarrierMap>
     513    void bBarrier(BarrierMap& barrier) const {
     514
     515      typename Graph::template ANodeMap<bool> areached(*graph, false);
     516      typename Graph::template BNodeMap<bool> breached(*graph, false);
     517     
     518      std::vector<Node> queue;
     519      for (ANodeIt it(*graph); it != INVALID; ++it) {
     520        if (anode_matching[it] == INVALID) {
     521          queue.push_back(it);
     522        }
     523      }
     524
     525      while (!queue.empty()) {
     526        std::vector<Node> newqueue;
     527        for (int i = 0; i < int(queue.size()); ++i) {
     528          Node anode = queue[i];
     529          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
     530            Node bnode = graph->bNode(jt);
     531            if (breached[bnode]) continue;
     532            breached[bnode] = true;
     533            if (bnode_matching[bnode] != INVALID) {
     534              Node newanode = graph->aNode(bnode_matching[bnode]);
     535              if (!areached[newanode]) {
     536                areached[newanode] = true;
     537                newqueue.push_back(newanode);
     538              }
     539            }
     540          }
     541        }
     542        queue.swap(newqueue);
     543      }
     544
     545      for (BNodeIt it(*graph); it != INVALID; ++it) {
     546        barrier[it] = !breached[it];
     547      }
    452548    }
    453549
  • lemon/pr_bipartite_matching.h

    r2391 r2462  
    1717 */
    1818
    19 #ifndef LEMON_BP_MATCHING
    20 #define LEMON_BP_MATCHING
     19#ifndef LEMON_PR_BIPARTITE_MATCHING
     20#define LEMON_PR_BIPARTITE_MATCHING
    2121
    2222#include <lemon/graph_utils.h>
     
    2424#include <iostream>
    2525#include <queue>
    26 #include <lemon/counter.h>
    2726#include <lemon/elevator.h>
    2827
     
    3130///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
    3231///
    33 ///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h
    34 ///\todo (Re)move the XYZ_TYPEDEFS macros
    3532namespace lemon {
    3633
    37 #define BIPARTITE_TYPEDEFS(Graph)               \
    38   GRAPH_TYPEDEFS(Graph)                         \
    39     typedef Graph::ANodeIt ANodeIt;     \
    40     typedef Graph::BNodeIt BNodeIt;
    41 
    42 #define UNDIRBIPARTITE_TYPEDEFS(Graph)          \
    43   UNDIRGRAPH_TYPEDEFS(Graph)                    \
    44     typedef Graph::ANodeIt ANodeIt;     \
    45     typedef Graph::BNodeIt BNodeIt;
    46 
    47   template<class Graph,
    48            class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >
    49   class BpMatching {
     34  ///Max cardinality matching algorithm based on push-relabel principle
     35
     36  ///\ingroup matching
     37  ///Bipartite Max Cardinality Matching algorithm. This class uses the
     38  ///push-relabel principle which in several cases has better runtime
     39  ///performance than the augmenting path solutions.
     40  ///
     41  ///\author Alpar Juttner
     42  template<class Graph>
     43  class PrBipartiteMatching {
    5044    typedef typename Graph::Node Node;
    5145    typedef typename Graph::ANodeIt ANodeIt;
    5246    typedef typename Graph::BNodeIt BNodeIt;
    5347    typedef typename Graph::UEdge UEdge;
     48    typedef typename Graph::UEdgeIt UEdgeIt;
    5449    typedef typename Graph::IncEdgeIt IncEdgeIt;
    5550   
    5651    const Graph &_g;
    5752    int _node_num;
    58     MT &_matching;
     53    int _matching_size;
     54    int _empty_level;
     55   
     56    typename Graph::template ANodeMap<typename Graph::UEdge> _matching;
    5957    Elevator<Graph,typename Graph::BNode> _levels;
    6058    typename Graph::template BNodeMap<int> _cov;
    6159
    6260  public:
    63     BpMatching(const Graph &g, MT &matching) :
     61
     62    PrBipartiteMatching(const Graph &g) :
    6463      _g(g),
    6564      _node_num(countBNodes(g)),
    66       _matching(matching),
     65      _matching(g),
    6766      _levels(g,_node_num),
    6867      _cov(g,0)
     
    7069    }
    7170   
    72   private:
    73     void init()
    74     {
    75 //     for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;
     71    /// \name Execution control
     72    /// The simplest way to execute the algorithm is to use one of the
     73    /// member functions called \c run(). \n
     74    /// If you need more control on the execution, first
     75    /// you must call \ref init() and then one variant of the start()
     76    /// member.
     77
     78    /// @{
     79
     80    ///Initialize the data structures
     81
     82    ///This function constructs a prematching first, which is a
     83    ///regular matching on the A-side of the graph, but on the B-side
     84    ///each node could cover more matching edges. After that, the
     85    ///B-nodes which multiple matched, will be pushed into the lowest
     86    ///level of the Elevator. The remaning B-nodes will be pushed to
     87    ///the consequent levels respect to a Bfs on following graph: the
     88    ///nodes are the B-nodes of the original bipartite graph and two
     89    ///nodes are adjacent if a node can pass over a matching edge to
     90    ///an other node. The source of the Bfs are the lowest level
     91    ///nodes. Last, the reached B-nodes without covered matching edge
     92    ///becomes active.
     93    void init() {
     94      _matching_size=0;
     95      _empty_level=_node_num;
    7696      for(ANodeIt n(_g);n!=INVALID;++n)
    7797        if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
    78           ++_cov[_g.oppositeNode(n,_matching[n])];
     98          ++_cov[_g.bNode(_matching[n])];
    7999
    80100      std::queue<Node> q;
     
    110130          _levels.activate(n);
    111131    }
    112   public:
    113     int run()
    114     {
    115       init();
    116 
    117       Node act;
    118       Node bact=INVALID;
    119       Node last_activated=INVALID;
    120 //       while((act=last_activated!=INVALID?
    121 //           last_activated:_levels.highestActive())
    122 //          !=INVALID)
    123       while((act=_levels.highestActive())!=INVALID) {
    124         last_activated=INVALID;
    125         int actlevel=_levels[act];
    126        
    127         UEdge bedge=INVALID;
    128         int nlevel=_node_num;
    129         {
    130           int nnlevel;
    131           for(IncEdgeIt tbedge(_g,act);
    132               tbedge!=INVALID && nlevel>=actlevel;
    133               ++tbedge)
    134             if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
    135                nlevel)
    136               {
    137                 nlevel=nnlevel;
    138                 bedge=tbedge;
    139               }
    140         }
    141         if(nlevel<_node_num) {
    142           if(nlevel>=actlevel)
    143             _levels.liftHighestActiveTo(nlevel+1);
    144 //          _levels.liftTo(act,nlevel+1);
    145           bact=_g.bNode(_matching[_g.aNode(bedge)]);
    146           if(--_cov[bact]<1) {
    147             _levels.activate(bact);
    148             last_activated=bact;
    149           }
    150           _matching[_g.aNode(bedge)]=bedge;
    151           _cov[act]=1;
    152           _levels.deactivate(act);
    153         }
    154         else {
    155           if(_node_num>actlevel)
    156             _levels.liftHighestActiveTo(_node_num);
    157 //          _levels.liftTo(act,_node_num);
    158           _levels.deactivate(act);
    159         }
    160 
    161         if(_levels.onLevel(actlevel)==0)
    162           _levels.liftToTop(actlevel);
    163       }
    164      
    165       int ret=_node_num;
    166       for(ANodeIt n(_g);n!=INVALID;++n)
    167         if(_matching[n]==INVALID) ret--;
    168         else if (_cov[_g.bNode(_matching[n])]>1) {
    169           _cov[_g.bNode(_matching[n])]--;
    170           ret--;
    171           _matching[n]=INVALID;
    172         }
    173       return ret;
    174     }
    175    
    176     ///\returns -1 if there is a perfect matching, or an empty level
    177     ///if it doesn't exists
    178     int runPerfect()
    179     {
    180       init();
    181 
     132
     133    ///Start the main phase of the algorithm
     134   
     135    ///This algorithm calculates the maximum matching with the
     136    ///push-relabel principle. This function should be called just
     137    ///after the init() function which already set the initial
     138    ///prematching, the level function on the B-nodes and the active,
     139    ///ie. unmatched B-nodes.
     140    ///
     141    ///The algorithm always takes highest active B-node, and it try to
     142    ///find a B-node which is eligible to pass over one of it's
     143    ///matching edge. This condition holds when the B-node is one
     144    ///level lower, and the opposite node of it's matching edge is
     145    ///adjacent to the highest active node. In this case the current
     146    ///node steals the matching edge and becomes inactive. If there is
     147    ///not eligible node then the highest active node should be lift
     148    ///to the next proper level.
     149    ///
     150    ///The nodes should not lift higher than the number of the
     151    ///B-nodes, if a node reach this level it remains unmatched. If
     152    ///during the execution one level becomes empty the nodes above it
     153    ///can be deactivated and lift to the highest level.
     154    void start() {
    182155      Node act;
    183156      Node bact=INVALID;
     
    220193
    221194        if(_levels.onLevel(actlevel)==0)
    222           return actlevel;
    223       }
    224       return -1;
    225     }
    226  
    227     template<class GT>
    228     void aBarrier(GT &bar,int empty_level=-1)
     195          _levels.liftToTop(actlevel);
     196      }
     197     
     198      _matching_size = _node_num;
     199      for(ANodeIt n(_g);n!=INVALID;++n)
     200        if(_matching[n]==INVALID) _matching_size--;
     201        else if (_cov[_g.bNode(_matching[n])]>1) {
     202          _cov[_g.bNode(_matching[n])]--;
     203          _matching_size--;
     204          _matching[n]=INVALID;
     205        }
     206    }
     207
     208    ///Start the algorithm to find a perfect matching
     209
     210    ///This function is close to identical to the simple start()
     211    ///member function but it calculates just perfect matching.
     212    ///However, the perfect property is only checked on the B-side of
     213    ///the graph
     214    ///
     215    ///The main difference between the two function is the handling of
     216    ///the empty levels. The simple start() function let the nodes
     217    ///above the empty levels unmatched while this variant if it find
     218    ///an empty level immediately terminates and gives back false
     219    ///return value.
     220    bool startPerfect() {
     221      Node act;
     222      Node bact=INVALID;
     223      Node last_activated=INVALID;
     224      while((act=_levels.highestActive())!=INVALID) {
     225        last_activated=INVALID;
     226        int actlevel=_levels[act];
     227       
     228        UEdge bedge=INVALID;
     229        int nlevel=_node_num;
     230        {
     231          int nnlevel;
     232          for(IncEdgeIt tbedge(_g,act);
     233              tbedge!=INVALID && nlevel>=actlevel;
     234              ++tbedge)
     235            if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
     236               nlevel)
     237              {
     238                nlevel=nnlevel;
     239                bedge=tbedge;
     240              }
     241        }
     242        if(nlevel<_node_num) {
     243          if(nlevel>=actlevel)
     244            _levels.liftHighestActiveTo(nlevel+1);
     245          bact=_g.bNode(_matching[_g.aNode(bedge)]);
     246          if(--_cov[bact]<1) {
     247            _levels.activate(bact);
     248            last_activated=bact;
     249          }
     250          _matching[_g.aNode(bedge)]=bedge;
     251          _cov[act]=1;
     252          _levels.deactivate(act);
     253        }
     254        else {
     255          if(_node_num>actlevel)
     256            _levels.liftHighestActiveTo(_node_num);
     257          _levels.deactivate(act);
     258        }
     259
     260        if(_levels.onLevel(actlevel)==0)
     261          _empty_level=actlevel;
     262          return false;
     263      }
     264      return true;
     265    }
     266 
     267    ///Runs the algorithm
     268   
     269    ///Just a shortcut for the next code:
     270    ///\code
     271    /// init();
     272    /// start();
     273    ///\endcode
     274    void run() {
     275      init();
     276      start();
     277    }
     278   
     279    ///Runs the algorithm to find a perfect matching
     280   
     281    ///Just a shortcut for the next code:
     282    ///\code
     283    /// init();
     284    /// startPerfect();
     285    ///\endcode
     286    ///
     287    ///\note If the two nodesets of the graph have different size then
     288    ///this algorithm checks the perfect property on the B-side.
     289    bool runPerfect() {
     290      init();
     291      return startPerfect();
     292    }
     293
     294    ///Runs the algorithm to find a perfect matching
     295   
     296    ///Just a shortcut for the next code:
     297    ///\code
     298    /// init();
     299    /// startPerfect();
     300    ///\endcode
     301    ///
     302    ///\note It checks that the size of the two nodesets are equal.
     303    bool checkedRunPerfect() {
     304      if (countANodes(_g) != _node_num) return false;
     305      init();
     306      return startPerfect();
     307    }
     308
     309    ///@}
     310
     311    /// \name Query Functions
     312    /// The result of the %Matching algorithm can be obtained using these
     313    /// functions.\n
     314    /// Before the use of these functions,
     315    /// either run() or start() must be called.
     316    ///@{
     317
     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.
     323    template <typename MatchingMap>
     324    int quickMatching(MatchingMap& mm) const {
     325      for (ANodeIt n(_g);n!=INVALID;++n) {
     326        if (_matching[n]!=INVALID) mm.set(_matching[n],true);
     327      }
     328      return _matching_size;
     329    }
     330
     331    ///\brief Set true all matching uedge in the map and the others to false.
     332
     333    ///Set true all matching uedge in the map and the others to false.
     334    ///\return The number of the matching edges.
     335    template<class MatchingMap>
     336    int matching(MatchingMap& mm) const {
     337      for (UEdgeIt e(_g);e!=INVALID;++e) {
     338        mm.set(e,e==_matching[_g.aNode(e)]);
     339      }
     340      return _matching_size;
     341    }
     342
     343
     344    ///Returns true if the given uedge is in the matching.
     345
     346    ///It returns true if the given uedge is in the matching.
     347    ///
     348    bool matchingEdge(const UEdge& e) const {
     349      return _matching[_g.aNode(e)]==e;
     350    }
     351
     352    ///Returns the matching edge from the node.
     353
     354    ///Returns the matching edge from the node. If there is not such
     355    ///edge it gives back \c INVALID. 
     356    ///\note If the parameter node is a B-node then the running time is
     357    ///propotional to the degree of the node.
     358    UEdge matchingEdge(const Node& n) const {
     359      if (_g.aNode(n)) {
     360        return _matching[n];
     361      } else {
     362        for (IncEdgeIt e(_g,n);e!=INVALID;++e)
     363          if (e==_matching[_g.aNode(e)]) return e;
     364        return INVALID;
     365      }
     366    }
     367
     368    ///Gives back the number of the matching edges.
     369
     370    ///Gives back the number of the matching edges.
     371    int matchingSize() const {
     372      return _matching_size;
     373    }
     374
     375    ///Gives back a barrier on the A-nodes
     376   
     377    ///The barrier is s subset of the nodes on the same side of the
     378    ///graph. If we tried to find a perfect matching and it failed
     379    ///then the barrier size will be greater than its neighbours. If
     380    ///the maximum matching searched then the barrier size minus its
     381    ///neighbours will be exactly the unmatched nodes on the A-side.
     382    ///\retval bar A WriteMap on the ANodes with bool value.
     383    template<class BarrierMap>
     384    void aBarrier(BarrierMap &bar) const
    229385    {
    230       if(empty_level==-1)
    231         for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
    232386      for(ANodeIt n(_g);n!=INVALID;++n)
    233         bar[n] = _matching[n]==INVALID ||
    234           _levels[_g.bNode(_matching[n])]<empty_level
     387        bar.set(n,_matching[n]==INVALID ||
     388          _levels[_g.bNode(_matching[n])]<_empty_level)
    235389    } 
    236     template<class GT>
    237     void bBarrier(GT &bar, int empty_level=-1)
     390
     391    ///Gives back a barrier on the B-nodes
     392   
     393    ///The barrier is s subset of the nodes on the same side of the
     394    ///graph. If we tried to find a perfect matching and it failed
     395    ///then the barrier size will be greater than its neighbours. If
     396    ///the maximum matching searched then the barrier size minus its
     397    ///neighbours will be exactly the unmatched nodes on the B-side.
     398    ///\retval bar A WriteMap on the BNodes with bool value.
     399    template<class BarrierMap>
     400    void bBarrier(BarrierMap &bar) const
    238401    {
    239       if(empty_level==-1)
    240         for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
    241       for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level); 
    242     } 
    243  
     402      for(BNodeIt n(_g);n!=INVALID;++n) bar.set(n,_levels[n]>=_empty_level); 
     403    }
     404
     405    ///Returns a minimum covering of the nodes.
     406
     407    ///The minimum covering set problem is the dual solution of the
     408    ///maximum bipartite matching. It provides a solution for this
     409    ///problem what is proof of the optimality of the matching.
     410    ///\param covering NodeMap of bool values, the nodes of the cover
     411    ///set will set true while the others false. 
     412    ///\return The size of the cover set.
     413    ///\note This function can be called just after the algorithm have
     414    ///already found a matching.
     415    template<class CoverMap>
     416    int coverSet(CoverMap& covering) const {
     417      int ret=0;
     418      for(BNodeIt n(_g);n!=INVALID;++n) {
     419        if (_levels[n]<_empty_level) { covering.set(n,true); ++ret; }
     420        else covering.set(n,false);
     421      }
     422      for(ANodeIt n(_g);n!=INVALID;++n) {
     423        if (_matching[n]!=INVALID &&
     424            _levels[_g.bNode(_matching[n])]>=_empty_level)
     425          { covering.set(n,true); ++ret; }
     426        else covering.set(n,false);
     427      }
     428      return ret;
     429    }
     430
     431
     432    /// @}
     433   
    244434  };
    245435 
     
    256446  ///on the push-relabel principle.
    257447  template<class Graph>
    258   int maxBpMatching(const Graph &g)
     448  int prBipartiteMatching(const Graph &g)
    259449  {
    260     typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
    261     return maxBpMatching(g,matching);
     450    PrBipartiteMatching<Graph> bpm(g);
     451    return bpm.matchingSize();
    262452  }
    263453
     
    268458  ///in a bipartite graph \c g.
    269459  ///\param g An undirected bipartite graph.
    270   ///\retval matching A readwrite ANodeMap of value type \c Edge.
    271   /// The found edges will be returned in this map,
    272   /// i.e. for an \c ANode \c n,
    273   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
    274   /// \ref INVALID if it is uncovered.
     460  ///\retval matching A write UEdgeMap of value type \c bool.
     461  /// The found edges will be returned in this map.
    275462  ///\return The cardinality of the maximum matching.
    276463  ///
     
    278465  ///on the push-relabel principle.
    279466  template<class Graph,class MT>
    280   int maxBpMatching(const Graph &g,MT &matching)
     467  int prBipartiteMatching(const Graph &g,MT &matching)
    281468  {
    282     return BpMatching<Graph,MT>(g,matching).run();
     469    PrBipartiteMatching<Graph> bpm(g);
     470    bpm.run();
     471    bpm.matching(matching);
     472    return bpm.matchingSize();
    283473  }
    284474
     
    289479  ///in a bipartite graph \c g.
    290480  ///\param g An undirected bipartite graph.
    291   ///\retval matching A readwrite ANodeMap of value type \c Edge.
    292   /// The found edges will be returned in this map,
    293   /// i.e. for an \c ANode \c n,
    294   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
    295   /// \ref INVALID if it is uncovered.
     481  ///\retval matching A write UEdgeMap of value type \c bool.
     482  /// The found edges will be returned in this map.
    296483  ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
    297484  /// exactly once for each BNode. The nodes with \c true value represent
     
    304491  ///on the push-relabel principle.
    305492  template<class Graph,class MT, class GT>
    306   int maxBpMatching(const Graph &g,MT &matching,GT &barrier)
     493  int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
    307494  {
    308     BpMatching<Graph,MT> bpm(g,matching);
    309     int ret=bpm.run();
    310     bpm.barrier(barrier);
    311     return ret;
     495    PrBipartiteMatching<Graph> bpm(g);
     496    bpm.run();
     497    bpm.matching(matching);
     498    bpm.bBarrier(barrier);
     499    return bpm.matchingSize();
    312500  } 
    313501
     
    323511  ///on the push-relabel principle.
    324512  template<class Graph>
    325   bool perfectBpMatching(const Graph &g)
     513  bool prPerfectBipartiteMatching(const Graph &g)
    326514  {
    327     typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
    328     return perfectBpMatching(g,matching);
     515    PrBipartiteMatching<Graph> bpm(g);
     516    return bpm.runPerfect();
    329517  }
    330518
     
    334522  ///This function finds a perfect matching in a bipartite graph \c g.
    335523  ///\param g An undirected bipartite graph.
    336   ///\retval matching A readwrite ANodeMap of value type \c Edge.
    337   /// The found edges will be returned in this map,
    338   /// i.e. for an \c ANode \c n,
    339   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
    340   /// The values are unspecified if the graph
     524  ///\retval matching A write UEdgeMap of value type \c bool.
     525  /// The found edges will be returned in this map.
     526  /// The values are unchanged if the graph
    341527  /// has no perfect matching.
    342528  ///\return \c true iff \c g has a perfect matching.
     
    345531  ///on the push-relabel principle.
    346532  template<class Graph,class MT>
    347   bool perfectBpMatching(const Graph &g,MT &matching)
     533  bool prPerfectBipartiteMatching(const Graph &g,MT &matching)
    348534  {
    349     return BpMatching<Graph,MT>(g,matching).runPerfect()<0;
     535    PrBipartiteMatching<Graph> bpm(g);
     536    bool ret = bpm.runPerfect();
     537    if (ret) bpm.matching(matching);
     538    return ret;
    350539  }
    351540
     
    355544  ///This function finds a perfect matching in a bipartite graph \c g.
    356545  ///\param g An undirected bipartite graph.
    357   ///\retval matching A readwrite ANodeMap of value type \c Edge.
    358   /// The found edges will be returned in this map,
    359   /// i.e. for an \c ANode \c n,
    360   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
    361   /// The values are unspecified if the graph
     546  ///\retval matching A readwrite UEdgeMap of value type \c bool.
     547  /// The found edges will be returned in this map.
     548  /// The values are unchanged if the graph
    362549  /// has no perfect matching.
    363550  ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
     
    365552  /// exactly once for each BNode. The nodes with \c true value represent
    366553  /// a barrier, i.e. a subset \e B a of BNodes with the property that
    367   /// the cardinality of \e B is greater than the numner of its neighbors.
     554  /// the cardinality of \e B is greater than the number of its neighbors.
    368555  ///\return \c true iff \c g has a perfect matching.
    369556  ///
     
    371558  ///on the push-relabel principle.
    372559  template<class Graph,class MT, class GT>
    373   int perfectBpMatching(const Graph &g,MT &matching,GT &barrier)
     560  int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
    374561  {
    375     BpMatching<Graph,MT> bpm(g,matching);
    376     int ret=bpm.run();
    377     if(ret>=0)
    378       bpm.barrier(barrier,ret);
    379     return ret<0;
     562    PrBipartiteMatching<Graph> bpm(g);
     563    bool ret=bpm.runPerfect();
     564    if(ret)
     565      bpm.matching(matching);
     566    else
     567      bpm.bBarrier(barrier);
     568    return ret;
    380569  } 
    381570}
  • test/bipartite_matching_test.cc

    r2391 r2462  
    2525#include <lemon/bpugraph_adaptor.h>
    2626#include <lemon/bipartite_matching.h>
     27#include <lemon/pr_bipartite_matching.h>
    2728
    2829#include <lemon/graph_utils.h>
     
    8990  {
    9091    MaxBipartiteMatching<Graph> bpmatch(graph);
     92
     93    bpmatch.run();
     94
     95    Graph::UEdgeMap<bool> mm(graph);
     96    Graph::NodeMap<bool> cs(graph);
     97   
     98    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
     99   
     100    for (UEdgeIt it(graph); it != INVALID; ++it) {
     101      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
     102    }
     103   
     104    for (ANodeIt it(graph); it != INVALID; ++it) {
     105      int num = 0;
     106      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     107        if (mm[jt]) ++num;
     108      }
     109      check(num <= 1, "INVALID PRIMAL");
     110    }
     111    max_cardinality = bpmatch.matchingSize();
     112  }
     113
     114  {
     115    PrBipartiteMatching<Graph> bpmatch(graph);
    91116
    92117    bpmatch.run();
Note: See TracChangeset for help on using the changeset viewer.