lemon/core.h
changeset 221 64613d8fae28
child 229 aebc0161f6e5
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/core.h	Tue Jul 15 18:49:30 2008 +0100
     1.3 @@ -0,0 +1,1851 @@
     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_CORE_H
    1.23 +#define LEMON_CORE_H
    1.24 +
    1.25 +#include <vector>
    1.26 +#include <algorithm>
    1.27 +
    1.28 +#include <lemon/bits/enable_if.h>
    1.29 +#include <lemon/bits/traits.h>
    1.30 +
    1.31 +///\file
    1.32 +///\brief LEMON core utilities.
    1.33 +
    1.34 +namespace lemon {
    1.35 +
    1.36 +  /// \brief Dummy type to make it easier to create invalid iterators.
    1.37 +  ///
    1.38 +  /// Dummy type to make it easier to create invalid iterators.
    1.39 +  /// See \ref INVALID for the usage.
    1.40 +  struct Invalid {
    1.41 +  public:
    1.42 +    bool operator==(Invalid) { return true;  }
    1.43 +    bool operator!=(Invalid) { return false; }
    1.44 +    bool operator< (Invalid) { return false; }
    1.45 +  };
    1.46 +
    1.47 +  /// \brief Invalid iterators.
    1.48 +  ///
    1.49 +  /// \ref Invalid is a global type that converts to each iterator
    1.50 +  /// in such a way that the value of the target iterator will be invalid.
    1.51 +#ifdef LEMON_ONLY_TEMPLATES
    1.52 +  const Invalid INVALID = Invalid();
    1.53 +#else
    1.54 +  extern const Invalid INVALID;
    1.55 +#endif
    1.56 +
    1.57 +  /// \addtogroup gutils
    1.58 +  /// @{
    1.59 +
    1.60 +  ///Creates convenience typedefs for the digraph types and iterators
    1.61 +
    1.62 +  ///This \c \#define creates convenience typedefs for the following types
    1.63 +  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    1.64 +  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
    1.65 +  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
    1.66 +  ///
    1.67 +  ///\note If the graph type is a dependent type, ie. the graph type depend
    1.68 +  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
    1.69 +  ///macro.
    1.70 +#define DIGRAPH_TYPEDEFS(Digraph)                                       \
    1.71 +  typedef Digraph::Node Node;                                           \
    1.72 +  typedef Digraph::NodeIt NodeIt;                                       \
    1.73 +  typedef Digraph::Arc Arc;                                             \
    1.74 +  typedef Digraph::ArcIt ArcIt;                                         \
    1.75 +  typedef Digraph::InArcIt InArcIt;                                     \
    1.76 +  typedef Digraph::OutArcIt OutArcIt;                                   \
    1.77 +  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
    1.78 +  typedef Digraph::NodeMap<int> IntNodeMap;                             \
    1.79 +  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
    1.80 +  typedef Digraph::ArcMap<bool> BoolArcMap;                             \
    1.81 +  typedef Digraph::ArcMap<int> IntArcMap;                               \
    1.82 +  typedef Digraph::ArcMap<double> DoubleArcMap
    1.83 +
    1.84 +  ///Creates convenience typedefs for the digraph types and iterators
    1.85 +
    1.86 +  ///\see DIGRAPH_TYPEDEFS
    1.87 +  ///
    1.88 +  ///\note Use this macro, if the graph type is a dependent type,
    1.89 +  ///ie. the graph type depend on a template parameter.
    1.90 +#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
    1.91 +  typedef typename Digraph::Node Node;                                  \
    1.92 +  typedef typename Digraph::NodeIt NodeIt;                              \
    1.93 +  typedef typename Digraph::Arc Arc;                                    \
    1.94 +  typedef typename Digraph::ArcIt ArcIt;                                \
    1.95 +  typedef typename Digraph::InArcIt InArcIt;                            \
    1.96 +  typedef typename Digraph::OutArcIt OutArcIt;                          \
    1.97 +  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
    1.98 +  typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
    1.99 +  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
   1.100 +  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
   1.101 +  typedef typename Digraph::template ArcMap<int> IntArcMap;             \
   1.102 +  typedef typename Digraph::template ArcMap<double> DoubleArcMap
   1.103 +
   1.104 +  ///Creates convenience typedefs for the graph types and iterators
   1.105 +
   1.106 +  ///This \c \#define creates the same convenience typedefs as defined
   1.107 +  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
   1.108 +  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
   1.109 +  ///\c DoubleEdgeMap.
   1.110 +  ///
   1.111 +  ///\note If the graph type is a dependent type, ie. the graph type depend
   1.112 +  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
   1.113 +  ///macro.
   1.114 +#define GRAPH_TYPEDEFS(Graph)                                           \
   1.115 +  DIGRAPH_TYPEDEFS(Graph);                                              \
   1.116 +  typedef Graph::Edge Edge;                                             \
   1.117 +  typedef Graph::EdgeIt EdgeIt;                                         \
   1.118 +  typedef Graph::IncEdgeIt IncEdgeIt;                                   \
   1.119 +  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
   1.120 +  typedef Graph::EdgeMap<int> IntEdgeMap;                               \
   1.121 +  typedef Graph::EdgeMap<double> DoubleEdgeMap
   1.122 +
   1.123 +  ///Creates convenience typedefs for the graph types and iterators
   1.124 +
   1.125 +  ///\see GRAPH_TYPEDEFS
   1.126 +  ///
   1.127 +  ///\note Use this macro, if the graph type is a dependent type,
   1.128 +  ///ie. the graph type depend on a template parameter.
   1.129 +#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
   1.130 +  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
   1.131 +  typedef typename Graph::Edge Edge;                                    \
   1.132 +  typedef typename Graph::EdgeIt EdgeIt;                                \
   1.133 +  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
   1.134 +  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
   1.135 +  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
   1.136 +  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
   1.137 +
   1.138 +  /// \brief Function to count the items in the graph.
   1.139 +  ///
   1.140 +  /// This function counts the items (nodes, arcs etc) in the graph.
   1.141 +  /// The complexity of the function is O(n) because
   1.142 +  /// it iterates on all of the items.
   1.143 +  template <typename Graph, typename Item>
   1.144 +  inline int countItems(const Graph& g) {
   1.145 +    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
   1.146 +    int num = 0;
   1.147 +    for (ItemIt it(g); it != INVALID; ++it) {
   1.148 +      ++num;
   1.149 +    }
   1.150 +    return num;
   1.151 +  }
   1.152 +
   1.153 +  // Node counting:
   1.154 +
   1.155 +  namespace _core_bits {
   1.156 +
   1.157 +    template <typename Graph, typename Enable = void>
   1.158 +    struct CountNodesSelector {
   1.159 +      static int count(const Graph &g) {
   1.160 +        return countItems<Graph, typename Graph::Node>(g);
   1.161 +      }
   1.162 +    };
   1.163 +
   1.164 +    template <typename Graph>
   1.165 +    struct CountNodesSelector<
   1.166 +      Graph, typename
   1.167 +      enable_if<typename Graph::NodeNumTag, void>::type>
   1.168 +    {
   1.169 +      static int count(const Graph &g) {
   1.170 +        return g.nodeNum();
   1.171 +      }
   1.172 +    };
   1.173 +  }
   1.174 +
   1.175 +  /// \brief Function to count the nodes in the graph.
   1.176 +  ///
   1.177 +  /// This function counts the nodes in the graph.
   1.178 +  /// The complexity of the function is O(n) but for some
   1.179 +  /// graph structures it is specialized to run in O(1).
   1.180 +  ///
   1.181 +  /// If the graph contains a \e nodeNum() member function and a
   1.182 +  /// \e NodeNumTag tag then this function calls directly the member
   1.183 +  /// function to query the cardinality of the node set.
   1.184 +  template <typename Graph>
   1.185 +  inline int countNodes(const Graph& g) {
   1.186 +    return _core_bits::CountNodesSelector<Graph>::count(g);
   1.187 +  }
   1.188 +
   1.189 +  // Arc counting:
   1.190 +
   1.191 +  namespace _core_bits {
   1.192 +
   1.193 +    template <typename Graph, typename Enable = void>
   1.194 +    struct CountArcsSelector {
   1.195 +      static int count(const Graph &g) {
   1.196 +        return countItems<Graph, typename Graph::Arc>(g);
   1.197 +      }
   1.198 +    };
   1.199 +
   1.200 +    template <typename Graph>
   1.201 +    struct CountArcsSelector<
   1.202 +      Graph,
   1.203 +      typename enable_if<typename Graph::ArcNumTag, void>::type>
   1.204 +    {
   1.205 +      static int count(const Graph &g) {
   1.206 +        return g.arcNum();
   1.207 +      }
   1.208 +    };
   1.209 +  }
   1.210 +
   1.211 +  /// \brief Function to count the arcs in the graph.
   1.212 +  ///
   1.213 +  /// This function counts the arcs in the graph.
   1.214 +  /// The complexity of the function is O(e) but for some
   1.215 +  /// graph structures it is specialized to run in O(1).
   1.216 +  ///
   1.217 +  /// If the graph contains a \e arcNum() member function and a
   1.218 +  /// \e EdgeNumTag tag then this function calls directly the member
   1.219 +  /// function to query the cardinality of the arc set.
   1.220 +  template <typename Graph>
   1.221 +  inline int countArcs(const Graph& g) {
   1.222 +    return _core_bits::CountArcsSelector<Graph>::count(g);
   1.223 +  }
   1.224 +
   1.225 +  // Edge counting:
   1.226 +  namespace _core_bits {
   1.227 +
   1.228 +    template <typename Graph, typename Enable = void>
   1.229 +    struct CountEdgesSelector {
   1.230 +      static int count(const Graph &g) {
   1.231 +        return countItems<Graph, typename Graph::Edge>(g);
   1.232 +      }
   1.233 +    };
   1.234 +
   1.235 +    template <typename Graph>
   1.236 +    struct CountEdgesSelector<
   1.237 +      Graph,
   1.238 +      typename enable_if<typename Graph::EdgeNumTag, void>::type>
   1.239 +    {
   1.240 +      static int count(const Graph &g) {
   1.241 +        return g.edgeNum();
   1.242 +      }
   1.243 +    };
   1.244 +  }
   1.245 +
   1.246 +  /// \brief Function to count the edges in the graph.
   1.247 +  ///
   1.248 +  /// This function counts the edges in the graph.
   1.249 +  /// The complexity of the function is O(m) but for some
   1.250 +  /// graph structures it is specialized to run in O(1).
   1.251 +  ///
   1.252 +  /// If the graph contains a \e edgeNum() member function and a
   1.253 +  /// \e EdgeNumTag tag then this function calls directly the member
   1.254 +  /// function to query the cardinality of the edge set.
   1.255 +  template <typename Graph>
   1.256 +  inline int countEdges(const Graph& g) {
   1.257 +    return _core_bits::CountEdgesSelector<Graph>::count(g);
   1.258 +
   1.259 +  }
   1.260 +
   1.261 +
   1.262 +  template <typename Graph, typename DegIt>
   1.263 +  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   1.264 +    int num = 0;
   1.265 +    for (DegIt it(_g, _n); it != INVALID; ++it) {
   1.266 +      ++num;
   1.267 +    }
   1.268 +    return num;
   1.269 +  }
   1.270 +
   1.271 +  /// \brief Function to count the number of the out-arcs from node \c n.
   1.272 +  ///
   1.273 +  /// This function counts the number of the out-arcs from node \c n
   1.274 +  /// in the graph.
   1.275 +  template <typename Graph>
   1.276 +  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
   1.277 +    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
   1.278 +  }
   1.279 +
   1.280 +  /// \brief Function to count the number of the in-arcs to node \c n.
   1.281 +  ///
   1.282 +  /// This function counts the number of the in-arcs to node \c n
   1.283 +  /// in the graph.
   1.284 +  template <typename Graph>
   1.285 +  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
   1.286 +    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
   1.287 +  }
   1.288 +
   1.289 +  /// \brief Function to count the number of the inc-edges to node \c n.
   1.290 +  ///
   1.291 +  /// This function counts the number of the inc-edges to node \c n
   1.292 +  /// in the graph.
   1.293 +  template <typename Graph>
   1.294 +  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
   1.295 +    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
   1.296 +  }
   1.297 +
   1.298 +  namespace _core_bits {
   1.299 +
   1.300 +    template <typename Digraph, typename Item, typename RefMap>
   1.301 +    class MapCopyBase {
   1.302 +    public:
   1.303 +      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
   1.304 +
   1.305 +      virtual ~MapCopyBase() {}
   1.306 +    };
   1.307 +
   1.308 +    template <typename Digraph, typename Item, typename RefMap,
   1.309 +              typename ToMap, typename FromMap>
   1.310 +    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.311 +    public:
   1.312 +
   1.313 +      MapCopy(ToMap& tmap, const FromMap& map)
   1.314 +        : _tmap(tmap), _map(map) {}
   1.315 +
   1.316 +      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   1.317 +        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   1.318 +        for (ItemIt it(digraph); it != INVALID; ++it) {
   1.319 +          _tmap.set(refMap[it], _map[it]);
   1.320 +        }
   1.321 +      }
   1.322 +
   1.323 +    private:
   1.324 +      ToMap& _tmap;
   1.325 +      const FromMap& _map;
   1.326 +    };
   1.327 +
   1.328 +    template <typename Digraph, typename Item, typename RefMap, typename It>
   1.329 +    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.330 +    public:
   1.331 +
   1.332 +      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
   1.333 +
   1.334 +      virtual void copy(const Digraph&, const RefMap& refMap) {
   1.335 +        _it = refMap[_item];
   1.336 +      }
   1.337 +
   1.338 +    private:
   1.339 +      It& _it;
   1.340 +      Item _item;
   1.341 +    };
   1.342 +
   1.343 +    template <typename Digraph, typename Item, typename RefMap, typename Ref>
   1.344 +    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.345 +    public:
   1.346 +
   1.347 +      RefCopy(Ref& map) : _map(map) {}
   1.348 +
   1.349 +      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   1.350 +        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   1.351 +        for (ItemIt it(digraph); it != INVALID; ++it) {
   1.352 +          _map.set(it, refMap[it]);
   1.353 +        }
   1.354 +      }
   1.355 +
   1.356 +    private:
   1.357 +      Ref& _map;
   1.358 +    };
   1.359 +
   1.360 +    template <typename Digraph, typename Item, typename RefMap,
   1.361 +              typename CrossRef>
   1.362 +    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   1.363 +    public:
   1.364 +
   1.365 +      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
   1.366 +
   1.367 +      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   1.368 +        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   1.369 +        for (ItemIt it(digraph); it != INVALID; ++it) {
   1.370 +          _cmap.set(refMap[it], it);
   1.371 +        }
   1.372 +      }
   1.373 +
   1.374 +    private:
   1.375 +      CrossRef& _cmap;
   1.376 +    };
   1.377 +
   1.378 +    template <typename Digraph, typename Enable = void>
   1.379 +    struct DigraphCopySelector {
   1.380 +      template <typename From, typename NodeRefMap, typename ArcRefMap>
   1.381 +      static void copy(Digraph &to, const From& from,
   1.382 +                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   1.383 +        for (typename From::NodeIt it(from); it != INVALID; ++it) {
   1.384 +          nodeRefMap[it] = to.addNode();
   1.385 +        }
   1.386 +        for (typename From::ArcIt it(from); it != INVALID; ++it) {
   1.387 +          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
   1.388 +                                    nodeRefMap[from.target(it)]);
   1.389 +        }
   1.390 +      }
   1.391 +    };
   1.392 +
   1.393 +    template <typename Digraph>
   1.394 +    struct DigraphCopySelector<
   1.395 +      Digraph,
   1.396 +      typename enable_if<typename Digraph::BuildTag, void>::type>
   1.397 +    {
   1.398 +      template <typename From, typename NodeRefMap, typename ArcRefMap>
   1.399 +      static void copy(Digraph &to, const From& from,
   1.400 +                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   1.401 +        to.build(from, nodeRefMap, arcRefMap);
   1.402 +      }
   1.403 +    };
   1.404 +
   1.405 +    template <typename Graph, typename Enable = void>
   1.406 +    struct GraphCopySelector {
   1.407 +      template <typename From, typename NodeRefMap, typename EdgeRefMap>
   1.408 +      static void copy(Graph &to, const From& from,
   1.409 +                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   1.410 +        for (typename From::NodeIt it(from); it != INVALID; ++it) {
   1.411 +          nodeRefMap[it] = to.addNode();
   1.412 +        }
   1.413 +        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
   1.414 +          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
   1.415 +                                      nodeRefMap[from.v(it)]);
   1.416 +        }
   1.417 +      }
   1.418 +    };
   1.419 +
   1.420 +    template <typename Graph>
   1.421 +    struct GraphCopySelector<
   1.422 +      Graph,
   1.423 +      typename enable_if<typename Graph::BuildTag, void>::type>
   1.424 +    {
   1.425 +      template <typename From, typename NodeRefMap, typename EdgeRefMap>
   1.426 +      static void copy(Graph &to, const From& from,
   1.427 +                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   1.428 +        to.build(from, nodeRefMap, edgeRefMap);
   1.429 +      }
   1.430 +    };
   1.431 +
   1.432 +  }
   1.433 +
   1.434 +  /// \brief Class to copy a digraph.
   1.435 +  ///
   1.436 +  /// Class to copy a digraph to another digraph (duplicate a digraph). The
   1.437 +  /// simplest way of using it is through the \c copyDigraph() function.
   1.438 +  ///
   1.439 +  /// This class not just make a copy of a graph, but it can create
   1.440 +  /// references and cross references between the nodes and arcs of
   1.441 +  /// the two graphs, it can copy maps for use with the newly created
   1.442 +  /// graph and copy nodes and arcs.
   1.443 +  ///
   1.444 +  /// To make a copy from a graph, first an instance of DigraphCopy
   1.445 +  /// should be created, then the data belongs to the graph should
   1.446 +  /// assigned to copy. In the end, the \c run() member should be
   1.447 +  /// called.
   1.448 +  ///
   1.449 +  /// The next code copies a graph with several data:
   1.450 +  ///\code
   1.451 +  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
   1.452 +  ///  // create a reference for the nodes
   1.453 +  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   1.454 +  ///  dc.nodeRef(nr);
   1.455 +  ///  // create a cross reference (inverse) for the arcs
   1.456 +  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
   1.457 +  ///  dc.arcCrossRef(acr);
   1.458 +  ///  // copy an arc map
   1.459 +  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
   1.460 +  ///  NewGraph::ArcMap<double> namap(new_graph);
   1.461 +  ///  dc.arcMap(namap, oamap);
   1.462 +  ///  // copy a node
   1.463 +  ///  OrigGraph::Node on;
   1.464 +  ///  NewGraph::Node nn;
   1.465 +  ///  dc.node(nn, on);
   1.466 +  ///  // Executions of copy
   1.467 +  ///  dc.run();
   1.468 +  ///\endcode
   1.469 +  template <typename To, typename From>
   1.470 +  class DigraphCopy {
   1.471 +  private:
   1.472 +
   1.473 +    typedef typename From::Node Node;
   1.474 +    typedef typename From::NodeIt NodeIt;
   1.475 +    typedef typename From::Arc Arc;
   1.476 +    typedef typename From::ArcIt ArcIt;
   1.477 +
   1.478 +    typedef typename To::Node TNode;
   1.479 +    typedef typename To::Arc TArc;
   1.480 +
   1.481 +    typedef typename From::template NodeMap<TNode> NodeRefMap;
   1.482 +    typedef typename From::template ArcMap<TArc> ArcRefMap;
   1.483 +
   1.484 +
   1.485 +  public:
   1.486 +
   1.487 +
   1.488 +    /// \brief Constructor for the DigraphCopy.
   1.489 +    ///
   1.490 +    /// It copies the content of the \c _from digraph into the
   1.491 +    /// \c _to digraph.
   1.492 +    DigraphCopy(To& to, const From& from)
   1.493 +      : _from(from), _to(to) {}
   1.494 +
   1.495 +    /// \brief Destructor of the DigraphCopy
   1.496 +    ///
   1.497 +    /// Destructor of the DigraphCopy
   1.498 +    ~DigraphCopy() {
   1.499 +      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.500 +        delete _node_maps[i];
   1.501 +      }
   1.502 +      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.503 +        delete _arc_maps[i];
   1.504 +      }
   1.505 +
   1.506 +    }
   1.507 +
   1.508 +    /// \brief Copies the node references into the given map.
   1.509 +    ///
   1.510 +    /// Copies the node references into the given map. The parameter
   1.511 +    /// should be a map, which key type is the Node type of the source
   1.512 +    /// graph, while the value type is the Node type of the
   1.513 +    /// destination graph.
   1.514 +    template <typename NodeRef>
   1.515 +    DigraphCopy& nodeRef(NodeRef& map) {
   1.516 +      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
   1.517 +                           NodeRefMap, NodeRef>(map));
   1.518 +      return *this;
   1.519 +    }
   1.520 +
   1.521 +    /// \brief Copies the node cross references into the given map.
   1.522 +    ///
   1.523 +    ///  Copies the node cross references (reverse references) into
   1.524 +    ///  the given map. The parameter should be a map, which key type
   1.525 +    ///  is the Node type of the destination graph, while the value type is
   1.526 +    ///  the Node type of the source graph.
   1.527 +    template <typename NodeCrossRef>
   1.528 +    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
   1.529 +      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
   1.530 +                           NodeRefMap, NodeCrossRef>(map));
   1.531 +      return *this;
   1.532 +    }
   1.533 +
   1.534 +    /// \brief Make copy of the given map.
   1.535 +    ///
   1.536 +    /// Makes copy of the given map for the newly created digraph.
   1.537 +    /// The new map's key type is the destination graph's node type,
   1.538 +    /// and the copied map's key type is the source graph's node type.
   1.539 +    template <typename ToMap, typename FromMap>
   1.540 +    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
   1.541 +      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
   1.542 +                           NodeRefMap, ToMap, FromMap>(tmap, map));
   1.543 +      return *this;
   1.544 +    }
   1.545 +
   1.546 +    /// \brief Make a copy of the given node.
   1.547 +    ///
   1.548 +    /// Make a copy of the given node.
   1.549 +    DigraphCopy& node(TNode& tnode, const Node& snode) {
   1.550 +      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
   1.551 +                           NodeRefMap, TNode>(tnode, snode));
   1.552 +      return *this;
   1.553 +    }
   1.554 +
   1.555 +    /// \brief Copies the arc references into the given map.
   1.556 +    ///
   1.557 +    /// Copies the arc references into the given map.
   1.558 +    template <typename ArcRef>
   1.559 +    DigraphCopy& arcRef(ArcRef& map) {
   1.560 +      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
   1.561 +                          ArcRefMap, ArcRef>(map));
   1.562 +      return *this;
   1.563 +    }
   1.564 +
   1.565 +    /// \brief Copies the arc cross references into the given map.
   1.566 +    ///
   1.567 +    ///  Copies the arc cross references (reverse references) into
   1.568 +    ///  the given map.
   1.569 +    template <typename ArcCrossRef>
   1.570 +    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
   1.571 +      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
   1.572 +                          ArcRefMap, ArcCrossRef>(map));
   1.573 +      return *this;
   1.574 +    }
   1.575 +
   1.576 +    /// \brief Make copy of the given map.
   1.577 +    ///
   1.578 +    /// Makes copy of the given map for the newly created digraph.
   1.579 +    /// The new map's key type is the to digraph's arc type,
   1.580 +    /// and the copied map's key type is the from digraph's arc
   1.581 +    /// type.
   1.582 +    template <typename ToMap, typename FromMap>
   1.583 +    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
   1.584 +      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
   1.585 +                          ArcRefMap, ToMap, FromMap>(tmap, map));
   1.586 +      return *this;
   1.587 +    }
   1.588 +
   1.589 +    /// \brief Make a copy of the given arc.
   1.590 +    ///
   1.591 +    /// Make a copy of the given arc.
   1.592 +    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
   1.593 +      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
   1.594 +                          ArcRefMap, TArc>(tarc, sarc));
   1.595 +      return *this;
   1.596 +    }
   1.597 +
   1.598 +    /// \brief Executes the copies.
   1.599 +    ///
   1.600 +    /// Executes the copies.
   1.601 +    void run() {
   1.602 +      NodeRefMap nodeRefMap(_from);
   1.603 +      ArcRefMap arcRefMap(_from);
   1.604 +      _core_bits::DigraphCopySelector<To>::
   1.605 +        copy(_to, _from, nodeRefMap, arcRefMap);
   1.606 +      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.607 +        _node_maps[i]->copy(_from, nodeRefMap);
   1.608 +      }
   1.609 +      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.610 +        _arc_maps[i]->copy(_from, arcRefMap);
   1.611 +      }
   1.612 +    }
   1.613 +
   1.614 +  protected:
   1.615 +
   1.616 +
   1.617 +    const From& _from;
   1.618 +    To& _to;
   1.619 +
   1.620 +    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
   1.621 +    _node_maps;
   1.622 +
   1.623 +    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
   1.624 +    _arc_maps;
   1.625 +
   1.626 +  };
   1.627 +
   1.628 +  /// \brief Copy a digraph to another digraph.
   1.629 +  ///
   1.630 +  /// Copy a digraph to another digraph. The complete usage of the
   1.631 +  /// function is detailed in the DigraphCopy class, but a short
   1.632 +  /// example shows a basic work:
   1.633 +  ///\code
   1.634 +  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
   1.635 +  ///\endcode
   1.636 +  ///
   1.637 +  /// After the copy the \c nr map will contain the mapping from the
   1.638 +  /// nodes of the \c from digraph to the nodes of the \c to digraph and
   1.639 +  /// \c ecr will contain the mapping from the arcs of the \c to digraph
   1.640 +  /// to the arcs of the \c from digraph.
   1.641 +  ///
   1.642 +  /// \see DigraphCopy
   1.643 +  template <typename To, typename From>
   1.644 +  DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
   1.645 +    return DigraphCopy<To, From>(to, from);
   1.646 +  }
   1.647 +
   1.648 +  /// \brief Class to copy a graph.
   1.649 +  ///
   1.650 +  /// Class to copy a graph to another graph (duplicate a graph). The
   1.651 +  /// simplest way of using it is through the \c copyGraph() function.
   1.652 +  ///
   1.653 +  /// This class not just make a copy of a graph, but it can create
   1.654 +  /// references and cross references between the nodes, edges and arcs of
   1.655 +  /// the two graphs, it can copy maps for use with the newly created
   1.656 +  /// graph and copy nodes, edges and arcs.
   1.657 +  ///
   1.658 +  /// To make a copy from a graph, first an instance of GraphCopy
   1.659 +  /// should be created, then the data belongs to the graph should
   1.660 +  /// assigned to copy. In the end, the \c run() member should be
   1.661 +  /// called.
   1.662 +  ///
   1.663 +  /// The next code copies a graph with several data:
   1.664 +  ///\code
   1.665 +  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
   1.666 +  ///  // create a reference for the nodes
   1.667 +  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   1.668 +  ///  dc.nodeRef(nr);
   1.669 +  ///  // create a cross reference (inverse) for the edges
   1.670 +  ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
   1.671 +  ///  dc.edgeCrossRef(ecr);
   1.672 +  ///  // copy an arc map
   1.673 +  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
   1.674 +  ///  NewGraph::ArcMap<double> namap(new_graph);
   1.675 +  ///  dc.arcMap(namap, oamap);
   1.676 +  ///  // copy a node
   1.677 +  ///  OrigGraph::Node on;
   1.678 +  ///  NewGraph::Node nn;
   1.679 +  ///  dc.node(nn, on);
   1.680 +  ///  // Executions of copy
   1.681 +  ///  dc.run();
   1.682 +  ///\endcode
   1.683 +  template <typename To, typename From>
   1.684 +  class GraphCopy {
   1.685 +  private:
   1.686 +
   1.687 +    typedef typename From::Node Node;
   1.688 +    typedef typename From::NodeIt NodeIt;
   1.689 +    typedef typename From::Arc Arc;
   1.690 +    typedef typename From::ArcIt ArcIt;
   1.691 +    typedef typename From::Edge Edge;
   1.692 +    typedef typename From::EdgeIt EdgeIt;
   1.693 +
   1.694 +    typedef typename To::Node TNode;
   1.695 +    typedef typename To::Arc TArc;
   1.696 +    typedef typename To::Edge TEdge;
   1.697 +
   1.698 +    typedef typename From::template NodeMap<TNode> NodeRefMap;
   1.699 +    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
   1.700 +
   1.701 +    struct ArcRefMap {
   1.702 +      ArcRefMap(const To& to, const From& from,
   1.703 +                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
   1.704 +        : _to(to), _from(from),
   1.705 +          _edge_ref(edge_ref), _node_ref(node_ref) {}
   1.706 +
   1.707 +      typedef typename From::Arc Key;
   1.708 +      typedef typename To::Arc Value;
   1.709 +
   1.710 +      Value operator[](const Key& key) const {
   1.711 +        bool forward = _from.u(key) != _from.v(key) ?
   1.712 +          _node_ref[_from.source(key)] ==
   1.713 +          _to.source(_to.direct(_edge_ref[key], true)) :
   1.714 +          _from.direction(key);
   1.715 +        return _to.direct(_edge_ref[key], forward);
   1.716 +      }
   1.717 +
   1.718 +      const To& _to;
   1.719 +      const From& _from;
   1.720 +      const EdgeRefMap& _edge_ref;
   1.721 +      const NodeRefMap& _node_ref;
   1.722 +    };
   1.723 +
   1.724 +
   1.725 +  public:
   1.726 +
   1.727 +
   1.728 +    /// \brief Constructor for the GraphCopy.
   1.729 +    ///
   1.730 +    /// It copies the content of the \c _from graph into the
   1.731 +    /// \c _to graph.
   1.732 +    GraphCopy(To& to, const From& from)
   1.733 +      : _from(from), _to(to) {}
   1.734 +
   1.735 +    /// \brief Destructor of the GraphCopy
   1.736 +    ///
   1.737 +    /// Destructor of the GraphCopy
   1.738 +    ~GraphCopy() {
   1.739 +      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.740 +        delete _node_maps[i];
   1.741 +      }
   1.742 +      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.743 +        delete _arc_maps[i];
   1.744 +      }
   1.745 +      for (int i = 0; i < int(_edge_maps.size()); ++i) {
   1.746 +        delete _edge_maps[i];
   1.747 +      }
   1.748 +
   1.749 +    }
   1.750 +
   1.751 +    /// \brief Copies the node references into the given map.
   1.752 +    ///
   1.753 +    /// Copies the node references into the given map.
   1.754 +    template <typename NodeRef>
   1.755 +    GraphCopy& nodeRef(NodeRef& map) {
   1.756 +      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
   1.757 +                           NodeRefMap, NodeRef>(map));
   1.758 +      return *this;
   1.759 +    }
   1.760 +
   1.761 +    /// \brief Copies the node cross references into the given map.
   1.762 +    ///
   1.763 +    ///  Copies the node cross references (reverse references) into
   1.764 +    ///  the given map.
   1.765 +    template <typename NodeCrossRef>
   1.766 +    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
   1.767 +      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
   1.768 +                           NodeRefMap, NodeCrossRef>(map));
   1.769 +      return *this;
   1.770 +    }
   1.771 +
   1.772 +    /// \brief Make copy of the given map.
   1.773 +    ///
   1.774 +    /// Makes copy of the given map for the newly created graph.
   1.775 +    /// The new map's key type is the to graph's node type,
   1.776 +    /// and the copied map's key type is the from graph's node
   1.777 +    /// type.
   1.778 +    template <typename ToMap, typename FromMap>
   1.779 +    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
   1.780 +      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
   1.781 +                           NodeRefMap, ToMap, FromMap>(tmap, map));
   1.782 +      return *this;
   1.783 +    }
   1.784 +
   1.785 +    /// \brief Make a copy of the given node.
   1.786 +    ///
   1.787 +    /// Make a copy of the given node.
   1.788 +    GraphCopy& node(TNode& tnode, const Node& snode) {
   1.789 +      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
   1.790 +                           NodeRefMap, TNode>(tnode, snode));
   1.791 +      return *this;
   1.792 +    }
   1.793 +
   1.794 +    /// \brief Copies the arc references into the given map.
   1.795 +    ///
   1.796 +    /// Copies the arc references into the given map.
   1.797 +    template <typename ArcRef>
   1.798 +    GraphCopy& arcRef(ArcRef& map) {
   1.799 +      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
   1.800 +                          ArcRefMap, ArcRef>(map));
   1.801 +      return *this;
   1.802 +    }
   1.803 +
   1.804 +    /// \brief Copies the arc cross references into the given map.
   1.805 +    ///
   1.806 +    ///  Copies the arc cross references (reverse references) into
   1.807 +    ///  the given map.
   1.808 +    template <typename ArcCrossRef>
   1.809 +    GraphCopy& arcCrossRef(ArcCrossRef& map) {
   1.810 +      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
   1.811 +                          ArcRefMap, ArcCrossRef>(map));
   1.812 +      return *this;
   1.813 +    }
   1.814 +
   1.815 +    /// \brief Make copy of the given map.
   1.816 +    ///
   1.817 +    /// Makes copy of the given map for the newly created graph.
   1.818 +    /// The new map's key type is the to graph's arc type,
   1.819 +    /// and the copied map's key type is the from graph's arc
   1.820 +    /// type.
   1.821 +    template <typename ToMap, typename FromMap>
   1.822 +    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
   1.823 +      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
   1.824 +                          ArcRefMap, ToMap, FromMap>(tmap, map));
   1.825 +      return *this;
   1.826 +    }
   1.827 +
   1.828 +    /// \brief Make a copy of the given arc.
   1.829 +    ///
   1.830 +    /// Make a copy of the given arc.
   1.831 +    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
   1.832 +      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
   1.833 +                          ArcRefMap, TArc>(tarc, sarc));
   1.834 +      return *this;
   1.835 +    }
   1.836 +
   1.837 +    /// \brief Copies the edge references into the given map.
   1.838 +    ///
   1.839 +    /// Copies the edge references into the given map.
   1.840 +    template <typename EdgeRef>
   1.841 +    GraphCopy& edgeRef(EdgeRef& map) {
   1.842 +      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
   1.843 +                           EdgeRefMap, EdgeRef>(map));
   1.844 +      return *this;
   1.845 +    }
   1.846 +
   1.847 +    /// \brief Copies the edge cross references into the given map.
   1.848 +    ///
   1.849 +    /// Copies the edge cross references (reverse
   1.850 +    /// references) into the given map.
   1.851 +    template <typename EdgeCrossRef>
   1.852 +    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
   1.853 +      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
   1.854 +                           Edge, EdgeRefMap, EdgeCrossRef>(map));
   1.855 +      return *this;
   1.856 +    }
   1.857 +
   1.858 +    /// \brief Make copy of the given map.
   1.859 +    ///
   1.860 +    /// Makes copy of the given map for the newly created graph.
   1.861 +    /// The new map's key type is the to graph's edge type,
   1.862 +    /// and the copied map's key type is the from graph's edge
   1.863 +    /// type.
   1.864 +    template <typename ToMap, typename FromMap>
   1.865 +    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
   1.866 +      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
   1.867 +                           EdgeRefMap, ToMap, FromMap>(tmap, map));
   1.868 +      return *this;
   1.869 +    }
   1.870 +
   1.871 +    /// \brief Make a copy of the given edge.
   1.872 +    ///
   1.873 +    /// Make a copy of the given edge.
   1.874 +    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
   1.875 +      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
   1.876 +                           EdgeRefMap, TEdge>(tedge, sedge));
   1.877 +      return *this;
   1.878 +    }
   1.879 +
   1.880 +    /// \brief Executes the copies.
   1.881 +    ///
   1.882 +    /// Executes the copies.
   1.883 +    void run() {
   1.884 +      NodeRefMap nodeRefMap(_from);
   1.885 +      EdgeRefMap edgeRefMap(_from);
   1.886 +      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
   1.887 +      _core_bits::GraphCopySelector<To>::
   1.888 +        copy(_to, _from, nodeRefMap, edgeRefMap);
   1.889 +      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.890 +        _node_maps[i]->copy(_from, nodeRefMap);
   1.891 +      }
   1.892 +      for (int i = 0; i < int(_edge_maps.size()); ++i) {
   1.893 +        _edge_maps[i]->copy(_from, edgeRefMap);
   1.894 +      }
   1.895 +      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.896 +        _arc_maps[i]->copy(_from, arcRefMap);
   1.897 +      }
   1.898 +    }
   1.899 +
   1.900 +  private:
   1.901 +
   1.902 +    const From& _from;
   1.903 +    To& _to;
   1.904 +
   1.905 +    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
   1.906 +    _node_maps;
   1.907 +
   1.908 +    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
   1.909 +    _arc_maps;
   1.910 +
   1.911 +    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
   1.912 +    _edge_maps;
   1.913 +
   1.914 +  };
   1.915 +
   1.916 +  /// \brief Copy a graph to another graph.
   1.917 +  ///
   1.918 +  /// Copy a graph to another graph. The complete usage of the
   1.919 +  /// function is detailed in the GraphCopy class, but a short
   1.920 +  /// example shows a basic work:
   1.921 +  ///\code
   1.922 +  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
   1.923 +  ///\endcode
   1.924 +  ///
   1.925 +  /// After the copy the \c nr map will contain the mapping from the
   1.926 +  /// nodes of the \c from graph to the nodes of the \c to graph and
   1.927 +  /// \c ecr will contain the mapping from the arcs of the \c to graph
   1.928 +  /// to the arcs of the \c from graph.
   1.929 +  ///
   1.930 +  /// \see GraphCopy
   1.931 +  template <typename To, typename From>
   1.932 +  GraphCopy<To, From>
   1.933 +  copyGraph(To& to, const From& from) {
   1.934 +    return GraphCopy<To, From>(to, from);
   1.935 +  }
   1.936 +
   1.937 +  namespace _core_bits {
   1.938 +
   1.939 +    template <typename Graph, typename Enable = void>
   1.940 +    struct FindArcSelector {
   1.941 +      typedef typename Graph::Node Node;
   1.942 +      typedef typename Graph::Arc Arc;
   1.943 +      static Arc find(const Graph &g, Node u, Node v, Arc e) {
   1.944 +        if (e == INVALID) {
   1.945 +          g.firstOut(e, u);
   1.946 +        } else {
   1.947 +          g.nextOut(e);
   1.948 +        }
   1.949 +        while (e != INVALID && g.target(e) != v) {
   1.950 +          g.nextOut(e);
   1.951 +        }
   1.952 +        return e;
   1.953 +      }
   1.954 +    };
   1.955 +
   1.956 +    template <typename Graph>
   1.957 +    struct FindArcSelector<
   1.958 +      Graph,
   1.959 +      typename enable_if<typename Graph::FindEdgeTag, void>::type>
   1.960 +    {
   1.961 +      typedef typename Graph::Node Node;
   1.962 +      typedef typename Graph::Arc Arc;
   1.963 +      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
   1.964 +        return g.findArc(u, v, prev);
   1.965 +      }
   1.966 +    };
   1.967 +  }
   1.968 +
   1.969 +  /// \brief Finds an arc between two nodes of a graph.
   1.970 +  ///
   1.971 +  /// Finds an arc from node \c u to node \c v in graph \c g.
   1.972 +  ///
   1.973 +  /// If \c prev is \ref INVALID (this is the default value), then
   1.974 +  /// it finds the first arc from \c u to \c v. Otherwise it looks for
   1.975 +  /// the next arc from \c u to \c v after \c prev.
   1.976 +  /// \return The found arc or \ref INVALID if there is no such an arc.
   1.977 +  ///
   1.978 +  /// Thus you can iterate through each arc from \c u to \c v as it follows.
   1.979 +  ///\code
   1.980 +  /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
   1.981 +  ///   ...
   1.982 +  /// }
   1.983 +  ///\endcode
   1.984 +  ///
   1.985 +  ///\sa ArcLookUp
   1.986 +  ///\sa AllArcLookUp
   1.987 +  ///\sa DynArcLookUp
   1.988 +  ///\sa ConArcIt
   1.989 +  template <typename Graph>
   1.990 +  inline typename Graph::Arc
   1.991 +  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
   1.992 +          typename Graph::Arc prev = INVALID) {
   1.993 +    return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
   1.994 +  }
   1.995 +
   1.996 +  /// \brief Iterator for iterating on arcs connected the same nodes.
   1.997 +  ///
   1.998 +  /// Iterator for iterating on arcs connected the same nodes. It is
   1.999 +  /// higher level interface for the findArc() function. You can
  1.1000 +  /// use it the following way:
  1.1001 +  ///\code
  1.1002 +  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
  1.1003 +  ///   ...
  1.1004 +  /// }
  1.1005 +  ///\endcode
  1.1006 +  ///
  1.1007 +  ///\sa findArc()
  1.1008 +  ///\sa ArcLookUp
  1.1009 +  ///\sa AllArcLookUp
  1.1010 +  ///\sa DynArcLookUp
  1.1011 +  template <typename _Graph>
  1.1012 +  class ConArcIt : public _Graph::Arc {
  1.1013 +  public:
  1.1014 +
  1.1015 +    typedef _Graph Graph;
  1.1016 +    typedef typename Graph::Arc Parent;
  1.1017 +
  1.1018 +    typedef typename Graph::Arc Arc;
  1.1019 +    typedef typename Graph::Node Node;
  1.1020 +
  1.1021 +    /// \brief Constructor.
  1.1022 +    ///
  1.1023 +    /// Construct a new ConArcIt iterating on the arcs which
  1.1024 +    /// connects the \c u and \c v node.
  1.1025 +    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
  1.1026 +      Parent::operator=(findArc(_graph, u, v));
  1.1027 +    }
  1.1028 +
  1.1029 +    /// \brief Constructor.
  1.1030 +    ///
  1.1031 +    /// Construct a new ConArcIt which continues the iterating from
  1.1032 +    /// the \c e arc.
  1.1033 +    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
  1.1034 +
  1.1035 +    /// \brief Increment operator.
  1.1036 +    ///
  1.1037 +    /// It increments the iterator and gives back the next arc.
  1.1038 +    ConArcIt& operator++() {
  1.1039 +      Parent::operator=(findArc(_graph, _graph.source(*this),
  1.1040 +                                _graph.target(*this), *this));
  1.1041 +      return *this;
  1.1042 +    }
  1.1043 +  private:
  1.1044 +    const Graph& _graph;
  1.1045 +  };
  1.1046 +
  1.1047 +  namespace _core_bits {
  1.1048 +
  1.1049 +    template <typename Graph, typename Enable = void>
  1.1050 +    struct FindEdgeSelector {
  1.1051 +      typedef typename Graph::Node Node;
  1.1052 +      typedef typename Graph::Edge Edge;
  1.1053 +      static Edge find(const Graph &g, Node u, Node v, Edge e) {
  1.1054 +        bool b;
  1.1055 +        if (u != v) {
  1.1056 +          if (e == INVALID) {
  1.1057 +            g.firstInc(e, b, u);
  1.1058 +          } else {
  1.1059 +            b = g.u(e) == u;
  1.1060 +            g.nextInc(e, b);
  1.1061 +          }
  1.1062 +          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
  1.1063 +            g.nextInc(e, b);
  1.1064 +          }
  1.1065 +        } else {
  1.1066 +          if (e == INVALID) {
  1.1067 +            g.firstInc(e, b, u);
  1.1068 +          } else {
  1.1069 +            b = true;
  1.1070 +            g.nextInc(e, b);
  1.1071 +          }
  1.1072 +          while (e != INVALID && (!b || g.v(e) != v)) {
  1.1073 +            g.nextInc(e, b);
  1.1074 +          }
  1.1075 +        }
  1.1076 +        return e;
  1.1077 +      }
  1.1078 +    };
  1.1079 +
  1.1080 +    template <typename Graph>
  1.1081 +    struct FindEdgeSelector<
  1.1082 +      Graph,
  1.1083 +      typename enable_if<typename Graph::FindEdgeTag, void>::type>
  1.1084 +    {
  1.1085 +      typedef typename Graph::Node Node;
  1.1086 +      typedef typename Graph::Edge Edge;
  1.1087 +      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
  1.1088 +        return g.findEdge(u, v, prev);
  1.1089 +      }
  1.1090 +    };
  1.1091 +  }
  1.1092 +
  1.1093 +  /// \brief Finds an edge between two nodes of a graph.
  1.1094 +  ///
  1.1095 +  /// Finds an edge from node \c u to node \c v in graph \c g.
  1.1096 +  /// If the node \c u and node \c v is equal then each loop edge
  1.1097 +  /// will be enumerated once.
  1.1098 +  ///
  1.1099 +  /// If \c prev is \ref INVALID (this is the default value), then
  1.1100 +  /// it finds the first arc from \c u to \c v. Otherwise it looks for
  1.1101 +  /// the next arc from \c u to \c v after \c prev.
  1.1102 +  /// \return The found arc or \ref INVALID if there is no such an arc.
  1.1103 +  ///
  1.1104 +  /// Thus you can iterate through each arc from \c u to \c v as it follows.
  1.1105 +  ///\code
  1.1106 +  /// for(Edge e = findEdge(g,u,v); e != INVALID;
  1.1107 +  ///     e = findEdge(g,u,v,e)) {
  1.1108 +  ///   ...
  1.1109 +  /// }
  1.1110 +  ///\endcode
  1.1111 +  ///
  1.1112 +  ///\sa ConEdgeIt
  1.1113 +
  1.1114 +  template <typename Graph>
  1.1115 +  inline typename Graph::Edge
  1.1116 +  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
  1.1117 +            typename Graph::Edge p = INVALID) {
  1.1118 +    return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
  1.1119 +  }
  1.1120 +
  1.1121 +  /// \brief Iterator for iterating on edges connected the same nodes.
  1.1122 +  ///
  1.1123 +  /// Iterator for iterating on edges connected the same nodes. It is
  1.1124 +  /// higher level interface for the findEdge() function. You can
  1.1125 +  /// use it the following way:
  1.1126 +  ///\code
  1.1127 +  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
  1.1128 +  ///   ...
  1.1129 +  /// }
  1.1130 +  ///\endcode
  1.1131 +  ///
  1.1132 +  ///\sa findEdge()
  1.1133 +  template <typename _Graph>
  1.1134 +  class ConEdgeIt : public _Graph::Edge {
  1.1135 +  public:
  1.1136 +
  1.1137 +    typedef _Graph Graph;
  1.1138 +    typedef typename Graph::Edge Parent;
  1.1139 +
  1.1140 +    typedef typename Graph::Edge Edge;
  1.1141 +    typedef typename Graph::Node Node;
  1.1142 +
  1.1143 +    /// \brief Constructor.
  1.1144 +    ///
  1.1145 +    /// Construct a new ConEdgeIt iterating on the edges which
  1.1146 +    /// connects the \c u and \c v node.
  1.1147 +    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
  1.1148 +      Parent::operator=(findEdge(_graph, u, v));
  1.1149 +    }
  1.1150 +
  1.1151 +    /// \brief Constructor.
  1.1152 +    ///
  1.1153 +    /// Construct a new ConEdgeIt which continues the iterating from
  1.1154 +    /// the \c e edge.
  1.1155 +    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
  1.1156 +
  1.1157 +    /// \brief Increment operator.
  1.1158 +    ///
  1.1159 +    /// It increments the iterator and gives back the next edge.
  1.1160 +    ConEdgeIt& operator++() {
  1.1161 +      Parent::operator=(findEdge(_graph, _graph.u(*this),
  1.1162 +                                 _graph.v(*this), *this));
  1.1163 +      return *this;
  1.1164 +    }
  1.1165 +  private:
  1.1166 +    const Graph& _graph;
  1.1167 +  };
  1.1168 +
  1.1169 +
  1.1170 +  ///Dynamic arc look up between given endpoints.
  1.1171 +
  1.1172 +  ///Using this class, you can find an arc in a digraph from a given
  1.1173 +  ///source to a given target in amortized time <em>O(log d)</em>,
  1.1174 +  ///where <em>d</em> is the out-degree of the source node.
  1.1175 +  ///
  1.1176 +  ///It is possible to find \e all parallel arcs between two nodes with
  1.1177 +  ///the \c findFirst() and \c findNext() members.
  1.1178 +  ///
  1.1179 +  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
  1.1180 +  ///digraph is not changed so frequently.
  1.1181 +  ///
  1.1182 +  ///This class uses a self-adjusting binary search tree, Sleator's
  1.1183 +  ///and Tarjan's Splay tree for guarantee the logarithmic amortized
  1.1184 +  ///time bound for arc lookups. This class also guarantees the
  1.1185 +  ///optimal time bound in a constant factor for any distribution of
  1.1186 +  ///queries.
  1.1187 +  ///
  1.1188 +  ///\tparam G The type of the underlying digraph.
  1.1189 +  ///
  1.1190 +  ///\sa ArcLookUp
  1.1191 +  ///\sa AllArcLookUp
  1.1192 +  template<class G>
  1.1193 +  class DynArcLookUp
  1.1194 +    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
  1.1195 +  {
  1.1196 +  public:
  1.1197 +    typedef typename ItemSetTraits<G, typename G::Arc>
  1.1198 +    ::ItemNotifier::ObserverBase Parent;
  1.1199 +
  1.1200 +    TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1.1201 +    typedef G Digraph;
  1.1202 +
  1.1203 +  protected:
  1.1204 +
  1.1205 +    class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
  1.1206 +    public:
  1.1207 +
  1.1208 +      typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
  1.1209 +
  1.1210 +      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
  1.1211 +
  1.1212 +      virtual void add(const Node& node) {
  1.1213 +        Parent::add(node);
  1.1214 +        Parent::set(node, INVALID);
  1.1215 +      }
  1.1216 +
  1.1217 +      virtual void add(const std::vector<Node>& nodes) {
  1.1218 +        Parent::add(nodes);
  1.1219 +        for (int i = 0; i < int(nodes.size()); ++i) {
  1.1220 +          Parent::set(nodes[i], INVALID);
  1.1221 +        }
  1.1222 +      }
  1.1223 +
  1.1224 +      virtual void build() {
  1.1225 +        Parent::build();
  1.1226 +        Node it;
  1.1227 +        typename Parent::Notifier* nf = Parent::notifier();
  1.1228 +        for (nf->first(it); it != INVALID; nf->next(it)) {
  1.1229 +          Parent::set(it, INVALID);
  1.1230 +        }
  1.1231 +      }
  1.1232 +    };
  1.1233 +
  1.1234 +    const Digraph &_g;
  1.1235 +    AutoNodeMap _head;
  1.1236 +    typename Digraph::template ArcMap<Arc> _parent;
  1.1237 +    typename Digraph::template ArcMap<Arc> _left;
  1.1238 +    typename Digraph::template ArcMap<Arc> _right;
  1.1239 +
  1.1240 +    class ArcLess {
  1.1241 +      const Digraph &g;
  1.1242 +    public:
  1.1243 +      ArcLess(const Digraph &_g) : g(_g) {}
  1.1244 +      bool operator()(Arc a,Arc b) const
  1.1245 +      {
  1.1246 +        return g.target(a)<g.target(b);
  1.1247 +      }
  1.1248 +    };
  1.1249 +
  1.1250 +  public:
  1.1251 +
  1.1252 +    ///Constructor
  1.1253 +
  1.1254 +    ///Constructor.
  1.1255 +    ///
  1.1256 +    ///It builds up the search database.
  1.1257 +    DynArcLookUp(const Digraph &g)
  1.1258 +      : _g(g),_head(g),_parent(g),_left(g),_right(g)
  1.1259 +    {
  1.1260 +      Parent::attach(_g.notifier(typename Digraph::Arc()));
  1.1261 +      refresh();
  1.1262 +    }
  1.1263 +
  1.1264 +  protected:
  1.1265 +
  1.1266 +    virtual void add(const Arc& arc) {
  1.1267 +      insert(arc);
  1.1268 +    }
  1.1269 +
  1.1270 +    virtual void add(const std::vector<Arc>& arcs) {
  1.1271 +      for (int i = 0; i < int(arcs.size()); ++i) {
  1.1272 +        insert(arcs[i]);
  1.1273 +      }
  1.1274 +    }
  1.1275 +
  1.1276 +    virtual void erase(const Arc& arc) {
  1.1277 +      remove(arc);
  1.1278 +    }
  1.1279 +
  1.1280 +    virtual void erase(const std::vector<Arc>& arcs) {
  1.1281 +      for (int i = 0; i < int(arcs.size()); ++i) {
  1.1282 +        remove(arcs[i]);
  1.1283 +      }
  1.1284 +    }
  1.1285 +
  1.1286 +    virtual void build() {
  1.1287 +      refresh();
  1.1288 +    }
  1.1289 +
  1.1290 +    virtual void clear() {
  1.1291 +      for(NodeIt n(_g);n!=INVALID;++n) {
  1.1292 +        _head.set(n, INVALID);
  1.1293 +      }
  1.1294 +    }
  1.1295 +
  1.1296 +    void insert(Arc arc) {
  1.1297 +      Node s = _g.source(arc);
  1.1298 +      Node t = _g.target(arc);
  1.1299 +      _left.set(arc, INVALID);
  1.1300 +      _right.set(arc, INVALID);
  1.1301 +
  1.1302 +      Arc e = _head[s];
  1.1303 +      if (e == INVALID) {
  1.1304 +        _head.set(s, arc);
  1.1305 +        _parent.set(arc, INVALID);
  1.1306 +        return;
  1.1307 +      }
  1.1308 +      while (true) {
  1.1309 +        if (t < _g.target(e)) {
  1.1310 +          if (_left[e] == INVALID) {
  1.1311 +            _left.set(e, arc);
  1.1312 +            _parent.set(arc, e);
  1.1313 +            splay(arc);
  1.1314 +            return;
  1.1315 +          } else {
  1.1316 +            e = _left[e];
  1.1317 +          }
  1.1318 +        } else {
  1.1319 +          if (_right[e] == INVALID) {
  1.1320 +            _right.set(e, arc);
  1.1321 +            _parent.set(arc, e);
  1.1322 +            splay(arc);
  1.1323 +            return;
  1.1324 +          } else {
  1.1325 +            e = _right[e];
  1.1326 +          }
  1.1327 +        }
  1.1328 +      }
  1.1329 +    }
  1.1330 +
  1.1331 +    void remove(Arc arc) {
  1.1332 +      if (_left[arc] == INVALID) {
  1.1333 +        if (_right[arc] != INVALID) {
  1.1334 +          _parent.set(_right[arc], _parent[arc]);
  1.1335 +        }
  1.1336 +        if (_parent[arc] != INVALID) {
  1.1337 +          if (_left[_parent[arc]] == arc) {
  1.1338 +            _left.set(_parent[arc], _right[arc]);
  1.1339 +          } else {
  1.1340 +            _right.set(_parent[arc], _right[arc]);
  1.1341 +          }
  1.1342 +        } else {
  1.1343 +          _head.set(_g.source(arc), _right[arc]);
  1.1344 +        }
  1.1345 +      } else if (_right[arc] == INVALID) {
  1.1346 +        _parent.set(_left[arc], _parent[arc]);
  1.1347 +        if (_parent[arc] != INVALID) {
  1.1348 +          if (_left[_parent[arc]] == arc) {
  1.1349 +            _left.set(_parent[arc], _left[arc]);
  1.1350 +          } else {
  1.1351 +            _right.set(_parent[arc], _left[arc]);
  1.1352 +          }
  1.1353 +        } else {
  1.1354 +          _head.set(_g.source(arc), _left[arc]);
  1.1355 +        }
  1.1356 +      } else {
  1.1357 +        Arc e = _left[arc];
  1.1358 +        if (_right[e] != INVALID) {
  1.1359 +          e = _right[e];
  1.1360 +          while (_right[e] != INVALID) {
  1.1361 +            e = _right[e];
  1.1362 +          }
  1.1363 +          Arc s = _parent[e];
  1.1364 +          _right.set(_parent[e], _left[e]);
  1.1365 +          if (_left[e] != INVALID) {
  1.1366 +            _parent.set(_left[e], _parent[e]);
  1.1367 +          }
  1.1368 +
  1.1369 +          _left.set(e, _left[arc]);
  1.1370 +          _parent.set(_left[arc], e);
  1.1371 +          _right.set(e, _right[arc]);
  1.1372 +          _parent.set(_right[arc], e);
  1.1373 +
  1.1374 +          _parent.set(e, _parent[arc]);
  1.1375 +          if (_parent[arc] != INVALID) {
  1.1376 +            if (_left[_parent[arc]] == arc) {
  1.1377 +              _left.set(_parent[arc], e);
  1.1378 +            } else {
  1.1379 +              _right.set(_parent[arc], e);
  1.1380 +            }
  1.1381 +          }
  1.1382 +          splay(s);
  1.1383 +        } else {
  1.1384 +          _right.set(e, _right[arc]);
  1.1385 +          _parent.set(_right[arc], e);
  1.1386 +
  1.1387 +          if (_parent[arc] != INVALID) {
  1.1388 +            if (_left[_parent[arc]] == arc) {
  1.1389 +              _left.set(_parent[arc], e);
  1.1390 +            } else {
  1.1391 +              _right.set(_parent[arc], e);
  1.1392 +            }
  1.1393 +          } else {
  1.1394 +            _head.set(_g.source(arc), e);
  1.1395 +          }
  1.1396 +        }
  1.1397 +      }
  1.1398 +    }
  1.1399 +
  1.1400 +    Arc refreshRec(std::vector<Arc> &v,int a,int b)
  1.1401 +    {
  1.1402 +      int m=(a+b)/2;
  1.1403 +      Arc me=v[m];
  1.1404 +      if (a < m) {
  1.1405 +        Arc left = refreshRec(v,a,m-1);
  1.1406 +        _left.set(me, left);
  1.1407 +        _parent.set(left, me);
  1.1408 +      } else {
  1.1409 +        _left.set(me, INVALID);
  1.1410 +      }
  1.1411 +      if (m < b) {
  1.1412 +        Arc right = refreshRec(v,m+1,b);
  1.1413 +        _right.set(me, right);
  1.1414 +        _parent.set(right, me);
  1.1415 +      } else {
  1.1416 +        _right.set(me, INVALID);
  1.1417 +      }
  1.1418 +      return me;
  1.1419 +    }
  1.1420 +
  1.1421 +    void refresh() {
  1.1422 +      for(NodeIt n(_g);n!=INVALID;++n) {
  1.1423 +        std::vector<Arc> v;
  1.1424 +        for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  1.1425 +        if(v.size()) {
  1.1426 +          std::sort(v.begin(),v.end(),ArcLess(_g));
  1.1427 +          Arc head = refreshRec(v,0,v.size()-1);
  1.1428 +          _head.set(n, head);
  1.1429 +          _parent.set(head, INVALID);
  1.1430 +        }
  1.1431 +        else _head.set(n, INVALID);
  1.1432 +      }
  1.1433 +    }
  1.1434 +
  1.1435 +    void zig(Arc v) {
  1.1436 +      Arc w = _parent[v];
  1.1437 +      _parent.set(v, _parent[w]);
  1.1438 +      _parent.set(w, v);
  1.1439 +      _left.set(w, _right[v]);
  1.1440 +      _right.set(v, w);
  1.1441 +      if (_parent[v] != INVALID) {
  1.1442 +        if (_right[_parent[v]] == w) {
  1.1443 +          _right.set(_parent[v], v);
  1.1444 +        } else {
  1.1445 +          _left.set(_parent[v], v);
  1.1446 +        }
  1.1447 +      }
  1.1448 +      if (_left[w] != INVALID){
  1.1449 +        _parent.set(_left[w], w);
  1.1450 +      }
  1.1451 +    }
  1.1452 +
  1.1453 +    void zag(Arc v) {
  1.1454 +      Arc w = _parent[v];
  1.1455 +      _parent.set(v, _parent[w]);
  1.1456 +      _parent.set(w, v);
  1.1457 +      _right.set(w, _left[v]);
  1.1458 +      _left.set(v, w);
  1.1459 +      if (_parent[v] != INVALID){
  1.1460 +        if (_left[_parent[v]] == w) {
  1.1461 +          _left.set(_parent[v], v);
  1.1462 +        } else {
  1.1463 +          _right.set(_parent[v], v);
  1.1464 +        }
  1.1465 +      }
  1.1466 +      if (_right[w] != INVALID){
  1.1467 +        _parent.set(_right[w], w);
  1.1468 +      }
  1.1469 +    }
  1.1470 +
  1.1471 +    void splay(Arc v) {
  1.1472 +      while (_parent[v] != INVALID) {
  1.1473 +        if (v == _left[_parent[v]]) {
  1.1474 +          if (_parent[_parent[v]] == INVALID) {
  1.1475 +            zig(v);
  1.1476 +          } else {
  1.1477 +            if (_parent[v] == _left[_parent[_parent[v]]]) {
  1.1478 +              zig(_parent[v]);
  1.1479 +              zig(v);
  1.1480 +            } else {
  1.1481 +              zig(v);
  1.1482 +              zag(v);
  1.1483 +            }
  1.1484 +          }
  1.1485 +        } else {
  1.1486 +          if (_parent[_parent[v]] == INVALID) {
  1.1487 +            zag(v);
  1.1488 +          } else {
  1.1489 +            if (_parent[v] == _left[_parent[_parent[v]]]) {
  1.1490 +              zag(v);
  1.1491 +              zig(v);
  1.1492 +            } else {
  1.1493 +              zag(_parent[v]);
  1.1494 +              zag(v);
  1.1495 +            }
  1.1496 +          }
  1.1497 +        }
  1.1498 +      }
  1.1499 +      _head[_g.source(v)] = v;
  1.1500 +    }
  1.1501 +
  1.1502 +
  1.1503 +  public:
  1.1504 +
  1.1505 +    ///Find an arc between two nodes.
  1.1506 +
  1.1507 +    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
  1.1508 +    /// <em>d</em> is the number of outgoing arcs of \c s.
  1.1509 +    ///\param s The source node
  1.1510 +    ///\param t The target node
  1.1511 +    ///\return An arc from \c s to \c t if there exists,
  1.1512 +    ///\ref INVALID otherwise.
  1.1513 +    Arc operator()(Node s, Node t) const
  1.1514 +    {
  1.1515 +      Arc a = _head[s];
  1.1516 +      while (true) {
  1.1517 +        if (_g.target(a) == t) {
  1.1518 +          const_cast<DynArcLookUp&>(*this).splay(a);
  1.1519 +          return a;
  1.1520 +        } else if (t < _g.target(a)) {
  1.1521 +          if (_left[a] == INVALID) {
  1.1522 +            const_cast<DynArcLookUp&>(*this).splay(a);
  1.1523 +            return INVALID;
  1.1524 +          } else {
  1.1525 +            a = _left[a];
  1.1526 +          }
  1.1527 +        } else  {
  1.1528 +          if (_right[a] == INVALID) {
  1.1529 +            const_cast<DynArcLookUp&>(*this).splay(a);
  1.1530 +            return INVALID;
  1.1531 +          } else {
  1.1532 +            a = _right[a];
  1.1533 +          }
  1.1534 +        }
  1.1535 +      }
  1.1536 +    }
  1.1537 +
  1.1538 +    ///Find the first arc between two nodes.
  1.1539 +
  1.1540 +    ///Find the first arc between two nodes in time
  1.1541 +    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
  1.1542 +    /// outgoing arcs of \c s.
  1.1543 +    ///\param s The source node
  1.1544 +    ///\param t The target node
  1.1545 +    ///\return An arc from \c s to \c t if there exists, \ref INVALID
  1.1546 +    /// otherwise.
  1.1547 +    Arc findFirst(Node s, Node t) const
  1.1548 +    {
  1.1549 +      Arc a = _head[s];
  1.1550 +      Arc r = INVALID;
  1.1551 +      while (true) {
  1.1552 +        if (_g.target(a) < t) {
  1.1553 +          if (_right[a] == INVALID) {
  1.1554 +            const_cast<DynArcLookUp&>(*this).splay(a);
  1.1555 +            return r;
  1.1556 +          } else {
  1.1557 +            a = _right[a];
  1.1558 +          }
  1.1559 +        } else {
  1.1560 +          if (_g.target(a) == t) {
  1.1561 +            r = a;
  1.1562 +          }
  1.1563 +          if (_left[a] == INVALID) {
  1.1564 +            const_cast<DynArcLookUp&>(*this).splay(a);
  1.1565 +            return r;
  1.1566 +          } else {
  1.1567 +            a = _left[a];
  1.1568 +          }
  1.1569 +        }
  1.1570 +      }
  1.1571 +    }
  1.1572 +
  1.1573 +    ///Find the next arc between two nodes.
  1.1574 +
  1.1575 +    ///Find the next arc between two nodes in time
  1.1576 +    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
  1.1577 +    /// outgoing arcs of \c s.
  1.1578 +    ///\param s The source node
  1.1579 +    ///\param t The target node
  1.1580 +    ///\return An arc from \c s to \c t if there exists, \ref INVALID
  1.1581 +    /// otherwise.
  1.1582 +
  1.1583 +    ///\note If \c e is not the result of the previous \c findFirst()
  1.1584 +    ///operation then the amorized time bound can not be guaranteed.
  1.1585 +#ifdef DOXYGEN
  1.1586 +    Arc findNext(Node s, Node t, Arc a) const
  1.1587 +#else
  1.1588 +    Arc findNext(Node, Node t, Arc a) const
  1.1589 +#endif
  1.1590 +    {
  1.1591 +      if (_right[a] != INVALID) {
  1.1592 +        a = _right[a];
  1.1593 +        while (_left[a] != INVALID) {
  1.1594 +          a = _left[a];
  1.1595 +        }
  1.1596 +        const_cast<DynArcLookUp&>(*this).splay(a);
  1.1597 +      } else {
  1.1598 +        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
  1.1599 +          a = _parent[a];
  1.1600 +        }
  1.1601 +        if (_parent[a] == INVALID) {
  1.1602 +          return INVALID;
  1.1603 +        } else {
  1.1604 +          a = _parent[a];
  1.1605 +          const_cast<DynArcLookUp&>(*this).splay(a);
  1.1606 +        }
  1.1607 +      }
  1.1608 +      if (_g.target(a) == t) return a;
  1.1609 +      else return INVALID;
  1.1610 +    }
  1.1611 +
  1.1612 +  };
  1.1613 +
  1.1614 +  ///Fast arc look up between given endpoints.
  1.1615 +
  1.1616 +  ///Using this class, you can find an arc in a digraph from a given
  1.1617 +  ///source to a given target in time <em>O(log d)</em>,
  1.1618 +  ///where <em>d</em> is the out-degree of the source node.
  1.1619 +  ///
  1.1620 +  ///It is not possible to find \e all parallel arcs between two nodes.
  1.1621 +  ///Use \ref AllArcLookUp for this purpose.
  1.1622 +  ///
  1.1623 +  ///\warning This class is static, so you should refresh() (or at least
  1.1624 +  ///refresh(Node)) this data structure
  1.1625 +  ///whenever the digraph changes. This is a time consuming (superlinearly
  1.1626 +  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  1.1627 +  ///
  1.1628 +  ///\tparam G The type of the underlying digraph.
  1.1629 +  ///
  1.1630 +  ///\sa DynArcLookUp
  1.1631 +  ///\sa AllArcLookUp
  1.1632 +  template<class G>
  1.1633 +  class ArcLookUp
  1.1634 +  {
  1.1635 +  public:
  1.1636 +    TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1.1637 +    typedef G Digraph;
  1.1638 +
  1.1639 +  protected:
  1.1640 +    const Digraph &_g;
  1.1641 +    typename Digraph::template NodeMap<Arc> _head;
  1.1642 +    typename Digraph::template ArcMap<Arc> _left;
  1.1643 +    typename Digraph::template ArcMap<Arc> _right;
  1.1644 +
  1.1645 +    class ArcLess {
  1.1646 +      const Digraph &g;
  1.1647 +    public:
  1.1648 +      ArcLess(const Digraph &_g) : g(_g) {}
  1.1649 +      bool operator()(Arc a,Arc b) const
  1.1650 +      {
  1.1651 +        return g.target(a)<g.target(b);
  1.1652 +      }
  1.1653 +    };
  1.1654 +
  1.1655 +  public:
  1.1656 +
  1.1657 +    ///Constructor
  1.1658 +
  1.1659 +    ///Constructor.
  1.1660 +    ///
  1.1661 +    ///It builds up the search database, which remains valid until the digraph
  1.1662 +    ///changes.
  1.1663 +    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
  1.1664 +
  1.1665 +  private:
  1.1666 +    Arc refreshRec(std::vector<Arc> &v,int a,int b)
  1.1667 +    {
  1.1668 +      int m=(a+b)/2;
  1.1669 +      Arc me=v[m];
  1.1670 +      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
  1.1671 +      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
  1.1672 +      return me;
  1.1673 +    }
  1.1674 +  public:
  1.1675 +    ///Refresh the data structure at a node.
  1.1676 +
  1.1677 +    ///Build up the search database of node \c n.
  1.1678 +    ///
  1.1679 +    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
  1.1680 +    ///the number of the outgoing arcs of \c n.
  1.1681 +    void refresh(Node n)
  1.1682 +    {
  1.1683 +      std::vector<Arc> v;
  1.1684 +      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  1.1685 +      if(v.size()) {
  1.1686 +        std::sort(v.begin(),v.end(),ArcLess(_g));
  1.1687 +        _head[n]=refreshRec(v,0,v.size()-1);
  1.1688 +      }
  1.1689 +      else _head[n]=INVALID;
  1.1690 +    }
  1.1691 +    ///Refresh the full data structure.
  1.1692 +
  1.1693 +    ///Build up the full search database. In fact, it simply calls
  1.1694 +    ///\ref refresh(Node) "refresh(n)" for each node \c n.
  1.1695 +    ///
  1.1696 +    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
  1.1697 +    ///the number of the arcs of \c n and <em>D</em> is the maximum
  1.1698 +    ///out-degree of the digraph.
  1.1699 +
  1.1700 +    void refresh()
  1.1701 +    {
  1.1702 +      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
  1.1703 +    }
  1.1704 +
  1.1705 +    ///Find an arc between two nodes.
  1.1706 +
  1.1707 +    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
  1.1708 +    /// <em>d</em> is the number of outgoing arcs of \c s.
  1.1709 +    ///\param s The source node
  1.1710 +    ///\param t The target node
  1.1711 +    ///\return An arc from \c s to \c t if there exists,
  1.1712 +    ///\ref INVALID otherwise.
  1.1713 +    ///
  1.1714 +    ///\warning If you change the digraph, refresh() must be called before using
  1.1715 +    ///this operator. If you change the outgoing arcs of
  1.1716 +    ///a single node \c n, then
  1.1717 +    ///\ref refresh(Node) "refresh(n)" is enough.
  1.1718 +    ///
  1.1719 +    Arc operator()(Node s, Node t) const
  1.1720 +    {
  1.1721 +      Arc e;
  1.1722 +      for(e=_head[s];
  1.1723 +          e!=INVALID&&_g.target(e)!=t;
  1.1724 +          e = t < _g.target(e)?_left[e]:_right[e]) ;
  1.1725 +      return e;
  1.1726 +    }
  1.1727 +
  1.1728 +  };
  1.1729 +
  1.1730 +  ///Fast look up of all arcs between given endpoints.
  1.1731 +
  1.1732 +  ///This class is the same as \ref ArcLookUp, with the addition
  1.1733 +  ///that it makes it possible to find all arcs between given endpoints.
  1.1734 +  ///
  1.1735 +  ///\warning This class is static, so you should refresh() (or at least
  1.1736 +  ///refresh(Node)) this data structure
  1.1737 +  ///whenever the digraph changes. This is a time consuming (superlinearly
  1.1738 +  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  1.1739 +  ///
  1.1740 +  ///\tparam G The type of the underlying digraph.
  1.1741 +  ///
  1.1742 +  ///\sa DynArcLookUp
  1.1743 +  ///\sa ArcLookUp
  1.1744 +  template<class G>
  1.1745 +  class AllArcLookUp : public ArcLookUp<G>
  1.1746 +  {
  1.1747 +    using ArcLookUp<G>::_g;
  1.1748 +    using ArcLookUp<G>::_right;
  1.1749 +    using ArcLookUp<G>::_left;
  1.1750 +    using ArcLookUp<G>::_head;
  1.1751 +
  1.1752 +    TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1.1753 +    typedef G Digraph;
  1.1754 +
  1.1755 +    typename Digraph::template ArcMap<Arc> _next;
  1.1756 +
  1.1757 +    Arc refreshNext(Arc head,Arc next=INVALID)
  1.1758 +    {
  1.1759 +      if(head==INVALID) return next;
  1.1760 +      else {
  1.1761 +        next=refreshNext(_right[head],next);
  1.1762 +//         _next[head]=next;
  1.1763 +        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
  1.1764 +          ? next : INVALID;
  1.1765 +        return refreshNext(_left[head],head);
  1.1766 +      }
  1.1767 +    }
  1.1768 +
  1.1769 +    void refreshNext()
  1.1770 +    {
  1.1771 +      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
  1.1772 +    }
  1.1773 +
  1.1774 +  public:
  1.1775 +    ///Constructor
  1.1776 +
  1.1777 +    ///Constructor.
  1.1778 +    ///
  1.1779 +    ///It builds up the search database, which remains valid until the digraph
  1.1780 +    ///changes.
  1.1781 +    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
  1.1782 +
  1.1783 +    ///Refresh the data structure at a node.
  1.1784 +
  1.1785 +    ///Build up the search database of node \c n.
  1.1786 +    ///
  1.1787 +    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
  1.1788 +    ///the number of the outgoing arcs of \c n.
  1.1789 +
  1.1790 +    void refresh(Node n)
  1.1791 +    {
  1.1792 +      ArcLookUp<G>::refresh(n);
  1.1793 +      refreshNext(_head[n]);
  1.1794 +    }
  1.1795 +
  1.1796 +    ///Refresh the full data structure.
  1.1797 +
  1.1798 +    ///Build up the full search database. In fact, it simply calls
  1.1799 +    ///\ref refresh(Node) "refresh(n)" for each node \c n.
  1.1800 +    ///
  1.1801 +    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
  1.1802 +    ///the number of the arcs of \c n and <em>D</em> is the maximum
  1.1803 +    ///out-degree of the digraph.
  1.1804 +
  1.1805 +    void refresh()
  1.1806 +    {
  1.1807 +      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
  1.1808 +    }
  1.1809 +
  1.1810 +    ///Find an arc between two nodes.
  1.1811 +
  1.1812 +    ///Find an arc between two nodes.
  1.1813 +    ///\param s The source node
  1.1814 +    ///\param t The target node
  1.1815 +    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
  1.1816 +    ///not given, the operator finds the first appropriate arc.
  1.1817 +    ///\return An arc from \c s to \c t after \c prev or
  1.1818 +    ///\ref INVALID if there is no more.
  1.1819 +    ///
  1.1820 +    ///For example, you can count the number of arcs from \c u to \c v in the
  1.1821 +    ///following way.
  1.1822 +    ///\code
  1.1823 +    ///AllArcLookUp<ListDigraph> ae(g);
  1.1824 +    ///...
  1.1825 +    ///int n=0;
  1.1826 +    ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
  1.1827 +    ///\endcode
  1.1828 +    ///
  1.1829 +    ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
  1.1830 +    /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
  1.1831 +    ///consecutive arcs are found in constant time.
  1.1832 +    ///
  1.1833 +    ///\warning If you change the digraph, refresh() must be called before using
  1.1834 +    ///this operator. If you change the outgoing arcs of
  1.1835 +    ///a single node \c n, then
  1.1836 +    ///\ref refresh(Node) "refresh(n)" is enough.
  1.1837 +    ///
  1.1838 +#ifdef DOXYGEN
  1.1839 +    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
  1.1840 +#else
  1.1841 +    using ArcLookUp<G>::operator() ;
  1.1842 +    Arc operator()(Node s, Node t, Arc prev) const
  1.1843 +    {
  1.1844 +      return prev==INVALID?(*this)(s,t):_next[prev];
  1.1845 +    }
  1.1846 +#endif
  1.1847 +
  1.1848 +  };
  1.1849 +
  1.1850 +  /// @}
  1.1851 +
  1.1852 +} //namespace lemon
  1.1853 +
  1.1854 +#endif