101 Node target(const UEdge& e) const { return graph->target(e); } |
101 Node target(const UEdge& e) const { return graph->target(e); } |
102 |
102 |
103 Node source(const Edge& e) const { return graph->source(e); } |
103 Node source(const Edge& e) const { return graph->source(e); } |
104 Node target(const Edge& e) const { return graph->target(e); } |
104 Node target(const Edge& e) const { return graph->target(e); } |
105 |
105 |
|
106 Node aNode(const UEdge& e) const { return graph->aNode(e); } |
|
107 Node bNode(const UEdge& e) const { return graph->bNode(e); } |
|
108 |
|
109 bool aNode(const Node& n) const { return graph->aNode(n); } |
|
110 bool bNode(const Node& n) const { return graph->bNode(n); } |
|
111 |
106 typedef NodeNumTagIndicator<Graph> NodeNumTag; |
112 typedef NodeNumTagIndicator<Graph> NodeNumTag; |
107 int nodeNum() const { return graph->nodeNum(); } |
113 int nodeNum() const { return graph->nodeNum(); } |
108 int aNodeNum() const { return graph->aNodeNum(); } |
114 int aNodeNum() const { return graph->aNodeNum(); } |
109 int bNodeNum() const { return graph->bNodeNum(); } |
115 int bNodeNum() const { return graph->bNodeNum(); } |
110 |
116 |
120 UEdge findUEdge(const Node& source, const Node& target, |
126 UEdge findUEdge(const Node& source, const Node& target, |
121 const UEdge& prev = INVALID) { |
127 const UEdge& prev = INVALID) { |
122 return graph->findUEdge(source, target, prev); |
128 return graph->findUEdge(source, target, prev); |
123 } |
129 } |
124 |
130 |
125 Node addNode() const { return graph->addNode(); } |
131 Node addANode() const { return graph->addANode(); } |
|
132 Node addBNode() const { return graph->addBNode(); } |
126 UEdge addEdge(const Node& source, const Node& target) const { |
133 UEdge addEdge(const Node& source, const Node& target) const { |
127 return graph->addEdge(source, target); |
134 return graph->addEdge(source, target); |
128 } |
135 } |
129 |
136 |
130 void erase(const Node& i) const { graph->erase(i); } |
137 void erase(const Node& i) const { graph->erase(i); } |
308 public: |
320 public: |
309 |
321 |
310 typedef typename Parent::Node Node; |
322 typedef typename Parent::Node Node; |
311 typedef typename Parent::BNode ANode; |
323 typedef typename Parent::BNode ANode; |
312 typedef typename Parent::ANode BNode; |
324 typedef typename Parent::ANode BNode; |
|
325 typedef typename Parent::Edge Edge; |
|
326 typedef typename Parent::UEdge UEdge; |
|
327 |
|
328 bool direction(const Edge& e) const { return !Parent::direction(e); } |
|
329 Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); } |
|
330 |
|
331 Node aNode(const UEdge& e) const { return Parent::bNode(e); } |
|
332 Node bNode(const UEdge& e) const { return Parent::aNode(e); } |
|
333 |
|
334 bool aNode(const Node& n) const { return Parent::bNode(n); } |
|
335 bool bNode(const Node& n) const { return Parent::aNode(n); } |
313 |
336 |
314 void firstANode(Node& i) const { Parent::firstBNode(i); } |
337 void firstANode(Node& i) const { Parent::firstBNode(i); } |
315 void firstBNode(Node& i) const { Parent::firstANode(i); } |
338 void firstBNode(Node& i) const { Parent::firstANode(i); } |
316 |
339 |
317 void nextANode(Node& i) const { Parent::nextBNode(i); } |
340 void nextANode(Node& i) const { Parent::nextBNode(i); } |
405 explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); } |
428 explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); } |
406 |
429 |
407 }; |
430 }; |
408 |
431 |
409 |
432 |
|
433 template <typename _BpUGraph, |
|
434 typename _ANMatchingMap, typename _BNMatchingMap> |
|
435 class MatchingBpUGraphAdaptorBase |
|
436 : public BpUGraphAdaptorBase<const _BpUGraph> |
|
437 { |
|
438 public: |
|
439 |
|
440 typedef _BpUGraph Graph; |
|
441 typedef _ANMatchingMap ANodeMatchingMap; |
|
442 typedef _BNMatchingMap BNodeMatchingMap; |
|
443 |
|
444 typedef BpUGraphAdaptorBase<const _BpUGraph> Parent; |
|
445 |
|
446 protected: |
|
447 |
|
448 MatchingBpUGraphAdaptorBase() {} |
|
449 |
|
450 void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) { |
|
451 anode_matching = &_anode_matching; |
|
452 } |
|
453 |
|
454 void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) { |
|
455 bnode_matching = &_bnode_matching; |
|
456 } |
|
457 |
|
458 public: |
|
459 |
|
460 typedef typename Parent::Node Node; |
|
461 typedef typename Parent::Edge Edge; |
|
462 |
|
463 void firstOut(Edge& edge, const Node& node) const { |
|
464 if (Parent::aNode(node)) { |
|
465 Parent::firstOut(edge, node); |
|
466 if (edge != INVALID && (*anode_matching)[node] == edge) { |
|
467 Parent::nextOut(edge); |
|
468 } |
|
469 } else { |
|
470 edge = (*bnode_matching)[node] != INVALID ? |
|
471 Parent::direct((*bnode_matching)[node], false) : INVALID; |
|
472 } |
|
473 } |
|
474 |
|
475 void nextOut(Edge& edge) const { |
|
476 if (Parent::aNode(Parent::source(edge))) { |
|
477 Parent::nextOut(edge); |
|
478 if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) { |
|
479 Parent::nextOut(edge); |
|
480 } |
|
481 } else { |
|
482 edge = INVALID; |
|
483 } |
|
484 } |
|
485 |
|
486 void firstIn(Edge& edge, const Node& node) const { |
|
487 if (Parent::aNode(node)) { |
|
488 edge = (*bnode_matching)[node] != INVALID ? |
|
489 Parent::direct((*anode_matching)[node], false) : INVALID; |
|
490 } else { |
|
491 Parent::firstIn(edge, node); |
|
492 if (edge != INVALID && (*bnode_matching)[node] == edge) { |
|
493 Parent::nextIn(edge); |
|
494 } |
|
495 } |
|
496 } |
|
497 |
|
498 void nextIn(Edge& edge) const { |
|
499 if (Parent::aNode(Parent::target(edge))) { |
|
500 edge = INVALID; |
|
501 } else { |
|
502 Parent::nextIn(edge); |
|
503 if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) { |
|
504 Parent::nextIn(edge); |
|
505 } |
|
506 } |
|
507 } |
|
508 |
|
509 private: |
|
510 ANodeMatchingMap* anode_matching; |
|
511 BNodeMatchingMap* bnode_matching; |
|
512 }; |
|
513 |
|
514 |
|
515 /// \ingroup graph_adaptors |
|
516 /// |
|
517 /// \brief Bipartite graph adaptor to implement matching algorithms. |
|
518 /// |
|
519 /// Bipartite graph adaptor to implement matchings. It implements |
|
520 /// the residual graph of the matching. |
|
521 template <typename _BpUGraph, |
|
522 typename _ANMatchingMap, typename _BNMatchingMap> |
|
523 class MatchingBpUGraphAdaptor |
|
524 : public BpUGraphAdaptorExtender< |
|
525 MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> > |
|
526 { |
|
527 public: |
|
528 |
|
529 typedef _BpUGraph BpUGraph; |
|
530 typedef _BpUGraph Graph; |
|
531 typedef _ANMatchingMap ANodeMatchingMap; |
|
532 typedef _BNMatchingMap BNodeMatchingMap; |
|
533 typedef BpUGraphAdaptorExtender< |
|
534 MatchingBpUGraphAdaptorBase<BpUGraph, |
|
535 ANodeMatchingMap, BNodeMatchingMap> > |
|
536 Parent; |
|
537 |
|
538 protected: |
|
539 MatchingBpUGraphAdaptor() : Parent() {} |
|
540 |
|
541 public: |
|
542 |
|
543 MatchingBpUGraphAdaptor(const Graph& _graph, |
|
544 ANodeMatchingMap& _anode_matching, |
|
545 BNodeMatchingMap& _bnode_matching) { |
|
546 setGraph(_graph); |
|
547 setANodeMatchingMap(_anode_matching); |
|
548 setBNodeMatchingMap(_bnode_matching); |
|
549 } |
|
550 |
|
551 }; |
|
552 |
410 } |
553 } |
411 |
554 |
412 #endif |
555 #endif |