# HG changeset patch
# User alpar
# Date 1169735935 0
# Node ID c43f8802c90ae97269781ca1c99f1e21eda5e868
# Parent  5e273e0bd5e24f29e9e88971322d4835ecdb50b1
A push/relabel type max cardinality matching implementation.
(slightly incompatible with bipartite_matching.h)

diff -r 5e273e0bd5e2 -r c43f8802c90a lemon/Makefile.am
--- a/lemon/Makefile.am	Thu Jan 25 14:36:21 2007 +0000
+++ b/lemon/Makefile.am	Thu Jan 25 14:38:55 2007 +0000
@@ -37,6 +37,7 @@
 	lemon/bfs.h \
 	lemon/bin_heap.h \
 	lemon/bipartite_matching.h \
+	lemon/bp_matching.h \
 	lemon/bpugraph_adaptor.h \
 	lemon/bucket_heap.h \
 	lemon/color.h \
diff -r 5e273e0bd5e2 -r c43f8802c90a lemon/bp_matching.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bp_matching.h	Thu Jan 25 14:38:55 2007 +0000
@@ -0,0 +1,381 @@
+/* -*- C++ -*-
+ * lemon/preflow_matching.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 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