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