Changeset 1820:22099ef840d7 in lemon0.x for lemon/full_graph.h
 Timestamp:
 11/21/05 18:48:00 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2370
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/full_graph.h
r1791 r1820 403 403 }; 404 404 405 406 class FullUndirBipartiteGraphBase { 407 protected: 408 409 int _upperNodeNum; 410 int _lowerNodeNum; 411 412 int _edgeNum; 413 414 public: 415 416 class NodeSetError : public LogicError { 417 virtual const char* exceptionName() const { 418 return "lemon::FullUndirBipartiteGraph::NodeSetError"; 419 } 420 }; 421 422 class Node { 423 friend class FullUndirBipartiteGraphBase; 424 protected: 425 int id; 426 427 Node(int _id) : id(_id) {} 428 public: 429 Node() {} 430 Node(Invalid) { id = 1; } 431 bool operator==(const Node i) const {return id==i.id;} 432 bool operator!=(const Node i) const {return id!=i.id;} 433 bool operator<(const Node i) const {return id<i.id;} 434 }; 435 436 class Edge { 437 friend class FullUndirBipartiteGraphBase; 438 protected: 439 int id; 440 441 Edge(int _id) { id = _id;} 442 public: 443 Edge() {} 444 Edge (Invalid) { id = 1; } 445 bool operator==(const Edge i) const {return id==i.id;} 446 bool operator!=(const Edge i) const {return id!=i.id;} 447 bool operator<(const Edge i) const {return id<i.id;} 448 }; 449 450 void construct(int upperNodeNum, int lowerNodeNum) { 451 _upperNodeNum = upperNodeNum; 452 _lowerNodeNum = lowerNodeNum; 453 _edgeNum = upperNodeNum * lowerNodeNum; 454 } 455 456 void firstUpper(Node& node) const { 457 node.id = 2 * _upperNodeNum  2; 458 if (node.id < 0) node.id = 1; 459 } 460 void nextUpper(Node& node) const { 461 node.id = 2; 462 if (node.id < 0) node.id = 1; 463 } 464 465 void firstLower(Node& node) const { 466 node.id = 2 * _lowerNodeNum  1; 467 } 468 void nextLower(Node& node) const { 469 node.id = 2; 470 } 471 472 void first(Node& node) const { 473 if (_upperNodeNum > 0) { 474 node.id = 2 * _upperNodeNum  2; 475 } else { 476 node.id = 2 * _lowerNodeNum  1; 477 } 478 } 479 void next(Node& node) const { 480 node.id = 2; 481 if (node.id == 2) { 482 node.id = 2 * _lowerNodeNum  1; 483 } 484 } 485 486 void first(Edge& edge) const { 487 edge.id = _edgeNum  1; 488 } 489 void next(Edge& edge) const { 490 edge.id; 491 } 492 493 void firstDown(Edge& edge, const Node& node) const { 494 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 495 edge.id = (node.id >> 1) * _lowerNodeNum; 496 } 497 void nextDown(Edge& edge) const { 498 ++(edge.id); 499 if (edge.id % _lowerNodeNum == 0) edge.id = 1; 500 } 501 502 void firstUp(Edge& edge, const Node& node) const { 503 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 504 edge.id = (node.id >> 1); 505 } 506 void nextUp(Edge& edge) const { 507 edge.id += _lowerNodeNum; 508 if (edge.id >= _edgeNum) edge.id = 1; 509 } 510 511 static int id(const Node& node) { 512 return node.id; 513 } 514 static Node nodeFromId(int id) { 515 return Node(id); 516 } 517 int maxNodeId() const { 518 return _upperNodeNum > _lowerNodeNum ? 519 _upperNodeNum * 2  2 : _lowerNodeNum * 2  1; 520 } 521 522 static int id(const Edge& edge) { 523 return edge.id; 524 } 525 static Edge edgeFromId(int id) { 526 return Edge(id); 527 } 528 int maxEdgeId() const { 529 return _edgeNum  1; 530 } 531 532 static int upperId(const Node& node) { 533 return node.id >> 1; 534 } 535 static Node fromUpperId(int id, Node) { 536 return Node(id << 1); 537 } 538 int maxUpperId() const { 539 return _upperNodeNum; 540 } 541 542 static int lowerId(const Node& node) { 543 return node.id >> 1; 544 } 545 static Node fromLowerId(int id) { 546 return Node((id << 1) + 1); 547 } 548 int maxLowerId() 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) { 560 return (node.id & 1) == 0; 561 } 562 563 static bool lower(const Node& node) { 564 return (node.id & 1) == 1; 565 } 566 567 static Node upperNode(int index) { 568 return Node(index << 1); 569 } 570 571 static Node lowerNode(int index) { 572 return Node((index << 1) + 1); 573 } 574 575 }; 576 577 578 typedef MappableUndirBipartiteGraphExtender< 579 IterableUndirBipartiteGraphExtender< 580 AlterableUndirBipartiteGraphExtender< 581 UndirBipartiteGraphExtender < 582 FullUndirBipartiteGraphBase> > > > 583 ExtendedFullUndirBipartiteGraphBase; 584 585 586 class FullUndirBipartiteGraph : 587 public ExtendedFullUndirBipartiteGraphBase { 588 public: 589 typedef ExtendedFullUndirBipartiteGraphBase Parent; 590 FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) { 591 Parent::construct(upperNodeNum, lowerNodeNum); 592 } 593 }; 594 405 595 } //namespace lemon 406 596
Note: See TracChangeset
for help on using the changeset viewer.