lemon-0.x: lemon/bp_matching.h@467ca6d16556

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

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2007

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

     8  *

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

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

    11  * precise terms see the accompanying LICENSE file.

    12  *

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

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

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_BP_MATCHING

    20 #define LEMON_BP_MATCHING

    22 #include <lemon/graph_utils.h>

    23 #include <lemon/iterable_maps.h>

    24 #include <iostream>

    25 #include <queue>

    26 #include <lemon/counter.h>

    27 #include <lemon/elevator.h>

    29 ///\ingroup matching

    30 ///\file

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

    32 ///

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

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

    35 namespace lemon {

    37 #define BIPARTITE_TYPEDEFS(Graph)		\

    38   GRAPH_TYPEDEFS(Graph)				\

    39     typedef Graph::ANodeIt ANodeIt;	\

    40     typedef Graph::BNodeIt BNodeIt;

    42 #define UNDIRBIPARTITE_TYPEDEFS(Graph)		\

    43   UNDIRGRAPH_TYPEDEFS(Graph)			\

    44     typedef Graph::ANodeIt ANodeIt;	\

    45     typedef Graph::BNodeIt BNodeIt;

    47   template<class Graph,

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

    49   class BpMatching {

    50     typedef typename Graph::Node Node;

    51     typedef typename Graph::ANodeIt ANodeIt;

    52     typedef typename Graph::BNodeIt BNodeIt;

    53     typedef typename Graph::UEdge UEdge;

    54     typedef typename Graph::IncEdgeIt IncEdgeIt;

    56     const Graph &_g;

    57     int _node_num;

    58     MT &_matching;

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

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

    62   public:

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

    64       _g(g),

    65       _node_num(countBNodes(g)),

    66       _matching(matching),

    67       _levels(g,_node_num),

    68       _cov(g,0)

    69     {

    70     }

    72   private:

    73     void init()

    74     {

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

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

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

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

    80       std::queue<Node> q;

    81       _levels.initStart();

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

    83 	if(_cov[n]>1) {

    84 	  _levels.initAddItem(n);

    85 	  q.push(n);

    86 	}

    87       int hlev=0;

    88       while(!q.empty()) {

    89 	Node n=q.front();

    90 	q.pop();

    91 	int nlev=_levels[n]+1;

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

    93 	  Node m=_g.runningNode(e);

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

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

    96 	      Node r=_g.runningNode(f);

    97 	      if(_levels[r]>nlev) {

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

    99 		  _levels.initNewLevel();

   100 		_levels.initAddItem(r);

   101 		q.push(r);

   102 	      }

   103 	    }

   104 	  }

   105 	}

   106       }

   107       _levels.initFinish();

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

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

   110 	  _levels.activate(n);

   111     }

   112   public:

   113     int run()

   114     {

   115       init();

   117       Node act;

   118       Node bact=INVALID;

   119       Node last_activated=INVALID;

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

   121 // 	     last_activated:_levels.highestActive())

   122 // 	    !=INVALID)

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

   124 	last_activated=INVALID;

   125 	int actlevel=_levels[act];

   127 	UEdge bedge=INVALID;

   128 	int nlevel=_node_num;

   129 	{

   130 	  int nnlevel;

   131 	  for(IncEdgeIt tbedge(_g,act);

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

   133 	      ++tbedge)

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

   135 	       nlevel)

   136 	      {

   137 		nlevel=nnlevel;

   138 		bedge=tbedge;

   139 	      }

   140 	}

   141 	if(nlevel<_node_num) {

   142 	  if(nlevel>=actlevel)

   143 	    _levels.liftHighestActiveTo(nlevel+1);

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

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

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

   147 	    _levels.activate(bact);

   148 	    last_activated=bact;

   149 	  }

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

   151 	  _cov[act]=1;

   152 	  _levels.deactivate(act);

   153 	}

   154 	else {

   155 	  if(_node_num>actlevel)

   156 	    _levels.liftHighestActiveTo(_node_num);

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

   158 	  _levels.deactivate(act);

   159 	}

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

   162 	  _levels.liftToTop(actlevel);

   163       }

   165       int ret=_node_num;

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

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

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

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

   170 	  ret--;

   171 	  _matching[n]=INVALID;

   172 	}

   173       return ret;

   174     }

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

   177     ///if it doesn't exists

   178     int runPerfect()

   179     {

   180       init();

   182       Node act;

   183       Node bact=INVALID;

   184       Node last_activated=INVALID;

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

   186 	last_activated=INVALID;

   187 	int actlevel=_levels[act];

   189 	UEdge bedge=INVALID;

   190 	int nlevel=_node_num;

   191 	{

   192 	  int nnlevel;

   193 	  for(IncEdgeIt tbedge(_g,act);

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

   195 	      ++tbedge)

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

   197 	       nlevel)

   198 	      {

   199 		nlevel=nnlevel;

   200 		bedge=tbedge;

   201 	      }

   202 	}

   203 	if(nlevel<_node_num) {

   204 	  if(nlevel>=actlevel)

   205 	    _levels.liftHighestActiveTo(nlevel+1);

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

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

   208 	    _levels.activate(bact);

   209 	    last_activated=bact;

   210 	  }

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

   212 	  _cov[act]=1;

   213 	  _levels.deactivate(act);

   214 	}

   215 	else {

   216 	  if(_node_num>actlevel)

   217 	    _levels.liftHighestActiveTo(_node_num);

   218 	  _levels.deactivate(act);

   219 	}

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

   222 	  return actlevel;

   223       }

   224       return -1;

   225     }

   227     template<class GT>

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

   229     {

   230       if(empty_level==-1)

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

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

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

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

   235     }

   236     template<class GT>

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

   238     {

   239       if(empty_level==-1)

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

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

   242     }

   244   };

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

   249   ///\ingroup matching

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

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

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

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

   254   ///

   255   ///\note The the implementation is based

   256   ///on the push-relabel principle.

   257   template<class Graph>

   258   int maxBpMatching(const Graph &g)

   259   {

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

   261     return maxBpMatching(g,matching);

   262   }

   264   ///Maximum cardinality matching in a bipartite graph

   266   ///\ingroup matching

   267   ///This function finds a maximum cardinality matching

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

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

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

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

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

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

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

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

   276   ///

   277   ///\note The the implementation is based

   278   ///on the push-relabel principle.

   279   template<class Graph,class MT>

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

   281   {

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

   283   }

   285   ///Maximum cardinality matching in a bipartite graph

   287   ///\ingroup matching

   288   ///This function finds a maximum cardinality matching

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

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

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

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

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

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

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

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

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

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

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

   300   /// cardinality of the maximum matching.

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

   302   ///

   303   ///\note The the implementation is based

   304   ///on the push-relabel principle.

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

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

   307   {

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

   309     int ret=bpm.run();

   310     bpm.barrier(barrier);

   311     return ret;

   312   }

   314   ///Perfect matching in a bipartite graph

   316   ///\ingroup matching

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

   318   ///has a perfect matching.

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

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

   321   ///

   322   ///\note The the implementation is based

   323   ///on the push-relabel principle.

   324   template<class Graph>

   325   bool perfectBpMatching(const Graph &g)

   326   {

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

   328     return perfectBpMatching(g,matching);

   329   }

   331   ///Perfect matching in a bipartite graph

   333   ///\ingroup matching

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

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

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

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

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

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

   340   /// The values are unspecified if the graph

   341   /// has no perfect matching.

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

   343   ///

   344   ///\note The the implementation is based

   345   ///on the push-relabel principle.

   346   template<class Graph,class MT>

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

   348   {

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

   350   }

   352   ///Perfect matching in a bipartite graph

   354   ///\ingroup matching

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

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

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

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

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

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

   361   /// The values are unspecified if the graph

   362   /// has no perfect matching.

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

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

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

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

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

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

   369   ///

   370   ///\note The the implementation is based

   371   ///on the push-relabel principle.

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

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

   374   {

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

   376     int ret=bpm.run();

   377     if(ret>=0)

   378       bpm.barrier(barrier,ret);

   379     return ret<0;

   380   }

   381 }

   383 #endif

author	alpar
	Tue, 13 Mar 2007 15:42:06 +0000
changeset 2408	467ca6d16556
parent 2353	c43f8802c90a
permissions	-rw-r--r--