lemon/graph_utils.h
changeset 221 64613d8fae28
parent 219 b9c6a47c977b
parent 220 a5d8c039f218
child 222 f9a18c21dba8
     1.1 --- a/lemon/graph_utils.h	Tue Jul 15 18:43:41 2008 +0100
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,2760 +0,0 @@
     1.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 - *
     1.6 - * This file is a part of LEMON, a generic C++ optimization library.
     1.7 - *
     1.8 - * Copyright (C) 2003-2008
     1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 - *
    1.12 - * Permission to use, modify and distribute this software is granted
    1.13 - * provided that this copyright notice appears in all copies. For
    1.14 - * precise terms see the accompanying LICENSE file.
    1.15 - *
    1.16 - * This software is provided "AS IS" with no warranty of any kind,
    1.17 - * express or implied, and with no claim as to its suitability for any
    1.18 - * purpose.
    1.19 - *
    1.20 - */
    1.21 -
    1.22 -#ifndef LEMON_GRAPH_UTILS_H
    1.23 -#define LEMON_GRAPH_UTILS_H
    1.24 -
    1.25 -#include <iterator>
    1.26 -#include <vector>
    1.27 -#include <map>
    1.28 -#include <cmath>
    1.29 -#include <algorithm>
    1.30 -
    1.31 -#include <lemon/bits/invalid.h>
    1.32 -#include <lemon/bits/utility.h>
    1.33 -#include <lemon/maps.h>
    1.34 -#include <lemon/bits/traits.h>
    1.35 -
    1.36 -#include <lemon/bits/alteration_notifier.h>
    1.37 -#include <lemon/bits/default_map.h>
    1.38 -
    1.39 -///\ingroup gutils
    1.40 -///\file
    1.41 -///\brief Graph utilities.
    1.42 -
    1.43 -namespace lemon {
    1.44 -
    1.45 -  /// \addtogroup gutils
    1.46 -  /// @{
    1.47 -
    1.48 -  ///Creates convenience typedefs for the digraph types and iterators
    1.49 -
    1.50 -  ///This \c \#define creates convenience typedefs for the following types
    1.51 -  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    1.52 -  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
    1.53 -  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
    1.54 -  ///
    1.55 -  ///\note If the graph type is a dependent type, ie. the graph type depend
    1.56 -  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
    1.57 -  ///macro.
    1.58 -#define DIGRAPH_TYPEDEFS(Digraph)                                       \
    1.59 -  typedef Digraph::Node Node;                                           \
    1.60 -  typedef Digraph::NodeIt NodeIt;                                       \
    1.61 -  typedef Digraph::Arc Arc;                                             \
    1.62 -  typedef Digraph::ArcIt ArcIt;                                         \
    1.63 -  typedef Digraph::InArcIt InArcIt;                                     \
    1.64 -  typedef Digraph::OutArcIt OutArcIt;                                   \
    1.65 -  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
    1.66 -  typedef Digraph::NodeMap<int> IntNodeMap;                             \
    1.67 -  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
    1.68 -  typedef Digraph::ArcMap<bool> BoolArcMap;                             \
    1.69 -  typedef Digraph::ArcMap<int> IntArcMap;                               \
    1.70 -  typedef Digraph::ArcMap<double> DoubleArcMap
    1.71 -
    1.72 -  ///Creates convenience typedefs for the digraph types and iterators
    1.73 -
    1.74 -  ///\see DIGRAPH_TYPEDEFS
    1.75 -  ///
    1.76 -  ///\note Use this macro, if the graph type is a dependent type,
    1.77 -  ///ie. the graph type depend on a template parameter.
    1.78 -#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
    1.79 -  typedef typename Digraph::Node Node;                                  \
    1.80 -  typedef typename Digraph::NodeIt NodeIt;                              \
    1.81 -  typedef typename Digraph::Arc Arc;                                    \
    1.82 -  typedef typename Digraph::ArcIt ArcIt;                                \
    1.83 -  typedef typename Digraph::InArcIt InArcIt;                            \
    1.84 -  typedef typename Digraph::OutArcIt OutArcIt;                          \
    1.85 -  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
    1.86 -  typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
    1.87 -  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
    1.88 -  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
    1.89 -  typedef typename Digraph::template ArcMap<int> IntArcMap;             \
    1.90 -  typedef typename Digraph::template ArcMap<double> DoubleArcMap
    1.91 -
    1.92 -  ///Creates convenience typedefs for the graph types and iterators
    1.93 -
    1.94 -  ///This \c \#define creates the same convenience typedefs as defined
    1.95 -  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
    1.96 -  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
    1.97 -  ///\c DoubleEdgeMap.
    1.98 -  ///
    1.99 -  ///\note If the graph type is a dependent type, ie. the graph type depend
   1.100 -  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
   1.101 -  ///macro.
   1.102 -#define GRAPH_TYPEDEFS(Graph)                                           \
   1.103 -  DIGRAPH_TYPEDEFS(Graph);                                              \
   1.104 -  typedef Graph::Edge Edge;                                             \
   1.105 -  typedef Graph::EdgeIt EdgeIt;                                         \
   1.106 -  typedef Graph::IncEdgeIt IncEdgeIt;                                   \
   1.107 -  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
   1.108 -  typedef Graph::EdgeMap<int> IntEdgeMap;                               \
   1.109 -  typedef Graph::EdgeMap<double> DoubleEdgeMap
   1.110 -
   1.111 -  ///Creates convenience typedefs for the graph types and iterators
   1.112 -
   1.113 -  ///\see GRAPH_TYPEDEFS
   1.114 -  ///
   1.115 -  ///\note Use this macro, if the graph type is a dependent type,
   1.116 -  ///ie. the graph type depend on a template parameter.
   1.117 -#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
   1.118 -  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
   1.119 -  typedef typename Graph::Edge Edge;                                    \
   1.120 -  typedef typename Graph::EdgeIt EdgeIt;                                \
   1.121 -  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
   1.122 -  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
   1.123 -  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
   1.124 -  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
   1.125 -
   1.126 -  /// \brief Function to count the items in the graph.
   1.127 -  ///
   1.128 -  /// This function counts the items (nodes, arcs etc) in the graph.
   1.129 -  /// The complexity of the function is O(n) because
   1.130 -  /// it iterates on all of the items.
   1.131 -  template <typename Graph, typename Item>
   1.132 -  inline int countItems(const Graph& g) {
   1.133 -    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
   1.134 -    int num = 0;
   1.135 -    for (ItemIt it(g); it != INVALID; ++it) {
   1.136 -      ++num;
   1.137 -    }
   1.138 -    return num;
   1.139 -  }
   1.140 -
   1.141 -  // Node counting:
   1.142 -
   1.143 -  namespace _graph_utils_bits {
   1.144 -
   1.145 -    template <typename Graph, typename Enable = void>
   1.146 -    struct CountNodesSelector {
   1.147 -      static int count(const Graph &g) {
   1.148 -        return countItems<Graph, typename Graph::Node>(g);
   1.149 -      }
   1.150 -    };
   1.151 -
   1.152 -    template <typename Graph>
   1.153 -    struct CountNodesSelector<
   1.154 -      Graph, typename
   1.155 -      enable_if<typename Graph::NodeNumTag, void>::type>
   1.156 -    {
   1.157 -      static int count(const Graph &g) {
   1.158 -        return g.nodeNum();
   1.159 -      }
   1.160 -    };
   1.161 -  }
   1.162 -
   1.163 -  /// \brief Function to count the nodes in the graph.
   1.164 -  ///
   1.165 -  /// This function counts the nodes in the graph.
   1.166 -  /// The complexity of the function is O(n) but for some
   1.167 -  /// graph structures it is specialized to run in O(1).
   1.168 -  ///
   1.169 -  /// If the graph contains a \e nodeNum() member function and a
   1.170 -  /// \e NodeNumTag tag then this function calls directly the member
   1.171 -  /// function to query the cardinality of the node set.
   1.172 -  template <typename Graph>
   1.173 -  inline int countNodes(const Graph& g) {
   1.174 -    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
   1.175 -  }
   1.176 -
   1.177 -  // Arc counting:
   1.178 -
   1.179 -  namespace _graph_utils_bits {
   1.180 -
   1.181 -    template <typename Graph, typename Enable = void>
   1.182 -    struct CountArcsSelector {
   1.183 -      static int count(const Graph &g) {
   1.184 -        return countItems<Graph, typename Graph::Arc>(g);
   1.185 -      }
   1.186 -    };
   1.187 -
   1.188 -    template <typename Graph>
   1.189 -    struct CountArcsSelector<
   1.190 -      Graph,
   1.191 -      typename enable_if<typename Graph::ArcNumTag, void>::type>
   1.192 -    {
   1.193 -      static int count(const Graph &g) {
   1.194 -        return g.arcNum();
   1.195 -      }
   1.196 -    };
   1.197 -  }
   1.198 -
   1.199 -  /// \brief Function to count the arcs in the graph.
   1.200 -  ///
   1.201 -  /// This function counts the arcs in the graph.
   1.202 -  /// The complexity of the function is O(e) but for some
   1.203 -  /// graph structures it is specialized to run in O(1).
   1.204 -  ///
   1.205 -  /// If the graph contains a \e arcNum() member function and a
   1.206 -  /// \e EdgeNumTag tag then this function calls directly the member
   1.207 -  /// function to query the cardinality of the arc set.
   1.208 -  template <typename Graph>
   1.209 -  inline int countArcs(const Graph& g) {
   1.210 -    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
   1.211 -  }
   1.212 -
   1.213 -  // Edge counting:
   1.214 -  namespace _graph_utils_bits {
   1.215 -
   1.216 -    template <typename Graph, typename Enable = void>
   1.217 -    struct CountEdgesSelector {
   1.218 -      static int count(const Graph &g) {
   1.219 -        return countItems<Graph, typename Graph::Edge>(g);
   1.220 -      }
   1.221 -    };
   1.222 -
   1.223 -    template <typename Graph>
   1.224 -    struct CountEdgesSelector<
   1.225 -      Graph,
   1.226 -      typename enable_if<typename Graph::EdgeNumTag, void>::type>
   1.227 -    {
   1.228 -      static int count(const Graph &g) {
   1.229 -        return g.edgeNum();
   1.230 -      }
   1.231 -    };
   1.232 -  }
   1.233 -
   1.234 -  /// \brief Function to count the edges in the graph.
   1.235 -  ///
   1.236 -  /// This function counts the edges in the graph.
   1.237 -  /// The complexity of the function is O(m) but for some
   1.238 -  /// graph structures it is specialized to run in O(1).
   1.239 -  ///
   1.240 -  /// If the graph contains a \e edgeNum() member function and a
   1.241 -  /// \e EdgeNumTag tag then this function calls directly the member
   1.242 -  /// function to query the cardinality of the edge set.
   1.243 -  template <typename Graph>
   1.244 -  inline int countEdges(const Graph& g) {
   1.245 -    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
   1.246 -
   1.247 -  }
   1.248 -
   1.249 -
   1.250 -  template <typename Graph, typename DegIt>
   1.251 -  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   1.252 -    int num = 0;
   1.253 -    for (DegIt it(_g, _n); it != INVALID; ++it) {
   1.254 -      ++num;
   1.255 -    }
   1.256 -    return num;
   1.257 -  }
   1.258 -
   1.259 -  /// \brief Function to count the number of the out-arcs from node \c n.
   1.260 -  ///
   1.261 -  /// This function counts the number of the out-arcs from node \c n
   1.262 -  /// in the graph.
   1.263 -  template <typename Graph>
   1.264 -  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
   1.265 -    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
   1.266 -  }
   1.267 -
   1.268 -  /// \brief Function to count the number of the in-arcs to node \c n.
   1.269 -  ///
   1.270 -  /// This function counts the number of the in-arcs to node \c n
   1.271 -  /// in the graph.
   1.272 -  template <typename Graph>
   1.273 -  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
   1.274 -    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
   1.275 -  }
   1.276 -
   1.277 -  /// \brief Function to count the number of the inc-edges to node \c n.
   1.278 -  ///
   1.279 -  /// This function counts the number of the inc-edges to node \c n
   1.280 -  /// in the graph.
   1.281 -  template <typename Graph>
   1.282 -  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
   1.283 -    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
   1.284 -  }
   1.285 -
   1.286 -  namespace _graph_utils_bits {
   1.287 -
   1.288 -    template <typename Graph, typename Enable = void>
   1.289 -    struct FindArcSelector {
   1.290 -      typedef typename Graph::Node Node;
   1.291 -      typedef typename Graph::Arc Arc;
   1.292 -      static Arc find(const Graph &g, Node u, Node v, Arc e) {
   1.293 -        if (e == INVALID) {
   1.294 -          g.firstOut(e, u);
   1.295 -        } else {
   1.296 -          g.nextOut(e);
   1.297 -        }
   1.298 -        while (e != INVALID && g.target(e) != v) {
   1.299 -          g.nextOut(e);
   1.300 -        }
   1.301 -        return e;
   1.302 -      }
   1.303 -    };
   1.304 -
   1.305 -    template <typename Graph>
   1.306 -    struct FindArcSelector<
   1.307 -      Graph,
   1.308 -      typename enable_if<typename Graph::FindEdgeTag, void>::type>
   1.309 -    {
   1.310 -      typedef typename Graph::Node Node;
   1.311 -      typedef typename Graph::Arc Arc;
   1.312 -      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
   1.313 -        return g.findArc(u, v, prev);
   1.314 -      }
   1.315 -    };
   1.316 -  }
   1.317 -
   1.318 -  /// \brief Finds an arc between two nodes of a graph.
   1.319 -  ///
   1.320 -  /// Finds an arc from node \c u to node \c v in graph \c g.
   1.321 -  ///
   1.322 -  /// If \c prev is \ref INVALID (this is the default value), then
   1.323 -  /// it finds the first arc from \c u to \c v. Otherwise it looks for
   1.324 -  /// the next arc from \c u to \c v after \c prev.
   1.325 -  /// \return The found arc or \ref INVALID if there is no such an arc.
   1.326 -  ///
   1.327 -  /// Thus you can iterate through each arc from \c u to \c v as it follows.
   1.328 -  ///\code
   1.329 -  /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
   1.330 -  ///   ...
   1.331 -  /// }
   1.332 -  ///\endcode
   1.333 -  ///
   1.334 -  ///\sa ArcLookUp
   1.335 -  ///\sa AllArcLookUp
   1.336 -  ///\sa DynArcLookUp
   1.337 -  ///\sa ConArcIt
   1.338 -  template <typename Graph>
   1.339 -  inline typename Graph::Arc
   1.340 -  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
   1.341 -           typename Graph::Arc prev = INVALID) {
   1.342 -    return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
   1.343 -  }
   1.344 -
   1.345 -  /// \brief Iterator for iterating on arcs connected the same nodes.
   1.346 -  ///
   1.347 -  /// Iterator for iterating on arcs connected the same nodes. It is
   1.348 -  /// higher level interface for the findArc() function. You can
   1.349 -  /// use it the following way:
   1.350 -  ///\code
   1.351 -  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
   1.352 -  ///   ...
   1.353 -  /// }
   1.354 -  ///\endcode
   1.355 -  ///
   1.356 -  ///\sa findArc()
   1.357 -  ///\sa ArcLookUp
   1.358 -  ///\sa AllArcLookUp
   1.359 -  ///\sa DynArcLookUp
   1.360 -  template <typename _Graph>
   1.361 -  class ConArcIt : public _Graph::Arc {
   1.362 -  public:
   1.363 -
   1.364 -    typedef _Graph Graph;
   1.365 -    typedef typename Graph::Arc Parent;
   1.366 -
   1.367 -    typedef typename Graph::Arc Arc;
   1.368 -    typedef typename Graph::Node Node;
   1.369 -
   1.370 -    /// \brief Constructor.
   1.371 -    ///
   1.372 -    /// Construct a new ConArcIt iterating on the arcs which
   1.373 -    /// connects the \c u and \c v node.
   1.374 -    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
   1.375 -      Parent::operator=(findArc(_graph, u, v));
   1.376 -    }
   1.377 -
   1.378 -    /// \brief Constructor.
   1.379 -    ///
   1.380 -    /// Construct a new ConArcIt which continues the iterating from
   1.381 -    /// the \c e arc.
   1.382 -    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
   1.383 -
   1.384 -    /// \brief Increment operator.
   1.385 -    ///
   1.386 -    /// It increments the iterator and gives back the next arc.
   1.387 -    ConArcIt& operator++() {
   1.388 -      Parent::operator=(findArc(_graph, _graph.source(*this),
   1.389 -                                _graph.target(*this), *this));
   1.390 -      return *this;
   1.391 -    }
   1.392 -  private:
   1.393 -    const Graph& _graph;
   1.394 -  };
   1.395 -
   1.396 -  namespace _graph_utils_bits {
   1.397 -
   1.398 -    template <typename Graph, typename Enable = void>
   1.399 -    struct FindEdgeSelector {
   1.400 -      typedef typename Graph::Node Node;
   1.401 -      typedef typename Graph::Edge Edge;
   1.402 -      static Edge find(const Graph &g, Node u, Node v, Edge e) {
   1.403 -        bool b;
   1.404 -        if (u != v) {
   1.405 -          if (e == INVALID) {
   1.406 -            g.firstInc(e, b, u);
   1.407 -          } else {
   1.408 -            b = g.u(e) == u;
   1.409 -            g.nextInc(e, b);
   1.410 -          }
   1.411 -          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
   1.412 -            g.nextInc(e, b);
   1.413 -          }
   1.414 -        } else {
   1.415 -          if (e == INVALID) {
   1.416 -            g.firstInc(e, b, u);
   1.417 -          } else {
   1.418 -            b = true;
   1.419 -            g.nextInc(e, b);
   1.420 -          }
   1.421 -          while (e != INVALID && (!b || g.v(e) != v)) {
   1.422 -            g.nextInc(e, b);
   1.423 -          }
   1.424 -        }
   1.425 -        return e;
   1.426 -      }
   1.427 -    };
   1.428 -
   1.429 -    template <typename Graph>
   1.430 -    struct FindEdgeSelector<
   1.431 -      Graph,
   1.432 -      typename enable_if<typename Graph::FindEdgeTag, void>::type>
   1.433 -    {
   1.434 -      typedef typename Graph::Node Node;
   1.435 -      typedef typename Graph::Edge Edge;
   1.436 -      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
   1.437 -        return g.findEdge(u, v, prev);
   1.438 -      }
   1.439 -    };
   1.440 -  }
   1.441 -
   1.442 -  /// \brief Finds an edge between two nodes of a graph.
   1.443 -  ///
   1.444 -  /// Finds an edge from node \c u to node \c v in graph \c g.
   1.445 -  /// If the node \c u and node \c v is equal then each loop edge
   1.446 -  /// will be enumerated once.
   1.447 -  ///
   1.448 -  /// If \c prev is \ref INVALID (this is the default value), then
   1.449 -  /// it finds the first arc from \c u to \c v. Otherwise it looks for
   1.450 -  /// the next arc from \c u to \c v after \c prev.
   1.451 -  /// \return The found arc or \ref INVALID if there is no such an arc.
   1.452 -  ///
   1.453 -  /// Thus you can iterate through each arc from \c u to \c v as it follows.
   1.454 -  ///\code
   1.455 -  /// for(Edge e = findEdge(g,u,v); e != INVALID;
   1.456 -  ///     e = findEdge(g,u,v,e)) {
   1.457 -  ///   ...
   1.458 -  /// }
   1.459 -  ///\endcode
   1.460 -  ///
   1.461 -  ///\sa ConEdgeIt
   1.462 -
   1.463 -  template <typename Graph>
   1.464 -  inline typename Graph::Edge
   1.465 -  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
   1.466 -            typename Graph::Edge p = INVALID) {
   1.467 -    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
   1.468 -  }
   1.469 -
   1.470 -  /// \brief Iterator for iterating on edges connected the same nodes.
   1.471 -  ///
   1.472 -  /// Iterator for iterating on edges connected the same nodes. It is
   1.473 -  /// higher level interface for the findEdge() function. You can
   1.474 -  /// use it the following way:
   1.475 -  ///\code
   1.476 -  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
   1.477 -  ///   ...
   1.478 -  /// }
   1.479 -  ///\endcode
   1.480 -  ///
   1.481 -  ///\sa findEdge()
   1.482 -  template <typename _Graph>
   1.483 -  class ConEdgeIt : public _Graph::Edge {
   1.484 -  public:
   1.485 -
   1.486 -    typedef _Graph Graph;
   1.487 -    typedef typename Graph::Edge Parent;
   1.488 -
   1.489 -    typedef typename Graph::Edge Edge;
   1.490 -    typedef typename Graph::Node Node;
   1.491 -
   1.492 -    /// \brief Constructor.
   1.493 -    ///
   1.494 -    /// Construct a new ConEdgeIt iterating on the edges which
   1.495 -    /// connects the \c u and \c v node.
   1.496 -    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
   1.497 -      Parent::operator=(findEdge(_graph, u, v));
   1.498 -    }
   1.499 -
   1.500 -    /// \brief Constructor.
   1.501 -    ///
   1.502 -    /// Construct a new ConEdgeIt which continues the iterating from
   1.503 -    /// the \c e edge.
   1.504 -    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
   1.505 -
   1.506 -    /// \brief Increment operator.
   1.507 -    ///
   1.508 -    /// It increments the iterator and gives back the next edge.
   1.509 -    ConEdgeIt& operator++() {
   1.510 -      Parent::operator=(findEdge(_graph, _graph.u(*this),
   1.511 -                                 _graph.v(*this), *this));
   1.512 -      return *this;
   1.513 -    }
   1.514 -  private:
   1.515 -    const Graph& _graph;
   1.516 -  };
   1.517 -
   1.518 -  namespace _graph_utils_bits {
   1.519 -
   1.520 -    template <typename Digraph, typename Item, typename RefMap>
   1.521 -    class MapCopyBase {
   1.522 -    public:
   1.523 -      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
   1.524 -
   1.525 -      virtual ~MapCopyBase() {}
   1.526 -    };
   1.527 -
   1.528 -    template <typename Digraph, typename Item, typename RefMap,
   1.529 -              typename ToMap, typename FromMap>
   1.530 -    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.531 -    public:
   1.532 -
   1.533 -      MapCopy(ToMap& tmap, const FromMap& map)
   1.534 -        : _tmap(tmap), _map(map) {}
   1.535 -
   1.536 -      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   1.537 -        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   1.538 -        for (ItemIt it(digraph); it != INVALID; ++it) {
   1.539 -          _tmap.set(refMap[it], _map[it]);
   1.540 -        }
   1.541 -      }
   1.542 -
   1.543 -    private:
   1.544 -      ToMap& _tmap;
   1.545 -      const FromMap& _map;
   1.546 -    };
   1.547 -
   1.548 -    template <typename Digraph, typename Item, typename RefMap, typename It>
   1.549 -    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.550 -    public:
   1.551 -
   1.552 -      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
   1.553 -
   1.554 -      virtual void copy(const Digraph&, const RefMap& refMap) {
   1.555 -        _it = refMap[_item];
   1.556 -      }
   1.557 -
   1.558 -    private:
   1.559 -      It& _it;
   1.560 -      Item _item;
   1.561 -    };
   1.562 -
   1.563 -    template <typename Digraph, typename Item, typename RefMap, typename Ref>
   1.564 -    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.565 -    public:
   1.566 -
   1.567 -      RefCopy(Ref& map) : _map(map) {}
   1.568 -
   1.569 -      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   1.570 -        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   1.571 -        for (ItemIt it(digraph); it != INVALID; ++it) {
   1.572 -          _map.set(it, refMap[it]);
   1.573 -        }
   1.574 -      }
   1.575 -
   1.576 -    private:
   1.577 -      Ref& _map;
   1.578 -    };
   1.579 -
   1.580 -    template <typename Digraph, typename Item, typename RefMap,
   1.581 -              typename CrossRef>
   1.582 -    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.583 -    public:
   1.584 -
   1.585 -      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
   1.586 -
   1.587 -      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   1.588 -        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   1.589 -        for (ItemIt it(digraph); it != INVALID; ++it) {
   1.590 -          _cmap.set(refMap[it], it);
   1.591 -        }
   1.592 -      }
   1.593 -
   1.594 -    private:
   1.595 -      CrossRef& _cmap;
   1.596 -    };
   1.597 -
   1.598 -    template <typename Digraph, typename Enable = void>
   1.599 -    struct DigraphCopySelector {
   1.600 -      template <typename From, typename NodeRefMap, typename ArcRefMap>
   1.601 -      static void copy(Digraph &to, const From& from,
   1.602 -                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   1.603 -        for (typename From::NodeIt it(from); it != INVALID; ++it) {
   1.604 -          nodeRefMap[it] = to.addNode();
   1.605 -        }
   1.606 -        for (typename From::ArcIt it(from); it != INVALID; ++it) {
   1.607 -          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
   1.608 -                                    nodeRefMap[from.target(it)]);
   1.609 -        }
   1.610 -      }
   1.611 -    };
   1.612 -
   1.613 -    template <typename Digraph>
   1.614 -    struct DigraphCopySelector<
   1.615 -      Digraph,
   1.616 -      typename enable_if<typename Digraph::BuildTag, void>::type>
   1.617 -    {
   1.618 -      template <typename From, typename NodeRefMap, typename ArcRefMap>
   1.619 -      static void copy(Digraph &to, const From& from,
   1.620 -                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   1.621 -        to.build(from, nodeRefMap, arcRefMap);
   1.622 -      }
   1.623 -    };
   1.624 -
   1.625 -    template <typename Graph, typename Enable = void>
   1.626 -    struct GraphCopySelector {
   1.627 -      template <typename From, typename NodeRefMap, typename EdgeRefMap>
   1.628 -      static void copy(Graph &to, const From& from,
   1.629 -                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   1.630 -        for (typename From::NodeIt it(from); it != INVALID; ++it) {
   1.631 -          nodeRefMap[it] = to.addNode();
   1.632 -        }
   1.633 -        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
   1.634 -          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
   1.635 -                                      nodeRefMap[from.v(it)]);
   1.636 -        }
   1.637 -      }
   1.638 -    };
   1.639 -
   1.640 -    template <typename Graph>
   1.641 -    struct GraphCopySelector<
   1.642 -      Graph,
   1.643 -      typename enable_if<typename Graph::BuildTag, void>::type>
   1.644 -    {
   1.645 -      template <typename From, typename NodeRefMap, typename EdgeRefMap>
   1.646 -      static void copy(Graph &to, const From& from,
   1.647 -                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   1.648 -        to.build(from, nodeRefMap, edgeRefMap);
   1.649 -      }
   1.650 -    };
   1.651 -
   1.652 -  }
   1.653 -
   1.654 -  /// \brief Class to copy a digraph.
   1.655 -  ///
   1.656 -  /// Class to copy a digraph to another digraph (duplicate a digraph). The
   1.657 -  /// simplest way of using it is through the \c copyDigraph() function.
   1.658 -  ///
   1.659 -  /// This class not just make a copy of a graph, but it can create
   1.660 -  /// references and cross references between the nodes and arcs of
   1.661 -  /// the two graphs, it can copy maps for use with the newly created
   1.662 -  /// graph and copy nodes and arcs.
   1.663 -  ///
   1.664 -  /// To make a copy from a graph, first an instance of DigraphCopy
   1.665 -  /// should be created, then the data belongs to the graph should
   1.666 -  /// assigned to copy. In the end, the \c run() member should be
   1.667 -  /// called.
   1.668 -  ///
   1.669 -  /// The next code copies a graph with several data:
   1.670 -  ///\code
   1.671 -  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
   1.672 -  ///  // create a reference for the nodes
   1.673 -  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   1.674 -  ///  dc.nodeRef(nr);
   1.675 -  ///  // create a cross reference (inverse) for the arcs
   1.676 -  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
   1.677 -  ///  dc.arcCrossRef(acr);
   1.678 -  ///  // copy an arc map
   1.679 -  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
   1.680 -  ///  NewGraph::ArcMap<double> namap(new_graph);
   1.681 -  ///  dc.arcMap(namap, oamap);
   1.682 -  ///  // copy a node
   1.683 -  ///  OrigGraph::Node on;
   1.684 -  ///  NewGraph::Node nn;
   1.685 -  ///  dc.node(nn, on);
   1.686 -  ///  // Executions of copy
   1.687 -  ///  dc.run();
   1.688 -  ///\endcode
   1.689 -  template <typename To, typename From>
   1.690 -  class DigraphCopy {
   1.691 -  private:
   1.692 -
   1.693 -    typedef typename From::Node Node;
   1.694 -    typedef typename From::NodeIt NodeIt;
   1.695 -    typedef typename From::Arc Arc;
   1.696 -    typedef typename From::ArcIt ArcIt;
   1.697 -
   1.698 -    typedef typename To::Node TNode;
   1.699 -    typedef typename To::Arc TArc;
   1.700 -
   1.701 -    typedef typename From::template NodeMap<TNode> NodeRefMap;
   1.702 -    typedef typename From::template ArcMap<TArc> ArcRefMap;
   1.703 -
   1.704 -
   1.705 -  public:
   1.706 -
   1.707 -
   1.708 -    /// \brief Constructor for the DigraphCopy.
   1.709 -    ///
   1.710 -    /// It copies the content of the \c _from digraph into the
   1.711 -    /// \c _to digraph.
   1.712 -    DigraphCopy(To& to, const From& from)
   1.713 -      : _from(from), _to(to) {}
   1.714 -
   1.715 -    /// \brief Destructor of the DigraphCopy
   1.716 -    ///
   1.717 -    /// Destructor of the DigraphCopy
   1.718 -    ~DigraphCopy() {
   1.719 -      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.720 -        delete _node_maps[i];
   1.721 -      }
   1.722 -      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.723 -        delete _arc_maps[i];
   1.724 -      }
   1.725 -
   1.726 -    }
   1.727 -
   1.728 -    /// \brief Copies the node references into the given map.
   1.729 -    ///
   1.730 -    /// Copies the node references into the given map. The parameter
   1.731 -    /// should be a map, which key type is the Node type of the source
   1.732 -    /// graph, while the value type is the Node type of the
   1.733 -    /// destination graph.
   1.734 -    template <typename NodeRef>
   1.735 -    DigraphCopy& nodeRef(NodeRef& map) {
   1.736 -      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
   1.737 -                           NodeRefMap, NodeRef>(map));
   1.738 -      return *this;
   1.739 -    }
   1.740 -
   1.741 -    /// \brief Copies the node cross references into the given map.
   1.742 -    ///
   1.743 -    ///  Copies the node cross references (reverse references) into
   1.744 -    ///  the given map. The parameter should be a map, which key type
   1.745 -    ///  is the Node type of the destination graph, while the value type is
   1.746 -    ///  the Node type of the source graph.
   1.747 -    template <typename NodeCrossRef>
   1.748 -    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
   1.749 -      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
   1.750 -                           NodeRefMap, NodeCrossRef>(map));
   1.751 -      return *this;
   1.752 -    }
   1.753 -
   1.754 -    /// \brief Make copy of the given map.
   1.755 -    ///
   1.756 -    /// Makes copy of the given map for the newly created digraph.
   1.757 -    /// The new map's key type is the destination graph's node type,
   1.758 -    /// and the copied map's key type is the source graph's node type.
   1.759 -    template <typename ToMap, typename FromMap>
   1.760 -    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
   1.761 -      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
   1.762 -                           NodeRefMap, ToMap, FromMap>(tmap, map));
   1.763 -      return *this;
   1.764 -    }
   1.765 -
   1.766 -    /// \brief Make a copy of the given node.
   1.767 -    ///
   1.768 -    /// Make a copy of the given node.
   1.769 -    DigraphCopy& node(TNode& tnode, const Node& snode) {
   1.770 -      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
   1.771 -                           NodeRefMap, TNode>(tnode, snode));
   1.772 -      return *this;
   1.773 -    }
   1.774 -
   1.775 -    /// \brief Copies the arc references into the given map.
   1.776 -    ///
   1.777 -    /// Copies the arc references into the given map.
   1.778 -    template <typename ArcRef>
   1.779 -    DigraphCopy& arcRef(ArcRef& map) {
   1.780 -      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
   1.781 -                          ArcRefMap, ArcRef>(map));
   1.782 -      return *this;
   1.783 -    }
   1.784 -
   1.785 -    /// \brief Copies the arc cross references into the given map.
   1.786 -    ///
   1.787 -    ///  Copies the arc cross references (reverse references) into
   1.788 -    ///  the given map.
   1.789 -    template <typename ArcCrossRef>
   1.790 -    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
   1.791 -      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
   1.792 -                          ArcRefMap, ArcCrossRef>(map));
   1.793 -      return *this;
   1.794 -    }
   1.795 -
   1.796 -    /// \brief Make copy of the given map.
   1.797 -    ///
   1.798 -    /// Makes copy of the given map for the newly created digraph.
   1.799 -    /// The new map's key type is the to digraph's arc type,
   1.800 -    /// and the copied map's key type is the from digraph's arc
   1.801 -    /// type.
   1.802 -    template <typename ToMap, typename FromMap>
   1.803 -    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
   1.804 -      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
   1.805 -                          ArcRefMap, ToMap, FromMap>(tmap, map));
   1.806 -      return *this;
   1.807 -    }
   1.808 -
   1.809 -    /// \brief Make a copy of the given arc.
   1.810 -    ///
   1.811 -    /// Make a copy of the given arc.
   1.812 -    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
   1.813 -      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
   1.814 -                          ArcRefMap, TArc>(tarc, sarc));
   1.815 -      return *this;
   1.816 -    }
   1.817 -
   1.818 -    /// \brief Executes the copies.
   1.819 -    ///
   1.820 -    /// Executes the copies.
   1.821 -    void run() {
   1.822 -      NodeRefMap nodeRefMap(_from);
   1.823 -      ArcRefMap arcRefMap(_from);
   1.824 -      _graph_utils_bits::DigraphCopySelector<To>::
   1.825 -        copy(_to, _from, nodeRefMap, arcRefMap);
   1.826 -      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.827 -        _node_maps[i]->copy(_from, nodeRefMap);
   1.828 -      }
   1.829 -      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.830 -        _arc_maps[i]->copy(_from, arcRefMap);
   1.831 -      }
   1.832 -    }
   1.833 -
   1.834 -  protected:
   1.835 -
   1.836 -
   1.837 -    const From& _from;
   1.838 -    To& _to;
   1.839 -
   1.840 -    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
   1.841 -    _node_maps;
   1.842 -
   1.843 -    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
   1.844 -    _arc_maps;
   1.845 -
   1.846 -  };
   1.847 -
   1.848 -  /// \brief Copy a digraph to another digraph.
   1.849 -  ///
   1.850 -  /// Copy a digraph to another digraph. The complete usage of the
   1.851 -  /// function is detailed in the DigraphCopy class, but a short
   1.852 -  /// example shows a basic work:
   1.853 -  ///\code
   1.854 -  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
   1.855 -  ///\endcode
   1.856 -  ///
   1.857 -  /// After the copy the \c nr map will contain the mapping from the
   1.858 -  /// nodes of the \c from digraph to the nodes of the \c to digraph and
   1.859 -  /// \c ecr will contain the mapping from the arcs of the \c to digraph
   1.860 -  /// to the arcs of the \c from digraph.
   1.861 -  ///
   1.862 -  /// \see DigraphCopy
   1.863 -  template <typename To, typename From>
   1.864 -  DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
   1.865 -    return DigraphCopy<To, From>(to, from);
   1.866 -  }
   1.867 -
   1.868 -  /// \brief Class to copy a graph.
   1.869 -  ///
   1.870 -  /// Class to copy a graph to another graph (duplicate a graph). The
   1.871 -  /// simplest way of using it is through the \c copyGraph() function.
   1.872 -  ///
   1.873 -  /// This class not just make a copy of a graph, but it can create
   1.874 -  /// references and cross references between the nodes, edges and arcs of
   1.875 -  /// the two graphs, it can copy maps for use with the newly created
   1.876 -  /// graph and copy nodes, edges and arcs.
   1.877 -  ///
   1.878 -  /// To make a copy from a graph, first an instance of GraphCopy
   1.879 -  /// should be created, then the data belongs to the graph should
   1.880 -  /// assigned to copy. In the end, the \c run() member should be
   1.881 -  /// called.
   1.882 -  ///
   1.883 -  /// The next code copies a graph with several data:
   1.884 -  ///\code
   1.885 -  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
   1.886 -  ///  // create a reference for the nodes
   1.887 -  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   1.888 -  ///  dc.nodeRef(nr);
   1.889 -  ///  // create a cross reference (inverse) for the edges
   1.890 -  ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
   1.891 -  ///  dc.edgeCrossRef(ecr);
   1.892 -  ///  // copy an arc map
   1.893 -  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
   1.894 -  ///  NewGraph::ArcMap<double> namap(new_graph);
   1.895 -  ///  dc.arcMap(namap, oamap);
   1.896 -  ///  // copy a node
   1.897 -  ///  OrigGraph::Node on;
   1.898 -  ///  NewGraph::Node nn;
   1.899 -  ///  dc.node(nn, on);
   1.900 -  ///  // Executions of copy
   1.901 -  ///  dc.run();
   1.902 -  ///\endcode
   1.903 -  template <typename To, typename From>
   1.904 -  class GraphCopy {
   1.905 -  private:
   1.906 -
   1.907 -    typedef typename From::Node Node;
   1.908 -    typedef typename From::NodeIt NodeIt;
   1.909 -    typedef typename From::Arc Arc;
   1.910 -    typedef typename From::ArcIt ArcIt;
   1.911 -    typedef typename From::Edge Edge;
   1.912 -    typedef typename From::EdgeIt EdgeIt;
   1.913 -
   1.914 -    typedef typename To::Node TNode;
   1.915 -    typedef typename To::Arc TArc;
   1.916 -    typedef typename To::Edge TEdge;
   1.917 -
   1.918 -    typedef typename From::template NodeMap<TNode> NodeRefMap;
   1.919 -    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
   1.920 -
   1.921 -    struct ArcRefMap {
   1.922 -      ArcRefMap(const To& to, const From& from,
   1.923 -                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
   1.924 -        : _to(to), _from(from),
   1.925 -          _edge_ref(edge_ref), _node_ref(node_ref) {}
   1.926 -
   1.927 -      typedef typename From::Arc Key;
   1.928 -      typedef typename To::Arc Value;
   1.929 -
   1.930 -      Value operator[](const Key& key) const {
   1.931 -        bool forward = _from.u(key) != _from.v(key) ?
   1.932 -          _node_ref[_from.source(key)] ==
   1.933 -          _to.source(_to.direct(_edge_ref[key], true)) :
   1.934 -          _from.direction(key);
   1.935 -        return _to.direct(_edge_ref[key], forward);
   1.936 -      }
   1.937 -
   1.938 -      const To& _to;
   1.939 -      const From& _from;
   1.940 -      const EdgeRefMap& _edge_ref;
   1.941 -      const NodeRefMap& _node_ref;
   1.942 -    };
   1.943 -
   1.944 -
   1.945 -  public:
   1.946 -
   1.947 -
   1.948 -    /// \brief Constructor for the GraphCopy.
   1.949 -    ///
   1.950 -    /// It copies the content of the \c _from graph into the
   1.951 -    /// \c _to graph.
   1.952 -    GraphCopy(To& to, const From& from)
   1.953 -      : _from(from), _to(to) {}
   1.954 -
   1.955 -    /// \brief Destructor of the GraphCopy
   1.956 -    ///
   1.957 -    /// Destructor of the GraphCopy
   1.958 -    ~GraphCopy() {
   1.959 -      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.960 -        delete _node_maps[i];
   1.961 -      }
   1.962 -      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.963 -        delete _arc_maps[i];
   1.964 -      }
   1.965 -      for (int i = 0; i < int(_edge_maps.size()); ++i) {
   1.966 -        delete _edge_maps[i];
   1.967 -      }
   1.968 -
   1.969 -    }
   1.970 -
   1.971 -    /// \brief Copies the node references into the given map.
   1.972 -    ///
   1.973 -    /// Copies the node references into the given map.
   1.974 -    template <typename NodeRef>
   1.975 -    GraphCopy& nodeRef(NodeRef& map) {
   1.976 -      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
   1.977 -                           NodeRefMap, NodeRef>(map));
   1.978 -      return *this;
   1.979 -    }
   1.980 -
   1.981 -    /// \brief Copies the node cross references into the given map.
   1.982 -    ///
   1.983 -    ///  Copies the node cross references (reverse references) into
   1.984 -    ///  the given map.
   1.985 -    template <typename NodeCrossRef>
   1.986 -    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
   1.987 -      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
   1.988 -                           NodeRefMap, NodeCrossRef>(map));
   1.989 -      return *this;
   1.990 -    }
   1.991 -
   1.992 -    /// \brief Make copy of the given map.
   1.993 -    ///
   1.994 -    /// Makes copy of the given map for the newly created graph.
   1.995 -    /// The new map's key type is the to graph's node type,
   1.996 -    /// and the copied map's key type is the from graph's node
   1.997 -    /// type.
   1.998 -    template <typename ToMap, typename FromMap>
   1.999 -    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
  1.1000 -      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
  1.1001 -                           NodeRefMap, ToMap, FromMap>(tmap, map));
  1.1002 -      return *this;
  1.1003 -    }
  1.1004 -
  1.1005 -    /// \brief Make a copy of the given node.
  1.1006 -    ///
  1.1007 -    /// Make a copy of the given node.
  1.1008 -    GraphCopy& node(TNode& tnode, const Node& snode) {
  1.1009 -      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
  1.1010 -                           NodeRefMap, TNode>(tnode, snode));
  1.1011 -      return *this;
  1.1012 -    }
  1.1013 -
  1.1014 -    /// \brief Copies the arc references into the given map.
  1.1015 -    ///
  1.1016 -    /// Copies the arc references into the given map.
  1.1017 -    template <typename ArcRef>
  1.1018 -    GraphCopy& arcRef(ArcRef& map) {
  1.1019 -      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
  1.1020 -                          ArcRefMap, ArcRef>(map));
  1.1021 -      return *this;
  1.1022 -    }
  1.1023 -
  1.1024 -    /// \brief Copies the arc cross references into the given map.
  1.1025 -    ///
  1.1026 -    ///  Copies the arc cross references (reverse references) into
  1.1027 -    ///  the given map.
  1.1028 -    template <typename ArcCrossRef>
  1.1029 -    GraphCopy& arcCrossRef(ArcCrossRef& map) {
  1.1030 -      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
  1.1031 -                          ArcRefMap, ArcCrossRef>(map));
  1.1032 -      return *this;
  1.1033 -    }
  1.1034 -
  1.1035 -    /// \brief Make copy of the given map.
  1.1036 -    ///
  1.1037 -    /// Makes copy of the given map for the newly created graph.
  1.1038 -    /// The new map's key type is the to graph's arc type,
  1.1039 -    /// and the copied map's key type is the from graph's arc
  1.1040 -    /// type.
  1.1041 -    template <typename ToMap, typename FromMap>
  1.1042 -    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
  1.1043 -      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
  1.1044 -                          ArcRefMap, ToMap, FromMap>(tmap, map));
  1.1045 -      return *this;
  1.1046 -    }
  1.1047 -
  1.1048 -    /// \brief Make a copy of the given arc.
  1.1049 -    ///
  1.1050 -    /// Make a copy of the given arc.
  1.1051 -    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
  1.1052 -      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
  1.1053 -                          ArcRefMap, TArc>(tarc, sarc));
  1.1054 -      return *this;
  1.1055 -    }
  1.1056 -
  1.1057 -    /// \brief Copies the edge references into the given map.
  1.1058 -    ///
  1.1059 -    /// Copies the edge references into the given map.
  1.1060 -    template <typename EdgeRef>
  1.1061 -    GraphCopy& edgeRef(EdgeRef& map) {
  1.1062 -      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
  1.1063 -                           EdgeRefMap, EdgeRef>(map));
  1.1064 -      return *this;
  1.1065 -    }
  1.1066 -
  1.1067 -    /// \brief Copies the edge cross references into the given map.
  1.1068 -    ///
  1.1069 -    /// Copies the edge cross references (reverse
  1.1070 -    /// references) into the given map.
  1.1071 -    template <typename EdgeCrossRef>
  1.1072 -    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
  1.1073 -      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
  1.1074 -                           Edge, EdgeRefMap, EdgeCrossRef>(map));
  1.1075 -      return *this;
  1.1076 -    }
  1.1077 -
  1.1078 -    /// \brief Make copy of the given map.
  1.1079 -    ///
  1.1080 -    /// Makes copy of the given map for the newly created graph.
  1.1081 -    /// The new map's key type is the to graph's edge type,
  1.1082 -    /// and the copied map's key type is the from graph's edge
  1.1083 -    /// type.
  1.1084 -    template <typename ToMap, typename FromMap>
  1.1085 -    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
  1.1086 -      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
  1.1087 -                           EdgeRefMap, ToMap, FromMap>(tmap, map));
  1.1088 -      return *this;
  1.1089 -    }
  1.1090 -
  1.1091 -    /// \brief Make a copy of the given edge.
  1.1092 -    ///
  1.1093 -    /// Make a copy of the given edge.
  1.1094 -    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
  1.1095 -      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
  1.1096 -                           EdgeRefMap, TEdge>(tedge, sedge));
  1.1097 -      return *this;
  1.1098 -    }
  1.1099 -
  1.1100 -    /// \brief Executes the copies.
  1.1101 -    ///
  1.1102 -    /// Executes the copies.
  1.1103 -    void run() {
  1.1104 -      NodeRefMap nodeRefMap(_from);
  1.1105 -      EdgeRefMap edgeRefMap(_from);
  1.1106 -      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
  1.1107 -      _graph_utils_bits::GraphCopySelector<To>::
  1.1108 -        copy(_to, _from, nodeRefMap, edgeRefMap);
  1.1109 -      for (int i = 0; i < int(_node_maps.size()); ++i) {
  1.1110 -        _node_maps[i]->copy(_from, nodeRefMap);
  1.1111 -      }
  1.1112 -      for (int i = 0; i < int(_edge_maps.size()); ++i) {
  1.1113 -        _edge_maps[i]->copy(_from, edgeRefMap);
  1.1114 -      }
  1.1115 -      for (int i = 0; i < int(_arc_maps.size()); ++i) {
  1.1116 -        _arc_maps[i]->copy(_from, arcRefMap);
  1.1117 -      }
  1.1118 -    }
  1.1119 -
  1.1120 -  private:
  1.1121 -
  1.1122 -    const From& _from;
  1.1123 -    To& _to;
  1.1124 -
  1.1125 -    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
  1.1126 -    _node_maps;
  1.1127 -
  1.1128 -    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
  1.1129 -    _arc_maps;
  1.1130 -
  1.1131 -    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
  1.1132 -    _edge_maps;
  1.1133 -
  1.1134 -  };
  1.1135 -
  1.1136 -  /// \brief Copy a graph to another graph.
  1.1137 -  ///
  1.1138 -  /// Copy a graph to another graph. The complete usage of the
  1.1139 -  /// function is detailed in the GraphCopy class, but a short
  1.1140 -  /// example shows a basic work:
  1.1141 -  ///\code
  1.1142 -  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
  1.1143 -  ///\endcode
  1.1144 -  ///
  1.1145 -  /// After the copy the \c nr map will contain the mapping from the
  1.1146 -  /// nodes of the \c from graph to the nodes of the \c to graph and
  1.1147 -  /// \c ecr will contain the mapping from the arcs of the \c to graph
  1.1148 -  /// to the arcs of the \c from graph.
  1.1149 -  ///
  1.1150 -  /// \see GraphCopy
  1.1151 -  template <typename To, typename From>
  1.1152 -  GraphCopy<To, From>
  1.1153 -  copyGraph(To& to, const From& from) {
  1.1154 -    return GraphCopy<To, From>(to, from);
  1.1155 -  }
  1.1156 -
  1.1157 -  /// @}
  1.1158 -
  1.1159 -  /// \addtogroup graph_maps
  1.1160 -  /// @{
  1.1161 -
  1.1162 -  /// Provides an immutable and unique id for each item in the graph.
  1.1163 -
  1.1164 -  /// The IdMap class provides a unique and immutable id for each item of the
  1.1165 -  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
  1.1166 -  /// different items (nodes) get different ids <li>\b immutable: the id of an
  1.1167 -  /// item (node) does not change (even if you delete other nodes).  </ul>
  1.1168 -  /// Through this map you get access (i.e. can read) the inner id values of
  1.1169 -  /// the items stored in the graph. This map can be inverted with its member
  1.1170 -  /// class \c InverseMap or with the \c operator() member.
  1.1171 -  ///
  1.1172 -  template <typename _Graph, typename _Item>
  1.1173 -  class IdMap {
  1.1174 -  public:
  1.1175 -    typedef _Graph Graph;
  1.1176 -    typedef int Value;
  1.1177 -    typedef _Item Item;
  1.1178 -    typedef _Item Key;
  1.1179 -
  1.1180 -    /// \brief Constructor.
  1.1181 -    ///
  1.1182 -    /// Constructor of the map.
  1.1183 -    explicit IdMap(const Graph& graph) : _graph(&graph) {}
  1.1184 -
  1.1185 -    /// \brief Gives back the \e id of the item.
  1.1186 -    ///
  1.1187 -    /// Gives back the immutable and unique \e id of the item.
  1.1188 -    int operator[](const Item& item) const { return _graph->id(item);}
  1.1189 -
  1.1190 -    /// \brief Gives back the item by its id.
  1.1191 -    ///
  1.1192 -    /// Gives back the item by its id.
  1.1193 -    Item operator()(int id) { return _graph->fromId(id, Item()); }
  1.1194 -
  1.1195 -  private:
  1.1196 -    const Graph* _graph;
  1.1197 -
  1.1198 -  public:
  1.1199 -
  1.1200 -    /// \brief The class represents the inverse of its owner (IdMap).
  1.1201 -    ///
  1.1202 -    /// The class represents the inverse of its owner (IdMap).
  1.1203 -    /// \see inverse()
  1.1204 -    class InverseMap {
  1.1205 -    public:
  1.1206 -
  1.1207 -      /// \brief Constructor.
  1.1208 -      ///
  1.1209 -      /// Constructor for creating an id-to-item map.
  1.1210 -      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
  1.1211 -
  1.1212 -      /// \brief Constructor.
  1.1213 -      ///
  1.1214 -      /// Constructor for creating an id-to-item map.
  1.1215 -      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
  1.1216 -
  1.1217 -      /// \brief Gives back the given item from its id.
  1.1218 -      ///
  1.1219 -      /// Gives back the given item from its id.
  1.1220 -      ///
  1.1221 -      Item operator[](int id) const { return _graph->fromId(id, Item());}
  1.1222 -
  1.1223 -    private:
  1.1224 -      const Graph* _graph;
  1.1225 -    };
  1.1226 -
  1.1227 -    /// \brief Gives back the inverse of the map.
  1.1228 -    ///
  1.1229 -    /// Gives back the inverse of the IdMap.
  1.1230 -    InverseMap inverse() const { return InverseMap(*_graph);}
  1.1231 -
  1.1232 -  };
  1.1233 -
  1.1234 -
  1.1235 -  /// \brief General invertable graph-map type.
  1.1236 -
  1.1237 -  /// This type provides simple invertable graph-maps.
  1.1238 -  /// The InvertableMap wraps an arbitrary ReadWriteMap
  1.1239 -  /// and if a key is set to a new value then store it
  1.1240 -  /// in the inverse map.
  1.1241 -  ///
  1.1242 -  /// The values of the map can be accessed
  1.1243 -  /// with stl compatible forward iterator.
  1.1244 -  ///
  1.1245 -  /// \tparam _Graph The graph type.
  1.1246 -  /// \tparam _Item The item type of the graph.
  1.1247 -  /// \tparam _Value The value type of the map.
  1.1248 -  ///
  1.1249 -  /// \see IterableValueMap
  1.1250 -  template <typename _Graph, typename _Item, typename _Value>
  1.1251 -  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
  1.1252 -  private:
  1.1253 -
  1.1254 -    typedef DefaultMap<_Graph, _Item, _Value> Map;
  1.1255 -    typedef _Graph Graph;
  1.1256 -
  1.1257 -    typedef std::map<_Value, _Item> Container;
  1.1258 -    Container _inv_map;
  1.1259 -
  1.1260 -  public:
  1.1261 -
  1.1262 -    /// The key type of InvertableMap (Node, Arc, Edge).
  1.1263 -    typedef typename Map::Key Key;
  1.1264 -    /// The value type of the InvertableMap.
  1.1265 -    typedef typename Map::Value Value;
  1.1266 -
  1.1267 -
  1.1268 -
  1.1269 -    /// \brief Constructor.
  1.1270 -    ///
  1.1271 -    /// Construct a new InvertableMap for the graph.
  1.1272 -    ///
  1.1273 -    explicit InvertableMap(const Graph& graph) : Map(graph) {}
  1.1274 -
  1.1275 -    /// \brief Forward iterator for values.
  1.1276 -    ///
  1.1277 -    /// This iterator is an stl compatible forward
  1.1278 -    /// iterator on the values of the map. The values can
  1.1279 -    /// be accessed in the [beginValue, endValue) range.
  1.1280 -    ///
  1.1281 -    class ValueIterator
  1.1282 -      : public std::iterator<std::forward_iterator_tag, Value> {
  1.1283 -      friend class InvertableMap;
  1.1284 -    private:
  1.1285 -      ValueIterator(typename Container::const_iterator _it)
  1.1286 -        : it(_it) {}
  1.1287 -    public:
  1.1288 -
  1.1289 -      ValueIterator() {}
  1.1290 -
  1.1291 -      ValueIterator& operator++() { ++it; return *this; }
  1.1292 -      ValueIterator operator++(int) {
  1.1293 -        ValueIterator tmp(*this);
  1.1294 -        operator++();
  1.1295 -        return tmp;
  1.1296 -      }
  1.1297 -
  1.1298 -      const Value& operator*() const { return it->first; }
  1.1299 -      const Value* operator->() const { return &(it->first); }
  1.1300 -
  1.1301 -      bool operator==(ValueIterator jt) const { return it == jt.it; }
  1.1302 -      bool operator!=(ValueIterator jt) const { return it != jt.it; }
  1.1303 -
  1.1304 -    private:
  1.1305 -      typename Container::const_iterator it;
  1.1306 -    };
  1.1307 -
  1.1308 -    /// \brief Returns an iterator to the first value.
  1.1309 -    ///
  1.1310 -    /// Returns an stl compatible iterator to the
  1.1311 -    /// first value of the map. The values of the
  1.1312 -    /// map can be accessed in the [beginValue, endValue)
  1.1313 -    /// range.
  1.1314 -    ValueIterator beginValue() const {
  1.1315 -      return ValueIterator(_inv_map.begin());
  1.1316 -    }
  1.1317 -
  1.1318 -    /// \brief Returns an iterator after the last value.
  1.1319 -    ///
  1.1320 -    /// Returns an stl compatible iterator after the
  1.1321 -    /// last value of the map. The values of the
  1.1322 -    /// map can be accessed in the [beginValue, endValue)
  1.1323 -    /// range.
  1.1324 -    ValueIterator endValue() const {
  1.1325 -      return ValueIterator(_inv_map.end());
  1.1326 -    }
  1.1327 -
  1.1328 -    /// \brief The setter function of the map.
  1.1329 -    ///
  1.1330 -    /// Sets the mapped value.
  1.1331 -    void set(const Key& key, const Value& val) {
  1.1332 -      Value oldval = Map::operator[](key);
  1.1333 -      typename Container::iterator it = _inv_map.find(oldval);
  1.1334 -      if (it != _inv_map.end() && it->second == key) {
  1.1335 -        _inv_map.erase(it);
  1.1336 -      }
  1.1337 -      _inv_map.insert(make_pair(val, key));
  1.1338 -      Map::set(key, val);
  1.1339 -    }
  1.1340 -
  1.1341 -    /// \brief The getter function of the map.
  1.1342 -    ///
  1.1343 -    /// It gives back the value associated with the key.
  1.1344 -    typename MapTraits<Map>::ConstReturnValue
  1.1345 -    operator[](const Key& key) const {
  1.1346 -      return Map::operator[](key);
  1.1347 -    }
  1.1348 -
  1.1349 -    /// \brief Gives back the item by its value.
  1.1350 -    ///
  1.1351 -    /// Gives back the item by its value.
  1.1352 -    Key operator()(const Value& key) const {
  1.1353 -      typename Container::const_iterator it = _inv_map.find(key);
  1.1354 -      return it != _inv_map.end() ? it->second : INVALID;
  1.1355 -    }
  1.1356 -
  1.1357 -  protected:
  1.1358 -
  1.1359 -    /// \brief Erase the key from the map.
  1.1360 -    ///
  1.1361 -    /// Erase the key to the map. It is called by the
  1.1362 -    /// \c AlterationNotifier.
  1.1363 -    virtual void erase(const Key& key) {
  1.1364 -      Value val = Map::operator[](key);
  1.1365 -      typename Container::iterator it = _inv_map.find(val);
  1.1366 -      if (it != _inv_map.end() && it->second == key) {
  1.1367 -        _inv_map.erase(it);
  1.1368 -      }
  1.1369 -      Map::erase(key);
  1.1370 -    }
  1.1371 -
  1.1372 -    /// \brief Erase more keys from the map.
  1.1373 -    ///
  1.1374 -    /// Erase more keys from the map. It is called by the
  1.1375 -    /// \c AlterationNotifier.
  1.1376 -    virtual void erase(const std::vector<Key>& keys) {
  1.1377 -      for (int i = 0; i < int(keys.size()); ++i) {
  1.1378 -        Value val = Map::operator[](keys[i]);
  1.1379 -        typename Container::iterator it = _inv_map.find(val);
  1.1380 -        if (it != _inv_map.end() && it->second == keys[i]) {
  1.1381 -          _inv_map.erase(it);
  1.1382 -        }
  1.1383 -      }
  1.1384 -      Map::erase(keys);
  1.1385 -    }
  1.1386 -
  1.1387 -    /// \brief Clear the keys from the map and inverse map.
  1.1388 -    ///
  1.1389 -    /// Clear the keys from the map and inverse map. It is called by the
  1.1390 -    /// \c AlterationNotifier.
  1.1391 -    virtual void clear() {
  1.1392 -      _inv_map.clear();
  1.1393 -      Map::clear();
  1.1394 -    }
  1.1395 -
  1.1396 -  public:
  1.1397 -
  1.1398 -    /// \brief The inverse map type.
  1.1399 -    ///
  1.1400 -    /// The inverse of this map. The subscript operator of the map
  1.1401 -    /// gives back always the item what was last assigned to the value.
  1.1402 -    class InverseMap {
  1.1403 -    public:
  1.1404 -      /// \brief Constructor of the InverseMap.
  1.1405 -      ///
  1.1406 -      /// Constructor of the InverseMap.
  1.1407 -      explicit InverseMap(const InvertableMap& inverted)
  1.1408 -        : _inverted(inverted) {}
  1.1409 -
  1.1410 -      /// The value type of the InverseMap.
  1.1411 -      typedef typename InvertableMap::Key Value;
  1.1412 -      /// The key type of the InverseMap.
  1.1413 -      typedef typename InvertableMap::Value Key;
  1.1414 -
  1.1415 -      /// \brief Subscript operator.
  1.1416 -      ///
  1.1417 -      /// Subscript operator. It gives back always the item
  1.1418 -      /// what was last assigned to the value.
  1.1419 -      Value operator[](const Key& key) const {
  1.1420 -        return _inverted(key);
  1.1421 -      }
  1.1422 -
  1.1423 -    private:
  1.1424 -      const InvertableMap& _inverted;
  1.1425 -    };
  1.1426 -
  1.1427 -    /// \brief It gives back the just readable inverse map.
  1.1428 -    ///
  1.1429 -    /// It gives back the just readable inverse map.
  1.1430 -    InverseMap inverse() const {
  1.1431 -      return InverseMap(*this);
  1.1432 -    }
  1.1433 -
  1.1434 -
  1.1435 -
  1.1436 -  };
  1.1437 -
  1.1438 -  /// \brief Provides a mutable, continuous and unique descriptor for each
  1.1439 -  /// item in the graph.
  1.1440 -  ///
  1.1441 -  /// The DescriptorMap class provides a unique and continuous (but mutable)
  1.1442 -  /// descriptor (id) for each item of the same type (e.g. node) in the
  1.1443 -  /// graph. This id is <ul><li>\b unique: different items (nodes) get
  1.1444 -  /// different ids <li>\b continuous: the range of the ids is the set of
  1.1445 -  /// integers between 0 and \c n-1, where \c n is the number of the items of
  1.1446 -  /// this type (e.g. nodes) (so the id of a node can change if you delete an
  1.1447 -  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  1.1448 -  /// with its member class \c InverseMap, or with the \c operator() member.
  1.1449 -  ///
  1.1450 -  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
  1.1451 -  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
  1.1452 -  /// Edge.
  1.1453 -  template <typename _Graph, typename _Item>
  1.1454 -  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
  1.1455 -
  1.1456 -    typedef _Item Item;
  1.1457 -    typedef DefaultMap<_Graph, _Item, int> Map;
  1.1458 -
  1.1459 -  public:
  1.1460 -    /// The graph class of DescriptorMap.
  1.1461 -    typedef _Graph Graph;
  1.1462 -
  1.1463 -    /// The key type of DescriptorMap (Node, Arc, Edge).
  1.1464 -    typedef typename Map::Key Key;
  1.1465 -    /// The value type of DescriptorMap.
  1.1466 -    typedef typename Map::Value Value;
  1.1467 -
  1.1468 -    /// \brief Constructor.
  1.1469 -    ///
  1.1470 -    /// Constructor for descriptor map.
  1.1471 -    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
  1.1472 -      Item it;
  1.1473 -      const typename Map::Notifier* nf = Map::notifier();
  1.1474 -      for (nf->first(it); it != INVALID; nf->next(it)) {
  1.1475 -        Map::set(it, _inv_map.size());
  1.1476 -        _inv_map.push_back(it);
  1.1477 -      }
  1.1478 -    }
  1.1479 -
  1.1480 -  protected:
  1.1481 -
  1.1482 -    /// \brief Add a new key to the map.
  1.1483 -    ///
  1.1484 -    /// Add a new key to the map. It is called by the
  1.1485 -    /// \c AlterationNotifier.
  1.1486 -    virtual void add(const Item& item) {
  1.1487 -      Map::add(item);
  1.1488 -      Map::set(item, _inv_map.size());
  1.1489 -      _inv_map.push_back(item);
  1.1490 -    }
  1.1491 -
  1.1492 -    /// \brief Add more new keys to the map.
  1.1493 -    ///
  1.1494 -    /// Add more new keys to the map. It is called by the
  1.1495 -    /// \c AlterationNotifier.
  1.1496 -    virtual void add(const std::vector<Item>& items) {
  1.1497 -      Map::add(items);
  1.1498 -      for (int i = 0; i < int(items.size()); ++i) {
  1.1499 -        Map::set(items[i], _inv_map.size());
  1.1500 -        _inv_map.push_back(items[i]);
  1.1501 -      }
  1.1502 -    }
  1.1503 -
  1.1504 -    /// \brief Erase the key from the map.
  1.1505 -    ///
  1.1506 -    /// Erase the key from the map. It is called by the
  1.1507 -    /// \c AlterationNotifier.
  1.1508 -    virtual void erase(const Item& item) {
  1.1509 -      Map::set(_inv_map.back(), Map::operator[](item));
  1.1510 -      _inv_map[Map::operator[](item)] = _inv_map.back();
  1.1511 -      _inv_map.pop_back();
  1.1512 -      Map::erase(item);
  1.1513 -    }
  1.1514 -
  1.1515 -    /// \brief Erase more keys from the map.
  1.1516 -    ///
  1.1517 -    /// Erase more keys from the map. It is called by the
  1.1518 -    /// \c AlterationNotifier.
  1.1519 -    virtual void erase(const std::vector<Item>& items) {
  1.1520 -      for (int i = 0; i < int(items.size()); ++i) {
  1.1521 -        Map::set(_inv_map.back(), Map::operator[](items[i]));
  1.1522 -        _inv_map[Map::operator[](items[i])] = _inv_map.back();
  1.1523 -        _inv_map.pop_back();
  1.1524 -      }
  1.1525 -      Map::erase(items);
  1.1526 -    }
  1.1527 -
  1.1528 -    /// \brief Build the unique map.
  1.1529 -    ///
  1.1530 -    /// Build the unique map. It is called by the
  1.1531 -    /// \c AlterationNotifier.
  1.1532 -    virtual void build() {
  1.1533 -      Map::build();
  1.1534 -      Item it;
  1.1535 -      const typename Map::Notifier* nf = Map::notifier();
  1.1536 -      for (nf->first(it); it != INVALID; nf->next(it)) {
  1.1537 -        Map::set(it, _inv_map.size());
  1.1538 -        _inv_map.push_back(it);
  1.1539 -      }
  1.1540 -    }
  1.1541 -
  1.1542 -    /// \brief Clear the keys from the map.
  1.1543 -    ///
  1.1544 -    /// Clear the keys from the map. It is called by the
  1.1545 -    /// \c AlterationNotifier.
  1.1546 -    virtual void clear() {
  1.1547 -      _inv_map.clear();
  1.1548 -      Map::clear();
  1.1549 -    }
  1.1550 -
  1.1551 -  public:
  1.1552 -
  1.1553 -    /// \brief Returns the maximal value plus one.
  1.1554 -    ///
  1.1555 -    /// Returns the maximal value plus one in the map.
  1.1556 -    unsigned int size() const {
  1.1557 -      return _inv_map.size();
  1.1558 -    }
  1.1559 -
  1.1560 -    /// \brief Swaps the position of the two items in the map.
  1.1561 -    ///
  1.1562 -    /// Swaps the position of the two items in the map.
  1.1563 -    void swap(const Item& p, const Item& q) {
  1.1564 -      int pi = Map::operator[](p);
  1.1565 -      int qi = Map::operator[](q);
  1.1566 -      Map::set(p, qi);
  1.1567 -      _inv_map[qi] = p;
  1.1568 -      Map::set(q, pi);
  1.1569 -      _inv_map[pi] = q;
  1.1570 -    }
  1.1571 -
  1.1572 -    /// \brief Gives back the \e descriptor of the item.
  1.1573 -    ///
  1.1574 -    /// Gives back the mutable and unique \e descriptor of the map.
  1.1575 -    int operator[](const Item& item) const {
  1.1576 -      return Map::operator[](item);
  1.1577 -    }
  1.1578 -
  1.1579 -    /// \brief Gives back the item by its descriptor.
  1.1580 -    ///
  1.1581 -    /// Gives back th item by its descriptor.
  1.1582 -    Item operator()(int id) const {
  1.1583 -      return _inv_map[id];
  1.1584 -    }
  1.1585 -
  1.1586 -  private:
  1.1587 -
  1.1588 -    typedef std::vector<Item> Container;
  1.1589 -    Container _inv_map;
  1.1590 -
  1.1591 -  public:
  1.1592 -    /// \brief The inverse map type of DescriptorMap.
  1.1593 -    ///
  1.1594 -    /// The inverse map type of DescriptorMap.
  1.1595 -    class InverseMap {
  1.1596 -    public:
  1.1597 -      /// \brief Constructor of the InverseMap.
  1.1598 -      ///
  1.1599 -      /// Constructor of the InverseMap.
  1.1600 -      explicit InverseMap(const DescriptorMap& inverted)
  1.1601 -        : _inverted(inverted) {}
  1.1602 -
  1.1603 -
  1.1604 -      /// The value type of the InverseMap.
  1.1605 -      typedef typename DescriptorMap::Key Value;
  1.1606 -      /// The key type of the InverseMap.
  1.1607 -      typedef typename DescriptorMap::Value Key;
  1.1608 -
  1.1609 -      /// \brief Subscript operator.
  1.1610 -      ///
  1.1611 -      /// Subscript operator. It gives back the item
  1.1612 -      /// that the descriptor belongs to currently.
  1.1613 -      Value operator[](const Key& key) const {
  1.1614 -        return _inverted(key);
  1.1615 -      }
  1.1616 -
  1.1617 -      /// \brief Size of the map.
  1.1618 -      ///
  1.1619 -      /// Returns the size of the map.
  1.1620 -      unsigned int size() const {
  1.1621 -        return _inverted.size();
  1.1622 -      }
  1.1623 -
  1.1624 -    private:
  1.1625 -      const DescriptorMap& _inverted;
  1.1626 -    };
  1.1627 -
  1.1628 -    /// \brief Gives back the inverse of the map.
  1.1629 -    ///
  1.1630 -    /// Gives back the inverse of the map.
  1.1631 -    const InverseMap inverse() const {
  1.1632 -      return InverseMap(*this);
  1.1633 -    }
  1.1634 -  };
  1.1635 -
  1.1636 -  /// \brief Returns the source of the given arc.
  1.1637 -  ///
  1.1638 -  /// The SourceMap gives back the source Node of the given arc.
  1.1639 -  /// \see TargetMap
  1.1640 -  template <typename Digraph>
  1.1641 -  class SourceMap {
  1.1642 -  public:
  1.1643 -
  1.1644 -    typedef typename Digraph::Node Value;
  1.1645 -    typedef typename Digraph::Arc Key;
  1.1646 -
  1.1647 -    /// \brief Constructor
  1.1648 -    ///
  1.1649 -    /// Constructor
  1.1650 -    /// \param _digraph The digraph that the map belongs to.
  1.1651 -    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
  1.1652 -
  1.1653 -    /// \brief The subscript operator.
  1.1654 -    ///
  1.1655 -    /// The subscript operator.
  1.1656 -    /// \param arc The arc
  1.1657 -    /// \return The source of the arc
  1.1658 -    Value operator[](const Key& arc) const {
  1.1659 -      return _digraph.source(arc);
  1.1660 -    }
  1.1661 -
  1.1662 -  private:
  1.1663 -    const Digraph& _digraph;
  1.1664 -  };
  1.1665 -
  1.1666 -  /// \brief Returns a \ref SourceMap class.
  1.1667 -  ///
  1.1668 -  /// This function just returns an \ref SourceMap class.
  1.1669 -  /// \relates SourceMap
  1.1670 -  template <typename Digraph>
  1.1671 -  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
  1.1672 -    return SourceMap<Digraph>(digraph);
  1.1673 -  }
  1.1674 -
  1.1675 -  /// \brief Returns the target of the given arc.
  1.1676 -  ///
  1.1677 -  /// The TargetMap gives back the target Node of the given arc.
  1.1678 -  /// \see SourceMap
  1.1679 -  template <typename Digraph>
  1.1680 -  class TargetMap {
  1.1681 -  public:
  1.1682 -
  1.1683 -    typedef typename Digraph::Node Value;
  1.1684 -    typedef typename Digraph::Arc Key;
  1.1685 -
  1.1686 -    /// \brief Constructor
  1.1687 -    ///
  1.1688 -    /// Constructor
  1.1689 -    /// \param _digraph The digraph that the map belongs to.
  1.1690 -    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
  1.1691 -
  1.1692 -    /// \brief The subscript operator.
  1.1693 -    ///
  1.1694 -    /// The subscript operator.
  1.1695 -    /// \param e The arc
  1.1696 -    /// \return The target of the arc
  1.1697 -    Value operator[](const Key& e) const {
  1.1698 -      return _digraph.target(e);
  1.1699 -    }
  1.1700 -
  1.1701 -  private:
  1.1702 -    const Digraph& _digraph;
  1.1703 -  };
  1.1704 -
  1.1705 -  /// \brief Returns a \ref TargetMap class.
  1.1706 -  ///
  1.1707 -  /// This function just returns a \ref TargetMap class.
  1.1708 -  /// \relates TargetMap
  1.1709 -  template <typename Digraph>
  1.1710 -  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
  1.1711 -    return TargetMap<Digraph>(digraph);
  1.1712 -  }
  1.1713 -
  1.1714 -  /// \brief Returns the "forward" directed arc view of an edge.
  1.1715 -  ///
  1.1716 -  /// Returns the "forward" directed arc view of an edge.
  1.1717 -  /// \see BackwardMap
  1.1718 -  template <typename Graph>
  1.1719 -  class ForwardMap {
  1.1720 -  public:
  1.1721 -
  1.1722 -    typedef typename Graph::Arc Value;
  1.1723 -    typedef typename Graph::Edge Key;
  1.1724 -
  1.1725 -    /// \brief Constructor
  1.1726 -    ///
  1.1727 -    /// Constructor
  1.1728 -    /// \param _graph The graph that the map belongs to.
  1.1729 -    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
  1.1730 -
  1.1731 -    /// \brief The subscript operator.
  1.1732 -    ///
  1.1733 -    /// The subscript operator.
  1.1734 -    /// \param key An edge
  1.1735 -    /// \return The "forward" directed arc view of edge
  1.1736 -    Value operator[](const Key& key) const {
  1.1737 -      return _graph.direct(key, true);
  1.1738 -    }
  1.1739 -
  1.1740 -  private:
  1.1741 -    const Graph& _graph;
  1.1742 -  };
  1.1743 -
  1.1744 -  /// \brief Returns a \ref ForwardMap class.
  1.1745 -  ///
  1.1746 -  /// This function just returns an \ref ForwardMap class.
  1.1747 -  /// \relates ForwardMap
  1.1748 -  template <typename Graph>
  1.1749 -  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
  1.1750 -    return ForwardMap<Graph>(graph);
  1.1751 -  }
  1.1752 -
  1.1753 -  /// \brief Returns the "backward" directed arc view of an edge.
  1.1754 -  ///
  1.1755 -  /// Returns the "backward" directed arc view of an edge.
  1.1756 -  /// \see ForwardMap
  1.1757 -  template <typename Graph>
  1.1758 -  class BackwardMap {
  1.1759 -  public:
  1.1760 -
  1.1761 -    typedef typename Graph::Arc Value;
  1.1762 -    typedef typename Graph::Edge Key;
  1.1763 -
  1.1764 -    /// \brief Constructor
  1.1765 -    ///
  1.1766 -    /// Constructor
  1.1767 -    /// \param _graph The graph that the map belongs to.
  1.1768 -    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
  1.1769 -
  1.1770 -    /// \brief The subscript operator.
  1.1771 -    ///
  1.1772 -    /// The subscript operator.
  1.1773 -    /// \param key An edge
  1.1774 -    /// \return The "backward" directed arc view of edge
  1.1775 -    Value operator[](const Key& key) const {
  1.1776 -      return _graph.direct(key, false);
  1.1777 -    }
  1.1778 -
  1.1779 -  private:
  1.1780 -    const Graph& _graph;
  1.1781 -  };
  1.1782 -
  1.1783 -  /// \brief Returns a \ref BackwardMap class
  1.1784 -
  1.1785 -  /// This function just returns a \ref BackwardMap class.
  1.1786 -  /// \relates BackwardMap
  1.1787 -  template <typename Graph>
  1.1788 -  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
  1.1789 -    return BackwardMap<Graph>(graph);
  1.1790 -  }
  1.1791 -
  1.1792 -  /// \brief Potential difference map
  1.1793 -  ///
  1.1794 -  /// If there is an potential map on the nodes then we
  1.1795 -  /// can get an arc map as we get the substraction of the
  1.1796 -  /// values of the target and source.
  1.1797 -  template <typename Digraph, typename NodeMap>
  1.1798 -  class PotentialDifferenceMap {
  1.1799 -  public:
  1.1800 -    typedef typename Digraph::Arc Key;
  1.1801 -    typedef typename NodeMap::Value Value;
  1.1802 -
  1.1803 -    /// \brief Constructor
  1.1804 -    ///
  1.1805 -    /// Contructor of the map
  1.1806 -    explicit PotentialDifferenceMap(const Digraph& digraph,
  1.1807 -                                    const NodeMap& potential)
  1.1808 -      : _digraph(digraph), _potential(potential) {}
  1.1809 -
  1.1810 -    /// \brief Const subscription operator
  1.1811 -    ///
  1.1812 -    /// Const subscription operator
  1.1813 -    Value operator[](const Key& arc) const {
  1.1814 -      return _potential[_digraph.target(arc)] -
  1.1815 -        _potential[_digraph.source(arc)];
  1.1816 -    }
  1.1817 -
  1.1818 -  private:
  1.1819 -    const Digraph& _digraph;
  1.1820 -    const NodeMap& _potential;
  1.1821 -  };
  1.1822 -
  1.1823 -  /// \brief Returns a PotentialDifferenceMap.
  1.1824 -  ///
  1.1825 -  /// This function just returns a PotentialDifferenceMap.
  1.1826 -  /// \relates PotentialDifferenceMap
  1.1827 -  template <typename Digraph, typename NodeMap>
  1.1828 -  PotentialDifferenceMap<Digraph, NodeMap>
  1.1829 -  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
  1.1830 -    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
  1.1831 -  }
  1.1832 -
  1.1833 -  /// \brief Map of the node in-degrees.
  1.1834 -  ///
  1.1835 -  /// This map returns the in-degree of a node. Once it is constructed,
  1.1836 -  /// the degrees are stored in a standard NodeMap, so each query is done
  1.1837 -  /// in constant time. On the other hand, the values are updated automatically
  1.1838 -  /// whenever the digraph changes.
  1.1839 -  ///
  1.1840 -  /// \warning Besides addNode() and addArc(), a digraph structure may provide
  1.1841 -  /// alternative ways to modify the digraph. The correct behavior of InDegMap
  1.1842 -  /// is not guarantied if these additional features are used. For example
  1.1843 -  /// the functions \ref ListDigraph::changeSource() "changeSource()",
  1.1844 -  /// \ref ListDigraph::changeTarget() "changeTarget()" and
  1.1845 -  /// \ref ListDigraph::reverseArc() "reverseArc()"
  1.1846 -  /// of \ref ListDigraph will \e not update the degree values correctly.
  1.1847 -  ///
  1.1848 -  /// \sa OutDegMap
  1.1849 -
  1.1850 -  template <typename _Digraph>
  1.1851 -  class InDegMap
  1.1852 -    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  1.1853 -      ::ItemNotifier::ObserverBase {
  1.1854 -
  1.1855 -  public:
  1.1856 -
  1.1857 -    typedef _Digraph Digraph;
  1.1858 -    typedef int Value;
  1.1859 -    typedef typename Digraph::Node Key;
  1.1860 -
  1.1861 -    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  1.1862 -    ::ItemNotifier::ObserverBase Parent;
  1.1863 -
  1.1864 -  private:
  1.1865 -
  1.1866 -    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
  1.1867 -    public:
  1.1868 -
  1.1869 -      typedef DefaultMap<Digraph, Key, int> Parent;
  1.1870 -
  1.1871 -      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
  1.1872 -
  1.1873 -      virtual void add(const Key& key) {
  1.1874 -        Parent::add(key);
  1.1875 -        Parent::set(key, 0);
  1.1876 -      }
  1.1877 -
  1.1878 -      virtual void add(const std::vector<Key>& keys) {
  1.1879 -        Parent::add(keys);
  1.1880 -        for (int i = 0; i < int(keys.size()); ++i) {
  1.1881 -          Parent::set(keys[i], 0);
  1.1882 -        }
  1.1883 -      }
  1.1884 -
  1.1885 -      virtual void build() {
  1.1886 -        Parent::build();
  1.1887 -        Key it;
  1.1888 -        typename Parent::Notifier* nf = Parent::notifier();
  1.1889 -        for (nf->first(it); it != INVALID; nf->next(it)) {
  1.1890 -          Parent::set(it, 0);
  1.1891 -        }
  1.1892 -      }
  1.1893 -    };
  1.1894 -
  1.1895 -  public:
  1.1896 -
  1.1897 -    /// \brief Constructor.
  1.1898 -    ///
  1.1899 -    /// Constructor for creating in-degree map.
  1.1900 -    explicit InDegMap(const Digraph& digraph)
  1.1901 -      : _digraph(digraph), _deg(digraph) {
  1.1902 -      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  1.1903 -
  1.1904 -      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  1.1905 -        _deg[it] = countInArcs(_digraph, it);
  1.1906 -      }
  1.1907 -    }
  1.1908 -
  1.1909 -    /// Gives back the in-degree of a Node.
  1.1910 -    int operator[](const Key& key) const {
  1.1911 -      return _deg[key];
  1.1912 -    }
  1.1913 -
  1.1914 -  protected:
  1.1915 -
  1.1916 -    typedef typename Digraph::Arc Arc;
  1.1917 -
  1.1918 -    virtual void add(const Arc& arc) {
  1.1919 -      ++_deg[_digraph.target(arc)];
  1.1920 -    }
  1.1921 -
  1.1922 -    virtual void add(const std::vector<Arc>& arcs) {
  1.1923 -      for (int i = 0; i < int(arcs.size()); ++i) {
  1.1924 -        ++_deg[_digraph.target(arcs[i])];
  1.1925 -      }
  1.1926 -    }
  1.1927 -
  1.1928 -    virtual void erase(const Arc& arc) {
  1.1929 -      --_deg[_digraph.target(arc)];
  1.1930 -    }
  1.1931 -
  1.1932 -    virtual void erase(const std::vector<Arc>& arcs) {
  1.1933 -      for (int i = 0; i < int(arcs.size()); ++i) {
  1.1934 -        --_deg[_digraph.target(arcs[i])];
  1.1935 -      }
  1.1936 -    }
  1.1937 -
  1.1938 -    virtual void build() {
  1.1939 -      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  1.1940 -        _deg[it] = countInArcs(_digraph, it);
  1.1941 -      }
  1.1942 -    }
  1.1943 -
  1.1944 -    virtual void clear() {
  1.1945 -      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  1.1946 -        _deg[it] = 0;
  1.1947 -      }
  1.1948 -    }
  1.1949 -  private:
  1.1950 -
  1.1951 -    const Digraph& _digraph;
  1.1952 -    AutoNodeMap _deg;
  1.1953 -  };
  1.1954 -
  1.1955 -  /// \brief Map of the node out-degrees.
  1.1956 -  ///
  1.1957 -  /// This map returns the out-degree of a node. Once it is constructed,
  1.1958 -  /// the degrees are stored in a standard NodeMap, so each query is done
  1.1959 -  /// in constant time. On the other hand, the values are updated automatically
  1.1960 -  /// whenever the digraph changes.
  1.1961 -  ///
  1.1962 -  /// \warning Besides addNode() and addArc(), a digraph structure may provide
  1.1963 -  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
  1.1964 -  /// is not guarantied if these additional features are used. For example
  1.1965 -  /// the functions \ref ListDigraph::changeSource() "changeSource()",
  1.1966 -  /// \ref ListDigraph::changeTarget() "changeTarget()" and
  1.1967 -  /// \ref ListDigraph::reverseArc() "reverseArc()"
  1.1968 -  /// of \ref ListDigraph will \e not update the degree values correctly.
  1.1969 -  ///
  1.1970 -  /// \sa InDegMap
  1.1971 -
  1.1972 -  template <typename _Digraph>
  1.1973 -  class OutDegMap
  1.1974 -    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  1.1975 -      ::ItemNotifier::ObserverBase {
  1.1976 -
  1.1977 -  public:
  1.1978 -
  1.1979 -    typedef _Digraph Digraph;
  1.1980 -    typedef int Value;
  1.1981 -    typedef typename Digraph::Node Key;
  1.1982 -
  1.1983 -    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  1.1984 -    ::ItemNotifier::ObserverBase Parent;
  1.1985 -
  1.1986 -  private:
  1.1987 -
  1.1988 -    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
  1.1989 -    public:
  1.1990 -
  1.1991 -      typedef DefaultMap<Digraph, Key, int> Parent;
  1.1992 -
  1.1993 -      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
  1.1994 -
  1.1995 -      virtual void add(const Key& key) {
  1.1996 -        Parent::add(key);
  1.1997 -        Parent::set(key, 0);
  1.1998 -      }
  1.1999 -      virtual void add(const std::vector<Key>& keys) {
  1.2000 -        Parent::add(keys);
  1.2001 -        for (int i = 0; i < int(keys.size()); ++i) {
  1.2002 -          Parent::set(keys[i], 0);
  1.2003 -        }
  1.2004 -      }
  1.2005 -      virtual void build() {
  1.2006 -        Parent::build();
  1.2007 -        Key it;
  1.2008 -        typename Parent::Notifier* nf = Parent::notifier();
  1.2009 -        for (nf->first(it); it != INVALID; nf->next(it)) {
  1.2010 -          Parent::set(it, 0);
  1.2011 -        }
  1.2012 -      }
  1.2013 -    };
  1.2014 -
  1.2015 -  public:
  1.2016 -
  1.2017 -    /// \brief Constructor.
  1.2018 -    ///
  1.2019 -    /// Constructor for creating out-degree map.
  1.2020 -    explicit OutDegMap(const Digraph& digraph)
  1.2021 -      : _digraph(digraph), _deg(digraph) {
  1.2022 -      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  1.2023 -
  1.2024 -      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  1.2025 -        _deg[it] = countOutArcs(_digraph, it);
  1.2026 -      }
  1.2027 -    }
  1.2028 -
  1.2029 -    /// Gives back the out-degree of a Node.
  1.2030 -    int operator[](const Key& key) const {
  1.2031 -      return _deg[key];
  1.2032 -    }
  1.2033 -
  1.2034 -  protected:
  1.2035 -
  1.2036 -    typedef typename Digraph::Arc Arc;
  1.2037 -
  1.2038 -    virtual void add(const Arc& arc) {
  1.2039 -      ++_deg[_digraph.source(arc)];
  1.2040 -    }
  1.2041 -
  1.2042 -    virtual void add(const std::vector<Arc>& arcs) {
  1.2043 -      for (int i = 0; i < int(arcs.size()); ++i) {
  1.2044 -        ++_deg[_digraph.source(arcs[i])];
  1.2045 -      }
  1.2046 -    }
  1.2047 -
  1.2048 -    virtual void erase(const Arc& arc) {
  1.2049 -      --_deg[_digraph.source(arc)];
  1.2050 -    }
  1.2051 -
  1.2052 -    virtual void erase(const std::vector<Arc>& arcs) {
  1.2053 -      for (int i = 0; i < int(arcs.size()); ++i) {
  1.2054 -        --_deg[_digraph.source(arcs[i])];
  1.2055 -      }
  1.2056 -    }
  1.2057 -
  1.2058 -    virtual void build() {
  1.2059 -      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  1.2060 -        _deg[it] = countOutArcs(_digraph, it);
  1.2061 -      }
  1.2062 -    }
  1.2063 -
  1.2064 -    virtual void clear() {
  1.2065 -      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  1.2066 -        _deg[it] = 0;
  1.2067 -      }
  1.2068 -    }
  1.2069 -  private:
  1.2070 -
  1.2071 -    const Digraph& _digraph;
  1.2072 -    AutoNodeMap _deg;
  1.2073 -  };
  1.2074 -
  1.2075 -
  1.2076 -  ///Dynamic arc look up between given endpoints.
  1.2077 -
  1.2078 -  ///\ingroup gutils
  1.2079 -  ///Using this class, you can find an arc in a digraph from a given
  1.2080 -  ///source to a given target in amortized time <em>O(log d)</em>,
  1.2081 -  ///where <em>d</em> is the out-degree of the source node.
  1.2082 -  ///
  1.2083 -  ///It is possible to find \e all parallel arcs between two nodes with
  1.2084 -  ///the \c findFirst() and \c findNext() members.
  1.2085 -  ///
  1.2086 -  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
  1.2087 -  ///digraph is not changed so frequently.
  1.2088 -  ///
  1.2089 -  ///This class uses a self-adjusting binary search tree, Sleator's
  1.2090 -  ///and Tarjan's Splay tree for guarantee the logarithmic amortized
  1.2091 -  ///time bound for arc lookups. This class also guarantees the
  1.2092 -  ///optimal time bound in a constant factor for any distribution of
  1.2093 -  ///queries.
  1.2094 -  ///
  1.2095 -  ///\tparam G The type of the underlying digraph.
  1.2096 -  ///
  1.2097 -  ///\sa ArcLookUp
  1.2098 -  ///\sa AllArcLookUp
  1.2099 -  template<class G>
  1.2100 -  class DynArcLookUp
  1.2101 -    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
  1.2102 -  {
  1.2103 -  public:
  1.2104 -    typedef typename ItemSetTraits<G, typename G::Arc>
  1.2105 -    ::ItemNotifier::ObserverBase Parent;
  1.2106 -
  1.2107 -    TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1.2108 -    typedef G Digraph;
  1.2109 -
  1.2110 -  protected:
  1.2111 -
  1.2112 -    class AutoNodeMap : public DefaultMap<G, Node, Arc> {
  1.2113 -    public:
  1.2114 -
  1.2115 -      typedef DefaultMap<G, Node, Arc> Parent;
  1.2116 -
  1.2117 -      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
  1.2118 -
  1.2119 -      virtual void add(const Node& node) {
  1.2120 -        Parent::add(node);
  1.2121 -        Parent::set(node, INVALID);
  1.2122 -      }
  1.2123 -
  1.2124 -      virtual void add(const std::vector<Node>& nodes) {
  1.2125 -        Parent::add(nodes);
  1.2126 -        for (int i = 0; i < int(nodes.size()); ++i) {
  1.2127 -          Parent::set(nodes[i], INVALID);
  1.2128 -        }
  1.2129 -      }
  1.2130 -
  1.2131 -      virtual void build() {
  1.2132 -        Parent::build();
  1.2133 -        Node it;
  1.2134 -        typename Parent::Notifier* nf = Parent::notifier();
  1.2135 -        for (nf->first(it); it != INVALID; nf->next(it)) {
  1.2136 -          Parent::set(it, INVALID);
  1.2137 -        }
  1.2138 -      }
  1.2139 -    };
  1.2140 -
  1.2141 -    const Digraph &_g;
  1.2142 -    AutoNodeMap _head;
  1.2143 -    typename Digraph::template ArcMap<Arc> _parent;
  1.2144 -    typename Digraph::template ArcMap<Arc> _left;
  1.2145 -    typename Digraph::template ArcMap<Arc> _right;
  1.2146 -
  1.2147 -    class ArcLess {
  1.2148 -      const Digraph &g;
  1.2149 -    public:
  1.2150 -      ArcLess(const Digraph &_g) : g(_g) {}
  1.2151 -      bool operator()(Arc a,Arc b) const
  1.2152 -      {
  1.2153 -        return g.target(a)<g.target(b);
  1.2154 -      }
  1.2155 -    };
  1.2156 -
  1.2157 -  public:
  1.2158 -
  1.2159 -    ///Constructor
  1.2160 -
  1.2161 -    ///Constructor.
  1.2162 -    ///
  1.2163 -    ///It builds up the search database.
  1.2164 -    DynArcLookUp(const Digraph &g)
  1.2165 -      : _g(g),_head(g),_parent(g),_left(g),_right(g)
  1.2166 -    {
  1.2167 -      Parent::attach(_g.notifier(typename Digraph::Arc()));
  1.2168 -      refresh();
  1.2169 -    }
  1.2170 -
  1.2171 -  protected:
  1.2172 -
  1.2173 -    virtual void add(const Arc& arc) {
  1.2174 -      insert(arc);
  1.2175 -    }
  1.2176 -
  1.2177 -    virtual void add(const std::vector<Arc>& arcs) {
  1.2178 -      for (int i = 0; i < int(arcs.size()); ++i) {
  1.2179 -        insert(arcs[i]);
  1.2180 -      }
  1.2181 -    }
  1.2182 -
  1.2183 -    virtual void erase(const Arc& arc) {
  1.2184 -      remove(arc);
  1.2185 -    }
  1.2186 -
  1.2187 -    virtual void erase(const std::vector<Arc>& arcs) {
  1.2188 -      for (int i = 0; i < int(arcs.size()); ++i) {
  1.2189 -        remove(arcs[i]);
  1.2190 -      }
  1.2191 -    }
  1.2192 -
  1.2193 -    virtual void build() {
  1.2194 -      refresh();
  1.2195 -    }
  1.2196 -
  1.2197 -    virtual void clear() {
  1.2198 -      for(NodeIt n(_g);n!=INVALID;++n) {
  1.2199 -        _head.set(n, INVALID);
  1.2200 -      }
  1.2201 -    }
  1.2202 -
  1.2203 -    void insert(Arc arc) {
  1.2204 -      Node s = _g.source(arc);
  1.2205 -      Node t = _g.target(arc);
  1.2206 -      _left.set(arc, INVALID);
  1.2207 -      _right.set(arc, INVALID);
  1.2208 -
  1.2209 -      Arc e = _head[s];
  1.2210 -      if (e == INVALID) {
  1.2211 -        _head.set(s, arc);
  1.2212 -        _parent.set(arc, INVALID);
  1.2213 -        return;
  1.2214 -      }
  1.2215 -      while (true) {
  1.2216 -        if (t < _g.target(e)) {
  1.2217 -          if (_left[e] == INVALID) {
  1.2218 -            _left.set(e, arc);
  1.2219 -            _parent.set(arc, e);
  1.2220 -            splay(arc);
  1.2221 -            return;
  1.2222 -          } else {
  1.2223 -            e = _left[e];
  1.2224 -          }
  1.2225 -        } else {
  1.2226 -          if (_right[e] == INVALID) {
  1.2227 -            _right.set(e, arc);
  1.2228 -            _parent.set(arc, e);
  1.2229 -            splay(arc);
  1.2230 -            return;
  1.2231 -          } else {
  1.2232 -            e = _right[e];
  1.2233 -          }
  1.2234 -        }
  1.2235 -      }
  1.2236 -    }
  1.2237 -
  1.2238 -    void remove(Arc arc) {
  1.2239 -      if (_left[arc] == INVALID) {
  1.2240 -        if (_right[arc] != INVALID) {
  1.2241 -          _parent.set(_right[arc], _parent[arc]);
  1.2242 -        }
  1.2243 -        if (_parent[arc] != INVALID) {
  1.2244 -          if (_left[_parent[arc]] == arc) {
  1.2245 -            _left.set(_parent[arc], _right[arc]);
  1.2246 -          } else {
  1.2247 -            _right.set(_parent[arc], _right[arc]);
  1.2248 -          }
  1.2249 -        } else {
  1.2250 -          _head.set(_g.source(arc), _right[arc]);
  1.2251 -        }
  1.2252 -      } else if (_right[arc] == INVALID) {
  1.2253 -        _parent.set(_left[arc], _parent[arc]);
  1.2254 -        if (_parent[arc] != INVALID) {
  1.2255 -          if (_left[_parent[arc]] == arc) {
  1.2256 -            _left.set(_parent[arc], _left[arc]);
  1.2257 -          } else {
  1.2258 -            _right.set(_parent[arc], _left[arc]);
  1.2259 -          }
  1.2260 -        } else {
  1.2261 -          _head.set(_g.source(arc), _left[arc]);
  1.2262 -        }
  1.2263 -      } else {
  1.2264 -        Arc e = _left[arc];
  1.2265 -        if (_right[e] != INVALID) {
  1.2266 -          e = _right[e];
  1.2267 -          while (_right[e] != INVALID) {
  1.2268 -            e = _right[e];
  1.2269 -          }
  1.2270 -          Arc s = _parent[e];
  1.2271 -          _right.set(_parent[e], _left[e]);
  1.2272 -          if (_left[e] != INVALID) {
  1.2273 -            _parent.set(_left[e], _parent[e]);
  1.2274 -          }
  1.2275 -
  1.2276 -          _left.set(e, _left[arc]);
  1.2277 -          _parent.set(_left[arc], e);
  1.2278 -          _right.set(e, _right[arc]);
  1.2279 -          _parent.set(_right[arc], e);
  1.2280 -
  1.2281 -          _parent.set(e, _parent[arc]);
  1.2282 -          if (_parent[arc] != INVALID) {
  1.2283 -            if (_left[_parent[arc]] == arc) {
  1.2284 -              _left.set(_parent[arc], e);
  1.2285 -            } else {
  1.2286 -              _right.set(_parent[arc], e);
  1.2287 -            }
  1.2288 -          }
  1.2289 -          splay(s);
  1.2290 -        } else {
  1.2291 -          _right.set(e, _right[arc]);
  1.2292 -          _parent.set(_right[arc], e);
  1.2293 -
  1.2294 -          if (_parent[arc] != INVALID) {
  1.2295 -            if (_left[_parent[arc]] == arc) {
  1.2296 -              _left.set(_parent[arc], e);
  1.2297 -            } else {
  1.2298 -              _right.set(_parent[arc], e);
  1.2299 -            }
  1.2300 -          } else {
  1.2301 -            _head.set(_g.source(arc), e);
  1.2302 -          }
  1.2303 -        }
  1.2304 -      }
  1.2305 -    }
  1.2306 -
  1.2307 -    Arc refreshRec(std::vector<Arc> &v,int a,int b)
  1.2308 -    {
  1.2309 -      int m=(a+b)/2;
  1.2310 -      Arc me=v[m];
  1.2311 -      if (a < m) {
  1.2312 -        Arc left = refreshRec(v,a,m-1);
  1.2313 -        _left.set(me, left);
  1.2314 -        _parent.set(left, me);
  1.2315 -      } else {
  1.2316 -        _left.set(me, INVALID);
  1.2317 -      }
  1.2318 -      if (m < b) {
  1.2319 -        Arc right = refreshRec(v,m+1,b);
  1.2320 -        _right.set(me, right);
  1.2321 -        _parent.set(right, me);
  1.2322 -      } else {
  1.2323 -        _right.set(me, INVALID);
  1.2324 -      }
  1.2325 -      return me;
  1.2326 -    }
  1.2327 -
  1.2328 -    void refresh() {
  1.2329 -      for(NodeIt n(_g);n!=INVALID;++n) {
  1.2330 -        std::vector<Arc> v;
  1.2331 -        for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  1.2332 -        if(v.size()) {
  1.2333 -          std::sort(v.begin(),v.end(),ArcLess(_g));
  1.2334 -          Arc head = refreshRec(v,0,v.size()-1);
  1.2335 -          _head.set(n, head);
  1.2336 -          _parent.set(head, INVALID);
  1.2337 -        }
  1.2338 -        else _head.set(n, INVALID);
  1.2339 -      }
  1.2340 -    }
  1.2341 -
  1.2342 -    void zig(Arc v) {
  1.2343 -      Arc w = _parent[v];
  1.2344 -      _parent.set(v, _parent[w]);
  1.2345 -      _parent.set(w, v);
  1.2346 -      _left.set(w, _right[v]);
  1.2347 -      _right.set(v, w);
  1.2348 -      if (_parent[v] != INVALID) {
  1.2349 -        if (_right[_parent[v]] == w) {
  1.2350 -          _right.set(_parent[v], v);
  1.2351 -        } else {
  1.2352 -          _left.set(_parent[v], v);
  1.2353 -        }
  1.2354 -      }
  1.2355 -      if (_left[w] != INVALID){
  1.2356 -        _parent.set(_left[w], w);
  1.2357 -      }
  1.2358 -    }
  1.2359 -
  1.2360 -    void zag(Arc v) {
  1.2361 -      Arc w = _parent[v];
  1.2362 -      _parent.set(v, _parent[w]);
  1.2363 -      _parent.set(w, v);
  1.2364 -      _right.set(w, _left[v]);
  1.2365 -      _left.set(v, w);
  1.2366 -      if (_parent[v] != INVALID){
  1.2367 -        if (_left[_parent[v]] == w) {
  1.2368 -          _left.set(_parent[v], v);
  1.2369 -        } else {
  1.2370 -          _right.set(_parent[v], v);
  1.2371 -        }
  1.2372 -      }
  1.2373 -      if (_right[w] != INVALID){
  1.2374 -        _parent.set(_right[w], w);
  1.2375 -      }
  1.2376 -    }
  1.2377 -
  1.2378 -    void splay(Arc v) {
  1.2379 -      while (_parent[v] != INVALID) {
  1.2380 -        if (v == _left[_parent[v]]) {
  1.2381 -          if (_parent[_parent[v]] == INVALID) {
  1.2382 -            zig(v);
  1.2383 -          } else {
  1.2384 -            if (_parent[v] == _left[_parent[_parent[v]]]) {
  1.2385 -              zig(_parent[v]);
  1.2386 -              zig(v);
  1.2387 -            } else {
  1.2388 -              zig(v);
  1.2389 -              zag(v);
  1.2390 -            }
  1.2391 -          }
  1.2392 -        } else {
  1.2393 -          if (_parent[_parent[v]] == INVALID) {
  1.2394 -            zag(v);
  1.2395 -          } else {
  1.2396 -            if (_parent[v] == _left[_parent[_parent[v]]]) {
  1.2397 -              zag(v);
  1.2398 -              zig(v);
  1.2399 -            } else {
  1.2400 -              zag(_parent[v]);
  1.2401 -              zag(v);
  1.2402 -            }
  1.2403 -          }
  1.2404 -        }
  1.2405 -      }
  1.2406 -      _head[_g.source(v)] = v;
  1.2407 -    }
  1.2408 -
  1.2409 -
  1.2410 -  public:
  1.2411 -
  1.2412 -    ///Find an arc between two nodes.
  1.2413 -
  1.2414 -    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
  1.2415 -    /// <em>d</em> is the number of outgoing arcs of \c s.
  1.2416 -    ///\param s The source node
  1.2417 -    ///\param t The target node
  1.2418 -    ///\return An arc from \c s to \c t if there exists,
  1.2419 -    ///\ref INVALID otherwise.
  1.2420 -    Arc operator()(Node s, Node t) const
  1.2421 -    {
  1.2422 -      Arc a = _head[s];
  1.2423 -      while (true) {
  1.2424 -        if (_g.target(a) == t) {
  1.2425 -          const_cast<DynArcLookUp&>(*this).splay(a);
  1.2426 -          return a;
  1.2427 -        } else if (t < _g.target(a)) {
  1.2428 -          if (_left[a] == INVALID) {
  1.2429 -            const_cast<DynArcLookUp&>(*this).splay(a);
  1.2430 -            return INVALID;
  1.2431 -          } else {
  1.2432 -            a = _left[a];
  1.2433 -          }
  1.2434 -        } else  {
  1.2435 -          if (_right[a] == INVALID) {
  1.2436 -            const_cast<DynArcLookUp&>(*this).splay(a);
  1.2437 -            return INVALID;
  1.2438 -          } else {
  1.2439 -            a = _right[a];
  1.2440 -          }
  1.2441 -        }
  1.2442 -      }
  1.2443 -    }
  1.2444 -
  1.2445 -    ///Find the first arc between two nodes.
  1.2446 -
  1.2447 -    ///Find the first arc between two nodes in time
  1.2448 -    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
  1.2449 -    /// outgoing arcs of \c s.
  1.2450 -    ///\param s The source node
  1.2451 -    ///\param t The target node
  1.2452 -    ///\return An arc from \c s to \c t if there exists, \ref INVALID
  1.2453 -    /// otherwise.
  1.2454 -    Arc findFirst(Node s, Node t) const
  1.2455 -    {
  1.2456 -      Arc a = _head[s];
  1.2457 -      Arc r = INVALID;
  1.2458 -      while (true) {
  1.2459 -        if (_g.target(a) < t) {
  1.2460 -          if (_right[a] == INVALID) {
  1.2461 -            const_cast<DynArcLookUp&>(*this).splay(a);
  1.2462 -            return r;
  1.2463 -          } else {
  1.2464 -            a = _right[a];
  1.2465 -          }
  1.2466 -        } else {
  1.2467 -          if (_g.target(a) == t) {
  1.2468 -            r = a;
  1.2469 -          }
  1.2470 -          if (_left[a] == INVALID) {
  1.2471 -            const_cast<DynArcLookUp&>(*this).splay(a);
  1.2472 -            return r;
  1.2473 -          } else {
  1.2474 -            a = _left[a];
  1.2475 -          }
  1.2476 -        }
  1.2477 -      }
  1.2478 -    }
  1.2479 -
  1.2480 -    ///Find the next arc between two nodes.
  1.2481 -
  1.2482 -    ///Find the next arc between two nodes in time
  1.2483 -    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
  1.2484 -    /// outgoing arcs of \c s.
  1.2485 -    ///\param s The source node
  1.2486 -    ///\param t The target node
  1.2487 -    ///\return An arc from \c s to \c t if there exists, \ref INVALID
  1.2488 -    /// otherwise.
  1.2489 -
  1.2490 -    ///\note If \c e is not the result of the previous \c findFirst()
  1.2491 -    ///operation then the amorized time bound can not be guaranteed.
  1.2492 -#ifdef DOXYGEN
  1.2493 -    Arc findNext(Node s, Node t, Arc a) const
  1.2494 -#else
  1.2495 -    Arc findNext(Node, Node t, Arc a) const
  1.2496 -#endif
  1.2497 -    {
  1.2498 -      if (_right[a] != INVALID) {
  1.2499 -        a = _right[a];
  1.2500 -        while (_left[a] != INVALID) {
  1.2501 -          a = _left[a];
  1.2502 -        }
  1.2503 -        const_cast<DynArcLookUp&>(*this).splay(a);
  1.2504 -      } else {
  1.2505 -        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
  1.2506 -          a = _parent[a];
  1.2507 -        }
  1.2508 -        if (_parent[a] == INVALID) {
  1.2509 -          return INVALID;
  1.2510 -        } else {
  1.2511 -          a = _parent[a];
  1.2512 -          const_cast<DynArcLookUp&>(*this).splay(a);
  1.2513 -        }
  1.2514 -      }
  1.2515 -      if (_g.target(a) == t) return a;
  1.2516 -      else return INVALID;
  1.2517 -    }
  1.2518 -
  1.2519 -  };
  1.2520 -
  1.2521 -  ///Fast arc look up between given endpoints.
  1.2522 -
  1.2523 -  ///\ingroup gutils
  1.2524 -  ///Using this class, you can find an arc in a digraph from a given
  1.2525 -  ///source to a given target in time <em>O(log d)</em>,
  1.2526 -  ///where <em>d</em> is the out-degree of the source node.
  1.2527 -  ///
  1.2528 -  ///It is not possible to find \e all parallel arcs between two nodes.
  1.2529 -  ///Use \ref AllArcLookUp for this purpose.
  1.2530 -  ///
  1.2531 -  ///\warning This class is static, so you should refresh() (or at least
  1.2532 -  ///refresh(Node)) this data structure
  1.2533 -  ///whenever the digraph changes. This is a time consuming (superlinearly
  1.2534 -  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  1.2535 -  ///
  1.2536 -  ///\tparam G The type of the underlying digraph.
  1.2537 -  ///
  1.2538 -  ///\sa DynArcLookUp
  1.2539 -  ///\sa AllArcLookUp
  1.2540 -  template<class G>
  1.2541 -  class ArcLookUp
  1.2542 -  {
  1.2543 -  public:
  1.2544 -    TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1.2545 -    typedef G Digraph;
  1.2546 -
  1.2547 -  protected:
  1.2548 -    const Digraph &_g;
  1.2549 -    typename Digraph::template NodeMap<Arc> _head;
  1.2550 -    typename Digraph::template ArcMap<Arc> _left;
  1.2551 -    typename Digraph::template ArcMap<Arc> _right;
  1.2552 -
  1.2553 -    class ArcLess {
  1.2554 -      const Digraph &g;
  1.2555 -    public:
  1.2556 -      ArcLess(const Digraph &_g) : g(_g) {}
  1.2557 -      bool operator()(Arc a,Arc b) const
  1.2558 -      {
  1.2559 -        return g.target(a)<g.target(b);
  1.2560 -      }
  1.2561 -    };
  1.2562 -
  1.2563 -  public:
  1.2564 -
  1.2565 -    ///Constructor
  1.2566 -
  1.2567 -    ///Constructor.
  1.2568 -    ///
  1.2569 -    ///It builds up the search database, which remains valid until the digraph
  1.2570 -    ///changes.
  1.2571 -    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
  1.2572 -
  1.2573 -  private:
  1.2574 -    Arc refreshRec(std::vector<Arc> &v,int a,int b)
  1.2575 -    {
  1.2576 -      int m=(a+b)/2;
  1.2577 -      Arc me=v[m];
  1.2578 -      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
  1.2579 -      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
  1.2580 -      return me;
  1.2581 -    }
  1.2582 -  public:
  1.2583 -    ///Refresh the data structure at a node.
  1.2584 -
  1.2585 -    ///Build up the search database of node \c n.
  1.2586 -    ///
  1.2587 -    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
  1.2588 -    ///the number of the outgoing arcs of \c n.
  1.2589 -    void refresh(Node n)
  1.2590 -    {
  1.2591 -      std::vector<Arc> v;
  1.2592 -      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  1.2593 -      if(v.size()) {
  1.2594 -        std::sort(v.begin(),v.end(),ArcLess(_g));
  1.2595 -        _head[n]=refreshRec(v,0,v.size()-1);
  1.2596 -      }
  1.2597 -      else _head[n]=INVALID;
  1.2598 -    }
  1.2599 -    ///Refresh the full data structure.
  1.2600 -
  1.2601 -    ///Build up the full search database. In fact, it simply calls
  1.2602 -    ///\ref refresh(Node) "refresh(n)" for each node \c n.
  1.2603 -    ///
  1.2604 -    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
  1.2605 -    ///the number of the arcs of \c n and <em>D</em> is the maximum
  1.2606 -    ///out-degree of the digraph.
  1.2607 -
  1.2608 -    void refresh()
  1.2609 -    {
  1.2610 -      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
  1.2611 -    }
  1.2612 -
  1.2613 -    ///Find an arc between two nodes.
  1.2614 -
  1.2615 -    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
  1.2616 -    /// <em>d</em> is the number of outgoing arcs of \c s.
  1.2617 -    ///\param s The source node
  1.2618 -    ///\param t The target node
  1.2619 -    ///\return An arc from \c s to \c t if there exists,
  1.2620 -    ///\ref INVALID otherwise.
  1.2621 -    ///
  1.2622 -    ///\warning If you change the digraph, refresh() must be called before using
  1.2623 -    ///this operator. If you change the outgoing arcs of
  1.2624 -    ///a single node \c n, then
  1.2625 -    ///\ref refresh(Node) "refresh(n)" is enough.
  1.2626 -    ///
  1.2627 -    Arc operator()(Node s, Node t) const
  1.2628 -    {
  1.2629 -      Arc e;
  1.2630 -      for(e=_head[s];
  1.2631 -          e!=INVALID&&_g.target(e)!=t;
  1.2632 -          e = t < _g.target(e)?_left[e]:_right[e]) ;
  1.2633 -      return e;
  1.2634 -    }
  1.2635 -
  1.2636 -  };
  1.2637 -
  1.2638 -  ///Fast look up of all arcs between given endpoints.
  1.2639 -
  1.2640 -  ///\ingroup gutils
  1.2641 -  ///This class is the same as \ref ArcLookUp, with the addition
  1.2642 -  ///that it makes it possible to find all arcs between given endpoints.
  1.2643 -  ///
  1.2644 -  ///\warning This class is static, so you should refresh() (or at least
  1.2645 -  ///refresh(Node)) this data structure
  1.2646 -  ///whenever the digraph changes. This is a time consuming (superlinearly
  1.2647 -  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  1.2648 -  ///
  1.2649 -  ///\tparam G The type of the underlying digraph.
  1.2650 -  ///
  1.2651 -  ///\sa DynArcLookUp
  1.2652 -  ///\sa ArcLookUp
  1.2653 -  template<class G>
  1.2654 -  class AllArcLookUp : public ArcLookUp<G>
  1.2655 -  {
  1.2656 -    using ArcLookUp<G>::_g;
  1.2657 -    using ArcLookUp<G>::_right;
  1.2658 -    using ArcLookUp<G>::_left;
  1.2659 -    using ArcLookUp<G>::_head;
  1.2660 -
  1.2661 -    TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1.2662 -    typedef G Digraph;
  1.2663 -
  1.2664 -    typename Digraph::template ArcMap<Arc> _next;
  1.2665 -
  1.2666 -    Arc refreshNext(Arc head,Arc next=INVALID)
  1.2667 -    {
  1.2668 -      if(head==INVALID) return next;
  1.2669 -      else {
  1.2670 -        next=refreshNext(_right[head],next);
  1.2671 -//         _next[head]=next;
  1.2672 -        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
  1.2673 -          ? next : INVALID;
  1.2674 -        return refreshNext(_left[head],head);
  1.2675 -      }
  1.2676 -    }
  1.2677 -
  1.2678 -    void refreshNext()
  1.2679 -    {
  1.2680 -      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
  1.2681 -    }
  1.2682 -
  1.2683 -  public:
  1.2684 -    ///Constructor
  1.2685 -
  1.2686 -    ///Constructor.
  1.2687 -    ///
  1.2688 -    ///It builds up the search database, which remains valid until the digraph
  1.2689 -    ///changes.
  1.2690 -    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
  1.2691 -
  1.2692 -    ///Refresh the data structure at a node.
  1.2693 -
  1.2694 -    ///Build up the search database of node \c n.
  1.2695 -    ///
  1.2696 -    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
  1.2697 -    ///the number of the outgoing arcs of \c n.
  1.2698 -
  1.2699 -    void refresh(Node n)
  1.2700 -    {
  1.2701 -      ArcLookUp<G>::refresh(n);
  1.2702 -      refreshNext(_head[n]);
  1.2703 -    }
  1.2704 -
  1.2705 -    ///Refresh the full data structure.
  1.2706 -
  1.2707 -    ///Build up the full search database. In fact, it simply calls
  1.2708 -    ///\ref refresh(Node) "refresh(n)" for each node \c n.
  1.2709 -    ///
  1.2710 -    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
  1.2711 -    ///the number of the arcs of \c n and <em>D</em> is the maximum
  1.2712 -    ///out-degree of the digraph.
  1.2713 -
  1.2714 -    void refresh()
  1.2715 -    {
  1.2716 -      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
  1.2717 -    }
  1.2718 -
  1.2719 -    ///Find an arc between two nodes.
  1.2720 -
  1.2721 -    ///Find an arc between two nodes.
  1.2722 -    ///\param s The source node
  1.2723 -    ///\param t The target node
  1.2724 -    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
  1.2725 -    ///not given, the operator finds the first appropriate arc.
  1.2726 -    ///\return An arc from \c s to \c t after \c prev or
  1.2727 -    ///\ref INVALID if there is no more.
  1.2728 -    ///
  1.2729 -    ///For example, you can count the number of arcs from \c u to \c v in the
  1.2730 -    ///following way.
  1.2731 -    ///\code
  1.2732 -    ///AllArcLookUp<ListDigraph> ae(g);
  1.2733 -    ///...
  1.2734 -    ///int n=0;
  1.2735 -    ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
  1.2736 -    ///\endcode
  1.2737 -    ///
  1.2738 -    ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
  1.2739 -    /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
  1.2740 -    ///consecutive arcs are found in constant time.
  1.2741 -    ///
  1.2742 -    ///\warning If you change the digraph, refresh() must be called before using
  1.2743 -    ///this operator. If you change the outgoing arcs of
  1.2744 -    ///a single node \c n, then
  1.2745 -    ///\ref refresh(Node) "refresh(n)" is enough.
  1.2746 -    ///
  1.2747 -#ifdef DOXYGEN
  1.2748 -    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
  1.2749 -#else
  1.2750 -    using ArcLookUp<G>::operator() ;
  1.2751 -    Arc operator()(Node s, Node t, Arc prev) const
  1.2752 -    {
  1.2753 -      return prev==INVALID?(*this)(s,t):_next[prev];
  1.2754 -    }
  1.2755 -#endif
  1.2756 -
  1.2757 -  };
  1.2758 -
  1.2759 -  /// @}
  1.2760 -
  1.2761 -} //END OF NAMESPACE LEMON
  1.2762 -
  1.2763 -#endif