1.1 --- a/lemon/concepts/graph_components.h Thu Mar 05 10:13:20 2009 +0000
1.2 +++ b/lemon/concepts/graph_components.h Sun Mar 29 23:08:20 2009 +0200
1.3 @@ -20,7 +20,6 @@
1.4 ///\file
1.5 ///\brief The concept of graph components.
1.6
1.7 -
1.8 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
1.9 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
1.10
1.11 @@ -44,7 +43,7 @@
1.12 /// with 'a'.
1.13
1.14 #ifndef DOXYGEN
1.15 - template <char _selector = '0'>
1.16 + template <char sel = '0'>
1.17 #endif
1.18 class GraphItem {
1.19 public:
1.20 @@ -296,11 +295,11 @@
1.21 /// core id functions for the digraph structure.
1.22 /// The most of the base digraphs should conform to this concept.
1.23 /// The id's are unique and immutable.
1.24 - template <typename _Base = BaseDigraphComponent>
1.25 - class IDableDigraphComponent : public _Base {
1.26 + template <typename BAS = BaseDigraphComponent>
1.27 + class IDableDigraphComponent : public BAS {
1.28 public:
1.29
1.30 - typedef _Base Base;
1.31 + typedef BAS Base;
1.32 typedef typename Base::Node Node;
1.33 typedef typename Base::Arc Arc;
1.34
1.35 @@ -374,14 +373,14 @@
1.36 /// core id functions for the undirected graph structure. The
1.37 /// most of the base undirected graphs should conform to this
1.38 /// concept. The id's are unique and immutable.
1.39 - template <typename _Base = BaseGraphComponent>
1.40 - class IDableGraphComponent : public IDableDigraphComponent<_Base> {
1.41 + template <typename BAS = BaseGraphComponent>
1.42 + class IDableGraphComponent : public IDableDigraphComponent<BAS> {
1.43 public:
1.44
1.45 - typedef _Base Base;
1.46 + typedef BAS Base;
1.47 typedef typename Base::Edge Edge;
1.48
1.49 - using IDableDigraphComponent<_Base>::id;
1.50 + using IDableDigraphComponent<Base>::id;
1.51
1.52 /// \brief Gives back an unique integer id for the Edge.
1.53 ///
1.54 @@ -425,8 +424,8 @@
1.55 ///
1.56 /// Skeleton class for graph NodeIt and ArcIt.
1.57 ///
1.58 - template <typename _Graph, typename _Item>
1.59 - class GraphItemIt : public _Item {
1.60 + template <typename GR, typename Item>
1.61 + class GraphItemIt : public Item {
1.62 public:
1.63 /// \brief Default constructor.
1.64 ///
1.65 @@ -442,7 +441,7 @@
1.66 ///
1.67 /// Sets the iterator to the first item of \c the graph.
1.68 ///
1.69 - explicit GraphItemIt(const _Graph&) {}
1.70 + explicit GraphItemIt(const GR&) {}
1.71 /// \brief Invalid constructor \& conversion.
1.72 ///
1.73 /// This constructor initializes the item to be invalid.
1.74 @@ -479,24 +478,24 @@
1.75 ++it2 = it1;
1.76 ++(++it1);
1.77
1.78 - _Item bi = it1;
1.79 + Item bi = it1;
1.80 bi = it2;
1.81 }
1.82 - _Graph& g;
1.83 + GR& g;
1.84 };
1.85 };
1.86
1.87 /// \brief Skeleton class for graph InArcIt and OutArcIt
1.88 ///
1.89 /// \note Because InArcIt and OutArcIt may not inherit from the same
1.90 - /// base class, the _selector is a additional template parameter. For
1.91 - /// InArcIt you should instantiate it with character 'i' and for
1.92 + /// base class, the \c sel is a additional template parameter (selector).
1.93 + /// For InArcIt you should instantiate it with character 'i' and for
1.94 /// OutArcIt with 'o'.
1.95 - template <typename _Graph,
1.96 - typename _Item = typename _Graph::Arc,
1.97 - typename _Base = typename _Graph::Node,
1.98 - char _selector = '0'>
1.99 - class GraphIncIt : public _Item {
1.100 + template <typename GR,
1.101 + typename Item = typename GR::Arc,
1.102 + typename Base = typename GR::Node,
1.103 + char sel = '0'>
1.104 + class GraphIncIt : public Item {
1.105 public:
1.106 /// \brief Default constructor.
1.107 ///
1.108 @@ -507,14 +506,14 @@
1.109 ///
1.110 /// Copy constructor.
1.111 ///
1.112 - GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
1.113 + GraphIncIt(GraphIncIt const& gi) : Item(gi) {}
1.114 /// \brief Sets the iterator to the first arc incoming into or outgoing
1.115 /// from the node.
1.116 ///
1.117 /// Sets the iterator to the first arc incoming into or outgoing
1.118 /// from the node.
1.119 ///
1.120 - explicit GraphIncIt(const _Graph&, const _Base&) {}
1.121 + explicit GraphIncIt(const GR&, const Base&) {}
1.122 /// \brief Invalid constructor \& conversion.
1.123 ///
1.124 /// This constructor initializes the item to be invalid.
1.125 @@ -546,21 +545,21 @@
1.126 template <typename _GraphIncIt>
1.127 struct Constraints {
1.128 void constraints() {
1.129 - checkConcept<GraphItem<_selector>, _GraphIncIt>();
1.130 + checkConcept<GraphItem<sel>, _GraphIncIt>();
1.131 _GraphIncIt it1(graph, node);
1.132 _GraphIncIt it2;
1.133
1.134 it2 = ++it1;
1.135 ++it2 = it1;
1.136 ++(++it1);
1.137 - _Item e = it1;
1.138 + Item e = it1;
1.139 e = it2;
1.140
1.141 }
1.142
1.143 - _Item arc;
1.144 - _Base node;
1.145 - _Graph graph;
1.146 + Item arc;
1.147 + Base node;
1.148 + GR graph;
1.149 _GraphIncIt it;
1.150 };
1.151 };
1.152 @@ -571,12 +570,12 @@
1.153 /// This class provides beside the core digraph features
1.154 /// iterator based iterable interface for the digraph structure.
1.155 /// This concept is part of the Digraph concept.
1.156 - template <typename _Base = BaseDigraphComponent>
1.157 - class IterableDigraphComponent : public _Base {
1.158 + template <typename BAS = BaseDigraphComponent>
1.159 + class IterableDigraphComponent : public BAS {
1.160
1.161 public:
1.162
1.163 - typedef _Base Base;
1.164 + typedef BAS Base;
1.165 typedef typename Base::Node Node;
1.166 typedef typename Base::Arc Arc;
1.167
1.168 @@ -756,11 +755,11 @@
1.169 /// This class provides beside the core graph features iterator
1.170 /// based iterable interface for the undirected graph structure.
1.171 /// This concept is part of the Graph concept.
1.172 - template <typename _Base = BaseGraphComponent>
1.173 - class IterableGraphComponent : public IterableDigraphComponent<_Base> {
1.174 + template <typename BAS = BaseGraphComponent>
1.175 + class IterableGraphComponent : public IterableDigraphComponent<BAS> {
1.176 public:
1.177
1.178 - typedef _Base Base;
1.179 + typedef BAS Base;
1.180 typedef typename Base::Node Node;
1.181 typedef typename Base::Arc Arc;
1.182 typedef typename Base::Edge Edge;
1.183 @@ -773,8 +772,8 @@
1.184 /// This interface provides functions for iteration on graph items
1.185 /// @{
1.186
1.187 - using IterableDigraphComponent<_Base>::first;
1.188 - using IterableDigraphComponent<_Base>::next;
1.189 + using IterableDigraphComponent<Base>::first;
1.190 + using IterableDigraphComponent<Base>::next;
1.191
1.192 /// \brief Gives back the first edge in the iterating
1.193 /// order.
1.194 @@ -808,8 +807,8 @@
1.195 /// use it.
1.196 void nextInc(Edge&, bool&) const {}
1.197
1.198 - using IterableDigraphComponent<_Base>::baseNode;
1.199 - using IterableDigraphComponent<_Base>::runningNode;
1.200 + using IterableDigraphComponent<Base>::baseNode;
1.201 + using IterableDigraphComponent<Base>::runningNode;
1.202
1.203 /// @}
1.204
1.205 @@ -875,7 +874,6 @@
1.206 }
1.207
1.208 const _Graph& graph;
1.209 -
1.210 };
1.211 };
1.212
1.213 @@ -887,11 +885,11 @@
1.214 /// obsevers can be registered into the notifier and whenever an
1.215 /// alteration occured in the digraph all the observers will
1.216 /// notified about it.
1.217 - template <typename _Base = BaseDigraphComponent>
1.218 - class AlterableDigraphComponent : public _Base {
1.219 + template <typename BAS = BaseDigraphComponent>
1.220 + class AlterableDigraphComponent : public BAS {
1.221 public:
1.222
1.223 - typedef _Base Base;
1.224 + typedef BAS Base;
1.225 typedef typename Base::Node Node;
1.226 typedef typename Base::Arc Arc;
1.227
1.228 @@ -945,11 +943,11 @@
1.229 /// obsevers can be registered into the notifier and whenever an
1.230 /// alteration occured in the graph all the observers will
1.231 /// notified about it.
1.232 - template <typename _Base = BaseGraphComponent>
1.233 - class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
1.234 + template <typename BAS = BaseGraphComponent>
1.235 + class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
1.236 public:
1.237
1.238 - typedef _Base Base;
1.239 + typedef BAS Base;
1.240 typedef typename Base::Edge Edge;
1.241
1.242
1.243 @@ -974,9 +972,7 @@
1.244 }
1.245
1.246 const _Graph& graph;
1.247 -
1.248 };
1.249 -
1.250 };
1.251
1.252 /// \brief Class describing the concept of graph maps
1.253 @@ -984,18 +980,18 @@
1.254 /// This class describes the common interface of the graph maps
1.255 /// (NodeMap, ArcMap), that is maps that can be used to
1.256 /// associate data to graph descriptors (nodes or arcs).
1.257 - template <typename _Graph, typename _Item, typename _Value>
1.258 - class GraphMap : public ReadWriteMap<_Item, _Value> {
1.259 + template <typename GR, typename K, typename V>
1.260 + class GraphMap : public ReadWriteMap<K, V> {
1.261 public:
1.262
1.263 - typedef ReadWriteMap<_Item, _Value> Parent;
1.264 + typedef ReadWriteMap<K, V> Parent;
1.265
1.266 /// The graph type of the map.
1.267 - typedef _Graph Graph;
1.268 + typedef GR Graph;
1.269 /// The key type of the map.
1.270 - typedef _Item Key;
1.271 + typedef K Key;
1.272 /// The value type of the map.
1.273 - typedef _Value Value;
1.274 + typedef V Value;
1.275
1.276 /// \brief Construct a new map.
1.277 ///
1.278 @@ -1055,11 +1051,11 @@
1.279 /// This class provides beside the core digraph features
1.280 /// map interface for the digraph structure.
1.281 /// This concept is part of the Digraph concept.
1.282 - template <typename _Base = BaseDigraphComponent>
1.283 - class MappableDigraphComponent : public _Base {
1.284 + template <typename BAS = BaseDigraphComponent>
1.285 + class MappableDigraphComponent : public BAS {
1.286 public:
1.287
1.288 - typedef _Base Base;
1.289 + typedef BAS Base;
1.290 typedef typename Base::Node Node;
1.291 typedef typename Base::Arc Arc;
1.292
1.293 @@ -1069,10 +1065,10 @@
1.294 ///
1.295 /// ReadWrite map of the nodes.
1.296 ///
1.297 - template <typename _Value>
1.298 - class NodeMap : public GraphMap<Digraph, Node, _Value> {
1.299 + template <typename V>
1.300 + class NodeMap : public GraphMap<Digraph, Node, V> {
1.301 public:
1.302 - typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
1.303 + typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
1.304
1.305 /// \brief Construct a new map.
1.306 ///
1.307 @@ -1083,7 +1079,7 @@
1.308 /// \brief Construct a new map with default value.
1.309 ///
1.310 /// Construct a new map for the digraph and initalise the values.
1.311 - NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
1.312 + NodeMap(const MappableDigraphComponent& digraph, const V& value)
1.313 : Parent(digraph, value) {}
1.314
1.315 private:
1.316 @@ -1097,7 +1093,7 @@
1.317 /// Assign operator.
1.318 template <typename CMap>
1.319 NodeMap& operator=(const CMap&) {
1.320 - checkConcept<ReadMap<Node, _Value>, CMap>();
1.321 + checkConcept<ReadMap<Node, V>, CMap>();
1.322 return *this;
1.323 }
1.324
1.325 @@ -1107,10 +1103,10 @@
1.326 ///
1.327 /// ReadWrite map of the arcs.
1.328 ///
1.329 - template <typename _Value>
1.330 - class ArcMap : public GraphMap<Digraph, Arc, _Value> {
1.331 + template <typename V>
1.332 + class ArcMap : public GraphMap<Digraph, Arc, V> {
1.333 public:
1.334 - typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
1.335 + typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
1.336
1.337 /// \brief Construct a new map.
1.338 ///
1.339 @@ -1121,7 +1117,7 @@
1.340 /// \brief Construct a new map with default value.
1.341 ///
1.342 /// Construct a new map for the digraph and initalise the values.
1.343 - ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
1.344 + ArcMap(const MappableDigraphComponent& digraph, const V& value)
1.345 : Parent(digraph, value) {}
1.346
1.347 private:
1.348 @@ -1135,7 +1131,7 @@
1.349 /// Assign operator.
1.350 template <typename CMap>
1.351 ArcMap& operator=(const CMap&) {
1.352 - checkConcept<ReadMap<Arc, _Value>, CMap>();
1.353 + checkConcept<ReadMap<Arc, V>, CMap>();
1.354 return *this;
1.355 }
1.356
1.357 @@ -1191,11 +1187,11 @@
1.358 /// This class provides beside the core graph features
1.359 /// map interface for the graph structure.
1.360 /// This concept is part of the Graph concept.
1.361 - template <typename _Base = BaseGraphComponent>
1.362 - class MappableGraphComponent : public MappableDigraphComponent<_Base> {
1.363 + template <typename BAS = BaseGraphComponent>
1.364 + class MappableGraphComponent : public MappableDigraphComponent<BAS> {
1.365 public:
1.366
1.367 - typedef _Base Base;
1.368 + typedef BAS Base;
1.369 typedef typename Base::Edge Edge;
1.370
1.371 typedef MappableGraphComponent Graph;
1.372 @@ -1204,10 +1200,10 @@
1.373 ///
1.374 /// ReadWrite map of the edges.
1.375 ///
1.376 - template <typename _Value>
1.377 - class EdgeMap : public GraphMap<Graph, Edge, _Value> {
1.378 + template <typename V>
1.379 + class EdgeMap : public GraphMap<Graph, Edge, V> {
1.380 public:
1.381 - typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
1.382 + typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
1.383
1.384 /// \brief Construct a new map.
1.385 ///
1.386 @@ -1218,7 +1214,7 @@
1.387 /// \brief Construct a new map with default value.
1.388 ///
1.389 /// Construct a new map for the graph and initalise the values.
1.390 - EdgeMap(const MappableGraphComponent& graph, const _Value& value)
1.391 + EdgeMap(const MappableGraphComponent& graph, const V& value)
1.392 : Parent(graph, value) {}
1.393
1.394 private:
1.395 @@ -1232,7 +1228,7 @@
1.396 /// Assign operator.
1.397 template <typename CMap>
1.398 EdgeMap& operator=(const CMap&) {
1.399 - checkConcept<ReadMap<Edge, _Value>, CMap>();
1.400 + checkConcept<ReadMap<Edge, V>, CMap>();
1.401 return *this;
1.402 }
1.403
1.404 @@ -1276,13 +1272,13 @@
1.405 /// extendable interface for the digraph structure. The main
1.406 /// difference between the base and this interface is that the
1.407 /// digraph alterations should handled already on this level.
1.408 - template <typename _Base = BaseDigraphComponent>
1.409 - class ExtendableDigraphComponent : public _Base {
1.410 + template <typename BAS = BaseDigraphComponent>
1.411 + class ExtendableDigraphComponent : public BAS {
1.412 public:
1.413 - typedef _Base Base;
1.414 + typedef BAS Base;
1.415
1.416 - typedef typename _Base::Node Node;
1.417 - typedef typename _Base::Arc Arc;
1.418 + typedef typename Base::Node Node;
1.419 + typedef typename Base::Arc Arc;
1.420
1.421 /// \brief Adds a new node to the digraph.
1.422 ///
1.423 @@ -1321,13 +1317,13 @@
1.424 /// The main difference between the base and this interface is
1.425 /// that the graph alterations should handled already on this
1.426 /// level.
1.427 - template <typename _Base = BaseGraphComponent>
1.428 - class ExtendableGraphComponent : public _Base {
1.429 + template <typename BAS = BaseGraphComponent>
1.430 + class ExtendableGraphComponent : public BAS {
1.431 public:
1.432
1.433 - typedef _Base Base;
1.434 - typedef typename _Base::Node Node;
1.435 - typedef typename _Base::Edge Edge;
1.436 + typedef BAS Base;
1.437 + typedef typename Base::Node Node;
1.438 + typedef typename Base::Edge Edge;
1.439
1.440 /// \brief Adds a new node to the graph.
1.441 ///
1.442 @@ -1365,11 +1361,11 @@
1.443 /// functions for the digraph structure. The main difference between
1.444 /// the base and this interface is that the digraph alterations
1.445 /// should handled already on this level.
1.446 - template <typename _Base = BaseDigraphComponent>
1.447 - class ErasableDigraphComponent : public _Base {
1.448 + template <typename BAS = BaseDigraphComponent>
1.449 + class ErasableDigraphComponent : public BAS {
1.450 public:
1.451
1.452 - typedef _Base Base;
1.453 + typedef BAS Base;
1.454 typedef typename Base::Node Node;
1.455 typedef typename Base::Arc Arc;
1.456
1.457 @@ -1405,11 +1401,11 @@
1.458 /// core erase functions for the undirceted graph structure. The
1.459 /// main difference between the base and this interface is that
1.460 /// the graph alterations should handled already on this level.
1.461 - template <typename _Base = BaseGraphComponent>
1.462 - class ErasableGraphComponent : public _Base {
1.463 + template <typename BAS = BaseGraphComponent>
1.464 + class ErasableGraphComponent : public BAS {
1.465 public:
1.466
1.467 - typedef _Base Base;
1.468 + typedef BAS Base;
1.469 typedef typename Base::Node Node;
1.470 typedef typename Base::Edge Edge;
1.471
1.472 @@ -1445,11 +1441,11 @@
1.473 /// functions for the digraph structure. The main difference between
1.474 /// the base and this interface is that the digraph alterations
1.475 /// should handled already on this level.
1.476 - template <typename _Base = BaseDigraphComponent>
1.477 - class ClearableDigraphComponent : public _Base {
1.478 + template <typename BAS = BaseDigraphComponent>
1.479 + class ClearableDigraphComponent : public BAS {
1.480 public:
1.481
1.482 - typedef _Base Base;
1.483 + typedef BAS Base;
1.484
1.485 /// \brief Erase all nodes and arcs from the digraph.
1.486 ///
1.487 @@ -1474,11 +1470,11 @@
1.488 /// core clear functions for the undirected graph structure. The
1.489 /// main difference between the base and this interface is that
1.490 /// the graph alterations should handled already on this level.
1.491 - template <typename _Base = BaseGraphComponent>
1.492 - class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {
1.493 + template <typename BAS = BaseGraphComponent>
1.494 + class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
1.495 public:
1.496
1.497 - typedef _Base Base;
1.498 + typedef BAS Base;
1.499
1.500 template <typename _Graph>
1.501 struct Constraints {