Changeset 2231:06faf3f06d67 in lemon-0.x for lemon/bits
- Timestamp:
- 10/03/06 13:46:39 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2973
- Location:
- lemon/bits
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/base_extender.h
r2222 r2231 280 280 }; 281 281 282 template <typename Base> 283 class BidirBpUGraphExtender : public Base { 284 public: 285 typedef Base Parent; 286 typedef BidirBpUGraphExtender Graph; 287 288 typedef typename Parent::Node Node; 289 typedef typename Parent::UEdge UEdge; 290 291 292 using Parent::first; 293 using Parent::next; 294 295 using Parent::id; 296 297 class ANode : public Node { 298 friend class BidirBpUGraphExtender; 299 public: 300 ANode() {} 301 ANode(const Node& node) : Node(node) { 302 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 303 typename Parent::NodeSetError()); 304 } 305 ANode& operator=(const Node& node) { 306 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 307 typename Parent::NodeSetError()); 308 Node::operator=(node); 309 return *this; 310 } 311 ANode(Invalid) : Node(INVALID) {} 312 }; 313 314 void first(ANode& node) const { 315 Parent::firstANode(static_cast<Node&>(node)); 316 } 317 void next(ANode& node) const { 318 Parent::nextANode(static_cast<Node&>(node)); 319 } 320 321 int id(const ANode& node) const { 322 return Parent::aNodeId(node); 323 } 324 325 class BNode : public Node { 326 friend class BidirBpUGraphExtender; 327 public: 328 BNode() {} 329 BNode(const Node& node) : Node(node) { 330 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 331 typename Parent::NodeSetError()); 332 } 333 BNode& operator=(const Node& node) { 334 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 335 typename Parent::NodeSetError()); 336 Node::operator=(node); 337 return *this; 338 } 339 BNode(Invalid) : Node(INVALID) {} 340 }; 341 342 void first(BNode& node) const { 343 Parent::firstBNode(static_cast<Node&>(node)); 344 } 345 void next(BNode& node) const { 346 Parent::nextBNode(static_cast<Node&>(node)); 347 } 348 349 int id(const BNode& node) const { 350 return Parent::aNodeId(node); 351 } 352 353 Node source(const UEdge& edge) const { 354 return aNode(edge); 355 } 356 Node target(const UEdge& edge) const { 357 return bNode(edge); 358 } 359 360 void firstInc(UEdge& edge, bool& direction, const Node& node) const { 361 if (Parent::aNode(node)) { 362 Parent::firstFromANode(edge, node); 363 direction = true; 364 } else { 365 Parent::firstFromBNode(edge, node); 366 direction = static_cast<UEdge&>(edge) == INVALID; 367 } 368 } 369 void nextInc(UEdge& edge, bool& direction) const { 370 if (direction) { 371 Parent::nextFromANode(edge); 372 } else { 373 Parent::nextFromBNode(edge); 374 if (edge == INVALID) direction = true; 375 } 376 } 377 378 class Edge : public UEdge { 379 friend class BidirBpUGraphExtender; 380 protected: 381 bool forward; 382 383 Edge(const UEdge& edge, bool _forward) 384 : UEdge(edge), forward(_forward) {} 385 386 public: 387 Edge() {} 388 Edge (Invalid) : UEdge(INVALID), forward(true) {} 389 bool operator==(const Edge& i) const { 390 return UEdge::operator==(i) && forward == i.forward; 391 } 392 bool operator!=(const Edge& i) const { 393 return UEdge::operator!=(i) || forward != i.forward; 394 } 395 bool operator<(const Edge& i) const { 396 return UEdge::operator<(i) || 397 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); 398 } 399 }; 400 401 void first(Edge& edge) const { 402 Parent::first(static_cast<UEdge&>(edge)); 403 edge.forward = true; 404 } 405 406 void next(Edge& edge) const { 407 if (!edge.forward) { 408 Parent::next(static_cast<UEdge&>(edge)); 409 } 410 edge.forward = !edge.forward; 411 } 412 413 void firstOut(Edge& edge, const Node& node) const { 414 if (Parent::aNode(node)) { 415 Parent::firstFromANode(edge, node); 416 edge.forward = true; 417 } else { 418 Parent::firstFromBNode(edge, node); 419 edge.forward = static_cast<UEdge&>(edge) == INVALID; 420 } 421 } 422 void nextOut(Edge& edge) const { 423 if (edge.forward) { 424 Parent::nextFromANode(edge); 425 } else { 426 Parent::nextFromBNode(edge); 427 edge.forward = static_cast<UEdge&>(edge) == INVALID; 428 } 429 } 430 431 void firstIn(Edge& edge, const Node& node) const { 432 if (Parent::bNode(node)) { 433 Parent::firstFromBNode(edge, node); 434 edge.forward = true; 435 } else { 436 Parent::firstFromANode(edge, node); 437 edge.forward = static_cast<UEdge&>(edge) == INVALID; 438 } 439 } 440 void nextIn(Edge& edge) const { 441 if (edge.forward) { 442 Parent::nextFromBNode(edge); 443 } else { 444 Parent::nextFromANode(edge); 445 edge.forward = static_cast<UEdge&>(edge) == INVALID; 446 } 447 } 448 449 Node source(const Edge& edge) const { 450 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); 451 } 452 Node target(const Edge& edge) const { 453 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); 454 } 455 456 int id(const Edge& edge) const { 457 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 458 (edge.forward ? 0 : 1); 459 } 460 Edge edgeFromId(int id) const { 461 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); 462 } 463 int maxEdgeId() const { 464 return (Parent::maxUEdgeId() << 1) + 1; 465 } 466 467 bool direction(const Edge& edge) const { 468 return edge.forward; 469 } 470 471 Edge direct(const UEdge& edge, bool direction) const { 472 return Edge(edge, direction); 473 } 474 475 int edgeNum() const { 476 return 2 * Parent::uEdgeNum(); 477 } 478 479 int uEdgeNum() const { 480 return Parent::uEdgeNum(); 481 } 482 483 484 }; 282 485 } 283 486 -
lemon/bits/graph_adaptor_extender.h
r2076 r2231 476 476 } 477 477 ANode fromId(int id, ANode) const { 478 return Parent:: fromANodeId(id);478 return Parent::nodeFromANodeId(id); 479 479 } 480 480 BNode fromId(int id, BNode) const { 481 return Parent:: fromBNodeId(id);481 return Parent::nodeFromBNodeId(id); 482 482 } 483 483 Edge fromId(int id, Edge) const { -
lemon/bits/graph_extender.h
r2222 r2231 731 731 class BpUGraphExtender : public Base { 732 732 public: 733 733 734 typedef Base Parent; 734 735 typedef BpUGraphExtender Graph; 735 736 736 737 typedef typename Parent::Node Node; 738 typedef typename Parent::ANode ANode; 739 typedef typename Parent::BNode BNode; 740 typedef typename Parent::Edge Edge; 737 741 typedef typename Parent::UEdge UEdge; 738 742 739 743 740 using Parent::first; 741 using Parent::next; 742 743 using Parent::id; 744 745 class ANode : public Node { 746 friend class BpUGraphExtender; 747 public: 748 ANode() {} 749 ANode(const Node& node) : Node(node) { 750 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 751 typename Parent::NodeSetError()); 752 } 753 ANode(Invalid) : Node(INVALID) {} 754 }; 755 756 void first(ANode& node) const { 757 Parent::firstANode(static_cast<Node&>(node)); 758 } 759 void next(ANode& node) const { 760 Parent::nextANode(static_cast<Node&>(node)); 761 } 762 763 int id(const ANode& node) const { 764 return Parent::aNodeId(node); 765 } 766 767 class BNode : public Node { 768 friend class BpUGraphExtender; 769 public: 770 BNode() {} 771 BNode(const Node& node) : Node(node) { 772 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 773 typename Parent::NodeSetError()); 774 } 775 BNode(Invalid) : Node(INVALID) {} 776 }; 777 778 void first(BNode& node) const { 779 Parent::firstBNode(static_cast<Node&>(node)); 780 } 781 void next(BNode& node) const { 782 Parent::nextBNode(static_cast<Node&>(node)); 783 } 784 785 int id(const BNode& node) const { 786 return Parent::aNodeId(node); 787 } 788 789 Node source(const UEdge& edge) const { 790 return aNode(edge); 791 } 792 Node target(const UEdge& edge) const { 793 return bNode(edge); 794 } 795 796 void firstInc(UEdge& edge, bool& direction, const Node& node) const { 797 if (Parent::aNode(node)) { 798 Parent::firstFromANode(edge, node); 799 direction = true; 800 } else { 801 Parent::firstFromBNode(edge, node); 802 direction = static_cast<UEdge&>(edge) == INVALID; 803 } 804 } 805 void nextInc(UEdge& edge, bool& direction) const { 806 if (direction) { 807 Parent::nextFromANode(edge); 808 } else { 809 Parent::nextFromBNode(edge); 810 if (edge == INVALID) direction = true; 811 } 812 } 813 814 class Edge : public UEdge { 815 friend class BpUGraphExtender; 816 protected: 817 bool forward; 818 819 Edge(const UEdge& edge, bool _forward) 820 : UEdge(edge), forward(_forward) {} 821 822 public: 823 Edge() {} 824 Edge (Invalid) : UEdge(INVALID), forward(true) {} 825 bool operator==(const Edge& i) const { 826 return UEdge::operator==(i) && forward == i.forward; 827 } 828 bool operator!=(const Edge& i) const { 829 return UEdge::operator!=(i) || forward != i.forward; 830 } 831 bool operator<(const Edge& i) const { 832 return UEdge::operator<(i) || 833 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); 834 } 835 }; 836 837 void first(Edge& edge) const { 838 Parent::first(static_cast<UEdge&>(edge)); 839 edge.forward = true; 840 } 841 842 void next(Edge& edge) const { 843 if (!edge.forward) { 844 Parent::next(static_cast<UEdge&>(edge)); 845 } 846 edge.forward = !edge.forward; 847 } 848 849 void firstOut(Edge& edge, const Node& node) const { 850 if (Parent::aNode(node)) { 851 Parent::firstFromANode(edge, node); 852 edge.forward = true; 853 } else { 854 Parent::firstFromBNode(edge, node); 855 edge.forward = static_cast<UEdge&>(edge) == INVALID; 856 } 857 } 858 void nextOut(Edge& edge) const { 859 if (edge.forward) { 860 Parent::nextFromANode(edge); 861 } else { 862 Parent::nextFromBNode(edge); 863 edge.forward = static_cast<UEdge&>(edge) == INVALID; 864 } 865 } 866 867 void firstIn(Edge& edge, const Node& node) const { 868 if (Parent::bNode(node)) { 869 Parent::firstFromBNode(edge, node); 870 edge.forward = true; 871 } else { 872 Parent::firstFromANode(edge, node); 873 edge.forward = static_cast<UEdge&>(edge) == INVALID; 874 } 875 } 876 void nextIn(Edge& edge) const { 877 if (edge.forward) { 878 Parent::nextFromBNode(edge); 879 } else { 880 Parent::nextFromANode(edge); 881 edge.forward = static_cast<UEdge&>(edge) == INVALID; 882 } 883 } 884 885 Node source(const Edge& edge) const { 886 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); 887 } 888 Node target(const Edge& edge) const { 889 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); 890 } 891 892 int id(const Edge& edge) const { 893 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 894 (edge.forward ? 0 : 1); 895 } 896 Edge edgeFromId(int id) const { 897 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); 898 } 899 int maxEdgeId() const { 900 return (Parent::maxUEdgeId(UEdge()) << 1) + 1; 901 } 902 903 bool direction(const Edge& edge) const { 904 return edge.forward; 905 } 906 907 Edge direct(const UEdge& edge, bool direction) const { 908 return Edge(edge, direction); 909 } 910 911 int edgeNum() const { 912 return 2 * Parent::uEdgeNum(); 913 } 914 915 int uEdgeNum() const { 916 return Parent::uEdgeNum(); 917 } 918 919 Node oppositeNode(const UEdge& edge, const Node& node) const { 920 return source(edge) == node ? 921 target(edge) : source(edge); 922 } 923 744 Node oppositeNode(const Node& node, const UEdge& edge) const { 745 return Parent::aNode(edge) == node ? 746 Parent::bNode(edge) : Parent::aNode(edge); 747 } 748 749 using Parent::direct; 924 750 Edge direct(const UEdge& edge, const Node& node) const { 925 return Edge(edge, node == Parent::source(edge));751 return Parent::direct(edge, node == Parent::source(edge)); 926 752 } 927 753 928 754 Edge oppositeEdge(const Edge& edge) const { 929 return Parent::direct(edge, !Parent::direction(edge)); 930 } 931 932 755 return direct(edge, !Parent::direction(edge)); 756 } 757 933 758 int maxId(Node) const { 934 759 return Parent::maxNodeId(); … … 941 766 } 942 767 int maxId(Edge) const { 943 return maxEdgeId();768 return Parent::maxEdgeId(); 944 769 } 945 770 int maxId(UEdge) const { … … 952 777 } 953 778 ANode fromId(int id, ANode) const { 954 return Parent:: fromANodeId(id);779 return Parent::nodeFromANodeId(id); 955 780 } 956 781 BNode fromId(int id, BNode) const { 957 return Parent:: fromBNodeId(id);782 return Parent::nodeFromBNodeId(id); 958 783 } 959 784 Edge fromId(int id, Edge) const { … … 1305 1130 NodeMap& operator=(const CMap& cmap) { 1306 1131 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 1307 const typename Parent::Notifier* notifier = Parent::getNotifier(); 1308 Edge it; 1309 for (graph.first(it); it != INVALID; graph.next(it)) { 1310 Parent::set(it, cmap[it]); 1311 } 1312 return *this; 1132 aNodeMap = cmap; 1133 bNodeMap = cmap; 1134 return *this; 1313 1135 } 1314 1136 … … 1460 1282 1461 1283 std::vector<Edge> edges; 1462 edges.push_back( direct(uedge, true));1463 edges.push_back( direct(uedge, false));1284 edges.push_back(Parent::direct(uedge, true)); 1285 edges.push_back(Parent::direct(uedge, false)); 1464 1286 getNotifier(Edge()).add(edges); 1465 1287 … … 1500 1322 void erase(const UEdge& uedge) { 1501 1323 std::vector<Edge> edges; 1502 edges.push_back( direct(uedge, true));1503 edges.push_back( direct(uedge, false));1324 edges.push_back(Parent::direct(uedge, true)); 1325 edges.push_back(Parent::direct(uedge, false)); 1504 1326 getNotifier(Edge()).erase(edges); 1505 1327 getNotifier(UEdge()).erase(uedge); … … 1527 1349 UEdge uedge = Parent::findUEdge(u, v, prev); 1528 1350 if (uedge != INVALID) { 1529 return direct(uedge, Parent::aNode(u));1351 return Parent::direct(uedge, Parent::aNode(u)); 1530 1352 } else { 1531 1353 return INVALID;
Note: See TracChangeset
for help on using the changeset viewer.