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 |
|
35 namespace 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 |
|