Changeset 2115:4cd528a30ec1 in lemon0.x for lemon/bits/graph_extender.h
 Timestamp:
 06/30/06 14:14:36 (13 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2821
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bits/graph_extender.h
r2102 r2115 21 21 22 22 #include <lemon/bits/invalid.h> 23 #include <lemon/error.h>24 23 25 24 #include <lemon/bits/map_extender.h> 26 25 #include <lemon/bits/default_map.h> 27 28 #include <lemon/concept_check.h>29 #include <lemon/concept/maps.h>30 26 31 27 ///\ingroup graphbits … … 319 315 }; 320 316 321 /// \ingroup graphbits322 ///323 /// \brief Extender for the UGraphs324 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 extension336 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 else367 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 extension380 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 iterator550 ///551 /// Returns the base node (ie. the source in this case) of the iterator552 Node baseNode(const OutEdgeIt &e) const {553 return Parent::source((Edge)e);554 }555 /// \brief Running node of the iterator556 ///557 /// Returns the running node (ie. the target in this case) of the558 /// iterator559 Node runningNode(const OutEdgeIt &e) const {560 return Parent::target((Edge)e);561 }562 563 /// \brief Base node of the iterator564 ///565 /// Returns the base node (ie. the target in this case) of the iterator566 Node baseNode(const InEdgeIt &e) const {567 return Parent::target((Edge)e);568 }569 /// \brief Running node of the iterator570 ///571 /// Returns the running node (ie. the source in this case) of the572 /// iterator573 Node runningNode(const InEdgeIt &e) const {574 return Parent::source((Edge)e);575 }576 577 /// Base node of the iterator578 ///579 /// Returns the base node of the iterator580 Node baseNode(const IncEdgeIt &e) const {581 return e.direction ? source(e) : target(e);582 }583 /// Running node of the iterator584 ///585 /// Returns the running node of the iterator586 Node runningNode(const IncEdgeIt &e) const {587 return e.direction ? target(e) : source(e);588 }589 590 // Mappable extension591 592 template <typename _Value>593 class NodeMap594 : 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 EdgeMap618 : 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 UEdgeMap642 : 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 extension666 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 graphbits728 ///729 /// \brief Extender for the BpUGraphs730 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 iterator1163 ///1164 /// Returns the base node (ie. the source in this case) of the iterator1165 Node baseNode(const OutEdgeIt &e) const {1166 return Parent::source((Edge&)e);1167 }1168 /// \brief Running node of the iterator1169 ///1170 /// Returns the running node (ie. the target in this case) of the1171 /// iterator1172 Node runningNode(const OutEdgeIt &e) const {1173 return Parent::target((Edge&)e);1174 }1175 1176 /// \brief Base node of the iterator1177 ///1178 /// Returns the base node (ie. the target in this case) of the iterator1179 Node baseNode(const InEdgeIt &e) const {1180 return Parent::target((Edge&)e);1181 }1182 /// \brief Running node of the iterator1183 ///1184 /// Returns the running node (ie. the source in this case) of the1185 /// iterator1186 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 iterator1217 ///1218 /// Returns the base node of the iterator1219 Node baseNode(const IncEdgeIt &e) const {1220 return e.direction ? source(e) : target(e);1221 }1222 1223 /// Running node of the iterator1224 ///1225 /// Returns the running node of the iterator1226 Node runningNode(const IncEdgeIt &e) const {1227 return e.direction ? target(e) : source(e);1228 }1229 1230 template <typename _Value>1231 class ANodeMap1232 : 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 BNodeMap1256 : 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 EdgeMap1398 : 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 UEdgeMap1421 : 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 1527 317 } 1528 318
Note: See TracChangeset
for help on using the changeset viewer.