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