313 /// functions.\n |
313 /// functions.\n |
314 /// Before the use of these functions, |
314 /// Before the use of these functions, |
315 /// either run() or start() must be called. |
315 /// either run() or start() must be called. |
316 ///@{ |
316 ///@{ |
317 |
317 |
318 /// \brief Set true all matching uedge in the map. |
318 ///Set true all matching uedge in the map. |
319 /// |
319 |
320 /// Set true all matching uedge in the map. It does not change the |
320 ///Set true all matching uedge in the map. It does not change the |
321 /// value mapped to the other uedges. |
321 ///value mapped to the other uedges. |
322 /// \return The number of the matching edges. |
322 ///\return The number of the matching edges. |
323 template <typename MatchingMap> |
323 template <typename MatchingMap> |
324 int quickMatching(MatchingMap& mm) const { |
324 int quickMatching(MatchingMap& mm) const { |
325 for (ANodeIt n(_g);n!=INVALID;++n) { |
325 for (ANodeIt n(_g);n!=INVALID;++n) { |
326 if (_matching[n]!=INVALID) mm.set(_matching[n],true); |
326 if (_matching[n]!=INVALID) mm.set(_matching[n],true); |
327 } |
327 } |
328 return _matching_size; |
328 return _matching_size; |
329 } |
329 } |
330 |
330 |
331 ///\brief Set true all matching uedge in the map and the others to false. |
331 ///Set true all matching uedge in the map and the others to false. |
332 |
332 |
333 ///Set true all matching uedge in the map and the others to false. |
333 ///Set true all matching uedge in the map and the others to false. |
334 ///\return The number of the matching edges. |
334 ///\return The number of the matching edges. |
335 template<class MatchingMap> |
335 template<class MatchingMap> |
336 int matching(MatchingMap& mm) const { |
336 int matching(MatchingMap& mm) const { |
337 for (UEdgeIt e(_g);e!=INVALID;++e) { |
337 for (UEdgeIt e(_g);e!=INVALID;++e) { |
338 mm.set(e,e==_matching[_g.aNode(e)]); |
338 mm.set(e,e==_matching[_g.aNode(e)]); |
|
339 } |
|
340 return _matching_size; |
|
341 } |
|
342 |
|
343 ///Gives back the matching in an ANodeMap. |
|
344 |
|
345 ///Gives back the matching in an ANodeMap. The parameter should |
|
346 ///be a write ANodeMap of UEdge values. |
|
347 ///\return The number of the matching edges. |
|
348 template<class MatchingMap> |
|
349 int aMatching(MatchingMap& mm) const { |
|
350 for (ANodeIt n(_g);n!=INVALID;++n) { |
|
351 mm.set(n,_matching[n]); |
|
352 } |
|
353 return _matching_size; |
|
354 } |
|
355 |
|
356 ///Gives back the matching in a BNodeMap. |
|
357 |
|
358 ///Gives back the matching in a BNodeMap. The parameter should |
|
359 ///be a write BNodeMap of UEdge values. |
|
360 ///\return The number of the matching edges. |
|
361 template<class MatchingMap> |
|
362 int bMatching(MatchingMap& mm) const { |
|
363 for (BNodeIt n(_g);n!=INVALID;++n) { |
|
364 mm.set(n,INVALID); |
|
365 } |
|
366 for (ANodeIt n(_g);n!=INVALID;++n) { |
|
367 if (_matching[n]!=INVALID) |
|
368 mm.set(_g.bNode(_matching[n]),_matching[n]); |
339 } |
369 } |
340 return _matching_size; |
370 return _matching_size; |
341 } |
371 } |
342 |
372 |
343 |
373 |
455 |
485 |
456 ///\ingroup matching |
486 ///\ingroup matching |
457 ///This function finds a maximum cardinality matching |
487 ///This function finds a maximum cardinality matching |
458 ///in a bipartite graph \c g. |
488 ///in a bipartite graph \c g. |
459 ///\param g An undirected bipartite graph. |
489 ///\param g An undirected bipartite graph. |
460 ///\retval matching A write UEdgeMap of value type \c bool. |
490 ///\retval matching A write ANodeMap of value type \c UEdge. |
461 /// The found edges will be returned in this map. |
491 /// The found edges will be returned in this map, |
|
492 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one |
|
493 /// that covers the node \c n. |
462 ///\return The cardinality of the maximum matching. |
494 ///\return The cardinality of the maximum matching. |
463 /// |
495 /// |
464 ///\note The the implementation is based |
496 ///\note The the implementation is based |
465 ///on the push-relabel principle. |
497 ///on the push-relabel principle. |
466 template<class Graph,class MT> |
498 template<class Graph,class MT> |
467 int prBipartiteMatching(const Graph &g,MT &matching) |
499 int prBipartiteMatching(const Graph &g,MT &matching) |
468 { |
500 { |
469 PrBipartiteMatching<Graph> bpm(g); |
501 PrBipartiteMatching<Graph> bpm(g); |
470 bpm.run(); |
502 bpm.run(); |
471 bpm.matching(matching); |
503 bpm.aMatching(matching); |
472 return bpm.matchingSize(); |
504 return bpm.matchingSize(); |
473 } |
505 } |
474 |
506 |
475 ///Maximum cardinality matching in a bipartite graph |
507 ///Maximum cardinality matching in a bipartite graph |
476 |
508 |
477 ///\ingroup matching |
509 ///\ingroup matching |
478 ///This function finds a maximum cardinality matching |
510 ///This function finds a maximum cardinality matching |
479 ///in a bipartite graph \c g. |
511 ///in a bipartite graph \c g. |
480 ///\param g An undirected bipartite graph. |
512 ///\param g An undirected bipartite graph. |
481 ///\retval matching A write UEdgeMap of value type \c bool. |
513 ///\retval matching A write ANodeMap of value type \c UEdge. |
482 /// The found edges will be returned in this map. |
514 /// The found edges will be returned in this map, |
|
515 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one |
|
516 /// that covers the node \c n. |
483 ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set |
517 ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set |
484 /// exactly once for each BNode. The nodes with \c true value represent |
518 /// exactly once for each BNode. The nodes with \c true value represent |
485 /// a barrier \e B, i.e. the cardinality of \e B minus the number of its |
519 /// a barrier \e B, i.e. the cardinality of \e B minus the number of its |
486 /// neighbor is equal to the number of the <tt>BNode</tt>s minus the |
520 /// neighbor is equal to the number of the <tt>BNode</tt>s minus the |
487 /// cardinality of the maximum matching. |
521 /// cardinality of the maximum matching. |
492 template<class Graph,class MT, class GT> |
526 template<class Graph,class MT, class GT> |
493 int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier) |
527 int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier) |
494 { |
528 { |
495 PrBipartiteMatching<Graph> bpm(g); |
529 PrBipartiteMatching<Graph> bpm(g); |
496 bpm.run(); |
530 bpm.run(); |
497 bpm.matching(matching); |
531 bpm.aMatching(matching); |
498 bpm.bBarrier(barrier); |
532 bpm.bBarrier(barrier); |
499 return bpm.matchingSize(); |
533 return bpm.matchingSize(); |
500 } |
534 } |
501 |
535 |
502 ///Perfect matching in a bipartite graph |
536 ///Perfect matching in a bipartite graph |
519 ///Perfect matching in a bipartite graph |
553 ///Perfect matching in a bipartite graph |
520 |
554 |
521 ///\ingroup matching |
555 ///\ingroup matching |
522 ///This function finds a perfect matching in a bipartite graph \c g. |
556 ///This function finds a perfect matching in a bipartite graph \c g. |
523 ///\param g An undirected bipartite graph. |
557 ///\param g An undirected bipartite graph. |
524 ///\retval matching A write UEdgeMap of value type \c bool. |
558 ///\retval matching A write ANodeMap of value type \c UEdge. |
525 /// The found edges will be returned in this map. |
559 /// The found edges will be returned in this map, |
|
560 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one |
|
561 /// that covers the node \c n. |
526 /// The values are unchanged if the graph |
562 /// The values are unchanged if the graph |
527 /// has no perfect matching. |
563 /// has no perfect matching. |
528 ///\return \c true iff \c g has a perfect matching. |
564 ///\return \c true iff \c g has a perfect matching. |
529 /// |
565 /// |
530 ///\note The the implementation is based |
566 ///\note The the implementation is based |
531 ///on the push-relabel principle. |
567 ///on the push-relabel principle. |
532 template<class Graph,class MT> |
568 template<class Graph,class MT> |
533 bool prPerfectBipartiteMatching(const Graph &g,MT &matching) |
569 bool prPerfectBipartiteMatching(const Graph &g,MT &matching) |
534 { |
570 { |
535 PrBipartiteMatching<Graph> bpm(g); |
571 PrBipartiteMatching<Graph> bpm(g); |
536 bool ret = bpm.runPerfect(); |
572 bool ret = bpm.checkedRunPerfect(); |
537 if (ret) bpm.matching(matching); |
573 if (ret) bpm.aMatching(matching); |
538 return ret; |
574 return ret; |
539 } |
575 } |
540 |
576 |
541 ///Perfect matching in a bipartite graph |
577 ///Perfect matching in a bipartite graph |
542 |
578 |
543 ///\ingroup matching |
579 ///\ingroup matching |
544 ///This function finds a perfect matching in a bipartite graph \c g. |
580 ///This function finds a perfect matching in a bipartite graph \c g. |
545 ///\param g An undirected bipartite graph. |
581 ///\param g An undirected bipartite graph. |
546 ///\retval matching A readwrite UEdgeMap of value type \c bool. |
582 ///\retval matching A write ANodeMap of value type \c UEdge. |
547 /// The found edges will be returned in this map. |
583 /// The found edges will be returned in this map, |
|
584 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one |
|
585 /// that covers the node \c n. |
548 /// The values are unchanged if the graph |
586 /// The values are unchanged if the graph |
549 /// has no perfect matching. |
587 /// has no perfect matching. |
550 ///\retval barrier A \c bool WriteMap on the BNodes. The map will only |
588 ///\retval barrier A \c bool WriteMap on the BNodes. The map will only |
551 /// be set if \c g has no perfect matching. In this case it is set |
589 /// be set if \c g has no perfect matching. In this case it is set |
552 /// exactly once for each BNode. The nodes with \c true value represent |
590 /// exactly once for each BNode. The nodes with \c true value represent |
555 ///\return \c true iff \c g has a perfect matching. |
593 ///\return \c true iff \c g has a perfect matching. |
556 /// |
594 /// |
557 ///\note The the implementation is based |
595 ///\note The the implementation is based |
558 ///on the push-relabel principle. |
596 ///on the push-relabel principle. |
559 template<class Graph,class MT, class GT> |
597 template<class Graph,class MT, class GT> |
560 int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) |
598 bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) |
561 { |
599 { |
562 PrBipartiteMatching<Graph> bpm(g); |
600 PrBipartiteMatching<Graph> bpm(g); |
563 bool ret=bpm.runPerfect(); |
601 bool ret=bpm.checkedRunPerfect(); |
564 if(ret) |
602 if(ret) |
565 bpm.matching(matching); |
603 bpm.aMatching(matching); |
566 else |
604 else |
567 bpm.bBarrier(barrier); |
605 bpm.bBarrier(barrier); |
568 return ret; |
606 return ret; |
569 } |
607 } |
570 } |
608 } |