Port graph adaptors from svn -r3498 (#67)
authorBalazs Dezso <deba@inf.elte.hu>
Sun, 30 Nov 2008 18:57:18 +0100 (2008-11-30)
changeset 41405357da973ce
parent 395 0c5dd7ceda03
child 415 4b6112235fad
Port graph adaptors from svn -r3498 (#67)
lemon/Makefile.am
lemon/bits/graph_adaptor_extender.h
lemon/bits/variant.h
lemon/digraph_adaptor.h
lemon/graph_adaptor.h
test/Makefile.am
test/graph_adaptor_test.cc
     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 +}