1.1 --- a/lemon/Makefile.am Sun Nov 30 09:39:34 2008 +0000
1.2 +++ b/lemon/Makefile.am Sun Nov 30 18:57:18 2008 +0100
1.3 @@ -58,10 +58,12 @@
1.4 lemon/bits/bezier.h \
1.5 lemon/bits/default_map.h \
1.6 lemon/bits/enable_if.h \
1.7 + lemon/bits/graph_adaptor_extender.h \
1.8 lemon/bits/graph_extender.h \
1.9 lemon/bits/map_extender.h \
1.10 lemon/bits/path_dump.h \
1.11 lemon/bits/traits.h \
1.12 + lemon/bits/variant.h \
1.13 lemon/bits/vector_map.h
1.14
1.15 concept_HEADERS += \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/bits/graph_adaptor_extender.h Sun Nov 30 18:57:18 2008 +0100
2.3 @@ -0,0 +1,444 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
2.23 +#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
2.24 +
2.25 +#include <lemon/core.h>
2.26 +#include <lemon/error.h>
2.27 +
2.28 +#include <lemon/bits/default_map.h>
2.29 +
2.30 +
2.31 +///\ingroup digraphbits
2.32 +///\file
2.33 +///\brief Extenders for the digraph adaptor types
2.34 +namespace lemon {
2.35 +
2.36 + /// \ingroup digraphbits
2.37 + ///
2.38 + /// \brief Extender for the DigraphAdaptors
2.39 + template <typename _Digraph>
2.40 + class DigraphAdaptorExtender : public _Digraph {
2.41 + public:
2.42 +
2.43 + typedef _Digraph Parent;
2.44 + typedef _Digraph Digraph;
2.45 + typedef DigraphAdaptorExtender Adaptor;
2.46 +
2.47 + // Base extensions
2.48 +
2.49 + typedef typename Parent::Node Node;
2.50 + typedef typename Parent::Arc Arc;
2.51 +
2.52 + int maxId(Node) const {
2.53 + return Parent::maxNodeId();
2.54 + }
2.55 +
2.56 + int maxId(Arc) const {
2.57 + return Parent::maxArcId();
2.58 + }
2.59 +
2.60 + Node fromId(int id, Node) const {
2.61 + return Parent::nodeFromId(id);
2.62 + }
2.63 +
2.64 + Arc fromId(int id, Arc) const {
2.65 + return Parent::arcFromId(id);
2.66 + }
2.67 +
2.68 + Node oppositeNode(const Node &n, const Arc &e) const {
2.69 + if (n == Parent::source(e))
2.70 + return Parent::target(e);
2.71 + else if(n==Parent::target(e))
2.72 + return Parent::source(e);
2.73 + else
2.74 + return INVALID;
2.75 + }
2.76 +
2.77 + class NodeIt : public Node {
2.78 + const Adaptor* _adaptor;
2.79 + public:
2.80 +
2.81 + NodeIt() {}
2.82 +
2.83 + NodeIt(Invalid i) : Node(i) { }
2.84 +
2.85 + explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
2.86 + _adaptor->first(static_cast<Node&>(*this));
2.87 + }
2.88 +
2.89 + NodeIt(const Adaptor& adaptor, const Node& node)
2.90 + : Node(node), _adaptor(&adaptor) {}
2.91 +
2.92 + NodeIt& operator++() {
2.93 + _adaptor->next(*this);
2.94 + return *this;
2.95 + }
2.96 +
2.97 + };
2.98 +
2.99 +
2.100 + class ArcIt : public Arc {
2.101 + const Adaptor* _adaptor;
2.102 + public:
2.103 +
2.104 + ArcIt() { }
2.105 +
2.106 + ArcIt(Invalid i) : Arc(i) { }
2.107 +
2.108 + explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
2.109 + _adaptor->first(static_cast<Arc&>(*this));
2.110 + }
2.111 +
2.112 + ArcIt(const Adaptor& adaptor, const Arc& e) :
2.113 + Arc(e), _adaptor(&adaptor) { }
2.114 +
2.115 + ArcIt& operator++() {
2.116 + _adaptor->next(*this);
2.117 + return *this;
2.118 + }
2.119 +
2.120 + };
2.121 +
2.122 +
2.123 + class OutArcIt : public Arc {
2.124 + const Adaptor* _adaptor;
2.125 + public:
2.126 +
2.127 + OutArcIt() { }
2.128 +
2.129 + OutArcIt(Invalid i) : Arc(i) { }
2.130 +
2.131 + OutArcIt(const Adaptor& adaptor, const Node& node)
2.132 + : _adaptor(&adaptor) {
2.133 + _adaptor->firstOut(*this, node);
2.134 + }
2.135 +
2.136 + OutArcIt(const Adaptor& adaptor, const Arc& arc)
2.137 + : Arc(arc), _adaptor(&adaptor) {}
2.138 +
2.139 + OutArcIt& operator++() {
2.140 + _adaptor->nextOut(*this);
2.141 + return *this;
2.142 + }
2.143 +
2.144 + };
2.145 +
2.146 +
2.147 + class InArcIt : public Arc {
2.148 + const Adaptor* _adaptor;
2.149 + public:
2.150 +
2.151 + InArcIt() { }
2.152 +
2.153 + InArcIt(Invalid i) : Arc(i) { }
2.154 +
2.155 + InArcIt(const Adaptor& adaptor, const Node& node)
2.156 + : _adaptor(&adaptor) {
2.157 + _adaptor->firstIn(*this, node);
2.158 + }
2.159 +
2.160 + InArcIt(const Adaptor& adaptor, const Arc& arc) :
2.161 + Arc(arc), _adaptor(&adaptor) {}
2.162 +
2.163 + InArcIt& operator++() {
2.164 + _adaptor->nextIn(*this);
2.165 + return *this;
2.166 + }
2.167 +
2.168 + };
2.169 +
2.170 + /// \brief Base node of the iterator
2.171 + ///
2.172 + /// Returns the base node (ie. the source in this case) of the iterator
2.173 + Node baseNode(const OutArcIt &e) const {
2.174 + return Parent::source(e);
2.175 + }
2.176 + /// \brief Running node of the iterator
2.177 + ///
2.178 + /// Returns the running node (ie. the target in this case) of the
2.179 + /// iterator
2.180 + Node runningNode(const OutArcIt &e) const {
2.181 + return Parent::target(e);
2.182 + }
2.183 +
2.184 + /// \brief Base node of the iterator
2.185 + ///
2.186 + /// Returns the base node (ie. the target in this case) of the iterator
2.187 + Node baseNode(const InArcIt &e) const {
2.188 + return Parent::target(e);
2.189 + }
2.190 + /// \brief Running node of the iterator
2.191 + ///
2.192 + /// Returns the running node (ie. the source in this case) of the
2.193 + /// iterator
2.194 + Node runningNode(const InArcIt &e) const {
2.195 + return Parent::source(e);
2.196 + }
2.197 +
2.198 + };
2.199 +
2.200 +
2.201 + /// \ingroup digraphbits
2.202 + ///
2.203 + /// \brief Extender for the GraphAdaptors
2.204 + template <typename _Graph>
2.205 + class GraphAdaptorExtender : public _Graph {
2.206 + public:
2.207 +
2.208 + typedef _Graph Parent;
2.209 + typedef _Graph Graph;
2.210 + typedef GraphAdaptorExtender Adaptor;
2.211 +
2.212 + typedef typename Parent::Node Node;
2.213 + typedef typename Parent::Arc Arc;
2.214 + typedef typename Parent::Edge Edge;
2.215 +
2.216 + // Graph extension
2.217 +
2.218 + int maxId(Node) const {
2.219 + return Parent::maxNodeId();
2.220 + }
2.221 +
2.222 + int maxId(Arc) const {
2.223 + return Parent::maxArcId();
2.224 + }
2.225 +
2.226 + int maxId(Edge) const {
2.227 + return Parent::maxEdgeId();
2.228 + }
2.229 +
2.230 + Node fromId(int id, Node) const {
2.231 + return Parent::nodeFromId(id);
2.232 + }
2.233 +
2.234 + Arc fromId(int id, Arc) const {
2.235 + return Parent::arcFromId(id);
2.236 + }
2.237 +
2.238 + Edge fromId(int id, Edge) const {
2.239 + return Parent::edgeFromId(id);
2.240 + }
2.241 +
2.242 + Node oppositeNode(const Node &n, const Edge &e) const {
2.243 + if( n == Parent::u(e))
2.244 + return Parent::v(e);
2.245 + else if( n == Parent::v(e))
2.246 + return Parent::u(e);
2.247 + else
2.248 + return INVALID;
2.249 + }
2.250 +
2.251 + Arc oppositeArc(const Arc &a) const {
2.252 + return Parent::direct(a, !Parent::direction(a));
2.253 + }
2.254 +
2.255 + using Parent::direct;
2.256 + Arc direct(const Edge &e, const Node &s) const {
2.257 + return Parent::direct(e, Parent::u(e) == s);
2.258 + }
2.259 +
2.260 +
2.261 + class NodeIt : public Node {
2.262 + const Adaptor* _adaptor;
2.263 + public:
2.264 +
2.265 + NodeIt() {}
2.266 +
2.267 + NodeIt(Invalid i) : Node(i) { }
2.268 +
2.269 + explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
2.270 + _adaptor->first(static_cast<Node&>(*this));
2.271 + }
2.272 +
2.273 + NodeIt(const Adaptor& adaptor, const Node& node)
2.274 + : Node(node), _adaptor(&adaptor) {}
2.275 +
2.276 + NodeIt& operator++() {
2.277 + _adaptor->next(*this);
2.278 + return *this;
2.279 + }
2.280 +
2.281 + };
2.282 +
2.283 +
2.284 + class ArcIt : public Arc {
2.285 + const Adaptor* _adaptor;
2.286 + public:
2.287 +
2.288 + ArcIt() { }
2.289 +
2.290 + ArcIt(Invalid i) : Arc(i) { }
2.291 +
2.292 + explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
2.293 + _adaptor->first(static_cast<Arc&>(*this));
2.294 + }
2.295 +
2.296 + ArcIt(const Adaptor& adaptor, const Arc& e) :
2.297 + Arc(e), _adaptor(&adaptor) { }
2.298 +
2.299 + ArcIt& operator++() {
2.300 + _adaptor->next(*this);
2.301 + return *this;
2.302 + }
2.303 +
2.304 + };
2.305 +
2.306 +
2.307 + class OutArcIt : public Arc {
2.308 + const Adaptor* _adaptor;
2.309 + public:
2.310 +
2.311 + OutArcIt() { }
2.312 +
2.313 + OutArcIt(Invalid i) : Arc(i) { }
2.314 +
2.315 + OutArcIt(const Adaptor& adaptor, const Node& node)
2.316 + : _adaptor(&adaptor) {
2.317 + _adaptor->firstOut(*this, node);
2.318 + }
2.319 +
2.320 + OutArcIt(const Adaptor& adaptor, const Arc& arc)
2.321 + : Arc(arc), _adaptor(&adaptor) {}
2.322 +
2.323 + OutArcIt& operator++() {
2.324 + _adaptor->nextOut(*this);
2.325 + return *this;
2.326 + }
2.327 +
2.328 + };
2.329 +
2.330 +
2.331 + class InArcIt : public Arc {
2.332 + const Adaptor* _adaptor;
2.333 + public:
2.334 +
2.335 + InArcIt() { }
2.336 +
2.337 + InArcIt(Invalid i) : Arc(i) { }
2.338 +
2.339 + InArcIt(const Adaptor& adaptor, const Node& node)
2.340 + : _adaptor(&adaptor) {
2.341 + _adaptor->firstIn(*this, node);
2.342 + }
2.343 +
2.344 + InArcIt(const Adaptor& adaptor, const Arc& arc) :
2.345 + Arc(arc), _adaptor(&adaptor) {}
2.346 +
2.347 + InArcIt& operator++() {
2.348 + _adaptor->nextIn(*this);
2.349 + return *this;
2.350 + }
2.351 +
2.352 + };
2.353 +
2.354 + class EdgeIt : public Parent::Edge {
2.355 + const Adaptor* _adaptor;
2.356 + public:
2.357 +
2.358 + EdgeIt() { }
2.359 +
2.360 + EdgeIt(Invalid i) : Edge(i) { }
2.361 +
2.362 + explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
2.363 + _adaptor->first(static_cast<Edge&>(*this));
2.364 + }
2.365 +
2.366 + EdgeIt(const Adaptor& adaptor, const Edge& e) :
2.367 + Edge(e), _adaptor(&adaptor) { }
2.368 +
2.369 + EdgeIt& operator++() {
2.370 + _adaptor->next(*this);
2.371 + return *this;
2.372 + }
2.373 +
2.374 + };
2.375 +
2.376 + class IncEdgeIt : public Edge {
2.377 + friend class GraphAdaptorExtender;
2.378 + const Adaptor* _adaptor;
2.379 + bool direction;
2.380 + public:
2.381 +
2.382 + IncEdgeIt() { }
2.383 +
2.384 + IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
2.385 +
2.386 + IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
2.387 + _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
2.388 + }
2.389 +
2.390 + IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
2.391 + : _adaptor(&adaptor), Edge(e) {
2.392 + direction = (_adaptor->u(e) == n);
2.393 + }
2.394 +
2.395 + IncEdgeIt& operator++() {
2.396 + _adaptor->nextInc(*this, direction);
2.397 + return *this;
2.398 + }
2.399 + };
2.400 +
2.401 + /// \brief Base node of the iterator
2.402 + ///
2.403 + /// Returns the base node (ie. the source in this case) of the iterator
2.404 + Node baseNode(const OutArcIt &a) const {
2.405 + return Parent::source(a);
2.406 + }
2.407 + /// \brief Running node of the iterator
2.408 + ///
2.409 + /// Returns the running node (ie. the target in this case) of the
2.410 + /// iterator
2.411 + Node runningNode(const OutArcIt &a) const {
2.412 + return Parent::target(a);
2.413 + }
2.414 +
2.415 + /// \brief Base node of the iterator
2.416 + ///
2.417 + /// Returns the base node (ie. the target in this case) of the iterator
2.418 + Node baseNode(const InArcIt &a) const {
2.419 + return Parent::target(a);
2.420 + }
2.421 + /// \brief Running node of the iterator
2.422 + ///
2.423 + /// Returns the running node (ie. the source in this case) of the
2.424 + /// iterator
2.425 + Node runningNode(const InArcIt &a) const {
2.426 + return Parent::source(a);
2.427 + }
2.428 +
2.429 + /// Base node of the iterator
2.430 + ///
2.431 + /// Returns the base node of the iterator
2.432 + Node baseNode(const IncEdgeIt &e) const {
2.433 + return e.direction ? Parent::u(e) : Parent::v(e);
2.434 + }
2.435 + /// Running node of the iterator
2.436 + ///
2.437 + /// Returns the running node of the iterator
2.438 + Node runningNode(const IncEdgeIt &e) const {
2.439 + return e.direction ? Parent::v(e) : Parent::u(e);
2.440 + }
2.441 +
2.442 + };
2.443 +
2.444 +}
2.445 +
2.446 +
2.447 +#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/bits/variant.h Sun Nov 30 18:57:18 2008 +0100
3.3 @@ -0,0 +1,494 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2008
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#ifndef LEMON_BITS_VARIANT_H
3.23 +#define LEMON_BITS_VARIANT_H
3.24 +
3.25 +#include <lemon/assert.h>
3.26 +
3.27 +/// \file
3.28 +/// \brief Variant types
3.29 +
3.30 +namespace lemon {
3.31 +
3.32 + namespace _variant_bits {
3.33 +
3.34 + template <int left, int right>
3.35 + struct CTMax {
3.36 + static const int value = left < right ? right : left;
3.37 + };
3.38 +
3.39 + }
3.40 +
3.41 +
3.42 + /// \brief Simple Variant type for two types
3.43 + ///
3.44 + /// Simple Variant type for two types. The Variant type is a type
3.45 + /// safe union. The C++ has strong limitations for using unions, by
3.46 + /// example we can not store type with non default constructor or
3.47 + /// destructor in an union. This class always knowns the current
3.48 + /// state of the variant and it cares for the proper construction
3.49 + /// and destruction.
3.50 + template <typename _First, typename _Second>
3.51 + class BiVariant {
3.52 + public:
3.53 +
3.54 + /// \brief The \c First type.
3.55 + typedef _First First;
3.56 + /// \brief The \c Second type.
3.57 + typedef _Second Second;
3.58 +
3.59 + /// \brief Constructor
3.60 + ///
3.61 + /// This constructor initalizes to the default value of the \c First
3.62 + /// type.
3.63 + BiVariant() {
3.64 + flag = true;
3.65 + new(reinterpret_cast<First*>(data)) First();
3.66 + }
3.67 +
3.68 + /// \brief Constructor
3.69 + ///
3.70 + /// This constructor initalizes to the given value of the \c First
3.71 + /// type.
3.72 + BiVariant(const First& f) {
3.73 + flag = true;
3.74 + new(reinterpret_cast<First*>(data)) First(f);
3.75 + }
3.76 +
3.77 + /// \brief Constructor
3.78 + ///
3.79 + /// This constructor initalizes to the given value of the \c
3.80 + /// Second type.
3.81 + BiVariant(const Second& s) {
3.82 + flag = false;
3.83 + new(reinterpret_cast<Second*>(data)) Second(s);
3.84 + }
3.85 +
3.86 + /// \brief Copy constructor
3.87 + ///
3.88 + /// Copy constructor
3.89 + BiVariant(const BiVariant& bivariant) {
3.90 + flag = bivariant.flag;
3.91 + if (flag) {
3.92 + new(reinterpret_cast<First*>(data)) First(bivariant.first());
3.93 + } else {
3.94 + new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
3.95 + }
3.96 + }
3.97 +
3.98 + /// \brief Destrcutor
3.99 + ///
3.100 + /// Destructor
3.101 + ~BiVariant() {
3.102 + destroy();
3.103 + }
3.104 +
3.105 + /// \brief Set to the default value of the \c First type.
3.106 + ///
3.107 + /// This function sets the variant to the default value of the \c
3.108 + /// First type.
3.109 + BiVariant& setFirst() {
3.110 + destroy();
3.111 + flag = true;
3.112 + new(reinterpret_cast<First*>(data)) First();
3.113 + return *this;
3.114 + }
3.115 +
3.116 + /// \brief Set to the given value of the \c First type.
3.117 + ///
3.118 + /// This function sets the variant to the given value of the \c
3.119 + /// First type.
3.120 + BiVariant& setFirst(const First& f) {
3.121 + destroy();
3.122 + flag = true;
3.123 + new(reinterpret_cast<First*>(data)) First(f);
3.124 + return *this;
3.125 + }
3.126 +
3.127 + /// \brief Set to the default value of the \c Second type.
3.128 + ///
3.129 + /// This function sets the variant to the default value of the \c
3.130 + /// Second type.
3.131 + BiVariant& setSecond() {
3.132 + destroy();
3.133 + flag = false;
3.134 + new(reinterpret_cast<Second*>(data)) Second();
3.135 + return *this;
3.136 + }
3.137 +
3.138 + /// \brief Set to the given value of the \c Second type.
3.139 + ///
3.140 + /// This function sets the variant to the given value of the \c
3.141 + /// Second type.
3.142 + BiVariant& setSecond(const Second& s) {
3.143 + destroy();
3.144 + flag = false;
3.145 + new(reinterpret_cast<Second*>(data)) Second(s);
3.146 + return *this;
3.147 + }
3.148 +
3.149 + /// \brief Operator form of the \c setFirst()
3.150 + BiVariant& operator=(const First& f) {
3.151 + return setFirst(f);
3.152 + }
3.153 +
3.154 + /// \brief Operator form of the \c setSecond()
3.155 + BiVariant& operator=(const Second& s) {
3.156 + return setSecond(s);
3.157 + }
3.158 +
3.159 + /// \brief Assign operator
3.160 + BiVariant& operator=(const BiVariant& bivariant) {
3.161 + if (this == &bivariant) return *this;
3.162 + destroy();
3.163 + flag = bivariant.flag;
3.164 + if (flag) {
3.165 + new(reinterpret_cast<First*>(data)) First(bivariant.first());
3.166 + } else {
3.167 + new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
3.168 + }
3.169 + return *this;
3.170 + }
3.171 +
3.172 + /// \brief Reference to the value
3.173 + ///
3.174 + /// Reference to the value of the \c First type.
3.175 + /// \pre The BiVariant should store value of \c First type.
3.176 + First& first() {
3.177 + LEMON_DEBUG(flag, "Variant wrong state");
3.178 + return *reinterpret_cast<First*>(data);
3.179 + }
3.180 +
3.181 + /// \brief Const reference to the value
3.182 + ///
3.183 + /// Const reference to the value of the \c First type.
3.184 + /// \pre The BiVariant should store value of \c First type.
3.185 + const First& first() const {
3.186 + LEMON_DEBUG(flag, "Variant wrong state");
3.187 + return *reinterpret_cast<const First*>(data);
3.188 + }
3.189 +
3.190 + /// \brief Operator form of the \c first()
3.191 + operator First&() { return first(); }
3.192 + /// \brief Operator form of the const \c first()
3.193 + operator const First&() const { return first(); }
3.194 +
3.195 + /// \brief Reference to the value
3.196 + ///
3.197 + /// Reference to the value of the \c Second type.
3.198 + /// \pre The BiVariant should store value of \c Second type.
3.199 + Second& second() {
3.200 + LEMON_DEBUG(!flag, "Variant wrong state");
3.201 + return *reinterpret_cast<Second*>(data);
3.202 + }
3.203 +
3.204 + /// \brief Const reference to the value
3.205 + ///
3.206 + /// Const reference to the value of the \c Second type.
3.207 + /// \pre The BiVariant should store value of \c Second type.
3.208 + const Second& second() const {
3.209 + LEMON_DEBUG(!flag, "Variant wrong state");
3.210 + return *reinterpret_cast<const Second*>(data);
3.211 + }
3.212 +
3.213 + /// \brief Operator form of the \c second()
3.214 + operator Second&() { return second(); }
3.215 + /// \brief Operator form of the const \c second()
3.216 + operator const Second&() const { return second(); }
3.217 +
3.218 + /// \brief %True when the variant is in the first state
3.219 + ///
3.220 + /// %True when the variant stores value of the \c First type.
3.221 + bool firstState() const { return flag; }
3.222 +
3.223 + /// \brief %True when the variant is in the second state
3.224 + ///
3.225 + /// %True when the variant stores value of the \c Second type.
3.226 + bool secondState() const { return !flag; }
3.227 +
3.228 + private:
3.229 +
3.230 + void destroy() {
3.231 + if (flag) {
3.232 + reinterpret_cast<First*>(data)->~First();
3.233 + } else {
3.234 + reinterpret_cast<Second*>(data)->~Second();
3.235 + }
3.236 + }
3.237 +
3.238 + char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value];
3.239 + bool flag;
3.240 + };
3.241 +
3.242 + namespace _variant_bits {
3.243 +
3.244 + template <int _idx, typename _TypeMap>
3.245 + struct Memory {
3.246 +
3.247 + typedef typename _TypeMap::template Map<_idx>::Type Current;
3.248 +
3.249 + static void destroy(int index, char* place) {
3.250 + if (index == _idx) {
3.251 + reinterpret_cast<Current*>(place)->~Current();
3.252 + } else {
3.253 + Memory<_idx - 1, _TypeMap>::destroy(index, place);
3.254 + }
3.255 + }
3.256 +
3.257 + static void copy(int index, char* to, const char* from) {
3.258 + if (index == _idx) {
3.259 + new (reinterpret_cast<Current*>(to))
3.260 + Current(reinterpret_cast<const Current*>(from));
3.261 + } else {
3.262 + Memory<_idx - 1, _TypeMap>::copy(index, to, from);
3.263 + }
3.264 + }
3.265 +
3.266 + };
3.267 +
3.268 + template <typename _TypeMap>
3.269 + struct Memory<-1, _TypeMap> {
3.270 +
3.271 + static void destroy(int, char*) {
3.272 + LEMON_DEBUG(false, "Variant wrong index.");
3.273 + }
3.274 +
3.275 + static void copy(int, char*, const char*) {
3.276 + LEMON_DEBUG(false, "Variant wrong index.");
3.277 + }
3.278 + };
3.279 +
3.280 + template <int _idx, typename _TypeMap>
3.281 + struct Size {
3.282 + static const int value =
3.283 + CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type),
3.284 + Size<_idx - 1, _TypeMap>::value>::value;
3.285 + };
3.286 +
3.287 + template <typename _TypeMap>
3.288 + struct Size<0, _TypeMap> {
3.289 + static const int value =
3.290 + sizeof(typename _TypeMap::template Map<0>::Type);
3.291 + };
3.292 +
3.293 + }
3.294 +
3.295 + /// \brief Variant type
3.296 + ///
3.297 + /// Simple Variant type. The Variant type is a type safe union. The
3.298 + /// C++ has strong limitations for using unions, for example we
3.299 + /// cannot store type with non default constructor or destructor in
3.300 + /// a union. This class always knowns the current state of the
3.301 + /// variant and it cares for the proper construction and
3.302 + /// destruction.
3.303 + ///
3.304 + /// \param _num The number of the types which can be stored in the
3.305 + /// variant type.
3.306 + /// \param _TypeMap This class describes the types of the Variant. The
3.307 + /// _TypeMap::Map<index>::Type should be a valid type for each index
3.308 + /// in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper
3.309 + /// class to define such type mappings up to 10 types.
3.310 + ///
3.311 + /// And the usage of the class:
3.312 + ///\code
3.313 + /// typedef Variant<3, VariantTypeMap<int, std::string, double> > MyVariant;
3.314 + /// MyVariant var;
3.315 + /// var.set<0>(12);
3.316 + /// std::cout << var.get<0>() << std::endl;
3.317 + /// var.set<1>("alpha");
3.318 + /// std::cout << var.get<1>() << std::endl;
3.319 + /// var.set<2>(0.75);
3.320 + /// std::cout << var.get<2>() << std::endl;
3.321 + ///\endcode
3.322 + ///
3.323 + /// The result of course:
3.324 + ///\code
3.325 + /// 12
3.326 + /// alpha
3.327 + /// 0.75
3.328 + ///\endcode
3.329 + template <int _num, typename _TypeMap>
3.330 + class Variant {
3.331 + public:
3.332 +
3.333 + static const int num = _num;
3.334 +
3.335 + typedef _TypeMap TypeMap;
3.336 +
3.337 + /// \brief Constructor
3.338 + ///
3.339 + /// This constructor initalizes to the default value of the \c type
3.340 + /// with 0 index.
3.341 + Variant() {
3.342 + flag = 0;
3.343 + new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data))
3.344 + typename TypeMap::template Map<0>::Type();
3.345 + }
3.346 +
3.347 +
3.348 + /// \brief Copy constructor
3.349 + ///
3.350 + /// Copy constructor
3.351 + Variant(const Variant& variant) {
3.352 + flag = variant.flag;
3.353 + _variant_bits::Memory<num - 1, TypeMap>::copy(flag, data, variant.data);
3.354 + }
3.355 +
3.356 + /// \brief Assign operator
3.357 + ///
3.358 + /// Assign operator
3.359 + Variant& operator=(const Variant& variant) {
3.360 + if (this == &variant) return *this;
3.361 + _variant_bits::Memory<num - 1, TypeMap>::
3.362 + destroy(flag, data);
3.363 + flag = variant.flag;
3.364 + _variant_bits::Memory<num - 1, TypeMap>::
3.365 + copy(flag, data, variant.data);
3.366 + return *this;
3.367 + }
3.368 +
3.369 + /// \brief Destrcutor
3.370 + ///
3.371 + /// Destructor
3.372 + ~Variant() {
3.373 + _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
3.374 + }
3.375 +
3.376 + /// \brief Set to the default value of the type with \c _idx index.
3.377 + ///
3.378 + /// This function sets the variant to the default value of the
3.379 + /// type with \c _idx index.
3.380 + template <int _idx>
3.381 + Variant& set() {
3.382 + _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
3.383 + flag = _idx;
3.384 + new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
3.385 + typename TypeMap::template Map<_idx>::Type();
3.386 + return *this;
3.387 + }
3.388 +
3.389 + /// \brief Set to the given value of the type with \c _idx index.
3.390 + ///
3.391 + /// This function sets the variant to the given value of the type
3.392 + /// with \c _idx index.
3.393 + template <int _idx>
3.394 + Variant& set(const typename _TypeMap::template Map<_idx>::Type& init) {
3.395 + _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
3.396 + flag = _idx;
3.397 + new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
3.398 + typename TypeMap::template Map<_idx>::Type(init);
3.399 + return *this;
3.400 + }
3.401 +
3.402 + /// \brief Gets the current value of the type with \c _idx index.
3.403 + ///
3.404 + /// Gets the current value of the type with \c _idx index.
3.405 + template <int _idx>
3.406 + const typename TypeMap::template Map<_idx>::Type& get() const {
3.407 + LEMON_DEBUG(_idx == flag, "Variant wrong index");
3.408 + return *reinterpret_cast<const typename TypeMap::
3.409 + template Map<_idx>::Type*>(data);
3.410 + }
3.411 +
3.412 + /// \brief Gets the current value of the type with \c _idx index.
3.413 + ///
3.414 + /// Gets the current value of the type with \c _idx index.
3.415 + template <int _idx>
3.416 + typename _TypeMap::template Map<_idx>::Type& get() {
3.417 + LEMON_DEBUG(_idx == flag, "Variant wrong index");
3.418 + return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>
3.419 + (data);
3.420 + }
3.421 +
3.422 + /// \brief Returns the current state of the variant.
3.423 + ///
3.424 + /// Returns the current state of the variant.
3.425 + int state() const {
3.426 + return flag;
3.427 + }
3.428 +
3.429 + private:
3.430 +
3.431 + char data[_variant_bits::Size<num - 1, TypeMap>::value];
3.432 + int flag;
3.433 + };
3.434 +
3.435 + namespace _variant_bits {
3.436 +
3.437 + template <int _index, typename _List>
3.438 + struct Get {
3.439 + typedef typename Get<_index - 1, typename _List::Next>::Type Type;
3.440 + };
3.441 +
3.442 + template <typename _List>
3.443 + struct Get<0, _List> {
3.444 + typedef typename _List::Type Type;
3.445 + };
3.446 +
3.447 + struct List {};
3.448 +
3.449 + template <typename _Type, typename _List>
3.450 + struct Insert {
3.451 + typedef _List Next;
3.452 + typedef _Type Type;
3.453 + };
3.454 +
3.455 + template <int _idx, typename _T0, typename _T1, typename _T2,
3.456 + typename _T3, typename _T5, typename _T4, typename _T6,
3.457 + typename _T7, typename _T8, typename _T9>
3.458 + struct Mapper {
3.459 + typedef List L10;
3.460 + typedef Insert<_T9, L10> L9;
3.461 + typedef Insert<_T8, L9> L8;
3.462 + typedef Insert<_T7, L8> L7;
3.463 + typedef Insert<_T6, L7> L6;
3.464 + typedef Insert<_T5, L6> L5;
3.465 + typedef Insert<_T4, L5> L4;
3.466 + typedef Insert<_T3, L4> L3;
3.467 + typedef Insert<_T2, L3> L2;
3.468 + typedef Insert<_T1, L2> L1;
3.469 + typedef Insert<_T0, L1> L0;
3.470 + typedef typename Get<_idx, L0>::Type Type;
3.471 + };
3.472 +
3.473 + }
3.474 +
3.475 + /// \brief Helper class for Variant
3.476 + ///
3.477 + /// Helper class to define type mappings for Variant. This class
3.478 + /// converts the template parameters to be mappable by integer.
3.479 + /// \see Variant
3.480 + template <
3.481 + typename _T0,
3.482 + typename _T1 = void, typename _T2 = void, typename _T3 = void,
3.483 + typename _T5 = void, typename _T4 = void, typename _T6 = void,
3.484 + typename _T7 = void, typename _T8 = void, typename _T9 = void>
3.485 + struct VariantTypeMap {
3.486 + template <int _idx>
3.487 + struct Map {
3.488 + typedef typename _variant_bits::
3.489 + Mapper<_idx, _T0, _T1, _T2, _T3, _T4, _T5, _T6, _T7, _T8, _T9>::Type
3.490 + Type;
3.491 + };
3.492 + };
3.493 +
3.494 +}
3.495 +
3.496 +
3.497 +#endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/digraph_adaptor.h Sun Nov 30 18:57:18 2008 +0100
4.3 @@ -0,0 +1,2530 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2008
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_DIGRAPH_ADAPTOR_H
4.23 +#define LEMON_DIGRAPH_ADAPTOR_H
4.24 +
4.25 +///\ingroup graph_adaptors
4.26 +///\file
4.27 +///\brief Several digraph adaptors.
4.28 +///
4.29 +///This file contains several useful digraph adaptor functions.
4.30 +
4.31 +#include <lemon/core.h>
4.32 +#include <lemon/maps.h>
4.33 +#include <lemon/bits/variant.h>
4.34 +
4.35 +#include <lemon/bits/base_extender.h>
4.36 +#include <lemon/bits/graph_adaptor_extender.h>
4.37 +#include <lemon/bits/graph_extender.h>
4.38 +#include <lemon/tolerance.h>
4.39 +
4.40 +#include <algorithm>
4.41 +
4.42 +namespace lemon {
4.43 +
4.44 + ///\brief Base type for the Digraph Adaptors
4.45 + ///
4.46 + ///Base type for the Digraph Adaptors
4.47 + ///
4.48 + ///This is the base type for most of LEMON digraph adaptors. This
4.49 + ///class implements a trivial digraph adaptor i.e. it only wraps the
4.50 + ///functions and types of the digraph. The purpose of this class is
4.51 + ///to make easier implementing digraph adaptors. E.g. if an adaptor
4.52 + ///is considered which differs from the wrapped digraph only in some
4.53 + ///of its functions or types, then it can be derived from
4.54 + ///DigraphAdaptor, and only the differences should be implemented.
4.55 + template<typename _Digraph>
4.56 + class DigraphAdaptorBase {
4.57 + public:
4.58 + typedef _Digraph Digraph;
4.59 + typedef DigraphAdaptorBase Adaptor;
4.60 + typedef Digraph ParentDigraph;
4.61 +
4.62 + protected:
4.63 + Digraph* _digraph;
4.64 + DigraphAdaptorBase() : _digraph(0) { }
4.65 + void setDigraph(Digraph& digraph) { _digraph = &digraph; }
4.66 +
4.67 + public:
4.68 + DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
4.69 +
4.70 + typedef typename Digraph::Node Node;
4.71 + typedef typename Digraph::Arc Arc;
4.72 +
4.73 + void first(Node& i) const { _digraph->first(i); }
4.74 + void first(Arc& i) const { _digraph->first(i); }
4.75 + void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
4.76 + void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
4.77 +
4.78 + void next(Node& i) const { _digraph->next(i); }
4.79 + void next(Arc& i) const { _digraph->next(i); }
4.80 + void nextIn(Arc& i) const { _digraph->nextIn(i); }
4.81 + void nextOut(Arc& i) const { _digraph->nextOut(i); }
4.82 +
4.83 + Node source(const Arc& a) const { return _digraph->source(a); }
4.84 + Node target(const Arc& a) const { return _digraph->target(a); }
4.85 +
4.86 + typedef NodeNumTagIndicator<Digraph> NodeNumTag;
4.87 + int nodeNum() const { return _digraph->nodeNum(); }
4.88 +
4.89 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
4.90 + int arcNum() const { return _digraph->arcNum(); }
4.91 +
4.92 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
4.93 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
4.94 + return _digraph->findArc(u, v, prev);
4.95 + }
4.96 +
4.97 + Node addNode() { return _digraph->addNode(); }
4.98 + Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
4.99 +
4.100 + void erase(const Node& n) const { _digraph->erase(n); }
4.101 + void erase(const Arc& a) const { _digraph->erase(a); }
4.102 +
4.103 + void clear() const { _digraph->clear(); }
4.104 +
4.105 + int id(const Node& n) const { return _digraph->id(n); }
4.106 + int id(const Arc& a) const { return _digraph->id(a); }
4.107 +
4.108 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
4.109 + Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
4.110 +
4.111 + int maxNodeId() const { return _digraph->maxNodeId(); }
4.112 + int maxArcId() const { return _digraph->maxArcId(); }
4.113 +
4.114 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
4.115 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
4.116 +
4.117 + typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
4.118 + ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
4.119 +
4.120 + template <typename _Value>
4.121 + class NodeMap : public Digraph::template NodeMap<_Value> {
4.122 + public:
4.123 +
4.124 + typedef typename Digraph::template NodeMap<_Value> Parent;
4.125 +
4.126 + explicit NodeMap(const Adaptor& adaptor)
4.127 + : Parent(*adaptor._digraph) {}
4.128 +
4.129 + NodeMap(const Adaptor& adaptor, const _Value& value)
4.130 + : Parent(*adaptor._digraph, value) { }
4.131 +
4.132 + private:
4.133 + NodeMap& operator=(const NodeMap& cmap) {
4.134 + return operator=<NodeMap>(cmap);
4.135 + }
4.136 +
4.137 + template <typename CMap>
4.138 + NodeMap& operator=(const CMap& cmap) {
4.139 + Parent::operator=(cmap);
4.140 + return *this;
4.141 + }
4.142 +
4.143 + };
4.144 +
4.145 + template <typename _Value>
4.146 + class ArcMap : public Digraph::template ArcMap<_Value> {
4.147 + public:
4.148 +
4.149 + typedef typename Digraph::template ArcMap<_Value> Parent;
4.150 +
4.151 + explicit ArcMap(const Adaptor& adaptor)
4.152 + : Parent(*adaptor._digraph) {}
4.153 +
4.154 + ArcMap(const Adaptor& adaptor, const _Value& value)
4.155 + : Parent(*adaptor._digraph, value) {}
4.156 +
4.157 + private:
4.158 + ArcMap& operator=(const ArcMap& cmap) {
4.159 + return operator=<ArcMap>(cmap);
4.160 + }
4.161 +
4.162 + template <typename CMap>
4.163 + ArcMap& operator=(const CMap& cmap) {
4.164 + Parent::operator=(cmap);
4.165 + return *this;
4.166 + }
4.167 +
4.168 + };
4.169 +
4.170 + };
4.171 +
4.172 + ///\ingroup graph_adaptors
4.173 + ///
4.174 + ///\brief Trivial Digraph Adaptor
4.175 + ///
4.176 + /// This class is an adaptor which does not change the adapted
4.177 + /// digraph. It can be used only to test the digraph adaptors.
4.178 + template <typename _Digraph>
4.179 + class DigraphAdaptor :
4.180 + public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {
4.181 + public:
4.182 + typedef _Digraph Digraph;
4.183 + typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;
4.184 + protected:
4.185 + DigraphAdaptor() : Parent() { }
4.186 +
4.187 + public:
4.188 + explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }
4.189 + };
4.190 +
4.191 + /// \brief Just gives back a digraph adaptor
4.192 + ///
4.193 + /// Just gives back a digraph adaptor which
4.194 + /// should be provide original digraph
4.195 + template<typename Digraph>
4.196 + DigraphAdaptor<const Digraph>
4.197 + digraphAdaptor(const Digraph& digraph) {
4.198 + return DigraphAdaptor<const Digraph>(digraph);
4.199 + }
4.200 +
4.201 +
4.202 + template <typename _Digraph>
4.203 + class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
4.204 + public:
4.205 + typedef _Digraph Digraph;
4.206 + typedef DigraphAdaptorBase<_Digraph> Parent;
4.207 + protected:
4.208 + RevDigraphAdaptorBase() : Parent() { }
4.209 + public:
4.210 + typedef typename Parent::Node Node;
4.211 + typedef typename Parent::Arc Arc;
4.212 +
4.213 + void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
4.214 + void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
4.215 +
4.216 + void nextIn(Arc& a) const { Parent::nextOut(a); }
4.217 + void nextOut(Arc& a) const { Parent::nextIn(a); }
4.218 +
4.219 + Node source(const Arc& a) const { return Parent::target(a); }
4.220 + Node target(const Arc& a) const { return Parent::source(a); }
4.221 +
4.222 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
4.223 + Arc findArc(const Node& u, const Node& v,
4.224 + const Arc& prev = INVALID) {
4.225 + return Parent::findArc(v, u, prev);
4.226 + }
4.227 +
4.228 + };
4.229 +
4.230 +
4.231 + ///\ingroup graph_adaptors
4.232 + ///
4.233 + ///\brief A digraph adaptor which reverses the orientation of the arcs.
4.234 + ///
4.235 + /// If \c g is defined as
4.236 + ///\code
4.237 + /// ListDigraph g;
4.238 + ///\endcode
4.239 + /// then
4.240 + ///\code
4.241 + /// RevDigraphAdaptor<ListDigraph> ga(g);
4.242 + ///\endcode
4.243 + /// implements the digraph obtained from \c g by
4.244 + /// reversing the orientation of its arcs.
4.245 + ///
4.246 + /// A good example of using RevDigraphAdaptor is to decide that the
4.247 + /// directed graph is wheter strongly connected or not. If from one
4.248 + /// node each node is reachable and from each node is reachable this
4.249 + /// node then and just then the digraph is strongly
4.250 + /// connected. Instead of this condition we use a little bit
4.251 + /// different. From one node each node ahould be reachable in the
4.252 + /// digraph and in the reversed digraph. Now this condition can be
4.253 + /// checked with the Dfs algorithm class and the RevDigraphAdaptor
4.254 + /// algorithm class.
4.255 + ///
4.256 + /// And look at the code:
4.257 + ///
4.258 + ///\code
4.259 + /// bool stronglyConnected(const Digraph& digraph) {
4.260 + /// if (NodeIt(digraph) == INVALID) return true;
4.261 + /// Dfs<Digraph> dfs(digraph);
4.262 + /// dfs.run(NodeIt(digraph));
4.263 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
4.264 + /// if (!dfs.reached(it)) {
4.265 + /// return false;
4.266 + /// }
4.267 + /// }
4.268 + /// typedef RevDigraphAdaptor<const Digraph> RDigraph;
4.269 + /// RDigraph rdigraph(digraph);
4.270 + /// DfsVisit<RDigraph> rdfs(rdigraph);
4.271 + /// rdfs.run(NodeIt(digraph));
4.272 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
4.273 + /// if (!rdfs.reached(it)) {
4.274 + /// return false;
4.275 + /// }
4.276 + /// }
4.277 + /// return true;
4.278 + /// }
4.279 + ///\endcode
4.280 + template<typename _Digraph>
4.281 + class RevDigraphAdaptor :
4.282 + public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
4.283 + public:
4.284 + typedef _Digraph Digraph;
4.285 + typedef DigraphAdaptorExtender<
4.286 + RevDigraphAdaptorBase<_Digraph> > Parent;
4.287 + protected:
4.288 + RevDigraphAdaptor() { }
4.289 + public:
4.290 + explicit RevDigraphAdaptor(Digraph& digraph) {
4.291 + Parent::setDigraph(digraph);
4.292 + }
4.293 + };
4.294 +
4.295 + /// \brief Just gives back a reverse digraph adaptor
4.296 + ///
4.297 + /// Just gives back a reverse digraph adaptor
4.298 + template<typename Digraph>
4.299 + RevDigraphAdaptor<const Digraph>
4.300 + revDigraphAdaptor(const Digraph& digraph) {
4.301 + return RevDigraphAdaptor<const Digraph>(digraph);
4.302 + }
4.303 +
4.304 + template <typename _Digraph, typename _NodeFilterMap,
4.305 + typename _ArcFilterMap, bool checked = true>
4.306 + class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
4.307 + public:
4.308 + typedef _Digraph Digraph;
4.309 + typedef _NodeFilterMap NodeFilterMap;
4.310 + typedef _ArcFilterMap ArcFilterMap;
4.311 +
4.312 + typedef SubDigraphAdaptorBase Adaptor;
4.313 + typedef DigraphAdaptorBase<_Digraph> Parent;
4.314 + protected:
4.315 + NodeFilterMap* _node_filter;
4.316 + ArcFilterMap* _arc_filter;
4.317 + SubDigraphAdaptorBase()
4.318 + : Parent(), _node_filter(0), _arc_filter(0) { }
4.319 +
4.320 + void setNodeFilterMap(NodeFilterMap& node_filter) {
4.321 + _node_filter = &node_filter;
4.322 + }
4.323 + void setArcFilterMap(ArcFilterMap& arc_filter) {
4.324 + _arc_filter = &arc_filter;
4.325 + }
4.326 +
4.327 + public:
4.328 +
4.329 + typedef typename Parent::Node Node;
4.330 + typedef typename Parent::Arc Arc;
4.331 +
4.332 + void first(Node& i) const {
4.333 + Parent::first(i);
4.334 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
4.335 + }
4.336 +
4.337 + void first(Arc& i) const {
4.338 + Parent::first(i);
4.339 + while (i != INVALID && (!(*_arc_filter)[i]
4.340 + || !(*_node_filter)[Parent::source(i)]
4.341 + || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
4.342 + }
4.343 +
4.344 + void firstIn(Arc& i, const Node& n) const {
4.345 + Parent::firstIn(i, n);
4.346 + while (i != INVALID && (!(*_arc_filter)[i]
4.347 + || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
4.348 + }
4.349 +
4.350 + void firstOut(Arc& i, const Node& n) const {
4.351 + Parent::firstOut(i, n);
4.352 + while (i != INVALID && (!(*_arc_filter)[i]
4.353 + || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
4.354 + }
4.355 +
4.356 + void next(Node& i) const {
4.357 + Parent::next(i);
4.358 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
4.359 + }
4.360 +
4.361 + void next(Arc& i) const {
4.362 + Parent::next(i);
4.363 + while (i != INVALID && (!(*_arc_filter)[i]
4.364 + || !(*_node_filter)[Parent::source(i)]
4.365 + || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
4.366 + }
4.367 +
4.368 + void nextIn(Arc& i) const {
4.369 + Parent::nextIn(i);
4.370 + while (i != INVALID && (!(*_arc_filter)[i]
4.371 + || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
4.372 + }
4.373 +
4.374 + void nextOut(Arc& i) const {
4.375 + Parent::nextOut(i);
4.376 + while (i != INVALID && (!(*_arc_filter)[i]
4.377 + || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
4.378 + }
4.379 +
4.380 + ///\e
4.381 +
4.382 + /// This function hides \c n in the digraph, i.e. the iteration
4.383 + /// jumps over it. This is done by simply setting the value of \c n
4.384 + /// to be false in the corresponding node-map.
4.385 + void hide(const Node& n) const { _node_filter->set(n, false); }
4.386 +
4.387 + ///\e
4.388 +
4.389 + /// This function hides \c a in the digraph, i.e. the iteration
4.390 + /// jumps over it. This is done by simply setting the value of \c a
4.391 + /// to be false in the corresponding arc-map.
4.392 + void hide(const Arc& a) const { _arc_filter->set(a, false); }
4.393 +
4.394 + ///\e
4.395 +
4.396 + /// The value of \c n is set to be true in the node-map which stores
4.397 + /// hide information. If \c n was hidden previuosly, then it is shown
4.398 + /// again
4.399 + void unHide(const Node& n) const { _node_filter->set(n, true); }
4.400 +
4.401 + ///\e
4.402 +
4.403 + /// The value of \c a is set to be true in the arc-map which stores
4.404 + /// hide information. If \c a was hidden previuosly, then it is shown
4.405 + /// again
4.406 + void unHide(const Arc& a) const { _arc_filter->set(a, true); }
4.407 +
4.408 + /// Returns true if \c n is hidden.
4.409 +
4.410 + ///\e
4.411 + ///
4.412 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
4.413 +
4.414 + /// Returns true if \c a is hidden.
4.415 +
4.416 + ///\e
4.417 + ///
4.418 + bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
4.419 +
4.420 + typedef False NodeNumTag;
4.421 + typedef False EdgeNumTag;
4.422 +
4.423 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
4.424 + Arc findArc(const Node& source, const Node& target,
4.425 + const Arc& prev = INVALID) {
4.426 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
4.427 + return INVALID;
4.428 + }
4.429 + Arc arc = Parent::findArc(source, target, prev);
4.430 + while (arc != INVALID && !(*_arc_filter)[arc]) {
4.431 + arc = Parent::findArc(source, target, arc);
4.432 + }
4.433 + return arc;
4.434 + }
4.435 +
4.436 + template <typename _Value>
4.437 + class NodeMap : public SubMapExtender<Adaptor,
4.438 + typename Parent::template NodeMap<_Value> > {
4.439 + public:
4.440 + typedef _Value Value;
4.441 + typedef SubMapExtender<Adaptor, typename Parent::
4.442 + template NodeMap<Value> > MapParent;
4.443 +
4.444 + NodeMap(const Adaptor& adaptor)
4.445 + : MapParent(adaptor) {}
4.446 + NodeMap(const Adaptor& adaptor, const Value& value)
4.447 + : MapParent(adaptor, value) {}
4.448 +
4.449 + private:
4.450 + NodeMap& operator=(const NodeMap& cmap) {
4.451 + return operator=<NodeMap>(cmap);
4.452 + }
4.453 +
4.454 + template <typename CMap>
4.455 + NodeMap& operator=(const CMap& cmap) {
4.456 + MapParent::operator=(cmap);
4.457 + return *this;
4.458 + }
4.459 + };
4.460 +
4.461 + template <typename _Value>
4.462 + class ArcMap : public SubMapExtender<Adaptor,
4.463 + typename Parent::template ArcMap<_Value> > {
4.464 + public:
4.465 + typedef _Value Value;
4.466 + typedef SubMapExtender<Adaptor, typename Parent::
4.467 + template ArcMap<Value> > MapParent;
4.468 +
4.469 + ArcMap(const Adaptor& adaptor)
4.470 + : MapParent(adaptor) {}
4.471 + ArcMap(const Adaptor& adaptor, const Value& value)
4.472 + : MapParent(adaptor, value) {}
4.473 +
4.474 + private:
4.475 + ArcMap& operator=(const ArcMap& cmap) {
4.476 + return operator=<ArcMap>(cmap);
4.477 + }
4.478 +
4.479 + template <typename CMap>
4.480 + ArcMap& operator=(const CMap& cmap) {
4.481 + MapParent::operator=(cmap);
4.482 + return *this;
4.483 + }
4.484 + };
4.485 +
4.486 + };
4.487 +
4.488 + template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
4.489 + class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
4.490 + : public DigraphAdaptorBase<_Digraph> {
4.491 + public:
4.492 + typedef _Digraph Digraph;
4.493 + typedef _NodeFilterMap NodeFilterMap;
4.494 + typedef _ArcFilterMap ArcFilterMap;
4.495 +
4.496 + typedef SubDigraphAdaptorBase Adaptor;
4.497 + typedef DigraphAdaptorBase<Digraph> Parent;
4.498 + protected:
4.499 + NodeFilterMap* _node_filter;
4.500 + ArcFilterMap* _arc_filter;
4.501 + SubDigraphAdaptorBase()
4.502 + : Parent(), _node_filter(0), _arc_filter(0) { }
4.503 +
4.504 + void setNodeFilterMap(NodeFilterMap& node_filter) {
4.505 + _node_filter = &node_filter;
4.506 + }
4.507 + void setArcFilterMap(ArcFilterMap& arc_filter) {
4.508 + _arc_filter = &arc_filter;
4.509 + }
4.510 +
4.511 + public:
4.512 +
4.513 + typedef typename Parent::Node Node;
4.514 + typedef typename Parent::Arc Arc;
4.515 +
4.516 + void first(Node& i) const {
4.517 + Parent::first(i);
4.518 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
4.519 + }
4.520 +
4.521 + void first(Arc& i) const {
4.522 + Parent::first(i);
4.523 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
4.524 + }
4.525 +
4.526 + void firstIn(Arc& i, const Node& n) const {
4.527 + Parent::firstIn(i, n);
4.528 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
4.529 + }
4.530 +
4.531 + void firstOut(Arc& i, const Node& n) const {
4.532 + Parent::firstOut(i, n);
4.533 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
4.534 + }
4.535 +
4.536 + void next(Node& i) const {
4.537 + Parent::next(i);
4.538 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
4.539 + }
4.540 + void next(Arc& i) const {
4.541 + Parent::next(i);
4.542 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
4.543 + }
4.544 + void nextIn(Arc& i) const {
4.545 + Parent::nextIn(i);
4.546 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
4.547 + }
4.548 +
4.549 + void nextOut(Arc& i) const {
4.550 + Parent::nextOut(i);
4.551 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
4.552 + }
4.553 +
4.554 + ///\e
4.555 +
4.556 + /// This function hides \c n in the digraph, i.e. the iteration
4.557 + /// jumps over it. This is done by simply setting the value of \c n
4.558 + /// to be false in the corresponding node-map.
4.559 + void hide(const Node& n) const { _node_filter->set(n, false); }
4.560 +
4.561 + ///\e
4.562 +
4.563 + /// This function hides \c e in the digraph, i.e. the iteration
4.564 + /// jumps over it. This is done by simply setting the value of \c e
4.565 + /// to be false in the corresponding arc-map.
4.566 + void hide(const Arc& e) const { _arc_filter->set(e, false); }
4.567 +
4.568 + ///\e
4.569 +
4.570 + /// The value of \c n is set to be true in the node-map which stores
4.571 + /// hide information. If \c n was hidden previuosly, then it is shown
4.572 + /// again
4.573 + void unHide(const Node& n) const { _node_filter->set(n, true); }
4.574 +
4.575 + ///\e
4.576 +
4.577 + /// The value of \c e is set to be true in the arc-map which stores
4.578 + /// hide information. If \c e was hidden previuosly, then it is shown
4.579 + /// again
4.580 + void unHide(const Arc& e) const { _arc_filter->set(e, true); }
4.581 +
4.582 + /// Returns true if \c n is hidden.
4.583 +
4.584 + ///\e
4.585 + ///
4.586 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
4.587 +
4.588 + /// Returns true if \c n is hidden.
4.589 +
4.590 + ///\e
4.591 + ///
4.592 + bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
4.593 +
4.594 + typedef False NodeNumTag;
4.595 + typedef False EdgeNumTag;
4.596 +
4.597 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
4.598 + Arc findArc(const Node& source, const Node& target,
4.599 + const Arc& prev = INVALID) {
4.600 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
4.601 + return INVALID;
4.602 + }
4.603 + Arc arc = Parent::findArc(source, target, prev);
4.604 + while (arc != INVALID && !(*_arc_filter)[arc]) {
4.605 + arc = Parent::findArc(source, target, arc);
4.606 + }
4.607 + return arc;
4.608 + }
4.609 +
4.610 + template <typename _Value>
4.611 + class NodeMap : public SubMapExtender<Adaptor,
4.612 + typename Parent::template NodeMap<_Value> > {
4.613 + public:
4.614 + typedef _Value Value;
4.615 + typedef SubMapExtender<Adaptor, typename Parent::
4.616 + template NodeMap<Value> > MapParent;
4.617 +
4.618 + NodeMap(const Adaptor& adaptor)
4.619 + : MapParent(adaptor) {}
4.620 + NodeMap(const Adaptor& adaptor, const Value& value)
4.621 + : MapParent(adaptor, value) {}
4.622 +
4.623 + private:
4.624 + NodeMap& operator=(const NodeMap& cmap) {
4.625 + return operator=<NodeMap>(cmap);
4.626 + }
4.627 +
4.628 + template <typename CMap>
4.629 + NodeMap& operator=(const CMap& cmap) {
4.630 + MapParent::operator=(cmap);
4.631 + return *this;
4.632 + }
4.633 + };
4.634 +
4.635 + template <typename _Value>
4.636 + class ArcMap : public SubMapExtender<Adaptor,
4.637 + typename Parent::template ArcMap<_Value> > {
4.638 + public:
4.639 + typedef _Value Value;
4.640 + typedef SubMapExtender<Adaptor, typename Parent::
4.641 + template ArcMap<Value> > MapParent;
4.642 +
4.643 + ArcMap(const Adaptor& adaptor)
4.644 + : MapParent(adaptor) {}
4.645 + ArcMap(const Adaptor& adaptor, const Value& value)
4.646 + : MapParent(adaptor, value) {}
4.647 +
4.648 + private:
4.649 + ArcMap& operator=(const ArcMap& cmap) {
4.650 + return operator=<ArcMap>(cmap);
4.651 + }
4.652 +
4.653 + template <typename CMap>
4.654 + ArcMap& operator=(const CMap& cmap) {
4.655 + MapParent::operator=(cmap);
4.656 + return *this;
4.657 + }
4.658 + };
4.659 +
4.660 + };
4.661 +
4.662 + /// \ingroup graph_adaptors
4.663 + ///
4.664 + /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
4.665 + ///
4.666 + /// SubDigraphAdaptor shows the digraph with filtered node-set and
4.667 + /// arc-set. If the \c checked parameter is true then it filters the arcset
4.668 + /// to do not get invalid arcs without source or target.
4.669 + /// Let \f$ G=(V, A) \f$ be a directed digraph
4.670 + /// and suppose that the digraph instance \c g of type ListDigraph
4.671 + /// implements \f$ G \f$.
4.672 + /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
4.673 + /// on the node-set and arc-set.
4.674 + /// SubDigraphAdaptor<...>::NodeIt iterates
4.675 + /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
4.676 + /// SubDigraphAdaptor<...>::ArcIt iterates
4.677 + /// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
4.678 + /// SubDigraphAdaptor<...>::OutArcIt and
4.679 + /// SubDigraphAdaptor<...>::InArcIt iterates
4.680 + /// only on arcs leaving and entering a specific node which have true value.
4.681 + ///
4.682 + /// If the \c checked template parameter is false then we have to
4.683 + /// note that the node-iterator cares only the filter on the
4.684 + /// node-set, and the arc-iterator cares only the filter on the
4.685 + /// arc-set. This way the arc-map should filter all arcs which's
4.686 + /// source or target is filtered by the node-filter.
4.687 + ///\code
4.688 + /// typedef ListDigraph Digraph;
4.689 + /// DIGRAPH_TYPEDEFS(Digraph);
4.690 + /// Digraph g;
4.691 + /// Node u=g.addNode(); //node of id 0
4.692 + /// Node v=g.addNode(); //node of id 1
4.693 + /// Arc a=g.addArc(u, v); //arc of id 0
4.694 + /// Arc f=g.addArc(v, u); //arc of id 1
4.695 + /// BoolNodeMap nm(g, true);
4.696 + /// nm.set(u, false);
4.697 + /// BoolArcMap am(g, true);
4.698 + /// am.set(a, false);
4.699 + /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubGA;
4.700 + /// SubGA ga(g, nm, am);
4.701 + /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)
4.702 + /// std::cout << g.id(n) << std::endl;
4.703 + /// std::cout << ":-)" << std::endl;
4.704 + /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a)
4.705 + /// std::cout << g.id(a) << std::endl;
4.706 + ///\endcode
4.707 + /// The output of the above code is the following.
4.708 + ///\code
4.709 + /// 1
4.710 + /// :-)
4.711 + /// 1
4.712 + ///\endcode
4.713 + /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
4.714 + /// \c Digraph::Node that is why \c g.id(n) can be applied.
4.715 + ///
4.716 + /// For other examples see also the documentation of
4.717 + /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
4.718 + template<typename _Digraph,
4.719 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
4.720 + typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
4.721 + bool checked = true>
4.722 + class SubDigraphAdaptor :
4.723 + public DigraphAdaptorExtender<
4.724 + SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {
4.725 + public:
4.726 + typedef _Digraph Digraph;
4.727 + typedef _NodeFilterMap NodeFilterMap;
4.728 + typedef _ArcFilterMap ArcFilterMap;
4.729 +
4.730 + typedef DigraphAdaptorExtender<
4.731 + SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
4.732 + Parent;
4.733 +
4.734 + protected:
4.735 + SubDigraphAdaptor() { }
4.736 + public:
4.737 +
4.738 + SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
4.739 + ArcFilterMap& arc_filter) {
4.740 + setDigraph(digraph);
4.741 + setNodeFilterMap(node_filter);
4.742 + setArcFilterMap(arc_filter);
4.743 + }
4.744 +
4.745 + };
4.746 +
4.747 + /// \brief Just gives back a sub digraph adaptor
4.748 + ///
4.749 + /// Just gives back a sub digraph adaptor
4.750 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
4.751 + SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
4.752 + subDigraphAdaptor(const Digraph& digraph,
4.753 + NodeFilterMap& nfm, ArcFilterMap& afm) {
4.754 + return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
4.755 + (digraph, nfm, afm);
4.756 + }
4.757 +
4.758 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
4.759 + SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
4.760 + subDigraphAdaptor(const Digraph& digraph,
4.761 + NodeFilterMap& nfm, ArcFilterMap& afm) {
4.762 + return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
4.763 + (digraph, nfm, afm);
4.764 + }
4.765 +
4.766 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
4.767 + SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
4.768 + subDigraphAdaptor(const Digraph& digraph,
4.769 + NodeFilterMap& nfm, ArcFilterMap& afm) {
4.770 + return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
4.771 + (digraph, nfm, afm);
4.772 + }
4.773 +
4.774 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
4.775 + SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
4.776 + subDigraphAdaptor(const Digraph& digraph,
4.777 + NodeFilterMap& nfm, ArcFilterMap& afm) {
4.778 + return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
4.779 + const ArcFilterMap>(digraph, nfm, afm);
4.780 + }
4.781 +
4.782 +
4.783 +
4.784 + ///\ingroup graph_adaptors
4.785 + ///
4.786 + ///\brief An adaptor for hiding nodes from a digraph.
4.787 + ///
4.788 + ///An adaptor for hiding nodes from a digraph. This adaptor
4.789 + ///specializes SubDigraphAdaptor in the way that only the node-set
4.790 + ///can be filtered. In usual case the checked parameter is true, we
4.791 + ///get the induced subgraph. But if the checked parameter is false
4.792 + ///then we can filter only isolated nodes.
4.793 + template<typename _Digraph,
4.794 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
4.795 + bool checked = true>
4.796 + class NodeSubDigraphAdaptor :
4.797 + public SubDigraphAdaptor<_Digraph, _NodeFilterMap,
4.798 + ConstMap<typename _Digraph::Arc, bool>, checked> {
4.799 + public:
4.800 +
4.801 + typedef _Digraph Digraph;
4.802 + typedef _NodeFilterMap NodeFilterMap;
4.803 +
4.804 + typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
4.805 + ConstMap<typename Digraph::Arc, bool>, checked>
4.806 + Parent;
4.807 +
4.808 + protected:
4.809 + ConstMap<typename Digraph::Arc, bool> const_true_map;
4.810 +
4.811 + NodeSubDigraphAdaptor() : const_true_map(true) {
4.812 + Parent::setArcFilterMap(const_true_map);
4.813 + }
4.814 +
4.815 + public:
4.816 +
4.817 + NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
4.818 + Parent(), const_true_map(true) {
4.819 + Parent::setDigraph(_digraph);
4.820 + Parent::setNodeFilterMap(node_filter);
4.821 + Parent::setArcFilterMap(const_true_map);
4.822 + }
4.823 +
4.824 + };
4.825 +
4.826 +
4.827 + /// \brief Just gives back a \c NodeSubDigraphAdaptor
4.828 + ///
4.829 + /// Just gives back a \c NodeSubDigraphAdaptor
4.830 + template<typename Digraph, typename NodeFilterMap>
4.831 + NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
4.832 + nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
4.833 + return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
4.834 + }
4.835 +
4.836 + template<typename Digraph, typename NodeFilterMap>
4.837 + NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
4.838 + nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
4.839 + return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
4.840 + (digraph, nfm);
4.841 + }
4.842 +
4.843 + ///\ingroup graph_adaptors
4.844 + ///
4.845 + ///\brief An adaptor for hiding arcs from a digraph.
4.846 + ///
4.847 + ///An adaptor for hiding arcs from a digraph. This adaptor
4.848 + ///specializes SubDigraphAdaptor in the way that only the arc-set
4.849 + ///can be filtered. The usefulness of this adaptor is demonstrated
4.850 + ///in the problem of searching a maximum number of arc-disjoint
4.851 + ///shortest paths between two nodes \c s and \c t. Shortest here
4.852 + ///means being shortest w.r.t. non-negative arc-lengths. Note that
4.853 + ///the comprehension of the presented solution need's some
4.854 + ///elementary knowlarc from combinatorial optimization.
4.855 + ///
4.856 + ///If a single shortest path is to be searched between \c s and \c
4.857 + ///t, then this can be done easily by applying the Dijkstra
4.858 + ///algorithm. What happens, if a maximum number of arc-disjoint
4.859 + ///shortest paths is to be computed. It can be proved that an arc
4.860 + ///can be in a shortest path if and only if it is tight with respect
4.861 + ///to the potential function computed by Dijkstra. Moreover, any
4.862 + ///path containing only such arcs is a shortest one. Thus we have
4.863 + ///to compute a maximum number of arc-disjoint paths between \c s
4.864 + ///and \c t in the digraph which has arc-set all the tight arcs. The
4.865 + ///computation will be demonstrated on the following digraph, which
4.866 + ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.
4.867 + ///The full source code is available in \ref
4.868 + ///sub_digraph_adaptor_demo.cc. If you are interested in more demo
4.869 + ///programs, you can use \ref dim_to_dot.cc to generate .dot files
4.870 + ///from dimacs files. The .dot file of the following figure was
4.871 + ///generated by the demo program \ref dim_to_dot.cc.
4.872 + ///
4.873 + ///\dot
4.874 + ///didigraph lemon_dot_example {
4.875 + ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
4.876 + ///n0 [ label="0 (s)" ];
4.877 + ///n1 [ label="1" ];
4.878 + ///n2 [ label="2" ];
4.879 + ///n3 [ label="3" ];
4.880 + ///n4 [ label="4" ];
4.881 + ///n5 [ label="5" ];
4.882 + ///n6 [ label="6 (t)" ];
4.883 + ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
4.884 + ///n5 -> n6 [ label="9, length:4" ];
4.885 + ///n4 -> n6 [ label="8, length:2" ];
4.886 + ///n3 -> n5 [ label="7, length:1" ];
4.887 + ///n2 -> n5 [ label="6, length:3" ];
4.888 + ///n2 -> n6 [ label="5, length:5" ];
4.889 + ///n2 -> n4 [ label="4, length:2" ];
4.890 + ///n1 -> n4 [ label="3, length:3" ];
4.891 + ///n0 -> n3 [ label="2, length:1" ];
4.892 + ///n0 -> n2 [ label="1, length:2" ];
4.893 + ///n0 -> n1 [ label="0, length:3" ];
4.894 + ///}
4.895 + ///\enddot
4.896 + ///
4.897 + ///\code
4.898 + ///Digraph g;
4.899 + ///Node s, t;
4.900 + ///LengthMap length(g);
4.901 + ///
4.902 + ///readDimacs(std::cin, g, length, s, t);
4.903 + ///
4.904 + ///cout << "arcs with lengths (of form id, source--length->target): " << endl;
4.905 + ///for(ArcIt e(g); e!=INVALID; ++e)
4.906 + /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
4.907 + /// << length[e] << "->" << g.id(g.target(e)) << endl;
4.908 + ///
4.909 + ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
4.910 + ///\endcode
4.911 + ///Next, the potential function is computed with Dijkstra.
4.912 + ///\code
4.913 + ///typedef Dijkstra<Digraph, LengthMap> Dijkstra;
4.914 + ///Dijkstra dijkstra(g, length);
4.915 + ///dijkstra.run(s);
4.916 + ///\endcode
4.917 + ///Next, we consrtruct a map which filters the arc-set to the tight arcs.
4.918 + ///\code
4.919 + ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap>
4.920 + /// TightArcFilter;
4.921 + ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length);
4.922 + ///
4.923 + ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA;
4.924 + ///SubGA ga(g, tight_arc_filter);
4.925 + ///\endcode
4.926 + ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed
4.927 + ///with a max flow algorithm Preflow.
4.928 + ///\code
4.929 + ///ConstMap<Arc, int> const_1_map(1);
4.930 + ///Digraph::ArcMap<int> flow(g, 0);
4.931 + ///
4.932 + ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> >
4.933 + /// preflow(ga, const_1_map, s, t);
4.934 + ///preflow.run();
4.935 + ///\endcode
4.936 + ///Last, the output is:
4.937 + ///\code
4.938 + ///cout << "maximum number of arc-disjoint shortest path: "
4.939 + /// << preflow.flowValue() << endl;
4.940 + ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: "
4.941 + /// << endl;
4.942 + ///for(ArcIt e(g); e!=INVALID; ++e)
4.943 + /// if (preflow.flow(e))
4.944 + /// cout << " " << g.id(g.source(e)) << "--"
4.945 + /// << length[e] << "->" << g.id(g.target(e)) << endl;
4.946 + ///\endcode
4.947 + ///The program has the following (expected :-)) output:
4.948 + ///\code
4.949 + ///arcs with lengths (of form id, source--length->target):
4.950 + /// 9, 5--4->6
4.951 + /// 8, 4--2->6
4.952 + /// 7, 3--1->5
4.953 + /// 6, 2--3->5
4.954 + /// 5, 2--5->6
4.955 + /// 4, 2--2->4
4.956 + /// 3, 1--3->4
4.957 + /// 2, 0--1->3
4.958 + /// 1, 0--2->2
4.959 + /// 0, 0--3->1
4.960 + ///s: 0 t: 6
4.961 + ///maximum number of arc-disjoint shortest path: 2
4.962 + ///arcs of the maximum number of arc-disjoint shortest s-t paths:
4.963 + /// 9, 5--4->6
4.964 + /// 8, 4--2->6
4.965 + /// 7, 3--1->5
4.966 + /// 4, 2--2->4
4.967 + /// 2, 0--1->3
4.968 + /// 1, 0--2->2
4.969 + ///\endcode
4.970 + template<typename _Digraph, typename _ArcFilterMap>
4.971 + class ArcSubDigraphAdaptor :
4.972 + public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
4.973 + _ArcFilterMap, false> {
4.974 + public:
4.975 + typedef _Digraph Digraph;
4.976 + typedef _ArcFilterMap ArcFilterMap;
4.977 +
4.978 + typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
4.979 + ArcFilterMap, false> Parent;
4.980 + protected:
4.981 + ConstMap<typename Digraph::Node, bool> const_true_map;
4.982 +
4.983 + ArcSubDigraphAdaptor() : const_true_map(true) {
4.984 + Parent::setNodeFilterMap(const_true_map);
4.985 + }
4.986 +
4.987 + public:
4.988 +
4.989 + ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
4.990 + : Parent(), const_true_map(true) {
4.991 + Parent::setDigraph(digraph);
4.992 + Parent::setNodeFilterMap(const_true_map);
4.993 + Parent::setArcFilterMap(arc_filter);
4.994 + }
4.995 +
4.996 + };
4.997 +
4.998 + /// \brief Just gives back an arc sub digraph adaptor
4.999 + ///
4.1000 + /// Just gives back an arc sub digraph adaptor
4.1001 + template<typename Digraph, typename ArcFilterMap>
4.1002 + ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
4.1003 + arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
4.1004 + return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
4.1005 + }
4.1006 +
4.1007 + template<typename Digraph, typename ArcFilterMap>
4.1008 + ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
4.1009 + arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
4.1010 + return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
4.1011 + (digraph, afm);
4.1012 + }
4.1013 +
4.1014 + template <typename _Digraph>
4.1015 + class UndirDigraphAdaptorBase {
4.1016 + public:
4.1017 + typedef _Digraph Digraph;
4.1018 + typedef UndirDigraphAdaptorBase Adaptor;
4.1019 +
4.1020 + typedef True UndirectedTag;
4.1021 +
4.1022 + typedef typename Digraph::Arc Edge;
4.1023 + typedef typename Digraph::Node Node;
4.1024 +
4.1025 + class Arc : public Edge {
4.1026 + friend class UndirDigraphAdaptorBase;
4.1027 + protected:
4.1028 + bool _forward;
4.1029 +
4.1030 + Arc(const Edge& edge, bool forward) :
4.1031 + Edge(edge), _forward(forward) {}
4.1032 +
4.1033 + public:
4.1034 + Arc() {}
4.1035 +
4.1036 + Arc(Invalid) : Edge(INVALID), _forward(true) {}
4.1037 +
4.1038 + bool operator==(const Arc &other) const {
4.1039 + return _forward == other._forward &&
4.1040 + static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
4.1041 + }
4.1042 + bool operator!=(const Arc &other) const {
4.1043 + return _forward != other._forward ||
4.1044 + static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
4.1045 + }
4.1046 + bool operator<(const Arc &other) const {
4.1047 + return _forward < other._forward ||
4.1048 + (_forward == other._forward &&
4.1049 + static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
4.1050 + }
4.1051 + };
4.1052 +
4.1053 +
4.1054 +
4.1055 + void first(Node& n) const {
4.1056 + _digraph->first(n);
4.1057 + }
4.1058 +
4.1059 + void next(Node& n) const {
4.1060 + _digraph->next(n);
4.1061 + }
4.1062 +
4.1063 + void first(Arc& a) const {
4.1064 + _digraph->first(a);
4.1065 + a._forward = true;
4.1066 + }
4.1067 +
4.1068 + void next(Arc& a) const {
4.1069 + if (a._forward) {
4.1070 + a._forward = false;
4.1071 + } else {
4.1072 + _digraph->next(a);
4.1073 + a._forward = true;
4.1074 + }
4.1075 + }
4.1076 +
4.1077 + void first(Edge& e) const {
4.1078 + _digraph->first(e);
4.1079 + }
4.1080 +
4.1081 + void next(Edge& e) const {
4.1082 + _digraph->next(e);
4.1083 + }
4.1084 +
4.1085 + void firstOut(Arc& a, const Node& n) const {
4.1086 + _digraph->firstIn(a, n);
4.1087 + if( static_cast<const Edge&>(a) != INVALID ) {
4.1088 + a._forward = false;
4.1089 + } else {
4.1090 + _digraph->firstOut(a, n);
4.1091 + a._forward = true;
4.1092 + }
4.1093 + }
4.1094 + void nextOut(Arc &a) const {
4.1095 + if (!a._forward) {
4.1096 + Node n = _digraph->target(a);
4.1097 + _digraph->nextIn(a);
4.1098 + if (static_cast<const Edge&>(a) == INVALID ) {
4.1099 + _digraph->firstOut(a, n);
4.1100 + a._forward = true;
4.1101 + }
4.1102 + }
4.1103 + else {
4.1104 + _digraph->nextOut(a);
4.1105 + }
4.1106 + }
4.1107 +
4.1108 + void firstIn(Arc &a, const Node &n) const {
4.1109 + _digraph->firstOut(a, n);
4.1110 + if (static_cast<const Edge&>(a) != INVALID ) {
4.1111 + a._forward = false;
4.1112 + } else {
4.1113 + _digraph->firstIn(a, n);
4.1114 + a._forward = true;
4.1115 + }
4.1116 + }
4.1117 + void nextIn(Arc &a) const {
4.1118 + if (!a._forward) {
4.1119 + Node n = _digraph->source(a);
4.1120 + _digraph->nextOut(a);
4.1121 + if( static_cast<const Edge&>(a) == INVALID ) {
4.1122 + _digraph->firstIn(a, n);
4.1123 + a._forward = true;
4.1124 + }
4.1125 + }
4.1126 + else {
4.1127 + _digraph->nextIn(a);
4.1128 + }
4.1129 + }
4.1130 +
4.1131 + void firstInc(Edge &e, bool &d, const Node &n) const {
4.1132 + d = true;
4.1133 + _digraph->firstOut(e, n);
4.1134 + if (e != INVALID) return;
4.1135 + d = false;
4.1136 + _digraph->firstIn(e, n);
4.1137 + }
4.1138 +
4.1139 + void nextInc(Edge &e, bool &d) const {
4.1140 + if (d) {
4.1141 + Node s = _digraph->source(e);
4.1142 + _digraph->nextOut(e);
4.1143 + if (e != INVALID) return;
4.1144 + d = false;
4.1145 + _digraph->firstIn(e, s);
4.1146 + } else {
4.1147 + _digraph->nextIn(e);
4.1148 + }
4.1149 + }
4.1150 +
4.1151 + Node u(const Edge& e) const {
4.1152 + return _digraph->source(e);
4.1153 + }
4.1154 +
4.1155 + Node v(const Edge& e) const {
4.1156 + return _digraph->target(e);
4.1157 + }
4.1158 +
4.1159 + Node source(const Arc &a) const {
4.1160 + return a._forward ? _digraph->source(a) : _digraph->target(a);
4.1161 + }
4.1162 +
4.1163 + Node target(const Arc &a) const {
4.1164 + return a._forward ? _digraph->target(a) : _digraph->source(a);
4.1165 + }
4.1166 +
4.1167 + static Arc direct(const Edge &e, bool d) {
4.1168 + return Arc(e, d);
4.1169 + }
4.1170 + Arc direct(const Edge &e, const Node& n) const {
4.1171 + return Arc(e, _digraph->source(e) == n);
4.1172 + }
4.1173 +
4.1174 + static bool direction(const Arc &a) { return a._forward; }
4.1175 +
4.1176 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
4.1177 + Arc arcFromId(int ix) const {
4.1178 + return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
4.1179 + }
4.1180 + Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
4.1181 +
4.1182 + int id(const Node &n) const { return _digraph->id(n); }
4.1183 + int id(const Arc &a) const {
4.1184 + return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
4.1185 + }
4.1186 + int id(const Edge &e) const { return _digraph->id(e); }
4.1187 +
4.1188 + int maxNodeId() const { return _digraph->maxNodeId(); }
4.1189 + int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
4.1190 + int maxEdgeId() const { return _digraph->maxArcId(); }
4.1191 +
4.1192 + Node addNode() { return _digraph->addNode(); }
4.1193 + Edge addEdge(const Node& u, const Node& v) {
4.1194 + return _digraph->addArc(u, v);
4.1195 + }
4.1196 +
4.1197 + void erase(const Node& i) { _digraph->erase(i); }
4.1198 + void erase(const Edge& i) { _digraph->erase(i); }
4.1199 +
4.1200 + void clear() { _digraph->clear(); }
4.1201 +
4.1202 + typedef NodeNumTagIndicator<Digraph> NodeNumTag;
4.1203 + int nodeNum() const { return 2 * _digraph->arcNum(); }
4.1204 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
4.1205 + int arcNum() const { return 2 * _digraph->arcNum(); }
4.1206 + int edgeNum() const { return _digraph->arcNum(); }
4.1207 +
4.1208 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
4.1209 + Arc findArc(Node s, Node t, Arc p = INVALID) const {
4.1210 + if (p == INVALID) {
4.1211 + Edge arc = _digraph->findArc(s, t);
4.1212 + if (arc != INVALID) return direct(arc, true);
4.1213 + arc = _digraph->findArc(t, s);
4.1214 + if (arc != INVALID) return direct(arc, false);
4.1215 + } else if (direction(p)) {
4.1216 + Edge arc = _digraph->findArc(s, t, p);
4.1217 + if (arc != INVALID) return direct(arc, true);
4.1218 + arc = _digraph->findArc(t, s);
4.1219 + if (arc != INVALID) return direct(arc, false);
4.1220 + } else {
4.1221 + Edge arc = _digraph->findArc(t, s, p);
4.1222 + if (arc != INVALID) return direct(arc, false);
4.1223 + }
4.1224 + return INVALID;
4.1225 + }
4.1226 +
4.1227 + Edge findEdge(Node s, Node t, Edge p = INVALID) const {
4.1228 + if (s != t) {
4.1229 + if (p == INVALID) {
4.1230 + Edge arc = _digraph->findArc(s, t);
4.1231 + if (arc != INVALID) return arc;
4.1232 + arc = _digraph->findArc(t, s);
4.1233 + if (arc != INVALID) return arc;
4.1234 + } else if (_digraph->s(p) == s) {
4.1235 + Edge arc = _digraph->findArc(s, t, p);
4.1236 + if (arc != INVALID) return arc;
4.1237 + arc = _digraph->findArc(t, s);
4.1238 + if (arc != INVALID) return arc;
4.1239 + } else {
4.1240 + Edge arc = _digraph->findArc(t, s, p);
4.1241 + if (arc != INVALID) return arc;
4.1242 + }
4.1243 + } else {
4.1244 + return _digraph->findArc(s, t, p);
4.1245 + }
4.1246 + return INVALID;
4.1247 + }
4.1248 +
4.1249 + private:
4.1250 +
4.1251 + template <typename _Value>
4.1252 + class ArcMapBase {
4.1253 + private:
4.1254 +
4.1255 + typedef typename Digraph::template ArcMap<_Value> MapImpl;
4.1256 +
4.1257 + public:
4.1258 +
4.1259 + typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
4.1260 +
4.1261 + typedef _Value Value;
4.1262 + typedef Arc Key;
4.1263 +
4.1264 + ArcMapBase(const Adaptor& adaptor) :
4.1265 + _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
4.1266 +
4.1267 + ArcMapBase(const Adaptor& adaptor, const Value& v)
4.1268 + : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
4.1269 +
4.1270 + void set(const Arc& a, const Value& v) {
4.1271 + if (direction(a)) {
4.1272 + _forward.set(a, v);
4.1273 + } else {
4.1274 + _backward.set(a, v);
4.1275 + }
4.1276 + }
4.1277 +
4.1278 + typename MapTraits<MapImpl>::ConstReturnValue
4.1279 + operator[](const Arc& a) const {
4.1280 + if (direction(a)) {
4.1281 + return _forward[a];
4.1282 + } else {
4.1283 + return _backward[a];
4.1284 + }
4.1285 + }
4.1286 +
4.1287 + typename MapTraits<MapImpl>::ReturnValue
4.1288 + operator[](const Arc& a) {
4.1289 + if (direction(a)) {
4.1290 + return _forward[a];
4.1291 + } else {
4.1292 + return _backward[a];
4.1293 + }
4.1294 + }
4.1295 +
4.1296 + protected:
4.1297 +
4.1298 + MapImpl _forward, _backward;
4.1299 +
4.1300 + };
4.1301 +
4.1302 + public:
4.1303 +
4.1304 + template <typename _Value>
4.1305 + class NodeMap : public Digraph::template NodeMap<_Value> {
4.1306 + public:
4.1307 +
4.1308 + typedef _Value Value;
4.1309 + typedef typename Digraph::template NodeMap<Value> Parent;
4.1310 +
4.1311 + explicit NodeMap(const Adaptor& adaptor)
4.1312 + : Parent(*adaptor._digraph) {}
4.1313 +
4.1314 + NodeMap(const Adaptor& adaptor, const _Value& value)
4.1315 + : Parent(*adaptor._digraph, value) { }
4.1316 +
4.1317 + private:
4.1318 + NodeMap& operator=(const NodeMap& cmap) {
4.1319 + return operator=<NodeMap>(cmap);
4.1320 + }
4.1321 +
4.1322 + template <typename CMap>
4.1323 + NodeMap& operator=(const CMap& cmap) {
4.1324 + Parent::operator=(cmap);
4.1325 + return *this;
4.1326 + }
4.1327 +
4.1328 + };
4.1329 +
4.1330 + template <typename _Value>
4.1331 + class ArcMap
4.1332 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
4.1333 + {
4.1334 + public:
4.1335 + typedef _Value Value;
4.1336 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
4.1337 +
4.1338 + ArcMap(const Adaptor& adaptor)
4.1339 + : Parent(adaptor) {}
4.1340 +
4.1341 + ArcMap(const Adaptor& adaptor, const Value& value)
4.1342 + : Parent(adaptor, value) {}
4.1343 +
4.1344 + private:
4.1345 + ArcMap& operator=(const ArcMap& cmap) {
4.1346 + return operator=<ArcMap>(cmap);
4.1347 + }
4.1348 +
4.1349 + template <typename CMap>
4.1350 + ArcMap& operator=(const CMap& cmap) {
4.1351 + Parent::operator=(cmap);
4.1352 + return *this;
4.1353 + }
4.1354 + };
4.1355 +
4.1356 + template <typename _Value>
4.1357 + class EdgeMap : public Digraph::template ArcMap<_Value> {
4.1358 + public:
4.1359 +
4.1360 + typedef _Value Value;
4.1361 + typedef typename Digraph::template ArcMap<Value> Parent;
4.1362 +
4.1363 + explicit EdgeMap(const Adaptor& adaptor)
4.1364 + : Parent(*adaptor._digraph) {}
4.1365 +
4.1366 + EdgeMap(const Adaptor& adaptor, const Value& value)
4.1367 + : Parent(*adaptor._digraph, value) {}
4.1368 +
4.1369 + private:
4.1370 + EdgeMap& operator=(const EdgeMap& cmap) {
4.1371 + return operator=<EdgeMap>(cmap);
4.1372 + }
4.1373 +
4.1374 + template <typename CMap>
4.1375 + EdgeMap& operator=(const CMap& cmap) {
4.1376 + Parent::operator=(cmap);
4.1377 + return *this;
4.1378 + }
4.1379 +
4.1380 + };
4.1381 +
4.1382 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
4.1383 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
4.1384 +
4.1385 + protected:
4.1386 +
4.1387 + UndirDigraphAdaptorBase() : _digraph(0) {}
4.1388 +
4.1389 + Digraph* _digraph;
4.1390 +
4.1391 + void setDigraph(Digraph& digraph) {
4.1392 + _digraph = &digraph;
4.1393 + }
4.1394 +
4.1395 + };
4.1396 +
4.1397 + ///\ingroup graph_adaptors
4.1398 + ///
4.1399 + /// \brief An graph is made from a directed digraph by an adaptor
4.1400 + ///
4.1401 + /// This adaptor makes an undirected graph from a directed
4.1402 + /// digraph. All arc of the underlying will be showed in the adaptor
4.1403 + /// as an edge. Let's see an informal example about using
4.1404 + /// this adaptor:
4.1405 + ///
4.1406 + /// There is a network of the streets of a town. Of course there are
4.1407 + /// some one-way street in the town hence the network is a directed
4.1408 + /// one. There is a crazy driver who go oppositely in the one-way
4.1409 + /// street without moral sense. Of course he can pass this streets
4.1410 + /// slower than the regular way, in fact his speed is half of the
4.1411 + /// normal speed. How long should he drive to get from a source
4.1412 + /// point to the target? Let see the example code which calculate it:
4.1413 + ///
4.1414 + /// \todo BadCode, SimpleMap does no exists
4.1415 + ///\code
4.1416 + /// typedef UndirDigraphAdaptor<Digraph> Graph;
4.1417 + /// Graph graph(digraph);
4.1418 + ///
4.1419 + /// typedef SimpleMap<LengthMap> FLengthMap;
4.1420 + /// FLengthMap flength(length);
4.1421 + ///
4.1422 + /// typedef ScaleMap<LengthMap> RLengthMap;
4.1423 + /// RLengthMap rlength(length, 2.0);
4.1424 + ///
4.1425 + /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap;
4.1426 + /// ULengthMap ulength(flength, rlength);
4.1427 + ///
4.1428 + /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength);
4.1429 + /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
4.1430 + ///\endcode
4.1431 + ///
4.1432 + /// The combined arc map makes the length map for the undirected
4.1433 + /// graph. It is created from a forward and reverse map. The forward
4.1434 + /// map is created from the original length map with a SimpleMap
4.1435 + /// adaptor which just makes a read-write map from the reference map
4.1436 + /// i.e. it forgets that it can be return reference to values. The
4.1437 + /// reverse map is just the scaled original map with the ScaleMap
4.1438 + /// adaptor. The combination solves that passing the reverse way
4.1439 + /// takes double time than the original. To get the driving time we
4.1440 + /// run the dijkstra algorithm on the graph.
4.1441 + template<typename _Digraph>
4.1442 + class UndirDigraphAdaptor
4.1443 + : public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
4.1444 + public:
4.1445 + typedef _Digraph Digraph;
4.1446 + typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
4.1447 + protected:
4.1448 + UndirDigraphAdaptor() { }
4.1449 + public:
4.1450 +
4.1451 + /// \brief Constructor
4.1452 + ///
4.1453 + /// Constructor
4.1454 + UndirDigraphAdaptor(_Digraph& _digraph) {
4.1455 + setDigraph(_digraph);
4.1456 + }
4.1457 +
4.1458 + /// \brief ArcMap combined from two original ArcMap
4.1459 + ///
4.1460 + /// This class adapts two original digraph ArcMap to
4.1461 + /// get an arc map on the adaptor.
4.1462 + template <typename _ForwardMap, typename _BackwardMap>
4.1463 + class CombinedArcMap {
4.1464 + public:
4.1465 +
4.1466 + typedef _ForwardMap ForwardMap;
4.1467 + typedef _BackwardMap BackwardMap;
4.1468 +
4.1469 + typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
4.1470 +
4.1471 + typedef typename ForwardMap::Value Value;
4.1472 + typedef typename Parent::Arc Key;
4.1473 +
4.1474 + /// \brief Constructor
4.1475 + ///
4.1476 + /// Constructor
4.1477 + CombinedArcMap() : _forward(0), _backward(0) {}
4.1478 +
4.1479 + /// \brief Constructor
4.1480 + ///
4.1481 + /// Constructor
4.1482 + CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
4.1483 + : _forward(&forward), _backward(&backward) {}
4.1484 +
4.1485 +
4.1486 + /// \brief Sets the value associated with a key.
4.1487 + ///
4.1488 + /// Sets the value associated with a key.
4.1489 + void set(const Key& e, const Value& a) {
4.1490 + if (Parent::direction(e)) {
4.1491 + _forward->set(e, a);
4.1492 + } else {
4.1493 + _backward->set(e, a);
4.1494 + }
4.1495 + }
4.1496 +
4.1497 + /// \brief Returns the value associated with a key.
4.1498 + ///
4.1499 + /// Returns the value associated with a key.
4.1500 + typename MapTraits<ForwardMap>::ConstReturnValue
4.1501 + operator[](const Key& e) const {
4.1502 + if (Parent::direction(e)) {
4.1503 + return (*_forward)[e];
4.1504 + } else {
4.1505 + return (*_backward)[e];
4.1506 + }
4.1507 + }
4.1508 +
4.1509 + /// \brief Returns the value associated with a key.
4.1510 + ///
4.1511 + /// Returns the value associated with a key.
4.1512 + typename MapTraits<ForwardMap>::ReturnValue
4.1513 + operator[](const Key& e) {
4.1514 + if (Parent::direction(e)) {
4.1515 + return (*_forward)[e];
4.1516 + } else {
4.1517 + return (*_backward)[e];
4.1518 + }
4.1519 + }
4.1520 +
4.1521 + /// \brief Sets the forward map
4.1522 + ///
4.1523 + /// Sets the forward map
4.1524 + void setForwardMap(ForwardMap& forward) {
4.1525 + _forward = &forward;
4.1526 + }
4.1527 +
4.1528 + /// \brief Sets the backward map
4.1529 + ///
4.1530 + /// Sets the backward map
4.1531 + void setBackwardMap(BackwardMap& backward) {
4.1532 + _backward = &backward;
4.1533 + }
4.1534 +
4.1535 + protected:
4.1536 +
4.1537 + ForwardMap* _forward;
4.1538 + BackwardMap* _backward;
4.1539 +
4.1540 + };
4.1541 +
4.1542 + };
4.1543 +
4.1544 + /// \brief Just gives back an undir digraph adaptor
4.1545 + ///
4.1546 + /// Just gives back an undir digraph adaptor
4.1547 + template<typename Digraph>
4.1548 + UndirDigraphAdaptor<const Digraph>
4.1549 + undirDigraphAdaptor(const Digraph& digraph) {
4.1550 + return UndirDigraphAdaptor<const Digraph>(digraph);
4.1551 + }
4.1552 +
4.1553 + template<typename _Digraph,
4.1554 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
4.1555 + typename _FlowMap = _CapacityMap,
4.1556 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
4.1557 + class ResForwardFilter {
4.1558 + public:
4.1559 +
4.1560 + typedef _Digraph Digraph;
4.1561 + typedef _CapacityMap CapacityMap;
4.1562 + typedef _FlowMap FlowMap;
4.1563 + typedef _Tolerance Tolerance;
4.1564 +
4.1565 + typedef typename Digraph::Arc Key;
4.1566 + typedef bool Value;
4.1567 +
4.1568 + private:
4.1569 +
4.1570 + const CapacityMap* _capacity;
4.1571 + const FlowMap* _flow;
4.1572 + Tolerance _tolerance;
4.1573 + public:
4.1574 +
4.1575 + ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
4.1576 + const Tolerance& tolerance = Tolerance())
4.1577 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
4.1578 +
4.1579 + ResForwardFilter(const Tolerance& tolerance = Tolerance())
4.1580 + : _capacity(0), _flow(0), _tolerance(tolerance) { }
4.1581 +
4.1582 + void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
4.1583 + void setFlow(const FlowMap& flow) { _flow = &flow; }
4.1584 +
4.1585 + bool operator[](const typename Digraph::Arc& a) const {
4.1586 + return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
4.1587 + }
4.1588 + };
4.1589 +
4.1590 + template<typename _Digraph,
4.1591 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
4.1592 + typename _FlowMap = _CapacityMap,
4.1593 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
4.1594 + class ResBackwardFilter {
4.1595 + public:
4.1596 +
4.1597 + typedef _Digraph Digraph;
4.1598 + typedef _CapacityMap CapacityMap;
4.1599 + typedef _FlowMap FlowMap;
4.1600 + typedef _Tolerance Tolerance;
4.1601 +
4.1602 + typedef typename Digraph::Arc Key;
4.1603 + typedef bool Value;
4.1604 +
4.1605 + private:
4.1606 +
4.1607 + const CapacityMap* _capacity;
4.1608 + const FlowMap* _flow;
4.1609 + Tolerance _tolerance;
4.1610 +
4.1611 + public:
4.1612 +
4.1613 + ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
4.1614 + const Tolerance& tolerance = Tolerance())
4.1615 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
4.1616 + ResBackwardFilter(const Tolerance& tolerance = Tolerance())
4.1617 + : _capacity(0), _flow(0), _tolerance(tolerance) { }
4.1618 +
4.1619 + void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
4.1620 + void setFlow(const FlowMap& flow) { _flow = &flow; }
4.1621 +
4.1622 + bool operator[](const typename Digraph::Arc& a) const {
4.1623 + return _tolerance.positive((*_flow)[a]);
4.1624 + }
4.1625 + };
4.1626 +
4.1627 +
4.1628 + ///\ingroup graph_adaptors
4.1629 + ///
4.1630 + ///\brief An adaptor for composing the residual graph for directed
4.1631 + ///flow and circulation problems.
4.1632 + ///
4.1633 + ///An adaptor for composing the residual graph for directed flow and
4.1634 + ///circulation problems. Let \f$ G=(V, A) \f$ be a directed digraph
4.1635 + ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F
4.1636 + ///\f$, be functions on the arc-set.
4.1637 + ///
4.1638 + ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands
4.1639 + ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
4.1640 + ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.
4.1641 + ///
4.1642 + ///\code
4.1643 + /// ListDigraph g;
4.1644 + ///\endcode
4.1645 + ///
4.1646 + ///Then ResDigraphAdaptor implements the digraph structure with
4.1647 + /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}
4.1648 + /// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
4.1649 + /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
4.1650 + /// called residual graph. When we take the union \f$
4.1651 + /// A_{forward}\cup A_{backward} \f$, multilicities are counted,
4.1652 + /// i.e. if an arc is in both \f$ A_{forward} \f$ and \f$
4.1653 + /// A_{backward} \f$, then in the adaptor it appears twice. The
4.1654 + /// following code shows how such an instance can be constructed.
4.1655 + ///
4.1656 + ///\code
4.1657 + /// typedef ListDigraph Digraph;
4.1658 + /// IntArcMap f(g), c(g);
4.1659 + /// ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);
4.1660 + ///\endcode
4.1661 + template<typename _Digraph,
4.1662 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
4.1663 + typename _FlowMap = _CapacityMap,
4.1664 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
4.1665 + class ResDigraphAdaptor :
4.1666 + public ArcSubDigraphAdaptor<
4.1667 + UndirDigraphAdaptor<const _Digraph>,
4.1668 + typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<
4.1669 + ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,
4.1670 + ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {
4.1671 + public:
4.1672 +
4.1673 + typedef _Digraph Digraph;
4.1674 + typedef _CapacityMap CapacityMap;
4.1675 + typedef _FlowMap FlowMap;
4.1676 + typedef _Tolerance Tolerance;
4.1677 +
4.1678 + typedef typename CapacityMap::Value Value;
4.1679 + typedef ResDigraphAdaptor Adaptor;
4.1680 +
4.1681 + protected:
4.1682 +
4.1683 + typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
4.1684 +
4.1685 + typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>
4.1686 + ForwardFilter;
4.1687 +
4.1688 + typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>
4.1689 + BackwardFilter;
4.1690 +
4.1691 + typedef typename UndirDigraph::
4.1692 + template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
4.1693 +
4.1694 + typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
4.1695 +
4.1696 + const CapacityMap* _capacity;
4.1697 + FlowMap* _flow;
4.1698 +
4.1699 + UndirDigraph _graph;
4.1700 + ForwardFilter _forward_filter;
4.1701 + BackwardFilter _backward_filter;
4.1702 + ArcFilter _arc_filter;
4.1703 +
4.1704 + void setCapacityMap(const CapacityMap& capacity) {
4.1705 + _capacity = &capacity;
4.1706 + _forward_filter.setCapacity(capacity);
4.1707 + _backward_filter.setCapacity(capacity);
4.1708 + }
4.1709 +
4.1710 + void setFlowMap(FlowMap& flow) {
4.1711 + _flow = &flow;
4.1712 + _forward_filter.setFlow(flow);
4.1713 + _backward_filter.setFlow(flow);
4.1714 + }
4.1715 +
4.1716 + public:
4.1717 +
4.1718 + /// \brief Constructor of the residual digraph.
4.1719 + ///
4.1720 + /// Constructor of the residual graph. The parameters are the digraph type,
4.1721 + /// the flow map, the capacity map and a tolerance object.
4.1722 + ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,
4.1723 + FlowMap& flow, const Tolerance& tolerance = Tolerance())
4.1724 + : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
4.1725 + _forward_filter(capacity, flow, tolerance),
4.1726 + _backward_filter(capacity, flow, tolerance),
4.1727 + _arc_filter(_forward_filter, _backward_filter)
4.1728 + {
4.1729 + Parent::setDigraph(_graph);
4.1730 + Parent::setArcFilterMap(_arc_filter);
4.1731 + }
4.1732 +
4.1733 + typedef typename Parent::Arc Arc;
4.1734 +
4.1735 + /// \brief Gives back the residual capacity of the arc.
4.1736 + ///
4.1737 + /// Gives back the residual capacity of the arc.
4.1738 + Value rescap(const Arc& arc) const {
4.1739 + if (UndirDigraph::direction(arc)) {
4.1740 + return (*_capacity)[arc] - (*_flow)[arc];
4.1741 + } else {
4.1742 + return (*_flow)[arc];
4.1743 + }
4.1744 + }
4.1745 +
4.1746 + /// \brief Augment on the given arc in the residual digraph.
4.1747 + ///
4.1748 + /// Augment on the given arc in the residual digraph. It increase
4.1749 + /// or decrease the flow on the original arc depend on the direction
4.1750 + /// of the residual arc.
4.1751 + void augment(const Arc& e, const Value& a) const {
4.1752 + if (UndirDigraph::direction(e)) {
4.1753 + _flow->set(e, (*_flow)[e] + a);
4.1754 + } else {
4.1755 + _flow->set(e, (*_flow)[e] - a);
4.1756 + }
4.1757 + }
4.1758 +
4.1759 + /// \brief Returns the direction of the arc.
4.1760 + ///
4.1761 + /// Returns true when the arc is same oriented as the original arc.
4.1762 + static bool forward(const Arc& e) {
4.1763 + return UndirDigraph::direction(e);
4.1764 + }
4.1765 +
4.1766 + /// \brief Returns the direction of the arc.
4.1767 + ///
4.1768 + /// Returns true when the arc is opposite oriented as the original arc.
4.1769 + static bool backward(const Arc& e) {
4.1770 + return !UndirDigraph::direction(e);
4.1771 + }
4.1772 +
4.1773 + /// \brief Gives back the forward oriented residual arc.
4.1774 + ///
4.1775 + /// Gives back the forward oriented residual arc.
4.1776 + static Arc forward(const typename Digraph::Arc& e) {
4.1777 + return UndirDigraph::direct(e, true);
4.1778 + }
4.1779 +
4.1780 + /// \brief Gives back the backward oriented residual arc.
4.1781 + ///
4.1782 + /// Gives back the backward oriented residual arc.
4.1783 + static Arc backward(const typename Digraph::Arc& e) {
4.1784 + return UndirDigraph::direct(e, false);
4.1785 + }
4.1786 +
4.1787 + /// \brief Residual capacity map.
4.1788 + ///
4.1789 + /// In generic residual digraphs the residual capacity can be obtained
4.1790 + /// as a map.
4.1791 + class ResCap {
4.1792 + protected:
4.1793 + const Adaptor* _adaptor;
4.1794 + public:
4.1795 + typedef Arc Key;
4.1796 + typedef typename _CapacityMap::Value Value;
4.1797 +
4.1798 + ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
4.1799 +
4.1800 + Value operator[](const Arc& e) const {
4.1801 + return _adaptor->rescap(e);
4.1802 + }
4.1803 +
4.1804 + };
4.1805 +
4.1806 + };
4.1807 +
4.1808 + /// \brief Base class for split digraph adaptor
4.1809 + ///
4.1810 + /// Base class of split digraph adaptor. In most case you do not need to
4.1811 + /// use it directly but the documented member functions of this class can
4.1812 + /// be used with the SplitDigraphAdaptor class.
4.1813 + /// \sa SplitDigraphAdaptor
4.1814 + template <typename _Digraph>
4.1815 + class SplitDigraphAdaptorBase {
4.1816 + public:
4.1817 +
4.1818 + typedef _Digraph Digraph;
4.1819 + typedef DigraphAdaptorBase<const _Digraph> Parent;
4.1820 + typedef SplitDigraphAdaptorBase Adaptor;
4.1821 +
4.1822 + typedef typename Digraph::Node DigraphNode;
4.1823 + typedef typename Digraph::Arc DigraphArc;
4.1824 +
4.1825 + class Node;
4.1826 + class Arc;
4.1827 +
4.1828 + private:
4.1829 +
4.1830 + template <typename T> class NodeMapBase;
4.1831 + template <typename T> class ArcMapBase;
4.1832 +
4.1833 + public:
4.1834 +
4.1835 + class Node : public DigraphNode {
4.1836 + friend class SplitDigraphAdaptorBase;
4.1837 + template <typename T> friend class NodeMapBase;
4.1838 + private:
4.1839 +
4.1840 + bool _in;
4.1841 + Node(DigraphNode node, bool in)
4.1842 + : DigraphNode(node), _in(in) {}
4.1843 +
4.1844 + public:
4.1845 +
4.1846 + Node() {}
4.1847 + Node(Invalid) : DigraphNode(INVALID), _in(true) {}
4.1848 +
4.1849 + bool operator==(const Node& node) const {
4.1850 + return DigraphNode::operator==(node) && _in == node._in;
4.1851 + }
4.1852 +
4.1853 + bool operator!=(const Node& node) const {
4.1854 + return !(*this == node);
4.1855 + }
4.1856 +
4.1857 + bool operator<(const Node& node) const {
4.1858 + return DigraphNode::operator<(node) ||
4.1859 + (DigraphNode::operator==(node) && _in < node._in);
4.1860 + }
4.1861 + };
4.1862 +
4.1863 + class Arc {
4.1864 + friend class SplitDigraphAdaptorBase;
4.1865 + template <typename T> friend class ArcMapBase;
4.1866 + private:
4.1867 + typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
4.1868 +
4.1869 + explicit Arc(const DigraphArc& arc) : _item(arc) {}
4.1870 + explicit Arc(const DigraphNode& node) : _item(node) {}
4.1871 +
4.1872 + ArcImpl _item;
4.1873 +
4.1874 + public:
4.1875 + Arc() {}
4.1876 + Arc(Invalid) : _item(DigraphArc(INVALID)) {}
4.1877 +
4.1878 + bool operator==(const Arc& arc) const {
4.1879 + if (_item.firstState()) {
4.1880 + if (arc._item.firstState()) {
4.1881 + return _item.first() == arc._item.first();
4.1882 + }
4.1883 + } else {
4.1884 + if (arc._item.secondState()) {
4.1885 + return _item.second() == arc._item.second();
4.1886 + }
4.1887 + }
4.1888 + return false;
4.1889 + }
4.1890 +
4.1891 + bool operator!=(const Arc& arc) const {
4.1892 + return !(*this == arc);
4.1893 + }
4.1894 +
4.1895 + bool operator<(const Arc& arc) const {
4.1896 + if (_item.firstState()) {
4.1897 + if (arc._item.firstState()) {
4.1898 + return _item.first() < arc._item.first();
4.1899 + }
4.1900 + return false;
4.1901 + } else {
4.1902 + if (arc._item.secondState()) {
4.1903 + return _item.second() < arc._item.second();
4.1904 + }
4.1905 + return true;
4.1906 + }
4.1907 + }
4.1908 +
4.1909 + operator DigraphArc() const { return _item.first(); }
4.1910 + operator DigraphNode() const { return _item.second(); }
4.1911 +
4.1912 + };
4.1913 +
4.1914 + void first(Node& n) const {
4.1915 + _digraph->first(n);
4.1916 + n._in = true;
4.1917 + }
4.1918 +
4.1919 + void next(Node& n) const {
4.1920 + if (n._in) {
4.1921 + n._in = false;
4.1922 + } else {
4.1923 + n._in = true;
4.1924 + _digraph->next(n);
4.1925 + }
4.1926 + }
4.1927 +
4.1928 + void first(Arc& e) const {
4.1929 + e._item.setSecond();
4.1930 + _digraph->first(e._item.second());
4.1931 + if (e._item.second() == INVALID) {
4.1932 + e._item.setFirst();
4.1933 + _digraph->first(e._item.first());
4.1934 + }
4.1935 + }
4.1936 +
4.1937 + void next(Arc& e) const {
4.1938 + if (e._item.secondState()) {
4.1939 + _digraph->next(e._item.second());
4.1940 + if (e._item.second() == INVALID) {
4.1941 + e._item.setFirst();
4.1942 + _digraph->first(e._item.first());
4.1943 + }
4.1944 + } else {
4.1945 + _digraph->next(e._item.first());
4.1946 + }
4.1947 + }
4.1948 +
4.1949 + void firstOut(Arc& e, const Node& n) const {
4.1950 + if (n._in) {
4.1951 + e._item.setSecond(n);
4.1952 + } else {
4.1953 + e._item.setFirst();
4.1954 + _digraph->firstOut(e._item.first(), n);
4.1955 + }
4.1956 + }
4.1957 +
4.1958 + void nextOut(Arc& e) const {
4.1959 + if (!e._item.firstState()) {
4.1960 + e._item.setFirst(INVALID);
4.1961 + } else {
4.1962 + _digraph->nextOut(e._item.first());
4.1963 + }
4.1964 + }
4.1965 +
4.1966 + void firstIn(Arc& e, const Node& n) const {
4.1967 + if (!n._in) {
4.1968 + e._item.setSecond(n);
4.1969 + } else {
4.1970 + e._item.setFirst();
4.1971 + _digraph->firstIn(e._item.first(), n);
4.1972 + }
4.1973 + }
4.1974 +
4.1975 + void nextIn(Arc& e) const {
4.1976 + if (!e._item.firstState()) {
4.1977 + e._item.setFirst(INVALID);
4.1978 + } else {
4.1979 + _digraph->nextIn(e._item.first());
4.1980 + }
4.1981 + }
4.1982 +
4.1983 + Node source(const Arc& e) const {
4.1984 + if (e._item.firstState()) {
4.1985 + return Node(_digraph->source(e._item.first()), false);
4.1986 + } else {
4.1987 + return Node(e._item.second(), true);
4.1988 + }
4.1989 + }
4.1990 +
4.1991 + Node target(const Arc& e) const {
4.1992 + if (e._item.firstState()) {
4.1993 + return Node(_digraph->target(e._item.first()), true);
4.1994 + } else {
4.1995 + return Node(e._item.second(), false);
4.1996 + }
4.1997 + }
4.1998 +
4.1999 + int id(const Node& n) const {
4.2000 + return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
4.2001 + }
4.2002 + Node nodeFromId(int ix) const {
4.2003 + return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
4.2004 + }
4.2005 + int maxNodeId() const {
4.2006 + return 2 * _digraph->maxNodeId() + 1;
4.2007 + }
4.2008 +
4.2009 + int id(const Arc& e) const {
4.2010 + if (e._item.firstState()) {
4.2011 + return _digraph->id(e._item.first()) << 1;
4.2012 + } else {
4.2013 + return (_digraph->id(e._item.second()) << 1) | 1;
4.2014 + }
4.2015 + }
4.2016 + Arc arcFromId(int ix) const {
4.2017 + if ((ix & 1) == 0) {
4.2018 + return Arc(_digraph->arcFromId(ix >> 1));
4.2019 + } else {
4.2020 + return Arc(_digraph->nodeFromId(ix >> 1));
4.2021 + }
4.2022 + }
4.2023 + int maxArcId() const {
4.2024 + return std::max(_digraph->maxNodeId() << 1,
4.2025 + (_digraph->maxArcId() << 1) | 1);
4.2026 + }
4.2027 +
4.2028 + /// \brief Returns true when the node is in-node.
4.2029 + ///
4.2030 + /// Returns true when the node is in-node.
4.2031 + static bool inNode(const Node& n) {
4.2032 + return n._in;
4.2033 + }
4.2034 +
4.2035 + /// \brief Returns true when the node is out-node.
4.2036 + ///
4.2037 + /// Returns true when the node is out-node.
4.2038 + static bool outNode(const Node& n) {
4.2039 + return !n._in;
4.2040 + }
4.2041 +
4.2042 + /// \brief Returns true when the arc is arc in the original digraph.
4.2043 + ///
4.2044 + /// Returns true when the arc is arc in the original digraph.
4.2045 + static bool origArc(const Arc& e) {
4.2046 + return e._item.firstState();
4.2047 + }
4.2048 +
4.2049 + /// \brief Returns true when the arc binds an in-node and an out-node.
4.2050 + ///
4.2051 + /// Returns true when the arc binds an in-node and an out-node.
4.2052 + static bool bindArc(const Arc& e) {
4.2053 + return e._item.secondState();
4.2054 + }
4.2055 +
4.2056 + /// \brief Gives back the in-node created from the \c node.
4.2057 + ///
4.2058 + /// Gives back the in-node created from the \c node.
4.2059 + static Node inNode(const DigraphNode& n) {
4.2060 + return Node(n, true);
4.2061 + }
4.2062 +
4.2063 + /// \brief Gives back the out-node created from the \c node.
4.2064 + ///
4.2065 + /// Gives back the out-node created from the \c node.
4.2066 + static Node outNode(const DigraphNode& n) {
4.2067 + return Node(n, false);
4.2068 + }
4.2069 +
4.2070 + /// \brief Gives back the arc binds the two part of the node.
4.2071 + ///
4.2072 + /// Gives back the arc binds the two part of the node.
4.2073 + static Arc arc(const DigraphNode& n) {
4.2074 + return Arc(n);
4.2075 + }
4.2076 +
4.2077 + /// \brief Gives back the arc of the original arc.
4.2078 + ///
4.2079 + /// Gives back the arc of the original arc.
4.2080 + static Arc arc(const DigraphArc& e) {
4.2081 + return Arc(e);
4.2082 + }
4.2083 +
4.2084 + typedef True NodeNumTag;
4.2085 +
4.2086 + int nodeNum() const {
4.2087 + return 2 * countNodes(*_digraph);
4.2088 + }
4.2089 +
4.2090 + typedef True EdgeNumTag;
4.2091 + int arcNum() const {
4.2092 + return countArcs(*_digraph) + countNodes(*_digraph);
4.2093 + }
4.2094 +
4.2095 + typedef True FindEdgeTag;
4.2096 + Arc findArc(const Node& u, const Node& v,
4.2097 + const Arc& prev = INVALID) const {
4.2098 + if (inNode(u)) {
4.2099 + if (outNode(v)) {
4.2100 + if (static_cast<const DigraphNode&>(u) ==
4.2101 + static_cast<const DigraphNode&>(v) && prev == INVALID) {
4.2102 + return Arc(u);
4.2103 + }
4.2104 + }
4.2105 + } else {
4.2106 + if (inNode(v)) {
4.2107 + return Arc(::lemon::findArc(*_digraph, u, v, prev));
4.2108 + }
4.2109 + }
4.2110 + return INVALID;
4.2111 + }
4.2112 +
4.2113 + private:
4.2114 +
4.2115 + template <typename _Value>
4.2116 + class NodeMapBase
4.2117 + : public MapTraits<typename Parent::template NodeMap<_Value> > {
4.2118 + typedef typename Parent::template NodeMap<_Value> NodeImpl;
4.2119 + public:
4.2120 + typedef Node Key;
4.2121 + typedef _Value Value;
4.2122 +
4.2123 + NodeMapBase(const Adaptor& adaptor)
4.2124 + : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
4.2125 + NodeMapBase(const Adaptor& adaptor, const Value& value)
4.2126 + : _in_map(*adaptor._digraph, value),
4.2127 + _out_map(*adaptor._digraph, value) {}
4.2128 +
4.2129 + void set(const Node& key, const Value& val) {
4.2130 + if (Adaptor::inNode(key)) { _in_map.set(key, val); }
4.2131 + else {_out_map.set(key, val); }
4.2132 + }
4.2133 +
4.2134 + typename MapTraits<NodeImpl>::ReturnValue
4.2135 + operator[](const Node& key) {
4.2136 + if (Adaptor::inNode(key)) { return _in_map[key]; }
4.2137 + else { return _out_map[key]; }
4.2138 + }
4.2139 +
4.2140 + typename MapTraits<NodeImpl>::ConstReturnValue
4.2141 + operator[](const Node& key) const {
4.2142 + if (Adaptor::inNode(key)) { return _in_map[key]; }
4.2143 + else { return _out_map[key]; }
4.2144 + }
4.2145 +
4.2146 + private:
4.2147 + NodeImpl _in_map, _out_map;
4.2148 + };
4.2149 +
4.2150 + template <typename _Value>
4.2151 + class ArcMapBase
4.2152 + : public MapTraits<typename Parent::template ArcMap<_Value> > {
4.2153 + typedef typename Parent::template ArcMap<_Value> ArcImpl;
4.2154 + typedef typename Parent::template NodeMap<_Value> NodeImpl;
4.2155 + public:
4.2156 + typedef Arc Key;
4.2157 + typedef _Value Value;
4.2158 +
4.2159 + ArcMapBase(const Adaptor& adaptor)
4.2160 + : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
4.2161 + ArcMapBase(const Adaptor& adaptor, const Value& value)
4.2162 + : _arc_map(*adaptor._digraph, value),
4.2163 + _node_map(*adaptor._digraph, value) {}
4.2164 +
4.2165 + void set(const Arc& key, const Value& val) {
4.2166 + if (Adaptor::origArc(key)) {
4.2167 + _arc_map.set(key._item.first(), val);
4.2168 + } else {
4.2169 + _node_map.set(key._item.second(), val);
4.2170 + }
4.2171 + }
4.2172 +
4.2173 + typename MapTraits<ArcImpl>::ReturnValue
4.2174 + operator[](const Arc& key) {
4.2175 + if (Adaptor::origArc(key)) {
4.2176 + return _arc_map[key._item.first()];
4.2177 + } else {
4.2178 + return _node_map[key._item.second()];
4.2179 + }
4.2180 + }
4.2181 +
4.2182 + typename MapTraits<ArcImpl>::ConstReturnValue
4.2183 + operator[](const Arc& key) const {
4.2184 + if (Adaptor::origArc(key)) {
4.2185 + return _arc_map[key._item.first()];
4.2186 + } else {
4.2187 + return _node_map[key._item.second()];
4.2188 + }
4.2189 + }
4.2190 +
4.2191 + private:
4.2192 + ArcImpl _arc_map;
4.2193 + NodeImpl _node_map;
4.2194 + };
4.2195 +
4.2196 + public:
4.2197 +
4.2198 + template <typename _Value>
4.2199 + class NodeMap
4.2200 + : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
4.2201 + {
4.2202 + public:
4.2203 + typedef _Value Value;
4.2204 + typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
4.2205 +
4.2206 + NodeMap(const Adaptor& adaptor)
4.2207 + : Parent(adaptor) {}
4.2208 +
4.2209 + NodeMap(const Adaptor& adaptor, const Value& value)
4.2210 + : Parent(adaptor, value) {}
4.2211 +
4.2212 + private:
4.2213 + NodeMap& operator=(const NodeMap& cmap) {
4.2214 + return operator=<NodeMap>(cmap);
4.2215 + }
4.2216 +
4.2217 + template <typename CMap>
4.2218 + NodeMap& operator=(const CMap& cmap) {
4.2219 + Parent::operator=(cmap);
4.2220 + return *this;
4.2221 + }
4.2222 + };
4.2223 +
4.2224 + template <typename _Value>
4.2225 + class ArcMap
4.2226 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
4.2227 + {
4.2228 + public:
4.2229 + typedef _Value Value;
4.2230 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
4.2231 +
4.2232 + ArcMap(const Adaptor& adaptor)
4.2233 + : Parent(adaptor) {}
4.2234 +
4.2235 + ArcMap(const Adaptor& adaptor, const Value& value)
4.2236 + : Parent(adaptor, value) {}
4.2237 +
4.2238 + private:
4.2239 + ArcMap& operator=(const ArcMap& cmap) {
4.2240 + return operator=<ArcMap>(cmap);
4.2241 + }
4.2242 +
4.2243 + template <typename CMap>
4.2244 + ArcMap& operator=(const CMap& cmap) {
4.2245 + Parent::operator=(cmap);
4.2246 + return *this;
4.2247 + }
4.2248 + };
4.2249 +
4.2250 + protected:
4.2251 +
4.2252 + SplitDigraphAdaptorBase() : _digraph(0) {}
4.2253 +
4.2254 + Digraph* _digraph;
4.2255 +
4.2256 + void setDigraph(Digraph& digraph) {
4.2257 + _digraph = &digraph;
4.2258 + }
4.2259 +
4.2260 + };
4.2261 +
4.2262 + /// \ingroup graph_adaptors
4.2263 + ///
4.2264 + /// \brief Split digraph adaptor class
4.2265 + ///
4.2266 + /// This is an digraph adaptor which splits all node into an in-node
4.2267 + /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
4.2268 + /// node in the digraph with two node, \f$ u_{in} \f$ node and
4.2269 + /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the
4.2270 + /// original digraph the new target of the arc will be \f$ u_{in} \f$ and
4.2271 + /// similarly the source of the original \f$ (u, v) \f$ arc will be
4.2272 + /// \f$ u_{out} \f$. The adaptor will add for each node in the
4.2273 + /// original digraph an additional arc which will connect
4.2274 + /// \f$ (u_{in}, u_{out}) \f$.
4.2275 + ///
4.2276 + /// The aim of this class is to run algorithm with node costs if the
4.2277 + /// algorithm can use directly just arc costs. In this case we should use
4.2278 + /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
4.2279 + /// bind arc in the adapted digraph.
4.2280 + ///
4.2281 + /// By example a maximum flow algoritm can compute how many arc
4.2282 + /// disjoint paths are in the digraph. But we would like to know how
4.2283 + /// many node disjoint paths are in the digraph. First we have to
4.2284 + /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
4.2285 + /// algorithm on the adapted digraph. The bottleneck of the flow will
4.2286 + /// be the bind arcs which bounds the flow with the count of the
4.2287 + /// node disjoint paths.
4.2288 + ///
4.2289 + ///\code
4.2290 + ///
4.2291 + /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;
4.2292 + ///
4.2293 + /// SDigraph sdigraph(digraph);
4.2294 + ///
4.2295 + /// typedef ConstMap<SDigraph::Arc, int> SCapacity;
4.2296 + /// SCapacity scapacity(1);
4.2297 + ///
4.2298 + /// SDigraph::ArcMap<int> sflow(sdigraph);
4.2299 + ///
4.2300 + /// Preflow<SDigraph, SCapacity>
4.2301 + /// spreflow(sdigraph, scapacity,
4.2302 + /// SDigraph::outNode(source), SDigraph::inNode(target));
4.2303 + ///
4.2304 + /// spreflow.run();
4.2305 + ///
4.2306 + ///\endcode
4.2307 + ///
4.2308 + /// The result of the mamixum flow on the original digraph
4.2309 + /// shows the next figure:
4.2310 + ///
4.2311 + /// \image html arc_disjoint.png
4.2312 + /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth
4.2313 + ///
4.2314 + /// And the maximum flow on the adapted digraph:
4.2315 + ///
4.2316 + /// \image html node_disjoint.png
4.2317 + /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
4.2318 + ///
4.2319 + /// The second solution contains just 3 disjoint paths while the first 4.
4.2320 + /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
4.2321 + ///
4.2322 + /// This digraph adaptor is fully conform to the
4.2323 + /// \ref concepts::Digraph "Digraph" concept and
4.2324 + /// contains some additional member functions and types. The
4.2325 + /// documentation of some member functions may be found just in the
4.2326 + /// SplitDigraphAdaptorBase class.
4.2327 + ///
4.2328 + /// \sa SplitDigraphAdaptorBase
4.2329 + template <typename _Digraph>
4.2330 + class SplitDigraphAdaptor
4.2331 + : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
4.2332 + public:
4.2333 + typedef _Digraph Digraph;
4.2334 + typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
4.2335 +
4.2336 + typedef typename Parent::Node Node;
4.2337 + typedef typename Parent::Arc Arc;
4.2338 +
4.2339 + /// \brief Constructor of the adaptor.
4.2340 + ///
4.2341 + /// Constructor of the adaptor.
4.2342 + SplitDigraphAdaptor(Digraph& g) {
4.2343 + Parent::setDigraph(g);
4.2344 + }
4.2345 +
4.2346 + /// \brief NodeMap combined from two original NodeMap
4.2347 + ///
4.2348 + /// This class adapt two of the original digraph NodeMap to
4.2349 + /// get a node map on the adapted digraph.
4.2350 + template <typename InNodeMap, typename OutNodeMap>
4.2351 + class CombinedNodeMap {
4.2352 + public:
4.2353 +
4.2354 + typedef Node Key;
4.2355 + typedef typename InNodeMap::Value Value;
4.2356 +
4.2357 + /// \brief Constructor
4.2358 + ///
4.2359 + /// Constructor.
4.2360 + CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
4.2361 + : _in_map(in_map), _out_map(out_map) {}
4.2362 +
4.2363 + /// \brief The subscript operator.
4.2364 + ///
4.2365 + /// The subscript operator.
4.2366 + Value& operator[](const Key& key) {
4.2367 + if (Parent::inNode(key)) {
4.2368 + return _in_map[key];
4.2369 + } else {
4.2370 + return _out_map[key];
4.2371 + }
4.2372 + }
4.2373 +
4.2374 + /// \brief The const subscript operator.
4.2375 + ///
4.2376 + /// The const subscript operator.
4.2377 + Value operator[](const Key& key) const {
4.2378 + if (Parent::inNode(key)) {
4.2379 + return _in_map[key];
4.2380 + } else {
4.2381 + return _out_map[key];
4.2382 + }
4.2383 + }
4.2384 +
4.2385 + /// \brief The setter function of the map.
4.2386 + ///
4.2387 + /// The setter function of the map.
4.2388 + void set(const Key& key, const Value& value) {
4.2389 + if (Parent::inNode(key)) {
4.2390 + _in_map.set(key, value);
4.2391 + } else {
4.2392 + _out_map.set(key, value);
4.2393 + }
4.2394 + }
4.2395 +
4.2396 + private:
4.2397 +
4.2398 + InNodeMap& _in_map;
4.2399 + OutNodeMap& _out_map;
4.2400 +
4.2401 + };
4.2402 +
4.2403 +
4.2404 + /// \brief Just gives back a combined node map.
4.2405 + ///
4.2406 + /// Just gives back a combined node map.
4.2407 + template <typename InNodeMap, typename OutNodeMap>
4.2408 + static CombinedNodeMap<InNodeMap, OutNodeMap>
4.2409 + combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
4.2410 + return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
4.2411 + }
4.2412 +
4.2413 + template <typename InNodeMap, typename OutNodeMap>
4.2414 + static CombinedNodeMap<const InNodeMap, OutNodeMap>
4.2415 + combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
4.2416 + return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
4.2417 + }
4.2418 +
4.2419 + template <typename InNodeMap, typename OutNodeMap>
4.2420 + static CombinedNodeMap<InNodeMap, const OutNodeMap>
4.2421 + combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
4.2422 + return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
4.2423 + }
4.2424 +
4.2425 + template <typename InNodeMap, typename OutNodeMap>
4.2426 + static CombinedNodeMap<const InNodeMap, const OutNodeMap>
4.2427 + combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
4.2428 + return CombinedNodeMap<const InNodeMap,
4.2429 + const OutNodeMap>(in_map, out_map);
4.2430 + }
4.2431 +
4.2432 + /// \brief ArcMap combined from an original ArcMap and NodeMap
4.2433 + ///
4.2434 + /// This class adapt an original digraph ArcMap and NodeMap to
4.2435 + /// get an arc map on the adapted digraph.
4.2436 + template <typename DigraphArcMap, typename DigraphNodeMap>
4.2437 + class CombinedArcMap {
4.2438 + public:
4.2439 +
4.2440 + typedef Arc Key;
4.2441 + typedef typename DigraphArcMap::Value Value;
4.2442 +
4.2443 + /// \brief Constructor
4.2444 + ///
4.2445 + /// Constructor.
4.2446 + CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
4.2447 + : _arc_map(arc_map), _node_map(node_map) {}
4.2448 +
4.2449 + /// \brief The subscript operator.
4.2450 + ///
4.2451 + /// The subscript operator.
4.2452 + void set(const Arc& arc, const Value& val) {
4.2453 + if (Parent::origArc(arc)) {
4.2454 + _arc_map.set(arc, val);
4.2455 + } else {
4.2456 + _node_map.set(arc, val);
4.2457 + }
4.2458 + }
4.2459 +
4.2460 + /// \brief The const subscript operator.
4.2461 + ///
4.2462 + /// The const subscript operator.
4.2463 + Value operator[](const Key& arc) const {
4.2464 + if (Parent::origArc(arc)) {
4.2465 + return _arc_map[arc];
4.2466 + } else {
4.2467 + return _node_map[arc];
4.2468 + }
4.2469 + }
4.2470 +
4.2471 + /// \brief The const subscript operator.
4.2472 + ///
4.2473 + /// The const subscript operator.
4.2474 + Value& operator[](const Key& arc) {
4.2475 + if (Parent::origArc(arc)) {
4.2476 + return _arc_map[arc];
4.2477 + } else {
4.2478 + return _node_map[arc];
4.2479 + }
4.2480 + }
4.2481 +
4.2482 + private:
4.2483 + DigraphArcMap& _arc_map;
4.2484 + DigraphNodeMap& _node_map;
4.2485 + };
4.2486 +
4.2487 + /// \brief Just gives back a combined arc map.
4.2488 + ///
4.2489 + /// Just gives back a combined arc map.
4.2490 + template <typename DigraphArcMap, typename DigraphNodeMap>
4.2491 + static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
4.2492 + combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
4.2493 + return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
4.2494 + }
4.2495 +
4.2496 + template <typename DigraphArcMap, typename DigraphNodeMap>
4.2497 + static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
4.2498 + combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
4.2499 + return CombinedArcMap<const DigraphArcMap,
4.2500 + DigraphNodeMap>(arc_map, node_map);
4.2501 + }
4.2502 +
4.2503 + template <typename DigraphArcMap, typename DigraphNodeMap>
4.2504 + static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
4.2505 + combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
4.2506 + return CombinedArcMap<DigraphArcMap,
4.2507 + const DigraphNodeMap>(arc_map, node_map);
4.2508 + }
4.2509 +
4.2510 + template <typename DigraphArcMap, typename DigraphNodeMap>
4.2511 + static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
4.2512 + combinedArcMap(const DigraphArcMap& arc_map,
4.2513 + const DigraphNodeMap& node_map) {
4.2514 + return CombinedArcMap<const DigraphArcMap,
4.2515 + const DigraphNodeMap>(arc_map, node_map);
4.2516 + }
4.2517 +
4.2518 + };
4.2519 +
4.2520 + /// \brief Just gives back a split digraph adaptor
4.2521 + ///
4.2522 + /// Just gives back a split digraph adaptor
4.2523 + template<typename Digraph>
4.2524 + SplitDigraphAdaptor<Digraph>
4.2525 + splitDigraphAdaptor(const Digraph& digraph) {
4.2526 + return SplitDigraphAdaptor<Digraph>(digraph);
4.2527 + }
4.2528 +
4.2529 +
4.2530 +} //namespace lemon
4.2531 +
4.2532 +#endif //LEMON_DIGRAPH_ADAPTOR_H
4.2533 +
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/graph_adaptor.h Sun Nov 30 18:57:18 2008 +0100
5.3 @@ -0,0 +1,1136 @@
5.4 +/* -*- C++ -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library
5.7 + *
5.8 + * Copyright (C) 2003-2008
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#ifndef LEMON_GRAPH_ADAPTOR_H
5.23 +#define LEMON_GRAPH_ADAPTOR_H
5.24 +
5.25 +///\ingroup graph_adaptors
5.26 +///\file
5.27 +///\brief Several graph adaptors.
5.28 +///
5.29 +///This file contains several useful undirected graph adaptor classes.
5.30 +
5.31 +#include <lemon/core.h>
5.32 +#include <lemon/maps.h>
5.33 +#include <lemon/bits/graph_adaptor_extender.h>
5.34 +
5.35 +namespace lemon {
5.36 +
5.37 + /// \brief Base type for the Graph Adaptors
5.38 + ///
5.39 + /// This is the base type for most of LEMON graph adaptors.
5.40 + /// This class implements a trivial graph adaptor i.e. it only wraps the
5.41 + /// functions and types of the graph. The purpose of this class is to
5.42 + /// make easier implementing graph adaptors. E.g. if an adaptor is
5.43 + /// considered which differs from the wrapped graph only in some of its
5.44 + /// functions or types, then it can be derived from GraphAdaptor, and only
5.45 + /// the differences should be implemented.
5.46 + template<typename _Graph>
5.47 + class GraphAdaptorBase {
5.48 + public:
5.49 + typedef _Graph Graph;
5.50 + typedef Graph ParentGraph;
5.51 +
5.52 + protected:
5.53 + Graph* _graph;
5.54 +
5.55 + GraphAdaptorBase() : _graph(0) {}
5.56 +
5.57 + void setGraph(Graph& graph) { _graph = &graph; }
5.58 +
5.59 + public:
5.60 + GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
5.61 +
5.62 + typedef typename Graph::Node Node;
5.63 + typedef typename Graph::Arc Arc;
5.64 + typedef typename Graph::Edge Edge;
5.65 +
5.66 + void first(Node& i) const { _graph->first(i); }
5.67 + void first(Arc& i) const { _graph->first(i); }
5.68 + void first(Edge& i) const { _graph->first(i); }
5.69 + void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
5.70 + void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
5.71 + void firstInc(Edge &i, bool &d, const Node &n) const {
5.72 + _graph->firstInc(i, d, n);
5.73 + }
5.74 +
5.75 + void next(Node& i) const { _graph->next(i); }
5.76 + void next(Arc& i) const { _graph->next(i); }
5.77 + void next(Edge& i) const { _graph->next(i); }
5.78 + void nextIn(Arc& i) const { _graph->nextIn(i); }
5.79 + void nextOut(Arc& i) const { _graph->nextOut(i); }
5.80 + void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
5.81 +
5.82 + Node u(const Edge& e) const { return _graph->u(e); }
5.83 + Node v(const Edge& e) const { return _graph->v(e); }
5.84 +
5.85 + Node source(const Arc& a) const { return _graph->source(a); }
5.86 + Node target(const Arc& a) const { return _graph->target(a); }
5.87 +
5.88 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
5.89 + int nodeNum() const { return _graph->nodeNum(); }
5.90 +
5.91 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
5.92 + int arcNum() const { return _graph->arcNum(); }
5.93 + int edgeNum() const { return _graph->edgeNum(); }
5.94 +
5.95 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
5.96 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
5.97 + return _graph->findArc(u, v, prev);
5.98 + }
5.99 + Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
5.100 + return _graph->findEdge(u, v, prev);
5.101 + }
5.102 +
5.103 + Node addNode() { return _graph->addNode(); }
5.104 + Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
5.105 +
5.106 + void erase(const Node& i) { _graph->erase(i); }
5.107 + void erase(const Edge& i) { _graph->erase(i); }
5.108 +
5.109 + void clear() { _graph->clear(); }
5.110 +
5.111 + bool direction(const Arc& a) const { return _graph->direction(a); }
5.112 + Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
5.113 +
5.114 + int id(const Node& v) const { return _graph->id(v); }
5.115 + int id(const Arc& a) const { return _graph->id(a); }
5.116 + int id(const Edge& e) const { return _graph->id(e); }
5.117 +
5.118 + Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
5.119 + Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
5.120 + Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
5.121 +
5.122 + int maxNodeId() const { return _graph->maxNodeId(); }
5.123 + int maxArcId() const { return _graph->maxArcId(); }
5.124 + int maxEdgeId() const { return _graph->maxEdgeId(); }
5.125 +
5.126 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
5.127 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
5.128 +
5.129 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
5.130 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
5.131 +
5.132 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
5.133 + EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
5.134 +
5.135 + template <typename _Value>
5.136 + class NodeMap : public Graph::template NodeMap<_Value> {
5.137 + public:
5.138 + typedef typename Graph::template NodeMap<_Value> Parent;
5.139 + explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
5.140 + : Parent(*adapter._graph) {}
5.141 + NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
5.142 + : Parent(*adapter._graph, value) {}
5.143 +
5.144 + private:
5.145 + NodeMap& operator=(const NodeMap& cmap) {
5.146 + return operator=<NodeMap>(cmap);
5.147 + }
5.148 +
5.149 + template <typename CMap>
5.150 + NodeMap& operator=(const CMap& cmap) {
5.151 + Parent::operator=(cmap);
5.152 + return *this;
5.153 + }
5.154 +
5.155 + };
5.156 +
5.157 + template <typename _Value>
5.158 + class ArcMap : public Graph::template ArcMap<_Value> {
5.159 + public:
5.160 + typedef typename Graph::template ArcMap<_Value> Parent;
5.161 + explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
5.162 + : Parent(*adapter._graph) {}
5.163 + ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
5.164 + : Parent(*adapter._graph, value) {}
5.165 +
5.166 + private:
5.167 + ArcMap& operator=(const ArcMap& cmap) {
5.168 + return operator=<ArcMap>(cmap);
5.169 + }
5.170 +
5.171 + template <typename CMap>
5.172 + ArcMap& operator=(const CMap& cmap) {
5.173 + Parent::operator=(cmap);
5.174 + return *this;
5.175 + }
5.176 + };
5.177 +
5.178 + template <typename _Value>
5.179 + class EdgeMap : public Graph::template EdgeMap<_Value> {
5.180 + public:
5.181 + typedef typename Graph::template EdgeMap<_Value> Parent;
5.182 + explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
5.183 + : Parent(*adapter._graph) {}
5.184 + EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
5.185 + : Parent(*adapter._graph, value) {}
5.186 +
5.187 + private:
5.188 + EdgeMap& operator=(const EdgeMap& cmap) {
5.189 + return operator=<EdgeMap>(cmap);
5.190 + }
5.191 +
5.192 + template <typename CMap>
5.193 + EdgeMap& operator=(const CMap& cmap) {
5.194 + Parent::operator=(cmap);
5.195 + return *this;
5.196 + }
5.197 + };
5.198 +
5.199 + };
5.200 +
5.201 + /// \ingroup graph_adaptors
5.202 + ///
5.203 + /// \brief Trivial graph adaptor
5.204 + ///
5.205 + /// This class is an adaptor which does not change the adapted undirected
5.206 + /// graph. It can be used only to test the graph adaptors.
5.207 + template <typename _Graph>
5.208 + class GraphAdaptor
5.209 + : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {
5.210 + public:
5.211 + typedef _Graph Graph;
5.212 + typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
5.213 + protected:
5.214 + GraphAdaptor() : Parent() {}
5.215 +
5.216 + public:
5.217 + explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
5.218 + };
5.219 +
5.220 + template <typename _Graph, typename NodeFilterMap,
5.221 + typename EdgeFilterMap, bool checked = true>
5.222 + class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
5.223 + public:
5.224 + typedef _Graph Graph;
5.225 + typedef SubGraphAdaptorBase Adaptor;
5.226 + typedef GraphAdaptorBase<_Graph> Parent;
5.227 + protected:
5.228 +
5.229 + NodeFilterMap* _node_filter_map;
5.230 + EdgeFilterMap* _edge_filter_map;
5.231 +
5.232 + SubGraphAdaptorBase()
5.233 + : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
5.234 +
5.235 + void setNodeFilterMap(NodeFilterMap& node_filter_map) {
5.236 + _node_filter_map=&node_filter_map;
5.237 + }
5.238 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
5.239 + _edge_filter_map=&edge_filter_map;
5.240 + }
5.241 +
5.242 + public:
5.243 +
5.244 + typedef typename Parent::Node Node;
5.245 + typedef typename Parent::Arc Arc;
5.246 + typedef typename Parent::Edge Edge;
5.247 +
5.248 + void first(Node& i) const {
5.249 + Parent::first(i);
5.250 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
5.251 + }
5.252 +
5.253 + void first(Arc& i) const {
5.254 + Parent::first(i);
5.255 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.256 + || !(*_node_filter_map)[Parent::source(i)]
5.257 + || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
5.258 + }
5.259 +
5.260 + void first(Edge& i) const {
5.261 + Parent::first(i);
5.262 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.263 + || !(*_node_filter_map)[Parent::u(i)]
5.264 + || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
5.265 + }
5.266 +
5.267 + void firstIn(Arc& i, const Node& n) const {
5.268 + Parent::firstIn(i, n);
5.269 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.270 + || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
5.271 + }
5.272 +
5.273 + void firstOut(Arc& i, const Node& n) const {
5.274 + Parent::firstOut(i, n);
5.275 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.276 + || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
5.277 + }
5.278 +
5.279 + void firstInc(Edge& i, bool& d, const Node& n) const {
5.280 + Parent::firstInc(i, d, n);
5.281 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.282 + || !(*_node_filter_map)[Parent::u(i)]
5.283 + || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
5.284 + }
5.285 +
5.286 + void next(Node& i) const {
5.287 + Parent::next(i);
5.288 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
5.289 + }
5.290 +
5.291 + void next(Arc& i) const {
5.292 + Parent::next(i);
5.293 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.294 + || !(*_node_filter_map)[Parent::source(i)]
5.295 + || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
5.296 + }
5.297 +
5.298 + void next(Edge& i) const {
5.299 + Parent::next(i);
5.300 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.301 + || !(*_node_filter_map)[Parent::u(i)]
5.302 + || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
5.303 + }
5.304 +
5.305 + void nextIn(Arc& i) const {
5.306 + Parent::nextIn(i);
5.307 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.308 + || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
5.309 + }
5.310 +
5.311 + void nextOut(Arc& i) const {
5.312 + Parent::nextOut(i);
5.313 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.314 + || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
5.315 + }
5.316 +
5.317 + void nextInc(Edge& i, bool& d) const {
5.318 + Parent::nextInc(i, d);
5.319 + while (i!=INVALID && (!(*_edge_filter_map)[i]
5.320 + || !(*_node_filter_map)[Parent::u(i)]
5.321 + || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
5.322 + }
5.323 +
5.324 + /// \brief Hide the given node in the graph.
5.325 + ///
5.326 + /// This function hides \c n in the graph, i.e. the iteration
5.327 + /// jumps over it. This is done by simply setting the value of \c n
5.328 + /// to be false in the corresponding node-map.
5.329 + void hide(const Node& n) const { _node_filter_map->set(n, false); }
5.330 +
5.331 + /// \brief Hide the given edge in the graph.
5.332 + ///
5.333 + /// This function hides \c e in the graph, i.e. the iteration
5.334 + /// jumps over it. This is done by simply setting the value of \c e
5.335 + /// to be false in the corresponding edge-map.
5.336 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
5.337 +
5.338 + /// \brief Unhide the given node in the graph.
5.339 + ///
5.340 + /// The value of \c n is set to be true in the node-map which stores
5.341 + /// hide information. If \c n was hidden previuosly, then it is shown
5.342 + /// again
5.343 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
5.344 +
5.345 + /// \brief Hide the given edge in the graph.
5.346 + ///
5.347 + /// The value of \c e is set to be true in the edge-map which stores
5.348 + /// hide information. If \c e was hidden previuosly, then it is shown
5.349 + /// again
5.350 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
5.351 +
5.352 + /// \brief Returns true if \c n is hidden.
5.353 + ///
5.354 + /// Returns true if \c n is hidden.
5.355 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
5.356 +
5.357 + /// \brief Returns true if \c e is hidden.
5.358 + ///
5.359 + /// Returns true if \c e is hidden.
5.360 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
5.361 +
5.362 + typedef False NodeNumTag;
5.363 + typedef False EdgeNumTag;
5.364 +
5.365 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
5.366 + Arc findArc(const Node& u, const Node& v,
5.367 + const Arc& prev = INVALID) {
5.368 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
5.369 + return INVALID;
5.370 + }
5.371 + Arc arc = Parent::findArc(u, v, prev);
5.372 + while (arc != INVALID && !(*_edge_filter_map)[arc]) {
5.373 + arc = Parent::findArc(u, v, arc);
5.374 + }
5.375 + return arc;
5.376 + }
5.377 + Edge findEdge(const Node& u, const Node& v,
5.378 + const Edge& prev = INVALID) {
5.379 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
5.380 + return INVALID;
5.381 + }
5.382 + Edge edge = Parent::findEdge(u, v, prev);
5.383 + while (edge != INVALID && !(*_edge_filter_map)[edge]) {
5.384 + edge = Parent::findEdge(u, v, edge);
5.385 + }
5.386 + return edge;
5.387 + }
5.388 +
5.389 + template <typename _Value>
5.390 + class NodeMap : public SubMapExtender<Adaptor,
5.391 + typename Parent::template NodeMap<_Value> > {
5.392 + public:
5.393 + typedef _Value Value;
5.394 + typedef SubMapExtender<Adaptor, typename Parent::
5.395 + template NodeMap<Value> > MapParent;
5.396 +
5.397 + NodeMap(const Adaptor& adaptor)
5.398 + : MapParent(adaptor) {}
5.399 + NodeMap(const Adaptor& adaptor, const Value& value)
5.400 + : MapParent(adaptor, value) {}
5.401 +
5.402 + private:
5.403 + NodeMap& operator=(const NodeMap& cmap) {
5.404 + return operator=<NodeMap>(cmap);
5.405 + }
5.406 +
5.407 + template <typename CMap>
5.408 + NodeMap& operator=(const CMap& cmap) {
5.409 + MapParent::operator=(cmap);
5.410 + return *this;
5.411 + }
5.412 + };
5.413 +
5.414 + template <typename _Value>
5.415 + class ArcMap : public SubMapExtender<Adaptor,
5.416 + typename Parent::template ArcMap<_Value> > {
5.417 + public:
5.418 + typedef _Value Value;
5.419 + typedef SubMapExtender<Adaptor, typename Parent::
5.420 + template ArcMap<Value> > MapParent;
5.421 +
5.422 + ArcMap(const Adaptor& adaptor)
5.423 + : MapParent(adaptor) {}
5.424 + ArcMap(const Adaptor& adaptor, const Value& value)
5.425 + : MapParent(adaptor, value) {}
5.426 +
5.427 + private:
5.428 + ArcMap& operator=(const ArcMap& cmap) {
5.429 + return operator=<ArcMap>(cmap);
5.430 + }
5.431 +
5.432 + template <typename CMap>
5.433 + ArcMap& operator=(const CMap& cmap) {
5.434 + MapParent::operator=(cmap);
5.435 + return *this;
5.436 + }
5.437 + };
5.438 +
5.439 + template <typename _Value>
5.440 + class EdgeMap : public SubMapExtender<Adaptor,
5.441 + typename Parent::template EdgeMap<_Value> > {
5.442 + public:
5.443 + typedef _Value Value;
5.444 + typedef SubMapExtender<Adaptor, typename Parent::
5.445 + template EdgeMap<Value> > MapParent;
5.446 +
5.447 + EdgeMap(const Adaptor& adaptor)
5.448 + : MapParent(adaptor) {}
5.449 +
5.450 + EdgeMap(const Adaptor& adaptor, const Value& value)
5.451 + : MapParent(adaptor, value) {}
5.452 +
5.453 + private:
5.454 + EdgeMap& operator=(const EdgeMap& cmap) {
5.455 + return operator=<EdgeMap>(cmap);
5.456 + }
5.457 +
5.458 + template <typename CMap>
5.459 + EdgeMap& operator=(const CMap& cmap) {
5.460 + MapParent::operator=(cmap);
5.461 + return *this;
5.462 + }
5.463 + };
5.464 +
5.465 + };
5.466 +
5.467 + template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
5.468 + class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
5.469 + : public GraphAdaptorBase<_Graph> {
5.470 + public:
5.471 + typedef _Graph Graph;
5.472 + typedef SubGraphAdaptorBase Adaptor;
5.473 + typedef GraphAdaptorBase<_Graph> Parent;
5.474 + protected:
5.475 + NodeFilterMap* _node_filter_map;
5.476 + EdgeFilterMap* _edge_filter_map;
5.477 + SubGraphAdaptorBase() : Parent(),
5.478 + _node_filter_map(0), _edge_filter_map(0) { }
5.479 +
5.480 + void setNodeFilterMap(NodeFilterMap& node_filter_map) {
5.481 + _node_filter_map=&node_filter_map;
5.482 + }
5.483 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
5.484 + _edge_filter_map=&edge_filter_map;
5.485 + }
5.486 +
5.487 + public:
5.488 +
5.489 + typedef typename Parent::Node Node;
5.490 + typedef typename Parent::Arc Arc;
5.491 + typedef typename Parent::Edge Edge;
5.492 +
5.493 + void first(Node& i) const {
5.494 + Parent::first(i);
5.495 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
5.496 + }
5.497 +
5.498 + void first(Arc& i) const {
5.499 + Parent::first(i);
5.500 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
5.501 + }
5.502 +
5.503 + void first(Edge& i) const {
5.504 + Parent::first(i);
5.505 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
5.506 + }
5.507 +
5.508 + void firstIn(Arc& i, const Node& n) const {
5.509 + Parent::firstIn(i, n);
5.510 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
5.511 + }
5.512 +
5.513 + void firstOut(Arc& i, const Node& n) const {
5.514 + Parent::firstOut(i, n);
5.515 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
5.516 + }
5.517 +
5.518 + void firstInc(Edge& i, bool& d, const Node& n) const {
5.519 + Parent::firstInc(i, d, n);
5.520 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
5.521 + }
5.522 +
5.523 + void next(Node& i) const {
5.524 + Parent::next(i);
5.525 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
5.526 + }
5.527 + void next(Arc& i) const {
5.528 + Parent::next(i);
5.529 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
5.530 + }
5.531 + void next(Edge& i) const {
5.532 + Parent::next(i);
5.533 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
5.534 + }
5.535 + void nextIn(Arc& i) const {
5.536 + Parent::nextIn(i);
5.537 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
5.538 + }
5.539 +
5.540 + void nextOut(Arc& i) const {
5.541 + Parent::nextOut(i);
5.542 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
5.543 + }
5.544 + void nextInc(Edge& i, bool& d) const {
5.545 + Parent::nextInc(i, d);
5.546 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
5.547 + }
5.548 +
5.549 + /// \brief Hide the given node in the graph.
5.550 + ///
5.551 + /// This function hides \c n in the graph, i.e. the iteration
5.552 + /// jumps over it. This is done by simply setting the value of \c n
5.553 + /// to be false in the corresponding node-map.
5.554 + void hide(const Node& n) const { _node_filter_map->set(n, false); }
5.555 +
5.556 + /// \brief Hide the given edge in the graph.
5.557 + ///
5.558 + /// This function hides \c e in the graph, i.e. the iteration
5.559 + /// jumps over it. This is done by simply setting the value of \c e
5.560 + /// to be false in the corresponding edge-map.
5.561 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
5.562 +
5.563 + /// \brief Unhide the given node in the graph.
5.564 + ///
5.565 + /// The value of \c n is set to be true in the node-map which stores
5.566 + /// hide information. If \c n was hidden previuosly, then it is shown
5.567 + /// again
5.568 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
5.569 +
5.570 + /// \brief Hide the given edge in the graph.
5.571 + ///
5.572 + /// The value of \c e is set to be true in the edge-map which stores
5.573 + /// hide information. If \c e was hidden previuosly, then it is shown
5.574 + /// again
5.575 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
5.576 +
5.577 + /// \brief Returns true if \c n is hidden.
5.578 + ///
5.579 + /// Returns true if \c n is hidden.
5.580 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
5.581 +
5.582 + /// \brief Returns true if \c e is hidden.
5.583 + ///
5.584 + /// Returns true if \c e is hidden.
5.585 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
5.586 +
5.587 + typedef False NodeNumTag;
5.588 + typedef False EdgeNumTag;
5.589 +
5.590 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
5.591 + Arc findArc(const Node& u, const Node& v,
5.592 + const Arc& prev = INVALID) {
5.593 + Arc arc = Parent::findArc(u, v, prev);
5.594 + while (arc != INVALID && !(*_edge_filter_map)[arc]) {
5.595 + arc = Parent::findArc(u, v, arc);
5.596 + }
5.597 + return arc;
5.598 + }
5.599 + Edge findEdge(const Node& u, const Node& v,
5.600 + const Edge& prev = INVALID) {
5.601 + Edge edge = Parent::findEdge(u, v, prev);
5.602 + while (edge != INVALID && !(*_edge_filter_map)[edge]) {
5.603 + edge = Parent::findEdge(u, v, edge);
5.604 + }
5.605 + return edge;
5.606 + }
5.607 +
5.608 + template <typename _Value>
5.609 + class NodeMap : public SubMapExtender<Adaptor,
5.610 + typename Parent::template NodeMap<_Value> > {
5.611 + public:
5.612 + typedef _Value Value;
5.613 + typedef SubMapExtender<Adaptor, typename Parent::
5.614 + template NodeMap<Value> > MapParent;
5.615 +
5.616 + NodeMap(const Adaptor& adaptor)
5.617 + : MapParent(adaptor) {}
5.618 + NodeMap(const Adaptor& adaptor, const Value& value)
5.619 + : MapParent(adaptor, value) {}
5.620 +
5.621 + private:
5.622 + NodeMap& operator=(const NodeMap& cmap) {
5.623 + return operator=<NodeMap>(cmap);
5.624 + }
5.625 +
5.626 + template <typename CMap>
5.627 + NodeMap& operator=(const CMap& cmap) {
5.628 + MapParent::operator=(cmap);
5.629 + return *this;
5.630 + }
5.631 + };
5.632 +
5.633 + template <typename _Value>
5.634 + class ArcMap : public SubMapExtender<Adaptor,
5.635 + typename Parent::template ArcMap<_Value> > {
5.636 + public:
5.637 + typedef _Value Value;
5.638 + typedef SubMapExtender<Adaptor, typename Parent::
5.639 + template ArcMap<Value> > MapParent;
5.640 +
5.641 + ArcMap(const Adaptor& adaptor)
5.642 + : MapParent(adaptor) {}
5.643 + ArcMap(const Adaptor& adaptor, const Value& value)
5.644 + : MapParent(adaptor, value) {}
5.645 +
5.646 + private:
5.647 + ArcMap& operator=(const ArcMap& cmap) {
5.648 + return operator=<ArcMap>(cmap);
5.649 + }
5.650 +
5.651 + template <typename CMap>
5.652 + ArcMap& operator=(const CMap& cmap) {
5.653 + MapParent::operator=(cmap);
5.654 + return *this;
5.655 + }
5.656 + };
5.657 +
5.658 + template <typename _Value>
5.659 + class EdgeMap : public SubMapExtender<Adaptor,
5.660 + typename Parent::template EdgeMap<_Value> > {
5.661 + public:
5.662 + typedef _Value Value;
5.663 + typedef SubMapExtender<Adaptor, typename Parent::
5.664 + template EdgeMap<Value> > MapParent;
5.665 +
5.666 + EdgeMap(const Adaptor& adaptor)
5.667 + : MapParent(adaptor) {}
5.668 +
5.669 + EdgeMap(const Adaptor& adaptor, const _Value& value)
5.670 + : MapParent(adaptor, value) {}
5.671 +
5.672 + private:
5.673 + EdgeMap& operator=(const EdgeMap& cmap) {
5.674 + return operator=<EdgeMap>(cmap);
5.675 + }
5.676 +
5.677 + template <typename CMap>
5.678 + EdgeMap& operator=(const CMap& cmap) {
5.679 + MapParent::operator=(cmap);
5.680 + return *this;
5.681 + }
5.682 + };
5.683 +
5.684 + };
5.685 +
5.686 + /// \ingroup graph_adaptors
5.687 + ///
5.688 + /// \brief A graph adaptor for hiding nodes and arcs from an
5.689 + /// undirected graph.
5.690 + ///
5.691 + /// SubGraphAdaptor shows the graph with filtered node-set and
5.692 + /// edge-set. If the \c checked parameter is true then it filters
5.693 + /// the edge-set to do not get invalid edges which incident node is
5.694 + /// filtered.
5.695 + ///
5.696 + /// If the \c checked template parameter is false then we have to
5.697 + /// note that the node-iterator cares only the filter on the
5.698 + /// node-set, and the edge-iterator cares only the filter on the
5.699 + /// edge-set. This way the edge-map should filter all arcs which
5.700 + /// has filtered end node.
5.701 + template<typename _Graph, typename NodeFilterMap,
5.702 + typename EdgeFilterMap, bool checked = true>
5.703 + class SubGraphAdaptor :
5.704 + public GraphAdaptorExtender<
5.705 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
5.706 + public:
5.707 + typedef _Graph Graph;
5.708 + typedef GraphAdaptorExtender<
5.709 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
5.710 + protected:
5.711 + SubGraphAdaptor() { }
5.712 + public:
5.713 + SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
5.714 + EdgeFilterMap& edge_filter_map) {
5.715 + setGraph(_graph);
5.716 + setNodeFilterMap(node_filter_map);
5.717 + setEdgeFilterMap(edge_filter_map);
5.718 + }
5.719 + };
5.720 +
5.721 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
5.722 + SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
5.723 + subGraphAdaptor(const Graph& graph,
5.724 + NodeFilterMap& nfm, ArcFilterMap& efm) {
5.725 + return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
5.726 + (graph, nfm, efm);
5.727 + }
5.728 +
5.729 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
5.730 + SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
5.731 + subGraphAdaptor(const Graph& graph,
5.732 + NodeFilterMap& nfm, ArcFilterMap& efm) {
5.733 + return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
5.734 + (graph, nfm, efm);
5.735 + }
5.736 +
5.737 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
5.738 + SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
5.739 + subGraphAdaptor(const Graph& graph,
5.740 + NodeFilterMap& nfm, ArcFilterMap& efm) {
5.741 + return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
5.742 + (graph, nfm, efm);
5.743 + }
5.744 +
5.745 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
5.746 + SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
5.747 + subGraphAdaptor(const Graph& graph,
5.748 + NodeFilterMap& nfm, ArcFilterMap& efm) {
5.749 + return SubGraphAdaptor<const Graph, const NodeFilterMap,
5.750 + const ArcFilterMap>(graph, nfm, efm);
5.751 + }
5.752 +
5.753 + /// \ingroup graph_adaptors
5.754 + ///
5.755 + /// \brief An adaptor for hiding nodes from an graph.
5.756 + ///
5.757 + /// An adaptor for hiding nodes from an graph. This
5.758 + /// adaptor specializes SubGraphAdaptor in the way that only the
5.759 + /// node-set can be filtered. In usual case the checked parameter is
5.760 + /// true, we get the induced subgraph. But if the checked parameter
5.761 + /// is false then we can filter only isolated nodes.
5.762 + template<typename _Graph, typename _NodeFilterMap, bool checked = true>
5.763 + class NodeSubGraphAdaptor :
5.764 + public SubGraphAdaptor<_Graph, _NodeFilterMap,
5.765 + ConstMap<typename _Graph::Edge, bool>, checked> {
5.766 + public:
5.767 + typedef _Graph Graph;
5.768 + typedef _NodeFilterMap NodeFilterMap;
5.769 + typedef SubGraphAdaptor<Graph, NodeFilterMap,
5.770 + ConstMap<typename Graph::Edge, bool> > Parent;
5.771 + protected:
5.772 + ConstMap<typename Graph::Edge, bool> const_true_map;
5.773 +
5.774 + NodeSubGraphAdaptor() : const_true_map(true) {
5.775 + Parent::setEdgeFilterMap(const_true_map);
5.776 + }
5.777 +
5.778 + public:
5.779 + NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
5.780 + Parent(), const_true_map(true) {
5.781 + Parent::setGraph(_graph);
5.782 + Parent::setNodeFilterMap(node_filter_map);
5.783 + Parent::setEdgeFilterMap(const_true_map);
5.784 + }
5.785 + };
5.786 +
5.787 + template<typename Graph, typename NodeFilterMap>
5.788 + NodeSubGraphAdaptor<const Graph, NodeFilterMap>
5.789 + nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
5.790 + return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
5.791 + }
5.792 +
5.793 + template<typename Graph, typename NodeFilterMap>
5.794 + NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
5.795 + nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
5.796 + return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
5.797 + }
5.798 +
5.799 + /// \ingroup graph_adaptors
5.800 + ///
5.801 + /// \brief An adaptor for hiding edges from an graph.
5.802 + ///
5.803 + /// \warning Graph adaptors are in even more experimental state
5.804 + /// than the other parts of the lib. Use them at you own risk.
5.805 + ///
5.806 + /// An adaptor for hiding edges from an graph.
5.807 + /// This adaptor specializes SubGraphAdaptor in the way that
5.808 + /// only the arc-set
5.809 + /// can be filtered.
5.810 + template<typename _Graph, typename _EdgeFilterMap>
5.811 + class EdgeSubGraphAdaptor :
5.812 + public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>,
5.813 + _EdgeFilterMap, false> {
5.814 + public:
5.815 + typedef _Graph Graph;
5.816 + typedef _EdgeFilterMap EdgeFilterMap;
5.817 + typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
5.818 + EdgeFilterMap, false> Parent;
5.819 + protected:
5.820 + ConstMap<typename Graph::Node, bool> const_true_map;
5.821 +
5.822 + EdgeSubGraphAdaptor() : const_true_map(true) {
5.823 + Parent::setNodeFilterMap(const_true_map);
5.824 + }
5.825 +
5.826 + public:
5.827 +
5.828 + EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
5.829 + Parent(), const_true_map(true) {
5.830 + Parent::setGraph(_graph);
5.831 + Parent::setNodeFilterMap(const_true_map);
5.832 + Parent::setEdgeFilterMap(edge_filter_map);
5.833 + }
5.834 +
5.835 + };
5.836 +
5.837 + template<typename Graph, typename EdgeFilterMap>
5.838 + EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
5.839 + edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
5.840 + return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
5.841 + }
5.842 +
5.843 + template<typename Graph, typename EdgeFilterMap>
5.844 + EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
5.845 + edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
5.846 + return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
5.847 + }
5.848 +
5.849 + /// \brief Base of direct graph adaptor
5.850 + ///
5.851 + /// Base class of the direct graph adaptor. All public member
5.852 + /// of this class can be used with the DirGraphAdaptor too.
5.853 + /// \sa DirGraphAdaptor
5.854 + template <typename _Graph, typename _DirectionMap>
5.855 + class DirGraphAdaptorBase {
5.856 + public:
5.857 +
5.858 + typedef _Graph Graph;
5.859 + typedef _DirectionMap DirectionMap;
5.860 +
5.861 + typedef typename Graph::Node Node;
5.862 + typedef typename Graph::Edge Arc;
5.863 +
5.864 + /// \brief Reverse arc
5.865 + ///
5.866 + /// It reverse the given arc. It simply negate the direction in the map.
5.867 + void reverseArc(const Arc& arc) {
5.868 + _direction->set(arc, !(*_direction)[arc]);
5.869 + }
5.870 +
5.871 + void first(Node& i) const { _graph->first(i); }
5.872 + void first(Arc& i) const { _graph->first(i); }
5.873 + void firstIn(Arc& i, const Node& n) const {
5.874 + bool d;
5.875 + _graph->firstInc(i, d, n);
5.876 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
5.877 + }
5.878 + void firstOut(Arc& i, const Node& n ) const {
5.879 + bool d;
5.880 + _graph->firstInc(i, d, n);
5.881 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
5.882 + }
5.883 +
5.884 + void next(Node& i) const { _graph->next(i); }
5.885 + void next(Arc& i) const { _graph->next(i); }
5.886 + void nextIn(Arc& i) const {
5.887 + bool d = !(*_direction)[i];
5.888 + _graph->nextInc(i, d);
5.889 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
5.890 + }
5.891 + void nextOut(Arc& i) const {
5.892 + bool d = (*_direction)[i];
5.893 + _graph->nextInc(i, d);
5.894 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
5.895 + }
5.896 +
5.897 + Node source(const Arc& e) const {
5.898 + return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
5.899 + }
5.900 + Node target(const Arc& e) const {
5.901 + return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
5.902 + }
5.903 +
5.904 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
5.905 + int nodeNum() const { return _graph->nodeNum(); }
5.906 +
5.907 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
5.908 + int arcNum() const { return _graph->edgeNum(); }
5.909 +
5.910 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
5.911 + Arc findArc(const Node& u, const Node& v,
5.912 + const Arc& prev = INVALID) {
5.913 + Arc arc = prev;
5.914 + bool d = arc == INVALID ? true : (*_direction)[arc];
5.915 + if (d) {
5.916 + arc = _graph->findEdge(u, v, arc);
5.917 + while (arc != INVALID && !(*_direction)[arc]) {
5.918 + _graph->findEdge(u, v, arc);
5.919 + }
5.920 + if (arc != INVALID) return arc;
5.921 + }
5.922 + _graph->findEdge(v, u, arc);
5.923 + while (arc != INVALID && (*_direction)[arc]) {
5.924 + _graph->findEdge(u, v, arc);
5.925 + }
5.926 + return arc;
5.927 + }
5.928 +
5.929 + Node addNode() {
5.930 + return Node(_graph->addNode());
5.931 + }
5.932 +
5.933 + Arc addArc(const Node& u, const Node& v) {
5.934 + Arc arc = _graph->addArc(u, v);
5.935 + _direction->set(arc, _graph->source(arc) == u);
5.936 + return arc;
5.937 + }
5.938 +
5.939 + void erase(const Node& i) { _graph->erase(i); }
5.940 + void erase(const Arc& i) { _graph->erase(i); }
5.941 +
5.942 + void clear() { _graph->clear(); }
5.943 +
5.944 + int id(const Node& v) const { return _graph->id(v); }
5.945 + int id(const Arc& e) const { return _graph->id(e); }
5.946 +
5.947 + Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
5.948 + Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
5.949 +
5.950 + int maxNodeId() const { return _graph->maxNodeId(); }
5.951 + int maxArcId() const { return _graph->maxEdgeId(); }
5.952 +
5.953 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
5.954 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
5.955 +
5.956 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
5.957 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
5.958 +
5.959 + template <typename _Value>
5.960 + class NodeMap : public _Graph::template NodeMap<_Value> {
5.961 + public:
5.962 +
5.963 + typedef typename _Graph::template NodeMap<_Value> Parent;
5.964 +
5.965 + explicit NodeMap(const DirGraphAdaptorBase& adapter)
5.966 + : Parent(*adapter._graph) {}
5.967 +
5.968 + NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
5.969 + : Parent(*adapter._graph, value) {}
5.970 +
5.971 + private:
5.972 + NodeMap& operator=(const NodeMap& cmap) {
5.973 + return operator=<NodeMap>(cmap);
5.974 + }
5.975 +
5.976 + template <typename CMap>
5.977 + NodeMap& operator=(const CMap& cmap) {
5.978 + Parent::operator=(cmap);
5.979 + return *this;
5.980 + }
5.981 +
5.982 + };
5.983 +
5.984 + template <typename _Value>
5.985 + class ArcMap : public _Graph::template EdgeMap<_Value> {
5.986 + public:
5.987 +
5.988 + typedef typename Graph::template EdgeMap<_Value> Parent;
5.989 +
5.990 + explicit ArcMap(const DirGraphAdaptorBase& adapter)
5.991 + : Parent(*adapter._graph) { }
5.992 +
5.993 + ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
5.994 + : Parent(*adapter._graph, value) { }
5.995 +
5.996 + private:
5.997 + ArcMap& operator=(const ArcMap& cmap) {
5.998 + return operator=<ArcMap>(cmap);
5.999 + }
5.1000 +
5.1001 + template <typename CMap>
5.1002 + ArcMap& operator=(const CMap& cmap) {
5.1003 + Parent::operator=(cmap);
5.1004 + return *this;
5.1005 + }
5.1006 + };
5.1007 +
5.1008 +
5.1009 +
5.1010 + protected:
5.1011 + Graph* _graph;
5.1012 + DirectionMap* _direction;
5.1013 +
5.1014 + void setDirectionMap(DirectionMap& direction) {
5.1015 + _direction = &direction;
5.1016 + }
5.1017 +
5.1018 + void setGraph(Graph& graph) {
5.1019 + _graph = &graph;
5.1020 + }
5.1021 +
5.1022 + };
5.1023 +
5.1024 +
5.1025 + /// \ingroup graph_adaptors
5.1026 + ///
5.1027 + /// \brief A directed graph is made from an graph by an adaptor
5.1028 + ///
5.1029 + /// This adaptor gives a direction for each edge in the undirected
5.1030 + /// graph. The direction of the arcs stored in the
5.1031 + /// DirectionMap. This map is a bool map on the edges. If
5.1032 + /// the edge is mapped to true then the direction of the directed
5.1033 + /// arc will be the same as the default direction of the edge. The
5.1034 + /// arcs can be easily reverted by the \ref
5.1035 + /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
5.1036 + /// adaptor.
5.1037 + ///
5.1038 + /// It can be used to solve orientation problems on directed graphs.
5.1039 + /// For example how can we orient an graph to get the minimum
5.1040 + /// number of strongly connected components. If we orient the arcs with
5.1041 + /// the dfs algorithm out from the source then we will get such an
5.1042 + /// orientation.
5.1043 + ///
5.1044 + /// We use the \ref DfsVisitor "visitor" interface of the
5.1045 + /// \ref DfsVisit "dfs" algorithm:
5.1046 + ///\code
5.1047 + /// template <typename DirMap>
5.1048 + /// class OrientVisitor : public DfsVisitor<Graph> {
5.1049 + /// public:
5.1050 + ///
5.1051 + /// OrientVisitor(const Graph& graph, DirMap& dirMap)
5.1052 + /// : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
5.1053 + ///
5.1054 + /// void discover(const Arc& arc) {
5.1055 + /// _processed.set(arc, true);
5.1056 + /// _dirMap.set(arc, _graph.direction(arc));
5.1057 + /// }
5.1058 + ///
5.1059 + /// void examine(const Arc& arc) {
5.1060 + /// if (_processed[arc]) return;
5.1061 + /// _processed.set(arc, true);
5.1062 + /// _dirMap.set(arc, _graph.direction(arc));
5.1063 + /// }
5.1064 + ///
5.1065 + /// private:
5.1066 + /// const Graph& _graph;
5.1067 + /// DirMap& _dirMap;
5.1068 + /// Graph::EdgeMap<bool> _processed;
5.1069 + /// };
5.1070 + ///\endcode
5.1071 + ///
5.1072 + /// And now we can use the orientation:
5.1073 + ///\code
5.1074 + /// Graph::EdgeMap<bool> dmap(graph);
5.1075 + ///
5.1076 + /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
5.1077 + /// Visitor visitor(graph, dmap);
5.1078 + ///
5.1079 + /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
5.1080 + ///
5.1081 + /// dfs.run();
5.1082 + ///
5.1083 + /// typedef DirGraphAdaptor<Graph> DGraph;
5.1084 + /// DGraph dgraph(graph, dmap);
5.1085 + ///
5.1086 + /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
5.1087 + /// countBiArcConnectedComponents(graph), "Wrong Orientation");
5.1088 + ///\endcode
5.1089 + ///
5.1090 + /// The number of the bi-connected components is a lower bound for
5.1091 + /// the number of the strongly connected components in the directed
5.1092 + /// graph because if we contract the bi-connected components to
5.1093 + /// nodes we will get a tree therefore we cannot orient arcs in
5.1094 + /// both direction between bi-connected components. In the other way
5.1095 + /// the algorithm will orient one component to be strongly
5.1096 + /// connected. The two relations proof that the assertion will
5.1097 + /// be always true and the found solution is optimal.
5.1098 + ///
5.1099 + /// \sa DirGraphAdaptorBase
5.1100 + /// \sa dirGraphAdaptor
5.1101 + template<typename _Graph,
5.1102 + typename DirectionMap = typename _Graph::template EdgeMap<bool> >
5.1103 + class DirGraphAdaptor :
5.1104 + public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
5.1105 + public:
5.1106 + typedef _Graph Graph;
5.1107 + typedef DigraphAdaptorExtender<
5.1108 + DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
5.1109 + protected:
5.1110 + DirGraphAdaptor() { }
5.1111 + public:
5.1112 +
5.1113 + /// \brief Constructor of the adaptor
5.1114 + ///
5.1115 + /// Constructor of the adaptor
5.1116 + DirGraphAdaptor(Graph& graph, DirectionMap& direction) {
5.1117 + setGraph(graph);
5.1118 + setDirectionMap(direction);
5.1119 + }
5.1120 + };
5.1121 +
5.1122 + /// \brief Just gives back a DirGraphAdaptor
5.1123 + ///
5.1124 + /// Just gives back a DirGraphAdaptor
5.1125 + template<typename Graph, typename DirectionMap>
5.1126 + DirGraphAdaptor<const Graph, DirectionMap>
5.1127 + dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
5.1128 + return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
5.1129 + }
5.1130 +
5.1131 + template<typename Graph, typename DirectionMap>
5.1132 + DirGraphAdaptor<const Graph, const DirectionMap>
5.1133 + dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
5.1134 + return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);
5.1135 + }
5.1136 +
5.1137 +}
5.1138 +
5.1139 +#endif
6.1 --- a/test/Makefile.am Sun Nov 30 09:39:34 2008 +0000
6.2 +++ b/test/Makefile.am Sun Nov 30 18:57:18 2008 +0100
6.3 @@ -15,6 +15,7 @@
6.4 test/dijkstra_test \
6.5 test/dim_test \
6.6 test/error_test \
6.7 + test/graph_adaptor_test \
6.8 test/graph_copy_test \
6.9 test/graph_test \
6.10 test/graph_utils_test \
6.11 @@ -41,6 +42,7 @@
6.12 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
6.13 test_dim_test_SOURCES = test/dim_test.cc
6.14 test_error_test_SOURCES = test/error_test.cc
6.15 +test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
6.16 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
6.17 test_graph_test_SOURCES = test/graph_test.cc
6.18 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/test/graph_adaptor_test.cc Sun Nov 30 18:57:18 2008 +0100
7.3 @@ -0,0 +1,1072 @@
7.4 +/* -*- C++ -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library
7.7 + *
7.8 + * Copyright (C) 2003-2008
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +#include<iostream>
7.23 +#include<lemon/concept_check.h>
7.24 +
7.25 +#include<lemon/list_graph.h>
7.26 +#include<lemon/smart_graph.h>
7.27 +
7.28 +#include<lemon/concepts/digraph.h>
7.29 +#include<lemon/concepts/graph.h>
7.30 +
7.31 +#include<lemon/digraph_adaptor.h>
7.32 +#include<lemon/graph_adaptor.h>
7.33 +
7.34 +#include <limits>
7.35 +#include <lemon/bfs.h>
7.36 +#include <lemon/path.h>
7.37 +
7.38 +#include"test/test_tools.h"
7.39 +#include"test/graph_test.h"
7.40 +
7.41 +using namespace lemon;
7.42 +
7.43 +void checkDigraphAdaptor() {
7.44 + checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();
7.45 +
7.46 + typedef ListDigraph Digraph;
7.47 + typedef DigraphAdaptor<Digraph> Adaptor;
7.48 +
7.49 + Digraph digraph;
7.50 + Adaptor adaptor(digraph);
7.51 +
7.52 + Digraph::Node n1 = digraph.addNode();
7.53 + Digraph::Node n2 = digraph.addNode();
7.54 + Digraph::Node n3 = digraph.addNode();
7.55 +
7.56 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.57 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.58 + Digraph::Arc a3 = digraph.addArc(n2, n3);
7.59 +
7.60 + checkGraphNodeList(adaptor, 3);
7.61 + checkGraphArcList(adaptor, 3);
7.62 + checkGraphConArcList(adaptor, 3);
7.63 +
7.64 + checkGraphOutArcList(adaptor, n1, 2);
7.65 + checkGraphOutArcList(adaptor, n2, 1);
7.66 + checkGraphOutArcList(adaptor, n3, 0);
7.67 +
7.68 + checkGraphInArcList(adaptor, n1, 0);
7.69 + checkGraphInArcList(adaptor, n2, 1);
7.70 + checkGraphInArcList(adaptor, n3, 2);
7.71 +
7.72 + checkNodeIds(adaptor);
7.73 + checkArcIds(adaptor);
7.74 +
7.75 + checkGraphNodeMap(adaptor);
7.76 + checkGraphArcMap(adaptor);
7.77 +}
7.78 +
7.79 +void checkRevDigraphAdaptor() {
7.80 + checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
7.81 +
7.82 + typedef ListDigraph Digraph;
7.83 + typedef RevDigraphAdaptor<Digraph> Adaptor;
7.84 +
7.85 + Digraph digraph;
7.86 + Adaptor adaptor(digraph);
7.87 +
7.88 + Digraph::Node n1 = digraph.addNode();
7.89 + Digraph::Node n2 = digraph.addNode();
7.90 + Digraph::Node n3 = digraph.addNode();
7.91 +
7.92 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.93 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.94 + Digraph::Arc a3 = digraph.addArc(n2, n3);
7.95 +
7.96 + checkGraphNodeList(adaptor, 3);
7.97 + checkGraphArcList(adaptor, 3);
7.98 + checkGraphConArcList(adaptor, 3);
7.99 +
7.100 + checkGraphOutArcList(adaptor, n1, 0);
7.101 + checkGraphOutArcList(adaptor, n2, 1);
7.102 + checkGraphOutArcList(adaptor, n3, 2);
7.103 +
7.104 + checkGraphInArcList(adaptor, n1, 2);
7.105 + checkGraphInArcList(adaptor, n2, 1);
7.106 + checkGraphInArcList(adaptor, n3, 0);
7.107 +
7.108 + checkNodeIds(adaptor);
7.109 + checkArcIds(adaptor);
7.110 +
7.111 + checkGraphNodeMap(adaptor);
7.112 + checkGraphArcMap(adaptor);
7.113 +
7.114 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
7.115 + check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
7.116 + check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
7.117 + }
7.118 +}
7.119 +
7.120 +void checkSubDigraphAdaptor() {
7.121 + checkConcept<concepts::Digraph,
7.122 + SubDigraphAdaptor<concepts::Digraph,
7.123 + concepts::Digraph::NodeMap<bool>,
7.124 + concepts::Digraph::ArcMap<bool> > >();
7.125 +
7.126 + typedef ListDigraph Digraph;
7.127 + typedef Digraph::NodeMap<bool> NodeFilter;
7.128 + typedef Digraph::ArcMap<bool> ArcFilter;
7.129 + typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
7.130 +
7.131 + Digraph digraph;
7.132 + NodeFilter node_filter(digraph);
7.133 + ArcFilter arc_filter(digraph);
7.134 + Adaptor adaptor(digraph, node_filter, arc_filter);
7.135 +
7.136 + Digraph::Node n1 = digraph.addNode();
7.137 + Digraph::Node n2 = digraph.addNode();
7.138 + Digraph::Node n3 = digraph.addNode();
7.139 +
7.140 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.141 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.142 + Digraph::Arc a3 = digraph.addArc(n2, n3);
7.143 +
7.144 + node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
7.145 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
7.146 +
7.147 + checkGraphNodeList(adaptor, 3);
7.148 + checkGraphArcList(adaptor, 3);
7.149 + checkGraphConArcList(adaptor, 3);
7.150 +
7.151 + checkGraphOutArcList(adaptor, n1, 2);
7.152 + checkGraphOutArcList(adaptor, n2, 1);
7.153 + checkGraphOutArcList(adaptor, n3, 0);
7.154 +
7.155 + checkGraphInArcList(adaptor, n1, 0);
7.156 + checkGraphInArcList(adaptor, n2, 1);
7.157 + checkGraphInArcList(adaptor, n3, 2);
7.158 +
7.159 + checkNodeIds(adaptor);
7.160 + checkArcIds(adaptor);
7.161 +
7.162 + checkGraphNodeMap(adaptor);
7.163 + checkGraphArcMap(adaptor);
7.164 +
7.165 + arc_filter[a2] = false;
7.166 +
7.167 + checkGraphNodeList(adaptor, 3);
7.168 + checkGraphArcList(adaptor, 2);
7.169 + checkGraphConArcList(adaptor, 2);
7.170 +
7.171 + checkGraphOutArcList(adaptor, n1, 1);
7.172 + checkGraphOutArcList(adaptor, n2, 1);
7.173 + checkGraphOutArcList(adaptor, n3, 0);
7.174 +
7.175 + checkGraphInArcList(adaptor, n1, 0);
7.176 + checkGraphInArcList(adaptor, n2, 1);
7.177 + checkGraphInArcList(adaptor, n3, 1);
7.178 +
7.179 + checkNodeIds(adaptor);
7.180 + checkArcIds(adaptor);
7.181 +
7.182 + checkGraphNodeMap(adaptor);
7.183 + checkGraphArcMap(adaptor);
7.184 +
7.185 + node_filter[n1] = false;
7.186 +
7.187 + checkGraphNodeList(adaptor, 2);
7.188 + checkGraphArcList(adaptor, 1);
7.189 + checkGraphConArcList(adaptor, 1);
7.190 +
7.191 + checkGraphOutArcList(adaptor, n2, 1);
7.192 + checkGraphOutArcList(adaptor, n3, 0);
7.193 +
7.194 + checkGraphInArcList(adaptor, n2, 0);
7.195 + checkGraphInArcList(adaptor, n3, 1);
7.196 +
7.197 + checkNodeIds(adaptor);
7.198 + checkArcIds(adaptor);
7.199 +
7.200 + checkGraphNodeMap(adaptor);
7.201 + checkGraphArcMap(adaptor);
7.202 +
7.203 + node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
7.204 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
7.205 +
7.206 + checkGraphNodeList(adaptor, 0);
7.207 + checkGraphArcList(adaptor, 0);
7.208 + checkGraphConArcList(adaptor, 0);
7.209 +
7.210 + checkNodeIds(adaptor);
7.211 + checkArcIds(adaptor);
7.212 +
7.213 + checkGraphNodeMap(adaptor);
7.214 + checkGraphArcMap(adaptor);
7.215 +}
7.216 +
7.217 +void checkNodeSubDigraphAdaptor() {
7.218 + checkConcept<concepts::Digraph,
7.219 + NodeSubDigraphAdaptor<concepts::Digraph,
7.220 + concepts::Digraph::NodeMap<bool> > >();
7.221 +
7.222 + typedef ListDigraph Digraph;
7.223 + typedef Digraph::NodeMap<bool> NodeFilter;
7.224 + typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
7.225 +
7.226 + Digraph digraph;
7.227 + NodeFilter node_filter(digraph);
7.228 + Adaptor adaptor(digraph, node_filter);
7.229 +
7.230 + Digraph::Node n1 = digraph.addNode();
7.231 + Digraph::Node n2 = digraph.addNode();
7.232 + Digraph::Node n3 = digraph.addNode();
7.233 +
7.234 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.235 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.236 + Digraph::Arc a3 = digraph.addArc(n2, n3);
7.237 +
7.238 + node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
7.239 +
7.240 + checkGraphNodeList(adaptor, 3);
7.241 + checkGraphArcList(adaptor, 3);
7.242 + checkGraphConArcList(adaptor, 3);
7.243 +
7.244 + checkGraphOutArcList(adaptor, n1, 2);
7.245 + checkGraphOutArcList(adaptor, n2, 1);
7.246 + checkGraphOutArcList(adaptor, n3, 0);
7.247 +
7.248 + checkGraphInArcList(adaptor, n1, 0);
7.249 + checkGraphInArcList(adaptor, n2, 1);
7.250 + checkGraphInArcList(adaptor, n3, 2);
7.251 +
7.252 + checkNodeIds(adaptor);
7.253 + checkArcIds(adaptor);
7.254 +
7.255 + checkGraphNodeMap(adaptor);
7.256 + checkGraphArcMap(adaptor);
7.257 +
7.258 + node_filter[n1] = false;
7.259 +
7.260 + checkGraphNodeList(adaptor, 2);
7.261 + checkGraphArcList(adaptor, 1);
7.262 + checkGraphConArcList(adaptor, 1);
7.263 +
7.264 + checkGraphOutArcList(adaptor, n2, 1);
7.265 + checkGraphOutArcList(adaptor, n3, 0);
7.266 +
7.267 + checkGraphInArcList(adaptor, n2, 0);
7.268 + checkGraphInArcList(adaptor, n3, 1);
7.269 +
7.270 + checkNodeIds(adaptor);
7.271 + checkArcIds(adaptor);
7.272 +
7.273 + checkGraphNodeMap(adaptor);
7.274 + checkGraphArcMap(adaptor);
7.275 +
7.276 + node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
7.277 +
7.278 + checkGraphNodeList(adaptor, 0);
7.279 + checkGraphArcList(adaptor, 0);
7.280 + checkGraphConArcList(adaptor, 0);
7.281 +
7.282 + checkNodeIds(adaptor);
7.283 + checkArcIds(adaptor);
7.284 +
7.285 + checkGraphNodeMap(adaptor);
7.286 + checkGraphArcMap(adaptor);
7.287 +}
7.288 +
7.289 +void checkArcSubDigraphAdaptor() {
7.290 + checkConcept<concepts::Digraph,
7.291 + ArcSubDigraphAdaptor<concepts::Digraph,
7.292 + concepts::Digraph::ArcMap<bool> > >();
7.293 +
7.294 + typedef ListDigraph Digraph;
7.295 + typedef Digraph::ArcMap<bool> ArcFilter;
7.296 + typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
7.297 +
7.298 + Digraph digraph;
7.299 + ArcFilter arc_filter(digraph);
7.300 + Adaptor adaptor(digraph, arc_filter);
7.301 +
7.302 + Digraph::Node n1 = digraph.addNode();
7.303 + Digraph::Node n2 = digraph.addNode();
7.304 + Digraph::Node n3 = digraph.addNode();
7.305 +
7.306 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.307 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.308 + Digraph::Arc a3 = digraph.addArc(n2, n3);
7.309 +
7.310 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
7.311 +
7.312 + checkGraphNodeList(adaptor, 3);
7.313 + checkGraphArcList(adaptor, 3);
7.314 + checkGraphConArcList(adaptor, 3);
7.315 +
7.316 + checkGraphOutArcList(adaptor, n1, 2);
7.317 + checkGraphOutArcList(adaptor, n2, 1);
7.318 + checkGraphOutArcList(adaptor, n3, 0);
7.319 +
7.320 + checkGraphInArcList(adaptor, n1, 0);
7.321 + checkGraphInArcList(adaptor, n2, 1);
7.322 + checkGraphInArcList(adaptor, n3, 2);
7.323 +
7.324 + checkNodeIds(adaptor);
7.325 + checkArcIds(adaptor);
7.326 +
7.327 + checkGraphNodeMap(adaptor);
7.328 + checkGraphArcMap(adaptor);
7.329 +
7.330 + arc_filter[a2] = false;
7.331 +
7.332 + checkGraphNodeList(adaptor, 3);
7.333 + checkGraphArcList(adaptor, 2);
7.334 + checkGraphConArcList(adaptor, 2);
7.335 +
7.336 + checkGraphOutArcList(adaptor, n1, 1);
7.337 + checkGraphOutArcList(adaptor, n2, 1);
7.338 + checkGraphOutArcList(adaptor, n3, 0);
7.339 +
7.340 + checkGraphInArcList(adaptor, n1, 0);
7.341 + checkGraphInArcList(adaptor, n2, 1);
7.342 + checkGraphInArcList(adaptor, n3, 1);
7.343 +
7.344 + checkNodeIds(adaptor);
7.345 + checkArcIds(adaptor);
7.346 +
7.347 + checkGraphNodeMap(adaptor);
7.348 + checkGraphArcMap(adaptor);
7.349 +
7.350 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
7.351 +
7.352 + checkGraphNodeList(adaptor, 3);
7.353 + checkGraphArcList(adaptor, 0);
7.354 + checkGraphConArcList(adaptor, 0);
7.355 +
7.356 + checkNodeIds(adaptor);
7.357 + checkArcIds(adaptor);
7.358 +
7.359 + checkGraphNodeMap(adaptor);
7.360 + checkGraphArcMap(adaptor);
7.361 +}
7.362 +
7.363 +void checkUndirDigraphAdaptor() {
7.364 + checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
7.365 +
7.366 + typedef ListDigraph Digraph;
7.367 + typedef UndirDigraphAdaptor<Digraph> Adaptor;
7.368 +
7.369 + Digraph digraph;
7.370 + Adaptor adaptor(digraph);
7.371 +
7.372 + Digraph::Node n1 = digraph.addNode();
7.373 + Digraph::Node n2 = digraph.addNode();
7.374 + Digraph::Node n3 = digraph.addNode();
7.375 +
7.376 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.377 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.378 + Digraph::Arc a3 = digraph.addArc(n2, n3);
7.379 +
7.380 + checkGraphNodeList(adaptor, 3);
7.381 + checkGraphArcList(adaptor, 6);
7.382 + checkGraphEdgeList(adaptor, 3);
7.383 + checkGraphConArcList(adaptor, 6);
7.384 + checkGraphConEdgeList(adaptor, 3);
7.385 +
7.386 + checkGraphOutArcList(adaptor, n1, 2);
7.387 + checkGraphOutArcList(adaptor, n2, 2);
7.388 + checkGraphOutArcList(adaptor, n3, 2);
7.389 +
7.390 + checkGraphInArcList(adaptor, n1, 2);
7.391 + checkGraphInArcList(adaptor, n2, 2);
7.392 + checkGraphInArcList(adaptor, n3, 2);
7.393 +
7.394 + checkGraphIncEdgeList(adaptor, n1, 2);
7.395 + checkGraphIncEdgeList(adaptor, n2, 2);
7.396 + checkGraphIncEdgeList(adaptor, n3, 2);
7.397 +
7.398 + checkNodeIds(adaptor);
7.399 + checkArcIds(adaptor);
7.400 + checkEdgeIds(adaptor);
7.401 +
7.402 + checkGraphNodeMap(adaptor);
7.403 + checkGraphArcMap(adaptor);
7.404 + checkGraphEdgeMap(adaptor);
7.405 +
7.406 + for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
7.407 + check(adaptor.u(e) == digraph.source(e), "Wrong undir");
7.408 + check(adaptor.v(e) == digraph.target(e), "Wrong undir");
7.409 + }
7.410 +
7.411 +}
7.412 +
7.413 +void checkResDigraphAdaptor() {
7.414 + checkConcept<concepts::Digraph,
7.415 + ResDigraphAdaptor<concepts::Digraph,
7.416 + concepts::Digraph::ArcMap<int>,
7.417 + concepts::Digraph::ArcMap<int> > >();
7.418 +
7.419 + typedef ListDigraph Digraph;
7.420 + typedef Digraph::ArcMap<int> IntArcMap;
7.421 + typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
7.422 +
7.423 + Digraph digraph;
7.424 + IntArcMap capacity(digraph), flow(digraph);
7.425 + Adaptor adaptor(digraph, capacity, flow);
7.426 +
7.427 + Digraph::Node n1 = digraph.addNode();
7.428 + Digraph::Node n2 = digraph.addNode();
7.429 + Digraph::Node n3 = digraph.addNode();
7.430 + Digraph::Node n4 = digraph.addNode();
7.431 +
7.432 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.433 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.434 + Digraph::Arc a3 = digraph.addArc(n1, n4);
7.435 + Digraph::Arc a4 = digraph.addArc(n2, n3);
7.436 + Digraph::Arc a5 = digraph.addArc(n2, n4);
7.437 + Digraph::Arc a6 = digraph.addArc(n3, n4);
7.438 +
7.439 + capacity[a1] = 8;
7.440 + capacity[a2] = 6;
7.441 + capacity[a3] = 4;
7.442 + capacity[a4] = 4;
7.443 + capacity[a5] = 6;
7.444 + capacity[a6] = 10;
7.445 +
7.446 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
7.447 + flow[a] = 0;
7.448 + }
7.449 +
7.450 + checkGraphNodeList(adaptor, 4);
7.451 + checkGraphArcList(adaptor, 6);
7.452 + checkGraphConArcList(adaptor, 6);
7.453 +
7.454 + checkGraphOutArcList(adaptor, n1, 3);
7.455 + checkGraphOutArcList(adaptor, n2, 2);
7.456 + checkGraphOutArcList(adaptor, n3, 1);
7.457 + checkGraphOutArcList(adaptor, n4, 0);
7.458 +
7.459 + checkGraphInArcList(adaptor, n1, 0);
7.460 + checkGraphInArcList(adaptor, n2, 1);
7.461 + checkGraphInArcList(adaptor, n3, 2);
7.462 + checkGraphInArcList(adaptor, n4, 3);
7.463 +
7.464 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
7.465 + flow[a] = capacity[a] / 2;
7.466 + }
7.467 +
7.468 + checkGraphNodeList(adaptor, 4);
7.469 + checkGraphArcList(adaptor, 12);
7.470 + checkGraphConArcList(adaptor, 12);
7.471 +
7.472 + checkGraphOutArcList(adaptor, n1, 3);
7.473 + checkGraphOutArcList(adaptor, n2, 3);
7.474 + checkGraphOutArcList(adaptor, n3, 3);
7.475 + checkGraphOutArcList(adaptor, n4, 3);
7.476 +
7.477 + checkGraphInArcList(adaptor, n1, 3);
7.478 + checkGraphInArcList(adaptor, n2, 3);
7.479 + checkGraphInArcList(adaptor, n3, 3);
7.480 + checkGraphInArcList(adaptor, n4, 3);
7.481 +
7.482 + checkNodeIds(adaptor);
7.483 + checkArcIds(adaptor);
7.484 +
7.485 + checkGraphNodeMap(adaptor);
7.486 + checkGraphArcMap(adaptor);
7.487 +
7.488 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
7.489 + flow[a] = capacity[a];
7.490 + }
7.491 +
7.492 + checkGraphNodeList(adaptor, 4);
7.493 + checkGraphArcList(adaptor, 6);
7.494 + checkGraphConArcList(adaptor, 6);
7.495 +
7.496 + checkGraphOutArcList(adaptor, n1, 0);
7.497 + checkGraphOutArcList(adaptor, n2, 1);
7.498 + checkGraphOutArcList(adaptor, n3, 2);
7.499 + checkGraphOutArcList(adaptor, n4, 3);
7.500 +
7.501 + checkGraphInArcList(adaptor, n1, 3);
7.502 + checkGraphInArcList(adaptor, n2, 2);
7.503 + checkGraphInArcList(adaptor, n3, 1);
7.504 + checkGraphInArcList(adaptor, n4, 0);
7.505 +
7.506 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
7.507 + flow[a] = 0;
7.508 + }
7.509 +
7.510 + int flow_value = 0;
7.511 + while (true) {
7.512 +
7.513 + Bfs<Adaptor> bfs(adaptor);
7.514 + bfs.run(n1, n4);
7.515 +
7.516 + if (!bfs.reached(n4)) break;
7.517 +
7.518 + Path<Adaptor> p = bfs.path(n4);
7.519 +
7.520 + int min = std::numeric_limits<int>::max();
7.521 + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
7.522 + if (adaptor.rescap(a) < min) min = adaptor.rescap(a);
7.523 + }
7.524 +
7.525 + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
7.526 + adaptor.augment(a, min);
7.527 + }
7.528 + flow_value += min;
7.529 + }
7.530 +
7.531 + check(flow_value == 18, "Wrong flow with res graph adaptor");
7.532 +
7.533 +}
7.534 +
7.535 +void checkSplitDigraphAdaptor() {
7.536 + checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
7.537 +
7.538 + typedef ListDigraph Digraph;
7.539 + typedef SplitDigraphAdaptor<Digraph> Adaptor;
7.540 +
7.541 + Digraph digraph;
7.542 + Adaptor adaptor(digraph);
7.543 +
7.544 + Digraph::Node n1 = digraph.addNode();
7.545 + Digraph::Node n2 = digraph.addNode();
7.546 + Digraph::Node n3 = digraph.addNode();
7.547 +
7.548 + Digraph::Arc a1 = digraph.addArc(n1, n2);
7.549 + Digraph::Arc a2 = digraph.addArc(n1, n3);
7.550 + Digraph::Arc a3 = digraph.addArc(n2, n3);
7.551 +
7.552 + checkGraphNodeList(adaptor, 6);
7.553 + checkGraphArcList(adaptor, 6);
7.554 + checkGraphConArcList(adaptor, 6);
7.555 +
7.556 + checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
7.557 + checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
7.558 + checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
7.559 + checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
7.560 + checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
7.561 + checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
7.562 +
7.563 + checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
7.564 + checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
7.565 + checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
7.566 + checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
7.567 + checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
7.568 + checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
7.569 +
7.570 + checkNodeIds(adaptor);
7.571 + checkArcIds(adaptor);
7.572 +
7.573 + checkGraphNodeMap(adaptor);
7.574 + checkGraphArcMap(adaptor);
7.575 +
7.576 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
7.577 + if (adaptor.origArc(a)) {
7.578 + Digraph::Arc oa = a;
7.579 + check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
7.580 + "Wrong split");
7.581 + check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
7.582 + "Wrong split");
7.583 + } else {
7.584 + Digraph::Node on = a;
7.585 + check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
7.586 + check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
7.587 + }
7.588 + }
7.589 +}
7.590 +
7.591 +void checkGraphAdaptor() {
7.592 + checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();
7.593 +
7.594 + typedef ListGraph Graph;
7.595 + typedef GraphAdaptor<Graph> Adaptor;
7.596 +
7.597 + Graph graph;
7.598 + Adaptor adaptor(graph);
7.599 +
7.600 + Graph::Node n1 = graph.addNode();
7.601 + Graph::Node n2 = graph.addNode();
7.602 + Graph::Node n3 = graph.addNode();
7.603 + Graph::Node n4 = graph.addNode();
7.604 +
7.605 + Graph::Edge a1 = graph.addEdge(n1, n2);
7.606 + Graph::Edge a2 = graph.addEdge(n1, n3);
7.607 + Graph::Edge a3 = graph.addEdge(n2, n3);
7.608 + Graph::Edge a4 = graph.addEdge(n3, n4);
7.609 +
7.610 + checkGraphNodeList(adaptor, 4);
7.611 + checkGraphArcList(adaptor, 8);
7.612 + checkGraphEdgeList(adaptor, 4);
7.613 + checkGraphConArcList(adaptor, 8);
7.614 + checkGraphConEdgeList(adaptor, 4);
7.615 +
7.616 + checkGraphOutArcList(adaptor, n1, 2);
7.617 + checkGraphOutArcList(adaptor, n2, 2);
7.618 + checkGraphOutArcList(adaptor, n3, 3);
7.619 + checkGraphOutArcList(adaptor, n4, 1);
7.620 +
7.621 + checkGraphInArcList(adaptor, n1, 2);
7.622 + checkGraphInArcList(adaptor, n2, 2);
7.623 + checkGraphInArcList(adaptor, n3, 3);
7.624 + checkGraphInArcList(adaptor, n4, 1);
7.625 +
7.626 + checkGraphIncEdgeList(adaptor, n1, 2);
7.627 + checkGraphIncEdgeList(adaptor, n2, 2);
7.628 + checkGraphIncEdgeList(adaptor, n3, 3);
7.629 + checkGraphIncEdgeList(adaptor, n4, 1);
7.630 +
7.631 +
7.632 + checkNodeIds(adaptor);
7.633 + checkArcIds(adaptor);
7.634 + checkEdgeIds(adaptor);
7.635 +
7.636 + checkGraphNodeMap(adaptor);
7.637 + checkGraphArcMap(adaptor);
7.638 + checkGraphEdgeMap(adaptor);
7.639 +}
7.640 +
7.641 +void checkSubGraphAdaptor() {
7.642 + checkConcept<concepts::Graph,
7.643 + SubGraphAdaptor<concepts::Graph,
7.644 + concepts::Graph::NodeMap<bool>,
7.645 + concepts::Graph::EdgeMap<bool> > >();
7.646 +
7.647 + typedef ListGraph Graph;
7.648 + typedef Graph::NodeMap<bool> NodeFilter;
7.649 + typedef Graph::EdgeMap<bool> EdgeFilter;
7.650 + typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
7.651 +
7.652 + Graph graph;
7.653 + NodeFilter node_filter(graph);
7.654 + EdgeFilter edge_filter(graph);
7.655 + Adaptor adaptor(graph, node_filter, edge_filter);
7.656 +
7.657 + Graph::Node n1 = graph.addNode();
7.658 + Graph::Node n2 = graph.addNode();
7.659 + Graph::Node n3 = graph.addNode();
7.660 + Graph::Node n4 = graph.addNode();
7.661 +
7.662 + Graph::Edge e1 = graph.addEdge(n1, n2);
7.663 + Graph::Edge e2 = graph.addEdge(n1, n3);
7.664 + Graph::Edge e3 = graph.addEdge(n2, n3);
7.665 + Graph::Edge e4 = graph.addEdge(n3, n4);
7.666 +
7.667 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
7.668 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
7.669 +
7.670 + checkGraphNodeList(adaptor, 4);
7.671 + checkGraphArcList(adaptor, 8);
7.672 + checkGraphEdgeList(adaptor, 4);
7.673 + checkGraphConArcList(adaptor, 8);
7.674 + checkGraphConEdgeList(adaptor, 4);
7.675 +
7.676 + checkGraphOutArcList(adaptor, n1, 2);
7.677 + checkGraphOutArcList(adaptor, n2, 2);
7.678 + checkGraphOutArcList(adaptor, n3, 3);
7.679 + checkGraphOutArcList(adaptor, n4, 1);
7.680 +
7.681 + checkGraphInArcList(adaptor, n1, 2);
7.682 + checkGraphInArcList(adaptor, n2, 2);
7.683 + checkGraphInArcList(adaptor, n3, 3);
7.684 + checkGraphInArcList(adaptor, n4, 1);
7.685 +
7.686 + checkGraphIncEdgeList(adaptor, n1, 2);
7.687 + checkGraphIncEdgeList(adaptor, n2, 2);
7.688 + checkGraphIncEdgeList(adaptor, n3, 3);
7.689 + checkGraphIncEdgeList(adaptor, n4, 1);
7.690 +
7.691 + checkNodeIds(adaptor);
7.692 + checkArcIds(adaptor);
7.693 + checkEdgeIds(adaptor);
7.694 +
7.695 + checkGraphNodeMap(adaptor);
7.696 + checkGraphArcMap(adaptor);
7.697 + checkGraphEdgeMap(adaptor);
7.698 +
7.699 + edge_filter[e2] = false;
7.700 +
7.701 + checkGraphNodeList(adaptor, 4);
7.702 + checkGraphArcList(adaptor, 6);
7.703 + checkGraphEdgeList(adaptor, 3);
7.704 + checkGraphConArcList(adaptor, 6);
7.705 + checkGraphConEdgeList(adaptor, 3);
7.706 +
7.707 + checkGraphOutArcList(adaptor, n1, 1);
7.708 + checkGraphOutArcList(adaptor, n2, 2);
7.709 + checkGraphOutArcList(adaptor, n3, 2);
7.710 + checkGraphOutArcList(adaptor, n4, 1);
7.711 +
7.712 + checkGraphInArcList(adaptor, n1, 1);
7.713 + checkGraphInArcList(adaptor, n2, 2);
7.714 + checkGraphInArcList(adaptor, n3, 2);
7.715 + checkGraphInArcList(adaptor, n4, 1);
7.716 +
7.717 + checkGraphIncEdgeList(adaptor, n1, 1);
7.718 + checkGraphIncEdgeList(adaptor, n2, 2);
7.719 + checkGraphIncEdgeList(adaptor, n3, 2);
7.720 + checkGraphIncEdgeList(adaptor, n4, 1);
7.721 +
7.722 + checkNodeIds(adaptor);
7.723 + checkArcIds(adaptor);
7.724 + checkEdgeIds(adaptor);
7.725 +
7.726 + checkGraphNodeMap(adaptor);
7.727 + checkGraphArcMap(adaptor);
7.728 + checkGraphEdgeMap(adaptor);
7.729 +
7.730 + node_filter[n1] = false;
7.731 +
7.732 + checkGraphNodeList(adaptor, 3);
7.733 + checkGraphArcList(adaptor, 4);
7.734 + checkGraphEdgeList(adaptor, 2);
7.735 + checkGraphConArcList(adaptor, 4);
7.736 + checkGraphConEdgeList(adaptor, 2);
7.737 +
7.738 + checkGraphOutArcList(adaptor, n2, 1);
7.739 + checkGraphOutArcList(adaptor, n3, 2);
7.740 + checkGraphOutArcList(adaptor, n4, 1);
7.741 +
7.742 + checkGraphInArcList(adaptor, n2, 1);
7.743 + checkGraphInArcList(adaptor, n3, 2);
7.744 + checkGraphInArcList(adaptor, n4, 1);
7.745 +
7.746 + checkGraphIncEdgeList(adaptor, n2, 1);
7.747 + checkGraphIncEdgeList(adaptor, n3, 2);
7.748 + checkGraphIncEdgeList(adaptor, n4, 1);
7.749 +
7.750 + checkNodeIds(adaptor);
7.751 + checkArcIds(adaptor);
7.752 + checkEdgeIds(adaptor);
7.753 +
7.754 + checkGraphNodeMap(adaptor);
7.755 + checkGraphArcMap(adaptor);
7.756 + checkGraphEdgeMap(adaptor);
7.757 +
7.758 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
7.759 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
7.760 +
7.761 + checkGraphNodeList(adaptor, 0);
7.762 + checkGraphArcList(adaptor, 0);
7.763 + checkGraphEdgeList(adaptor, 0);
7.764 + checkGraphConArcList(adaptor, 0);
7.765 + checkGraphConEdgeList(adaptor, 0);
7.766 +
7.767 + checkNodeIds(adaptor);
7.768 + checkArcIds(adaptor);
7.769 + checkEdgeIds(adaptor);
7.770 +
7.771 + checkGraphNodeMap(adaptor);
7.772 + checkGraphArcMap(adaptor);
7.773 + checkGraphEdgeMap(adaptor);
7.774 +}
7.775 +
7.776 +void checkNodeSubGraphAdaptor() {
7.777 + checkConcept<concepts::Graph,
7.778 + NodeSubGraphAdaptor<concepts::Graph,
7.779 + concepts::Graph::NodeMap<bool> > >();
7.780 +
7.781 + typedef ListGraph Graph;
7.782 + typedef Graph::NodeMap<bool> NodeFilter;
7.783 + typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
7.784 +
7.785 + Graph graph;
7.786 + NodeFilter node_filter(graph);
7.787 + Adaptor adaptor(graph, node_filter);
7.788 +
7.789 + Graph::Node n1 = graph.addNode();
7.790 + Graph::Node n2 = graph.addNode();
7.791 + Graph::Node n3 = graph.addNode();
7.792 + Graph::Node n4 = graph.addNode();
7.793 +
7.794 + Graph::Edge e1 = graph.addEdge(n1, n2);
7.795 + Graph::Edge e2 = graph.addEdge(n1, n3);
7.796 + Graph::Edge e3 = graph.addEdge(n2, n3);
7.797 + Graph::Edge e4 = graph.addEdge(n3, n4);
7.798 +
7.799 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
7.800 +
7.801 + checkGraphNodeList(adaptor, 4);
7.802 + checkGraphArcList(adaptor, 8);
7.803 + checkGraphEdgeList(adaptor, 4);
7.804 + checkGraphConArcList(adaptor, 8);
7.805 + checkGraphConEdgeList(adaptor, 4);
7.806 +
7.807 + checkGraphOutArcList(adaptor, n1, 2);
7.808 + checkGraphOutArcList(adaptor, n2, 2);
7.809 + checkGraphOutArcList(adaptor, n3, 3);
7.810 + checkGraphOutArcList(adaptor, n4, 1);
7.811 +
7.812 + checkGraphInArcList(adaptor, n1, 2);
7.813 + checkGraphInArcList(adaptor, n2, 2);
7.814 + checkGraphInArcList(adaptor, n3, 3);
7.815 + checkGraphInArcList(adaptor, n4, 1);
7.816 +
7.817 + checkGraphIncEdgeList(adaptor, n1, 2);
7.818 + checkGraphIncEdgeList(adaptor, n2, 2);
7.819 + checkGraphIncEdgeList(adaptor, n3, 3);
7.820 + checkGraphIncEdgeList(adaptor, n4, 1);
7.821 +
7.822 + checkNodeIds(adaptor);
7.823 + checkArcIds(adaptor);
7.824 + checkEdgeIds(adaptor);
7.825 +
7.826 + checkGraphNodeMap(adaptor);
7.827 + checkGraphArcMap(adaptor);
7.828 + checkGraphEdgeMap(adaptor);
7.829 +
7.830 + node_filter[n1] = false;
7.831 +
7.832 + checkGraphNodeList(adaptor, 3);
7.833 + checkGraphArcList(adaptor, 4);
7.834 + checkGraphEdgeList(adaptor, 2);
7.835 + checkGraphConArcList(adaptor, 4);
7.836 + checkGraphConEdgeList(adaptor, 2);
7.837 +
7.838 + checkGraphOutArcList(adaptor, n2, 1);
7.839 + checkGraphOutArcList(adaptor, n3, 2);
7.840 + checkGraphOutArcList(adaptor, n4, 1);
7.841 +
7.842 + checkGraphInArcList(adaptor, n2, 1);
7.843 + checkGraphInArcList(adaptor, n3, 2);
7.844 + checkGraphInArcList(adaptor, n4, 1);
7.845 +
7.846 + checkGraphIncEdgeList(adaptor, n2, 1);
7.847 + checkGraphIncEdgeList(adaptor, n3, 2);
7.848 + checkGraphIncEdgeList(adaptor, n4, 1);
7.849 +
7.850 + checkNodeIds(adaptor);
7.851 + checkArcIds(adaptor);
7.852 + checkEdgeIds(adaptor);
7.853 +
7.854 + checkGraphNodeMap(adaptor);
7.855 + checkGraphArcMap(adaptor);
7.856 + checkGraphEdgeMap(adaptor);
7.857 +
7.858 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
7.859 +
7.860 + checkGraphNodeList(adaptor, 0);
7.861 + checkGraphArcList(adaptor, 0);
7.862 + checkGraphEdgeList(adaptor, 0);
7.863 + checkGraphConArcList(adaptor, 0);
7.864 + checkGraphConEdgeList(adaptor, 0);
7.865 +
7.866 + checkNodeIds(adaptor);
7.867 + checkArcIds(adaptor);
7.868 + checkEdgeIds(adaptor);
7.869 +
7.870 + checkGraphNodeMap(adaptor);
7.871 + checkGraphArcMap(adaptor);
7.872 + checkGraphEdgeMap(adaptor);
7.873 +}
7.874 +
7.875 +void checkEdgeSubGraphAdaptor() {
7.876 + checkConcept<concepts::Graph,
7.877 + EdgeSubGraphAdaptor<concepts::Graph,
7.878 + concepts::Graph::EdgeMap<bool> > >();
7.879 +
7.880 + typedef ListGraph Graph;
7.881 + typedef Graph::EdgeMap<bool> EdgeFilter;
7.882 + typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
7.883 +
7.884 + Graph graph;
7.885 + EdgeFilter edge_filter(graph);
7.886 + Adaptor adaptor(graph, edge_filter);
7.887 +
7.888 + Graph::Node n1 = graph.addNode();
7.889 + Graph::Node n2 = graph.addNode();
7.890 + Graph::Node n3 = graph.addNode();
7.891 + Graph::Node n4 = graph.addNode();
7.892 +
7.893 + Graph::Edge e1 = graph.addEdge(n1, n2);
7.894 + Graph::Edge e2 = graph.addEdge(n1, n3);
7.895 + Graph::Edge e3 = graph.addEdge(n2, n3);
7.896 + Graph::Edge e4 = graph.addEdge(n3, n4);
7.897 +
7.898 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
7.899 +
7.900 + checkGraphNodeList(adaptor, 4);
7.901 + checkGraphArcList(adaptor, 8);
7.902 + checkGraphEdgeList(adaptor, 4);
7.903 + checkGraphConArcList(adaptor, 8);
7.904 + checkGraphConEdgeList(adaptor, 4);
7.905 +
7.906 + checkGraphOutArcList(adaptor, n1, 2);
7.907 + checkGraphOutArcList(adaptor, n2, 2);
7.908 + checkGraphOutArcList(adaptor, n3, 3);
7.909 + checkGraphOutArcList(adaptor, n4, 1);
7.910 +
7.911 + checkGraphInArcList(adaptor, n1, 2);
7.912 + checkGraphInArcList(adaptor, n2, 2);
7.913 + checkGraphInArcList(adaptor, n3, 3);
7.914 + checkGraphInArcList(adaptor, n4, 1);
7.915 +
7.916 + checkGraphIncEdgeList(adaptor, n1, 2);
7.917 + checkGraphIncEdgeList(adaptor, n2, 2);
7.918 + checkGraphIncEdgeList(adaptor, n3, 3);
7.919 + checkGraphIncEdgeList(adaptor, n4, 1);
7.920 +
7.921 + checkNodeIds(adaptor);
7.922 + checkArcIds(adaptor);
7.923 + checkEdgeIds(adaptor);
7.924 +
7.925 + checkGraphNodeMap(adaptor);
7.926 + checkGraphArcMap(adaptor);
7.927 + checkGraphEdgeMap(adaptor);
7.928 +
7.929 + edge_filter[e2] = false;
7.930 +
7.931 + checkGraphNodeList(adaptor, 4);
7.932 + checkGraphArcList(adaptor, 6);
7.933 + checkGraphEdgeList(adaptor, 3);
7.934 + checkGraphConArcList(adaptor, 6);
7.935 + checkGraphConEdgeList(adaptor, 3);
7.936 +
7.937 + checkGraphOutArcList(adaptor, n1, 1);
7.938 + checkGraphOutArcList(adaptor, n2, 2);
7.939 + checkGraphOutArcList(adaptor, n3, 2);
7.940 + checkGraphOutArcList(adaptor, n4, 1);
7.941 +
7.942 + checkGraphInArcList(adaptor, n1, 1);
7.943 + checkGraphInArcList(adaptor, n2, 2);
7.944 + checkGraphInArcList(adaptor, n3, 2);
7.945 + checkGraphInArcList(adaptor, n4, 1);
7.946 +
7.947 + checkGraphIncEdgeList(adaptor, n1, 1);
7.948 + checkGraphIncEdgeList(adaptor, n2, 2);
7.949 + checkGraphIncEdgeList(adaptor, n3, 2);
7.950 + checkGraphIncEdgeList(adaptor, n4, 1);
7.951 +
7.952 + checkNodeIds(adaptor);
7.953 + checkArcIds(adaptor);
7.954 + checkEdgeIds(adaptor);
7.955 +
7.956 + checkGraphNodeMap(adaptor);
7.957 + checkGraphArcMap(adaptor);
7.958 + checkGraphEdgeMap(adaptor);
7.959 +
7.960 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
7.961 +
7.962 + checkGraphNodeList(adaptor, 4);
7.963 + checkGraphArcList(adaptor, 0);
7.964 + checkGraphEdgeList(adaptor, 0);
7.965 + checkGraphConArcList(adaptor, 0);
7.966 + checkGraphConEdgeList(adaptor, 0);
7.967 +
7.968 + checkNodeIds(adaptor);
7.969 + checkArcIds(adaptor);
7.970 + checkEdgeIds(adaptor);
7.971 +
7.972 + checkGraphNodeMap(adaptor);
7.973 + checkGraphArcMap(adaptor);
7.974 + checkGraphEdgeMap(adaptor);
7.975 +}
7.976 +
7.977 +void checkDirGraphAdaptor() {
7.978 + checkConcept<concepts::Digraph,
7.979 + DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
7.980 +
7.981 + typedef ListGraph Graph;
7.982 + typedef ListGraph::EdgeMap<bool> DirMap;
7.983 + typedef DirGraphAdaptor<Graph> Adaptor;
7.984 +
7.985 + Graph graph;
7.986 + DirMap dir(graph, true);
7.987 + Adaptor adaptor(graph, dir);
7.988 +
7.989 + Graph::Node n1 = graph.addNode();
7.990 + Graph::Node n2 = graph.addNode();
7.991 + Graph::Node n3 = graph.addNode();
7.992 +
7.993 + Graph::Edge e1 = graph.addEdge(n1, n2);
7.994 + Graph::Edge e2 = graph.addEdge(n1, n3);
7.995 + Graph::Edge e3 = graph.addEdge(n2, n3);
7.996 +
7.997 + checkGraphNodeList(adaptor, 3);
7.998 + checkGraphArcList(adaptor, 3);
7.999 + checkGraphConArcList(adaptor, 3);
7.1000 +
7.1001 + {
7.1002 + dir[e1] = true;
7.1003 + Adaptor::Node u = adaptor.source(e1);
7.1004 + Adaptor::Node v = adaptor.target(e1);
7.1005 +
7.1006 + dir[e1] = false;
7.1007 + check (u == adaptor.target(e1), "Wrong dir");
7.1008 + check (v == adaptor.source(e1), "Wrong dir");
7.1009 +
7.1010 + check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
7.1011 + dir[e1] = n1 == u;
7.1012 + }
7.1013 +
7.1014 + {
7.1015 + dir[e2] = true;
7.1016 + Adaptor::Node u = adaptor.source(e2);
7.1017 + Adaptor::Node v = adaptor.target(e2);
7.1018 +
7.1019 + dir[e2] = false;
7.1020 + check (u == adaptor.target(e2), "Wrong dir");
7.1021 + check (v == adaptor.source(e2), "Wrong dir");
7.1022 +
7.1023 + check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
7.1024 + dir[e2] = n3 == u;
7.1025 + }
7.1026 +
7.1027 + {
7.1028 + dir[e3] = true;
7.1029 + Adaptor::Node u = adaptor.source(e3);
7.1030 + Adaptor::Node v = adaptor.target(e3);
7.1031 +
7.1032 + dir[e3] = false;
7.1033 + check (u == adaptor.target(e3), "Wrong dir");
7.1034 + check (v == adaptor.source(e3), "Wrong dir");
7.1035 +
7.1036 + check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
7.1037 + dir[e3] = n2 == u;
7.1038 + }
7.1039 +
7.1040 + checkGraphOutArcList(adaptor, n1, 1);
7.1041 + checkGraphOutArcList(adaptor, n2, 1);
7.1042 + checkGraphOutArcList(adaptor, n3, 1);
7.1043 +
7.1044 + checkGraphInArcList(adaptor, n1, 1);
7.1045 + checkGraphInArcList(adaptor, n2, 1);
7.1046 + checkGraphInArcList(adaptor, n3, 1);
7.1047 +
7.1048 + checkNodeIds(adaptor);
7.1049 + checkArcIds(adaptor);
7.1050 +
7.1051 + checkGraphNodeMap(adaptor);
7.1052 + checkGraphArcMap(adaptor);
7.1053 +
7.1054 +}
7.1055 +
7.1056 +
7.1057 +int main(int, const char **) {
7.1058 +
7.1059 + checkDigraphAdaptor();
7.1060 + checkRevDigraphAdaptor();
7.1061 + checkSubDigraphAdaptor();
7.1062 + checkNodeSubDigraphAdaptor();
7.1063 + checkArcSubDigraphAdaptor();
7.1064 + checkUndirDigraphAdaptor();
7.1065 + checkResDigraphAdaptor();
7.1066 + checkSplitDigraphAdaptor();
7.1067 +
7.1068 + checkGraphAdaptor();
7.1069 + checkSubGraphAdaptor();
7.1070 + checkNodeSubGraphAdaptor();
7.1071 + checkEdgeSubGraphAdaptor();
7.1072 + checkDirGraphAdaptor();
7.1073 +
7.1074 + return 0;
7.1075 +}