Changeset 209:765619b7cbb2 in lemon1.2 for lemon/concepts/graph_components.h
 Timestamp:
 07/13/08 20:51:02 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/graph_components.h
r169 r209 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 50 50 public: 51 51 /// \brief Default constructor. 52 /// 52 /// 53 53 /// \warning The default constructor is not required to set 54 54 /// the item to some welldefined value. So you should consider it … … 67 67 /// \brief Assign operator for nodes. 68 68 /// 69 /// The nodes are assignable. 69 /// The nodes are assignable. 70 70 /// 71 71 GraphItem& operator=(GraphItem const&) { return *this; } … … 93 93 template<typename _GraphItem> 94 94 struct Constraints { 95 96 97 98 99 100 101 102 103 //b = (ia == ib) && (ia != ib) && (ia < ib);104 105 95 void constraints() { 96 _GraphItem i1; 97 _GraphItem i2 = i1; 98 _GraphItem i3 = INVALID; 99 100 i1 = i2 = i3; 101 102 bool b; 103 // b = (ia == ib) && (ia != ib) && (ia < ib); 104 b = (ia == ib) && (ia != ib); 105 b = (ia == INVALID) && (ib != INVALID); 106 106 b = (ia < ib); 107 108 109 110 107 } 108 109 const _GraphItem &ia; 110 const _GraphItem &ib; 111 111 }; 112 112 }; 113 113 114 114 /// \brief An empty base directed graph class. 115 /// 115 /// 116 116 /// This class provides the minimal set of features needed for a 117 117 /// directed graph structure. All digraph concepts have to be … … 123 123 124 124 typedef BaseDigraphComponent Digraph; 125 125 126 126 /// \brief Node class of the digraph. 127 127 /// 128 /// This class represents the Nodes of the digraph. 128 /// This class represents the Nodes of the digraph. 129 129 /// 130 130 typedef GraphItem<'n'> Node; … … 132 132 /// \brief Arc class of the digraph. 133 133 /// 134 /// This class represents the Arcs of the digraph. 134 /// This class represents the Arcs of the digraph. 135 135 /// 136 136 typedef GraphItem<'e'> Arc; … … 157 157 template <typename _Digraph> 158 158 struct Constraints { 159 160 161 162 163 164 165 166 167 168 169 159 typedef typename _Digraph::Node Node; 160 typedef typename _Digraph::Arc Arc; 161 162 void constraints() { 163 checkConcept<GraphItem<'n'>, Node>(); 164 checkConcept<GraphItem<'a'>, Arc>(); 165 { 166 Node n; 167 Arc e(INVALID); 168 n = digraph.source(e); 169 n = digraph.target(e); 170 170 n = digraph.oppositeNode(n, e); 171 } 172 173 174 171 } 172 } 173 174 const _Digraph& digraph; 175 175 }; 176 176 }; 177 177 178 178 /// \brief An empty base undirected graph class. 179 /// 179 /// 180 180 /// This class provides the minimal set of features needed for an 181 181 /// undirected graph structure. All undirected graph concepts have … … 200 200 typedef GraphItem<'u'> Parent; 201 201 /// \brief Default constructor. 202 /// 202 /// 203 203 /// \warning The default constructor is not required to set 204 204 /// the item to some welldefined value. So you should consider it … … 218 218 /// 219 219 /// Besides the core graph item functionality each arc should 220 /// be convertible to the represented edge. 220 /// be convertible to the represented edge. 221 221 Edge(const Arc&) {} 222 222 /// \brief Assign arc to edge. 223 223 /// 224 224 /// Besides the core graph item functionality each arc should 225 /// be convertible to the represented edge. 225 /// be convertible to the represented edge. 226 226 Edge& operator=(const Arc&) { return *this; } 227 227 }; … … 238 238 /// Returns the directed arc from its direction and the 239 239 /// represented edge. 240 Arc direct(const Edge&, bool) const { return INVALID;} 240 Arc direct(const Edge&, bool) const { return INVALID;} 241 241 242 242 /// \brief Returns the directed arc. … … 244 244 /// Returns the directed arc from its source and the 245 245 /// represented edge. 246 Arc direct(const Edge&, const Node&) const { return INVALID;} 246 Arc direct(const Edge&, const Node&) const { return INVALID;} 247 247 248 248 /// \brief Returns the opposite arc. … … 261 261 /// Gives back the other ending of an edge. 262 262 Node v(const Edge&) const { return INVALID;} 263 263 264 264 template <typename _Graph> 265 265 struct Constraints { 266 267 268 269 270 266 typedef typename _Graph::Node Node; 267 typedef typename _Graph::Arc Arc; 268 typedef typename _Graph::Edge Edge; 269 270 void constraints() { 271 271 checkConcept<BaseDigraphComponent, _Graph>(); 272 273 274 275 272 checkConcept<GraphItem<'u'>, Edge>(); 273 { 274 Node n; 275 Edge ue(INVALID); 276 276 Arc e; 277 278 277 n = graph.u(ue); 278 n = graph.v(ue); 279 279 e = graph.direct(ue, true); 280 280 e = graph.direct(ue, n); … … 283 283 bool d = graph.direction(e); 284 284 ignore_unused_variable_warning(d); 285 } 286 287 288 285 } 286 } 287 288 const _Graph& graph; 289 289 }; 290 290 … … 292 292 293 293 /// \brief An empty idable base digraph class. 294 /// 294 /// 295 295 /// This class provides beside the core digraph features 296 296 /// core id functions for the digraph structure. … … 305 305 typedef typename Base::Arc Arc; 306 306 307 /// \brief Gives back an unique integer id for the Node. 308 /// 309 /// Gives back an unique integer id for the Node. 307 /// \brief Gives back an unique integer id for the Node. 308 /// 309 /// Gives back an unique integer id for the Node. 310 310 /// 311 311 int id(const Node&) const { return 1;} … … 315 315 /// Gives back the node by the unique id. 316 316 /// If the digraph does not contain node with the given id 317 /// then the result of the function is undetermined. 317 /// then the result of the function is undetermined. 318 318 Node nodeFromId(int) const { return INVALID;} 319 319 320 /// \brief Gives back an unique integer id for the Arc. 321 /// 322 /// Gives back an unique integer id for the Arc. 320 /// \brief Gives back an unique integer id for the Arc. 321 /// 322 /// Gives back an unique integer id for the Arc. 323 323 /// 324 324 int id(const Arc&) const { return 1;} … … 328 328 /// Gives back the arc by the unique id. 329 329 /// If the digraph does not contain arc with the given id 330 /// then the result of the function is undetermined. 330 /// then the result of the function is undetermined. 331 331 Arc arcFromId(int) const { return INVALID;} 332 332 … … 348 348 struct Constraints { 349 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 350 void constraints() { 351 checkConcept<Base, _Digraph >(); 352 typename _Digraph::Node node; 353 int nid = digraph.id(node); 354 nid = digraph.id(node); 355 node = digraph.nodeFromId(nid); 356 typename _Digraph::Arc arc; 357 int eid = digraph.id(arc); 358 eid = digraph.id(arc); 359 arc = digraph.arcFromId(eid); 360 361 nid = digraph.maxNodeId(); 362 ignore_unused_variable_warning(nid); 363 eid = digraph.maxArcId(); 364 ignore_unused_variable_warning(eid); 365 } 366 367 const _Digraph& digraph; 368 368 }; 369 369 }; 370 370 371 371 /// \brief An empty idable base undirected graph class. 372 /// 372 /// 373 373 /// This class provides beside the core undirected graph features 374 374 /// core id functions for the undirected graph structure. The … … 384 384 using IDableDigraphComponent<_Base>::id; 385 385 386 /// \brief Gives back an unique integer id for the Edge. 387 /// 388 /// Gives back an unique integer id for the Edge. 386 /// \brief Gives back an unique integer id for the Edge. 387 /// 388 /// Gives back an unique integer id for the Edge. 389 389 /// 390 390 int id(const Edge&) const { return 1;} … … 407 407 struct Constraints { 408 408 409 410 411 412 413 414 415 416 417 418 419 420 409 void constraints() { 410 checkConcept<Base, _Graph >(); 411 checkConcept<IDableDigraphComponent<Base>, _Graph >(); 412 typename _Graph::Edge edge; 413 int ueid = graph.id(edge); 414 ueid = graph.id(edge); 415 edge = graph.edgeFromId(ueid); 416 ueid = graph.maxEdgeId(); 417 ignore_unused_variable_warning(ueid); 418 } 419 420 const _Graph& graph; 421 421 }; 422 422 }; … … 451 451 /// \brief Assign operator for items. 452 452 /// 453 /// The items are assignable. 454 /// 455 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 453 /// The items are assignable. 454 /// 455 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 456 456 /// \brief Next item. 457 /// 457 /// 458 458 /// Assign the iterator to the next item. 459 459 /// 460 460 GraphItemIt& operator++() { return *this; } 461 461 /// \brief Equality operator 462 /// 462 /// 463 463 /// Two iterators are equal if and only if they point to the 464 464 /// same object or both are invalid. 465 465 bool operator==(const GraphItemIt&) const { return true;} 466 466 /// \brief Inequality operator 467 /// 467 /// 468 468 /// \sa operator==(Node n) 469 469 /// 470 470 bool operator!=(const GraphItemIt&) const { return true;} 471 471 472 472 template<typename _GraphItemIt> 473 473 struct Constraints { 474 475 _GraphItemIt it1(g); 476 477 478 479 480 481 482 483 484 485 474 void constraints() { 475 _GraphItemIt it1(g); 476 _GraphItemIt it2; 477 478 it2 = ++it1; 479 ++it2 = it1; 480 ++(++it1); 481 482 _Item bi = it1; 483 bi = it2; 484 } 485 _Graph& g; 486 486 }; 487 487 }; … … 490 490 /// 491 491 /// \note Because InArcIt and OutArcIt may not inherit from the same 492 /// base class, the _selector is a additional template parameter. For 493 /// InArcIt you should instantiate it with character 'i' and for 492 /// base class, the _selector is a additional template parameter. For 493 /// InArcIt you should instantiate it with character 'i' and for 494 494 /// OutArcIt with 'o'. 495 495 template <typename _Graph, 496 497 typename _Base = typename _Graph::Node, 498 496 typename _Item = typename _Graph::Arc, 497 typename _Base = typename _Graph::Node, 498 char _selector = '0'> 499 499 class GraphIncIt : public _Item { 500 500 public: … … 509 509 /// 510 510 GraphIncIt(GraphIncIt const& gi) : _Item(gi) {} 511 /// \brief Sets the iterator to the first arc incoming into or outgoing 511 /// \brief Sets the iterator to the first arc incoming into or outgoing 512 512 /// from the node. 513 513 /// 514 /// Sets the iterator to the first arc incoming into or outgoing 514 /// Sets the iterator to the first arc incoming into or outgoing 515 515 /// from the node. 516 516 /// … … 523 523 /// \brief Assign operator for iterators. 524 524 /// 525 /// The iterators are assignable. 526 /// 527 GraphIncIt& operator=(GraphIncIt const&) { return *this; } 525 /// The iterators are assignable. 526 /// 527 GraphIncIt& operator=(GraphIncIt const&) { return *this; } 528 528 /// \brief Next item. 529 529 /// … … 546 546 template <typename _GraphIncIt> 547 547 struct Constraints { 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 548 void constraints() { 549 checkConcept<GraphItem<_selector>, _GraphIncIt>(); 550 _GraphIncIt it1(graph, node); 551 _GraphIncIt it2; 552 553 it2 = ++it1; 554 ++it2 = it1; 555 ++(++it1); 556 _Item e = it1; 557 e = it2; 558 559 } 560 561 _Item arc; 562 _Base node; 563 _Graph graph; 564 _GraphIncIt it; 565 565 }; 566 566 }; … … 576 576 577 577 public: 578 578 579 579 typedef _Base Base; 580 580 typedef typename Base::Node Node; … … 584 584 585 585 /// \name Base iteration 586 /// 586 /// 587 587 /// This interface provides functions for iteration on digraph items 588 588 /// 589 /// @{ 589 /// @{ 590 590 591 591 /// \brief Gives back the first node in the iterating order. 592 /// 592 /// 593 593 /// Gives back the first node in the iterating order. 594 /// 594 /// 595 595 void first(Node&) const {} 596 596 … … 598 598 /// 599 599 /// Gives back the next node in the iterating order. 600 /// 600 /// 601 601 void next(Node&) const {} 602 602 … … 604 604 /// 605 605 /// Gives back the first arc in the iterating order. 606 /// 606 /// 607 607 void first(Arc&) const {} 608 608 … … 610 610 /// 611 611 /// Gives back the next arc in the iterating order. 612 /// 612 /// 613 613 void next(Arc&) const {} 614 614 … … 618 618 /// 619 619 /// Gives back the first of the arcs point to the given node. 620 /// 620 /// 621 621 void firstIn(Arc&, const Node&) const {} 622 622 … … 630 630 /// \brief Gives back the first of the arcs start from the 631 631 /// given node. 632 /// 632 /// 633 633 /// Gives back the first of the arcs start from the given node. 634 /// 634 /// 635 635 void firstOut(Arc&, const Node&) const {} 636 636 … … 639 639 /// 640 640 /// Gives back the next of the arcs start from the given node. 641 /// 641 /// 642 642 void nextOut(Arc&) const {} 643 643 … … 645 645 646 646 /// \name Class based iteration 647 /// 647 /// 648 648 /// This interface provides functions for iteration on digraph items 649 649 /// … … 700 700 /// @} 701 701 702 template <typename _Digraph> 703 struct Constraints { 704 705 702 template <typename _Digraph> 703 struct Constraints { 704 void constraints() { 705 checkConcept<Base, _Digraph>(); 706 706 707 707 { 708 typename _Digraph::Node node(INVALID); 708 typename _Digraph::Node node(INVALID); 709 709 typename _Digraph::Arc arc(INVALID); 710 710 { … … 724 724 digraph.nextOut(arc); 725 725 } 726 } 726 } 727 727 728 728 { … … 731 731 checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>, 732 732 typename _Digraph::NodeIt >(); 733 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 733 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 734 734 typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>(); 735 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 735 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 736 736 typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>(); 737 737 … … 746 746 } 747 747 } 748 749 750 748 749 const _Digraph& digraph; 750 751 751 }; 752 752 }; … … 766 766 typedef typename Base::Edge Edge; 767 767 768 768 769 769 typedef IterableGraphComponent Graph; 770 770 771 771 /// \name Base iteration 772 /// 772 /// 773 773 /// This interface provides functions for iteration on graph items 774 /// @{ 774 /// @{ 775 775 776 776 using IterableDigraphComponent<_Base>::first; … … 781 781 /// 782 782 /// Gives back the first edge in the iterating order. 783 /// 783 /// 784 784 void first(Edge&) const {} 785 785 … … 788 788 /// 789 789 /// Gives back the next edge in the iterating order. 790 /// 790 /// 791 791 void next(Edge&) const {} 792 792 … … 815 815 816 816 /// \name Class based iteration 817 /// 817 /// 818 818 /// This interface provides functions for iteration on graph items 819 819 /// … … 842 842 /// @} 843 843 844 template <typename _Graph> 845 struct Constraints { 846 847 844 template <typename _Graph> 845 struct Constraints { 846 void constraints() { 847 checkConcept<IterableDigraphComponent<Base>, _Graph>(); 848 848 849 849 { … … 859 859 graph.nextInc(edge, dir); 860 860 } 861 862 } 863 861 862 } 863 864 864 { 865 865 checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>, 866 866 typename _Graph::EdgeIt >(); 867 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 867 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 868 868 typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>(); 869 869 870 870 typename _Graph::Node n; 871 871 typename _Graph::IncEdgeIt ueit(INVALID); … … 874 874 } 875 875 } 876 877 878 876 877 const _Graph& graph; 878 879 879 }; 880 880 }; 881 881 882 882 /// \brief An empty alteration notifier digraph class. 883 /// 883 /// 884 884 /// This class provides beside the core digraph features alteration 885 885 /// notifier interface for the digraph structure. This implements … … 898 898 899 899 /// The node observer registry. 900 typedef AlterationNotifier<AlterableDigraphComponent, Node> 900 typedef AlterationNotifier<AlterableDigraphComponent, Node> 901 901 NodeNotifier; 902 902 /// The arc observer registry. 903 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 903 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 904 904 ArcNotifier; 905 905 906 906 /// \brief Gives back the node alteration notifier. 907 907 /// 908 908 /// Gives back the node alteration notifier. 909 909 NodeNotifier& notifier(Node) const { 910 910 return NodeNotifier(); 911 911 } 912 912 913 913 /// \brief Gives back the arc alteration notifier. 914 914 /// 915 915 /// Gives back the arc alteration notifier. 916 916 ArcNotifier& notifier(Arc) const { 917 917 return ArcNotifier(); 918 918 } 919 919 920 template <typename _Digraph> 921 struct Constraints { 922 923 924 typename _Digraph::NodeNotifier& nn 920 template <typename _Digraph> 921 struct Constraints { 922 void constraints() { 923 checkConcept<Base, _Digraph>(); 924 typename _Digraph::NodeNotifier& nn 925 925 = digraph.notifier(typename _Digraph::Node()); 926 926 927 typename _Digraph::ArcNotifier& en 927 typename _Digraph::ArcNotifier& en 928 928 = digraph.notifier(typename _Digraph::Arc()); 929 929 930 930 ignore_unused_variable_warning(nn); 931 931 ignore_unused_variable_warning(en); 932 933 934 935 936 }; 937 932 } 933 934 const _Digraph& digraph; 935 936 }; 937 938 938 }; 939 939 940 940 /// \brief An empty alteration notifier undirected graph class. 941 /// 941 /// 942 942 /// This class provides beside the core graph features alteration 943 943 /// notifier interface for the graph structure. This implements … … 955 955 956 956 /// The arc observer registry. 957 typedef AlterationNotifier<AlterableGraphComponent, Edge> 957 typedef AlterationNotifier<AlterableGraphComponent, Edge> 958 958 EdgeNotifier; 959 959 960 960 /// \brief Gives back the arc alteration notifier. 961 961 /// 962 962 /// Gives back the arc alteration notifier. 963 963 EdgeNotifier& notifier(Edge) const { 964 964 return EdgeNotifier(); 965 965 } 966 966 967 template <typename _Graph> 968 struct Constraints { 969 970 971 typename _Graph::EdgeNotifier& uen 967 template <typename _Graph> 968 struct Constraints { 969 void constraints() { 970 checkConcept<AlterableGraphComponent<Base>, _Graph>(); 971 typename _Graph::EdgeNotifier& uen 972 972 = graph.notifier(typename _Graph::Edge()); 973 973 ignore_unused_variable_warning(uen); 974 975 976 977 978 }; 979 974 } 975 976 const _Graph& graph; 977 978 }; 979 980 980 }; 981 981 982 982 /// \brief Class describing the concept of graph maps 983 /// 983 /// 984 984 /// This class describes the common interface of the graph maps 985 985 /// (NodeMap, ArcMap), that is \ref mapspage "maps" which can be used to … … 1010 1010 /// Copy Constructor. 1011 1011 GraphMap(const GraphMap&) : Parent() {} 1012 1012 1013 1013 /// \brief Assign operator. 1014 1014 /// 1015 1015 /// Assign operator. It does not mofify the underlying graph, 1016 1016 /// it just iterates on the current item set and set the map 1017 /// with the value returned by the assigned map. 1017 /// with the value returned by the assigned map. 1018 1018 template <typename CMap> 1019 GraphMap& operator=(const CMap&) { 1019 GraphMap& operator=(const CMap&) { 1020 1020 checkConcept<ReadMap<Key, Value>, CMap>(); 1021 1021 return *this; … … 1024 1024 template<typename _Map> 1025 1025 struct Constraints { 1026 1027 1028 1029 1030 1031 1032 1033 1034 1026 void constraints() { 1027 checkConcept<ReadWriteMap<Key, Value>, _Map >(); 1028 // Construction with a graph parameter 1029 _Map a(g); 1030 // Constructor with a graph and a default value parameter 1031 _Map a2(g,t); 1032 // Copy constructor. 1033 _Map b(c); 1034 1035 1035 ReadMap<Key, Value> cmap; 1036 1036 b = cmap; 1037 1037 1038 1039 1040 1041 1042 1043 1044 1038 ignore_unused_variable_warning(a2); 1039 ignore_unused_variable_warning(b); 1040 } 1041 1042 const _Map &c; 1043 const Graph &g; 1044 const typename GraphMap::Value &t; 1045 1045 }; 1046 1046 … … 1071 1071 typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent; 1072 1072 1073 1074 1075 1076 explicit NodeMap(const MappableDigraphComponent& digraph) 1073 /// \brief Construct a new map. 1074 /// 1075 /// Construct a new map for the digraph. 1076 explicit NodeMap(const MappableDigraphComponent& digraph) 1077 1077 : Parent(digraph) {} 1078 1078 1079 1080 1081 1082 1079 /// \brief Construct a new map with default value. 1080 /// 1081 /// Construct a new map for the digraph and initalise the values. 1082 NodeMap(const MappableDigraphComponent& digraph, const _Value& value) 1083 1083 : Parent(digraph, value) {} 1084 1084 1085 1086 1087 1088 1089 1090 1091 1092 1085 /// \brief Copy constructor. 1086 /// 1087 /// Copy Constructor. 1088 NodeMap(const NodeMap& nm) : Parent(nm) {} 1089 1090 /// \brief Assign operator. 1091 /// 1092 /// Assign operator. 1093 1093 template <typename CMap> 1094 NodeMap& operator=(const CMap&) { 1094 NodeMap& operator=(const CMap&) { 1095 1095 checkConcept<ReadMap<Node, _Value>, CMap>(); 1096 1096 return *this; … … 1108 1108 typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent; 1109 1109 1110 1111 1112 1113 explicit ArcMap(const MappableDigraphComponent& digraph) 1110 /// \brief Construct a new map. 1111 /// 1112 /// Construct a new map for the digraph. 1113 explicit ArcMap(const MappableDigraphComponent& digraph) 1114 1114 : Parent(digraph) {} 1115 1115 1116 1117 1118 1119 1116 /// \brief Construct a new map with default value. 1117 /// 1118 /// Construct a new map for the digraph and initalise the values. 1119 ArcMap(const MappableDigraphComponent& digraph, const _Value& value) 1120 1120 : Parent(digraph, value) {} 1121 1121 1122 1123 1124 1125 1126 1127 1128 1129 1122 /// \brief Copy constructor. 1123 /// 1124 /// Copy Constructor. 1125 ArcMap(const ArcMap& nm) : Parent(nm) {} 1126 1127 /// \brief Assign operator. 1128 /// 1129 /// Assign operator. 1130 1130 template <typename CMap> 1131 ArcMap& operator=(const CMap&) { 1131 ArcMap& operator=(const CMap&) { 1132 1132 checkConcept<ReadMap<Arc, _Value>, CMap>(); 1133 1133 return *this; … … 1140 1140 struct Constraints { 1141 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>, 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 } 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>, 1175 1176 } 1177 1178 1179 1142 struct Dummy { 1143 int value; 1144 Dummy() : value(0) {} 1145 Dummy(int _v) : value(_v) {} 1146 }; 1147 1148 void constraints() { 1149 checkConcept<Base, _Digraph>(); 1150 { // int map test 1151 typedef typename _Digraph::template NodeMap<int> IntNodeMap; 1152 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>, 1153 IntNodeMap >(); 1154 } { // bool map test 1155 typedef typename _Digraph::template NodeMap<bool> BoolNodeMap; 1156 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>, 1157 BoolNodeMap >(); 1158 } { // Dummy map test 1159 typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap; 1160 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>, 1161 DummyNodeMap >(); 1162 } 1163 1164 { // int map test 1165 typedef typename _Digraph::template ArcMap<int> IntArcMap; 1166 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>, 1167 IntArcMap >(); 1168 } { // bool map test 1169 typedef typename _Digraph::template ArcMap<bool> BoolArcMap; 1170 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>, 1171 BoolArcMap >(); 1172 } { // Dummy map test 1173 typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap; 1174 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>, 1175 DummyArcMap >(); 1176 } 1177 } 1178 1179 _Digraph& digraph; 1180 1180 }; 1181 1181 }; … … 1200 1200 /// 1201 1201 template <typename _Value> 1202 class EdgeMap : public GraphMap<Graph, Edge, _Value> { 1202 class EdgeMap : public GraphMap<Graph, Edge, _Value> { 1203 1203 public: 1204 1204 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent; 1205 1205 1206 1207 1208 1209 explicit EdgeMap(const MappableGraphComponent& graph) 1206 /// \brief Construct a new map. 1207 /// 1208 /// Construct a new map for the graph. 1209 explicit EdgeMap(const MappableGraphComponent& graph) 1210 1210 : Parent(graph) {} 1211 1211 1212 1213 1214 1215 1212 /// \brief Construct a new map with default value. 1213 /// 1214 /// Construct a new map for the graph and initalise the values. 1215 EdgeMap(const MappableGraphComponent& graph, const _Value& value) 1216 1216 : Parent(graph, value) {} 1217 1217 1218 1219 1220 1221 1222 1223 1224 1225 1218 /// \brief Copy constructor. 1219 /// 1220 /// Copy Constructor. 1221 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1222 1223 /// \brief Assign operator. 1224 /// 1225 /// Assign operator. 1226 1226 template <typename CMap> 1227 EdgeMap& operator=(const CMap&) { 1227 EdgeMap& operator=(const CMap&) { 1228 1228 checkConcept<ReadMap<Edge, _Value>, CMap>(); 1229 1229 return *this; … … 1236 1236 struct Constraints { 1237 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>, 1258 1259 } 1260 1261 1262 1238 struct Dummy { 1239 int value; 1240 Dummy() : value(0) {} 1241 Dummy(int _v) : value(_v) {} 1242 }; 1243 1244 void constraints() { 1245 checkConcept<MappableGraphComponent<Base>, _Graph>(); 1246 1247 { // int map test 1248 typedef typename _Graph::template EdgeMap<int> IntEdgeMap; 1249 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, 1250 IntEdgeMap >(); 1251 } { // bool map test 1252 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap; 1253 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, 1254 BoolEdgeMap >(); 1255 } { // Dummy map test 1256 typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap; 1257 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>, 1258 DummyEdgeMap >(); 1259 } 1260 } 1261 1262 _Graph& graph; 1263 1263 }; 1264 1264 }; … … 1283 1283 /// 1284 1284 Node addNode() { 1285 1285 return INVALID; 1286 1286 } 1287 1287 1288 1288 /// \brief Adds a new arc connects the given two nodes. 1289 1289 /// 1290 1290 /// Adds a new arc connects the the given two nodes. 1291 1291 Arc addArc(const Node&, const Node&) { 1292 1292 return INVALID; 1293 1293 } 1294 1294 1295 1295 template <typename _Digraph> 1296 1296 struct Constraints { 1297 1297 void constraints() { 1298 1298 checkConcept<Base, _Digraph>(); 1299 1300 1301 1302 1303 1304 1305 1306 1299 typename _Digraph::Node node_a, node_b; 1300 node_a = digraph.addNode(); 1301 node_b = digraph.addNode(); 1302 typename _Digraph::Arc arc; 1303 arc = digraph.addArc(node_a, node_b); 1304 } 1305 1306 _Digraph& digraph; 1307 1307 }; 1308 1308 }; … … 1328 1328 /// 1329 1329 Node addNode() { 1330 1330 return INVALID; 1331 1331 } 1332 1332 1333 1333 /// \brief Adds a new arc connects the given two nodes. 1334 1334 /// 1335 1335 /// Adds a new arc connects the the given two nodes. 1336 1336 Edge addArc(const Node&, const Node&) { 1337 1337 return INVALID; 1338 1338 } 1339 1339 1340 1340 template <typename _Graph> 1341 1341 struct Constraints { 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1342 void constraints() { 1343 checkConcept<Base, _Graph>(); 1344 typename _Graph::Node node_a, node_b; 1345 node_a = graph.addNode(); 1346 node_b = graph.addNode(); 1347 typename _Graph::Edge edge; 1348 edge = graph.addEdge(node_a, node_b); 1349 } 1350 1351 _Graph& graph; 1352 1352 }; 1353 1353 }; 1354 1354 1355 1355 /// \brief An empty erasable digraph class. 1356 /// 1356 /// 1357 1357 /// This class provides beside the core digraph features core erase 1358 1358 /// functions for the digraph structure. The main difference between … … 1369 1369 /// \brief Erase a node from the digraph. 1370 1370 /// 1371 /// Erase a node from the digraph. This function should 1371 /// Erase a node from the digraph. This function should 1372 1372 /// erase all arcs connecting to the node. 1373 void erase(const Node&) {} 1373 void erase(const Node&) {} 1374 1374 1375 1375 /// \brief Erase an arc from the digraph. … … 1381 1381 template <typename _Digraph> 1382 1382 struct Constraints { 1383 1383 void constraints() { 1384 1384 checkConcept<Base, _Digraph>(); 1385 1386 1387 1388 1389 1390 1391 1385 typename _Digraph::Node node; 1386 digraph.erase(node); 1387 typename _Digraph::Arc arc; 1388 digraph.erase(arc); 1389 } 1390 1391 _Digraph& digraph; 1392 1392 }; 1393 1393 }; 1394 1394 1395 1395 /// \brief An empty erasable base undirected graph class. 1396 /// 1396 /// 1397 1397 /// This class provides beside the core undirected graph features 1398 1398 /// core erase functions for the undirceted graph structure. The … … 1411 1411 /// Erase a node from the graph. This function should erase 1412 1412 /// arcs connecting to the node. 1413 void erase(const Node&) {} 1413 void erase(const Node&) {} 1414 1414 1415 1415 /// \brief Erase an arc from the graph. … … 1421 1421 template <typename _Graph> 1422 1422 struct Constraints { 1423 1423 void constraints() { 1424 1424 checkConcept<Base, _Graph>(); 1425 1426 1427 1428 1429 1430 1431 1425 typename _Graph::Node node; 1426 graph.erase(node); 1427 typename _Graph::Edge edge; 1428 graph.erase(edge); 1429 } 1430 1431 _Graph& graph; 1432 1432 }; 1433 1433 }; … … 1449 1449 /// Erase all nodes and arcs from the digraph. 1450 1450 /// 1451 void clear() {} 1451 void clear() {} 1452 1452 1453 1453 template <typename _Digraph> 1454 1454 struct Constraints { 1455 1455 void constraints() { 1456 1456 checkConcept<Base, _Digraph>(); 1457 1458 1459 1460 1457 digraph.clear(); 1458 } 1459 1460 _Digraph digraph; 1461 1461 }; 1462 1462 }; … … 1476 1476 template <typename _Graph> 1477 1477 struct Constraints { 1478 1478 void constraints() { 1479 1479 checkConcept<ClearableGraphComponent<Base>, _Graph>(); 1480 1481 1482 1480 } 1481 1482 _Graph graph; 1483 1483 }; 1484 1484 };
Note: See TracChangeset
for help on using the changeset viewer.