COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bp_matching.h @ 2428:c06e86364234

Last change on this file since 2428:c06e86364234 was 2391:14a343be7a5a, checked in by Alpar Juttner, 17 years ago

Happy New Year to all source files!

File size: 10.9 KB
Line 
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 */
18
19#ifndef LEMON_BP_MATCHING
20#define LEMON_BP_MATCHING
21
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>
28
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
35namespace lemon {
36
37#define BIPARTITE_TYPEDEFS(Graph)               \
38  GRAPH_TYPEDEFS(Graph)                         \
39    typedef Graph::ANodeIt ANodeIt;     \
40    typedef Graph::BNodeIt BNodeIt;
41
42#define UNDIRBIPARTITE_TYPEDEFS(Graph)          \
43  UNDIRGRAPH_TYPEDEFS(Graph)                    \
44    typedef Graph::ANodeIt ANodeIt;     \
45    typedef Graph::BNodeIt BNodeIt;
46
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;
55   
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;
61
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    }
71   
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])];
79
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();
116
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];
126       
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        }
160
161        if(_levels.onLevel(actlevel)==0)
162          _levels.liftToTop(actlevel);
163      }
164     
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    }
175   
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();
181
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];
188       
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        }
220
221        if(_levels.onLevel(actlevel)==0)
222          return actlevel;
223      }
224      return -1;
225    }
226 
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    } 
243 
244  };
245 
246 
247  ///Maximum cardinality of the matchings in a bipartite graph
248
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  }
263
264  ///Maximum cardinality matching in a bipartite graph
265
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  }
284
285  ///Maximum cardinality matching in a bipartite graph
286
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  } 
313
314  ///Perfect matching in a bipartite graph
315
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  }
330
331  ///Perfect matching in a bipartite graph
332
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  }
351
352  ///Perfect matching in a bipartite graph
353
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}
382
383#endif
Note: See TracBrowser for help on using the repository browser.