lemon/core.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 01 Apr 2015 18:13:30 +0200
changeset 1325 1d80ec7d17eb
parent 1270 dceba191c00d
child 1327 18c89646185e
permissions -rw-r--r--
Remove GCC_VERSION define (#536)

This fix is due to marciso.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_CORE_H
    20 #define LEMON_CORE_H
    21 
    22 #include <vector>
    23 #include <algorithm>
    24 
    25 #include <lemon/config.h>
    26 #include <lemon/bits/enable_if.h>
    27 #include <lemon/bits/traits.h>
    28 #include <lemon/assert.h>
    29 
    30 // Disable the following warnings when compiling with MSVC:
    31 // C4250: 'class1' : inherits 'class2::member' via dominance
    32 // C4355: 'this' : used in base member initializer list
    33 // C4503: 'function' : decorated name length exceeded, name was truncated
    34 // C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
    35 // C4996: 'function': was declared deprecated
    36 #ifdef _MSC_VER
    37 #pragma warning( disable : 4250 4355 4503 4800 4996 )
    38 #endif
    39 
    40 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)
    41 // Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
    42 #pragma GCC diagnostic ignored "-Wunused-local-typedefs"
    43 #endif
    44 
    45 ///\file
    46 ///\brief LEMON core utilities.
    47 ///
    48 ///This header file contains core utilities for LEMON.
    49 ///It is automatically included by all graph types, therefore it usually
    50 ///do not have to be included directly.
    51 
    52 namespace lemon {
    53 
    54   /// \brief Dummy type to make it easier to create invalid iterators.
    55   ///
    56   /// Dummy type to make it easier to create invalid iterators.
    57   /// See \ref INVALID for the usage.
    58   struct Invalid {
    59   public:
    60     bool operator==(Invalid) { return true;  }
    61     bool operator!=(Invalid) { return false; }
    62     bool operator< (Invalid) { return false; }
    63   };
    64 
    65   /// \brief Invalid iterators.
    66   ///
    67   /// \ref Invalid is a global type that converts to each iterator
    68   /// in such a way that the value of the target iterator will be invalid.
    69 #ifdef LEMON_ONLY_TEMPLATES
    70   const Invalid INVALID = Invalid();
    71 #else
    72   extern const Invalid INVALID;
    73 #endif
    74 
    75   /// \addtogroup gutils
    76   /// @{
    77 
    78   ///Create convenience typedefs for the digraph types and iterators
    79 
    80   ///This \c \#define creates convenient type definitions for the following
    81   ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    82   ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
    83   ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
    84   ///
    85   ///\note If the graph type is a dependent type, ie. the graph type depend
    86   ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
    87   ///macro.
    88 #define DIGRAPH_TYPEDEFS(Digraph)                                       \
    89   typedef Digraph::Node Node;                                           \
    90   typedef Digraph::NodeIt NodeIt;                                       \
    91   typedef Digraph::Arc Arc;                                             \
    92   typedef Digraph::ArcIt ArcIt;                                         \
    93   typedef Digraph::InArcIt InArcIt;                                     \
    94   typedef Digraph::OutArcIt OutArcIt;                                   \
    95   typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
    96   typedef Digraph::NodeMap<int> IntNodeMap;                             \
    97   typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
    98   typedef Digraph::ArcMap<bool> BoolArcMap;                             \
    99   typedef Digraph::ArcMap<int> IntArcMap;                               \
   100   typedef Digraph::ArcMap<double> DoubleArcMap
   101 
   102   ///Create convenience typedefs for the digraph types and iterators
   103 
   104   ///\see DIGRAPH_TYPEDEFS
   105   ///
   106   ///\note Use this macro, if the graph type is a dependent type,
   107   ///ie. the graph type depend on a template parameter.
   108 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
   109   typedef typename Digraph::Node Node;                                  \
   110   typedef typename Digraph::NodeIt NodeIt;                              \
   111   typedef typename Digraph::Arc Arc;                                    \
   112   typedef typename Digraph::ArcIt ArcIt;                                \
   113   typedef typename Digraph::InArcIt InArcIt;                            \
   114   typedef typename Digraph::OutArcIt OutArcIt;                          \
   115   typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
   116   typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
   117   typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
   118   typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
   119   typedef typename Digraph::template ArcMap<int> IntArcMap;             \
   120   typedef typename Digraph::template ArcMap<double> DoubleArcMap
   121 
   122   ///Create convenience typedefs for the graph types and iterators
   123 
   124   ///This \c \#define creates the same convenient type definitions as defined
   125   ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
   126   ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
   127   ///\c DoubleEdgeMap.
   128   ///
   129   ///\note If the graph type is a dependent type, ie. the graph type depend
   130   ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
   131   ///macro.
   132 #define GRAPH_TYPEDEFS(Graph)                                           \
   133   DIGRAPH_TYPEDEFS(Graph);                                              \
   134   typedef Graph::Edge Edge;                                             \
   135   typedef Graph::EdgeIt EdgeIt;                                         \
   136   typedef Graph::IncEdgeIt IncEdgeIt;                                   \
   137   typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
   138   typedef Graph::EdgeMap<int> IntEdgeMap;                               \
   139   typedef Graph::EdgeMap<double> DoubleEdgeMap
   140 
   141   ///Create convenience typedefs for the graph types and iterators
   142 
   143   ///\see GRAPH_TYPEDEFS
   144   ///
   145   ///\note Use this macro, if the graph type is a dependent type,
   146   ///ie. the graph type depend on a template parameter.
   147 #define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
   148   TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
   149   typedef typename Graph::Edge Edge;                                    \
   150   typedef typename Graph::EdgeIt EdgeIt;                                \
   151   typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
   152   typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
   153   typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
   154   typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
   155 
   156   ///Create convenience typedefs for the bipartite graph types and iterators
   157 
   158   ///This \c \#define creates the same convenient type definitions as
   159   ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
   160   ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
   161   ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
   162   ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
   163   ///
   164   ///\note If the graph type is a dependent type, ie. the graph type depend
   165   ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
   166   ///macro.
   167 #define BPGRAPH_TYPEDEFS(BpGraph)                                       \
   168   GRAPH_TYPEDEFS(BpGraph);                                              \
   169   typedef BpGraph::RedNode RedNode;                                     \
   170   typedef BpGraph::RedNodeIt RedNodeIt;                                 \
   171   typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
   172   typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
   173   typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
   174   typedef BpGraph::BlueNode BlueNode;                                   \
   175   typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
   176   typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
   177   typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
   178   typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
   179 
   180   ///Create convenience typedefs for the bipartite graph types and iterators
   181 
   182   ///\see BPGRAPH_TYPEDEFS
   183   ///
   184   ///\note Use this macro, if the graph type is a dependent type,
   185   ///ie. the graph type depend on a template parameter.
   186 #define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                                  \
   187   TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                         \
   188   typedef typename BpGraph::RedNode RedNode;                                \
   189   typedef typename BpGraph::RedNodeIt RedNodeIt;                            \
   190   typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap;       \
   191   typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap;         \
   192   typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap;   \
   193   typedef typename BpGraph::BlueNode BlueNode;                              \
   194   typedef typename BpGraph::BlueNodeIt BlueNodeIt;                          \
   195   typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap;     \
   196   typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap;       \
   197   typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
   198 
   199   /// \brief Function to count the items in a graph.
   200   ///
   201   /// This function counts the items (nodes, arcs etc.) in a graph.
   202   /// The complexity of the function is linear because
   203   /// it iterates on all of the items.
   204   template <typename Graph, typename Item>
   205   inline int countItems(const Graph& g) {
   206     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
   207     int num = 0;
   208     for (ItemIt it(g); it != INVALID; ++it) {
   209       ++num;
   210     }
   211     return num;
   212   }
   213 
   214   // Node counting:
   215 
   216   namespace _core_bits {
   217 
   218     template <typename Graph, typename Enable = void>
   219     struct CountNodesSelector {
   220       static int count(const Graph &g) {
   221         return countItems<Graph, typename Graph::Node>(g);
   222       }
   223     };
   224 
   225     template <typename Graph>
   226     struct CountNodesSelector<
   227       Graph, typename
   228       enable_if<typename Graph::NodeNumTag, void>::type>
   229     {
   230       static int count(const Graph &g) {
   231         return g.nodeNum();
   232       }
   233     };
   234   }
   235 
   236   /// \brief Function to count the nodes in the graph.
   237   ///
   238   /// This function counts the nodes in the graph.
   239   /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
   240   /// graph structures it is specialized to run in <em>O</em>(1).
   241   ///
   242   /// \note If the graph contains a \c nodeNum() member function and a
   243   /// \c NodeNumTag tag then this function calls directly the member
   244   /// function to query the cardinality of the node set.
   245   template <typename Graph>
   246   inline int countNodes(const Graph& g) {
   247     return _core_bits::CountNodesSelector<Graph>::count(g);
   248   }
   249 
   250   namespace _graph_utils_bits {
   251 
   252     template <typename Graph, typename Enable = void>
   253     struct CountRedNodesSelector {
   254       static int count(const Graph &g) {
   255         return countItems<Graph, typename Graph::RedNode>(g);
   256       }
   257     };
   258 
   259     template <typename Graph>
   260     struct CountRedNodesSelector<
   261       Graph, typename
   262       enable_if<typename Graph::NodeNumTag, void>::type>
   263     {
   264       static int count(const Graph &g) {
   265         return g.redNum();
   266       }
   267     };
   268   }
   269 
   270   /// \brief Function to count the red nodes in the graph.
   271   ///
   272   /// This function counts the red nodes in the graph.
   273   /// The complexity of the function is O(n) but for some
   274   /// graph structures it is specialized to run in O(1).
   275   ///
   276   /// If the graph contains a \e redNum() member function and a
   277   /// \e NodeNumTag tag then this function calls directly the member
   278   /// function to query the cardinality of the node set.
   279   template <typename Graph>
   280   inline int countRedNodes(const Graph& g) {
   281     return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
   282   }
   283 
   284   namespace _graph_utils_bits {
   285 
   286     template <typename Graph, typename Enable = void>
   287     struct CountBlueNodesSelector {
   288       static int count(const Graph &g) {
   289         return countItems<Graph, typename Graph::BlueNode>(g);
   290       }
   291     };
   292 
   293     template <typename Graph>
   294     struct CountBlueNodesSelector<
   295       Graph, typename
   296       enable_if<typename Graph::NodeNumTag, void>::type>
   297     {
   298       static int count(const Graph &g) {
   299         return g.blueNum();
   300       }
   301     };
   302   }
   303 
   304   /// \brief Function to count the blue nodes in the graph.
   305   ///
   306   /// This function counts the blue nodes in the graph.
   307   /// The complexity of the function is O(n) but for some
   308   /// graph structures it is specialized to run in O(1).
   309   ///
   310   /// If the graph contains a \e blueNum() member function and a
   311   /// \e NodeNumTag tag then this function calls directly the member
   312   /// function to query the cardinality of the node set.
   313   template <typename Graph>
   314   inline int countBlueNodes(const Graph& g) {
   315     return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
   316   }
   317 
   318   // Arc counting:
   319 
   320   namespace _core_bits {
   321 
   322     template <typename Graph, typename Enable = void>
   323     struct CountArcsSelector {
   324       static int count(const Graph &g) {
   325         return countItems<Graph, typename Graph::Arc>(g);
   326       }
   327     };
   328 
   329     template <typename Graph>
   330     struct CountArcsSelector<
   331       Graph,
   332       typename enable_if<typename Graph::ArcNumTag, void>::type>
   333     {
   334       static int count(const Graph &g) {
   335         return g.arcNum();
   336       }
   337     };
   338   }
   339 
   340   /// \brief Function to count the arcs in the graph.
   341   ///
   342   /// This function counts the arcs in the graph.
   343   /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
   344   /// graph structures it is specialized to run in <em>O</em>(1).
   345   ///
   346   /// \note If the graph contains a \c arcNum() member function and a
   347   /// \c ArcNumTag tag then this function calls directly the member
   348   /// function to query the cardinality of the arc set.
   349   template <typename Graph>
   350   inline int countArcs(const Graph& g) {
   351     return _core_bits::CountArcsSelector<Graph>::count(g);
   352   }
   353 
   354   // Edge counting:
   355 
   356   namespace _core_bits {
   357 
   358     template <typename Graph, typename Enable = void>
   359     struct CountEdgesSelector {
   360       static int count(const Graph &g) {
   361         return countItems<Graph, typename Graph::Edge>(g);
   362       }
   363     };
   364 
   365     template <typename Graph>
   366     struct CountEdgesSelector<
   367       Graph,
   368       typename enable_if<typename Graph::EdgeNumTag, void>::type>
   369     {
   370       static int count(const Graph &g) {
   371         return g.edgeNum();
   372       }
   373     };
   374   }
   375 
   376   /// \brief Function to count the edges in the graph.
   377   ///
   378   /// This function counts the edges in the graph.
   379   /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
   380   /// graph structures it is specialized to run in <em>O</em>(1).
   381   ///
   382   /// \note If the graph contains a \c edgeNum() member function and a
   383   /// \c EdgeNumTag tag then this function calls directly the member
   384   /// function to query the cardinality of the edge set.
   385   template <typename Graph>
   386   inline int countEdges(const Graph& g) {
   387     return _core_bits::CountEdgesSelector<Graph>::count(g);
   388 
   389   }
   390 
   391 
   392   template <typename Graph, typename DegIt>
   393   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   394     int num = 0;
   395     for (DegIt it(_g, _n); it != INVALID; ++it) {
   396       ++num;
   397     }
   398     return num;
   399   }
   400 
   401   /// \brief Function to count the number of the out-arcs from node \c n.
   402   ///
   403   /// This function counts the number of the out-arcs from node \c n
   404   /// in the graph \c g.
   405   template <typename Graph>
   406   inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) {
   407     return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
   408   }
   409 
   410   /// \brief Function to count the number of the in-arcs to node \c n.
   411   ///
   412   /// This function counts the number of the in-arcs to node \c n
   413   /// in the graph \c g.
   414   template <typename Graph>
   415   inline int countInArcs(const Graph& g,  const typename Graph::Node& n) {
   416     return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
   417   }
   418 
   419   /// \brief Function to count the number of the inc-edges to node \c n.
   420   ///
   421   /// This function counts the number of the inc-edges to node \c n
   422   /// in the undirected graph \c g.
   423   template <typename Graph>
   424   inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) {
   425     return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
   426   }
   427 
   428   namespace _core_bits {
   429 
   430     template <typename Digraph, typename Item, typename RefMap>
   431     class MapCopyBase {
   432     public:
   433       virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
   434 
   435       virtual ~MapCopyBase() {}
   436     };
   437 
   438     template <typename Digraph, typename Item, typename RefMap,
   439               typename FromMap, typename ToMap>
   440     class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
   441     public:
   442 
   443       MapCopy(const FromMap& map, ToMap& tmap)
   444         : _map(map), _tmap(tmap) {}
   445 
   446       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   447         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   448         for (ItemIt it(digraph); it != INVALID; ++it) {
   449           _tmap.set(refMap[it], _map[it]);
   450         }
   451       }
   452 
   453     private:
   454       const FromMap& _map;
   455       ToMap& _tmap;
   456     };
   457 
   458     template <typename Digraph, typename Item, typename RefMap, typename It>
   459     class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
   460     public:
   461 
   462       ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
   463 
   464       virtual void copy(const Digraph&, const RefMap& refMap) {
   465         _it = refMap[_item];
   466       }
   467 
   468     private:
   469       Item _item;
   470       It& _it;
   471     };
   472 
   473     template <typename Digraph, typename Item, typename RefMap, typename Ref>
   474     class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   475     public:
   476 
   477       RefCopy(Ref& map) : _map(map) {}
   478 
   479       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   480         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   481         for (ItemIt it(digraph); it != INVALID; ++it) {
   482           _map.set(it, refMap[it]);
   483         }
   484       }
   485 
   486     private:
   487       Ref& _map;
   488     };
   489 
   490     template <typename Digraph, typename Item, typename RefMap,
   491               typename CrossRef>
   492     class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   493     public:
   494 
   495       CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
   496 
   497       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   498         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   499         for (ItemIt it(digraph); it != INVALID; ++it) {
   500           _cmap.set(refMap[it], it);
   501         }
   502       }
   503 
   504     private:
   505       CrossRef& _cmap;
   506     };
   507 
   508     template <typename Digraph, typename Enable = void>
   509     struct DigraphCopySelector {
   510       template <typename From, typename NodeRefMap, typename ArcRefMap>
   511       static void copy(const From& from, Digraph &to,
   512                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   513         to.clear();
   514         for (typename From::NodeIt it(from); it != INVALID; ++it) {
   515           nodeRefMap[it] = to.addNode();
   516         }
   517         for (typename From::ArcIt it(from); it != INVALID; ++it) {
   518           arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
   519                                     nodeRefMap[from.target(it)]);
   520         }
   521       }
   522     };
   523 
   524     template <typename Digraph>
   525     struct DigraphCopySelector<
   526       Digraph,
   527       typename enable_if<typename Digraph::BuildTag, void>::type>
   528     {
   529       template <typename From, typename NodeRefMap, typename ArcRefMap>
   530       static void copy(const From& from, Digraph &to,
   531                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   532         to.build(from, nodeRefMap, arcRefMap);
   533       }
   534     };
   535 
   536     template <typename Graph, typename Enable = void>
   537     struct GraphCopySelector {
   538       template <typename From, typename NodeRefMap, typename EdgeRefMap>
   539       static void copy(const From& from, Graph &to,
   540                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   541         to.clear();
   542         for (typename From::NodeIt it(from); it != INVALID; ++it) {
   543           nodeRefMap[it] = to.addNode();
   544         }
   545         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
   546           edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
   547                                       nodeRefMap[from.v(it)]);
   548         }
   549       }
   550     };
   551 
   552     template <typename Graph>
   553     struct GraphCopySelector<
   554       Graph,
   555       typename enable_if<typename Graph::BuildTag, void>::type>
   556     {
   557       template <typename From, typename NodeRefMap, typename EdgeRefMap>
   558       static void copy(const From& from, Graph &to,
   559                        NodeRefMap& nodeRefMap,
   560                        EdgeRefMap& edgeRefMap) {
   561         to.build(from, nodeRefMap, edgeRefMap);
   562       }
   563     };
   564 
   565     template <typename BpGraph, typename Enable = void>
   566     struct BpGraphCopySelector {
   567       template <typename From, typename RedNodeRefMap,
   568                 typename BlueNodeRefMap, typename EdgeRefMap>
   569       static void copy(const From& from, BpGraph &to,
   570                        RedNodeRefMap& redNodeRefMap,
   571                        BlueNodeRefMap& blueNodeRefMap,
   572                        EdgeRefMap& edgeRefMap) {
   573         to.clear();
   574         for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
   575           redNodeRefMap[it] = to.addRedNode();
   576         }
   577         for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
   578           blueNodeRefMap[it] = to.addBlueNode();
   579         }
   580         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
   581           edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
   582                                       blueNodeRefMap[from.blueNode(it)]);
   583         }
   584       }
   585     };
   586 
   587     template <typename BpGraph>
   588     struct BpGraphCopySelector<
   589       BpGraph,
   590       typename enable_if<typename BpGraph::BuildTag, void>::type>
   591     {
   592       template <typename From, typename RedNodeRefMap,
   593                 typename BlueNodeRefMap, typename EdgeRefMap>
   594       static void copy(const From& from, BpGraph &to,
   595                        RedNodeRefMap& redNodeRefMap,
   596                        BlueNodeRefMap& blueNodeRefMap,
   597                        EdgeRefMap& edgeRefMap) {
   598         to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
   599       }
   600     };
   601 
   602   }
   603 
   604   /// \brief Check whether a graph is undirected.
   605   ///
   606   /// This function returns \c true if the given graph is undirected.
   607 #ifdef DOXYGEN
   608   template <typename GR>
   609   bool undirected(const GR& g) { return false; }
   610 #else
   611   template <typename GR>
   612   typename enable_if<UndirectedTagIndicator<GR>, bool>::type
   613   undirected(const GR&) {
   614     return true;
   615   }
   616   template <typename GR>
   617   typename disable_if<UndirectedTagIndicator<GR>, bool>::type
   618   undirected(const GR&) {
   619     return false;
   620   }
   621 #endif
   622 
   623   /// \brief Class to copy a digraph.
   624   ///
   625   /// Class to copy a digraph to another digraph (duplicate a digraph). The
   626   /// simplest way of using it is through the \c digraphCopy() function.
   627   ///
   628   /// This class not only make a copy of a digraph, but it can create
   629   /// references and cross references between the nodes and arcs of
   630   /// the two digraphs, and it can copy maps to use with the newly created
   631   /// digraph.
   632   ///
   633   /// To make a copy from a digraph, first an instance of DigraphCopy
   634   /// should be created, then the data belongs to the digraph should
   635   /// assigned to copy. In the end, the \c run() member should be
   636   /// called.
   637   ///
   638   /// The next code copies a digraph with several data:
   639   ///\code
   640   ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
   641   ///  // Create references for the nodes
   642   ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   643   ///  cg.nodeRef(nr);
   644   ///  // Create cross references (inverse) for the arcs
   645   ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
   646   ///  cg.arcCrossRef(acr);
   647   ///  // Copy an arc map
   648   ///  OrigGraph::ArcMap<double> oamap(orig_graph);
   649   ///  NewGraph::ArcMap<double> namap(new_graph);
   650   ///  cg.arcMap(oamap, namap);
   651   ///  // Copy a node
   652   ///  OrigGraph::Node on;
   653   ///  NewGraph::Node nn;
   654   ///  cg.node(on, nn);
   655   ///  // Execute copying
   656   ///  cg.run();
   657   ///\endcode
   658   template <typename From, typename To>
   659   class DigraphCopy {
   660   private:
   661 
   662     typedef typename From::Node Node;
   663     typedef typename From::NodeIt NodeIt;
   664     typedef typename From::Arc Arc;
   665     typedef typename From::ArcIt ArcIt;
   666 
   667     typedef typename To::Node TNode;
   668     typedef typename To::Arc TArc;
   669 
   670     typedef typename From::template NodeMap<TNode> NodeRefMap;
   671     typedef typename From::template ArcMap<TArc> ArcRefMap;
   672 
   673   public:
   674 
   675     /// \brief Constructor of DigraphCopy.
   676     ///
   677     /// Constructor of DigraphCopy for copying the content of the
   678     /// \c from digraph into the \c to digraph.
   679     DigraphCopy(const From& from, To& to)
   680       : _from(from), _to(to) {}
   681 
   682     /// \brief Destructor of DigraphCopy
   683     ///
   684     /// Destructor of DigraphCopy.
   685     ~DigraphCopy() {
   686       for (int i = 0; i < int(_node_maps.size()); ++i) {
   687         delete _node_maps[i];
   688       }
   689       for (int i = 0; i < int(_arc_maps.size()); ++i) {
   690         delete _arc_maps[i];
   691       }
   692 
   693     }
   694 
   695     /// \brief Copy the node references into the given map.
   696     ///
   697     /// This function copies the node references into the given map.
   698     /// The parameter should be a map, whose key type is the Node type of
   699     /// the source digraph, while the value type is the Node type of the
   700     /// destination digraph.
   701     template <typename NodeRef>
   702     DigraphCopy& nodeRef(NodeRef& map) {
   703       _node_maps.push_back(new _core_bits::RefCopy<From, Node,
   704                            NodeRefMap, NodeRef>(map));
   705       return *this;
   706     }
   707 
   708     /// \brief Copy the node cross references into the given map.
   709     ///
   710     /// This function copies the node cross references (reverse references)
   711     /// into the given map. The parameter should be a map, whose key type
   712     /// is the Node type of the destination digraph, while the value type is
   713     /// the Node type of the source digraph.
   714     template <typename NodeCrossRef>
   715     DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
   716       _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
   717                            NodeRefMap, NodeCrossRef>(map));
   718       return *this;
   719     }
   720 
   721     /// \brief Make a copy of the given node map.
   722     ///
   723     /// This function makes a copy of the given node map for the newly
   724     /// created digraph.
   725     /// The key type of the new map \c tmap should be the Node type of the
   726     /// destination digraph, and the key type of the original map \c map
   727     /// should be the Node type of the source digraph.
   728     template <typename FromMap, typename ToMap>
   729     DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
   730       _node_maps.push_back(new _core_bits::MapCopy<From, Node,
   731                            NodeRefMap, FromMap, ToMap>(map, tmap));
   732       return *this;
   733     }
   734 
   735     /// \brief Make a copy of the given node.
   736     ///
   737     /// This function makes a copy of the given node.
   738     DigraphCopy& node(const Node& node, TNode& tnode) {
   739       _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
   740                            NodeRefMap, TNode>(node, tnode));
   741       return *this;
   742     }
   743 
   744     /// \brief Copy the arc references into the given map.
   745     ///
   746     /// This function copies the arc references into the given map.
   747     /// The parameter should be a map, whose key type is the Arc type of
   748     /// the source digraph, while the value type is the Arc type of the
   749     /// destination digraph.
   750     template <typename ArcRef>
   751     DigraphCopy& arcRef(ArcRef& map) {
   752       _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
   753                           ArcRefMap, ArcRef>(map));
   754       return *this;
   755     }
   756 
   757     /// \brief Copy the arc cross references into the given map.
   758     ///
   759     /// This function copies the arc cross references (reverse references)
   760     /// into the given map. The parameter should be a map, whose key type
   761     /// is the Arc type of the destination digraph, while the value type is
   762     /// the Arc type of the source digraph.
   763     template <typename ArcCrossRef>
   764     DigraphCopy& arcCrossRef(ArcCrossRef& map) {
   765       _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
   766                           ArcRefMap, ArcCrossRef>(map));
   767       return *this;
   768     }
   769 
   770     /// \brief Make a copy of the given arc map.
   771     ///
   772     /// This function makes a copy of the given arc map for the newly
   773     /// created digraph.
   774     /// The key type of the new map \c tmap should be the Arc type of the
   775     /// destination digraph, and the key type of the original map \c map
   776     /// should be the Arc type of the source digraph.
   777     template <typename FromMap, typename ToMap>
   778     DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
   779       _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
   780                           ArcRefMap, FromMap, ToMap>(map, tmap));
   781       return *this;
   782     }
   783 
   784     /// \brief Make a copy of the given arc.
   785     ///
   786     /// This function makes a copy of the given arc.
   787     DigraphCopy& arc(const Arc& arc, TArc& tarc) {
   788       _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
   789                           ArcRefMap, TArc>(arc, tarc));
   790       return *this;
   791     }
   792 
   793     /// \brief Execute copying.
   794     ///
   795     /// This function executes the copying of the digraph along with the
   796     /// copying of the assigned data.
   797     void run() {
   798       NodeRefMap nodeRefMap(_from);
   799       ArcRefMap arcRefMap(_from);
   800       _core_bits::DigraphCopySelector<To>::
   801         copy(_from, _to, nodeRefMap, arcRefMap);
   802       for (int i = 0; i < int(_node_maps.size()); ++i) {
   803         _node_maps[i]->copy(_from, nodeRefMap);
   804       }
   805       for (int i = 0; i < int(_arc_maps.size()); ++i) {
   806         _arc_maps[i]->copy(_from, arcRefMap);
   807       }
   808     }
   809 
   810   protected:
   811 
   812     const From& _from;
   813     To& _to;
   814 
   815     std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
   816       _node_maps;
   817 
   818     std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
   819       _arc_maps;
   820 
   821   };
   822 
   823   /// \brief Copy a digraph to another digraph.
   824   ///
   825   /// This function copies a digraph to another digraph.
   826   /// The complete usage of it is detailed in the DigraphCopy class, but
   827   /// a short example shows a basic work:
   828   ///\code
   829   /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
   830   ///\endcode
   831   ///
   832   /// After the copy the \c nr map will contain the mapping from the
   833   /// nodes of the \c from digraph to the nodes of the \c to digraph and
   834   /// \c acr will contain the mapping from the arcs of the \c to digraph
   835   /// to the arcs of the \c from digraph.
   836   ///
   837   /// \see DigraphCopy
   838   template <typename From, typename To>
   839   DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
   840     return DigraphCopy<From, To>(from, to);
   841   }
   842 
   843   /// \brief Class to copy a graph.
   844   ///
   845   /// Class to copy a graph to another graph (duplicate a graph). The
   846   /// simplest way of using it is through the \c graphCopy() function.
   847   ///
   848   /// This class not only make a copy of a graph, but it can create
   849   /// references and cross references between the nodes, edges and arcs of
   850   /// the two graphs, and it can copy maps for using with the newly created
   851   /// graph.
   852   ///
   853   /// To make a copy from a graph, first an instance of GraphCopy
   854   /// should be created, then the data belongs to the graph should
   855   /// assigned to copy. In the end, the \c run() member should be
   856   /// called.
   857   ///
   858   /// The next code copies a graph with several data:
   859   ///\code
   860   ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
   861   ///  // Create references for the nodes
   862   ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   863   ///  cg.nodeRef(nr);
   864   ///  // Create cross references (inverse) for the edges
   865   ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
   866   ///  cg.edgeCrossRef(ecr);
   867   ///  // Copy an edge map
   868   ///  OrigGraph::EdgeMap<double> oemap(orig_graph);
   869   ///  NewGraph::EdgeMap<double> nemap(new_graph);
   870   ///  cg.edgeMap(oemap, nemap);
   871   ///  // Copy a node
   872   ///  OrigGraph::Node on;
   873   ///  NewGraph::Node nn;
   874   ///  cg.node(on, nn);
   875   ///  // Execute copying
   876   ///  cg.run();
   877   ///\endcode
   878   template <typename From, typename To>
   879   class GraphCopy {
   880   private:
   881 
   882     typedef typename From::Node Node;
   883     typedef typename From::NodeIt NodeIt;
   884     typedef typename From::Arc Arc;
   885     typedef typename From::ArcIt ArcIt;
   886     typedef typename From::Edge Edge;
   887     typedef typename From::EdgeIt EdgeIt;
   888 
   889     typedef typename To::Node TNode;
   890     typedef typename To::Arc TArc;
   891     typedef typename To::Edge TEdge;
   892 
   893     typedef typename From::template NodeMap<TNode> NodeRefMap;
   894     typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
   895 
   896     struct ArcRefMap {
   897       ArcRefMap(const From& from, const To& to,
   898                 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
   899         : _from(from), _to(to),
   900           _edge_ref(edge_ref), _node_ref(node_ref) {}
   901 
   902       typedef typename From::Arc Key;
   903       typedef typename To::Arc Value;
   904 
   905       Value operator[](const Key& key) const {
   906         bool forward = _from.u(key) != _from.v(key) ?
   907           _node_ref[_from.source(key)] ==
   908           _to.source(_to.direct(_edge_ref[key], true)) :
   909           _from.direction(key);
   910         return _to.direct(_edge_ref[key], forward);
   911       }
   912 
   913       const From& _from;
   914       const To& _to;
   915       const EdgeRefMap& _edge_ref;
   916       const NodeRefMap& _node_ref;
   917     };
   918 
   919   public:
   920 
   921     /// \brief Constructor of GraphCopy.
   922     ///
   923     /// Constructor of GraphCopy for copying the content of the
   924     /// \c from graph into the \c to graph.
   925     GraphCopy(const From& from, To& to)
   926       : _from(from), _to(to) {}
   927 
   928     /// \brief Destructor of GraphCopy
   929     ///
   930     /// Destructor of GraphCopy.
   931     ~GraphCopy() {
   932       for (int i = 0; i < int(_node_maps.size()); ++i) {
   933         delete _node_maps[i];
   934       }
   935       for (int i = 0; i < int(_arc_maps.size()); ++i) {
   936         delete _arc_maps[i];
   937       }
   938       for (int i = 0; i < int(_edge_maps.size()); ++i) {
   939         delete _edge_maps[i];
   940       }
   941     }
   942 
   943     /// \brief Copy the node references into the given map.
   944     ///
   945     /// This function copies the node references into the given map.
   946     /// The parameter should be a map, whose key type is the Node type of
   947     /// the source graph, while the value type is the Node type of the
   948     /// destination graph.
   949     template <typename NodeRef>
   950     GraphCopy& nodeRef(NodeRef& map) {
   951       _node_maps.push_back(new _core_bits::RefCopy<From, Node,
   952                            NodeRefMap, NodeRef>(map));
   953       return *this;
   954     }
   955 
   956     /// \brief Copy the node cross references into the given map.
   957     ///
   958     /// This function copies the node cross references (reverse references)
   959     /// into the given map. The parameter should be a map, whose key type
   960     /// is the Node type of the destination graph, while the value type is
   961     /// the Node type of the source graph.
   962     template <typename NodeCrossRef>
   963     GraphCopy& nodeCrossRef(NodeCrossRef& map) {
   964       _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
   965                            NodeRefMap, NodeCrossRef>(map));
   966       return *this;
   967     }
   968 
   969     /// \brief Make a copy of the given node map.
   970     ///
   971     /// This function makes a copy of the given node map for the newly
   972     /// created graph.
   973     /// The key type of the new map \c tmap should be the Node type of the
   974     /// destination graph, and the key type of the original map \c map
   975     /// should be the Node type of the source graph.
   976     template <typename FromMap, typename ToMap>
   977     GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
   978       _node_maps.push_back(new _core_bits::MapCopy<From, Node,
   979                            NodeRefMap, FromMap, ToMap>(map, tmap));
   980       return *this;
   981     }
   982 
   983     /// \brief Make a copy of the given node.
   984     ///
   985     /// This function makes a copy of the given node.
   986     GraphCopy& node(const Node& node, TNode& tnode) {
   987       _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
   988                            NodeRefMap, TNode>(node, tnode));
   989       return *this;
   990     }
   991 
   992     /// \brief Copy the arc references into the given map.
   993     ///
   994     /// This function copies the arc references into the given map.
   995     /// The parameter should be a map, whose key type is the Arc type of
   996     /// the source graph, while the value type is the Arc type of the
   997     /// destination graph.
   998     template <typename ArcRef>
   999     GraphCopy& arcRef(ArcRef& map) {
  1000       _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
  1001                           ArcRefMap, ArcRef>(map));
  1002       return *this;
  1003     }
  1004 
  1005     /// \brief Copy the arc cross references into the given map.
  1006     ///
  1007     /// This function copies the arc cross references (reverse references)
  1008     /// into the given map. The parameter should be a map, whose key type
  1009     /// is the Arc type of the destination graph, while the value type is
  1010     /// the Arc type of the source graph.
  1011     template <typename ArcCrossRef>
  1012     GraphCopy& arcCrossRef(ArcCrossRef& map) {
  1013       _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
  1014                           ArcRefMap, ArcCrossRef>(map));
  1015       return *this;
  1016     }
  1017 
  1018     /// \brief Make a copy of the given arc map.
  1019     ///
  1020     /// This function makes a copy of the given arc map for the newly
  1021     /// created graph.
  1022     /// The key type of the new map \c tmap should be the Arc type of the
  1023     /// destination graph, and the key type of the original map \c map
  1024     /// should be the Arc type of the source graph.
  1025     template <typename FromMap, typename ToMap>
  1026     GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
  1027       _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
  1028                           ArcRefMap, FromMap, ToMap>(map, tmap));
  1029       return *this;
  1030     }
  1031 
  1032     /// \brief Make a copy of the given arc.
  1033     ///
  1034     /// This function makes a copy of the given arc.
  1035     GraphCopy& arc(const Arc& arc, TArc& tarc) {
  1036       _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
  1037                           ArcRefMap, TArc>(arc, tarc));
  1038       return *this;
  1039     }
  1040 
  1041     /// \brief Copy the edge references into the given map.
  1042     ///
  1043     /// This function copies the edge references into the given map.
  1044     /// The parameter should be a map, whose key type is the Edge type of
  1045     /// the source graph, while the value type is the Edge type of the
  1046     /// destination graph.
  1047     template <typename EdgeRef>
  1048     GraphCopy& edgeRef(EdgeRef& map) {
  1049       _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
  1050                            EdgeRefMap, EdgeRef>(map));
  1051       return *this;
  1052     }
  1053 
  1054     /// \brief Copy the edge cross references into the given map.
  1055     ///
  1056     /// This function copies the edge cross references (reverse references)
  1057     /// into the given map. The parameter should be a map, whose key type
  1058     /// is the Edge type of the destination graph, while the value type is
  1059     /// the Edge type of the source graph.
  1060     template <typename EdgeCrossRef>
  1061     GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
  1062       _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
  1063                            Edge, EdgeRefMap, EdgeCrossRef>(map));
  1064       return *this;
  1065     }
  1066 
  1067     /// \brief Make a copy of the given edge map.
  1068     ///
  1069     /// This function makes a copy of the given edge map for the newly
  1070     /// created graph.
  1071     /// The key type of the new map \c tmap should be the Edge type of the
  1072     /// destination graph, and the key type of the original map \c map
  1073     /// should be the Edge type of the source graph.
  1074     template <typename FromMap, typename ToMap>
  1075     GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
  1076       _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
  1077                            EdgeRefMap, FromMap, ToMap>(map, tmap));
  1078       return *this;
  1079     }
  1080 
  1081     /// \brief Make a copy of the given edge.
  1082     ///
  1083     /// This function makes a copy of the given edge.
  1084     GraphCopy& edge(const Edge& edge, TEdge& tedge) {
  1085       _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
  1086                            EdgeRefMap, TEdge>(edge, tedge));
  1087       return *this;
  1088     }
  1089 
  1090     /// \brief Execute copying.
  1091     ///
  1092     /// This function executes the copying of the graph along with the
  1093     /// copying of the assigned data.
  1094     void run() {
  1095       NodeRefMap nodeRefMap(_from);
  1096       EdgeRefMap edgeRefMap(_from);
  1097       ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
  1098       _core_bits::GraphCopySelector<To>::
  1099         copy(_from, _to, nodeRefMap, edgeRefMap);
  1100       for (int i = 0; i < int(_node_maps.size()); ++i) {
  1101         _node_maps[i]->copy(_from, nodeRefMap);
  1102       }
  1103       for (int i = 0; i < int(_edge_maps.size()); ++i) {
  1104         _edge_maps[i]->copy(_from, edgeRefMap);
  1105       }
  1106       for (int i = 0; i < int(_arc_maps.size()); ++i) {
  1107         _arc_maps[i]->copy(_from, arcRefMap);
  1108       }
  1109     }
  1110 
  1111   private:
  1112 
  1113     const From& _from;
  1114     To& _to;
  1115 
  1116     std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
  1117       _node_maps;
  1118 
  1119     std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
  1120       _arc_maps;
  1121 
  1122     std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
  1123       _edge_maps;
  1124 
  1125   };
  1126 
  1127   /// \brief Copy a graph to another graph.
  1128   ///
  1129   /// This function copies a graph to another graph.
  1130   /// The complete usage of it is detailed in the GraphCopy class,
  1131   /// but a short example shows a basic work:
  1132   ///\code
  1133   /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
  1134   ///\endcode
  1135   ///
  1136   /// After the copy the \c nr map will contain the mapping from the
  1137   /// nodes of the \c from graph to the nodes of the \c to graph and
  1138   /// \c ecr will contain the mapping from the edges of the \c to graph
  1139   /// to the edges of the \c from graph.
  1140   ///
  1141   /// \see GraphCopy
  1142   template <typename From, typename To>
  1143   GraphCopy<From, To>
  1144   graphCopy(const From& from, To& to) {
  1145     return GraphCopy<From, To>(from, to);
  1146   }
  1147 
  1148   /// \brief Class to copy a bipartite graph.
  1149   ///
  1150   /// Class to copy a bipartite graph to another graph (duplicate a
  1151   /// graph). The simplest way of using it is through the
  1152   /// \c bpGraphCopy() function.
  1153   ///
  1154   /// This class not only make a copy of a bipartite graph, but it can
  1155   /// create references and cross references between the nodes, edges
  1156   /// and arcs of the two graphs, and it can copy maps for using with
  1157   /// the newly created graph.
  1158   ///
  1159   /// To make a copy from a graph, first an instance of BpGraphCopy
  1160   /// should be created, then the data belongs to the graph should
  1161   /// assigned to copy. In the end, the \c run() member should be
  1162   /// called.
  1163   ///
  1164   /// The next code copies a graph with several data:
  1165   ///\code
  1166   ///  BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
  1167   ///  // Create references for the nodes
  1168   ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
  1169   ///  cg.nodeRef(nr);
  1170   ///  // Create cross references (inverse) for the edges
  1171   ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
  1172   ///  cg.edgeCrossRef(ecr);
  1173   ///  // Copy a red node map
  1174   ///  OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
  1175   ///  NewBpGraph::RedNodeMap<double> nrmap(new_graph);
  1176   ///  cg.redNodeMap(ormap, nrmap);
  1177   ///  // Copy a node
  1178   ///  OrigBpGraph::Node on;
  1179   ///  NewBpGraph::Node nn;
  1180   ///  cg.node(on, nn);
  1181   ///  // Execute copying
  1182   ///  cg.run();
  1183   ///\endcode
  1184   template <typename From, typename To>
  1185   class BpGraphCopy {
  1186   private:
  1187 
  1188     typedef typename From::Node Node;
  1189     typedef typename From::RedNode RedNode;
  1190     typedef typename From::BlueNode BlueNode;
  1191     typedef typename From::NodeIt NodeIt;
  1192     typedef typename From::Arc Arc;
  1193     typedef typename From::ArcIt ArcIt;
  1194     typedef typename From::Edge Edge;
  1195     typedef typename From::EdgeIt EdgeIt;
  1196 
  1197     typedef typename To::Node TNode;
  1198     typedef typename To::RedNode TRedNode;
  1199     typedef typename To::BlueNode TBlueNode;
  1200     typedef typename To::Arc TArc;
  1201     typedef typename To::Edge TEdge;
  1202 
  1203     typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
  1204     typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
  1205     typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
  1206 
  1207     struct NodeRefMap {
  1208       NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
  1209                  const BlueNodeRefMap& blue_node_ref)
  1210         : _from(from), _red_node_ref(red_node_ref),
  1211           _blue_node_ref(blue_node_ref) {}
  1212 
  1213       typedef typename From::Node Key;
  1214       typedef typename To::Node Value;
  1215 
  1216       Value operator[](const Key& key) const {
  1217         if (_from.red(key)) {
  1218           return _red_node_ref[_from.asRedNodeUnsafe(key)];
  1219         } else {
  1220           return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
  1221         }
  1222       }
  1223 
  1224       const From& _from;
  1225       const RedNodeRefMap& _red_node_ref;
  1226       const BlueNodeRefMap& _blue_node_ref;
  1227     };
  1228 
  1229     struct ArcRefMap {
  1230       ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
  1231         : _from(from), _to(to), _edge_ref(edge_ref) {}
  1232 
  1233       typedef typename From::Arc Key;
  1234       typedef typename To::Arc Value;
  1235 
  1236       Value operator[](const Key& key) const {
  1237         return _to.direct(_edge_ref[key], _from.direction(key));
  1238       }
  1239 
  1240       const From& _from;
  1241       const To& _to;
  1242       const EdgeRefMap& _edge_ref;
  1243     };
  1244 
  1245   public:
  1246 
  1247     /// \brief Constructor of BpGraphCopy.
  1248     ///
  1249     /// Constructor of BpGraphCopy for copying the content of the
  1250     /// \c from graph into the \c to graph.
  1251     BpGraphCopy(const From& from, To& to)
  1252       : _from(from), _to(to) {}
  1253 
  1254     /// \brief Destructor of BpGraphCopy
  1255     ///
  1256     /// Destructor of BpGraphCopy.
  1257     ~BpGraphCopy() {
  1258       for (int i = 0; i < int(_node_maps.size()); ++i) {
  1259         delete _node_maps[i];
  1260       }
  1261       for (int i = 0; i < int(_red_maps.size()); ++i) {
  1262         delete _red_maps[i];
  1263       }
  1264       for (int i = 0; i < int(_blue_maps.size()); ++i) {
  1265         delete _blue_maps[i];
  1266       }
  1267       for (int i = 0; i < int(_arc_maps.size()); ++i) {
  1268         delete _arc_maps[i];
  1269       }
  1270       for (int i = 0; i < int(_edge_maps.size()); ++i) {
  1271         delete _edge_maps[i];
  1272       }
  1273     }
  1274 
  1275     /// \brief Copy the node references into the given map.
  1276     ///
  1277     /// This function copies the node references into the given map.
  1278     /// The parameter should be a map, whose key type is the Node type of
  1279     /// the source graph, while the value type is the Node type of the
  1280     /// destination graph.
  1281     template <typename NodeRef>
  1282     BpGraphCopy& nodeRef(NodeRef& map) {
  1283       _node_maps.push_back(new _core_bits::RefCopy<From, Node,
  1284                            NodeRefMap, NodeRef>(map));
  1285       return *this;
  1286     }
  1287 
  1288     /// \brief Copy the node cross references into the given map.
  1289     ///
  1290     /// This function copies the node cross references (reverse references)
  1291     /// into the given map. The parameter should be a map, whose key type
  1292     /// is the Node type of the destination graph, while the value type is
  1293     /// the Node type of the source graph.
  1294     template <typename NodeCrossRef>
  1295     BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
  1296       _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
  1297                            NodeRefMap, NodeCrossRef>(map));
  1298       return *this;
  1299     }
  1300 
  1301     /// \brief Make a copy of the given node map.
  1302     ///
  1303     /// This function makes a copy of the given node map for the newly
  1304     /// created graph.
  1305     /// The key type of the new map \c tmap should be the Node type of the
  1306     /// destination graph, and the key type of the original map \c map
  1307     /// should be the Node type of the source graph.
  1308     template <typename FromMap, typename ToMap>
  1309     BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
  1310       _node_maps.push_back(new _core_bits::MapCopy<From, Node,
  1311                            NodeRefMap, FromMap, ToMap>(map, tmap));
  1312       return *this;
  1313     }
  1314 
  1315     /// \brief Make a copy of the given node.
  1316     ///
  1317     /// This function makes a copy of the given node.
  1318     BpGraphCopy& node(const Node& node, TNode& tnode) {
  1319       _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
  1320                            NodeRefMap, TNode>(node, tnode));
  1321       return *this;
  1322     }
  1323 
  1324     /// \brief Copy the red node references into the given map.
  1325     ///
  1326     /// This function copies the red node references into the given
  1327     /// map.  The parameter should be a map, whose key type is the
  1328     /// Node type of the source graph with the red item set, while the
  1329     /// value type is the Node type of the destination graph.
  1330     template <typename RedRef>
  1331     BpGraphCopy& redRef(RedRef& map) {
  1332       _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
  1333                           RedNodeRefMap, RedRef>(map));
  1334       return *this;
  1335     }
  1336 
  1337     /// \brief Copy the red node cross references into the given map.
  1338     ///
  1339     /// This function copies the red node cross references (reverse
  1340     /// references) into the given map. The parameter should be a map,
  1341     /// whose key type is the Node type of the destination graph with
  1342     /// the red item set, while the value type is the Node type of the
  1343     /// source graph.
  1344     template <typename RedCrossRef>
  1345     BpGraphCopy& redCrossRef(RedCrossRef& map) {
  1346       _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
  1347                           RedNodeRefMap, RedCrossRef>(map));
  1348       return *this;
  1349     }
  1350 
  1351     /// \brief Make a copy of the given red node map.
  1352     ///
  1353     /// This function makes a copy of the given red node map for the newly
  1354     /// created graph.
  1355     /// The key type of the new map \c tmap should be the Node type of
  1356     /// the destination graph with the red items, and the key type of
  1357     /// the original map \c map should be the Node type of the source
  1358     /// graph.
  1359     template <typename FromMap, typename ToMap>
  1360     BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
  1361       _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
  1362                           RedNodeRefMap, FromMap, ToMap>(map, tmap));
  1363       return *this;
  1364     }
  1365 
  1366     /// \brief Make a copy of the given red node.
  1367     ///
  1368     /// This function makes a copy of the given red node.
  1369     BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
  1370       _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
  1371                           RedNodeRefMap, TRedNode>(node, tnode));
  1372       return *this;
  1373     }
  1374 
  1375     /// \brief Copy the blue node references into the given map.
  1376     ///
  1377     /// This function copies the blue node references into the given
  1378     /// map.  The parameter should be a map, whose key type is the
  1379     /// Node type of the source graph with the blue item set, while the
  1380     /// value type is the Node type of the destination graph.
  1381     template <typename BlueRef>
  1382     BpGraphCopy& blueRef(BlueRef& map) {
  1383       _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
  1384                            BlueNodeRefMap, BlueRef>(map));
  1385       return *this;
  1386     }
  1387 
  1388     /// \brief Copy the blue node cross references into the given map.
  1389     ///
  1390     /// This function copies the blue node cross references (reverse
  1391     /// references) into the given map. The parameter should be a map,
  1392     /// whose key type is the Node type of the destination graph with
  1393     /// the blue item set, while the value type is the Node type of the
  1394     /// source graph.
  1395     template <typename BlueCrossRef>
  1396     BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
  1397       _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
  1398                            BlueNodeRefMap, BlueCrossRef>(map));
  1399       return *this;
  1400     }
  1401 
  1402     /// \brief Make a copy of the given blue node map.
  1403     ///
  1404     /// This function makes a copy of the given blue node map for the newly
  1405     /// created graph.
  1406     /// The key type of the new map \c tmap should be the Node type of
  1407     /// the destination graph with the blue items, and the key type of
  1408     /// the original map \c map should be the Node type of the source
  1409     /// graph.
  1410     template <typename FromMap, typename ToMap>
  1411     BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
  1412       _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
  1413                            BlueNodeRefMap, FromMap, ToMap>(map, tmap));
  1414       return *this;
  1415     }
  1416 
  1417     /// \brief Make a copy of the given blue node.
  1418     ///
  1419     /// This function makes a copy of the given blue node.
  1420     BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
  1421       _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
  1422                            BlueNodeRefMap, TBlueNode>(node, tnode));
  1423       return *this;
  1424     }
  1425 
  1426     /// \brief Copy the arc references into the given map.
  1427     ///
  1428     /// This function copies the arc references into the given map.
  1429     /// The parameter should be a map, whose key type is the Arc type of
  1430     /// the source graph, while the value type is the Arc type of the
  1431     /// destination graph.
  1432     template <typename ArcRef>
  1433     BpGraphCopy& arcRef(ArcRef& map) {
  1434       _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
  1435                           ArcRefMap, ArcRef>(map));
  1436       return *this;
  1437     }
  1438 
  1439     /// \brief Copy the arc cross references into the given map.
  1440     ///
  1441     /// This function copies the arc cross references (reverse references)
  1442     /// into the given map. The parameter should be a map, whose key type
  1443     /// is the Arc type of the destination graph, while the value type is
  1444     /// the Arc type of the source graph.
  1445     template <typename ArcCrossRef>
  1446     BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
  1447       _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
  1448                           ArcRefMap, ArcCrossRef>(map));
  1449       return *this;
  1450     }
  1451 
  1452     /// \brief Make a copy of the given arc map.
  1453     ///
  1454     /// This function makes a copy of the given arc map for the newly
  1455     /// created graph.
  1456     /// The key type of the new map \c tmap should be the Arc type of the
  1457     /// destination graph, and the key type of the original map \c map
  1458     /// should be the Arc type of the source graph.
  1459     template <typename FromMap, typename ToMap>
  1460     BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
  1461       _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
  1462                           ArcRefMap, FromMap, ToMap>(map, tmap));
  1463       return *this;
  1464     }
  1465 
  1466     /// \brief Make a copy of the given arc.
  1467     ///
  1468     /// This function makes a copy of the given arc.
  1469     BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
  1470       _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
  1471                           ArcRefMap, TArc>(arc, tarc));
  1472       return *this;
  1473     }
  1474 
  1475     /// \brief Copy the edge references into the given map.
  1476     ///
  1477     /// This function copies the edge references into the given map.
  1478     /// The parameter should be a map, whose key type is the Edge type of
  1479     /// the source graph, while the value type is the Edge type of the
  1480     /// destination graph.
  1481     template <typename EdgeRef>
  1482     BpGraphCopy& edgeRef(EdgeRef& map) {
  1483       _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
  1484                            EdgeRefMap, EdgeRef>(map));
  1485       return *this;
  1486     }
  1487 
  1488     /// \brief Copy the edge cross references into the given map.
  1489     ///
  1490     /// This function copies the edge cross references (reverse references)
  1491     /// into the given map. The parameter should be a map, whose key type
  1492     /// is the Edge type of the destination graph, while the value type is
  1493     /// the Edge type of the source graph.
  1494     template <typename EdgeCrossRef>
  1495     BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
  1496       _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
  1497                            Edge, EdgeRefMap, EdgeCrossRef>(map));
  1498       return *this;
  1499     }
  1500 
  1501     /// \brief Make a copy of the given edge map.
  1502     ///
  1503     /// This function makes a copy of the given edge map for the newly
  1504     /// created graph.
  1505     /// The key type of the new map \c tmap should be the Edge type of the
  1506     /// destination graph, and the key type of the original map \c map
  1507     /// should be the Edge type of the source graph.
  1508     template <typename FromMap, typename ToMap>
  1509     BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
  1510       _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
  1511                            EdgeRefMap, FromMap, ToMap>(map, tmap));
  1512       return *this;
  1513     }
  1514 
  1515     /// \brief Make a copy of the given edge.
  1516     ///
  1517     /// This function makes a copy of the given edge.
  1518     BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
  1519       _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
  1520                            EdgeRefMap, TEdge>(edge, tedge));
  1521       return *this;
  1522     }
  1523 
  1524     /// \brief Execute copying.
  1525     ///
  1526     /// This function executes the copying of the graph along with the
  1527     /// copying of the assigned data.
  1528     void run() {
  1529       RedNodeRefMap redNodeRefMap(_from);
  1530       BlueNodeRefMap blueNodeRefMap(_from);
  1531       NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
  1532       EdgeRefMap edgeRefMap(_from);
  1533       ArcRefMap arcRefMap(_from, _to, edgeRefMap);
  1534       _core_bits::BpGraphCopySelector<To>::
  1535         copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
  1536       for (int i = 0; i < int(_node_maps.size()); ++i) {
  1537         _node_maps[i]->copy(_from, nodeRefMap);
  1538       }
  1539       for (int i = 0; i < int(_red_maps.size()); ++i) {
  1540         _red_maps[i]->copy(_from, redNodeRefMap);
  1541       }
  1542       for (int i = 0; i < int(_blue_maps.size()); ++i) {
  1543         _blue_maps[i]->copy(_from, blueNodeRefMap);
  1544       }
  1545       for (int i = 0; i < int(_edge_maps.size()); ++i) {
  1546         _edge_maps[i]->copy(_from, edgeRefMap);
  1547       }
  1548       for (int i = 0; i < int(_arc_maps.size()); ++i) {
  1549         _arc_maps[i]->copy(_from, arcRefMap);
  1550       }
  1551     }
  1552 
  1553   private:
  1554 
  1555     const From& _from;
  1556     To& _to;
  1557 
  1558     std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
  1559       _node_maps;
  1560 
  1561     std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
  1562       _red_maps;
  1563 
  1564     std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
  1565       _blue_maps;
  1566 
  1567     std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
  1568       _arc_maps;
  1569 
  1570     std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
  1571       _edge_maps;
  1572 
  1573   };
  1574 
  1575   /// \brief Copy a graph to another graph.
  1576   ///
  1577   /// This function copies a graph to another graph.
  1578   /// The complete usage of it is detailed in the BpGraphCopy class,
  1579   /// but a short example shows a basic work:
  1580   ///\code
  1581   /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
  1582   ///\endcode
  1583   ///
  1584   /// After the copy the \c nr map will contain the mapping from the
  1585   /// nodes of the \c from graph to the nodes of the \c to graph and
  1586   /// \c ecr will contain the mapping from the edges of the \c to graph
  1587   /// to the edges of the \c from graph.
  1588   ///
  1589   /// \see BpGraphCopy
  1590   template <typename From, typename To>
  1591   BpGraphCopy<From, To>
  1592   bpGraphCopy(const From& from, To& to) {
  1593     return BpGraphCopy<From, To>(from, to);
  1594   }
  1595 
  1596   namespace _core_bits {
  1597 
  1598     template <typename Graph, typename Enable = void>
  1599     struct FindArcSelector {
  1600       typedef typename Graph::Node Node;
  1601       typedef typename Graph::Arc Arc;
  1602       static Arc find(const Graph &g, Node u, Node v, Arc e) {
  1603         if (e == INVALID) {
  1604           g.firstOut(e, u);
  1605         } else {
  1606           g.nextOut(e);
  1607         }
  1608         while (e != INVALID && g.target(e) != v) {
  1609           g.nextOut(e);
  1610         }
  1611         return e;
  1612       }
  1613     };
  1614 
  1615     template <typename Graph>
  1616     struct FindArcSelector<
  1617       Graph,
  1618       typename enable_if<typename Graph::FindArcTag, void>::type>
  1619     {
  1620       typedef typename Graph::Node Node;
  1621       typedef typename Graph::Arc Arc;
  1622       static Arc find(const Graph &g, Node u, Node v, Arc prev) {
  1623         return g.findArc(u, v, prev);
  1624       }
  1625     };
  1626   }
  1627 
  1628   /// \brief Find an arc between two nodes of a digraph.
  1629   ///
  1630   /// This function finds an arc from node \c u to node \c v in the
  1631   /// digraph \c g.
  1632   ///
  1633   /// If \c prev is \ref INVALID (this is the default value), then
  1634   /// it finds the first arc from \c u to \c v. Otherwise it looks for
  1635   /// the next arc from \c u to \c v after \c prev.
  1636   /// \return The found arc or \ref INVALID if there is no such an arc.
  1637   ///
  1638   /// Thus you can iterate through each arc from \c u to \c v as it follows.
  1639   ///\code
  1640   /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
  1641   ///   ...
  1642   /// }
  1643   ///\endcode
  1644   ///
  1645   /// \note \ref ConArcIt provides iterator interface for the same
  1646   /// functionality.
  1647   ///
  1648   ///\sa ConArcIt
  1649   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1650   template <typename Graph>
  1651   inline typename Graph::Arc
  1652   findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
  1653           typename Graph::Arc prev = INVALID) {
  1654     return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
  1655   }
  1656 
  1657   /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
  1658   ///
  1659   /// Iterator for iterating on parallel arcs connecting the same nodes. It is
  1660   /// a higher level interface for the \ref findArc() function. You can
  1661   /// use it the following way:
  1662   ///\code
  1663   /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
  1664   ///   ...
  1665   /// }
  1666   ///\endcode
  1667   ///
  1668   ///\sa findArc()
  1669   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1670   template <typename GR>
  1671   class ConArcIt : public GR::Arc {
  1672     typedef typename GR::Arc Parent;
  1673 
  1674   public:
  1675 
  1676     typedef typename GR::Arc Arc;
  1677     typedef typename GR::Node Node;
  1678 
  1679     /// \brief Constructor.
  1680     ///
  1681     /// Construct a new ConArcIt iterating on the arcs that
  1682     /// connects nodes \c u and \c v.
  1683     ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
  1684       Parent::operator=(findArc(_graph, u, v));
  1685     }
  1686 
  1687     /// \brief Constructor.
  1688     ///
  1689     /// Construct a new ConArcIt that continues the iterating from arc \c a.
  1690     ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
  1691 
  1692     /// \brief Increment operator.
  1693     ///
  1694     /// It increments the iterator and gives back the next arc.
  1695     ConArcIt& operator++() {
  1696       Parent::operator=(findArc(_graph, _graph.source(*this),
  1697                                 _graph.target(*this), *this));
  1698       return *this;
  1699     }
  1700   private:
  1701     const GR& _graph;
  1702   };
  1703 
  1704   namespace _core_bits {
  1705 
  1706     template <typename Graph, typename Enable = void>
  1707     struct FindEdgeSelector {
  1708       typedef typename Graph::Node Node;
  1709       typedef typename Graph::Edge Edge;
  1710       static Edge find(const Graph &g, Node u, Node v, Edge e) {
  1711         bool b;
  1712         if (u != v) {
  1713           if (e == INVALID) {
  1714             g.firstInc(e, b, u);
  1715           } else {
  1716             b = g.u(e) == u;
  1717             g.nextInc(e, b);
  1718           }
  1719           while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
  1720             g.nextInc(e, b);
  1721           }
  1722         } else {
  1723           if (e == INVALID) {
  1724             g.firstInc(e, b, u);
  1725           } else {
  1726             b = true;
  1727             g.nextInc(e, b);
  1728           }
  1729           while (e != INVALID && (!b || g.v(e) != v)) {
  1730             g.nextInc(e, b);
  1731           }
  1732         }
  1733         return e;
  1734       }
  1735     };
  1736 
  1737     template <typename Graph>
  1738     struct FindEdgeSelector<
  1739       Graph,
  1740       typename enable_if<typename Graph::FindEdgeTag, void>::type>
  1741     {
  1742       typedef typename Graph::Node Node;
  1743       typedef typename Graph::Edge Edge;
  1744       static Edge find(const Graph &g, Node u, Node v, Edge prev) {
  1745         return g.findEdge(u, v, prev);
  1746       }
  1747     };
  1748   }
  1749 
  1750   /// \brief Find an edge between two nodes of a graph.
  1751   ///
  1752   /// This function finds an edge from node \c u to node \c v in graph \c g.
  1753   /// If node \c u and node \c v is equal then each loop edge
  1754   /// will be enumerated once.
  1755   ///
  1756   /// If \c prev is \ref INVALID (this is the default value), then
  1757   /// it finds the first edge from \c u to \c v. Otherwise it looks for
  1758   /// the next edge from \c u to \c v after \c prev.
  1759   /// \return The found edge or \ref INVALID if there is no such an edge.
  1760   ///
  1761   /// Thus you can iterate through each edge between \c u and \c v
  1762   /// as it follows.
  1763   ///\code
  1764   /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
  1765   ///   ...
  1766   /// }
  1767   ///\endcode
  1768   ///
  1769   /// \note \ref ConEdgeIt provides iterator interface for the same
  1770   /// functionality.
  1771   ///
  1772   ///\sa ConEdgeIt
  1773   template <typename Graph>
  1774   inline typename Graph::Edge
  1775   findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
  1776             typename Graph::Edge p = INVALID) {
  1777     return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
  1778   }
  1779 
  1780   /// \brief Iterator for iterating on parallel edges connecting the same nodes.
  1781   ///
  1782   /// Iterator for iterating on parallel edges connecting the same nodes.
  1783   /// It is a higher level interface for the findEdge() function. You can
  1784   /// use it the following way:
  1785   ///\code
  1786   /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
  1787   ///   ...
  1788   /// }
  1789   ///\endcode
  1790   ///
  1791   ///\sa findEdge()
  1792   template <typename GR>
  1793   class ConEdgeIt : public GR::Edge {
  1794     typedef typename GR::Edge Parent;
  1795 
  1796   public:
  1797 
  1798     typedef typename GR::Edge Edge;
  1799     typedef typename GR::Node Node;
  1800 
  1801     /// \brief Constructor.
  1802     ///
  1803     /// Construct a new ConEdgeIt iterating on the edges that
  1804     /// connects nodes \c u and \c v.
  1805     ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
  1806       Parent::operator=(findEdge(_graph, _u, _v));
  1807     }
  1808 
  1809     /// \brief Constructor.
  1810     ///
  1811     /// Construct a new ConEdgeIt that continues iterating from edge \c e.
  1812     ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
  1813 
  1814     /// \brief Increment operator.
  1815     ///
  1816     /// It increments the iterator and gives back the next edge.
  1817     ConEdgeIt& operator++() {
  1818       Parent::operator=(findEdge(_graph, _u, _v, *this));
  1819       return *this;
  1820     }
  1821   private:
  1822     const GR& _graph;
  1823     Node _u, _v;
  1824   };
  1825 
  1826 
  1827   ///Dynamic arc look-up between given endpoints.
  1828 
  1829   ///Using this class, you can find an arc in a digraph from a given
  1830   ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
  1831   ///where <em>d</em> is the out-degree of the source node.
  1832   ///
  1833   ///It is possible to find \e all parallel arcs between two nodes with
  1834   ///the \c operator() member.
  1835   ///
  1836   ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
  1837   ///\ref AllArcLookUp if your digraph is not changed so frequently.
  1838   ///
  1839   ///This class uses a self-adjusting binary search tree, the Splay tree
  1840   ///of Sleator and Tarjan to guarantee the logarithmic amortized
  1841   ///time bound for arc look-ups. This class also guarantees the
  1842   ///optimal time bound in a constant factor for any distribution of
  1843   ///queries.
  1844   ///
  1845   ///\tparam GR The type of the underlying digraph.
  1846   ///
  1847   ///\sa ArcLookUp
  1848   ///\sa AllArcLookUp
  1849   template <typename GR>
  1850   class DynArcLookUp
  1851     : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
  1852   {
  1853     typedef typename ItemSetTraits<GR, typename GR::Arc>
  1854     ::ItemNotifier::ObserverBase Parent;
  1855 
  1856     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1857 
  1858   public:
  1859 
  1860     /// The Digraph type
  1861     typedef GR Digraph;
  1862 
  1863   protected:
  1864 
  1865     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
  1866     {
  1867       typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
  1868 
  1869     public:
  1870 
  1871       AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
  1872 
  1873       virtual void add(const Node& node) {
  1874         Parent::add(node);
  1875         Parent::set(node, INVALID);
  1876       }
  1877 
  1878       virtual void add(const std::vector<Node>& nodes) {
  1879         Parent::add(nodes);
  1880         for (int i = 0; i < int(nodes.size()); ++i) {
  1881           Parent::set(nodes[i], INVALID);
  1882         }
  1883       }
  1884 
  1885       virtual void build() {
  1886         Parent::build();
  1887         Node it;
  1888         typename Parent::Notifier* nf = Parent::notifier();
  1889         for (nf->first(it); it != INVALID; nf->next(it)) {
  1890           Parent::set(it, INVALID);
  1891         }
  1892       }
  1893     };
  1894 
  1895     class ArcLess {
  1896       const Digraph &g;
  1897     public:
  1898       ArcLess(const Digraph &_g) : g(_g) {}
  1899       bool operator()(Arc a,Arc b) const
  1900       {
  1901         return g.target(a)<g.target(b);
  1902       }
  1903     };
  1904 
  1905   protected:
  1906 
  1907     const Digraph &_g;
  1908     AutoNodeMap _head;
  1909     typename Digraph::template ArcMap<Arc> _parent;
  1910     typename Digraph::template ArcMap<Arc> _left;
  1911     typename Digraph::template ArcMap<Arc> _right;
  1912 
  1913   public:
  1914 
  1915     ///Constructor
  1916 
  1917     ///Constructor.
  1918     ///
  1919     ///It builds up the search database.
  1920     DynArcLookUp(const Digraph &g)
  1921       : _g(g),_head(g),_parent(g),_left(g),_right(g)
  1922     {
  1923       Parent::attach(_g.notifier(typename Digraph::Arc()));
  1924       refresh();
  1925     }
  1926 
  1927   protected:
  1928 
  1929     virtual void add(const Arc& arc) {
  1930       insert(arc);
  1931     }
  1932 
  1933     virtual void add(const std::vector<Arc>& arcs) {
  1934       for (int i = 0; i < int(arcs.size()); ++i) {
  1935         insert(arcs[i]);
  1936       }
  1937     }
  1938 
  1939     virtual void erase(const Arc& arc) {
  1940       remove(arc);
  1941     }
  1942 
  1943     virtual void erase(const std::vector<Arc>& arcs) {
  1944       for (int i = 0; i < int(arcs.size()); ++i) {
  1945         remove(arcs[i]);
  1946       }
  1947     }
  1948 
  1949     virtual void build() {
  1950       refresh();
  1951     }
  1952 
  1953     virtual void clear() {
  1954       for(NodeIt n(_g);n!=INVALID;++n) {
  1955         _head[n] = INVALID;
  1956       }
  1957     }
  1958 
  1959     void insert(Arc arc) {
  1960       Node s = _g.source(arc);
  1961       Node t = _g.target(arc);
  1962       _left[arc] = INVALID;
  1963       _right[arc] = INVALID;
  1964 
  1965       Arc e = _head[s];
  1966       if (e == INVALID) {
  1967         _head[s] = arc;
  1968         _parent[arc] = INVALID;
  1969         return;
  1970       }
  1971       while (true) {
  1972         if (t < _g.target(e)) {
  1973           if (_left[e] == INVALID) {
  1974             _left[e] = arc;
  1975             _parent[arc] = e;
  1976             splay(arc);
  1977             return;
  1978           } else {
  1979             e = _left[e];
  1980           }
  1981         } else {
  1982           if (_right[e] == INVALID) {
  1983             _right[e] = arc;
  1984             _parent[arc] = e;
  1985             splay(arc);
  1986             return;
  1987           } else {
  1988             e = _right[e];
  1989           }
  1990         }
  1991       }
  1992     }
  1993 
  1994     void remove(Arc arc) {
  1995       if (_left[arc] == INVALID) {
  1996         if (_right[arc] != INVALID) {
  1997           _parent[_right[arc]] = _parent[arc];
  1998         }
  1999         if (_parent[arc] != INVALID) {
  2000           if (_left[_parent[arc]] == arc) {
  2001             _left[_parent[arc]] = _right[arc];
  2002           } else {
  2003             _right[_parent[arc]] = _right[arc];
  2004           }
  2005         } else {
  2006           _head[_g.source(arc)] = _right[arc];
  2007         }
  2008       } else if (_right[arc] == INVALID) {
  2009         _parent[_left[arc]] = _parent[arc];
  2010         if (_parent[arc] != INVALID) {
  2011           if (_left[_parent[arc]] == arc) {
  2012             _left[_parent[arc]] = _left[arc];
  2013           } else {
  2014             _right[_parent[arc]] = _left[arc];
  2015           }
  2016         } else {
  2017           _head[_g.source(arc)] = _left[arc];
  2018         }
  2019       } else {
  2020         Arc e = _left[arc];
  2021         if (_right[e] != INVALID) {
  2022           e = _right[e];
  2023           while (_right[e] != INVALID) {
  2024             e = _right[e];
  2025           }
  2026           Arc s = _parent[e];
  2027           _right[_parent[e]] = _left[e];
  2028           if (_left[e] != INVALID) {
  2029             _parent[_left[e]] = _parent[e];
  2030           }
  2031 
  2032           _left[e] = _left[arc];
  2033           _parent[_left[arc]] = e;
  2034           _right[e] = _right[arc];
  2035           _parent[_right[arc]] = e;
  2036 
  2037           _parent[e] = _parent[arc];
  2038           if (_parent[arc] != INVALID) {
  2039             if (_left[_parent[arc]] == arc) {
  2040               _left[_parent[arc]] = e;
  2041             } else {
  2042               _right[_parent[arc]] = e;
  2043             }
  2044           }
  2045           splay(s);
  2046         } else {
  2047           _right[e] = _right[arc];
  2048           _parent[_right[arc]] = e;
  2049           _parent[e] = _parent[arc];
  2050 
  2051           if (_parent[arc] != INVALID) {
  2052             if (_left[_parent[arc]] == arc) {
  2053               _left[_parent[arc]] = e;
  2054             } else {
  2055               _right[_parent[arc]] = e;
  2056             }
  2057           } else {
  2058             _head[_g.source(arc)] = e;
  2059           }
  2060         }
  2061       }
  2062     }
  2063 
  2064     Arc refreshRec(std::vector<Arc> &v,int a,int b)
  2065     {
  2066       int m=(a+b)/2;
  2067       Arc me=v[m];
  2068       if (a < m) {
  2069         Arc left = refreshRec(v,a,m-1);
  2070         _left[me] = left;
  2071         _parent[left] = me;
  2072       } else {
  2073         _left[me] = INVALID;
  2074       }
  2075       if (m < b) {
  2076         Arc right = refreshRec(v,m+1,b);
  2077         _right[me] = right;
  2078         _parent[right] = me;
  2079       } else {
  2080         _right[me] = INVALID;
  2081       }
  2082       return me;
  2083     }
  2084 
  2085     void refresh() {
  2086       for(NodeIt n(_g);n!=INVALID;++n) {
  2087         std::vector<Arc> v;
  2088         for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
  2089         if (!v.empty()) {
  2090           std::sort(v.begin(),v.end(),ArcLess(_g));
  2091           Arc head = refreshRec(v,0,v.size()-1);
  2092           _head[n] = head;
  2093           _parent[head] = INVALID;
  2094         }
  2095         else _head[n] = INVALID;
  2096       }
  2097     }
  2098 
  2099     void zig(Arc v) {
  2100       Arc w = _parent[v];
  2101       _parent[v] = _parent[w];
  2102       _parent[w] = v;
  2103       _left[w] = _right[v];
  2104       _right[v] = w;
  2105       if (_parent[v] != INVALID) {
  2106         if (_right[_parent[v]] == w) {
  2107           _right[_parent[v]] = v;
  2108         } else {
  2109           _left[_parent[v]] = v;
  2110         }
  2111       }
  2112       if (_left[w] != INVALID){
  2113         _parent[_left[w]] = w;
  2114       }
  2115     }
  2116 
  2117     void zag(Arc v) {
  2118       Arc w = _parent[v];
  2119       _parent[v] = _parent[w];
  2120       _parent[w] = v;
  2121       _right[w] = _left[v];
  2122       _left[v] = w;
  2123       if (_parent[v] != INVALID){
  2124         if (_left[_parent[v]] == w) {
  2125           _left[_parent[v]] = v;
  2126         } else {
  2127           _right[_parent[v]] = v;
  2128         }
  2129       }
  2130       if (_right[w] != INVALID){
  2131         _parent[_right[w]] = w;
  2132       }
  2133     }
  2134 
  2135     void splay(Arc v) {
  2136       while (_parent[v] != INVALID) {
  2137         if (v == _left[_parent[v]]) {
  2138           if (_parent[_parent[v]] == INVALID) {
  2139             zig(v);
  2140           } else {
  2141             if (_parent[v] == _left[_parent[_parent[v]]]) {
  2142               zig(_parent[v]);
  2143               zig(v);
  2144             } else {
  2145               zig(v);
  2146               zag(v);
  2147             }
  2148           }
  2149         } else {
  2150           if (_parent[_parent[v]] == INVALID) {
  2151             zag(v);
  2152           } else {
  2153             if (_parent[v] == _left[_parent[_parent[v]]]) {
  2154               zag(v);
  2155               zig(v);
  2156             } else {
  2157               zag(_parent[v]);
  2158               zag(v);
  2159             }
  2160           }
  2161         }
  2162       }
  2163       _head[_g.source(v)] = v;
  2164     }
  2165 
  2166 
  2167   public:
  2168 
  2169     ///Find an arc between two nodes.
  2170 
  2171     ///Find an arc between two nodes.
  2172     ///\param s The source node.
  2173     ///\param t The target node.
  2174     ///\param p The previous arc between \c s and \c t. It it is INVALID or
  2175     ///not given, the operator finds the first appropriate arc.
  2176     ///\return An arc from \c s to \c t after \c p or
  2177     ///\ref INVALID if there is no more.
  2178     ///
  2179     ///For example, you can count the number of arcs from \c u to \c v in the
  2180     ///following way.
  2181     ///\code
  2182     ///DynArcLookUp<ListDigraph> ae(g);
  2183     ///...
  2184     ///int n = 0;
  2185     ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
  2186     ///\endcode
  2187     ///
  2188     ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
  2189     ///amortized time, specifically, the time complexity of the lookups
  2190     ///is equal to the optimal search tree implementation for the
  2191     ///current query distribution in a constant factor.
  2192     ///
  2193     ///\note This is a dynamic data structure, therefore the data
  2194     ///structure is updated after each graph alteration. Thus although
  2195     ///this data structure is theoretically faster than \ref ArcLookUp
  2196     ///and \ref AllArcLookUp, it often provides worse performance than
  2197     ///them.
  2198     Arc operator()(Node s, Node t, Arc p = INVALID) const  {
  2199       if (p == INVALID) {
  2200         Arc a = _head[s];
  2201         if (a == INVALID) return INVALID;
  2202         Arc r = INVALID;
  2203         while (true) {
  2204           if (_g.target(a) < t) {
  2205             if (_right[a] == INVALID) {
  2206               const_cast<DynArcLookUp&>(*this).splay(a);
  2207               return r;
  2208             } else {
  2209               a = _right[a];
  2210             }
  2211           } else {
  2212             if (_g.target(a) == t) {
  2213               r = a;
  2214             }
  2215             if (_left[a] == INVALID) {
  2216               const_cast<DynArcLookUp&>(*this).splay(a);
  2217               return r;
  2218             } else {
  2219               a = _left[a];
  2220             }
  2221           }
  2222         }
  2223       } else {
  2224         Arc a = p;
  2225         if (_right[a] != INVALID) {
  2226           a = _right[a];
  2227           while (_left[a] != INVALID) {
  2228             a = _left[a];
  2229           }
  2230           const_cast<DynArcLookUp&>(*this).splay(a);
  2231         } else {
  2232           while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
  2233             a = _parent[a];
  2234           }
  2235           if (_parent[a] == INVALID) {
  2236             return INVALID;
  2237           } else {
  2238             a = _parent[a];
  2239             const_cast<DynArcLookUp&>(*this).splay(a);
  2240           }
  2241         }
  2242         if (_g.target(a) == t) return a;
  2243         else return INVALID;
  2244       }
  2245     }
  2246 
  2247   };
  2248 
  2249   ///Fast arc look-up between given endpoints.
  2250 
  2251   ///Using this class, you can find an arc in a digraph from a given
  2252   ///source to a given target in time <em>O</em>(log<em>d</em>),
  2253   ///where <em>d</em> is the out-degree of the source node.
  2254   ///
  2255   ///It is not possible to find \e all parallel arcs between two nodes.
  2256   ///Use \ref AllArcLookUp for this purpose.
  2257   ///
  2258   ///\warning This class is static, so you should call refresh() (or at
  2259   ///least refresh(Node)) to refresh this data structure whenever the
  2260   ///digraph changes. This is a time consuming (superlinearly proportional
  2261   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  2262   ///
  2263   ///\tparam GR The type of the underlying digraph.
  2264   ///
  2265   ///\sa DynArcLookUp
  2266   ///\sa AllArcLookUp
  2267   template<class GR>
  2268   class ArcLookUp
  2269   {
  2270     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  2271 
  2272   public:
  2273 
  2274     /// The Digraph type
  2275     typedef GR Digraph;
  2276 
  2277   protected:
  2278     const Digraph &_g;
  2279     typename Digraph::template NodeMap<Arc> _head;
  2280     typename Digraph::template ArcMap<Arc> _left;
  2281     typename Digraph::template ArcMap<Arc> _right;
  2282 
  2283     class ArcLess {
  2284       const Digraph &g;
  2285     public:
  2286       ArcLess(const Digraph &_g) : g(_g) {}
  2287       bool operator()(Arc a,Arc b) const
  2288       {
  2289         return g.target(a)<g.target(b);
  2290       }
  2291     };
  2292 
  2293   public:
  2294 
  2295     ///Constructor
  2296 
  2297     ///Constructor.
  2298     ///
  2299     ///It builds up the search database, which remains valid until the digraph
  2300     ///changes.
  2301     ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
  2302 
  2303   private:
  2304     Arc refreshRec(std::vector<Arc> &v,int a,int b)
  2305     {
  2306       int m=(a+b)/2;
  2307       Arc me=v[m];
  2308       _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
  2309       _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
  2310       return me;
  2311     }
  2312   public:
  2313     ///Refresh the search data structure at a node.
  2314 
  2315     ///Build up the search database of node \c n.
  2316     ///
  2317     ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
  2318     ///is the number of the outgoing arcs of \c n.
  2319     void refresh(Node n)
  2320     {
  2321       std::vector<Arc> v;
  2322       for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  2323       if(v.size()) {
  2324         std::sort(v.begin(),v.end(),ArcLess(_g));
  2325         _head[n]=refreshRec(v,0,v.size()-1);
  2326       }
  2327       else _head[n]=INVALID;
  2328     }
  2329     ///Refresh the full data structure.
  2330 
  2331     ///Build up the full search database. In fact, it simply calls
  2332     ///\ref refresh(Node) "refresh(n)" for each node \c n.
  2333     ///
  2334     ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
  2335     ///the number of the arcs in the digraph and <em>D</em> is the maximum
  2336     ///out-degree of the digraph.
  2337     void refresh()
  2338     {
  2339       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
  2340     }
  2341 
  2342     ///Find an arc between two nodes.
  2343 
  2344     ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
  2345     ///where <em>d</em> is the number of outgoing arcs of \c s.
  2346     ///\param s The source node.
  2347     ///\param t The target node.
  2348     ///\return An arc from \c s to \c t if there exists,
  2349     ///\ref INVALID otherwise.
  2350     ///
  2351     ///\warning If you change the digraph, refresh() must be called before using
  2352     ///this operator. If you change the outgoing arcs of
  2353     ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
  2354     Arc operator()(Node s, Node t) const
  2355     {
  2356       Arc e;
  2357       for(e=_head[s];
  2358           e!=INVALID&&_g.target(e)!=t;
  2359           e = t < _g.target(e)?_left[e]:_right[e]) ;
  2360       return e;
  2361     }
  2362 
  2363   };
  2364 
  2365   ///Fast look-up of all arcs between given endpoints.
  2366 
  2367   ///This class is the same as \ref ArcLookUp, with the addition
  2368   ///that it makes it possible to find all parallel arcs between given
  2369   ///endpoints.
  2370   ///
  2371   ///\warning This class is static, so you should call refresh() (or at
  2372   ///least refresh(Node)) to refresh this data structure whenever the
  2373   ///digraph changes. This is a time consuming (superlinearly proportional
  2374   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  2375   ///
  2376   ///\tparam GR The type of the underlying digraph.
  2377   ///
  2378   ///\sa DynArcLookUp
  2379   ///\sa ArcLookUp
  2380   template<class GR>
  2381   class AllArcLookUp : public ArcLookUp<GR>
  2382   {
  2383     using ArcLookUp<GR>::_g;
  2384     using ArcLookUp<GR>::_right;
  2385     using ArcLookUp<GR>::_left;
  2386     using ArcLookUp<GR>::_head;
  2387 
  2388     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  2389 
  2390     typename GR::template ArcMap<Arc> _next;
  2391 
  2392     Arc refreshNext(Arc head,Arc next=INVALID)
  2393     {
  2394       if(head==INVALID) return next;
  2395       else {
  2396         next=refreshNext(_right[head],next);
  2397         _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
  2398           ? next : INVALID;
  2399         return refreshNext(_left[head],head);
  2400       }
  2401     }
  2402 
  2403     void refreshNext()
  2404     {
  2405       for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
  2406     }
  2407 
  2408   public:
  2409 
  2410     /// The Digraph type
  2411     typedef GR Digraph;
  2412 
  2413     ///Constructor
  2414 
  2415     ///Constructor.
  2416     ///
  2417     ///It builds up the search database, which remains valid until the digraph
  2418     ///changes.
  2419     AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
  2420 
  2421     ///Refresh the data structure at a node.
  2422 
  2423     ///Build up the search database of node \c n.
  2424     ///
  2425     ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
  2426     ///the number of the outgoing arcs of \c n.
  2427     void refresh(Node n)
  2428     {
  2429       ArcLookUp<GR>::refresh(n);
  2430       refreshNext(_head[n]);
  2431     }
  2432 
  2433     ///Refresh the full data structure.
  2434 
  2435     ///Build up the full search database. In fact, it simply calls
  2436     ///\ref refresh(Node) "refresh(n)" for each node \c n.
  2437     ///
  2438     ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
  2439     ///the number of the arcs in the digraph and <em>D</em> is the maximum
  2440     ///out-degree of the digraph.
  2441     void refresh()
  2442     {
  2443       for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
  2444     }
  2445 
  2446     ///Find an arc between two nodes.
  2447 
  2448     ///Find an arc between two nodes.
  2449     ///\param s The source node.
  2450     ///\param t The target node.
  2451     ///\param prev The previous arc between \c s and \c t. It it is INVALID or
  2452     ///not given, the operator finds the first appropriate arc.
  2453     ///\return An arc from \c s to \c t after \c prev or
  2454     ///\ref INVALID if there is no more.
  2455     ///
  2456     ///For example, you can count the number of arcs from \c u to \c v in the
  2457     ///following way.
  2458     ///\code
  2459     ///AllArcLookUp<ListDigraph> ae(g);
  2460     ///...
  2461     ///int n = 0;
  2462     ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
  2463     ///\endcode
  2464     ///
  2465     ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
  2466     ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
  2467     ///consecutive arcs are found in constant time.
  2468     ///
  2469     ///\warning If you change the digraph, refresh() must be called before using
  2470     ///this operator. If you change the outgoing arcs of
  2471     ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
  2472     ///
  2473     Arc operator()(Node s, Node t, Arc prev=INVALID) const
  2474     {
  2475       if(prev==INVALID)
  2476         {
  2477           Arc f=INVALID;
  2478           Arc e;
  2479           for(e=_head[s];
  2480               e!=INVALID&&_g.target(e)!=t;
  2481               e = t < _g.target(e)?_left[e]:_right[e]) ;
  2482           while(e!=INVALID)
  2483             if(_g.target(e)==t)
  2484               {
  2485                 f = e;
  2486                 e = _left[e];
  2487               }
  2488             else e = _right[e];
  2489           return f;
  2490         }
  2491       else return _next[prev];
  2492     }
  2493 
  2494   };
  2495 
  2496   /// @}
  2497 
  2498 } //namespace lemon
  2499 
  2500 #endif