1.1 --- a/lemon/bp_matching.h Thu Jul 26 13:59:12 2007 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,383 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2007
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_BP_MATCHING
1.23 -#define LEMON_BP_MATCHING
1.24 -
1.25 -#include <lemon/graph_utils.h>
1.26 -#include <lemon/iterable_maps.h>
1.27 -#include <iostream>
1.28 -#include <queue>
1.29 -#include <lemon/counter.h>
1.30 -#include <lemon/elevator.h>
1.31 -
1.32 -///\ingroup matching
1.33 -///\file
1.34 -///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
1.35 -///
1.36 -///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h
1.37 -///\todo (Re)move the XYZ_TYPEDEFS macros
1.38 -namespace lemon {
1.39 -
1.40 -#define BIPARTITE_TYPEDEFS(Graph) \
1.41 - GRAPH_TYPEDEFS(Graph) \
1.42 - typedef Graph::ANodeIt ANodeIt; \
1.43 - typedef Graph::BNodeIt BNodeIt;
1.44 -
1.45 -#define UNDIRBIPARTITE_TYPEDEFS(Graph) \
1.46 - UNDIRGRAPH_TYPEDEFS(Graph) \
1.47 - typedef Graph::ANodeIt ANodeIt; \
1.48 - typedef Graph::BNodeIt BNodeIt;
1.49 -
1.50 - template<class Graph,
1.51 - class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >
1.52 - class BpMatching {
1.53 - typedef typename Graph::Node Node;
1.54 - typedef typename Graph::ANodeIt ANodeIt;
1.55 - typedef typename Graph::BNodeIt BNodeIt;
1.56 - typedef typename Graph::UEdge UEdge;
1.57 - typedef typename Graph::IncEdgeIt IncEdgeIt;
1.58 -
1.59 - const Graph &_g;
1.60 - int _node_num;
1.61 - MT &_matching;
1.62 - Elevator<Graph,typename Graph::BNode> _levels;
1.63 - typename Graph::template BNodeMap<int> _cov;
1.64 -
1.65 - public:
1.66 - BpMatching(const Graph &g, MT &matching) :
1.67 - _g(g),
1.68 - _node_num(countBNodes(g)),
1.69 - _matching(matching),
1.70 - _levels(g,_node_num),
1.71 - _cov(g,0)
1.72 - {
1.73 - }
1.74 -
1.75 - private:
1.76 - void init()
1.77 - {
1.78 -// for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;
1.79 - for(ANodeIt n(_g);n!=INVALID;++n)
1.80 - if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
1.81 - ++_cov[_g.oppositeNode(n,_matching[n])];
1.82 -
1.83 - std::queue<Node> q;
1.84 - _levels.initStart();
1.85 - for(BNodeIt n(_g);n!=INVALID;++n)
1.86 - if(_cov[n]>1) {
1.87 - _levels.initAddItem(n);
1.88 - q.push(n);
1.89 - }
1.90 - int hlev=0;
1.91 - while(!q.empty()) {
1.92 - Node n=q.front();
1.93 - q.pop();
1.94 - int nlev=_levels[n]+1;
1.95 - for(IncEdgeIt e(_g,n);e!=INVALID;++e) {
1.96 - Node m=_g.runningNode(e);
1.97 - if(e==_matching[m]) {
1.98 - for(IncEdgeIt f(_g,m);f!=INVALID;++f) {
1.99 - Node r=_g.runningNode(f);
1.100 - if(_levels[r]>nlev) {
1.101 - for(;nlev>hlev;hlev++)
1.102 - _levels.initNewLevel();
1.103 - _levels.initAddItem(r);
1.104 - q.push(r);
1.105 - }
1.106 - }
1.107 - }
1.108 - }
1.109 - }
1.110 - _levels.initFinish();
1.111 - for(BNodeIt n(_g);n!=INVALID;++n)
1.112 - if(_cov[n]<1&&_levels[n]<_node_num)
1.113 - _levels.activate(n);
1.114 - }
1.115 - public:
1.116 - int run()
1.117 - {
1.118 - init();
1.119 -
1.120 - Node act;
1.121 - Node bact=INVALID;
1.122 - Node last_activated=INVALID;
1.123 -// while((act=last_activated!=INVALID?
1.124 -// last_activated:_levels.highestActive())
1.125 -// !=INVALID)
1.126 - while((act=_levels.highestActive())!=INVALID) {
1.127 - last_activated=INVALID;
1.128 - int actlevel=_levels[act];
1.129 -
1.130 - UEdge bedge=INVALID;
1.131 - int nlevel=_node_num;
1.132 - {
1.133 - int nnlevel;
1.134 - for(IncEdgeIt tbedge(_g,act);
1.135 - tbedge!=INVALID && nlevel>=actlevel;
1.136 - ++tbedge)
1.137 - if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
1.138 - nlevel)
1.139 - {
1.140 - nlevel=nnlevel;
1.141 - bedge=tbedge;
1.142 - }
1.143 - }
1.144 - if(nlevel<_node_num) {
1.145 - if(nlevel>=actlevel)
1.146 - _levels.liftHighestActiveTo(nlevel+1);
1.147 -// _levels.liftTo(act,nlevel+1);
1.148 - bact=_g.bNode(_matching[_g.aNode(bedge)]);
1.149 - if(--_cov[bact]<1) {
1.150 - _levels.activate(bact);
1.151 - last_activated=bact;
1.152 - }
1.153 - _matching[_g.aNode(bedge)]=bedge;
1.154 - _cov[act]=1;
1.155 - _levels.deactivate(act);
1.156 - }
1.157 - else {
1.158 - if(_node_num>actlevel)
1.159 - _levels.liftHighestActiveTo(_node_num);
1.160 -// _levels.liftTo(act,_node_num);
1.161 - _levels.deactivate(act);
1.162 - }
1.163 -
1.164 - if(_levels.onLevel(actlevel)==0)
1.165 - _levels.liftToTop(actlevel);
1.166 - }
1.167 -
1.168 - int ret=_node_num;
1.169 - for(ANodeIt n(_g);n!=INVALID;++n)
1.170 - if(_matching[n]==INVALID) ret--;
1.171 - else if (_cov[_g.bNode(_matching[n])]>1) {
1.172 - _cov[_g.bNode(_matching[n])]--;
1.173 - ret--;
1.174 - _matching[n]=INVALID;
1.175 - }
1.176 - return ret;
1.177 - }
1.178 -
1.179 - ///\returns -1 if there is a perfect matching, or an empty level
1.180 - ///if it doesn't exists
1.181 - int runPerfect()
1.182 - {
1.183 - init();
1.184 -
1.185 - Node act;
1.186 - Node bact=INVALID;
1.187 - Node last_activated=INVALID;
1.188 - while((act=_levels.highestActive())!=INVALID) {
1.189 - last_activated=INVALID;
1.190 - int actlevel=_levels[act];
1.191 -
1.192 - UEdge bedge=INVALID;
1.193 - int nlevel=_node_num;
1.194 - {
1.195 - int nnlevel;
1.196 - for(IncEdgeIt tbedge(_g,act);
1.197 - tbedge!=INVALID && nlevel>=actlevel;
1.198 - ++tbedge)
1.199 - if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
1.200 - nlevel)
1.201 - {
1.202 - nlevel=nnlevel;
1.203 - bedge=tbedge;
1.204 - }
1.205 - }
1.206 - if(nlevel<_node_num) {
1.207 - if(nlevel>=actlevel)
1.208 - _levels.liftHighestActiveTo(nlevel+1);
1.209 - bact=_g.bNode(_matching[_g.aNode(bedge)]);
1.210 - if(--_cov[bact]<1) {
1.211 - _levels.activate(bact);
1.212 - last_activated=bact;
1.213 - }
1.214 - _matching[_g.aNode(bedge)]=bedge;
1.215 - _cov[act]=1;
1.216 - _levels.deactivate(act);
1.217 - }
1.218 - else {
1.219 - if(_node_num>actlevel)
1.220 - _levels.liftHighestActiveTo(_node_num);
1.221 - _levels.deactivate(act);
1.222 - }
1.223 -
1.224 - if(_levels.onLevel(actlevel)==0)
1.225 - return actlevel;
1.226 - }
1.227 - return -1;
1.228 - }
1.229 -
1.230 - template<class GT>
1.231 - void aBarrier(GT &bar,int empty_level=-1)
1.232 - {
1.233 - if(empty_level==-1)
1.234 - for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
1.235 - for(ANodeIt n(_g);n!=INVALID;++n)
1.236 - bar[n] = _matching[n]==INVALID ||
1.237 - _levels[_g.bNode(_matching[n])]<empty_level;
1.238 - }
1.239 - template<class GT>
1.240 - void bBarrier(GT &bar, int empty_level=-1)
1.241 - {
1.242 - if(empty_level==-1)
1.243 - for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
1.244 - for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level);
1.245 - }
1.246 -
1.247 - };
1.248 -
1.249 -
1.250 - ///Maximum cardinality of the matchings in a bipartite graph
1.251 -
1.252 - ///\ingroup matching
1.253 - ///This function finds the maximum cardinality of the matchings
1.254 - ///in a bipartite graph \c g.
1.255 - ///\param g An undirected bipartite graph.
1.256 - ///\return The cardinality of the maximum matching.
1.257 - ///
1.258 - ///\note The the implementation is based
1.259 - ///on the push-relabel principle.
1.260 - template<class Graph>
1.261 - int maxBpMatching(const Graph &g)
1.262 - {
1.263 - typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
1.264 - return maxBpMatching(g,matching);
1.265 - }
1.266 -
1.267 - ///Maximum cardinality matching in a bipartite graph
1.268 -
1.269 - ///\ingroup matching
1.270 - ///This function finds a maximum cardinality matching
1.271 - ///in a bipartite graph \c g.
1.272 - ///\param g An undirected bipartite graph.
1.273 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
1.274 - /// The found edges will be returned in this map,
1.275 - /// i.e. for an \c ANode \c n,
1.276 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
1.277 - /// \ref INVALID if it is uncovered.
1.278 - ///\return The cardinality of the maximum matching.
1.279 - ///
1.280 - ///\note The the implementation is based
1.281 - ///on the push-relabel principle.
1.282 - template<class Graph,class MT>
1.283 - int maxBpMatching(const Graph &g,MT &matching)
1.284 - {
1.285 - return BpMatching<Graph,MT>(g,matching).run();
1.286 - }
1.287 -
1.288 - ///Maximum cardinality matching in a bipartite graph
1.289 -
1.290 - ///\ingroup matching
1.291 - ///This function finds a maximum cardinality matching
1.292 - ///in a bipartite graph \c g.
1.293 - ///\param g An undirected bipartite graph.
1.294 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
1.295 - /// The found edges will be returned in this map,
1.296 - /// i.e. for an \c ANode \c n,
1.297 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
1.298 - /// \ref INVALID if it is uncovered.
1.299 - ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
1.300 - /// exactly once for each BNode. The nodes with \c true value represent
1.301 - /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
1.302 - /// neighbor is equal to the number of the <tt>BNode</tt>s minus the
1.303 - /// cardinality of the maximum matching.
1.304 - ///\return The cardinality of the maximum matching.
1.305 - ///
1.306 - ///\note The the implementation is based
1.307 - ///on the push-relabel principle.
1.308 - template<class Graph,class MT, class GT>
1.309 - int maxBpMatching(const Graph &g,MT &matching,GT &barrier)
1.310 - {
1.311 - BpMatching<Graph,MT> bpm(g,matching);
1.312 - int ret=bpm.run();
1.313 - bpm.barrier(barrier);
1.314 - return ret;
1.315 - }
1.316 -
1.317 - ///Perfect matching in a bipartite graph
1.318 -
1.319 - ///\ingroup matching
1.320 - ///This function checks whether the bipartite graph \c g
1.321 - ///has a perfect matching.
1.322 - ///\param g An undirected bipartite graph.
1.323 - ///\return \c true iff \c g has a perfect matching.
1.324 - ///
1.325 - ///\note The the implementation is based
1.326 - ///on the push-relabel principle.
1.327 - template<class Graph>
1.328 - bool perfectBpMatching(const Graph &g)
1.329 - {
1.330 - typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
1.331 - return perfectBpMatching(g,matching);
1.332 - }
1.333 -
1.334 - ///Perfect matching in a bipartite graph
1.335 -
1.336 - ///\ingroup matching
1.337 - ///This function finds a perfect matching in a bipartite graph \c g.
1.338 - ///\param g An undirected bipartite graph.
1.339 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
1.340 - /// The found edges will be returned in this map,
1.341 - /// i.e. for an \c ANode \c n,
1.342 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
1.343 - /// The values are unspecified if the graph
1.344 - /// has no perfect matching.
1.345 - ///\return \c true iff \c g has a perfect matching.
1.346 - ///
1.347 - ///\note The the implementation is based
1.348 - ///on the push-relabel principle.
1.349 - template<class Graph,class MT>
1.350 - bool perfectBpMatching(const Graph &g,MT &matching)
1.351 - {
1.352 - return BpMatching<Graph,MT>(g,matching).runPerfect()<0;
1.353 - }
1.354 -
1.355 - ///Perfect matching in a bipartite graph
1.356 -
1.357 - ///\ingroup matching
1.358 - ///This function finds a perfect matching in a bipartite graph \c g.
1.359 - ///\param g An undirected bipartite graph.
1.360 - ///\retval matching A readwrite ANodeMap of value type \c Edge.
1.361 - /// The found edges will be returned in this map,
1.362 - /// i.e. for an \c ANode \c n,
1.363 - /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
1.364 - /// The values are unspecified if the graph
1.365 - /// has no perfect matching.
1.366 - ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
1.367 - /// be set if \c g has no perfect matching. In this case it is set
1.368 - /// exactly once for each BNode. The nodes with \c true value represent
1.369 - /// a barrier, i.e. a subset \e B a of BNodes with the property that
1.370 - /// the cardinality of \e B is greater than the numner of its neighbors.
1.371 - ///\return \c true iff \c g has a perfect matching.
1.372 - ///
1.373 - ///\note The the implementation is based
1.374 - ///on the push-relabel principle.
1.375 - template<class Graph,class MT, class GT>
1.376 - int perfectBpMatching(const Graph &g,MT &matching,GT &barrier)
1.377 - {
1.378 - BpMatching<Graph,MT> bpm(g,matching);
1.379 - int ret=bpm.run();
1.380 - if(ret>=0)
1.381 - bpm.barrier(barrier,ret);
1.382 - return ret<0;
1.383 - }
1.384 -}
1.385 -
1.386 -#endif