COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bp_matching.h @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2353:c43f8802c90a, checked in by Alpar Juttner, 13 years ago

A push/relabel type max cardinality matching implementation.
(slightly incompatible with bipartite_matching.h)

File size: 10.9 KB
Line 
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 */
16
17#ifndef LEMON_BP_MATCHING
18#define LEMON_BP_MATCHING
19
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>
26
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
33namespace lemon {
34
35#define BIPARTITE_TYPEDEFS(Graph)               \
36  GRAPH_TYPEDEFS(Graph)                         \
37    typedef Graph::ANodeIt ANodeIt;     \
38    typedef Graph::BNodeIt BNodeIt;
39
40#define UNDIRBIPARTITE_TYPEDEFS(Graph)          \
41  UNDIRGRAPH_TYPEDEFS(Graph)                    \
42    typedef Graph::ANodeIt ANodeIt;     \
43    typedef Graph::BNodeIt BNodeIt;
44
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;
53   
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;
59
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    }
69   
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])];
77
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();
114
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];
124       
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        }
158
159        if(_levels.onLevel(actlevel)==0)
160          _levels.liftToTop(actlevel);
161      }
162     
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    }
173   
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();
179
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];
186       
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        }
218
219        if(_levels.onLevel(actlevel)==0)
220          return actlevel;
221      }
222      return -1;
223    }
224 
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    } 
241 
242  };
243 
244 
245  ///Maximum cardinality of the matchings in a bipartite graph
246
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  }
261
262  ///Maximum cardinality matching in a bipartite graph
263
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  }
282
283  ///Maximum cardinality matching in a bipartite graph
284
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  } 
311
312  ///Perfect matching in a bipartite graph
313
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  }
328
329  ///Perfect matching in a bipartite graph
330
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  }
349
350  ///Perfect matching in a bipartite graph
351
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}
380
381#endif
Note: See TracBrowser for help on using the repository browser.