lemon/bp_matching.h
changeset 2462 7a096a6bf53a
parent 2461 1dd4d6ff9bac
child 2463 19651a04d056
     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