1.1 --- a/lemon/bits/graph_adaptor_extender.h Sun Nov 30 19:00:30 2008 +0100
1.2 +++ b/lemon/bits/graph_adaptor_extender.h Sun Nov 30 19:18:32 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -24,15 +24,8 @@
1.13
1.14 #include <lemon/bits/default_map.h>
1.15
1.16 -
1.17 -///\ingroup digraphbits
1.18 -///\file
1.19 -///\brief Extenders for the digraph adaptor types
1.20 namespace lemon {
1.21
1.22 - /// \ingroup digraphbits
1.23 - ///
1.24 - /// \brief Extender for the DigraphAdaptors
1.25 template <typename _Digraph>
1.26 class DigraphAdaptorExtender : public _Digraph {
1.27 public:
1.28 @@ -64,14 +57,14 @@
1.29
1.30 Node oppositeNode(const Node &n, const Arc &e) const {
1.31 if (n == Parent::source(e))
1.32 - return Parent::target(e);
1.33 + return Parent::target(e);
1.34 else if(n==Parent::target(e))
1.35 - return Parent::source(e);
1.36 + return Parent::source(e);
1.37 else
1.38 - return INVALID;
1.39 + return INVALID;
1.40 }
1.41
1.42 - class NodeIt : public Node {
1.43 + class NodeIt : public Node {
1.44 const Adaptor* _adaptor;
1.45 public:
1.46
1.47 @@ -80,21 +73,21 @@
1.48 NodeIt(Invalid i) : Node(i) { }
1.49
1.50 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.51 - _adaptor->first(static_cast<Node&>(*this));
1.52 + _adaptor->first(static_cast<Node&>(*this));
1.53 }
1.54
1.55 - NodeIt(const Adaptor& adaptor, const Node& node)
1.56 - : Node(node), _adaptor(&adaptor) {}
1.57 + NodeIt(const Adaptor& adaptor, const Node& node)
1.58 + : Node(node), _adaptor(&adaptor) {}
1.59
1.60 - NodeIt& operator++() {
1.61 - _adaptor->next(*this);
1.62 - return *this;
1.63 + NodeIt& operator++() {
1.64 + _adaptor->next(*this);
1.65 + return *this;
1.66 }
1.67
1.68 };
1.69
1.70
1.71 - class ArcIt : public Arc {
1.72 + class ArcIt : public Arc {
1.73 const Adaptor* _adaptor;
1.74 public:
1.75
1.76 @@ -103,21 +96,21 @@
1.77 ArcIt(Invalid i) : Arc(i) { }
1.78
1.79 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.80 - _adaptor->first(static_cast<Arc&>(*this));
1.81 + _adaptor->first(static_cast<Arc&>(*this));
1.82 }
1.83
1.84 - ArcIt(const Adaptor& adaptor, const Arc& e) :
1.85 - Arc(e), _adaptor(&adaptor) { }
1.86 + ArcIt(const Adaptor& adaptor, const Arc& e) :
1.87 + Arc(e), _adaptor(&adaptor) { }
1.88
1.89 - ArcIt& operator++() {
1.90 - _adaptor->next(*this);
1.91 - return *this;
1.92 + ArcIt& operator++() {
1.93 + _adaptor->next(*this);
1.94 + return *this;
1.95 }
1.96
1.97 };
1.98
1.99
1.100 - class OutArcIt : public Arc {
1.101 + class OutArcIt : public Arc {
1.102 const Adaptor* _adaptor;
1.103 public:
1.104
1.105 @@ -125,23 +118,23 @@
1.106
1.107 OutArcIt(Invalid i) : Arc(i) { }
1.108
1.109 - OutArcIt(const Adaptor& adaptor, const Node& node)
1.110 - : _adaptor(&adaptor) {
1.111 - _adaptor->firstOut(*this, node);
1.112 + OutArcIt(const Adaptor& adaptor, const Node& node)
1.113 + : _adaptor(&adaptor) {
1.114 + _adaptor->firstOut(*this, node);
1.115 }
1.116
1.117 - OutArcIt(const Adaptor& adaptor, const Arc& arc)
1.118 - : Arc(arc), _adaptor(&adaptor) {}
1.119 + OutArcIt(const Adaptor& adaptor, const Arc& arc)
1.120 + : Arc(arc), _adaptor(&adaptor) {}
1.121
1.122 - OutArcIt& operator++() {
1.123 - _adaptor->nextOut(*this);
1.124 - return *this;
1.125 + OutArcIt& operator++() {
1.126 + _adaptor->nextOut(*this);
1.127 + return *this;
1.128 }
1.129
1.130 };
1.131
1.132
1.133 - class InArcIt : public Arc {
1.134 + class InArcIt : public Arc {
1.135 const Adaptor* _adaptor;
1.136 public:
1.137
1.138 @@ -149,45 +142,31 @@
1.139
1.140 InArcIt(Invalid i) : Arc(i) { }
1.141
1.142 - InArcIt(const Adaptor& adaptor, const Node& node)
1.143 - : _adaptor(&adaptor) {
1.144 - _adaptor->firstIn(*this, node);
1.145 + InArcIt(const Adaptor& adaptor, const Node& node)
1.146 + : _adaptor(&adaptor) {
1.147 + _adaptor->firstIn(*this, node);
1.148 }
1.149
1.150 - InArcIt(const Adaptor& adaptor, const Arc& arc) :
1.151 - Arc(arc), _adaptor(&adaptor) {}
1.152 + InArcIt(const Adaptor& adaptor, const Arc& arc) :
1.153 + Arc(arc), _adaptor(&adaptor) {}
1.154
1.155 - InArcIt& operator++() {
1.156 - _adaptor->nextIn(*this);
1.157 - return *this;
1.158 + InArcIt& operator++() {
1.159 + _adaptor->nextIn(*this);
1.160 + return *this;
1.161 }
1.162
1.163 };
1.164
1.165 - /// \brief Base node of the iterator
1.166 - ///
1.167 - /// Returns the base node (ie. the source in this case) of the iterator
1.168 Node baseNode(const OutArcIt &e) const {
1.169 return Parent::source(e);
1.170 }
1.171 - /// \brief Running node of the iterator
1.172 - ///
1.173 - /// Returns the running node (ie. the target in this case) of the
1.174 - /// iterator
1.175 Node runningNode(const OutArcIt &e) const {
1.176 return Parent::target(e);
1.177 }
1.178
1.179 - /// \brief Base node of the iterator
1.180 - ///
1.181 - /// Returns the base node (ie. the target in this case) of the iterator
1.182 Node baseNode(const InArcIt &e) const {
1.183 return Parent::target(e);
1.184 }
1.185 - /// \brief Running node of the iterator
1.186 - ///
1.187 - /// Returns the running node (ie. the source in this case) of the
1.188 - /// iterator
1.189 Node runningNode(const InArcIt &e) const {
1.190 return Parent::source(e);
1.191 }
1.192 @@ -198,10 +177,10 @@
1.193 /// \ingroup digraphbits
1.194 ///
1.195 /// \brief Extender for the GraphAdaptors
1.196 - template <typename _Graph>
1.197 + template <typename _Graph>
1.198 class GraphAdaptorExtender : public _Graph {
1.199 public:
1.200 -
1.201 +
1.202 typedef _Graph Parent;
1.203 typedef _Graph Graph;
1.204 typedef GraphAdaptorExtender Adaptor;
1.205 @@ -210,7 +189,7 @@
1.206 typedef typename Parent::Arc Arc;
1.207 typedef typename Parent::Edge Edge;
1.208
1.209 - // Graph extension
1.210 + // Graph extension
1.211
1.212 int maxId(Node) const {
1.213 return Parent::maxNodeId();
1.214 @@ -238,11 +217,11 @@
1.215
1.216 Node oppositeNode(const Node &n, const Edge &e) const {
1.217 if( n == Parent::u(e))
1.218 - return Parent::v(e);
1.219 + return Parent::v(e);
1.220 else if( n == Parent::v(e))
1.221 - return Parent::u(e);
1.222 + return Parent::u(e);
1.223 else
1.224 - return INVALID;
1.225 + return INVALID;
1.226 }
1.227
1.228 Arc oppositeArc(const Arc &a) const {
1.229 @@ -255,7 +234,7 @@
1.230 }
1.231
1.232
1.233 - class NodeIt : public Node {
1.234 + class NodeIt : public Node {
1.235 const Adaptor* _adaptor;
1.236 public:
1.237
1.238 @@ -264,21 +243,21 @@
1.239 NodeIt(Invalid i) : Node(i) { }
1.240
1.241 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.242 - _adaptor->first(static_cast<Node&>(*this));
1.243 + _adaptor->first(static_cast<Node&>(*this));
1.244 }
1.245
1.246 - NodeIt(const Adaptor& adaptor, const Node& node)
1.247 - : Node(node), _adaptor(&adaptor) {}
1.248 + NodeIt(const Adaptor& adaptor, const Node& node)
1.249 + : Node(node), _adaptor(&adaptor) {}
1.250
1.251 - NodeIt& operator++() {
1.252 - _adaptor->next(*this);
1.253 - return *this;
1.254 + NodeIt& operator++() {
1.255 + _adaptor->next(*this);
1.256 + return *this;
1.257 }
1.258
1.259 };
1.260
1.261
1.262 - class ArcIt : public Arc {
1.263 + class ArcIt : public Arc {
1.264 const Adaptor* _adaptor;
1.265 public:
1.266
1.267 @@ -287,21 +266,21 @@
1.268 ArcIt(Invalid i) : Arc(i) { }
1.269
1.270 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.271 - _adaptor->first(static_cast<Arc&>(*this));
1.272 + _adaptor->first(static_cast<Arc&>(*this));
1.273 }
1.274
1.275 - ArcIt(const Adaptor& adaptor, const Arc& e) :
1.276 - Arc(e), _adaptor(&adaptor) { }
1.277 + ArcIt(const Adaptor& adaptor, const Arc& e) :
1.278 + Arc(e), _adaptor(&adaptor) { }
1.279
1.280 - ArcIt& operator++() {
1.281 - _adaptor->next(*this);
1.282 - return *this;
1.283 + ArcIt& operator++() {
1.284 + _adaptor->next(*this);
1.285 + return *this;
1.286 }
1.287
1.288 };
1.289
1.290
1.291 - class OutArcIt : public Arc {
1.292 + class OutArcIt : public Arc {
1.293 const Adaptor* _adaptor;
1.294 public:
1.295
1.296 @@ -309,23 +288,23 @@
1.297
1.298 OutArcIt(Invalid i) : Arc(i) { }
1.299
1.300 - OutArcIt(const Adaptor& adaptor, const Node& node)
1.301 - : _adaptor(&adaptor) {
1.302 - _adaptor->firstOut(*this, node);
1.303 + OutArcIt(const Adaptor& adaptor, const Node& node)
1.304 + : _adaptor(&adaptor) {
1.305 + _adaptor->firstOut(*this, node);
1.306 }
1.307
1.308 - OutArcIt(const Adaptor& adaptor, const Arc& arc)
1.309 - : Arc(arc), _adaptor(&adaptor) {}
1.310 + OutArcIt(const Adaptor& adaptor, const Arc& arc)
1.311 + : Arc(arc), _adaptor(&adaptor) {}
1.312
1.313 - OutArcIt& operator++() {
1.314 - _adaptor->nextOut(*this);
1.315 - return *this;
1.316 + OutArcIt& operator++() {
1.317 + _adaptor->nextOut(*this);
1.318 + return *this;
1.319 }
1.320
1.321 };
1.322
1.323
1.324 - class InArcIt : public Arc {
1.325 + class InArcIt : public Arc {
1.326 const Adaptor* _adaptor;
1.327 public:
1.328
1.329 @@ -333,22 +312,22 @@
1.330
1.331 InArcIt(Invalid i) : Arc(i) { }
1.332
1.333 - InArcIt(const Adaptor& adaptor, const Node& node)
1.334 - : _adaptor(&adaptor) {
1.335 - _adaptor->firstIn(*this, node);
1.336 + InArcIt(const Adaptor& adaptor, const Node& node)
1.337 + : _adaptor(&adaptor) {
1.338 + _adaptor->firstIn(*this, node);
1.339 }
1.340
1.341 - InArcIt(const Adaptor& adaptor, const Arc& arc) :
1.342 - Arc(arc), _adaptor(&adaptor) {}
1.343 + InArcIt(const Adaptor& adaptor, const Arc& arc) :
1.344 + Arc(arc), _adaptor(&adaptor) {}
1.345
1.346 - InArcIt& operator++() {
1.347 - _adaptor->nextIn(*this);
1.348 - return *this;
1.349 + InArcIt& operator++() {
1.350 + _adaptor->nextIn(*this);
1.351 + return *this;
1.352 }
1.353
1.354 };
1.355
1.356 - class EdgeIt : public Parent::Edge {
1.357 + class EdgeIt : public Parent::Edge {
1.358 const Adaptor* _adaptor;
1.359 public:
1.360
1.361 @@ -357,20 +336,20 @@
1.362 EdgeIt(Invalid i) : Edge(i) { }
1.363
1.364 explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.365 - _adaptor->first(static_cast<Edge&>(*this));
1.366 + _adaptor->first(static_cast<Edge&>(*this));
1.367 }
1.368
1.369 - EdgeIt(const Adaptor& adaptor, const Edge& e) :
1.370 - Edge(e), _adaptor(&adaptor) { }
1.371 + EdgeIt(const Adaptor& adaptor, const Edge& e) :
1.372 + Edge(e), _adaptor(&adaptor) { }
1.373
1.374 - EdgeIt& operator++() {
1.375 - _adaptor->next(*this);
1.376 - return *this;
1.377 + EdgeIt& operator++() {
1.378 + _adaptor->next(*this);
1.379 + return *this;
1.380 }
1.381
1.382 };
1.383
1.384 - class IncEdgeIt : public Edge {
1.385 + class IncEdgeIt : public Edge {
1.386 friend class GraphAdaptorExtender;
1.387 const Adaptor* _adaptor;
1.388 bool direction;
1.389 @@ -381,57 +360,37 @@
1.390 IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
1.391
1.392 IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
1.393 - _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
1.394 + _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
1.395 }
1.396
1.397 IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
1.398 - : _adaptor(&adaptor), Edge(e) {
1.399 - direction = (_adaptor->u(e) == n);
1.400 + : _adaptor(&adaptor), Edge(e) {
1.401 + direction = (_adaptor->u(e) == n);
1.402 }
1.403
1.404 IncEdgeIt& operator++() {
1.405 - _adaptor->nextInc(*this, direction);
1.406 - return *this;
1.407 + _adaptor->nextInc(*this, direction);
1.408 + return *this;
1.409 }
1.410 };
1.411
1.412 - /// \brief Base node of the iterator
1.413 - ///
1.414 - /// Returns the base node (ie. the source in this case) of the iterator
1.415 Node baseNode(const OutArcIt &a) const {
1.416 return Parent::source(a);
1.417 }
1.418 - /// \brief Running node of the iterator
1.419 - ///
1.420 - /// Returns the running node (ie. the target in this case) of the
1.421 - /// iterator
1.422 Node runningNode(const OutArcIt &a) const {
1.423 return Parent::target(a);
1.424 }
1.425
1.426 - /// \brief Base node of the iterator
1.427 - ///
1.428 - /// Returns the base node (ie. the target in this case) of the iterator
1.429 Node baseNode(const InArcIt &a) const {
1.430 return Parent::target(a);
1.431 }
1.432 - /// \brief Running node of the iterator
1.433 - ///
1.434 - /// Returns the running node (ie. the source in this case) of the
1.435 - /// iterator
1.436 Node runningNode(const InArcIt &a) const {
1.437 return Parent::source(a);
1.438 }
1.439
1.440 - /// Base node of the iterator
1.441 - ///
1.442 - /// Returns the base node of the iterator
1.443 Node baseNode(const IncEdgeIt &e) const {
1.444 return e.direction ? Parent::u(e) : Parent::v(e);
1.445 }
1.446 - /// Running node of the iterator
1.447 - ///
1.448 - /// Returns the running node of the iterator
1.449 Node runningNode(const IncEdgeIt &e) const {
1.450 return e.direction ? Parent::v(e) : Parent::u(e);
1.451 }