Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/bits
- Timestamp:
- 06/30/06 14:15:45 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
- Location:
- lemon/bits
- Files:
-
- 2 deleted
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/graph_extender.h
r2115 r2116 21 21 22 22 #include <lemon/bits/invalid.h> 23 #include <lemon/error.h> 23 24 24 25 #include <lemon/bits/map_extender.h> 25 26 #include <lemon/bits/default_map.h> 27 28 #include <lemon/concept_check.h> 29 #include <lemon/concept/maps.h> 26 30 27 31 ///\ingroup graphbits … … 315 319 }; 316 320 321 /// \ingroup graphbits 322 /// 323 /// \brief Extender for the UGraphs 324 template <typename Base> 325 class UGraphExtender : public Base { 326 public: 327 328 typedef Base Parent; 329 typedef UGraphExtender Graph; 330 331 typedef typename Parent::Node Node; 332 typedef typename Parent::Edge Edge; 333 typedef typename Parent::UEdge UEdge; 334 335 // UGraph extension 336 337 int maxId(Node) const { 338 return Parent::maxNodeId(); 339 } 340 341 int maxId(Edge) const { 342 return Parent::maxEdgeId(); 343 } 344 345 int maxId(UEdge) const { 346 return Parent::maxUEdgeId(); 347 } 348 349 Node fromId(int id, Node) const { 350 return Parent::nodeFromId(id); 351 } 352 353 Edge fromId(int id, Edge) const { 354 return Parent::edgeFromId(id); 355 } 356 357 UEdge fromId(int id, UEdge) const { 358 return Parent::uEdgeFromId(id); 359 } 360 361 Node oppositeNode(const Node &n, const UEdge &e) const { 362 if( n == Parent::source(e)) 363 return Parent::target(e); 364 else if( n == Parent::target(e)) 365 return Parent::source(e); 366 else 367 return INVALID; 368 } 369 370 Edge oppositeEdge(const Edge &e) const { 371 return Parent::direct(e, !Parent::direction(e)); 372 } 373 374 using Parent::direct; 375 Edge direct(const UEdge &ue, const Node &s) const { 376 return Parent::direct(ue, Parent::source(ue) == s); 377 } 378 379 // Alterable extension 380 381 typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier; 382 typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier; 383 typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier; 384 385 386 protected: 387 388 mutable NodeNotifier node_notifier; 389 mutable EdgeNotifier edge_notifier; 390 mutable UEdgeNotifier uedge_notifier; 391 392 public: 393 394 NodeNotifier& getNotifier(Node) const { 395 return node_notifier; 396 } 397 398 EdgeNotifier& getNotifier(Edge) const { 399 return edge_notifier; 400 } 401 402 UEdgeNotifier& getNotifier(UEdge) const { 403 return uedge_notifier; 404 } 405 406 407 408 class NodeIt : public Node { 409 const Graph* graph; 410 public: 411 412 NodeIt() {} 413 414 NodeIt(Invalid i) : Node(i) { } 415 416 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 417 _graph.first(static_cast<Node&>(*this)); 418 } 419 420 NodeIt(const Graph& _graph, const Node& node) 421 : Node(node), graph(&_graph) {} 422 423 NodeIt& operator++() { 424 graph->next(*this); 425 return *this; 426 } 427 428 }; 429 430 431 class EdgeIt : public Edge { 432 const Graph* graph; 433 public: 434 435 EdgeIt() { } 436 437 EdgeIt(Invalid i) : Edge(i) { } 438 439 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 440 _graph.first(static_cast<Edge&>(*this)); 441 } 442 443 EdgeIt(const Graph& _graph, const Edge& e) : 444 Edge(e), graph(&_graph) { } 445 446 EdgeIt& operator++() { 447 graph->next(*this); 448 return *this; 449 } 450 451 }; 452 453 454 class OutEdgeIt : public Edge { 455 const Graph* graph; 456 public: 457 458 OutEdgeIt() { } 459 460 OutEdgeIt(Invalid i) : Edge(i) { } 461 462 OutEdgeIt(const Graph& _graph, const Node& node) 463 : graph(&_graph) { 464 _graph.firstOut(*this, node); 465 } 466 467 OutEdgeIt(const Graph& _graph, const Edge& edge) 468 : Edge(edge), graph(&_graph) {} 469 470 OutEdgeIt& operator++() { 471 graph->nextOut(*this); 472 return *this; 473 } 474 475 }; 476 477 478 class InEdgeIt : public Edge { 479 const Graph* graph; 480 public: 481 482 InEdgeIt() { } 483 484 InEdgeIt(Invalid i) : Edge(i) { } 485 486 InEdgeIt(const Graph& _graph, const Node& node) 487 : graph(&_graph) { 488 _graph.firstIn(*this, node); 489 } 490 491 InEdgeIt(const Graph& _graph, const Edge& edge) : 492 Edge(edge), graph(&_graph) {} 493 494 InEdgeIt& operator++() { 495 graph->nextIn(*this); 496 return *this; 497 } 498 499 }; 500 501 502 class UEdgeIt : public Parent::UEdge { 503 const Graph* graph; 504 public: 505 506 UEdgeIt() { } 507 508 UEdgeIt(Invalid i) : UEdge(i) { } 509 510 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 511 _graph.first(static_cast<UEdge&>(*this)); 512 } 513 514 UEdgeIt(const Graph& _graph, const UEdge& e) : 515 UEdge(e), graph(&_graph) { } 516 517 UEdgeIt& operator++() { 518 graph->next(*this); 519 return *this; 520 } 521 522 }; 523 524 class IncEdgeIt : public Parent::UEdge { 525 friend class UGraphExtender; 526 const Graph* graph; 527 bool direction; 528 public: 529 530 IncEdgeIt() { } 531 532 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } 533 534 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 535 _graph.firstInc(*this, direction, n); 536 } 537 538 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 539 : graph(&_graph), UEdge(ue) { 540 direction = (_graph.source(ue) == n); 541 } 542 543 IncEdgeIt& operator++() { 544 graph->nextInc(*this, direction); 545 return *this; 546 } 547 }; 548 549 /// \brief Base node of the iterator 550 /// 551 /// Returns the base node (ie. the source in this case) of the iterator 552 Node baseNode(const OutEdgeIt &e) const { 553 return Parent::source((Edge)e); 554 } 555 /// \brief Running node of the iterator 556 /// 557 /// Returns the running node (ie. the target in this case) of the 558 /// iterator 559 Node runningNode(const OutEdgeIt &e) const { 560 return Parent::target((Edge)e); 561 } 562 563 /// \brief Base node of the iterator 564 /// 565 /// Returns the base node (ie. the target in this case) of the iterator 566 Node baseNode(const InEdgeIt &e) const { 567 return Parent::target((Edge)e); 568 } 569 /// \brief Running node of the iterator 570 /// 571 /// Returns the running node (ie. the source in this case) of the 572 /// iterator 573 Node runningNode(const InEdgeIt &e) const { 574 return Parent::source((Edge)e); 575 } 576 577 /// Base node of the iterator 578 /// 579 /// Returns the base node of the iterator 580 Node baseNode(const IncEdgeIt &e) const { 581 return e.direction ? source(e) : target(e); 582 } 583 /// Running node of the iterator 584 /// 585 /// Returns the running node of the iterator 586 Node runningNode(const IncEdgeIt &e) const { 587 return e.direction ? target(e) : source(e); 588 } 589 590 // Mappable extension 591 592 template <typename _Value> 593 class NodeMap 594 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 595 public: 596 typedef UGraphExtender Graph; 597 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 598 599 NodeMap(const Graph& graph) 600 : Parent(graph) {} 601 NodeMap(const Graph& graph, const _Value& value) 602 : Parent(graph, value) {} 603 604 NodeMap& operator=(const NodeMap& cmap) { 605 return operator=<NodeMap>(cmap); 606 } 607 608 template <typename CMap> 609 NodeMap& operator=(const CMap& cmap) { 610 Parent::operator=(cmap); 611 return *this; 612 } 613 614 }; 615 616 template <typename _Value> 617 class EdgeMap 618 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 619 public: 620 typedef UGraphExtender Graph; 621 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 622 623 EdgeMap(const Graph& graph) 624 : Parent(graph) {} 625 EdgeMap(const Graph& graph, const _Value& value) 626 : Parent(graph, value) {} 627 628 EdgeMap& operator=(const EdgeMap& cmap) { 629 return operator=<EdgeMap>(cmap); 630 } 631 632 template <typename CMap> 633 EdgeMap& operator=(const CMap& cmap) { 634 Parent::operator=(cmap); 635 return *this; 636 } 637 }; 638 639 640 template <typename _Value> 641 class UEdgeMap 642 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { 643 public: 644 typedef UGraphExtender Graph; 645 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 646 647 UEdgeMap(const Graph& graph) 648 : Parent(graph) {} 649 650 UEdgeMap(const Graph& graph, const _Value& value) 651 : Parent(graph, value) {} 652 653 UEdgeMap& operator=(const UEdgeMap& cmap) { 654 return operator=<UEdgeMap>(cmap); 655 } 656 657 template <typename CMap> 658 UEdgeMap& operator=(const CMap& cmap) { 659 Parent::operator=(cmap); 660 return *this; 661 } 662 663 }; 664 665 // Alteration extension 666 667 Node addNode() { 668 Node node = Parent::addNode(); 669 getNotifier(Node()).add(node); 670 return node; 671 } 672 673 UEdge addEdge(const Node& from, const Node& to) { 674 UEdge uedge = Parent::addEdge(from, to); 675 getNotifier(UEdge()).add(uedge); 676 getNotifier(Edge()).add(Parent::direct(uedge, true)); 677 getNotifier(Edge()).add(Parent::direct(uedge, false)); 678 return uedge; 679 } 680 681 void clear() { 682 getNotifier(Edge()).clear(); 683 getNotifier(UEdge()).clear(); 684 getNotifier(Node()).clear(); 685 Parent::clear(); 686 } 687 688 void erase(const Node& node) { 689 Edge edge; 690 Parent::firstOut(edge, node); 691 while (edge != INVALID ) { 692 erase(edge); 693 Parent::firstOut(edge, node); 694 } 695 696 Parent::firstIn(edge, node); 697 while (edge != INVALID ) { 698 erase(edge); 699 Parent::firstIn(edge, node); 700 } 701 702 getNotifier(Node()).erase(node); 703 Parent::erase(node); 704 } 705 706 void erase(const UEdge& uedge) { 707 getNotifier(Edge()).erase(Parent::direct(uedge, true)); 708 getNotifier(Edge()).erase(Parent::direct(uedge, false)); 709 getNotifier(UEdge()).erase(uedge); 710 Parent::erase(uedge); 711 } 712 713 UGraphExtender() { 714 node_notifier.setContainer(*this); 715 edge_notifier.setContainer(*this); 716 uedge_notifier.setContainer(*this); 717 } 718 719 ~UGraphExtender() { 720 uedge_notifier.clear(); 721 edge_notifier.clear(); 722 node_notifier.clear(); 723 } 724 725 }; 726 727 /// \ingroup graphbits 728 /// 729 /// \brief Extender for the BpUGraphs 730 template <typename Base> 731 class BpUGraphExtender : public Base { 732 public: 733 typedef Base Parent; 734 typedef BpUGraphExtender Graph; 735 736 typedef typename Parent::Node Node; 737 typedef typename Parent::UEdge UEdge; 738 739 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 924 Edge direct(const UEdge& edge, const Node& node) const { 925 return Edge(edge, node == Parent::source(edge)); 926 } 927 928 Edge oppositeEdge(const Edge& edge) const { 929 return Parent::direct(edge, !Parent::direction(edge)); 930 } 931 932 933 int maxId(Node) const { 934 return Parent::maxNodeId(); 935 } 936 int maxId(BNode) const { 937 return Parent::maxBNodeId(); 938 } 939 int maxId(ANode) const { 940 return Parent::maxANodeId(); 941 } 942 int maxId(Edge) const { 943 return maxEdgeId(); 944 } 945 int maxId(UEdge) const { 946 return Parent::maxUEdgeId(); 947 } 948 949 950 Node fromId(int id, Node) const { 951 return Parent::nodeFromId(id); 952 } 953 ANode fromId(int id, ANode) const { 954 return Parent::fromANodeId(id); 955 } 956 BNode fromId(int id, BNode) const { 957 return Parent::fromBNodeId(id); 958 } 959 Edge fromId(int id, Edge) const { 960 return Parent::edgeFromId(id); 961 } 962 UEdge fromId(int id, UEdge) const { 963 return Parent::uEdgeFromId(id); 964 } 965 966 typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier; 967 typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier; 968 typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier; 969 typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier; 970 typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier; 971 972 protected: 973 974 mutable ANodeNotifier anode_notifier; 975 mutable BNodeNotifier bnode_notifier; 976 mutable NodeNotifier node_notifier; 977 mutable EdgeNotifier edge_notifier; 978 mutable UEdgeNotifier uedge_notifier; 979 980 public: 981 982 NodeNotifier& getNotifier(Node) const { 983 return node_notifier; 984 } 985 986 ANodeNotifier& getNotifier(ANode) const { 987 return anode_notifier; 988 } 989 990 BNodeNotifier& getNotifier(BNode) const { 991 return bnode_notifier; 992 } 993 994 EdgeNotifier& getNotifier(Edge) const { 995 return edge_notifier; 996 } 997 998 UEdgeNotifier& getNotifier(UEdge) const { 999 return uedge_notifier; 1000 } 1001 1002 class NodeIt : public Node { 1003 const Graph* graph; 1004 public: 1005 1006 NodeIt() { } 1007 1008 NodeIt(Invalid i) : Node(INVALID) { } 1009 1010 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 1011 graph->first(static_cast<Node&>(*this)); 1012 } 1013 1014 NodeIt(const Graph& _graph, const Node& node) 1015 : Node(node), graph(&_graph) { } 1016 1017 NodeIt& operator++() { 1018 graph->next(*this); 1019 return *this; 1020 } 1021 1022 }; 1023 1024 class ANodeIt : public Node { 1025 friend class BpUGraphExtender; 1026 const Graph* graph; 1027 public: 1028 1029 ANodeIt() { } 1030 1031 ANodeIt(Invalid i) : Node(INVALID) { } 1032 1033 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { 1034 graph->firstANode(static_cast<Node&>(*this)); 1035 } 1036 1037 ANodeIt(const Graph& _graph, const Node& node) 1038 : Node(node), graph(&_graph) {} 1039 1040 ANodeIt& operator++() { 1041 graph->nextANode(*this); 1042 return *this; 1043 } 1044 }; 1045 1046 class BNodeIt : public Node { 1047 friend class BpUGraphExtender; 1048 const Graph* graph; 1049 public: 1050 1051 BNodeIt() { } 1052 1053 BNodeIt(Invalid i) : Node(INVALID) { } 1054 1055 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { 1056 graph->firstBNode(static_cast<Node&>(*this)); 1057 } 1058 1059 BNodeIt(const Graph& _graph, const Node& node) 1060 : Node(node), graph(&_graph) {} 1061 1062 BNodeIt& operator++() { 1063 graph->nextBNode(*this); 1064 return *this; 1065 } 1066 }; 1067 1068 class EdgeIt : public Edge { 1069 friend class BpUGraphExtender; 1070 const Graph* graph; 1071 public: 1072 1073 EdgeIt() { } 1074 1075 EdgeIt(Invalid i) : Edge(INVALID) { } 1076 1077 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 1078 graph->first(static_cast<Edge&>(*this)); 1079 } 1080 1081 EdgeIt(const Graph& _graph, const Edge& edge) 1082 : Edge(edge), graph(&_graph) { } 1083 1084 EdgeIt& operator++() { 1085 graph->next(*this); 1086 return *this; 1087 } 1088 1089 }; 1090 1091 class UEdgeIt : public UEdge { 1092 friend class BpUGraphExtender; 1093 const Graph* graph; 1094 public: 1095 1096 UEdgeIt() { } 1097 1098 UEdgeIt(Invalid i) : UEdge(INVALID) { } 1099 1100 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 1101 graph->first(static_cast<UEdge&>(*this)); 1102 } 1103 1104 UEdgeIt(const Graph& _graph, const UEdge& edge) 1105 : UEdge(edge), graph(&_graph) { } 1106 1107 UEdgeIt& operator++() { 1108 graph->next(*this); 1109 return *this; 1110 } 1111 }; 1112 1113 class OutEdgeIt : public Edge { 1114 friend class BpUGraphExtender; 1115 const Graph* graph; 1116 public: 1117 1118 OutEdgeIt() { } 1119 1120 OutEdgeIt(Invalid i) : Edge(i) { } 1121 1122 OutEdgeIt(const Graph& _graph, const Node& node) 1123 : graph(&_graph) { 1124 graph->firstOut(*this, node); 1125 } 1126 1127 OutEdgeIt(const Graph& _graph, const Edge& edge) 1128 : Edge(edge), graph(&_graph) {} 1129 1130 OutEdgeIt& operator++() { 1131 graph->nextOut(*this); 1132 return *this; 1133 } 1134 1135 }; 1136 1137 1138 class InEdgeIt : public Edge { 1139 friend class BpUGraphExtender; 1140 const Graph* graph; 1141 public: 1142 1143 InEdgeIt() { } 1144 1145 InEdgeIt(Invalid i) : Edge(i) { } 1146 1147 InEdgeIt(const Graph& _graph, const Node& node) 1148 : graph(&_graph) { 1149 graph->firstIn(*this, node); 1150 } 1151 1152 InEdgeIt(const Graph& _graph, const Edge& edge) : 1153 Edge(edge), graph(&_graph) {} 1154 1155 InEdgeIt& operator++() { 1156 graph->nextIn(*this); 1157 return *this; 1158 } 1159 1160 }; 1161 1162 /// \brief Base node of the iterator 1163 /// 1164 /// Returns the base node (ie. the source in this case) of the iterator 1165 Node baseNode(const OutEdgeIt &e) const { 1166 return Parent::source((Edge&)e); 1167 } 1168 /// \brief Running node of the iterator 1169 /// 1170 /// Returns the running node (ie. the target in this case) of the 1171 /// iterator 1172 Node runningNode(const OutEdgeIt &e) const { 1173 return Parent::target((Edge&)e); 1174 } 1175 1176 /// \brief Base node of the iterator 1177 /// 1178 /// Returns the base node (ie. the target in this case) of the iterator 1179 Node baseNode(const InEdgeIt &e) const { 1180 return Parent::target((Edge&)e); 1181 } 1182 /// \brief Running node of the iterator 1183 /// 1184 /// Returns the running node (ie. the source in this case) of the 1185 /// iterator 1186 Node runningNode(const InEdgeIt &e) const { 1187 return Parent::source((Edge&)e); 1188 } 1189 1190 class IncEdgeIt : public Parent::UEdge { 1191 friend class BpUGraphExtender; 1192 const Graph* graph; 1193 bool direction; 1194 public: 1195 1196 IncEdgeIt() { } 1197 1198 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } 1199 1200 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 1201 graph->firstInc(*this, direction, n); 1202 } 1203 1204 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 1205 : graph(&_graph), UEdge(ue) { 1206 direction = (graph->source(ue) == n); 1207 } 1208 1209 IncEdgeIt& operator++() { 1210 graph->nextInc(*this, direction); 1211 return *this; 1212 } 1213 }; 1214 1215 1216 /// Base node of the iterator 1217 /// 1218 /// Returns the base node of the iterator 1219 Node baseNode(const IncEdgeIt &e) const { 1220 return e.direction ? source(e) : target(e); 1221 } 1222 1223 /// Running node of the iterator 1224 /// 1225 /// Returns the running node of the iterator 1226 Node runningNode(const IncEdgeIt &e) const { 1227 return e.direction ? target(e) : source(e); 1228 } 1229 1230 template <typename _Value> 1231 class ANodeMap 1232 : public MapExtender<DefaultMap<Graph, ANode, _Value> > { 1233 public: 1234 typedef BpUGraphExtender Graph; 1235 typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent; 1236 1237 ANodeMap(const Graph& graph) 1238 : Parent(graph) {} 1239 ANodeMap(const Graph& graph, const _Value& value) 1240 : Parent(graph, value) {} 1241 1242 ANodeMap& operator=(const ANodeMap& cmap) { 1243 return operator=<ANodeMap>(cmap); 1244 } 1245 1246 template <typename CMap> 1247 ANodeMap& operator=(const CMap& cmap) { 1248 Parent::operator=(cmap); 1249 return *this; 1250 } 1251 1252 }; 1253 1254 template <typename _Value> 1255 class BNodeMap 1256 : public MapExtender<DefaultMap<Graph, BNode, _Value> > { 1257 public: 1258 typedef BpUGraphExtender Graph; 1259 typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent; 1260 1261 BNodeMap(const Graph& graph) 1262 : Parent(graph) {} 1263 BNodeMap(const Graph& graph, const _Value& value) 1264 : Parent(graph, value) {} 1265 1266 BNodeMap& operator=(const BNodeMap& cmap) { 1267 return operator=<BNodeMap>(cmap); 1268 } 1269 1270 template <typename CMap> 1271 BNodeMap& operator=(const CMap& cmap) { 1272 Parent::operator=(cmap); 1273 return *this; 1274 } 1275 1276 }; 1277 1278 public: 1279 1280 template <typename _Value> 1281 class NodeMap { 1282 public: 1283 typedef BpUGraphExtender Graph; 1284 1285 typedef Node Key; 1286 typedef _Value Value; 1287 1288 /// The reference type of the map; 1289 typedef typename ANodeMap<_Value>::Reference Reference; 1290 /// The const reference type of the map; 1291 typedef typename ANodeMap<_Value>::ConstReference ConstReference; 1292 1293 typedef True ReferenceMapTag; 1294 1295 NodeMap(const Graph& _graph) 1296 : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} 1297 NodeMap(const Graph& _graph, const _Value& _value) 1298 : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} 1299 1300 NodeMap& operator=(const NodeMap& cmap) { 1301 return operator=<NodeMap>(cmap); 1302 } 1303 1304 template <typename CMap> 1305 NodeMap& operator=(const CMap& cmap) { 1306 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; 1313 } 1314 1315 ConstReference operator[](const Key& node) const { 1316 if (Parent::aNode(node)) { 1317 return aNodeMap[node]; 1318 } else { 1319 return bNodeMap[node]; 1320 } 1321 } 1322 1323 Reference operator[](const Key& node) { 1324 if (Parent::aNode(node)) { 1325 return aNodeMap[node]; 1326 } else { 1327 return bNodeMap[node]; 1328 } 1329 } 1330 1331 void set(const Key& node, const Value& value) { 1332 if (Parent::aNode(node)) { 1333 aNodeMap.set(node, value); 1334 } else { 1335 bNodeMap.set(node, value); 1336 } 1337 } 1338 1339 class MapIt : public NodeIt { 1340 public: 1341 1342 typedef NodeIt Parent; 1343 1344 explicit MapIt(NodeMap& _map) 1345 : Parent(_map.graph), map(_map) {} 1346 1347 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { 1348 return map[*this]; 1349 } 1350 1351 typename MapTraits<NodeMap>::ReturnValue operator*() { 1352 return map[*this]; 1353 } 1354 1355 void set(const Value& value) { 1356 map.set(*this, value); 1357 } 1358 1359 private: 1360 NodeMap& map; 1361 }; 1362 1363 class ConstMapIt : public NodeIt { 1364 public: 1365 1366 typedef NodeIt Parent; 1367 1368 explicit ConstMapIt(const NodeMap& _map) 1369 : Parent(_map.graph), map(_map) {} 1370 1371 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { 1372 return map[*this]; 1373 } 1374 1375 private: 1376 const NodeMap& map; 1377 }; 1378 1379 class ItemIt : public NodeIt { 1380 public: 1381 1382 typedef NodeIt Parent; 1383 1384 explicit ItemIt(const NodeMap& _map) 1385 : Parent(_map.graph) {} 1386 1387 }; 1388 1389 private: 1390 const Graph& graph; 1391 ANodeMap<_Value> aNodeMap; 1392 BNodeMap<_Value> bNodeMap; 1393 }; 1394 1395 1396 template <typename _Value> 1397 class EdgeMap 1398 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 1399 public: 1400 typedef BpUGraphExtender Graph; 1401 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 1402 1403 EdgeMap(const Graph& graph) 1404 : Parent(graph) {} 1405 EdgeMap(const Graph& graph, const _Value& value) 1406 : Parent(graph, value) {} 1407 1408 EdgeMap& operator=(const EdgeMap& cmap) { 1409 return operator=<EdgeMap>(cmap); 1410 } 1411 1412 template <typename CMap> 1413 EdgeMap& operator=(const CMap& cmap) { 1414 Parent::operator=(cmap); 1415 return *this; 1416 } 1417 }; 1418 1419 template <typename _Value> 1420 class UEdgeMap 1421 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { 1422 public: 1423 typedef BpUGraphExtender Graph; 1424 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 1425 1426 UEdgeMap(const Graph& graph) 1427 : Parent(graph) {} 1428 UEdgeMap(const Graph& graph, const _Value& value) 1429 : Parent(graph, value) {} 1430 1431 UEdgeMap& operator=(const UEdgeMap& cmap) { 1432 return operator=<UEdgeMap>(cmap); 1433 } 1434 1435 template <typename CMap> 1436 UEdgeMap& operator=(const CMap& cmap) { 1437 Parent::operator=(cmap); 1438 return *this; 1439 } 1440 }; 1441 1442 1443 Node addANode() { 1444 Node node = Parent::addANode(); 1445 getNotifier(ANode()).add(node); 1446 getNotifier(Node()).add(node); 1447 return node; 1448 } 1449 1450 Node addBNode() { 1451 Node node = Parent::addBNode(); 1452 getNotifier(BNode()).add(node); 1453 getNotifier(Node()).add(node); 1454 return node; 1455 } 1456 1457 UEdge addEdge(const Node& source, const Node& target) { 1458 UEdge uedge = Parent::addEdge(source, target); 1459 getNotifier(UEdge()).add(uedge); 1460 1461 std::vector<Edge> edges; 1462 edges.push_back(direct(uedge, true)); 1463 edges.push_back(direct(uedge, false)); 1464 getNotifier(Edge()).add(edges); 1465 1466 return uedge; 1467 } 1468 1469 void clear() { 1470 getNotifier(Edge()).clear(); 1471 getNotifier(UEdge()).clear(); 1472 getNotifier(Node()).clear(); 1473 getNotifier(BNode()).clear(); 1474 getNotifier(ANode()).clear(); 1475 Parent::clear(); 1476 } 1477 1478 void erase(const Node& node) { 1479 UEdge uedge; 1480 if (Parent::aNode(node)) { 1481 Parent::firstFromANode(uedge, node); 1482 while (uedge != INVALID) { 1483 erase(uedge); 1484 Parent::firstFromANode(uedge, node); 1485 } 1486 } else { 1487 Parent::firstFromBNode(uedge, node); 1488 while (uedge != INVALID) { 1489 erase(uedge); 1490 Parent::firstFromBNode(uedge, node); 1491 } 1492 } 1493 1494 getNotifier(Node()).erase(node); 1495 Parent::erase(node); 1496 } 1497 1498 void erase(const UEdge& uedge) { 1499 std::vector<Edge> edges; 1500 edges.push_back(direct(uedge, true)); 1501 edges.push_back(direct(uedge, false)); 1502 getNotifier(Edge()).erase(edges); 1503 getNotifier(UEdge()).erase(uedge); 1504 Parent::erase(uedge); 1505 } 1506 1507 1508 BpUGraphExtender() { 1509 anode_notifier.setContainer(*this); 1510 bnode_notifier.setContainer(*this); 1511 node_notifier.setContainer(*this); 1512 edge_notifier.setContainer(*this); 1513 uedge_notifier.setContainer(*this); 1514 } 1515 1516 ~BpUGraphExtender() { 1517 uedge_notifier.clear(); 1518 edge_notifier.clear(); 1519 node_notifier.clear(); 1520 anode_notifier.clear(); 1521 bnode_notifier.clear(); 1522 } 1523 1524 1525 }; 1526 317 1527 } 318 1528
Note: See TracChangeset
for help on using the changeset viewer.