Changeset 1910:f95eea8c34b0 in lemon0.x for lemon/full_graph.h
 Timestamp:
 01/26/06 17:24:40 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2485
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/full_graph.h
r1909 r1910 404 404 405 405 406 class Full UBipartiteGraphBase {406 class FullBpUGraphBase { 407 407 protected: 408 408 409 int _ upperNodeNum;410 int _ lowerNodeNum;409 int _aNodeNum; 410 int _bNodeNum; 411 411 412 412 int _edgeNum; … … 416 416 class NodeSetError : public LogicError { 417 417 virtual const char* exceptionName() const { 418 return "lemon::Full UBipartiteGraph::NodeSetError";418 return "lemon::FullBpUGraph::NodeSetError"; 419 419 } 420 420 }; 421 421 422 422 class Node { 423 friend class Full UBipartiteGraphBase;423 friend class FullBpUGraphBase; 424 424 protected: 425 425 int id; … … 435 435 436 436 class Edge { 437 friend class Full UBipartiteGraphBase;437 friend class FullBpUGraphBase; 438 438 protected: 439 439 int id; … … 448 448 }; 449 449 450 void construct(int upperNodeNum, int lowerNodeNum) {451 _ upperNodeNum = upperNodeNum;452 _ lowerNodeNum = lowerNodeNum;453 _edgeNum = upperNodeNum * lowerNodeNum;454 } 455 456 void first Upper(Node& node) const {457 node.id = 2 * _ upperNodeNum  2;450 void construct(int aNodeNum, int bNodeNum) { 451 _aNodeNum = aNodeNum; 452 _bNodeNum = bNodeNum; 453 _edgeNum = aNodeNum * bNodeNum; 454 } 455 456 void firstANode(Node& node) const { 457 node.id = 2 * _aNodeNum  2; 458 458 if (node.id < 0) node.id = 1; 459 459 } 460 void next Upper(Node& node) const {460 void nextANode(Node& node) const { 461 461 node.id = 2; 462 462 if (node.id < 0) node.id = 1; 463 463 } 464 464 465 void first Lower(Node& node) const {466 node.id = 2 * _ lowerNodeNum  1;467 } 468 void next Lower(Node& node) const {465 void firstBNode(Node& node) const { 466 node.id = 2 * _bNodeNum  1; 467 } 468 void nextBNode(Node& node) const { 469 469 node.id = 2; 470 470 } 471 471 472 472 void first(Node& node) const { 473 if (_ upperNodeNum > 0) {474 node.id = 2 * _ upperNodeNum  2;473 if (_aNodeNum > 0) { 474 node.id = 2 * _aNodeNum  2; 475 475 } else { 476 node.id = 2 * _ lowerNodeNum  1;476 node.id = 2 * _bNodeNum  1; 477 477 } 478 478 } … … 480 480 node.id = 2; 481 481 if (node.id == 2) { 482 node.id = 2 * _ lowerNodeNum  1;482 node.id = 2 * _bNodeNum  1; 483 483 } 484 484 } … … 491 491 } 492 492 493 void first Down(Edge& edge, const Node& node) const {493 void firstOut(Edge& edge, const Node& node) const { 494 494 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 495 edge.id = (node.id >> 1) * _ lowerNodeNum;496 } 497 void next Down(Edge& edge) const {495 edge.id = (node.id >> 1) * _bNodeNum; 496 } 497 void nextOut(Edge& edge) const { 498 498 ++(edge.id); 499 if (edge.id % _ lowerNodeNum == 0) edge.id = 1;500 } 501 502 void first Up(Edge& edge, const Node& node) const {499 if (edge.id % _bNodeNum == 0) edge.id = 1; 500 } 501 502 void firstIn(Edge& edge, const Node& node) const { 503 503 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 504 504 edge.id = (node.id >> 1); 505 505 } 506 void next Up(Edge& edge) const {507 edge.id += _ lowerNodeNum;506 void nextIn(Edge& edge) const { 507 edge.id += _bNodeNum; 508 508 if (edge.id >= _edgeNum) edge.id = 1; 509 509 } … … 516 516 } 517 517 int maxNodeId() const { 518 return _ upperNodeNum > _lowerNodeNum ?519 _ upperNodeNum * 2  2 : _lowerNodeNum * 2  1;518 return _aNodeNum > _bNodeNum ? 519 _aNodeNum * 2  2 : _bNodeNum * 2  1; 520 520 } 521 521 … … 530 530 } 531 531 532 static int upperId(const Node& node) {532 static int aNodeId(const Node& node) { 533 533 return node.id >> 1; 534 534 } 535 static Node from UpperId(int id, Node) {535 static Node fromANodeId(int id, Node) { 536 536 return Node(id << 1); 537 537 } 538 int max UpperId() const {539 return _ upperNodeNum;540 } 541 542 static int lowerId(const Node& node) {538 int maxANodeId() const { 539 return _aNodeNum; 540 } 541 542 static int bNodeId(const Node& node) { 543 543 return node.id >> 1; 544 544 } 545 static Node from LowerId(int id) {545 static Node fromBNodeId(int id) { 546 546 return Node((id << 1) + 1); 547 547 } 548 int max LowerId() const {549 return _ lowerNodeNum;550 } 551 552 Node upperNode(const Edge& edge) const {553 return Node((edge.id / _ lowerNodeNum) << 1);554 } 555 Node lowerNode(const Edge& edge) const {556 return Node(((edge.id % _ lowerNodeNum) << 1) + 1);557 } 558 559 static bool upper(const Node& node) {548 int maxBNodeId() const { 549 return _bNodeNum; 550 } 551 552 Node aNode(const Edge& edge) const { 553 return Node((edge.id / _bNodeNum) << 1); 554 } 555 Node bNode(const Edge& edge) const { 556 return Node(((edge.id % _bNodeNum) << 1) + 1); 557 } 558 559 static bool aNode(const Node& node) { 560 560 return (node.id & 1) == 0; 561 561 } 562 562 563 static bool lower(const Node& node) {563 static bool bNode(const Node& node) { 564 564 return (node.id & 1) == 1; 565 565 } 566 566 567 static Node upperNode(int index) {567 static Node aNode(int index) { 568 568 return Node(index << 1); 569 569 } 570 570 571 static Node lowerNode(int index) {571 static Node bNode(int index) { 572 572 return Node((index << 1) + 1); 573 573 } … … 576 576 577 577 578 typedef StaticMappableUBipartiteGraphExtender< 579 IterableUBipartiteGraphExtender< 580 AlterableUBipartiteGraphExtender< 581 UBipartiteGraphExtender < 582 FullUBipartiteGraphBase> > > > 583 ExtendedFullUBipartiteGraphBase; 584 585 586 class FullUBipartiteGraph : 587 public ExtendedFullUBipartiteGraphBase { 588 public: 589 typedef ExtendedFullUBipartiteGraphBase Parent; 590 FullUBipartiteGraph(int upperNodeNum, int lowerNodeNum) { 591 Parent::construct(upperNodeNum, lowerNodeNum); 578 typedef StaticMappableBpUGraphExtender< 579 IterableBpUGraphExtender< 580 AlterableBpUGraphExtender< 581 BpUGraphExtender < 582 FullBpUGraphBase> > > > 583 ExtendedFullBpUGraphBase; 584 585 586 /// \ingroup graphs 587 /// 588 /// \brief An undirected full bipartite graph class. 589 /// 590 /// This is a simple and fast bipartite undirected full graph implementation. 591 /// It is completely static, so you can neither add nor delete either 592 /// edges or nodes. 593 /// 594 /// \sa FullGraph 595 /// 596 /// \author Balazs Dezso 597 class FullBpUGraph : 598 public ExtendedFullBpUGraphBase { 599 public: 600 typedef ExtendedFullBpUGraphBase Parent; 601 FullBpUGraph(int aNodeNum, int bNodeNum) { 602 Parent::construct(aNodeNum, bNodeNum); 592 603 } 593 604 };
Note: See TracChangeset
for help on using the changeset viewer.