Changeset 1910:f95eea8c34b0 in lemon-0.x for lemon/smart_graph.h
- Timestamp:
- 01/26/06 17:24:40 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2485
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/smart_graph.h
r1909 r1910 379 379 380 380 381 class Smart UBipartiteGraphBase {381 class SmartBpUGraphBase { 382 382 public: 383 383 384 384 class NodeSetError : public LogicError { 385 385 virtual const char* exceptionName() const { 386 return "lemon:: FullUBipartiteGraph::NodeSetError";386 return "lemon::SmartBpUGraph::NodeSetError"; 387 387 } 388 388 }; … … 397 397 398 398 struct EdgeT { 399 int upper, next_down;400 int lower, next_up;401 }; 402 403 std::vector<NodeT> upperNodes;404 std::vector<NodeT> lowerNodes;399 int aNode, next_out; 400 int bNode, next_in; 401 }; 402 403 std::vector<NodeT> aNodes; 404 std::vector<NodeT> bNodes; 405 405 406 406 std::vector<EdgeT> edges; … … 409 409 410 410 class Node { 411 friend class Smart UBipartiteGraphBase;411 friend class SmartBpUGraphBase; 412 412 protected: 413 413 int id; … … 423 423 424 424 class Edge { 425 friend class Smart UBipartiteGraphBase;425 friend class SmartBpUGraphBase; 426 426 protected: 427 427 int id; … … 436 436 }; 437 437 438 void first Upper(Node& node) const {439 node.id = 2 * upperNodes.size() - 2;438 void firstANode(Node& node) const { 439 node.id = 2 * aNodes.size() - 2; 440 440 if (node.id < 0) node.id = -1; 441 441 } 442 void next Upper(Node& node) const {442 void nextANode(Node& node) const { 443 443 node.id -= 2; 444 444 if (node.id < 0) node.id = -1; 445 445 } 446 446 447 void first Lower(Node& node) const {448 node.id = 2 * lowerNodes.size() - 1;449 } 450 void next Lower(Node& node) const {447 void firstBNode(Node& node) const { 448 node.id = 2 * bNodes.size() - 1; 449 } 450 void nextBNode(Node& node) const { 451 451 node.id -= 2; 452 452 } 453 453 454 454 void first(Node& node) const { 455 if ( upperNodes.size() > 0) {456 node.id = 2 * upperNodes.size() - 2;455 if (aNodes.size() > 0) { 456 node.id = 2 * aNodes.size() - 2; 457 457 } else { 458 node.id = 2 * lowerNodes.size() - 1;458 node.id = 2 * bNodes.size() - 1; 459 459 } 460 460 } … … 462 462 node.id -= 2; 463 463 if (node.id == -2) { 464 node.id = 2 * lowerNodes.size() - 1;464 node.id = 2 * bNodes.size() - 1; 465 465 } 466 466 } … … 473 473 } 474 474 475 void first Down(Edge& edge, const Node& node) const {475 void firstOut(Edge& edge, const Node& node) const { 476 476 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 477 edge.id = upperNodes[node.id >> 1].first;478 } 479 void next Down(Edge& edge) const {480 edge.id = edges[edge.id].next_ down;481 } 482 483 void first Up(Edge& edge, const Node& node) const {477 edge.id = aNodes[node.id >> 1].first; 478 } 479 void nextOut(Edge& edge) const { 480 edge.id = edges[edge.id].next_out; 481 } 482 483 void firstIn(Edge& edge, const Node& node) const { 484 484 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 485 edge.id = lowerNodes[node.id >> 1].first;486 } 487 void next Up(Edge& edge) const {488 edge.id = edges[edge.id].next_ up;485 edge.id = bNodes[node.id >> 1].first; 486 } 487 void nextIn(Edge& edge) const { 488 edge.id = edges[edge.id].next_in; 489 489 } 490 490 … … 496 496 } 497 497 int maxNodeId() const { 498 return upperNodes.size() > lowerNodes.size() ?499 upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;498 return aNodes.size() > bNodes.size() ? 499 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; 500 500 } 501 501 … … 510 510 } 511 511 512 static int upperId(const Node& node) {512 static int aNodeId(const Node& node) { 513 513 return node.id >> 1; 514 514 } 515 static Node from UpperId(int id, Node) {515 static Node fromANodeId(int id, Node) { 516 516 return Node(id << 1); 517 517 } 518 int max UpperId() const {519 return upperNodes.size();520 } 521 522 static int lowerId(const Node& node) {518 int maxANodeId() const { 519 return aNodes.size(); 520 } 521 522 static int bNodeId(const Node& node) { 523 523 return node.id >> 1; 524 524 } 525 static Node from LowerId(int id) {525 static Node fromBNodeId(int id) { 526 526 return Node((id << 1) + 1); 527 527 } 528 int max LowerId() const {529 return lowerNodes.size();530 } 531 532 Node upperNode(const Edge& edge) const {533 return Node(edges[edge.id]. upper);534 } 535 Node lowerNode(const Edge& edge) const {536 return Node(edges[edge.id]. lower);537 } 538 539 static bool upper(const Node& node) {528 int maxBNodeId() const { 529 return bNodes.size(); 530 } 531 532 Node aNode(const Edge& edge) const { 533 return Node(edges[edge.id].aNode); 534 } 535 Node bNode(const Edge& edge) const { 536 return Node(edges[edge.id].bNode); 537 } 538 539 static bool aNode(const Node& node) { 540 540 return (node.id & 1) == 0; 541 541 } 542 542 543 static bool lower(const Node& node) {543 static bool bNode(const Node& node) { 544 544 return (node.id & 1) == 1; 545 545 } 546 546 547 Node add UpperNode() {547 Node addANode() { 548 548 NodeT nodeT; 549 549 nodeT.first = -1; 550 upperNodes.push_back(nodeT);551 return Node( upperNodes.size() * 2 - 2);552 } 553 554 Node add LowerNode() {550 aNodes.push_back(nodeT); 551 return Node(aNodes.size() * 2 - 2); 552 } 553 554 Node addBNode() { 555 555 NodeT nodeT; 556 556 nodeT.first = -1; 557 lowerNodes.push_back(nodeT);558 return Node( lowerNodes.size() * 2 - 1);557 bNodes.push_back(nodeT); 558 return Node(bNodes.size() * 2 - 1); 559 559 } 560 560 … … 563 563 EdgeT edgeT; 564 564 if ((source.id & 1) == 0) { 565 edgeT. upper= source.id;566 edgeT. lower= target.id;565 edgeT.aNode = source.id; 566 edgeT.bNode = target.id; 567 567 } else { 568 edgeT. upper= target.id;569 edgeT. lower= source.id;570 } 571 edgeT.next_ down = upperNodes[edgeT.upper>> 1].first;572 upperNodes[edgeT.upper>> 1].first = edges.size();573 edgeT.next_ up = lowerNodes[edgeT.lower>> 1].first;574 lowerNodes[edgeT.lower>> 1].first = edges.size();568 edgeT.aNode = target.id; 569 edgeT.bNode = source.id; 570 } 571 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; 572 aNodes[edgeT.aNode >> 1].first = edges.size(); 573 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; 574 bNodes[edgeT.bNode >> 1].first = edges.size(); 575 575 edges.push_back(edgeT); 576 576 return Edge(edges.size() - 1); … … 578 578 579 579 void clear() { 580 upperNodes.clear();581 lowerNodes.clear();580 aNodes.clear(); 581 bNodes.clear(); 582 582 edges.clear(); 583 583 } … … 586 586 587 587 588 typedef ClearableUBipartiteGraphExtender< 589 ExtendableUBipartiteGraphExtender< 590 MappableUBipartiteGraphExtender< 591 IterableUBipartiteGraphExtender< 592 AlterableUBipartiteGraphExtender< 593 UBipartiteGraphExtender < 594 SmartUBipartiteGraphBase> > > > > > 595 ExtendedSmartUBipartiteGraphBase; 596 597 598 class SmartUBipartiteGraph : 599 public ExtendedSmartUBipartiteGraphBase { 600 }; 588 typedef ClearableBpUGraphExtender< 589 ExtendableBpUGraphExtender< 590 MappableBpUGraphExtender< 591 IterableBpUGraphExtender< 592 AlterableBpUGraphExtender< 593 BpUGraphExtender < 594 SmartBpUGraphBase> > > > > > 595 ExtendedSmartBpUGraphBase; 596 597 /// \ingroup graphs 598 /// 599 /// \brief A smart bipartite undirected graph class. 600 /// 601 /// This is a simple and fast bipartite undirected graph implementation. 602 /// It is also quite memory efficient, but at the price 603 /// that <b> it does not support node and edge deletions</b>. 604 /// Except from this it conforms to 605 /// the \ref concept::BpUGraph "BpUGraph" concept. 606 /// \sa concept::BpUGraph. 607 /// 608 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; 601 609 602 610
Note: See TracChangeset
for help on using the changeset viewer.