1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/graph_adaptor_extender.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,399 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
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_BITS_GRAPH_ADAPTOR_EXTENDER_H
1.23 +#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
1.24 +
1.25 +#include <lemon/core.h>
1.26 +#include <lemon/error.h>
1.27 +
1.28 +namespace lemon {
1.29 +
1.30 + template <typename _Digraph>
1.31 + class DigraphAdaptorExtender : public _Digraph {
1.32 + typedef _Digraph Parent;
1.33 +
1.34 + public:
1.35 +
1.36 + typedef _Digraph Digraph;
1.37 + typedef DigraphAdaptorExtender Adaptor;
1.38 +
1.39 + // Base extensions
1.40 +
1.41 + typedef typename Parent::Node Node;
1.42 + typedef typename Parent::Arc Arc;
1.43 +
1.44 + int maxId(Node) const {
1.45 + return Parent::maxNodeId();
1.46 + }
1.47 +
1.48 + int maxId(Arc) const {
1.49 + return Parent::maxArcId();
1.50 + }
1.51 +
1.52 + Node fromId(int id, Node) const {
1.53 + return Parent::nodeFromId(id);
1.54 + }
1.55 +
1.56 + Arc fromId(int id, Arc) const {
1.57 + return Parent::arcFromId(id);
1.58 + }
1.59 +
1.60 + Node oppositeNode(const Node &n, const Arc &e) const {
1.61 + if (n == Parent::source(e))
1.62 + return Parent::target(e);
1.63 + else if(n==Parent::target(e))
1.64 + return Parent::source(e);
1.65 + else
1.66 + return INVALID;
1.67 + }
1.68 +
1.69 + class NodeIt : public Node {
1.70 + const Adaptor* _adaptor;
1.71 + public:
1.72 +
1.73 + NodeIt() {}
1.74 +
1.75 + NodeIt(Invalid i) : Node(i) { }
1.76 +
1.77 + explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.78 + _adaptor->first(static_cast<Node&>(*this));
1.79 + }
1.80 +
1.81 + NodeIt(const Adaptor& adaptor, const Node& node)
1.82 + : Node(node), _adaptor(&adaptor) {}
1.83 +
1.84 + NodeIt& operator++() {
1.85 + _adaptor->next(*this);
1.86 + return *this;
1.87 + }
1.88 +
1.89 + };
1.90 +
1.91 +
1.92 + class ArcIt : public Arc {
1.93 + const Adaptor* _adaptor;
1.94 + public:
1.95 +
1.96 + ArcIt() { }
1.97 +
1.98 + ArcIt(Invalid i) : Arc(i) { }
1.99 +
1.100 + explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.101 + _adaptor->first(static_cast<Arc&>(*this));
1.102 + }
1.103 +
1.104 + ArcIt(const Adaptor& adaptor, const Arc& e) :
1.105 + Arc(e), _adaptor(&adaptor) { }
1.106 +
1.107 + ArcIt& operator++() {
1.108 + _adaptor->next(*this);
1.109 + return *this;
1.110 + }
1.111 +
1.112 + };
1.113 +
1.114 +
1.115 + class OutArcIt : public Arc {
1.116 + const Adaptor* _adaptor;
1.117 + public:
1.118 +
1.119 + OutArcIt() { }
1.120 +
1.121 + OutArcIt(Invalid i) : Arc(i) { }
1.122 +
1.123 + OutArcIt(const Adaptor& adaptor, const Node& node)
1.124 + : _adaptor(&adaptor) {
1.125 + _adaptor->firstOut(*this, node);
1.126 + }
1.127 +
1.128 + OutArcIt(const Adaptor& adaptor, const Arc& arc)
1.129 + : Arc(arc), _adaptor(&adaptor) {}
1.130 +
1.131 + OutArcIt& operator++() {
1.132 + _adaptor->nextOut(*this);
1.133 + return *this;
1.134 + }
1.135 +
1.136 + };
1.137 +
1.138 +
1.139 + class InArcIt : public Arc {
1.140 + const Adaptor* _adaptor;
1.141 + public:
1.142 +
1.143 + InArcIt() { }
1.144 +
1.145 + InArcIt(Invalid i) : Arc(i) { }
1.146 +
1.147 + InArcIt(const Adaptor& adaptor, const Node& node)
1.148 + : _adaptor(&adaptor) {
1.149 + _adaptor->firstIn(*this, node);
1.150 + }
1.151 +
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 + }
1.159 +
1.160 + };
1.161 +
1.162 + Node baseNode(const OutArcIt &e) const {
1.163 + return Parent::source(e);
1.164 + }
1.165 + Node runningNode(const OutArcIt &e) const {
1.166 + return Parent::target(e);
1.167 + }
1.168 +
1.169 + Node baseNode(const InArcIt &e) const {
1.170 + return Parent::target(e);
1.171 + }
1.172 + Node runningNode(const InArcIt &e) const {
1.173 + return Parent::source(e);
1.174 + }
1.175 +
1.176 + };
1.177 +
1.178 + template <typename _Graph>
1.179 + class GraphAdaptorExtender : public _Graph {
1.180 + typedef _Graph Parent;
1.181 +
1.182 + public:
1.183 +
1.184 + typedef _Graph Graph;
1.185 + typedef GraphAdaptorExtender Adaptor;
1.186 +
1.187 + typedef typename Parent::Node Node;
1.188 + typedef typename Parent::Arc Arc;
1.189 + typedef typename Parent::Edge Edge;
1.190 +
1.191 + // Graph extension
1.192 +
1.193 + int maxId(Node) const {
1.194 + return Parent::maxNodeId();
1.195 + }
1.196 +
1.197 + int maxId(Arc) const {
1.198 + return Parent::maxArcId();
1.199 + }
1.200 +
1.201 + int maxId(Edge) const {
1.202 + return Parent::maxEdgeId();
1.203 + }
1.204 +
1.205 + Node fromId(int id, Node) const {
1.206 + return Parent::nodeFromId(id);
1.207 + }
1.208 +
1.209 + Arc fromId(int id, Arc) const {
1.210 + return Parent::arcFromId(id);
1.211 + }
1.212 +
1.213 + Edge fromId(int id, Edge) const {
1.214 + return Parent::edgeFromId(id);
1.215 + }
1.216 +
1.217 + Node oppositeNode(const Node &n, const Edge &e) const {
1.218 + if( n == Parent::u(e))
1.219 + return Parent::v(e);
1.220 + else if( n == Parent::v(e))
1.221 + return Parent::u(e);
1.222 + else
1.223 + return INVALID;
1.224 + }
1.225 +
1.226 + Arc oppositeArc(const Arc &a) const {
1.227 + return Parent::direct(a, !Parent::direction(a));
1.228 + }
1.229 +
1.230 + using Parent::direct;
1.231 + Arc direct(const Edge &e, const Node &s) const {
1.232 + return Parent::direct(e, Parent::u(e) == s);
1.233 + }
1.234 +
1.235 +
1.236 + class NodeIt : public Node {
1.237 + const Adaptor* _adaptor;
1.238 + public:
1.239 +
1.240 + NodeIt() {}
1.241 +
1.242 + NodeIt(Invalid i) : Node(i) { }
1.243 +
1.244 + explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.245 + _adaptor->first(static_cast<Node&>(*this));
1.246 + }
1.247 +
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 + }
1.255 +
1.256 + };
1.257 +
1.258 +
1.259 + class ArcIt : public Arc {
1.260 + const Adaptor* _adaptor;
1.261 + public:
1.262 +
1.263 + ArcIt() { }
1.264 +
1.265 + ArcIt(Invalid i) : Arc(i) { }
1.266 +
1.267 + explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.268 + _adaptor->first(static_cast<Arc&>(*this));
1.269 + }
1.270 +
1.271 + ArcIt(const Adaptor& adaptor, const Arc& e) :
1.272 + Arc(e), _adaptor(&adaptor) { }
1.273 +
1.274 + ArcIt& operator++() {
1.275 + _adaptor->next(*this);
1.276 + return *this;
1.277 + }
1.278 +
1.279 + };
1.280 +
1.281 +
1.282 + class OutArcIt : public Arc {
1.283 + const Adaptor* _adaptor;
1.284 + public:
1.285 +
1.286 + OutArcIt() { }
1.287 +
1.288 + OutArcIt(Invalid i) : Arc(i) { }
1.289 +
1.290 + OutArcIt(const Adaptor& adaptor, const Node& node)
1.291 + : _adaptor(&adaptor) {
1.292 + _adaptor->firstOut(*this, node);
1.293 + }
1.294 +
1.295 + OutArcIt(const Adaptor& adaptor, const Arc& arc)
1.296 + : Arc(arc), _adaptor(&adaptor) {}
1.297 +
1.298 + OutArcIt& operator++() {
1.299 + _adaptor->nextOut(*this);
1.300 + return *this;
1.301 + }
1.302 +
1.303 + };
1.304 +
1.305 +
1.306 + class InArcIt : public Arc {
1.307 + const Adaptor* _adaptor;
1.308 + public:
1.309 +
1.310 + InArcIt() { }
1.311 +
1.312 + InArcIt(Invalid i) : Arc(i) { }
1.313 +
1.314 + InArcIt(const Adaptor& adaptor, const Node& node)
1.315 + : _adaptor(&adaptor) {
1.316 + _adaptor->firstIn(*this, node);
1.317 + }
1.318 +
1.319 + InArcIt(const Adaptor& adaptor, const Arc& arc) :
1.320 + Arc(arc), _adaptor(&adaptor) {}
1.321 +
1.322 + InArcIt& operator++() {
1.323 + _adaptor->nextIn(*this);
1.324 + return *this;
1.325 + }
1.326 +
1.327 + };
1.328 +
1.329 + class EdgeIt : public Parent::Edge {
1.330 + const Adaptor* _adaptor;
1.331 + public:
1.332 +
1.333 + EdgeIt() { }
1.334 +
1.335 + EdgeIt(Invalid i) : Edge(i) { }
1.336 +
1.337 + explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
1.338 + _adaptor->first(static_cast<Edge&>(*this));
1.339 + }
1.340 +
1.341 + EdgeIt(const Adaptor& adaptor, const Edge& e) :
1.342 + Edge(e), _adaptor(&adaptor) { }
1.343 +
1.344 + EdgeIt& operator++() {
1.345 + _adaptor->next(*this);
1.346 + return *this;
1.347 + }
1.348 +
1.349 + };
1.350 +
1.351 + class IncEdgeIt : public Edge {
1.352 + friend class GraphAdaptorExtender;
1.353 + const Adaptor* _adaptor;
1.354 + bool direction;
1.355 + public:
1.356 +
1.357 + IncEdgeIt() { }
1.358 +
1.359 + IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
1.360 +
1.361 + IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
1.362 + _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
1.363 + }
1.364 +
1.365 + IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
1.366 + : _adaptor(&adaptor), Edge(e) {
1.367 + direction = (_adaptor->u(e) == n);
1.368 + }
1.369 +
1.370 + IncEdgeIt& operator++() {
1.371 + _adaptor->nextInc(*this, direction);
1.372 + return *this;
1.373 + }
1.374 + };
1.375 +
1.376 + Node baseNode(const OutArcIt &a) const {
1.377 + return Parent::source(a);
1.378 + }
1.379 + Node runningNode(const OutArcIt &a) const {
1.380 + return Parent::target(a);
1.381 + }
1.382 +
1.383 + Node baseNode(const InArcIt &a) const {
1.384 + return Parent::target(a);
1.385 + }
1.386 + Node runningNode(const InArcIt &a) const {
1.387 + return Parent::source(a);
1.388 + }
1.389 +
1.390 + Node baseNode(const IncEdgeIt &e) const {
1.391 + return e.direction ? Parent::u(e) : Parent::v(e);
1.392 + }
1.393 + Node runningNode(const IncEdgeIt &e) const {
1.394 + return e.direction ? Parent::v(e) : Parent::u(e);
1.395 + }
1.396 +
1.397 + };
1.398 +
1.399 +}
1.400 +
1.401 +
1.402 +#endif