Changeset 559:c5fd2d996909 in lemon1.2 for lemon/concepts/graph_components.h
 Timestamp:
 03/29/09 23:08:20 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/graph_components.h
r534 r559 21 21 ///\brief The concept of graph components. 22 22 23 24 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H 25 24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H … … 45 44 46 45 #ifndef DOXYGEN 47 template <char _selector= '0'>46 template <char sel = '0'> 48 47 #endif 49 48 class GraphItem { … … 297 296 /// The most of the base digraphs should conform to this concept. 298 297 /// The id's are unique and immutable. 299 template <typename _Base= BaseDigraphComponent>300 class IDableDigraphComponent : public _Base{301 public: 302 303 typedef _BaseBase;298 template <typename BAS = BaseDigraphComponent> 299 class IDableDigraphComponent : public BAS { 300 public: 301 302 typedef BAS Base; 304 303 typedef typename Base::Node Node; 305 304 typedef typename Base::Arc Arc; … … 375 374 /// most of the base undirected graphs should conform to this 376 375 /// concept. The id's are unique and immutable. 377 template <typename _Base= BaseGraphComponent>378 class IDableGraphComponent : public IDableDigraphComponent< _Base> {379 public: 380 381 typedef _BaseBase;376 template <typename BAS = BaseGraphComponent> 377 class IDableGraphComponent : public IDableDigraphComponent<BAS> { 378 public: 379 380 typedef BAS Base; 382 381 typedef typename Base::Edge Edge; 383 382 384 using IDableDigraphComponent< _Base>::id;383 using IDableDigraphComponent<Base>::id; 385 384 386 385 /// \brief Gives back an unique integer id for the Edge. … … 426 425 /// Skeleton class for graph NodeIt and ArcIt. 427 426 /// 428 template <typename _Graph, typename _Item>429 class GraphItemIt : public _Item {427 template <typename GR, typename Item> 428 class GraphItemIt : public Item { 430 429 public: 431 430 /// \brief Default constructor. … … 443 442 /// Sets the iterator to the first item of \c the graph. 444 443 /// 445 explicit GraphItemIt(const _Graph&) {}444 explicit GraphItemIt(const GR&) {} 446 445 /// \brief Invalid constructor \& conversion. 447 446 /// … … 480 479 ++(++it1); 481 480 482 _Item bi = it1;481 Item bi = it1; 483 482 bi = it2; 484 483 } 485 _Graph& g;484 GR& g; 486 485 }; 487 486 }; … … 490 489 /// 491 490 /// \note Because InArcIt and OutArcIt may not inherit from the same 492 /// base class, the _selector is a additional template parameter. For493 /// InArcIt you should instantiate it with character 'i' and for491 /// base class, the \c sel is a additional template parameter (selector). 492 /// For InArcIt you should instantiate it with character 'i' and for 494 493 /// OutArcIt with 'o'. 495 template <typename _Graph,496 typename _Item = typename _Graph::Arc,497 typename _Base = typename _Graph::Node,498 char _selector= '0'>499 class GraphIncIt : public _Item {494 template <typename GR, 495 typename Item = typename GR::Arc, 496 typename Base = typename GR::Node, 497 char sel = '0'> 498 class GraphIncIt : public Item { 500 499 public: 501 500 /// \brief Default constructor. … … 508 507 /// Copy constructor. 509 508 /// 510 GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}509 GraphIncIt(GraphIncIt const& gi) : Item(gi) {} 511 510 /// \brief Sets the iterator to the first arc incoming into or outgoing 512 511 /// from the node. … … 515 514 /// from the node. 516 515 /// 517 explicit GraphIncIt(const _Graph&, const _Base&) {}516 explicit GraphIncIt(const GR&, const Base&) {} 518 517 /// \brief Invalid constructor \& conversion. 519 518 /// … … 547 546 struct Constraints { 548 547 void constraints() { 549 checkConcept<GraphItem< _selector>, _GraphIncIt>();548 checkConcept<GraphItem<sel>, _GraphIncIt>(); 550 549 _GraphIncIt it1(graph, node); 551 550 _GraphIncIt it2; … … 554 553 ++it2 = it1; 555 554 ++(++it1); 556 _Item e = it1;555 Item e = it1; 557 556 e = it2; 558 557 559 558 } 560 559 561 _Item arc;562 _Base node;563 _Graphgraph;560 Item arc; 561 Base node; 562 GR graph; 564 563 _GraphIncIt it; 565 564 }; … … 572 571 /// iterator based iterable interface for the digraph structure. 573 572 /// This concept is part of the Digraph concept. 574 template <typename _Base= BaseDigraphComponent>575 class IterableDigraphComponent : public _Base{576 577 public: 578 579 typedef _BaseBase;573 template <typename BAS = BaseDigraphComponent> 574 class IterableDigraphComponent : public BAS { 575 576 public: 577 578 typedef BAS Base; 580 579 typedef typename Base::Node Node; 581 580 typedef typename Base::Arc Arc; … … 757 756 /// based iterable interface for the undirected graph structure. 758 757 /// This concept is part of the Graph concept. 759 template <typename _Base= BaseGraphComponent>760 class IterableGraphComponent : public IterableDigraphComponent< _Base> {761 public: 762 763 typedef _BaseBase;758 template <typename BAS = BaseGraphComponent> 759 class IterableGraphComponent : public IterableDigraphComponent<BAS> { 760 public: 761 762 typedef BAS Base; 764 763 typedef typename Base::Node Node; 765 764 typedef typename Base::Arc Arc; … … 774 773 /// @{ 775 774 776 using IterableDigraphComponent< _Base>::first;777 using IterableDigraphComponent< _Base>::next;775 using IterableDigraphComponent<Base>::first; 776 using IterableDigraphComponent<Base>::next; 778 777 779 778 /// \brief Gives back the first edge in the iterating … … 809 808 void nextInc(Edge&, bool&) const {} 810 809 811 using IterableDigraphComponent< _Base>::baseNode;812 using IterableDigraphComponent< _Base>::runningNode;810 using IterableDigraphComponent<Base>::baseNode; 811 using IterableDigraphComponent<Base>::runningNode; 813 812 814 813 /// @} … … 876 875 877 876 const _Graph& graph; 878 879 877 }; 880 878 }; … … 888 886 /// alteration occured in the digraph all the observers will 889 887 /// notified about it. 890 template <typename _Base= BaseDigraphComponent>891 class AlterableDigraphComponent : public _Base{892 public: 893 894 typedef _BaseBase;888 template <typename BAS = BaseDigraphComponent> 889 class AlterableDigraphComponent : public BAS { 890 public: 891 892 typedef BAS Base; 895 893 typedef typename Base::Node Node; 896 894 typedef typename Base::Arc Arc; … … 946 944 /// alteration occured in the graph all the observers will 947 945 /// notified about it. 948 template <typename _Base= BaseGraphComponent>949 class AlterableGraphComponent : public AlterableDigraphComponent< _Base> {950 public: 951 952 typedef _BaseBase;946 template <typename BAS = BaseGraphComponent> 947 class AlterableGraphComponent : public AlterableDigraphComponent<BAS> { 948 public: 949 950 typedef BAS Base; 953 951 typedef typename Base::Edge Edge; 954 952 … … 975 973 976 974 const _Graph& graph; 977 978 }; 979 975 }; 980 976 }; 981 977 … … 985 981 /// (NodeMap, ArcMap), that is maps that can be used to 986 982 /// associate data to graph descriptors (nodes or arcs). 987 template <typename _Graph, typename _Item, typename _Value>988 class GraphMap : public ReadWriteMap< _Item, _Value> {989 public: 990 991 typedef ReadWriteMap< _Item, _Value> Parent;983 template <typename GR, typename K, typename V> 984 class GraphMap : public ReadWriteMap<K, V> { 985 public: 986 987 typedef ReadWriteMap<K, V> Parent; 992 988 993 989 /// The graph type of the map. 994 typedef _GraphGraph;990 typedef GR Graph; 995 991 /// The key type of the map. 996 typedef _ItemKey;992 typedef K Key; 997 993 /// The value type of the map. 998 typedef _ValueValue;994 typedef V Value; 999 995 1000 996 /// \brief Construct a new map. … … 1056 1052 /// map interface for the digraph structure. 1057 1053 /// This concept is part of the Digraph concept. 1058 template <typename _Base= BaseDigraphComponent>1059 class MappableDigraphComponent : public _Base{1060 public: 1061 1062 typedef _BaseBase;1054 template <typename BAS = BaseDigraphComponent> 1055 class MappableDigraphComponent : public BAS { 1056 public: 1057 1058 typedef BAS Base; 1063 1059 typedef typename Base::Node Node; 1064 1060 typedef typename Base::Arc Arc; … … 1070 1066 /// ReadWrite map of the nodes. 1071 1067 /// 1072 template <typename _Value>1073 class NodeMap : public GraphMap<Digraph, Node, _Value> {1068 template <typename V> 1069 class NodeMap : public GraphMap<Digraph, Node, V> { 1074 1070 public: 1075 typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;1071 typedef GraphMap<MappableDigraphComponent, Node, V> Parent; 1076 1072 1077 1073 /// \brief Construct a new map. … … 1084 1080 /// 1085 1081 /// Construct a new map for the digraph and initalise the values. 1086 NodeMap(const MappableDigraphComponent& digraph, const _Value& value)1082 NodeMap(const MappableDigraphComponent& digraph, const V& value) 1087 1083 : Parent(digraph, value) {} 1088 1084 … … 1098 1094 template <typename CMap> 1099 1095 NodeMap& operator=(const CMap&) { 1100 checkConcept<ReadMap<Node, _Value>, CMap>();1096 checkConcept<ReadMap<Node, V>, CMap>(); 1101 1097 return *this; 1102 1098 } … … 1108 1104 /// ReadWrite map of the arcs. 1109 1105 /// 1110 template <typename _Value>1111 class ArcMap : public GraphMap<Digraph, Arc, _Value> {1106 template <typename V> 1107 class ArcMap : public GraphMap<Digraph, Arc, V> { 1112 1108 public: 1113 typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;1109 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent; 1114 1110 1115 1111 /// \brief Construct a new map. … … 1122 1118 /// 1123 1119 /// Construct a new map for the digraph and initalise the values. 1124 ArcMap(const MappableDigraphComponent& digraph, const _Value& value)1120 ArcMap(const MappableDigraphComponent& digraph, const V& value) 1125 1121 : Parent(digraph, value) {} 1126 1122 … … 1136 1132 template <typename CMap> 1137 1133 ArcMap& operator=(const CMap&) { 1138 checkConcept<ReadMap<Arc, _Value>, CMap>();1134 checkConcept<ReadMap<Arc, V>, CMap>(); 1139 1135 return *this; 1140 1136 } … … 1192 1188 /// map interface for the graph structure. 1193 1189 /// This concept is part of the Graph concept. 1194 template <typename _Base= BaseGraphComponent>1195 class MappableGraphComponent : public MappableDigraphComponent< _Base> {1196 public: 1197 1198 typedef _BaseBase;1190 template <typename BAS = BaseGraphComponent> 1191 class MappableGraphComponent : public MappableDigraphComponent<BAS> { 1192 public: 1193 1194 typedef BAS Base; 1199 1195 typedef typename Base::Edge Edge; 1200 1196 … … 1205 1201 /// ReadWrite map of the edges. 1206 1202 /// 1207 template <typename _Value>1208 class EdgeMap : public GraphMap<Graph, Edge, _Value> {1203 template <typename V> 1204 class EdgeMap : public GraphMap<Graph, Edge, V> { 1209 1205 public: 1210 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;1206 typedef GraphMap<MappableGraphComponent, Edge, V> Parent; 1211 1207 1212 1208 /// \brief Construct a new map. … … 1219 1215 /// 1220 1216 /// Construct a new map for the graph and initalise the values. 1221 EdgeMap(const MappableGraphComponent& graph, const _Value& value)1217 EdgeMap(const MappableGraphComponent& graph, const V& value) 1222 1218 : Parent(graph, value) {} 1223 1219 … … 1233 1229 template <typename CMap> 1234 1230 EdgeMap& operator=(const CMap&) { 1235 checkConcept<ReadMap<Edge, _Value>, CMap>();1231 checkConcept<ReadMap<Edge, V>, CMap>(); 1236 1232 return *this; 1237 1233 } … … 1277 1273 /// difference between the base and this interface is that the 1278 1274 /// digraph alterations should handled already on this level. 1279 template <typename _Base= BaseDigraphComponent>1280 class ExtendableDigraphComponent : public _Base{1281 public: 1282 typedef _BaseBase;1283 1284 typedef typename _Base::Node Node;1285 typedef typename _Base::Arc Arc;1275 template <typename BAS = BaseDigraphComponent> 1276 class ExtendableDigraphComponent : public BAS { 1277 public: 1278 typedef BAS Base; 1279 1280 typedef typename Base::Node Node; 1281 typedef typename Base::Arc Arc; 1286 1282 1287 1283 /// \brief Adds a new node to the digraph. … … 1322 1318 /// that the graph alterations should handled already on this 1323 1319 /// level. 1324 template <typename _Base= BaseGraphComponent>1325 class ExtendableGraphComponent : public _Base{1326 public: 1327 1328 typedef _BaseBase;1329 typedef typename _Base::Node Node;1330 typedef typename _Base::Edge Edge;1320 template <typename BAS = BaseGraphComponent> 1321 class ExtendableGraphComponent : public BAS { 1322 public: 1323 1324 typedef BAS Base; 1325 typedef typename Base::Node Node; 1326 typedef typename Base::Edge Edge; 1331 1327 1332 1328 /// \brief Adds a new node to the graph. … … 1366 1362 /// the base and this interface is that the digraph alterations 1367 1363 /// should handled already on this level. 1368 template <typename _Base= BaseDigraphComponent>1369 class ErasableDigraphComponent : public _Base{1370 public: 1371 1372 typedef _BaseBase;1364 template <typename BAS = BaseDigraphComponent> 1365 class ErasableDigraphComponent : public BAS { 1366 public: 1367 1368 typedef BAS Base; 1373 1369 typedef typename Base::Node Node; 1374 1370 typedef typename Base::Arc Arc; … … 1406 1402 /// main difference between the base and this interface is that 1407 1403 /// the graph alterations should handled already on this level. 1408 template <typename _Base= BaseGraphComponent>1409 class ErasableGraphComponent : public _Base{1410 public: 1411 1412 typedef _BaseBase;1404 template <typename BAS = BaseGraphComponent> 1405 class ErasableGraphComponent : public BAS { 1406 public: 1407 1408 typedef BAS Base; 1413 1409 typedef typename Base::Node Node; 1414 1410 typedef typename Base::Edge Edge; … … 1446 1442 /// the base and this interface is that the digraph alterations 1447 1443 /// should handled already on this level. 1448 template <typename _Base= BaseDigraphComponent>1449 class ClearableDigraphComponent : public _Base{1450 public: 1451 1452 typedef _BaseBase;1444 template <typename BAS = BaseDigraphComponent> 1445 class ClearableDigraphComponent : public BAS { 1446 public: 1447 1448 typedef BAS Base; 1453 1449 1454 1450 /// \brief Erase all nodes and arcs from the digraph. … … 1475 1471 /// main difference between the base and this interface is that 1476 1472 /// the graph alterations should handled already on this level. 1477 template <typename _Base= BaseGraphComponent>1478 class ClearableGraphComponent : public ClearableDigraphComponent< _Base> {1479 public: 1480 1481 typedef _BaseBase;1473 template <typename BAS = BaseGraphComponent> 1474 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> { 1475 public: 1476 1477 typedef BAS Base; 1482 1478 1483 1479 template <typename _Graph>
Note: See TracChangeset
for help on using the changeset viewer.