diff -r 1dd4d6ff9bac -r 7a096a6bf53a lemon/bp_matching.h
--- a/lemon/bp_matching.h	Thu Jul 26 13:59:12 2007 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,383 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2007
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_BP_MATCHING
-#define LEMON_BP_MATCHING
-
-#include <lemon/graph_utils.h>
-#include <lemon/iterable_maps.h>
-#include <iostream>
-#include <queue>
-#include <lemon/counter.h>
-#include <lemon/elevator.h>
-
-///\ingroup matching
-///\file
-///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
-///
-///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h
-///\todo (Re)move the XYZ_TYPEDEFS macros
-namespace lemon {
-
-#define BIPARTITE_TYPEDEFS(Graph)		\
-  GRAPH_TYPEDEFS(Graph)				\
-    typedef Graph::ANodeIt ANodeIt;	\
-    typedef Graph::BNodeIt BNodeIt;
-
-#define UNDIRBIPARTITE_TYPEDEFS(Graph)		\
-  UNDIRGRAPH_TYPEDEFS(Graph)			\
-    typedef Graph::ANodeIt ANodeIt;	\
-    typedef Graph::BNodeIt BNodeIt;
-
-  template<class Graph,
-	   class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >
-  class BpMatching {
-    typedef typename Graph::Node Node;
-    typedef typename Graph::ANodeIt ANodeIt;
-    typedef typename Graph::BNodeIt BNodeIt;
-    typedef typename Graph::UEdge UEdge;
-    typedef typename Graph::IncEdgeIt IncEdgeIt;
-    
-    const Graph &_g;
-    int _node_num;
-    MT &_matching;
-    Elevator<Graph,typename Graph::BNode> _levels;
-    typename Graph::template BNodeMap<int> _cov;
-
-  public:
-    BpMatching(const Graph &g, MT &matching) :
-      _g(g),
-      _node_num(countBNodes(g)),
-      _matching(matching),
-      _levels(g,_node_num),
-      _cov(g,0)
-    {
-    }
-    
-  private:
-    void init() 
-    {
-//     for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;
-      for(ANodeIt n(_g);n!=INVALID;++n)
-	if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
-	  ++_cov[_g.oppositeNode(n,_matching[n])];
-
-      std::queue<Node> q;
-      _levels.initStart();
-      for(BNodeIt n(_g);n!=INVALID;++n)
-	if(_cov[n]>1) {
-	  _levels.initAddItem(n);
-	  q.push(n);
-	}
-      int hlev=0;
-      while(!q.empty()) {
-	Node n=q.front();
-	q.pop();
-	int nlev=_levels[n]+1;
-	for(IncEdgeIt e(_g,n);e!=INVALID;++e) {
-	  Node m=_g.runningNode(e);
-	  if(e==_matching[m]) {
-	    for(IncEdgeIt f(_g,m);f!=INVALID;++f) {
-	      Node r=_g.runningNode(f);
-	      if(_levels[r]>nlev) {
-		for(;nlev>hlev;hlev++)
-		  _levels.initNewLevel();
-		_levels.initAddItem(r);
-		q.push(r);
-	      }
-	    }
-	  }
-	}
-      }
-      _levels.initFinish();
-      for(BNodeIt n(_g);n!=INVALID;++n)
-	if(_cov[n]<1&&_levels[n]<_node_num)
-	  _levels.activate(n);
-    }
-  public:
-    int run() 
-    {
-      init();
-
-      Node act;
-      Node bact=INVALID;
-      Node last_activated=INVALID;
-//       while((act=last_activated!=INVALID?
-// 	     last_activated:_levels.highestActive())
-// 	    !=INVALID)
-      while((act=_levels.highestActive())!=INVALID) {
-	last_activated=INVALID;
-	int actlevel=_levels[act];
-	
-	UEdge bedge=INVALID;
-	int nlevel=_node_num;
-	{
-	  int nnlevel;
-	  for(IncEdgeIt tbedge(_g,act);
-	      tbedge!=INVALID && nlevel>=actlevel;
-	      ++tbedge)
-	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
-	       nlevel)
-	      {
-		nlevel=nnlevel;
-		bedge=tbedge;
-	      }
-	}
-	if(nlevel<_node_num) {
-	  if(nlevel>=actlevel)
-	    _levels.liftHighestActiveTo(nlevel+1);
-// 	    _levels.liftTo(act,nlevel+1);
-	  bact=_g.bNode(_matching[_g.aNode(bedge)]);
-	  if(--_cov[bact]<1) {
-	    _levels.activate(bact);
-	    last_activated=bact;
-	  }
-	  _matching[_g.aNode(bedge)]=bedge;
-	  _cov[act]=1;
-	  _levels.deactivate(act);
-	}
-	else {
-	  if(_node_num>actlevel) 
-	    _levels.liftHighestActiveTo(_node_num);
-//  	    _levels.liftTo(act,_node_num);
-	  _levels.deactivate(act); 
-	}
-
-	if(_levels.onLevel(actlevel)==0)
-	  _levels.liftToTop(actlevel);
-      }
-      
-      int ret=_node_num;
-      for(ANodeIt n(_g);n!=INVALID;++n)
-	if(_matching[n]==INVALID) ret--;
-	else if (_cov[_g.bNode(_matching[n])]>1) {
-	  _cov[_g.bNode(_matching[n])]--;
-	  ret--;
-	  _matching[n]=INVALID;
-	}
-      return ret;
-    }
-    
-    ///\returns -1 if there is a perfect matching, or an empty level
-    ///if it doesn't exists
-    int runPerfect() 
-    {
-      init();
-
-      Node act;
-      Node bact=INVALID;
-      Node last_activated=INVALID;
-      while((act=_levels.highestActive())!=INVALID) {
-	last_activated=INVALID;
-	int actlevel=_levels[act];
-	
-	UEdge bedge=INVALID;
-	int nlevel=_node_num;
-	{
-	  int nnlevel;
-	  for(IncEdgeIt tbedge(_g,act);
-	      tbedge!=INVALID && nlevel>=actlevel;
-	      ++tbedge)
-	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
-	       nlevel)
-	      {
-		nlevel=nnlevel;
-		bedge=tbedge;
-	      }
-	}
-	if(nlevel<_node_num) {
-	  if(nlevel>=actlevel)
-	    _levels.liftHighestActiveTo(nlevel+1);
-	  bact=_g.bNode(_matching[_g.aNode(bedge)]);
-	  if(--_cov[bact]<1) {
-	    _levels.activate(bact);
-	    last_activated=bact;
-	  }
-	  _matching[_g.aNode(bedge)]=bedge;
-	  _cov[act]=1;
-	  _levels.deactivate(act);
-	}
-	else {
-	  if(_node_num>actlevel) 
-	    _levels.liftHighestActiveTo(_node_num);
-	  _levels.deactivate(act); 
-	}
-
-	if(_levels.onLevel(actlevel)==0)
-	  return actlevel;
-      }
-      return -1;
-    }
- 
-    template<class GT>
-    void aBarrier(GT &bar,int empty_level=-1) 
-    {
-      if(empty_level==-1)
-	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
-      for(ANodeIt n(_g);n!=INVALID;++n)
-	bar[n] = _matching[n]==INVALID ||
-	  _levels[_g.bNode(_matching[n])]<empty_level;  
-    }  
-    template<class GT>
-    void bBarrier(GT &bar, int empty_level=-1) 
-    {
-      if(empty_level==-1)
-	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
-      for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level);  
-    }  
-  
-  };
-  
-  
-  ///Maximum cardinality of the matchings in a bipartite graph
-
-  ///\ingroup matching
-  ///This function finds the maximum cardinality of the matchings
-  ///in a bipartite graph \c g.
-  ///\param g An undirected bipartite graph.
-  ///\return The cardinality of the maximum matching.
-  ///
-  ///\note The the implementation is based
-  ///on the push-relabel principle.
-  template<class Graph>
-  int maxBpMatching(const Graph &g)
-  {
-    typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
-    return maxBpMatching(g,matching);
-  }
-
-  ///Maximum cardinality matching in a bipartite graph
-
-  ///\ingroup matching
-  ///This function finds a maximum cardinality matching
-  ///in a bipartite graph \c g.
-  ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
-  /// \ref INVALID if it is uncovered.
-  ///\return The cardinality of the maximum matching.
-  ///
-  ///\note The the implementation is based
-  ///on the push-relabel principle.
-  template<class Graph,class MT>
-  int maxBpMatching(const Graph &g,MT &matching) 
-  {
-    return BpMatching<Graph,MT>(g,matching).run();
-  }
-
-  ///Maximum cardinality matching in a bipartite graph
-
-  ///\ingroup matching
-  ///This function finds a maximum cardinality matching
-  ///in a bipartite graph \c g.
-  ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
-  /// \ref INVALID if it is uncovered.
-  ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
-  /// exactly once for each BNode. The nodes with \c true value represent
-  /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
-  /// neighbor is equal to the number of the <tt>BNode</tt>s minus the
-  /// cardinality of the maximum matching.
-  ///\return The cardinality of the maximum matching.
-  ///
-  ///\note The the implementation is based
-  ///on the push-relabel principle.
-  template<class Graph,class MT, class GT>
-  int maxBpMatching(const Graph &g,MT &matching,GT &barrier) 
-  {
-    BpMatching<Graph,MT> bpm(g,matching);
-    int ret=bpm.run();
-    bpm.barrier(barrier);
-    return ret;
-  }  
-
-  ///Perfect matching in a bipartite graph
-
-  ///\ingroup matching
-  ///This function checks whether the bipartite graph \c g
-  ///has a perfect matching.
-  ///\param g An undirected bipartite graph.
-  ///\return \c true iff \c g has a perfect matching.
-  ///
-  ///\note The the implementation is based
-  ///on the push-relabel principle.
-  template<class Graph>
-  bool perfectBpMatching(const Graph &g)
-  {
-    typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
-    return perfectBpMatching(g,matching);
-  }
-
-  ///Perfect matching in a bipartite graph
-
-  ///\ingroup matching
-  ///This function finds a perfect matching in a bipartite graph \c g.
-  ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
-  /// The values are unspecified if the graph
-  /// has no perfect matching.
-  ///\return \c true iff \c g has a perfect matching.
-  ///
-  ///\note The the implementation is based
-  ///on the push-relabel principle.
-  template<class Graph,class MT>
-  bool perfectBpMatching(const Graph &g,MT &matching) 
-  {
-    return BpMatching<Graph,MT>(g,matching).runPerfect()<0;
-  }
-
-  ///Perfect matching in a bipartite graph
-
-  ///\ingroup matching
-  ///This function finds a perfect matching in a bipartite graph \c g.
-  ///\param g An undirected bipartite graph.
-  ///\retval matching A readwrite ANodeMap of value type \c Edge.
-  /// The found edges will be returned in this map,
-  /// i.e. for an \c ANode \c n,
-  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
-  /// The values are unspecified if the graph
-  /// has no perfect matching.
-  ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
-  /// be set if \c g has no perfect matching. In this case it is set 
-  /// exactly once for each BNode. The nodes with \c true value represent
-  /// a barrier, i.e. a subset \e B a of BNodes with the property that
-  /// the cardinality of \e B is greater than the numner of its neighbors.
-  ///\return \c true iff \c g has a perfect matching.
-  ///
-  ///\note The the implementation is based
-  ///on the push-relabel principle.
-  template<class Graph,class MT, class GT>
-  int perfectBpMatching(const Graph &g,MT &matching,GT &barrier) 
-  {
-    BpMatching<Graph,MT> bpm(g,matching);
-    int ret=bpm.run();
-    if(ret>=0)
-      bpm.barrier(barrier,ret);
-    return ret<0;
-  }  
-}
-
-#endif