Changeset 2040:c7bd55c0d820 in lemon-0.x
- Timestamp:
- 04/07/06 11:51:23 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2679
- Files:
-
- 2 added
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r2038 r2040 32 32 bin_heap.h \ 33 33 bpugraph_adaptor.h \ 34 bipartite_matching.h \ 35 bucket_heap.h \ 34 36 color.h \ 35 37 config.h \ … … 54 56 johnson.h \ 55 57 kruskal.h \ 56 bucket_heap.h \57 58 list_graph.h \ 58 59 lp.h \ -
lemon/bpugraph_adaptor.h
r2031 r2040 104 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 112 typedef NodeNumTagIndicator<Graph> NodeNumTag; 107 113 int nodeNum() const { return graph->nodeNum(); } … … 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 133 UEdge addEdge(const Node& source, const Node& target) const { 127 134 return graph->addEdge(source, target); … … 282 289 283 290 /// \ingroup graph_adaptors 291 /// 292 /// \brief Trivial Bipartite Undirected Graph Adaptor 293 /// 294 /// Trivial Bipartite Undirected Graph Adaptor. It does not change 295 /// the functionality of the adapted graph. 284 296 template <typename _BpUGraph> 285 297 class BpUGraphAdaptor … … 311 323 typedef typename Parent::BNode ANode; 312 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 337 void firstANode(Node& i) const { Parent::firstBNode(i); } … … 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 -
test/Makefile.am
r2025 r2040 16 16 arborescence_test \ 17 17 bfs_test \ 18 bipartite_matching_test \ 18 19 counter_test \ 19 20 dfs_test \ … … 56 57 arborescence_test_SOURCES = arborescence_test.cc 57 58 bfs_test_SOURCES = bfs_test.cc 59 bipartite_matching_test_SOURCES = bipartite_matching_test.cc 58 60 counter_test_SOURCES = counter_test.cc 59 61 dfs_test_SOURCES = dfs_test.cc
Note: See TracChangeset
for help on using the changeset viewer.