1.1 --- a/lemon/Makefile.am Thu Jul 26 13:59:12 2007 +0000
1.2 +++ b/lemon/Makefile.am Sat Aug 11 16:34:41 2007 +0000
1.3 @@ -39,7 +39,6 @@
1.4 lemon/bfs.h \
1.5 lemon/bin_heap.h \
1.6 lemon/bipartite_matching.h \
1.7 - lemon/bp_matching.h \
1.8 lemon/bpugraph_adaptor.h \
1.9 lemon/bucket_heap.h \
1.10 lemon/capacity_scaling.h \
1.11 @@ -103,6 +102,7 @@
1.12 lemon/polynomial.h \
1.13 lemon/preflow.h \
1.14 lemon/prim.h \
1.15 + lemon/pr_bipartite_matching.h \
1.16 lemon/radix_heap.h \
1.17 lemon/radix_sort.h \
1.18 lemon/random.h \
2.1 --- a/lemon/bipartite_matching.h Thu Jul 26 13:59:12 2007 +0000
2.2 +++ b/lemon/bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000
2.3 @@ -29,6 +29,9 @@
2.4 ///\ingroup matching
2.5 ///\file
2.6 ///\brief Maximum matching algorithms in bipartite graphs.
2.7 +///
2.8 +///\note The pr_bipartite_matching.h file also contains algorithms to
2.9 +///solve maximum cardinality bipartite matching problems.
2.10
2.11 namespace lemon {
2.12
2.13 @@ -39,6 +42,11 @@
2.14 /// Bipartite Max Cardinality Matching algorithm. This class implements
2.15 /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time
2.16 /// complexity.
2.17 + ///
2.18 + /// \note In several cases the push-relabel based algorithms have
2.19 + /// better runtime performance than the augmenting path based ones.
2.20 + ///
2.21 + /// \see PrBipartiteMatching
2.22 template <typename BpUGraph>
2.23 class MaxBipartiteMatching {
2.24 protected:
2.25 @@ -342,10 +350,64 @@
2.26
2.27 ///@{
2.28
2.29 - /// \brief Returns an minimum covering of the nodes.
2.30 + /// \brief Set true all matching uedge in the map.
2.31 + ///
2.32 + /// Set true all matching uedge in the map. It does not change the
2.33 + /// value mapped to the other uedges.
2.34 + /// \return The number of the matching edges.
2.35 + template <typename MatchingMap>
2.36 + int quickMatching(MatchingMap& mm) const {
2.37 + for (ANodeIt it(*graph); it != INVALID; ++it) {
2.38 + if (anode_matching[it] != INVALID) {
2.39 + mm[anode_matching[it]] = true;
2.40 + }
2.41 + }
2.42 + return matching_size;
2.43 + }
2.44 +
2.45 + /// \brief Set true all matching uedge in the map and the others to false.
2.46 + ///
2.47 + /// Set true all matching uedge in the map and the others to false.
2.48 + /// \return The number of the matching edges.
2.49 + template <typename MatchingMap>
2.50 + int matching(MatchingMap& mm) const {
2.51 + for (UEdgeIt it(*graph); it != INVALID; ++it) {
2.52 + mm[it] = it == anode_matching[graph->aNode(it)];
2.53 + }
2.54 + return matching_size;
2.55 + }
2.56 +
2.57 +
2.58 + /// \brief Return true if the given uedge is in the matching.
2.59 + ///
2.60 + /// It returns true if the given uedge is in the matching.
2.61 + bool matchingEdge(const UEdge& edge) const {
2.62 + return anode_matching[graph->aNode(edge)] == edge;
2.63 + }
2.64 +
2.65 + /// \brief Returns the matching edge from the node.
2.66 + ///
2.67 + /// Returns the matching edge from the node. If there is not such
2.68 + /// edge it gives back \c INVALID.
2.69 + UEdge matchingEdge(const Node& node) const {
2.70 + if (graph->aNode(node)) {
2.71 + return anode_matching[node];
2.72 + } else {
2.73 + return bnode_matching[node];
2.74 + }
2.75 + }
2.76 +
2.77 + /// \brief Gives back the number of the matching edges.
2.78 + ///
2.79 + /// Gives back the number of the matching edges.
2.80 + int matchingSize() const {
2.81 + return matching_size;
2.82 + }
2.83 +
2.84 + /// \brief Returns a minimum covering of the nodes.
2.85 ///
2.86 /// The minimum covering set problem is the dual solution of the
2.87 - /// maximum bipartite matching. It provides an solution for this
2.88 + /// maximum bipartite matching. It provides a solution for this
2.89 /// problem what is proof of the optimality of the matching.
2.90 /// \return The size of the cover set.
2.91 template <typename CoverMap>
2.92 @@ -397,58 +459,92 @@
2.93 return size;
2.94 }
2.95
2.96 - /// \brief Set true all matching uedge in the map.
2.97 - ///
2.98 - /// Set true all matching uedge in the map. It does not change the
2.99 - /// value mapped to the other uedges.
2.100 - /// \return The number of the matching edges.
2.101 - template <typename MatchingMap>
2.102 - int quickMatching(MatchingMap& mm) const {
2.103 + /// \brief Gives back a barrier on the A-nodes
2.104 +
2.105 + /// The barrier is s subset of the nodes on the same side of the
2.106 + /// graph, which size minus its neighbours is exactly the
2.107 + /// unmatched nodes on the A-side.
2.108 + /// \retval barrier A WriteMap on the ANodes with bool value.
2.109 + template <typename BarrierMap>
2.110 + void aBarrier(BarrierMap& barrier) const {
2.111 +
2.112 + typename Graph::template ANodeMap<bool> areached(*graph, false);
2.113 + typename Graph::template BNodeMap<bool> breached(*graph, false);
2.114 +
2.115 + std::vector<Node> queue;
2.116 for (ANodeIt it(*graph); it != INVALID; ++it) {
2.117 - if (anode_matching[it] != INVALID) {
2.118 - mm[anode_matching[it]] = true;
2.119 + if (anode_matching[it] == INVALID) {
2.120 + queue.push_back(it);
2.121 }
2.122 }
2.123 - return matching_size;
2.124 - }
2.125
2.126 - /// \brief Set true all matching uedge in the map and the others to false.
2.127 - ///
2.128 - /// Set true all matching uedge in the map and the others to false.
2.129 - /// \return The number of the matching edges.
2.130 - template <typename MatchingMap>
2.131 - int matching(MatchingMap& mm) const {
2.132 - for (UEdgeIt it(*graph); it != INVALID; ++it) {
2.133 - mm[it] = it == anode_matching[graph->aNode(it)];
2.134 + while (!queue.empty()) {
2.135 + std::vector<Node> newqueue;
2.136 + for (int i = 0; i < int(queue.size()); ++i) {
2.137 + Node anode = queue[i];
2.138 + for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
2.139 + Node bnode = graph->bNode(jt);
2.140 + if (breached[bnode]) continue;
2.141 + breached[bnode] = true;
2.142 + if (bnode_matching[bnode] != INVALID) {
2.143 + Node newanode = graph->aNode(bnode_matching[bnode]);
2.144 + if (!areached[newanode]) {
2.145 + areached[newanode] = true;
2.146 + newqueue.push_back(newanode);
2.147 + }
2.148 + }
2.149 + }
2.150 + }
2.151 + queue.swap(newqueue);
2.152 }
2.153 - return matching_size;
2.154 - }
2.155
2.156 -
2.157 - /// \brief Return true if the given uedge is in the matching.
2.158 - ///
2.159 - /// It returns true if the given uedge is in the matching.
2.160 - bool matchingEdge(const UEdge& edge) const {
2.161 - return anode_matching[graph->aNode(edge)] == edge;
2.162 - }
2.163 -
2.164 - /// \brief Returns the matching edge from the node.
2.165 - ///
2.166 - /// Returns the matching edge from the node. If there is not such
2.167 - /// edge it gives back \c INVALID.
2.168 - UEdge matchingEdge(const Node& node) const {
2.169 - if (graph->aNode(node)) {
2.170 - return anode_matching[node];
2.171 - } else {
2.172 - return bnode_matching[node];
2.173 + for (ANodeIt it(*graph); it != INVALID; ++it) {
2.174 + barrier[it] = areached[it] || anode_matching[it] == INVALID;
2.175 }
2.176 }
2.177
2.178 - /// \brief Gives back the number of the matching edges.
2.179 - ///
2.180 - /// Gives back the number of the matching edges.
2.181 - int matchingSize() const {
2.182 - return matching_size;
2.183 + /// \brief Gives back a barrier on the B-nodes
2.184 +
2.185 + /// The barrier is s subset of the nodes on the same side of the
2.186 + /// graph, which size minus its neighbours is exactly the
2.187 + /// unmatched nodes on the B-side.
2.188 + /// \retval barrier A WriteMap on the BNodes with bool value.
2.189 + template <typename BarrierMap>
2.190 + void bBarrier(BarrierMap& barrier) const {
2.191 +
2.192 + typename Graph::template ANodeMap<bool> areached(*graph, false);
2.193 + typename Graph::template BNodeMap<bool> breached(*graph, false);
2.194 +
2.195 + std::vector<Node> queue;
2.196 + for (ANodeIt it(*graph); it != INVALID; ++it) {
2.197 + if (anode_matching[it] == INVALID) {
2.198 + queue.push_back(it);
2.199 + }
2.200 + }
2.201 +
2.202 + while (!queue.empty()) {
2.203 + std::vector<Node> newqueue;
2.204 + for (int i = 0; i < int(queue.size()); ++i) {
2.205 + Node anode = queue[i];
2.206 + for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
2.207 + Node bnode = graph->bNode(jt);
2.208 + if (breached[bnode]) continue;
2.209 + breached[bnode] = true;
2.210 + if (bnode_matching[bnode] != INVALID) {
2.211 + Node newanode = graph->aNode(bnode_matching[bnode]);
2.212 + if (!areached[newanode]) {
2.213 + areached[newanode] = true;
2.214 + newqueue.push_back(newanode);
2.215 + }
2.216 + }
2.217 + }
2.218 + }
2.219 + queue.swap(newqueue);
2.220 + }
2.221 +
2.222 + for (BNodeIt it(*graph); it != INVALID; ++it) {
2.223 + barrier[it] = !breached[it];
2.224 + }
2.225 }
2.226
2.227 /// @}
3.1 --- a/lemon/bp_matching.h Thu Jul 26 13:59:12 2007 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,383 +0,0 @@
3.4 -/* -*- C++ -*-
3.5 - *
3.6 - * This file is a part of LEMON, a generic C++ optimization library
3.7 - *
3.8 - * Copyright (C) 2003-2007
3.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 - *
3.12 - * Permission to use, modify and distribute this software is granted
3.13 - * provided that this copyright notice appears in all copies. For
3.14 - * precise terms see the accompanying LICENSE file.
3.15 - *
3.16 - * This software is provided "AS IS" with no warranty of any kind,
3.17 - * express or implied, and with no claim as to its suitability for any
3.18 - * purpose.
3.19 - *
3.20 - */
3.21 -
3.22 -#ifndef LEMON_BP_MATCHING
3.23 -#define LEMON_BP_MATCHING
3.24 -
3.25 -#include <lemon/graph_utils.h>
3.26 -#include <lemon/iterable_maps.h>
3.27 -#include <iostream>
3.28 -#include <queue>
3.29 -#include <lemon/counter.h>
3.30 -#include <lemon/elevator.h>
3.31 -
3.32 -///\ingroup matching
3.33 -///\file
3.34 -///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
3.35 -///
3.36 -///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h
3.37 -///\todo (Re)move the XYZ_TYPEDEFS macros
3.38 -namespace lemon {
3.39 -
3.40 -#define BIPARTITE_TYPEDEFS(Graph) \
3.41 - GRAPH_TYPEDEFS(Graph) \
3.42 - typedef Graph::ANodeIt ANodeIt; \
3.43 - typedef Graph::BNodeIt BNodeIt;
3.44 -
3.45 -#define UNDIRBIPARTITE_TYPEDEFS(Graph) \
3.46 - UNDIRGRAPH_TYPEDEFS(Graph) \
3.47 - typedef Graph::ANodeIt ANodeIt; \
3.48 - typedef Graph::BNodeIt BNodeIt;
3.49 -
3.50 - template<class Graph,
3.51 - class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >
3.52 - class BpMatching {
3.53 - typedef typename Graph::Node Node;
3.54 - typedef typename Graph::ANodeIt ANodeIt;
3.55 - typedef typename Graph::BNodeIt BNodeIt;
3.56 - typedef typename Graph::UEdge UEdge;
3.57 - typedef typename Graph::IncEdgeIt IncEdgeIt;
3.58 -
3.59 - const Graph &_g;
3.60 - int _node_num;
3.61 - MT &_matching;
3.62 - Elevator<Graph,typename Graph::BNode> _levels;
3.63 - typename Graph::template BNodeMap<int> _cov;
3.64 -
3.65 - public:
3.66 - BpMatching(const Graph &g, MT &matching) :
3.67 - _g(g),
3.68 - _node_num(countBNodes(g)),
3.69 - _matching(matching),
3.70 - _levels(g,_node_num),
3.71 - _cov(g,0)
3.72 - {
3.73 - }
3.74 -
3.75 - private:
3.76 - void init()
3.77 - {
3.78 -// for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;
3.79 - for(ANodeIt n(_g);n!=INVALID;++n)
3.80 - if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
3.81 - ++_cov[_g.oppositeNode(n,_matching[n])];
3.82 -
3.83 - std::queue<Node> q;
3.84 - _levels.initStart();
3.85 - for(BNodeIt n(_g);n!=INVALID;++n)
3.86 - if(_cov[n]>1) {
3.87 - _levels.initAddItem(n);
3.88 - q.push(n);
3.89 - }
3.90 - int hlev=0;
3.91 - while(!q.empty()) {
3.92 - Node n=q.front();
3.93 - q.pop();
3.94 - int nlev=_levels[n]+1;
3.95 - for(IncEdgeIt e(_g,n);e!=INVALID;++e) {
3.96 - Node m=_g.runningNode(e);
3.97 - if(e==_matching[m]) {
3.98 - for(IncEdgeIt f(_g,m);f!=INVALID;++f) {
3.99 - Node r=_g.runningNode(f);
3.100 - if(_levels[r]>nlev) {
3.101 - for(;nlev>hlev;hlev++)
3.102 - _levels.initNewLevel();
3.103 - _levels.initAddItem(r);
3.104 - q.push(r);
3.105 - }
3.106 - }
3.107 - }
3.108 - }
3.109 - }
3.110 - _levels.initFinish();
3.111 - for(BNodeIt n(_g);n!=INVALID;++n)
3.112 - if(_cov[n]<1&&_levels[n]<_node_num)
3.113 - _levels.activate(n);
3.114 - }
3.115 - public:
3.116 - int run()
3.117 - {
3.118 - init();
3.119 -
3.120 - Node act;
3.121 - Node bact=INVALID;
3.122 - Node last_activated=INVALID;
3.123 -// while((act=last_activated!=INVALID?
3.124 -// last_activated:_levels.highestActive())
3.125 -// !=INVALID)
3.126 - while((act=_levels.highestActive())!=INVALID) {
3.127 - last_activated=INVALID;
3.128 - int actlevel=_levels[act];
3.129 -
3.130 - UEdge bedge=INVALID;
3.131 - int nlevel=_node_num;
3.132 - {
3.133 - int nnlevel;
3.134 - for(IncEdgeIt tbedge(_g,act);
3.135 - tbedge!=INVALID && nlevel>=actlevel;
3.136 - ++tbedge)
3.137 - if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
3.138 - nlevel)
3.139 - {
3.140 - nlevel=nnlevel;
3.141 - bedge=tbedge;
3.142 - }
3.143 - }
3.144 - if(nlevel<_node_num) {
3.145 - if(nlevel>=actlevel)
3.146 - _levels.liftHighestActiveTo(nlevel+1);
3.147 -// _levels.liftTo(act,nlevel+1);
3.148 - bact=_g.bNode(_matching[_g.aNode(bedge)]);
3.149 - if(--_cov[bact]<1) {
3.150 - _levels.activate(bact);
3.151 - last_activated=bact;
3.152 - }
3.153 - _matching[_g.aNode(bedge)]=bedge;
3.154 - _cov[act]=1;
3.155 - _levels.deactivate(act);
3.156 - }
3.157 - else {
3.158 - if(_node_num>actlevel)
3.159 - _levels.liftHighestActiveTo(_node_num);
3.160 -// _levels.liftTo(act,_node_num);
3.161 - _levels.deactivate(act);
3.162 - }
3.163 -
3.164 - if(_levels.onLevel(actlevel)==0)
3.165 - _levels.liftToTop(actlevel);
3.166 - }
3.167 -
3.168 - int ret=_node_num;
3.169 - for(ANodeIt n(_g);n!=INVALID;++n)
3.170 - if(_matching[n]==INVALID) ret--;
3.171 - else if (_cov[_g.bNode(_matching[n])]>1) {
3.172 - _cov[_g.bNode(_matching[n])]--;
3.173 - ret--;
3.174 - _matching[n]=INVALID;
3.175 - }
3.176 - return ret;
3.177 - }
3.178 -
3.179 - ///\returns -1 if there is a perfect matching, or an empty level
3.180 - ///if it doesn't exists
3.181 - int runPerfect()
3.182 - {
3.183 - init();
3.184 -
3.185 - Node act;
3.186 - Node bact=INVALID;
3.187 - Node last_activated=INVALID;
3.188 - while((act=_levels.highestActive())!=INVALID) {
3.189 - last_activated=INVALID;
3.190 - int actlevel=_levels[act];
3.191 -
3.192 - UEdge bedge=INVALID;
3.193 - int nlevel=_node_num;
3.194 - {
3.195 - int nnlevel;
3.196 - for(IncEdgeIt tbedge(_g,act);
3.197 - tbedge!=INVALID && nlevel>=actlevel;
3.198 - ++tbedge)
3.199 - if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
3.200 - nlevel)
3.201 - {
3.202 - nlevel=nnlevel;
3.203 - bedge=tbedge;
3.204 - }
3.205 - }
3.206 - if(nlevel<_node_num) {
3.207 - if(nlevel>=actlevel)
3.208 - _levels.liftHighestActiveTo(nlevel+1);
3.209 - bact=_g.bNode(_matching[_g.aNode(bedge)]);
3.210 - if(--_cov[bact]<1) {
3.211 - _levels.activate(bact);
3.212 - last_activated=bact;
3.213 - }
3.214 - _matching[_g.aNode(bedge)]=bedge;
3.215 - _cov[act]=1;
3.216 - _levels.deactivate(act);
3.217 - }
3.218 - else {
3.219 - if(_node_num>actlevel)
3.220 - _levels.liftHighestActiveTo(_node_num);
3.221 - _levels.deactivate(act);
3.222 - }
3.223 -
3.224 - if(_levels.onLevel(actlevel)==0)
3.225 - return actlevel;
3.226 - }
3.227 - return -1;
3.228 - }
3.229 -
3.230 - template<class GT>
3.231 - void aBarrier(GT &bar,int empty_level=-1)
3.232 - {
3.233 - if(empty_level==-1)
3.234 - for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
3.235 - for(ANodeIt n(_g);n!=INVALID;++n)
3.236 - bar[n] = _matching[n]==INVALID ||
3.237 - _levels[_g.bNode(_matching[n])]<empty_level;
3.238 - }
3.239 - template<class GT>
3.240 - void bBarrier(GT &bar, int empty_level=-1)
3.241 - {
3.242 - if(empty_level==-1)
3.243 - for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
3.244 - for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level);
3.245 - }
3.246 -
3.247 - };
3.248 -
3.249 -
3.250 - ///Maximum cardinality of the matchings in a bipartite graph
3.251 -
3.252 - ///\ingroup matching
3.253 - ///This function finds the maximum cardinality of the matchings
3.254 - ///in a bipartite graph \c g.
3.255 - ///\param g An undirected bipartite graph.
3.256 - ///\return The cardinality of the maximum matching.
3.257 - ///
3.258 - ///\note The the implementation is based
3.259 - ///on the push-relabel principle.
3.260 - template<class Graph>
3.261 - int maxBpMatching(const Graph &g)
3.262 - {
3.263 - typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
3.264 - return maxBpMatching(g,matching);
3.265 - }
3.266 -
3.267 - ///Maximum cardinality matching in a bipartite graph
3.268 -
3.269 - ///\ingroup matching
3.270 - ///This function finds a maximum cardinality matching
3.271 - ///in a bipartite graph \c g.
3.272 - ///\param g An undirected bipartite graph.
3.273 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
3.274 - /// The found edges will be returned in this map,
3.275 - /// i.e. for an \c ANode \c n,
3.276 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
3.277 - /// \ref INVALID if it is uncovered.
3.278 - ///\return The cardinality of the maximum matching.
3.279 - ///
3.280 - ///\note The the implementation is based
3.281 - ///on the push-relabel principle.
3.282 - template<class Graph,class MT>
3.283 - int maxBpMatching(const Graph &g,MT &matching)
3.284 - {
3.285 - return BpMatching<Graph,MT>(g,matching).run();
3.286 - }
3.287 -
3.288 - ///Maximum cardinality matching in a bipartite graph
3.289 -
3.290 - ///\ingroup matching
3.291 - ///This function finds a maximum cardinality matching
3.292 - ///in a bipartite graph \c g.
3.293 - ///\param g An undirected bipartite graph.
3.294 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
3.295 - /// The found edges will be returned in this map,
3.296 - /// i.e. for an \c ANode \c n,
3.297 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
3.298 - /// \ref INVALID if it is uncovered.
3.299 - ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
3.300 - /// exactly once for each BNode. The nodes with \c true value represent
3.301 - /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
3.302 - /// neighbor is equal to the number of the <tt>BNode</tt>s minus the
3.303 - /// cardinality of the maximum matching.
3.304 - ///\return The cardinality of the maximum matching.
3.305 - ///
3.306 - ///\note The the implementation is based
3.307 - ///on the push-relabel principle.
3.308 - template<class Graph,class MT, class GT>
3.309 - int maxBpMatching(const Graph &g,MT &matching,GT &barrier)
3.310 - {
3.311 - BpMatching<Graph,MT> bpm(g,matching);
3.312 - int ret=bpm.run();
3.313 - bpm.barrier(barrier);
3.314 - return ret;
3.315 - }
3.316 -
3.317 - ///Perfect matching in a bipartite graph
3.318 -
3.319 - ///\ingroup matching
3.320 - ///This function checks whether the bipartite graph \c g
3.321 - ///has a perfect matching.
3.322 - ///\param g An undirected bipartite graph.
3.323 - ///\return \c true iff \c g has a perfect matching.
3.324 - ///
3.325 - ///\note The the implementation is based
3.326 - ///on the push-relabel principle.
3.327 - template<class Graph>
3.328 - bool perfectBpMatching(const Graph &g)
3.329 - {
3.330 - typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
3.331 - return perfectBpMatching(g,matching);
3.332 - }
3.333 -
3.334 - ///Perfect matching in a bipartite graph
3.335 -
3.336 - ///\ingroup matching
3.337 - ///This function finds a perfect matching in a bipartite graph \c g.
3.338 - ///\param g An undirected bipartite graph.
3.339 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
3.340 - /// The found edges will be returned in this map,
3.341 - /// i.e. for an \c ANode \c n,
3.342 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
3.343 - /// The values are unspecified if the graph
3.344 - /// has no perfect matching.
3.345 - ///\return \c true iff \c g has a perfect matching.
3.346 - ///
3.347 - ///\note The the implementation is based
3.348 - ///on the push-relabel principle.
3.349 - template<class Graph,class MT>
3.350 - bool perfectBpMatching(const Graph &g,MT &matching)
3.351 - {
3.352 - return BpMatching<Graph,MT>(g,matching).runPerfect()<0;
3.353 - }
3.354 -
3.355 - ///Perfect matching in a bipartite graph
3.356 -
3.357 - ///\ingroup matching
3.358 - ///This function finds a perfect matching in a bipartite graph \c g.
3.359 - ///\param g An undirected bipartite graph.
3.360 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
3.361 - /// The found edges will be returned in this map,
3.362 - /// i.e. for an \c ANode \c n,
3.363 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
3.364 - /// The values are unspecified if the graph
3.365 - /// has no perfect matching.
3.366 - ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
3.367 - /// be set if \c g has no perfect matching. In this case it is set
3.368 - /// exactly once for each BNode. The nodes with \c true value represent
3.369 - /// a barrier, i.e. a subset \e B a of BNodes with the property that
3.370 - /// the cardinality of \e B is greater than the numner of its neighbors.
3.371 - ///\return \c true iff \c g has a perfect matching.
3.372 - ///
3.373 - ///\note The the implementation is based
3.374 - ///on the push-relabel principle.
3.375 - template<class Graph,class MT, class GT>
3.376 - int perfectBpMatching(const Graph &g,MT &matching,GT &barrier)
3.377 - {
3.378 - BpMatching<Graph,MT> bpm(g,matching);
3.379 - int ret=bpm.run();
3.380 - if(ret>=0)
3.381 - bpm.barrier(barrier,ret);
3.382 - return ret<0;
3.383 - }
3.384 -}
3.385 -
3.386 -#endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/pr_bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000
4.3 @@ -0,0 +1,572 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2007
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_PR_BIPARTITE_MATCHING
4.23 +#define LEMON_PR_BIPARTITE_MATCHING
4.24 +
4.25 +#include <lemon/graph_utils.h>
4.26 +#include <lemon/iterable_maps.h>
4.27 +#include <iostream>
4.28 +#include <queue>
4.29 +#include <lemon/elevator.h>
4.30 +
4.31 +///\ingroup matching
4.32 +///\file
4.33 +///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
4.34 +///
4.35 +namespace lemon {
4.36 +
4.37 + ///Max cardinality matching algorithm based on push-relabel principle
4.38 +
4.39 + ///\ingroup matching
4.40 + ///Bipartite Max Cardinality Matching algorithm. This class uses the
4.41 + ///push-relabel principle which in several cases has better runtime
4.42 + ///performance than the augmenting path solutions.
4.43 + ///
4.44 + ///\author Alpar Juttner
4.45 + template<class Graph>
4.46 + class PrBipartiteMatching {
4.47 + typedef typename Graph::Node Node;
4.48 + typedef typename Graph::ANodeIt ANodeIt;
4.49 + typedef typename Graph::BNodeIt BNodeIt;
4.50 + typedef typename Graph::UEdge UEdge;
4.51 + typedef typename Graph::UEdgeIt UEdgeIt;
4.52 + typedef typename Graph::IncEdgeIt IncEdgeIt;
4.53 +
4.54 + const Graph &_g;
4.55 + int _node_num;
4.56 + int _matching_size;
4.57 + int _empty_level;
4.58 +
4.59 + typename Graph::template ANodeMap<typename Graph::UEdge> _matching;
4.60 + Elevator<Graph,typename Graph::BNode> _levels;
4.61 + typename Graph::template BNodeMap<int> _cov;
4.62 +
4.63 + public:
4.64 +
4.65 + PrBipartiteMatching(const Graph &g) :
4.66 + _g(g),
4.67 + _node_num(countBNodes(g)),
4.68 + _matching(g),
4.69 + _levels(g,_node_num),
4.70 + _cov(g,0)
4.71 + {
4.72 + }
4.73 +
4.74 + /// \name Execution control
4.75 + /// The simplest way to execute the algorithm is to use one of the
4.76 + /// member functions called \c run(). \n
4.77 + /// If you need more control on the execution, first
4.78 + /// you must call \ref init() and then one variant of the start()
4.79 + /// member.
4.80 +
4.81 + /// @{
4.82 +
4.83 + ///Initialize the data structures
4.84 +
4.85 + ///This function constructs a prematching first, which is a
4.86 + ///regular matching on the A-side of the graph, but on the B-side
4.87 + ///each node could cover more matching edges. After that, the
4.88 + ///B-nodes which multiple matched, will be pushed into the lowest
4.89 + ///level of the Elevator. The remaning B-nodes will be pushed to
4.90 + ///the consequent levels respect to a Bfs on following graph: the
4.91 + ///nodes are the B-nodes of the original bipartite graph and two
4.92 + ///nodes are adjacent if a node can pass over a matching edge to
4.93 + ///an other node. The source of the Bfs are the lowest level
4.94 + ///nodes. Last, the reached B-nodes without covered matching edge
4.95 + ///becomes active.
4.96 + void init() {
4.97 + _matching_size=0;
4.98 + _empty_level=_node_num;
4.99 + for(ANodeIt n(_g);n!=INVALID;++n)
4.100 + if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
4.101 + ++_cov[_g.bNode(_matching[n])];
4.102 +
4.103 + std::queue<Node> q;
4.104 + _levels.initStart();
4.105 + for(BNodeIt n(_g);n!=INVALID;++n)
4.106 + if(_cov[n]>1) {
4.107 + _levels.initAddItem(n);
4.108 + q.push(n);
4.109 + }
4.110 + int hlev=0;
4.111 + while(!q.empty()) {
4.112 + Node n=q.front();
4.113 + q.pop();
4.114 + int nlev=_levels[n]+1;
4.115 + for(IncEdgeIt e(_g,n);e!=INVALID;++e) {
4.116 + Node m=_g.runningNode(e);
4.117 + if(e==_matching[m]) {
4.118 + for(IncEdgeIt f(_g,m);f!=INVALID;++f) {
4.119 + Node r=_g.runningNode(f);
4.120 + if(_levels[r]>nlev) {
4.121 + for(;nlev>hlev;hlev++)
4.122 + _levels.initNewLevel();
4.123 + _levels.initAddItem(r);
4.124 + q.push(r);
4.125 + }
4.126 + }
4.127 + }
4.128 + }
4.129 + }
4.130 + _levels.initFinish();
4.131 + for(BNodeIt n(_g);n!=INVALID;++n)
4.132 + if(_cov[n]<1&&_levels[n]<_node_num)
4.133 + _levels.activate(n);
4.134 + }
4.135 +
4.136 + ///Start the main phase of the algorithm
4.137 +
4.138 + ///This algorithm calculates the maximum matching with the
4.139 + ///push-relabel principle. This function should be called just
4.140 + ///after the init() function which already set the initial
4.141 + ///prematching, the level function on the B-nodes and the active,
4.142 + ///ie. unmatched B-nodes.
4.143 + ///
4.144 + ///The algorithm always takes highest active B-node, and it try to
4.145 + ///find a B-node which is eligible to pass over one of it's
4.146 + ///matching edge. This condition holds when the B-node is one
4.147 + ///level lower, and the opposite node of it's matching edge is
4.148 + ///adjacent to the highest active node. In this case the current
4.149 + ///node steals the matching edge and becomes inactive. If there is
4.150 + ///not eligible node then the highest active node should be lift
4.151 + ///to the next proper level.
4.152 + ///
4.153 + ///The nodes should not lift higher than the number of the
4.154 + ///B-nodes, if a node reach this level it remains unmatched. If
4.155 + ///during the execution one level becomes empty the nodes above it
4.156 + ///can be deactivated and lift to the highest level.
4.157 + void start() {
4.158 + Node act;
4.159 + Node bact=INVALID;
4.160 + Node last_activated=INVALID;
4.161 + while((act=_levels.highestActive())!=INVALID) {
4.162 + last_activated=INVALID;
4.163 + int actlevel=_levels[act];
4.164 +
4.165 + UEdge bedge=INVALID;
4.166 + int nlevel=_node_num;
4.167 + {
4.168 + int nnlevel;
4.169 + for(IncEdgeIt tbedge(_g,act);
4.170 + tbedge!=INVALID && nlevel>=actlevel;
4.171 + ++tbedge)
4.172 + if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
4.173 + nlevel)
4.174 + {
4.175 + nlevel=nnlevel;
4.176 + bedge=tbedge;
4.177 + }
4.178 + }
4.179 + if(nlevel<_node_num) {
4.180 + if(nlevel>=actlevel)
4.181 + _levels.liftHighestActiveTo(nlevel+1);
4.182 + bact=_g.bNode(_matching[_g.aNode(bedge)]);
4.183 + if(--_cov[bact]<1) {
4.184 + _levels.activate(bact);
4.185 + last_activated=bact;
4.186 + }
4.187 + _matching[_g.aNode(bedge)]=bedge;
4.188 + _cov[act]=1;
4.189 + _levels.deactivate(act);
4.190 + }
4.191 + else {
4.192 + if(_node_num>actlevel)
4.193 + _levels.liftHighestActiveTo(_node_num);
4.194 + _levels.deactivate(act);
4.195 + }
4.196 +
4.197 + if(_levels.onLevel(actlevel)==0)
4.198 + _levels.liftToTop(actlevel);
4.199 + }
4.200 +
4.201 + _matching_size = _node_num;
4.202 + for(ANodeIt n(_g);n!=INVALID;++n)
4.203 + if(_matching[n]==INVALID) _matching_size--;
4.204 + else if (_cov[_g.bNode(_matching[n])]>1) {
4.205 + _cov[_g.bNode(_matching[n])]--;
4.206 + _matching_size--;
4.207 + _matching[n]=INVALID;
4.208 + }
4.209 + }
4.210 +
4.211 + ///Start the algorithm to find a perfect matching
4.212 +
4.213 + ///This function is close to identical to the simple start()
4.214 + ///member function but it calculates just perfect matching.
4.215 + ///However, the perfect property is only checked on the B-side of
4.216 + ///the graph
4.217 + ///
4.218 + ///The main difference between the two function is the handling of
4.219 + ///the empty levels. The simple start() function let the nodes
4.220 + ///above the empty levels unmatched while this variant if it find
4.221 + ///an empty level immediately terminates and gives back false
4.222 + ///return value.
4.223 + bool startPerfect() {
4.224 + Node act;
4.225 + Node bact=INVALID;
4.226 + Node last_activated=INVALID;
4.227 + while((act=_levels.highestActive())!=INVALID) {
4.228 + last_activated=INVALID;
4.229 + int actlevel=_levels[act];
4.230 +
4.231 + UEdge bedge=INVALID;
4.232 + int nlevel=_node_num;
4.233 + {
4.234 + int nnlevel;
4.235 + for(IncEdgeIt tbedge(_g,act);
4.236 + tbedge!=INVALID && nlevel>=actlevel;
4.237 + ++tbedge)
4.238 + if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
4.239 + nlevel)
4.240 + {
4.241 + nlevel=nnlevel;
4.242 + bedge=tbedge;
4.243 + }
4.244 + }
4.245 + if(nlevel<_node_num) {
4.246 + if(nlevel>=actlevel)
4.247 + _levels.liftHighestActiveTo(nlevel+1);
4.248 + bact=_g.bNode(_matching[_g.aNode(bedge)]);
4.249 + if(--_cov[bact]<1) {
4.250 + _levels.activate(bact);
4.251 + last_activated=bact;
4.252 + }
4.253 + _matching[_g.aNode(bedge)]=bedge;
4.254 + _cov[act]=1;
4.255 + _levels.deactivate(act);
4.256 + }
4.257 + else {
4.258 + if(_node_num>actlevel)
4.259 + _levels.liftHighestActiveTo(_node_num);
4.260 + _levels.deactivate(act);
4.261 + }
4.262 +
4.263 + if(_levels.onLevel(actlevel)==0)
4.264 + _empty_level=actlevel;
4.265 + return false;
4.266 + }
4.267 + return true;
4.268 + }
4.269 +
4.270 + ///Runs the algorithm
4.271 +
4.272 + ///Just a shortcut for the next code:
4.273 + ///\code
4.274 + /// init();
4.275 + /// start();
4.276 + ///\endcode
4.277 + void run() {
4.278 + init();
4.279 + start();
4.280 + }
4.281 +
4.282 + ///Runs the algorithm to find a perfect matching
4.283 +
4.284 + ///Just a shortcut for the next code:
4.285 + ///\code
4.286 + /// init();
4.287 + /// startPerfect();
4.288 + ///\endcode
4.289 + ///
4.290 + ///\note If the two nodesets of the graph have different size then
4.291 + ///this algorithm checks the perfect property on the B-side.
4.292 + bool runPerfect() {
4.293 + init();
4.294 + return startPerfect();
4.295 + }
4.296 +
4.297 + ///Runs the algorithm to find a perfect matching
4.298 +
4.299 + ///Just a shortcut for the next code:
4.300 + ///\code
4.301 + /// init();
4.302 + /// startPerfect();
4.303 + ///\endcode
4.304 + ///
4.305 + ///\note It checks that the size of the two nodesets are equal.
4.306 + bool checkedRunPerfect() {
4.307 + if (countANodes(_g) != _node_num) return false;
4.308 + init();
4.309 + return startPerfect();
4.310 + }
4.311 +
4.312 + ///@}
4.313 +
4.314 + /// \name Query Functions
4.315 + /// The result of the %Matching algorithm can be obtained using these
4.316 + /// functions.\n
4.317 + /// Before the use of these functions,
4.318 + /// either run() or start() must be called.
4.319 + ///@{
4.320 +
4.321 + /// \brief Set true all matching uedge in the map.
4.322 + ///
4.323 + /// Set true all matching uedge in the map. It does not change the
4.324 + /// value mapped to the other uedges.
4.325 + /// \return The number of the matching edges.
4.326 + template <typename MatchingMap>
4.327 + int quickMatching(MatchingMap& mm) const {
4.328 + for (ANodeIt n(_g);n!=INVALID;++n) {
4.329 + if (_matching[n]!=INVALID) mm.set(_matching[n],true);
4.330 + }
4.331 + return _matching_size;
4.332 + }
4.333 +
4.334 + ///\brief Set true all matching uedge in the map and the others to false.
4.335 +
4.336 + ///Set true all matching uedge in the map and the others to false.
4.337 + ///\return The number of the matching edges.
4.338 + template<class MatchingMap>
4.339 + int matching(MatchingMap& mm) const {
4.340 + for (UEdgeIt e(_g);e!=INVALID;++e) {
4.341 + mm.set(e,e==_matching[_g.aNode(e)]);
4.342 + }
4.343 + return _matching_size;
4.344 + }
4.345 +
4.346 +
4.347 + ///Returns true if the given uedge is in the matching.
4.348 +
4.349 + ///It returns true if the given uedge is in the matching.
4.350 + ///
4.351 + bool matchingEdge(const UEdge& e) const {
4.352 + return _matching[_g.aNode(e)]==e;
4.353 + }
4.354 +
4.355 + ///Returns the matching edge from the node.
4.356 +
4.357 + ///Returns the matching edge from the node. If there is not such
4.358 + ///edge it gives back \c INVALID.
4.359 + ///\note If the parameter node is a B-node then the running time is
4.360 + ///propotional to the degree of the node.
4.361 + UEdge matchingEdge(const Node& n) const {
4.362 + if (_g.aNode(n)) {
4.363 + return _matching[n];
4.364 + } else {
4.365 + for (IncEdgeIt e(_g,n);e!=INVALID;++e)
4.366 + if (e==_matching[_g.aNode(e)]) return e;
4.367 + return INVALID;
4.368 + }
4.369 + }
4.370 +
4.371 + ///Gives back the number of the matching edges.
4.372 +
4.373 + ///Gives back the number of the matching edges.
4.374 + int matchingSize() const {
4.375 + return _matching_size;
4.376 + }
4.377 +
4.378 + ///Gives back a barrier on the A-nodes
4.379 +
4.380 + ///The barrier is s subset of the nodes on the same side of the
4.381 + ///graph. If we tried to find a perfect matching and it failed
4.382 + ///then the barrier size will be greater than its neighbours. If
4.383 + ///the maximum matching searched then the barrier size minus its
4.384 + ///neighbours will be exactly the unmatched nodes on the A-side.
4.385 + ///\retval bar A WriteMap on the ANodes with bool value.
4.386 + template<class BarrierMap>
4.387 + void aBarrier(BarrierMap &bar) const
4.388 + {
4.389 + for(ANodeIt n(_g);n!=INVALID;++n)
4.390 + bar.set(n,_matching[n]==INVALID ||
4.391 + _levels[_g.bNode(_matching[n])]<_empty_level);
4.392 + }
4.393 +
4.394 + ///Gives back a barrier on the B-nodes
4.395 +
4.396 + ///The barrier is s subset of the nodes on the same side of the
4.397 + ///graph. If we tried to find a perfect matching and it failed
4.398 + ///then the barrier size will be greater than its neighbours. If
4.399 + ///the maximum matching searched then the barrier size minus its
4.400 + ///neighbours will be exactly the unmatched nodes on the B-side.
4.401 + ///\retval bar A WriteMap on the BNodes with bool value.
4.402 + template<class BarrierMap>
4.403 + void bBarrier(BarrierMap &bar) const
4.404 + {
4.405 + for(BNodeIt n(_g);n!=INVALID;++n) bar.set(n,_levels[n]>=_empty_level);
4.406 + }
4.407 +
4.408 + ///Returns a minimum covering of the nodes.
4.409 +
4.410 + ///The minimum covering set problem is the dual solution of the
4.411 + ///maximum bipartite matching. It provides a solution for this
4.412 + ///problem what is proof of the optimality of the matching.
4.413 + ///\param covering NodeMap of bool values, the nodes of the cover
4.414 + ///set will set true while the others false.
4.415 + ///\return The size of the cover set.
4.416 + ///\note This function can be called just after the algorithm have
4.417 + ///already found a matching.
4.418 + template<class CoverMap>
4.419 + int coverSet(CoverMap& covering) const {
4.420 + int ret=0;
4.421 + for(BNodeIt n(_g);n!=INVALID;++n) {
4.422 + if (_levels[n]<_empty_level) { covering.set(n,true); ++ret; }
4.423 + else covering.set(n,false);
4.424 + }
4.425 + for(ANodeIt n(_g);n!=INVALID;++n) {
4.426 + if (_matching[n]!=INVALID &&
4.427 + _levels[_g.bNode(_matching[n])]>=_empty_level)
4.428 + { covering.set(n,true); ++ret; }
4.429 + else covering.set(n,false);
4.430 + }
4.431 + return ret;
4.432 + }
4.433 +
4.434 +
4.435 + /// @}
4.436 +
4.437 + };
4.438 +
4.439 +
4.440 + ///Maximum cardinality of the matchings in a bipartite graph
4.441 +
4.442 + ///\ingroup matching
4.443 + ///This function finds the maximum cardinality of the matchings
4.444 + ///in a bipartite graph \c g.
4.445 + ///\param g An undirected bipartite graph.
4.446 + ///\return The cardinality of the maximum matching.
4.447 + ///
4.448 + ///\note The the implementation is based
4.449 + ///on the push-relabel principle.
4.450 + template<class Graph>
4.451 + int prBipartiteMatching(const Graph &g)
4.452 + {
4.453 + PrBipartiteMatching<Graph> bpm(g);
4.454 + return bpm.matchingSize();
4.455 + }
4.456 +
4.457 + ///Maximum cardinality matching in a bipartite graph
4.458 +
4.459 + ///\ingroup matching
4.460 + ///This function finds a maximum cardinality matching
4.461 + ///in a bipartite graph \c g.
4.462 + ///\param g An undirected bipartite graph.
4.463 + ///\retval matching A write UEdgeMap of value type \c bool.
4.464 + /// The found edges will be returned in this map.
4.465 + ///\return The cardinality of the maximum matching.
4.466 + ///
4.467 + ///\note The the implementation is based
4.468 + ///on the push-relabel principle.
4.469 + template<class Graph,class MT>
4.470 + int prBipartiteMatching(const Graph &g,MT &matching)
4.471 + {
4.472 + PrBipartiteMatching<Graph> bpm(g);
4.473 + bpm.run();
4.474 + bpm.matching(matching);
4.475 + return bpm.matchingSize();
4.476 + }
4.477 +
4.478 + ///Maximum cardinality matching in a bipartite graph
4.479 +
4.480 + ///\ingroup matching
4.481 + ///This function finds a maximum cardinality matching
4.482 + ///in a bipartite graph \c g.
4.483 + ///\param g An undirected bipartite graph.
4.484 + ///\retval matching A write UEdgeMap of value type \c bool.
4.485 + /// The found edges will be returned in this map.
4.486 + ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
4.487 + /// exactly once for each BNode. The nodes with \c true value represent
4.488 + /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
4.489 + /// neighbor is equal to the number of the <tt>BNode</tt>s minus the
4.490 + /// cardinality of the maximum matching.
4.491 + ///\return The cardinality of the maximum matching.
4.492 + ///
4.493 + ///\note The the implementation is based
4.494 + ///on the push-relabel principle.
4.495 + template<class Graph,class MT, class GT>
4.496 + int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
4.497 + {
4.498 + PrBipartiteMatching<Graph> bpm(g);
4.499 + bpm.run();
4.500 + bpm.matching(matching);
4.501 + bpm.bBarrier(barrier);
4.502 + return bpm.matchingSize();
4.503 + }
4.504 +
4.505 + ///Perfect matching in a bipartite graph
4.506 +
4.507 + ///\ingroup matching
4.508 + ///This function checks whether the bipartite graph \c g
4.509 + ///has a perfect matching.
4.510 + ///\param g An undirected bipartite graph.
4.511 + ///\return \c true iff \c g has a perfect matching.
4.512 + ///
4.513 + ///\note The the implementation is based
4.514 + ///on the push-relabel principle.
4.515 + template<class Graph>
4.516 + bool prPerfectBipartiteMatching(const Graph &g)
4.517 + {
4.518 + PrBipartiteMatching<Graph> bpm(g);
4.519 + return bpm.runPerfect();
4.520 + }
4.521 +
4.522 + ///Perfect matching in a bipartite graph
4.523 +
4.524 + ///\ingroup matching
4.525 + ///This function finds a perfect matching in a bipartite graph \c g.
4.526 + ///\param g An undirected bipartite graph.
4.527 + ///\retval matching A write UEdgeMap of value type \c bool.
4.528 + /// The found edges will be returned in this map.
4.529 + /// The values are unchanged if the graph
4.530 + /// has no perfect matching.
4.531 + ///\return \c true iff \c g has a perfect matching.
4.532 + ///
4.533 + ///\note The the implementation is based
4.534 + ///on the push-relabel principle.
4.535 + template<class Graph,class MT>
4.536 + bool prPerfectBipartiteMatching(const Graph &g,MT &matching)
4.537 + {
4.538 + PrBipartiteMatching<Graph> bpm(g);
4.539 + bool ret = bpm.runPerfect();
4.540 + if (ret) bpm.matching(matching);
4.541 + return ret;
4.542 + }
4.543 +
4.544 + ///Perfect matching in a bipartite graph
4.545 +
4.546 + ///\ingroup matching
4.547 + ///This function finds a perfect matching in a bipartite graph \c g.
4.548 + ///\param g An undirected bipartite graph.
4.549 + ///\retval matching A readwrite UEdgeMap of value type \c bool.
4.550 + /// The found edges will be returned in this map.
4.551 + /// The values are unchanged if the graph
4.552 + /// has no perfect matching.
4.553 + ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
4.554 + /// be set if \c g has no perfect matching. In this case it is set
4.555 + /// exactly once for each BNode. The nodes with \c true value represent
4.556 + /// a barrier, i.e. a subset \e B a of BNodes with the property that
4.557 + /// the cardinality of \e B is greater than the number of its neighbors.
4.558 + ///\return \c true iff \c g has a perfect matching.
4.559 + ///
4.560 + ///\note The the implementation is based
4.561 + ///on the push-relabel principle.
4.562 + template<class Graph,class MT, class GT>
4.563 + int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
4.564 + {
4.565 + PrBipartiteMatching<Graph> bpm(g);
4.566 + bool ret=bpm.runPerfect();
4.567 + if(ret)
4.568 + bpm.matching(matching);
4.569 + else
4.570 + bpm.bBarrier(barrier);
4.571 + return ret;
4.572 + }
4.573 +}
4.574 +
4.575 +#endif
5.1 --- a/test/bipartite_matching_test.cc Thu Jul 26 13:59:12 2007 +0000
5.2 +++ b/test/bipartite_matching_test.cc Sat Aug 11 16:34:41 2007 +0000
5.3 @@ -24,6 +24,7 @@
5.4
5.5 #include <lemon/bpugraph_adaptor.h>
5.6 #include <lemon/bipartite_matching.h>
5.7 +#include <lemon/pr_bipartite_matching.h>
5.8
5.9 #include <lemon/graph_utils.h>
5.10
5.11 @@ -111,6 +112,30 @@
5.12 }
5.13
5.14 {
5.15 + PrBipartiteMatching<Graph> bpmatch(graph);
5.16 +
5.17 + bpmatch.run();
5.18 +
5.19 + Graph::UEdgeMap<bool> mm(graph);
5.20 + Graph::NodeMap<bool> cs(graph);
5.21 +
5.22 + check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
5.23 +
5.24 + for (UEdgeIt it(graph); it != INVALID; ++it) {
5.25 + check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
5.26 + }
5.27 +
5.28 + for (ANodeIt it(graph); it != INVALID; ++it) {
5.29 + int num = 0;
5.30 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
5.31 + if (mm[jt]) ++num;
5.32 + }
5.33 + check(num <= 1, "INVALID PRIMAL");
5.34 + }
5.35 + max_cardinality = bpmatch.matchingSize();
5.36 + }
5.37 +
5.38 + {
5.39 Graph::UEdgeMap<bool> mm(graph);
5.40
5.41 check(max_cardinality == maxBipartiteMatching(graph, mm),