1.1 --- a/lemon/bits/iterable_graph_extender.h Wed Feb 22 12:45:59 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,533 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2006
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
1.23 -#define LEMON_ITERABLE_GRAPH_EXTENDER_H
1.24 -
1.25 -#include <lemon/invalid.h>
1.26 -#include <lemon/utility.h>
1.27 -
1.28 -namespace lemon {
1.29 -
1.30 - template <typename _Base>
1.31 - class IterableGraphExtender : public _Base {
1.32 - public:
1.33 -
1.34 - /// Indicates that the graph is undirected.
1.35 -
1.36 - ///\todo Better name?
1.37 - ///
1.38 - ///\bug Should it be here?
1.39 - typedef False UTag;
1.40 -
1.41 - typedef _Base Parent;
1.42 - typedef IterableGraphExtender<_Base> Graph;
1.43 -
1.44 - typedef typename Parent::Node Node;
1.45 - typedef typename Parent::Edge Edge;
1.46 -
1.47 -
1.48 - class NodeIt : public Node {
1.49 - const Graph* graph;
1.50 - public:
1.51 -
1.52 - NodeIt() {}
1.53 -
1.54 - NodeIt(Invalid i) : Node(i) { }
1.55 -
1.56 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
1.57 - _graph.first(*static_cast<Node*>(this));
1.58 - }
1.59 -
1.60 - NodeIt(const Graph& _graph, const Node& node)
1.61 - : Node(node), graph(&_graph) {}
1.62 -
1.63 - NodeIt& operator++() {
1.64 - graph->next(*this);
1.65 - return *this;
1.66 - }
1.67 -
1.68 - };
1.69 -
1.70 -
1.71 - class EdgeIt : public Edge {
1.72 - const Graph* graph;
1.73 - public:
1.74 -
1.75 - EdgeIt() { }
1.76 -
1.77 - EdgeIt(Invalid i) : Edge(i) { }
1.78 -
1.79 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
1.80 - _graph.first(*static_cast<Edge*>(this));
1.81 - }
1.82 -
1.83 - EdgeIt(const Graph& _graph, const Edge& e) :
1.84 - Edge(e), graph(&_graph) { }
1.85 -
1.86 - EdgeIt& operator++() {
1.87 - graph->next(*this);
1.88 - return *this;
1.89 - }
1.90 -
1.91 - };
1.92 -
1.93 -
1.94 - class OutEdgeIt : public Edge {
1.95 - const Graph* graph;
1.96 - public:
1.97 -
1.98 - OutEdgeIt() { }
1.99 -
1.100 - OutEdgeIt(Invalid i) : Edge(i) { }
1.101 -
1.102 - OutEdgeIt(const Graph& _graph, const Node& node)
1.103 - : graph(&_graph) {
1.104 - _graph.firstOut(*this, node);
1.105 - }
1.106 -
1.107 - OutEdgeIt(const Graph& _graph, const Edge& edge)
1.108 - : Edge(edge), graph(&_graph) {}
1.109 -
1.110 - OutEdgeIt& operator++() {
1.111 - graph->nextOut(*this);
1.112 - return *this;
1.113 - }
1.114 -
1.115 - };
1.116 -
1.117 -
1.118 - class InEdgeIt : public Edge {
1.119 - const Graph* graph;
1.120 - public:
1.121 -
1.122 - InEdgeIt() { }
1.123 -
1.124 - InEdgeIt(Invalid i) : Edge(i) { }
1.125 -
1.126 - InEdgeIt(const Graph& _graph, const Node& node)
1.127 - : graph(&_graph) {
1.128 - _graph.firstIn(*this, node);
1.129 - }
1.130 -
1.131 - InEdgeIt(const Graph& _graph, const Edge& edge) :
1.132 - Edge(edge), graph(&_graph) {}
1.133 -
1.134 - InEdgeIt& operator++() {
1.135 - graph->nextIn(*this);
1.136 - return *this;
1.137 - }
1.138 -
1.139 - };
1.140 -
1.141 - /// \brief Base node of the iterator
1.142 - ///
1.143 - /// Returns the base node (ie. the source in this case) of the iterator
1.144 - Node baseNode(const OutEdgeIt &e) const {
1.145 - return Parent::source((Edge)e);
1.146 - }
1.147 - /// \brief Running node of the iterator
1.148 - ///
1.149 - /// Returns the running node (ie. the target in this case) of the
1.150 - /// iterator
1.151 - Node runningNode(const OutEdgeIt &e) const {
1.152 - return Parent::target((Edge)e);
1.153 - }
1.154 -
1.155 - /// \brief Base node of the iterator
1.156 - ///
1.157 - /// Returns the base node (ie. the target in this case) of the iterator
1.158 - Node baseNode(const InEdgeIt &e) const {
1.159 - return Parent::target((Edge)e);
1.160 - }
1.161 - /// \brief Running node of the iterator
1.162 - ///
1.163 - /// Returns the running node (ie. the source in this case) of the
1.164 - /// iterator
1.165 - Node runningNode(const InEdgeIt &e) const {
1.166 - return Parent::source((Edge)e);
1.167 - }
1.168 -
1.169 - using Parent::first;
1.170 -
1.171 - /// \brief The opposite node on the given edge.
1.172 - ///
1.173 - /// Gives back the opposite on the given edge.
1.174 - Node oppositeNode(const Node& n, const Edge& e) const {
1.175 - if (Parent::source(e) == n) {
1.176 - return Parent::target(e);
1.177 - } else {
1.178 - return Parent::source(e);
1.179 - }
1.180 - }
1.181 -
1.182 - private:
1.183 -
1.184 - // void first(NodeIt &) const;
1.185 - // void first(EdgeIt &) const;
1.186 - // void first(OutEdgeIt &) const;
1.187 - // void first(InEdgeIt &) const;
1.188 -
1.189 - };
1.190 -
1.191 -
1.192 -
1.193 -
1.194 -
1.195 -
1.196 - template <typename _Base>
1.197 - class IterableUGraphExtender : public IterableGraphExtender<_Base> {
1.198 - public:
1.199 -
1.200 - /// Indicates that the graph is undirected.
1.201 -
1.202 - ///\todo Better name?
1.203 - ///
1.204 - ///\bug Should it be here?
1.205 - ///\bug Should be tested in the concept checker whether it is defined
1.206 - ///correctly.
1.207 - typedef True UTag;
1.208 -
1.209 - typedef IterableGraphExtender<_Base> Parent;
1.210 - typedef IterableUGraphExtender<_Base> Graph;
1.211 - typedef typename Parent::Node Node;
1.212 - typedef typename Parent::Edge Edge;
1.213 - typedef typename Parent::UEdge UEdge;
1.214 -
1.215 - class UEdgeIt : public Parent::UEdge {
1.216 - const Graph* graph;
1.217 - public:
1.218 -
1.219 - UEdgeIt() { }
1.220 -
1.221 - UEdgeIt(Invalid i) : UEdge(i) { }
1.222 -
1.223 - explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
1.224 - _graph.first(*static_cast<UEdge*>(this));
1.225 - }
1.226 -
1.227 - UEdgeIt(const Graph& _graph, const UEdge& e) :
1.228 - UEdge(e), graph(&_graph) { }
1.229 -
1.230 - UEdgeIt& operator++() {
1.231 - graph->next(*this);
1.232 - return *this;
1.233 - }
1.234 -
1.235 - };
1.236 -
1.237 - class IncEdgeIt : public Parent::UEdge {
1.238 - const Graph* graph;
1.239 - bool direction;
1.240 - friend class IterableUGraphExtender;
1.241 - public:
1.242 -
1.243 - IncEdgeIt() { }
1.244 -
1.245 - IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
1.246 -
1.247 - IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1.248 - _graph.firstInc(*this, direction, n);
1.249 - }
1.250 -
1.251 - IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1.252 - : graph(&_graph), UEdge(ue) {
1.253 - direction = (_graph.source(ue) == n);
1.254 - }
1.255 -
1.256 - IncEdgeIt& operator++() {
1.257 - graph->nextInc(*this, direction);
1.258 - return *this;
1.259 - }
1.260 - };
1.261 -
1.262 - using Parent::baseNode;
1.263 - using Parent::runningNode;
1.264 -
1.265 - /// Base node of the iterator
1.266 - ///
1.267 - /// Returns the base node of the iterator
1.268 - Node baseNode(const IncEdgeIt &e) const {
1.269 - return e.direction ? source(e) : target(e);
1.270 - }
1.271 - /// Running node of the iterator
1.272 - ///
1.273 - /// Returns the running node of the iterator
1.274 - Node runningNode(const IncEdgeIt &e) const {
1.275 - return e.direction ? target(e) : source(e);
1.276 - }
1.277 -
1.278 - /// \brief The opposite node on the given undirected edge.
1.279 - ///
1.280 - /// Gives back the opposite on the given undirected edge.
1.281 - Node oppositeNode(const Node& n, const UEdge& e) const {
1.282 - if (Parent::source(e) == n) {
1.283 - return Parent::target(e);
1.284 - } else {
1.285 - return Parent::source(e);
1.286 - }
1.287 - }
1.288 -
1.289 - };
1.290 -
1.291 -
1.292 - template <typename _Base>
1.293 - class IterableBpUGraphExtender : public _Base {
1.294 - public:
1.295 - typedef _Base Parent;
1.296 - typedef IterableBpUGraphExtender Graph;
1.297 -
1.298 - typedef typename Parent::Node Node;
1.299 - typedef typename Parent::ANode ANode;
1.300 - typedef typename Parent::BNode BNode;
1.301 - typedef typename Parent::Edge Edge;
1.302 - typedef typename Parent::UEdge UEdge;
1.303 -
1.304 - class NodeIt : public Node {
1.305 - const Graph* graph;
1.306 - public:
1.307 -
1.308 - NodeIt() { }
1.309 -
1.310 - NodeIt(Invalid i) : Node(INVALID) { }
1.311 -
1.312 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
1.313 - graph->first(static_cast<Node&>(*this));
1.314 - }
1.315 -
1.316 - NodeIt(const Graph& _graph, const Node& node)
1.317 - : Node(node), graph(&_graph) { }
1.318 -
1.319 - NodeIt& operator++() {
1.320 - graph->next(*this);
1.321 - return *this;
1.322 - }
1.323 -
1.324 - };
1.325 -
1.326 - class ANodeIt : public Node {
1.327 - friend class IterableBpUGraphExtender;
1.328 - const Graph* graph;
1.329 - public:
1.330 -
1.331 - ANodeIt() { }
1.332 -
1.333 - ANodeIt(Invalid i) : Node(INVALID) { }
1.334 -
1.335 - explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
1.336 - graph->firstANode(static_cast<Node&>(*this));
1.337 - }
1.338 -
1.339 - ANodeIt(const Graph& _graph, const Node& node)
1.340 - : Node(node), graph(&_graph) {}
1.341 -
1.342 - ANodeIt& operator++() {
1.343 - graph->nextANode(*this);
1.344 - return *this;
1.345 - }
1.346 - };
1.347 -
1.348 - class BNodeIt : public Node {
1.349 - friend class IterableBpUGraphExtender;
1.350 - const Graph* graph;
1.351 - public:
1.352 -
1.353 - BNodeIt() { }
1.354 -
1.355 - BNodeIt(Invalid i) : Node(INVALID) { }
1.356 -
1.357 - explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
1.358 - graph->firstBNode(static_cast<Node&>(*this));
1.359 - }
1.360 -
1.361 - BNodeIt(const Graph& _graph, const Node& node)
1.362 - : Node(node), graph(&_graph) {}
1.363 -
1.364 - BNodeIt& operator++() {
1.365 - graph->nextBNode(*this);
1.366 - return *this;
1.367 - }
1.368 - };
1.369 -
1.370 - class EdgeIt : public Edge {
1.371 - friend class IterableBpUGraphExtender;
1.372 - const Graph* graph;
1.373 - public:
1.374 -
1.375 - EdgeIt() { }
1.376 -
1.377 - EdgeIt(Invalid i) : Edge(INVALID) { }
1.378 -
1.379 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
1.380 - graph->first(static_cast<Edge&>(*this));
1.381 - }
1.382 -
1.383 - EdgeIt(const Graph& _graph, const Edge& edge)
1.384 - : Edge(edge), graph(&_graph) { }
1.385 -
1.386 - EdgeIt& operator++() {
1.387 - graph->next(*this);
1.388 - return *this;
1.389 - }
1.390 -
1.391 - };
1.392 -
1.393 - class UEdgeIt : public UEdge {
1.394 - friend class IterableBpUGraphExtender;
1.395 - const Graph* graph;
1.396 - public:
1.397 -
1.398 - UEdgeIt() { }
1.399 -
1.400 - UEdgeIt(Invalid i) : UEdge(INVALID) { }
1.401 -
1.402 - explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
1.403 - graph->first(static_cast<UEdge&>(*this));
1.404 - }
1.405 -
1.406 - UEdgeIt(const Graph& _graph, const UEdge& edge)
1.407 - : UEdge(edge), graph(&_graph) { }
1.408 -
1.409 - UEdgeIt& operator++() {
1.410 - graph->next(*this);
1.411 - return *this;
1.412 - }
1.413 - };
1.414 -
1.415 - class OutEdgeIt : public Edge {
1.416 - friend class IterableBpUGraphExtender;
1.417 - const Graph* graph;
1.418 - public:
1.419 -
1.420 - OutEdgeIt() { }
1.421 -
1.422 - OutEdgeIt(Invalid i) : Edge(i) { }
1.423 -
1.424 - OutEdgeIt(const Graph& _graph, const Node& node)
1.425 - : graph(&_graph) {
1.426 - graph->firstOut(*this, node);
1.427 - }
1.428 -
1.429 - OutEdgeIt(const Graph& _graph, const Edge& edge)
1.430 - : Edge(edge), graph(&_graph) {}
1.431 -
1.432 - OutEdgeIt& operator++() {
1.433 - graph->nextOut(*this);
1.434 - return *this;
1.435 - }
1.436 -
1.437 - };
1.438 -
1.439 -
1.440 - class InEdgeIt : public Edge {
1.441 - friend class IterableBpUGraphExtender;
1.442 - const Graph* graph;
1.443 - public:
1.444 -
1.445 - InEdgeIt() { }
1.446 -
1.447 - InEdgeIt(Invalid i) : Edge(i) { }
1.448 -
1.449 - InEdgeIt(const Graph& _graph, const Node& node)
1.450 - : graph(&_graph) {
1.451 - graph->firstIn(*this, node);
1.452 - }
1.453 -
1.454 - InEdgeIt(const Graph& _graph, const Edge& edge) :
1.455 - Edge(edge), graph(&_graph) {}
1.456 -
1.457 - InEdgeIt& operator++() {
1.458 - graph->nextIn(*this);
1.459 - return *this;
1.460 - }
1.461 -
1.462 - };
1.463 -
1.464 - /// \brief Base node of the iterator
1.465 - ///
1.466 - /// Returns the base node (ie. the source in this case) of the iterator
1.467 - Node baseNode(const OutEdgeIt &e) const {
1.468 - return Parent::source((Edge&)e);
1.469 - }
1.470 - /// \brief Running node of the iterator
1.471 - ///
1.472 - /// Returns the running node (ie. the target in this case) of the
1.473 - /// iterator
1.474 - Node runningNode(const OutEdgeIt &e) const {
1.475 - return Parent::target((Edge&)e);
1.476 - }
1.477 -
1.478 - /// \brief Base node of the iterator
1.479 - ///
1.480 - /// Returns the base node (ie. the target in this case) of the iterator
1.481 - Node baseNode(const InEdgeIt &e) const {
1.482 - return Parent::target((Edge&)e);
1.483 - }
1.484 - /// \brief Running node of the iterator
1.485 - ///
1.486 - /// Returns the running node (ie. the source in this case) of the
1.487 - /// iterator
1.488 - Node runningNode(const InEdgeIt &e) const {
1.489 - return Parent::source((Edge&)e);
1.490 - }
1.491 -
1.492 - class IncEdgeIt : public Parent::UEdge {
1.493 - friend class IterableBpUGraphExtender;
1.494 - const Graph* graph;
1.495 - bool direction;
1.496 - public:
1.497 -
1.498 - IncEdgeIt() { }
1.499 -
1.500 - IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
1.501 -
1.502 - IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1.503 - graph->firstInc(*this, direction, n);
1.504 - }
1.505 -
1.506 - IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1.507 - : graph(&_graph), UEdge(ue) {
1.508 - direction = (graph->source(ue) == n);
1.509 - }
1.510 -
1.511 - IncEdgeIt& operator++() {
1.512 - graph->nextInc(*this, direction);
1.513 - return *this;
1.514 - }
1.515 - };
1.516 -
1.517 -
1.518 - /// Base node of the iterator
1.519 - ///
1.520 - /// Returns the base node of the iterator
1.521 - Node baseNode(const IncEdgeIt &e) const {
1.522 - return e.direction ? source(e) : target(e);
1.523 - }
1.524 -
1.525 - /// Running node of the iterator
1.526 - ///
1.527 - /// Returns the running node of the iterator
1.528 - Node runningNode(const IncEdgeIt &e) const {
1.529 - return e.direction ? target(e) : source(e);
1.530 - }
1.531 -
1.532 - };
1.533 -
1.534 -}
1.535 -
1.536 -#endif // LEMON_GRAPH_EXTENDER_H