lemon-0.x: lemon/bp_matching.h@ac0d843b8873

     1 /* -*- C++ -*-

     2  * lemon/preflow_matching.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_BP_MATCHING

    18 #define LEMON_BP_MATCHING

    20 #include <lemon/graph_utils.h>

    21 #include <lemon/iterable_maps.h>

    22 #include <iostream>

    23 #include <queue>

    24 #include <lemon/counter.h>

    25 #include <lemon/elevator.h>

    27 ///\ingroup matching

    28 ///\file

    29 ///\brief Push-prelabel maximum matching algorithms in bipartite graphs.

    30 ///

    31 ///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h

    32 ///\todo (Re)move the XYZ_TYPEDEFS macros

    33 namespace lemon {

    35 #define BIPARTITE_TYPEDEFS(Graph)		\

    36   GRAPH_TYPEDEFS(Graph)				\

    37     typedef Graph::ANodeIt ANodeIt;	\

    38     typedef Graph::BNodeIt BNodeIt;

    40 #define UNDIRBIPARTITE_TYPEDEFS(Graph)		\

    41   UNDIRGRAPH_TYPEDEFS(Graph)			\

    42     typedef Graph::ANodeIt ANodeIt;	\

    43     typedef Graph::BNodeIt BNodeIt;

    45   template<class Graph,

    46 	   class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >

    47   class BpMatching {

    48     typedef typename Graph::Node Node;

    49     typedef typename Graph::ANodeIt ANodeIt;

    50     typedef typename Graph::BNodeIt BNodeIt;

    51     typedef typename Graph::UEdge UEdge;

    52     typedef typename Graph::IncEdgeIt IncEdgeIt;

    54     const Graph &_g;

    55     int _node_num;

    56     MT &_matching;

    57     Elevator<Graph,typename Graph::BNode> _levels;

    58     typename Graph::template BNodeMap<int> _cov;

    60   public:

    61     BpMatching(const Graph &g, MT &matching) :

    62       _g(g),

    63       _node_num(countBNodes(g)),

    64       _matching(matching),

    65       _levels(g,_node_num),

    66       _cov(g,0)

    67     {

    68     }

    70   private:

    71     void init()

    72     {

    73 //     for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;

    74       for(ANodeIt n(_g);n!=INVALID;++n)

    75 	if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)

    76 	  ++_cov[_g.oppositeNode(n,_matching[n])];

    78       std::queue<Node> q;

    79       _levels.initStart();

    80       for(BNodeIt n(_g);n!=INVALID;++n)

    81 	if(_cov[n]>1) {

    82 	  _levels.initAddItem(n);

    83 	  q.push(n);

    84 	}

    85       int hlev=0;

    86       while(!q.empty()) {

    87 	Node n=q.front();

    88 	q.pop();

    89 	int nlev=_levels[n]+1;

    90 	for(IncEdgeIt e(_g,n);e!=INVALID;++e) {

    91 	  Node m=_g.runningNode(e);

    92 	  if(e==_matching[m]) {

    93 	    for(IncEdgeIt f(_g,m);f!=INVALID;++f) {

    94 	      Node r=_g.runningNode(f);

    95 	      if(_levels[r]>nlev) {

    96 		for(;nlev>hlev;hlev++)

    97 		  _levels.initNewLevel();

    98 		_levels.initAddItem(r);

    99 		q.push(r);

   100 	      }

   101 	    }

   102 	  }

   103 	}

   104       }

   105       _levels.initFinish();

   106       for(BNodeIt n(_g);n!=INVALID;++n)

   107 	if(_cov[n]<1&&_levels[n]<_node_num)

   108 	  _levels.activate(n);

   109     }

   110   public:

   111     int run()

   112     {

   113       init();

   115       Node act;

   116       Node bact=INVALID;

   117       Node last_activated=INVALID;

   118 //       while((act=last_activated!=INVALID?

   119 // 	     last_activated:_levels.highestActive())

   120 // 	    !=INVALID)

   121       while((act=_levels.highestActive())!=INVALID) {

   122 	last_activated=INVALID;

   123 	int actlevel=_levels[act];

   125 	UEdge bedge=INVALID;

   126 	int nlevel=_node_num;

   127 	{

   128 	  int nnlevel;

   129 	  for(IncEdgeIt tbedge(_g,act);

   130 	      tbedge!=INVALID && nlevel>=actlevel;

   131 	      ++tbedge)

   132 	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<

   133 	       nlevel)

   134 	      {

   135 		nlevel=nnlevel;

   136 		bedge=tbedge;

   137 	      }

   138 	}

   139 	if(nlevel<_node_num) {

   140 	  if(nlevel>=actlevel)

   141 	    _levels.liftHighestActiveTo(nlevel+1);

   142 // 	    _levels.liftTo(act,nlevel+1);

   143 	  bact=_g.bNode(_matching[_g.aNode(bedge)]);

   144 	  if(--_cov[bact]<1) {

   145 	    _levels.activate(bact);

   146 	    last_activated=bact;

   147 	  }

   148 	  _matching[_g.aNode(bedge)]=bedge;

   149 	  _cov[act]=1;

   150 	  _levels.deactivate(act);

   151 	}

   152 	else {

   153 	  if(_node_num>actlevel)

   154 	    _levels.liftHighestActiveTo(_node_num);

   155 //  	    _levels.liftTo(act,_node_num);

   156 	  _levels.deactivate(act);

   157 	}

   159 	if(_levels.onLevel(actlevel)==0)

   160 	  _levels.liftToTop(actlevel);

   161       }

   163       int ret=_node_num;

   164       for(ANodeIt n(_g);n!=INVALID;++n)

   165 	if(_matching[n]==INVALID) ret--;

   166 	else if (_cov[_g.bNode(_matching[n])]>1) {

   167 	  _cov[_g.bNode(_matching[n])]--;

   168 	  ret--;

   169 	  _matching[n]=INVALID;

   170 	}

   171       return ret;

   172     }

   174     ///\returns -1 if there is a perfect matching, or an empty level

   175     ///if it doesn't exists

   176     int runPerfect()

   177     {

   178       init();

   180       Node act;

   181       Node bact=INVALID;

   182       Node last_activated=INVALID;

   183       while((act=_levels.highestActive())!=INVALID) {

   184 	last_activated=INVALID;

   185 	int actlevel=_levels[act];

   187 	UEdge bedge=INVALID;

   188 	int nlevel=_node_num;

   189 	{

   190 	  int nnlevel;

   191 	  for(IncEdgeIt tbedge(_g,act);

   192 	      tbedge!=INVALID && nlevel>=actlevel;

   193 	      ++tbedge)

   194 	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<

   195 	       nlevel)

   196 	      {

   197 		nlevel=nnlevel;

   198 		bedge=tbedge;

   199 	      }

   200 	}

   201 	if(nlevel<_node_num) {

   202 	  if(nlevel>=actlevel)

   203 	    _levels.liftHighestActiveTo(nlevel+1);

   204 	  bact=_g.bNode(_matching[_g.aNode(bedge)]);

   205 	  if(--_cov[bact]<1) {

   206 	    _levels.activate(bact);

   207 	    last_activated=bact;

   208 	  }

   209 	  _matching[_g.aNode(bedge)]=bedge;

   210 	  _cov[act]=1;

   211 	  _levels.deactivate(act);

   212 	}

   213 	else {

   214 	  if(_node_num>actlevel)

   215 	    _levels.liftHighestActiveTo(_node_num);

   216 	  _levels.deactivate(act);

   217 	}

   219 	if(_levels.onLevel(actlevel)==0)

   220 	  return actlevel;

   221       }

   222       return -1;

   223     }

   225     template<class GT>

   226     void aBarrier(GT &bar,int empty_level=-1)

   227     {

   228       if(empty_level==-1)

   229 	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;

   230       for(ANodeIt n(_g);n!=INVALID;++n)

   231 	bar[n] = _matching[n]==INVALID ||

   232 	  _levels[_g.bNode(_matching[n])]<empty_level;

   233     }

   234     template<class GT>

   235     void bBarrier(GT &bar, int empty_level=-1)

   236     {

   237       if(empty_level==-1)

   238 	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;

   239       for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level);

   240     }

   242   };

   245   ///Maximum cardinality of the matchings in a bipartite graph

   247   ///\ingroup matching

   248   ///This function finds the maximum cardinality of the matchings

   249   ///in a bipartite graph \c g.

   250   ///\param g An undirected bipartite graph.

   251   ///\return The cardinality of the maximum matching.

   252   ///

   253   ///\note The the implementation is based

   254   ///on the push-relabel principle.

   255   template<class Graph>

   256   int maxBpMatching(const Graph &g)

   257   {

   258     typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);

   259     return maxBpMatching(g,matching);

   260   }

   262   ///Maximum cardinality matching in a bipartite graph

   264   ///\ingroup matching

   265   ///This function finds a maximum cardinality matching

   266   ///in a bipartite graph \c g.

   267   ///\param g An undirected bipartite graph.

   268   ///\retval matching A readwrite ANodeMap of value type \c Edge.

   269   /// The found edges will be returned in this map,

   270   /// i.e. for an \c ANode \c n,

   271   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or

   272   /// \ref INVALID if it is uncovered.

   273   ///\return The cardinality of the maximum matching.

   274   ///

   275   ///\note The the implementation is based

   276   ///on the push-relabel principle.

   277   template<class Graph,class MT>

   278   int maxBpMatching(const Graph &g,MT &matching)

   279   {

   280     return BpMatching<Graph,MT>(g,matching).run();

   281   }

   283   ///Maximum cardinality matching in a bipartite graph

   285   ///\ingroup matching

   286   ///This function finds a maximum cardinality matching

   287   ///in a bipartite graph \c g.

   288   ///\param g An undirected bipartite graph.

   289   ///\retval matching A readwrite ANodeMap of value type \c Edge.

   290   /// The found edges will be returned in this map,

   291   /// i.e. for an \c ANode \c n,

   292   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or

   293   /// \ref INVALID if it is uncovered.

   294   ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set

   295   /// exactly once for each BNode. The nodes with \c true value represent

   296   /// a barrier \e B, i.e. the cardinality of \e B minus the number of its

   297   /// neighbor is equal to the number of the <tt>BNode</tt>s minus the

   298   /// cardinality of the maximum matching.

   299   ///\return The cardinality of the maximum matching.

   300   ///

   301   ///\note The the implementation is based

   302   ///on the push-relabel principle.

   303   template<class Graph,class MT, class GT>

   304   int maxBpMatching(const Graph &g,MT &matching,GT &barrier)

   305   {

   306     BpMatching<Graph,MT> bpm(g,matching);

   307     int ret=bpm.run();

   308     bpm.barrier(barrier);

   309     return ret;

   310   }

   312   ///Perfect matching in a bipartite graph

   314   ///\ingroup matching

   315   ///This function checks whether the bipartite graph \c g

   316   ///has a perfect matching.

   317   ///\param g An undirected bipartite graph.

   318   ///\return \c true iff \c g has a perfect matching.

   319   ///

   320   ///\note The the implementation is based

   321   ///on the push-relabel principle.

   322   template<class Graph>

   323   bool perfectBpMatching(const Graph &g)

   324   {

   325     typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);

   326     return perfectBpMatching(g,matching);

   327   }

   329   ///Perfect matching in a bipartite graph

   331   ///\ingroup matching

   332   ///This function finds a perfect matching in a bipartite graph \c g.

   333   ///\param g An undirected bipartite graph.

   334   ///\retval matching A readwrite ANodeMap of value type \c Edge.

   335   /// The found edges will be returned in this map,

   336   /// i.e. for an \c ANode \c n,

   337   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.

   338   /// The values are unspecified if the graph

   339   /// has no perfect matching.

   340   ///\return \c true iff \c g has a perfect matching.

   341   ///

   342   ///\note The the implementation is based

   343   ///on the push-relabel principle.

   344   template<class Graph,class MT>

   345   bool perfectBpMatching(const Graph &g,MT &matching)

   346   {

   347     return BpMatching<Graph,MT>(g,matching).runPerfect()<0;

   348   }

   350   ///Perfect matching in a bipartite graph

   352   ///\ingroup matching

   353   ///This function finds a perfect matching in a bipartite graph \c g.

   354   ///\param g An undirected bipartite graph.

   355   ///\retval matching A readwrite ANodeMap of value type \c Edge.

   356   /// The found edges will be returned in this map,

   357   /// i.e. for an \c ANode \c n,

   358   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.

   359   /// The values are unspecified if the graph

   360   /// has no perfect matching.

   361   ///\retval barrier A \c bool WriteMap on the BNodes. The map will only

   362   /// be set if \c g has no perfect matching. In this case it is set

   363   /// exactly once for each BNode. The nodes with \c true value represent

   364   /// a barrier, i.e. a subset \e B a of BNodes with the property that

   365   /// the cardinality of \e B is greater than the numner of its neighbors.

   366   ///\return \c true iff \c g has a perfect matching.

   367   ///

   368   ///\note The the implementation is based

   369   ///on the push-relabel principle.

   370   template<class Graph,class MT, class GT>

   371   int perfectBpMatching(const Graph &g,MT &matching,GT &barrier)

   372   {

   373     BpMatching<Graph,MT> bpm(g,matching);

   374     int ret=bpm.run();

   375     if(ret>=0)

   376       bpm.barrier(barrier,ret);

   377     return ret<0;

   378   }

   379 }

   381 #endif

author	alpar
	Tue, 06 Feb 2007 19:16:26 +0000
changeset 2355	ac0d843b8873
child 2391	14a343be7a5a
permissions	-rw-r--r--