equal
deleted
inserted
replaced
57 Elevator<Graph,typename Graph::BNode> _levels; |
57 Elevator<Graph,typename Graph::BNode> _levels; |
58 typename Graph::template BNodeMap<int> _cov; |
58 typename Graph::template BNodeMap<int> _cov; |
59 |
59 |
60 public: |
60 public: |
61 |
61 |
|
62 /// Constructor |
|
63 |
|
64 /// Constructor |
|
65 /// |
62 PrBipartiteMatching(const Graph &g) : |
66 PrBipartiteMatching(const Graph &g) : |
63 _g(g), |
67 _g(g), |
64 _node_num(countBNodes(g)), |
68 _node_num(countBNodes(g)), |
65 _matching(g), |
69 _matching(g), |
66 _levels(g,_node_num), |
70 _levels(g,_node_num), |
193 |
197 |
194 if(_levels.onLevel(actlevel)==0) |
198 if(_levels.onLevel(actlevel)==0) |
195 _levels.liftToTop(actlevel); |
199 _levels.liftToTop(actlevel); |
196 } |
200 } |
197 |
201 |
198 _matching_size = _node_num; |
202 for(ANodeIt n(_g);n!=INVALID;++n) { |
199 for(ANodeIt n(_g);n!=INVALID;++n) |
203 if (_matching[n]==INVALID)continue; |
200 if(_matching[n]==INVALID) _matching_size--; |
204 if (_cov[_g.bNode(_matching[n])]>1) { |
201 else if (_cov[_g.bNode(_matching[n])]>1) { |
|
202 _cov[_g.bNode(_matching[n])]--; |
205 _cov[_g.bNode(_matching[n])]--; |
203 _matching_size--; |
|
204 _matching[n]=INVALID; |
206 _matching[n]=INVALID; |
205 } |
207 } else { |
|
208 ++_matching_size; |
|
209 } |
|
210 } |
206 } |
211 } |
207 |
212 |
208 ///Start the algorithm to find a perfect matching |
213 ///Start the algorithm to find a perfect matching |
209 |
214 |
210 ///This function is close to identical to the simple start() |
215 ///This function is close to identical to the simple start() |
259 |
264 |
260 if(_levels.onLevel(actlevel)==0) |
265 if(_levels.onLevel(actlevel)==0) |
261 _empty_level=actlevel; |
266 _empty_level=actlevel; |
262 return false; |
267 return false; |
263 } |
268 } |
|
269 _matching_size = _node_num; |
264 return true; |
270 return true; |
265 } |
271 } |
266 |
272 |
267 ///Runs the algorithm |
273 ///Runs the algorithm |
268 |
274 |