lemon/core.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 23 Feb 2009 11:30:15 +0000
changeset 523 d9e43511d11c
parent 429 b0f74ca2e3ac
child 535 6a17a722b50e
permissions -rw-r--r--
Port lgf-gen from SVN -r3512 (#45)

- apply the migrate script
- apply the source unifyer
- fix the compilation
     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-2009
     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/bits/enable_if.h>
    26 #include <lemon/bits/traits.h>
    27 #include <lemon/assert.h>
    28 
    29 ///\file
    30 ///\brief LEMON core utilities.
    31 ///
    32 ///This header file contains core utilities for LEMON.
    33 ///It is automatically included by all graph types, therefore it usually
    34 ///do not have to be included directly.
    35 
    36 namespace lemon {
    37 
    38   /// \brief Dummy type to make it easier to create invalid iterators.
    39   ///
    40   /// Dummy type to make it easier to create invalid iterators.
    41   /// See \ref INVALID for the usage.
    42   struct Invalid {
    43   public:
    44     bool operator==(Invalid) { return true;  }
    45     bool operator!=(Invalid) { return false; }
    46     bool operator< (Invalid) { return false; }
    47   };
    48 
    49   /// \brief Invalid iterators.
    50   ///
    51   /// \ref Invalid is a global type that converts to each iterator
    52   /// in such a way that the value of the target iterator will be invalid.
    53 #ifdef LEMON_ONLY_TEMPLATES
    54   const Invalid INVALID = Invalid();
    55 #else
    56   extern const Invalid INVALID;
    57 #endif
    58 
    59   /// \addtogroup gutils
    60   /// @{
    61 
    62   ///Create convenience typedefs for the digraph types and iterators
    63 
    64   ///This \c \#define creates convenient type definitions for the following
    65   ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    66   ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
    67   ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
    68   ///
    69   ///\note If the graph type is a dependent type, ie. the graph type depend
    70   ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
    71   ///macro.
    72 #define DIGRAPH_TYPEDEFS(Digraph)                                       \
    73   typedef Digraph::Node Node;                                           \
    74   typedef Digraph::NodeIt NodeIt;                                       \
    75   typedef Digraph::Arc Arc;                                             \
    76   typedef Digraph::ArcIt ArcIt;                                         \
    77   typedef Digraph::InArcIt InArcIt;                                     \
    78   typedef Digraph::OutArcIt OutArcIt;                                   \
    79   typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
    80   typedef Digraph::NodeMap<int> IntNodeMap;                             \
    81   typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
    82   typedef Digraph::ArcMap<bool> BoolArcMap;                             \
    83   typedef Digraph::ArcMap<int> IntArcMap;                               \
    84   typedef Digraph::ArcMap<double> DoubleArcMap
    85 
    86   ///Create convenience typedefs for the digraph types and iterators
    87 
    88   ///\see DIGRAPH_TYPEDEFS
    89   ///
    90   ///\note Use this macro, if the graph type is a dependent type,
    91   ///ie. the graph type depend on a template parameter.
    92 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
    93   typedef typename Digraph::Node Node;                                  \
    94   typedef typename Digraph::NodeIt NodeIt;                              \
    95   typedef typename Digraph::Arc Arc;                                    \
    96   typedef typename Digraph::ArcIt ArcIt;                                \
    97   typedef typename Digraph::InArcIt InArcIt;                            \
    98   typedef typename Digraph::OutArcIt OutArcIt;                          \
    99   typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
   100   typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
   101   typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
   102   typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
   103   typedef typename Digraph::template ArcMap<int> IntArcMap;             \
   104   typedef typename Digraph::template ArcMap<double> DoubleArcMap
   105 
   106   ///Create convenience typedefs for the graph types and iterators
   107 
   108   ///This \c \#define creates the same convenient type definitions as defined
   109   ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
   110   ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
   111   ///\c DoubleEdgeMap.
   112   ///
   113   ///\note If the graph type is a dependent type, ie. the graph type depend
   114   ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
   115   ///macro.
   116 #define GRAPH_TYPEDEFS(Graph)                                           \
   117   DIGRAPH_TYPEDEFS(Graph);                                              \
   118   typedef Graph::Edge Edge;                                             \
   119   typedef Graph::EdgeIt EdgeIt;                                         \
   120   typedef Graph::IncEdgeIt IncEdgeIt;                                   \
   121   typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
   122   typedef Graph::EdgeMap<int> IntEdgeMap;                               \
   123   typedef Graph::EdgeMap<double> DoubleEdgeMap
   124 
   125   ///Create convenience typedefs for the graph types and iterators
   126 
   127   ///\see GRAPH_TYPEDEFS
   128   ///
   129   ///\note Use this macro, if the graph type is a dependent type,
   130   ///ie. the graph type depend on a template parameter.
   131 #define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
   132   TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
   133   typedef typename Graph::Edge Edge;                                    \
   134   typedef typename Graph::EdgeIt EdgeIt;                                \
   135   typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
   136   typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
   137   typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
   138   typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
   139 
   140   /// \brief Function to count the items in a graph.
   141   ///
   142   /// This function counts the items (nodes, arcs etc.) in a graph.
   143   /// The complexity of the function is linear because
   144   /// it iterates on all of the items.
   145   template <typename Graph, typename Item>
   146   inline int countItems(const Graph& g) {
   147     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
   148     int num = 0;
   149     for (ItemIt it(g); it != INVALID; ++it) {
   150       ++num;
   151     }
   152     return num;
   153   }
   154 
   155   // Node counting:
   156 
   157   namespace _core_bits {
   158 
   159     template <typename Graph, typename Enable = void>
   160     struct CountNodesSelector {
   161       static int count(const Graph &g) {
   162         return countItems<Graph, typename Graph::Node>(g);
   163       }
   164     };
   165 
   166     template <typename Graph>
   167     struct CountNodesSelector<
   168       Graph, typename
   169       enable_if<typename Graph::NodeNumTag, void>::type>
   170     {
   171       static int count(const Graph &g) {
   172         return g.nodeNum();
   173       }
   174     };
   175   }
   176 
   177   /// \brief Function to count the nodes in the graph.
   178   ///
   179   /// This function counts the nodes in the graph.
   180   /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
   181   /// graph structures it is specialized to run in <em>O</em>(1).
   182   ///
   183   /// \note If the graph contains a \c nodeNum() member function and a
   184   /// \c NodeNumTag tag then this function calls directly the member
   185   /// function to query the cardinality of the node set.
   186   template <typename Graph>
   187   inline int countNodes(const Graph& g) {
   188     return _core_bits::CountNodesSelector<Graph>::count(g);
   189   }
   190 
   191   // Arc counting:
   192 
   193   namespace _core_bits {
   194 
   195     template <typename Graph, typename Enable = void>
   196     struct CountArcsSelector {
   197       static int count(const Graph &g) {
   198         return countItems<Graph, typename Graph::Arc>(g);
   199       }
   200     };
   201 
   202     template <typename Graph>
   203     struct CountArcsSelector<
   204       Graph,
   205       typename enable_if<typename Graph::ArcNumTag, void>::type>
   206     {
   207       static int count(const Graph &g) {
   208         return g.arcNum();
   209       }
   210     };
   211   }
   212 
   213   /// \brief Function to count the arcs in the graph.
   214   ///
   215   /// This function counts the arcs in the graph.
   216   /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
   217   /// graph structures it is specialized to run in <em>O</em>(1).
   218   ///
   219   /// \note If the graph contains a \c arcNum() member function and a
   220   /// \c ArcNumTag tag then this function calls directly the member
   221   /// function to query the cardinality of the arc set.
   222   template <typename Graph>
   223   inline int countArcs(const Graph& g) {
   224     return _core_bits::CountArcsSelector<Graph>::count(g);
   225   }
   226 
   227   // Edge counting:
   228 
   229   namespace _core_bits {
   230 
   231     template <typename Graph, typename Enable = void>
   232     struct CountEdgesSelector {
   233       static int count(const Graph &g) {
   234         return countItems<Graph, typename Graph::Edge>(g);
   235       }
   236     };
   237 
   238     template <typename Graph>
   239     struct CountEdgesSelector<
   240       Graph,
   241       typename enable_if<typename Graph::EdgeNumTag, void>::type>
   242     {
   243       static int count(const Graph &g) {
   244         return g.edgeNum();
   245       }
   246     };
   247   }
   248 
   249   /// \brief Function to count the edges in the graph.
   250   ///
   251   /// This function counts the edges in the graph.
   252   /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
   253   /// graph structures it is specialized to run in <em>O</em>(1).
   254   ///
   255   /// \note If the graph contains a \c edgeNum() member function and a
   256   /// \c EdgeNumTag tag then this function calls directly the member
   257   /// function to query the cardinality of the edge set.
   258   template <typename Graph>
   259   inline int countEdges(const Graph& g) {
   260     return _core_bits::CountEdgesSelector<Graph>::count(g);
   261 
   262   }
   263 
   264 
   265   template <typename Graph, typename DegIt>
   266   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   267     int num = 0;
   268     for (DegIt it(_g, _n); it != INVALID; ++it) {
   269       ++num;
   270     }
   271     return num;
   272   }
   273 
   274   /// \brief Function to count the number of the out-arcs from node \c n.
   275   ///
   276   /// This function counts the number of the out-arcs from node \c n
   277   /// in the graph \c g.
   278   template <typename Graph>
   279   inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) {
   280     return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
   281   }
   282 
   283   /// \brief Function to count the number of the in-arcs to node \c n.
   284   ///
   285   /// This function counts the number of the in-arcs to node \c n
   286   /// in the graph \c g.
   287   template <typename Graph>
   288   inline int countInArcs(const Graph& g,  const typename Graph::Node& n) {
   289     return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
   290   }
   291 
   292   /// \brief Function to count the number of the inc-edges to node \c n.
   293   ///
   294   /// This function counts the number of the inc-edges to node \c n
   295   /// in the undirected graph \c g.
   296   template <typename Graph>
   297   inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) {
   298     return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
   299   }
   300 
   301   namespace _core_bits {
   302 
   303     template <typename Digraph, typename Item, typename RefMap>
   304     class MapCopyBase {
   305     public:
   306       virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
   307 
   308       virtual ~MapCopyBase() {}
   309     };
   310 
   311     template <typename Digraph, typename Item, typename RefMap,
   312               typename FromMap, typename ToMap>
   313     class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
   314     public:
   315 
   316       MapCopy(const FromMap& map, ToMap& tmap)
   317         : _map(map), _tmap(tmap) {}
   318 
   319       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   320         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   321         for (ItemIt it(digraph); it != INVALID; ++it) {
   322           _tmap.set(refMap[it], _map[it]);
   323         }
   324       }
   325 
   326     private:
   327       const FromMap& _map;
   328       ToMap& _tmap;
   329     };
   330 
   331     template <typename Digraph, typename Item, typename RefMap, typename It>
   332     class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
   333     public:
   334 
   335       ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
   336 
   337       virtual void copy(const Digraph&, const RefMap& refMap) {
   338         _it = refMap[_item];
   339       }
   340 
   341     private:
   342       Item _item;
   343       It& _it;
   344     };
   345 
   346     template <typename Digraph, typename Item, typename RefMap, typename Ref>
   347     class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   348     public:
   349 
   350       RefCopy(Ref& map) : _map(map) {}
   351 
   352       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   353         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   354         for (ItemIt it(digraph); it != INVALID; ++it) {
   355           _map.set(it, refMap[it]);
   356         }
   357       }
   358 
   359     private:
   360       Ref& _map;
   361     };
   362 
   363     template <typename Digraph, typename Item, typename RefMap,
   364               typename CrossRef>
   365     class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   366     public:
   367 
   368       CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
   369 
   370       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   371         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   372         for (ItemIt it(digraph); it != INVALID; ++it) {
   373           _cmap.set(refMap[it], it);
   374         }
   375       }
   376 
   377     private:
   378       CrossRef& _cmap;
   379     };
   380 
   381     template <typename Digraph, typename Enable = void>
   382     struct DigraphCopySelector {
   383       template <typename From, typename NodeRefMap, typename ArcRefMap>
   384       static void copy(const From& from, Digraph &to,
   385                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   386         for (typename From::NodeIt it(from); it != INVALID; ++it) {
   387           nodeRefMap[it] = to.addNode();
   388         }
   389         for (typename From::ArcIt it(from); it != INVALID; ++it) {
   390           arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
   391                                     nodeRefMap[from.target(it)]);
   392         }
   393       }
   394     };
   395 
   396     template <typename Digraph>
   397     struct DigraphCopySelector<
   398       Digraph,
   399       typename enable_if<typename Digraph::BuildTag, void>::type>
   400     {
   401       template <typename From, typename NodeRefMap, typename ArcRefMap>
   402       static void copy(const From& from, Digraph &to,
   403                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   404         to.build(from, nodeRefMap, arcRefMap);
   405       }
   406     };
   407 
   408     template <typename Graph, typename Enable = void>
   409     struct GraphCopySelector {
   410       template <typename From, typename NodeRefMap, typename EdgeRefMap>
   411       static void copy(const From& from, Graph &to,
   412                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   413         for (typename From::NodeIt it(from); it != INVALID; ++it) {
   414           nodeRefMap[it] = to.addNode();
   415         }
   416         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
   417           edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
   418                                       nodeRefMap[from.v(it)]);
   419         }
   420       }
   421     };
   422 
   423     template <typename Graph>
   424     struct GraphCopySelector<
   425       Graph,
   426       typename enable_if<typename Graph::BuildTag, void>::type>
   427     {
   428       template <typename From, typename NodeRefMap, typename EdgeRefMap>
   429       static void copy(const From& from, Graph &to,
   430                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   431         to.build(from, nodeRefMap, edgeRefMap);
   432       }
   433     };
   434 
   435   }
   436 
   437   /// \brief Class to copy a digraph.
   438   ///
   439   /// Class to copy a digraph to another digraph (duplicate a digraph). The
   440   /// simplest way of using it is through the \c digraphCopy() function.
   441   ///
   442   /// This class not only make a copy of a digraph, but it can create
   443   /// references and cross references between the nodes and arcs of
   444   /// the two digraphs, and it can copy maps to use with the newly created
   445   /// digraph.
   446   ///
   447   /// To make a copy from a digraph, first an instance of DigraphCopy
   448   /// should be created, then the data belongs to the digraph should
   449   /// assigned to copy. In the end, the \c run() member should be
   450   /// called.
   451   ///
   452   /// The next code copies a digraph with several data:
   453   ///\code
   454   ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
   455   ///  // Create references for the nodes
   456   ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   457   ///  cg.nodeRef(nr);
   458   ///  // Create cross references (inverse) for the arcs
   459   ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
   460   ///  cg.arcCrossRef(acr);
   461   ///  // Copy an arc map
   462   ///  OrigGraph::ArcMap<double> oamap(orig_graph);
   463   ///  NewGraph::ArcMap<double> namap(new_graph);
   464   ///  cg.arcMap(oamap, namap);
   465   ///  // Copy a node
   466   ///  OrigGraph::Node on;
   467   ///  NewGraph::Node nn;
   468   ///  cg.node(on, nn);
   469   ///  // Execute copying
   470   ///  cg.run();
   471   ///\endcode
   472   template <typename From, typename To>
   473   class DigraphCopy {
   474   private:
   475 
   476     typedef typename From::Node Node;
   477     typedef typename From::NodeIt NodeIt;
   478     typedef typename From::Arc Arc;
   479     typedef typename From::ArcIt ArcIt;
   480 
   481     typedef typename To::Node TNode;
   482     typedef typename To::Arc TArc;
   483 
   484     typedef typename From::template NodeMap<TNode> NodeRefMap;
   485     typedef typename From::template ArcMap<TArc> ArcRefMap;
   486 
   487   public:
   488 
   489     /// \brief Constructor of DigraphCopy.
   490     ///
   491     /// Constructor of DigraphCopy for copying the content of the
   492     /// \c from digraph into the \c to digraph.
   493     DigraphCopy(const From& from, To& to)
   494       : _from(from), _to(to) {}
   495 
   496     /// \brief Destructor of DigraphCopy
   497     ///
   498     /// Destructor of DigraphCopy.
   499     ~DigraphCopy() {
   500       for (int i = 0; i < int(_node_maps.size()); ++i) {
   501         delete _node_maps[i];
   502       }
   503       for (int i = 0; i < int(_arc_maps.size()); ++i) {
   504         delete _arc_maps[i];
   505       }
   506 
   507     }
   508 
   509     /// \brief Copy the node references into the given map.
   510     ///
   511     /// This function copies the node references into the given map.
   512     /// The parameter should be a map, whose key type is the Node type of
   513     /// the source digraph, while the value type is the Node type of the
   514     /// destination digraph.
   515     template <typename NodeRef>
   516     DigraphCopy& nodeRef(NodeRef& map) {
   517       _node_maps.push_back(new _core_bits::RefCopy<From, Node,
   518                            NodeRefMap, NodeRef>(map));
   519       return *this;
   520     }
   521 
   522     /// \brief Copy the node cross references into the given map.
   523     ///
   524     /// This function copies the node cross references (reverse references)
   525     /// into the given map. The parameter should be a map, whose key type
   526     /// is the Node type of the destination digraph, while the value type is
   527     /// the Node type of the source digraph.
   528     template <typename NodeCrossRef>
   529     DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
   530       _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
   531                            NodeRefMap, NodeCrossRef>(map));
   532       return *this;
   533     }
   534 
   535     /// \brief Make a copy of the given node map.
   536     ///
   537     /// This function makes a copy of the given node map for the newly
   538     /// created digraph.
   539     /// The key type of the new map \c tmap should be the Node type of the
   540     /// destination digraph, and the key type of the original map \c map
   541     /// should be the Node type of the source digraph.
   542     template <typename FromMap, typename ToMap>
   543     DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
   544       _node_maps.push_back(new _core_bits::MapCopy<From, Node,
   545                            NodeRefMap, FromMap, ToMap>(map, tmap));
   546       return *this;
   547     }
   548 
   549     /// \brief Make a copy of the given node.
   550     ///
   551     /// This function makes a copy of the given node.
   552     DigraphCopy& node(const Node& node, TNode& tnode) {
   553       _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
   554                            NodeRefMap, TNode>(node, tnode));
   555       return *this;
   556     }
   557 
   558     /// \brief Copy the arc references into the given map.
   559     ///
   560     /// This function copies the arc references into the given map.
   561     /// The parameter should be a map, whose key type is the Arc type of
   562     /// the source digraph, while the value type is the Arc type of the
   563     /// destination digraph.
   564     template <typename ArcRef>
   565     DigraphCopy& arcRef(ArcRef& map) {
   566       _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
   567                           ArcRefMap, ArcRef>(map));
   568       return *this;
   569     }
   570 
   571     /// \brief Copy the arc cross references into the given map.
   572     ///
   573     /// This function copies the arc cross references (reverse references)
   574     /// into the given map. The parameter should be a map, whose key type
   575     /// is the Arc type of the destination digraph, while the value type is
   576     /// the Arc type of the source digraph.
   577     template <typename ArcCrossRef>
   578     DigraphCopy& arcCrossRef(ArcCrossRef& map) {
   579       _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
   580                           ArcRefMap, ArcCrossRef>(map));
   581       return *this;
   582     }
   583 
   584     /// \brief Make a copy of the given arc map.
   585     ///
   586     /// This function makes a copy of the given arc map for the newly
   587     /// created digraph.
   588     /// The key type of the new map \c tmap should be the Arc type of the
   589     /// destination digraph, and the key type of the original map \c map
   590     /// should be the Arc type of the source digraph.
   591     template <typename FromMap, typename ToMap>
   592     DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
   593       _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
   594                           ArcRefMap, FromMap, ToMap>(map, tmap));
   595       return *this;
   596     }
   597 
   598     /// \brief Make a copy of the given arc.
   599     ///
   600     /// This function makes a copy of the given arc.
   601     DigraphCopy& arc(const Arc& arc, TArc& tarc) {
   602       _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
   603                           ArcRefMap, TArc>(arc, tarc));
   604       return *this;
   605     }
   606 
   607     /// \brief Execute copying.
   608     ///
   609     /// This function executes the copying of the digraph along with the
   610     /// copying of the assigned data.
   611     void run() {
   612       NodeRefMap nodeRefMap(_from);
   613       ArcRefMap arcRefMap(_from);
   614       _core_bits::DigraphCopySelector<To>::
   615         copy(_from, _to, nodeRefMap, arcRefMap);
   616       for (int i = 0; i < int(_node_maps.size()); ++i) {
   617         _node_maps[i]->copy(_from, nodeRefMap);
   618       }
   619       for (int i = 0; i < int(_arc_maps.size()); ++i) {
   620         _arc_maps[i]->copy(_from, arcRefMap);
   621       }
   622     }
   623 
   624   protected:
   625 
   626     const From& _from;
   627     To& _to;
   628 
   629     std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
   630       _node_maps;
   631 
   632     std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
   633       _arc_maps;
   634 
   635   };
   636 
   637   /// \brief Copy a digraph to another digraph.
   638   ///
   639   /// This function copies a digraph to another digraph.
   640   /// The complete usage of it is detailed in the DigraphCopy class, but
   641   /// a short example shows a basic work:
   642   ///\code
   643   /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
   644   ///\endcode
   645   ///
   646   /// After the copy the \c nr map will contain the mapping from the
   647   /// nodes of the \c from digraph to the nodes of the \c to digraph and
   648   /// \c acr will contain the mapping from the arcs of the \c to digraph
   649   /// to the arcs of the \c from digraph.
   650   ///
   651   /// \see DigraphCopy
   652   template <typename From, typename To>
   653   DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
   654     return DigraphCopy<From, To>(from, to);
   655   }
   656 
   657   /// \brief Class to copy a graph.
   658   ///
   659   /// Class to copy a graph to another graph (duplicate a graph). The
   660   /// simplest way of using it is through the \c graphCopy() function.
   661   ///
   662   /// This class not only make a copy of a graph, but it can create
   663   /// references and cross references between the nodes, edges and arcs of
   664   /// the two graphs, and it can copy maps for using with the newly created
   665   /// graph.
   666   ///
   667   /// To make a copy from a graph, first an instance of GraphCopy
   668   /// should be created, then the data belongs to the graph should
   669   /// assigned to copy. In the end, the \c run() member should be
   670   /// called.
   671   ///
   672   /// The next code copies a graph with several data:
   673   ///\code
   674   ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
   675   ///  // Create references for the nodes
   676   ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
   677   ///  cg.nodeRef(nr);
   678   ///  // Create cross references (inverse) for the edges
   679   ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
   680   ///  cg.edgeCrossRef(ecr);
   681   ///  // Copy an edge map
   682   ///  OrigGraph::EdgeMap<double> oemap(orig_graph);
   683   ///  NewGraph::EdgeMap<double> nemap(new_graph);
   684   ///  cg.edgeMap(oemap, nemap);
   685   ///  // Copy a node
   686   ///  OrigGraph::Node on;
   687   ///  NewGraph::Node nn;
   688   ///  cg.node(on, nn);
   689   ///  // Execute copying
   690   ///  cg.run();
   691   ///\endcode
   692   template <typename From, typename To>
   693   class GraphCopy {
   694   private:
   695 
   696     typedef typename From::Node Node;
   697     typedef typename From::NodeIt NodeIt;
   698     typedef typename From::Arc Arc;
   699     typedef typename From::ArcIt ArcIt;
   700     typedef typename From::Edge Edge;
   701     typedef typename From::EdgeIt EdgeIt;
   702 
   703     typedef typename To::Node TNode;
   704     typedef typename To::Arc TArc;
   705     typedef typename To::Edge TEdge;
   706 
   707     typedef typename From::template NodeMap<TNode> NodeRefMap;
   708     typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
   709 
   710     struct ArcRefMap {
   711       ArcRefMap(const From& from, const To& to,
   712                 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
   713         : _from(from), _to(to),
   714           _edge_ref(edge_ref), _node_ref(node_ref) {}
   715 
   716       typedef typename From::Arc Key;
   717       typedef typename To::Arc Value;
   718 
   719       Value operator[](const Key& key) const {
   720         bool forward = _from.u(key) != _from.v(key) ?
   721           _node_ref[_from.source(key)] ==
   722           _to.source(_to.direct(_edge_ref[key], true)) :
   723           _from.direction(key);
   724         return _to.direct(_edge_ref[key], forward);
   725       }
   726 
   727       const From& _from;
   728       const To& _to;
   729       const EdgeRefMap& _edge_ref;
   730       const NodeRefMap& _node_ref;
   731     };
   732 
   733   public:
   734 
   735     /// \brief Constructor of GraphCopy.
   736     ///
   737     /// Constructor of GraphCopy for copying the content of the
   738     /// \c from graph into the \c to graph.
   739     GraphCopy(const From& from, To& to)
   740       : _from(from), _to(to) {}
   741 
   742     /// \brief Destructor of GraphCopy
   743     ///
   744     /// Destructor of GraphCopy.
   745     ~GraphCopy() {
   746       for (int i = 0; i < int(_node_maps.size()); ++i) {
   747         delete _node_maps[i];
   748       }
   749       for (int i = 0; i < int(_arc_maps.size()); ++i) {
   750         delete _arc_maps[i];
   751       }
   752       for (int i = 0; i < int(_edge_maps.size()); ++i) {
   753         delete _edge_maps[i];
   754       }
   755     }
   756 
   757     /// \brief Copy the node references into the given map.
   758     ///
   759     /// This function copies the node references into the given map.
   760     /// The parameter should be a map, whose key type is the Node type of
   761     /// the source graph, while the value type is the Node type of the
   762     /// destination graph.
   763     template <typename NodeRef>
   764     GraphCopy& nodeRef(NodeRef& map) {
   765       _node_maps.push_back(new _core_bits::RefCopy<From, Node,
   766                            NodeRefMap, NodeRef>(map));
   767       return *this;
   768     }
   769 
   770     /// \brief Copy the node cross references into the given map.
   771     ///
   772     /// This function copies the node cross references (reverse references)
   773     /// into the given map. The parameter should be a map, whose key type
   774     /// is the Node type of the destination graph, while the value type is
   775     /// the Node type of the source graph.
   776     template <typename NodeCrossRef>
   777     GraphCopy& nodeCrossRef(NodeCrossRef& map) {
   778       _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
   779                            NodeRefMap, NodeCrossRef>(map));
   780       return *this;
   781     }
   782 
   783     /// \brief Make a copy of the given node map.
   784     ///
   785     /// This function makes a copy of the given node map for the newly
   786     /// created graph.
   787     /// The key type of the new map \c tmap should be the Node type of the
   788     /// destination graph, and the key type of the original map \c map
   789     /// should be the Node type of the source graph.
   790     template <typename FromMap, typename ToMap>
   791     GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
   792       _node_maps.push_back(new _core_bits::MapCopy<From, Node,
   793                            NodeRefMap, FromMap, ToMap>(map, tmap));
   794       return *this;
   795     }
   796 
   797     /// \brief Make a copy of the given node.
   798     ///
   799     /// This function makes a copy of the given node.
   800     GraphCopy& node(const Node& node, TNode& tnode) {
   801       _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
   802                            NodeRefMap, TNode>(node, tnode));
   803       return *this;
   804     }
   805 
   806     /// \brief Copy the arc references into the given map.
   807     ///
   808     /// This function copies the arc references into the given map.
   809     /// The parameter should be a map, whose key type is the Arc type of
   810     /// the source graph, while the value type is the Arc type of the
   811     /// destination graph.
   812     template <typename ArcRef>
   813     GraphCopy& arcRef(ArcRef& map) {
   814       _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
   815                           ArcRefMap, ArcRef>(map));
   816       return *this;
   817     }
   818 
   819     /// \brief Copy the arc cross references into the given map.
   820     ///
   821     /// This function copies the arc cross references (reverse references)
   822     /// into the given map. The parameter should be a map, whose key type
   823     /// is the Arc type of the destination graph, while the value type is
   824     /// the Arc type of the source graph.
   825     template <typename ArcCrossRef>
   826     GraphCopy& arcCrossRef(ArcCrossRef& map) {
   827       _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
   828                           ArcRefMap, ArcCrossRef>(map));
   829       return *this;
   830     }
   831 
   832     /// \brief Make a copy of the given arc map.
   833     ///
   834     /// This function makes a copy of the given arc map for the newly
   835     /// created graph.
   836     /// The key type of the new map \c tmap should be the Arc type of the
   837     /// destination graph, and the key type of the original map \c map
   838     /// should be the Arc type of the source graph.
   839     template <typename FromMap, typename ToMap>
   840     GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
   841       _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
   842                           ArcRefMap, FromMap, ToMap>(map, tmap));
   843       return *this;
   844     }
   845 
   846     /// \brief Make a copy of the given arc.
   847     ///
   848     /// This function makes a copy of the given arc.
   849     GraphCopy& arc(const Arc& arc, TArc& tarc) {
   850       _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
   851                           ArcRefMap, TArc>(arc, tarc));
   852       return *this;
   853     }
   854 
   855     /// \brief Copy the edge references into the given map.
   856     ///
   857     /// This function copies the edge references into the given map.
   858     /// The parameter should be a map, whose key type is the Edge type of
   859     /// the source graph, while the value type is the Edge type of the
   860     /// destination graph.
   861     template <typename EdgeRef>
   862     GraphCopy& edgeRef(EdgeRef& map) {
   863       _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
   864                            EdgeRefMap, EdgeRef>(map));
   865       return *this;
   866     }
   867 
   868     /// \brief Copy the edge cross references into the given map.
   869     ///
   870     /// This function copies the edge cross references (reverse references)
   871     /// into the given map. The parameter should be a map, whose key type
   872     /// is the Edge type of the destination graph, while the value type is
   873     /// the Edge type of the source graph.
   874     template <typename EdgeCrossRef>
   875     GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
   876       _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
   877                            Edge, EdgeRefMap, EdgeCrossRef>(map));
   878       return *this;
   879     }
   880 
   881     /// \brief Make a copy of the given edge map.
   882     ///
   883     /// This function makes a copy of the given edge map for the newly
   884     /// created graph.
   885     /// The key type of the new map \c tmap should be the Edge type of the
   886     /// destination graph, and the key type of the original map \c map
   887     /// should be the Edge type of the source graph.
   888     template <typename FromMap, typename ToMap>
   889     GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
   890       _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
   891                            EdgeRefMap, FromMap, ToMap>(map, tmap));
   892       return *this;
   893     }
   894 
   895     /// \brief Make a copy of the given edge.
   896     ///
   897     /// This function makes a copy of the given edge.
   898     GraphCopy& edge(const Edge& edge, TEdge& tedge) {
   899       _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
   900                            EdgeRefMap, TEdge>(edge, tedge));
   901       return *this;
   902     }
   903 
   904     /// \brief Execute copying.
   905     ///
   906     /// This function executes the copying of the graph along with the
   907     /// copying of the assigned data.
   908     void run() {
   909       NodeRefMap nodeRefMap(_from);
   910       EdgeRefMap edgeRefMap(_from);
   911       ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
   912       _core_bits::GraphCopySelector<To>::
   913         copy(_from, _to, nodeRefMap, edgeRefMap);
   914       for (int i = 0; i < int(_node_maps.size()); ++i) {
   915         _node_maps[i]->copy(_from, nodeRefMap);
   916       }
   917       for (int i = 0; i < int(_edge_maps.size()); ++i) {
   918         _edge_maps[i]->copy(_from, edgeRefMap);
   919       }
   920       for (int i = 0; i < int(_arc_maps.size()); ++i) {
   921         _arc_maps[i]->copy(_from, arcRefMap);
   922       }
   923     }
   924 
   925   private:
   926 
   927     const From& _from;
   928     To& _to;
   929 
   930     std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
   931       _node_maps;
   932 
   933     std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
   934       _arc_maps;
   935 
   936     std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
   937       _edge_maps;
   938 
   939   };
   940 
   941   /// \brief Copy a graph to another graph.
   942   ///
   943   /// This function copies a graph to another graph.
   944   /// The complete usage of it is detailed in the GraphCopy class,
   945   /// but a short example shows a basic work:
   946   ///\code
   947   /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
   948   ///\endcode
   949   ///
   950   /// After the copy the \c nr map will contain the mapping from the
   951   /// nodes of the \c from graph to the nodes of the \c to graph and
   952   /// \c ecr will contain the mapping from the edges of the \c to graph
   953   /// to the edges of the \c from graph.
   954   ///
   955   /// \see GraphCopy
   956   template <typename From, typename To>
   957   GraphCopy<From, To>
   958   graphCopy(const From& from, To& to) {
   959     return GraphCopy<From, To>(from, to);
   960   }
   961 
   962   namespace _core_bits {
   963 
   964     template <typename Graph, typename Enable = void>
   965     struct FindArcSelector {
   966       typedef typename Graph::Node Node;
   967       typedef typename Graph::Arc Arc;
   968       static Arc find(const Graph &g, Node u, Node v, Arc e) {
   969         if (e == INVALID) {
   970           g.firstOut(e, u);
   971         } else {
   972           g.nextOut(e);
   973         }
   974         while (e != INVALID && g.target(e) != v) {
   975           g.nextOut(e);
   976         }
   977         return e;
   978       }
   979     };
   980 
   981     template <typename Graph>
   982     struct FindArcSelector<
   983       Graph,
   984       typename enable_if<typename Graph::FindArcTag, void>::type>
   985     {
   986       typedef typename Graph::Node Node;
   987       typedef typename Graph::Arc Arc;
   988       static Arc find(const Graph &g, Node u, Node v, Arc prev) {
   989         return g.findArc(u, v, prev);
   990       }
   991     };
   992   }
   993 
   994   /// \brief Find an arc between two nodes of a digraph.
   995   ///
   996   /// This function finds an arc from node \c u to node \c v in the
   997   /// digraph \c g.
   998   ///
   999   /// If \c prev is \ref INVALID (this is the default value), then
  1000   /// it finds the first arc from \c u to \c v. Otherwise it looks for
  1001   /// the next arc from \c u to \c v after \c prev.
  1002   /// \return The found arc or \ref INVALID if there is no such an arc.
  1003   ///
  1004   /// Thus you can iterate through each arc from \c u to \c v as it follows.
  1005   ///\code
  1006   /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
  1007   ///   ...
  1008   /// }
  1009   ///\endcode
  1010   ///
  1011   /// \note \ref ConArcIt provides iterator interface for the same
  1012   /// functionality.
  1013   ///
  1014   ///\sa ConArcIt
  1015   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1016   template <typename Graph>
  1017   inline typename Graph::Arc
  1018   findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
  1019           typename Graph::Arc prev = INVALID) {
  1020     return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
  1021   }
  1022 
  1023   /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
  1024   ///
  1025   /// Iterator for iterating on parallel arcs connecting the same nodes. It is
  1026   /// a higher level interface for the \ref findArc() function. You can
  1027   /// use it the following way:
  1028   ///\code
  1029   /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
  1030   ///   ...
  1031   /// }
  1032   ///\endcode
  1033   ///
  1034   ///\sa findArc()
  1035   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1036   template <typename _Graph>
  1037   class ConArcIt : public _Graph::Arc {
  1038   public:
  1039 
  1040     typedef _Graph Graph;
  1041     typedef typename Graph::Arc Parent;
  1042 
  1043     typedef typename Graph::Arc Arc;
  1044     typedef typename Graph::Node Node;
  1045 
  1046     /// \brief Constructor.
  1047     ///
  1048     /// Construct a new ConArcIt iterating on the arcs that
  1049     /// connects nodes \c u and \c v.
  1050     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
  1051       Parent::operator=(findArc(_graph, u, v));
  1052     }
  1053 
  1054     /// \brief Constructor.
  1055     ///
  1056     /// Construct a new ConArcIt that continues the iterating from arc \c a.
  1057     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
  1058 
  1059     /// \brief Increment operator.
  1060     ///
  1061     /// It increments the iterator and gives back the next arc.
  1062     ConArcIt& operator++() {
  1063       Parent::operator=(findArc(_graph, _graph.source(*this),
  1064                                 _graph.target(*this), *this));
  1065       return *this;
  1066     }
  1067   private:
  1068     const Graph& _graph;
  1069   };
  1070 
  1071   namespace _core_bits {
  1072 
  1073     template <typename Graph, typename Enable = void>
  1074     struct FindEdgeSelector {
  1075       typedef typename Graph::Node Node;
  1076       typedef typename Graph::Edge Edge;
  1077       static Edge find(const Graph &g, Node u, Node v, Edge e) {
  1078         bool b;
  1079         if (u != v) {
  1080           if (e == INVALID) {
  1081             g.firstInc(e, b, u);
  1082           } else {
  1083             b = g.u(e) == u;
  1084             g.nextInc(e, b);
  1085           }
  1086           while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
  1087             g.nextInc(e, b);
  1088           }
  1089         } else {
  1090           if (e == INVALID) {
  1091             g.firstInc(e, b, u);
  1092           } else {
  1093             b = true;
  1094             g.nextInc(e, b);
  1095           }
  1096           while (e != INVALID && (!b || g.v(e) != v)) {
  1097             g.nextInc(e, b);
  1098           }
  1099         }
  1100         return e;
  1101       }
  1102     };
  1103 
  1104     template <typename Graph>
  1105     struct FindEdgeSelector<
  1106       Graph,
  1107       typename enable_if<typename Graph::FindEdgeTag, void>::type>
  1108     {
  1109       typedef typename Graph::Node Node;
  1110       typedef typename Graph::Edge Edge;
  1111       static Edge find(const Graph &g, Node u, Node v, Edge prev) {
  1112         return g.findEdge(u, v, prev);
  1113       }
  1114     };
  1115   }
  1116 
  1117   /// \brief Find an edge between two nodes of a graph.
  1118   ///
  1119   /// This function finds an edge from node \c u to node \c v in graph \c g.
  1120   /// If node \c u and node \c v is equal then each loop edge
  1121   /// will be enumerated once.
  1122   ///
  1123   /// If \c prev is \ref INVALID (this is the default value), then
  1124   /// it finds the first edge from \c u to \c v. Otherwise it looks for
  1125   /// the next edge from \c u to \c v after \c prev.
  1126   /// \return The found edge or \ref INVALID if there is no such an edge.
  1127   ///
  1128   /// Thus you can iterate through each edge between \c u and \c v
  1129   /// as it follows.
  1130   ///\code
  1131   /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
  1132   ///   ...
  1133   /// }
  1134   ///\endcode
  1135   ///
  1136   /// \note \ref ConEdgeIt provides iterator interface for the same
  1137   /// functionality.
  1138   ///
  1139   ///\sa ConEdgeIt
  1140   template <typename Graph>
  1141   inline typename Graph::Edge
  1142   findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
  1143             typename Graph::Edge p = INVALID) {
  1144     return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
  1145   }
  1146 
  1147   /// \brief Iterator for iterating on parallel edges connecting the same nodes.
  1148   ///
  1149   /// Iterator for iterating on parallel edges connecting the same nodes.
  1150   /// It is a higher level interface for the findEdge() function. You can
  1151   /// use it the following way:
  1152   ///\code
  1153   /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
  1154   ///   ...
  1155   /// }
  1156   ///\endcode
  1157   ///
  1158   ///\sa findEdge()
  1159   template <typename _Graph>
  1160   class ConEdgeIt : public _Graph::Edge {
  1161   public:
  1162 
  1163     typedef _Graph Graph;
  1164     typedef typename Graph::Edge Parent;
  1165 
  1166     typedef typename Graph::Edge Edge;
  1167     typedef typename Graph::Node Node;
  1168 
  1169     /// \brief Constructor.
  1170     ///
  1171     /// Construct a new ConEdgeIt iterating on the edges that
  1172     /// connects nodes \c u and \c v.
  1173     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
  1174       Parent::operator=(findEdge(_graph, _u, _v));
  1175     }
  1176 
  1177     /// \brief Constructor.
  1178     ///
  1179     /// Construct a new ConEdgeIt that continues iterating from edge \c e.
  1180     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
  1181 
  1182     /// \brief Increment operator.
  1183     ///
  1184     /// It increments the iterator and gives back the next edge.
  1185     ConEdgeIt& operator++() {
  1186       Parent::operator=(findEdge(_graph, _u, _v, *this));
  1187       return *this;
  1188     }
  1189   private:
  1190     const Graph& _graph;
  1191     Node _u, _v;
  1192   };
  1193 
  1194 
  1195   ///Dynamic arc look-up between given endpoints.
  1196 
  1197   ///Using this class, you can find an arc in a digraph from a given
  1198   ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
  1199   ///where <em>d</em> is the out-degree of the source node.
  1200   ///
  1201   ///It is possible to find \e all parallel arcs between two nodes with
  1202   ///the \c operator() member.
  1203   ///
  1204   ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
  1205   ///\ref AllArcLookUp if your digraph is not changed so frequently.
  1206   ///
  1207   ///This class uses a self-adjusting binary search tree, the Splay tree
  1208   ///of Sleator and Tarjan to guarantee the logarithmic amortized
  1209   ///time bound for arc look-ups. This class also guarantees the
  1210   ///optimal time bound in a constant factor for any distribution of
  1211   ///queries.
  1212   ///
  1213   ///\tparam G The type of the underlying digraph.
  1214   ///
  1215   ///\sa ArcLookUp
  1216   ///\sa AllArcLookUp
  1217   template<class G>
  1218   class DynArcLookUp
  1219     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
  1220   {
  1221   public:
  1222     typedef typename ItemSetTraits<G, typename G::Arc>
  1223     ::ItemNotifier::ObserverBase Parent;
  1224 
  1225     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1226     typedef G Digraph;
  1227 
  1228   protected:
  1229 
  1230     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
  1231     public:
  1232 
  1233       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
  1234 
  1235       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
  1236 
  1237       virtual void add(const Node& node) {
  1238         Parent::add(node);
  1239         Parent::set(node, INVALID);
  1240       }
  1241 
  1242       virtual void add(const std::vector<Node>& nodes) {
  1243         Parent::add(nodes);
  1244         for (int i = 0; i < int(nodes.size()); ++i) {
  1245           Parent::set(nodes[i], INVALID);
  1246         }
  1247       }
  1248 
  1249       virtual void build() {
  1250         Parent::build();
  1251         Node it;
  1252         typename Parent::Notifier* nf = Parent::notifier();
  1253         for (nf->first(it); it != INVALID; nf->next(it)) {
  1254           Parent::set(it, INVALID);
  1255         }
  1256       }
  1257     };
  1258 
  1259     const Digraph &_g;
  1260     AutoNodeMap _head;
  1261     typename Digraph::template ArcMap<Arc> _parent;
  1262     typename Digraph::template ArcMap<Arc> _left;
  1263     typename Digraph::template ArcMap<Arc> _right;
  1264 
  1265     class ArcLess {
  1266       const Digraph &g;
  1267     public:
  1268       ArcLess(const Digraph &_g) : g(_g) {}
  1269       bool operator()(Arc a,Arc b) const
  1270       {
  1271         return g.target(a)<g.target(b);
  1272       }
  1273     };
  1274 
  1275   public:
  1276 
  1277     ///Constructor
  1278 
  1279     ///Constructor.
  1280     ///
  1281     ///It builds up the search database.
  1282     DynArcLookUp(const Digraph &g)
  1283       : _g(g),_head(g),_parent(g),_left(g),_right(g)
  1284     {
  1285       Parent::attach(_g.notifier(typename Digraph::Arc()));
  1286       refresh();
  1287     }
  1288 
  1289   protected:
  1290 
  1291     virtual void add(const Arc& arc) {
  1292       insert(arc);
  1293     }
  1294 
  1295     virtual void add(const std::vector<Arc>& arcs) {
  1296       for (int i = 0; i < int(arcs.size()); ++i) {
  1297         insert(arcs[i]);
  1298       }
  1299     }
  1300 
  1301     virtual void erase(const Arc& arc) {
  1302       remove(arc);
  1303     }
  1304 
  1305     virtual void erase(const std::vector<Arc>& arcs) {
  1306       for (int i = 0; i < int(arcs.size()); ++i) {
  1307         remove(arcs[i]);
  1308       }
  1309     }
  1310 
  1311     virtual void build() {
  1312       refresh();
  1313     }
  1314 
  1315     virtual void clear() {
  1316       for(NodeIt n(_g);n!=INVALID;++n) {
  1317         _head.set(n, INVALID);
  1318       }
  1319     }
  1320 
  1321     void insert(Arc arc) {
  1322       Node s = _g.source(arc);
  1323       Node t = _g.target(arc);
  1324       _left.set(arc, INVALID);
  1325       _right.set(arc, INVALID);
  1326 
  1327       Arc e = _head[s];
  1328       if (e == INVALID) {
  1329         _head.set(s, arc);
  1330         _parent.set(arc, INVALID);
  1331         return;
  1332       }
  1333       while (true) {
  1334         if (t < _g.target(e)) {
  1335           if (_left[e] == INVALID) {
  1336             _left.set(e, arc);
  1337             _parent.set(arc, e);
  1338             splay(arc);
  1339             return;
  1340           } else {
  1341             e = _left[e];
  1342           }
  1343         } else {
  1344           if (_right[e] == INVALID) {
  1345             _right.set(e, arc);
  1346             _parent.set(arc, e);
  1347             splay(arc);
  1348             return;
  1349           } else {
  1350             e = _right[e];
  1351           }
  1352         }
  1353       }
  1354     }
  1355 
  1356     void remove(Arc arc) {
  1357       if (_left[arc] == INVALID) {
  1358         if (_right[arc] != INVALID) {
  1359           _parent.set(_right[arc], _parent[arc]);
  1360         }
  1361         if (_parent[arc] != INVALID) {
  1362           if (_left[_parent[arc]] == arc) {
  1363             _left.set(_parent[arc], _right[arc]);
  1364           } else {
  1365             _right.set(_parent[arc], _right[arc]);
  1366           }
  1367         } else {
  1368           _head.set(_g.source(arc), _right[arc]);
  1369         }
  1370       } else if (_right[arc] == INVALID) {
  1371         _parent.set(_left[arc], _parent[arc]);
  1372         if (_parent[arc] != INVALID) {
  1373           if (_left[_parent[arc]] == arc) {
  1374             _left.set(_parent[arc], _left[arc]);
  1375           } else {
  1376             _right.set(_parent[arc], _left[arc]);
  1377           }
  1378         } else {
  1379           _head.set(_g.source(arc), _left[arc]);
  1380         }
  1381       } else {
  1382         Arc e = _left[arc];
  1383         if (_right[e] != INVALID) {
  1384           e = _right[e];
  1385           while (_right[e] != INVALID) {
  1386             e = _right[e];
  1387           }
  1388           Arc s = _parent[e];
  1389           _right.set(_parent[e], _left[e]);
  1390           if (_left[e] != INVALID) {
  1391             _parent.set(_left[e], _parent[e]);
  1392           }
  1393 
  1394           _left.set(e, _left[arc]);
  1395           _parent.set(_left[arc], e);
  1396           _right.set(e, _right[arc]);
  1397           _parent.set(_right[arc], e);
  1398 
  1399           _parent.set(e, _parent[arc]);
  1400           if (_parent[arc] != INVALID) {
  1401             if (_left[_parent[arc]] == arc) {
  1402               _left.set(_parent[arc], e);
  1403             } else {
  1404               _right.set(_parent[arc], e);
  1405             }
  1406           }
  1407           splay(s);
  1408         } else {
  1409           _right.set(e, _right[arc]);
  1410           _parent.set(_right[arc], e);
  1411           _parent.set(e, _parent[arc]);
  1412 
  1413           if (_parent[arc] != INVALID) {
  1414             if (_left[_parent[arc]] == arc) {
  1415               _left.set(_parent[arc], e);
  1416             } else {
  1417               _right.set(_parent[arc], e);
  1418             }
  1419           } else {
  1420             _head.set(_g.source(arc), e);
  1421           }
  1422         }
  1423       }
  1424     }
  1425 
  1426     Arc refreshRec(std::vector<Arc> &v,int a,int b)
  1427     {
  1428       int m=(a+b)/2;
  1429       Arc me=v[m];
  1430       if (a < m) {
  1431         Arc left = refreshRec(v,a,m-1);
  1432         _left.set(me, left);
  1433         _parent.set(left, me);
  1434       } else {
  1435         _left.set(me, INVALID);
  1436       }
  1437       if (m < b) {
  1438         Arc right = refreshRec(v,m+1,b);
  1439         _right.set(me, right);
  1440         _parent.set(right, me);
  1441       } else {
  1442         _right.set(me, INVALID);
  1443       }
  1444       return me;
  1445     }
  1446 
  1447     void refresh() {
  1448       for(NodeIt n(_g);n!=INVALID;++n) {
  1449         std::vector<Arc> v;
  1450         for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
  1451         if (!v.empty()) {
  1452           std::sort(v.begin(),v.end(),ArcLess(_g));
  1453           Arc head = refreshRec(v,0,v.size()-1);
  1454           _head.set(n, head);
  1455           _parent.set(head, INVALID);
  1456         }
  1457         else _head.set(n, INVALID);
  1458       }
  1459     }
  1460 
  1461     void zig(Arc v) {
  1462       Arc w = _parent[v];
  1463       _parent.set(v, _parent[w]);
  1464       _parent.set(w, v);
  1465       _left.set(w, _right[v]);
  1466       _right.set(v, w);
  1467       if (_parent[v] != INVALID) {
  1468         if (_right[_parent[v]] == w) {
  1469           _right.set(_parent[v], v);
  1470         } else {
  1471           _left.set(_parent[v], v);
  1472         }
  1473       }
  1474       if (_left[w] != INVALID){
  1475         _parent.set(_left[w], w);
  1476       }
  1477     }
  1478 
  1479     void zag(Arc v) {
  1480       Arc w = _parent[v];
  1481       _parent.set(v, _parent[w]);
  1482       _parent.set(w, v);
  1483       _right.set(w, _left[v]);
  1484       _left.set(v, w);
  1485       if (_parent[v] != INVALID){
  1486         if (_left[_parent[v]] == w) {
  1487           _left.set(_parent[v], v);
  1488         } else {
  1489           _right.set(_parent[v], v);
  1490         }
  1491       }
  1492       if (_right[w] != INVALID){
  1493         _parent.set(_right[w], w);
  1494       }
  1495     }
  1496 
  1497     void splay(Arc v) {
  1498       while (_parent[v] != INVALID) {
  1499         if (v == _left[_parent[v]]) {
  1500           if (_parent[_parent[v]] == INVALID) {
  1501             zig(v);
  1502           } else {
  1503             if (_parent[v] == _left[_parent[_parent[v]]]) {
  1504               zig(_parent[v]);
  1505               zig(v);
  1506             } else {
  1507               zig(v);
  1508               zag(v);
  1509             }
  1510           }
  1511         } else {
  1512           if (_parent[_parent[v]] == INVALID) {
  1513             zag(v);
  1514           } else {
  1515             if (_parent[v] == _left[_parent[_parent[v]]]) {
  1516               zag(v);
  1517               zig(v);
  1518             } else {
  1519               zag(_parent[v]);
  1520               zag(v);
  1521             }
  1522           }
  1523         }
  1524       }
  1525       _head[_g.source(v)] = v;
  1526     }
  1527 
  1528 
  1529   public:
  1530 
  1531     ///Find an arc between two nodes.
  1532 
  1533     ///Find an arc between two nodes.
  1534     ///\param s The source node.
  1535     ///\param t The target node.
  1536     ///\param p The previous arc between \c s and \c t. It it is INVALID or
  1537     ///not given, the operator finds the first appropriate arc.
  1538     ///\return An arc from \c s to \c t after \c p or
  1539     ///\ref INVALID if there is no more.
  1540     ///
  1541     ///For example, you can count the number of arcs from \c u to \c v in the
  1542     ///following way.
  1543     ///\code
  1544     ///DynArcLookUp<ListDigraph> ae(g);
  1545     ///...
  1546     ///int n = 0;
  1547     ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
  1548     ///\endcode
  1549     ///
  1550     ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
  1551     ///amortized time, specifically, the time complexity of the lookups
  1552     ///is equal to the optimal search tree implementation for the
  1553     ///current query distribution in a constant factor.
  1554     ///
  1555     ///\note This is a dynamic data structure, therefore the data
  1556     ///structure is updated after each graph alteration. Thus although
  1557     ///this data structure is theoretically faster than \ref ArcLookUp
  1558     ///and \ref AllArcLookUp, it often provides worse performance than
  1559     ///them.
  1560     Arc operator()(Node s, Node t, Arc p = INVALID) const  {
  1561       if (p == INVALID) {
  1562         Arc a = _head[s];
  1563         if (a == INVALID) return INVALID;
  1564         Arc r = INVALID;
  1565         while (true) {
  1566           if (_g.target(a) < t) {
  1567             if (_right[a] == INVALID) {
  1568               const_cast<DynArcLookUp&>(*this).splay(a);
  1569               return r;
  1570             } else {
  1571               a = _right[a];
  1572             }
  1573           } else {
  1574             if (_g.target(a) == t) {
  1575               r = a;
  1576             }
  1577             if (_left[a] == INVALID) {
  1578               const_cast<DynArcLookUp&>(*this).splay(a);
  1579               return r;
  1580             } else {
  1581               a = _left[a];
  1582             }
  1583           }
  1584         }
  1585       } else {
  1586         Arc a = p;
  1587         if (_right[a] != INVALID) {
  1588           a = _right[a];
  1589           while (_left[a] != INVALID) {
  1590             a = _left[a];
  1591           }
  1592           const_cast<DynArcLookUp&>(*this).splay(a);
  1593         } else {
  1594           while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
  1595             a = _parent[a];
  1596           }
  1597           if (_parent[a] == INVALID) {
  1598             return INVALID;
  1599           } else {
  1600             a = _parent[a];
  1601             const_cast<DynArcLookUp&>(*this).splay(a);
  1602           }
  1603         }
  1604         if (_g.target(a) == t) return a;
  1605         else return INVALID;
  1606       }
  1607     }
  1608 
  1609   };
  1610 
  1611   ///Fast arc look-up between given endpoints.
  1612 
  1613   ///Using this class, you can find an arc in a digraph from a given
  1614   ///source to a given target in time <em>O</em>(log<em>d</em>),
  1615   ///where <em>d</em> is the out-degree of the source node.
  1616   ///
  1617   ///It is not possible to find \e all parallel arcs between two nodes.
  1618   ///Use \ref AllArcLookUp for this purpose.
  1619   ///
  1620   ///\warning This class is static, so you should call refresh() (or at
  1621   ///least refresh(Node)) to refresh this data structure whenever the
  1622   ///digraph changes. This is a time consuming (superlinearly proportional
  1623   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  1624   ///
  1625   ///\tparam G The type of the underlying digraph.
  1626   ///
  1627   ///\sa DynArcLookUp
  1628   ///\sa AllArcLookUp
  1629   template<class G>
  1630   class ArcLookUp
  1631   {
  1632   public:
  1633     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1634     typedef G Digraph;
  1635 
  1636   protected:
  1637     const Digraph &_g;
  1638     typename Digraph::template NodeMap<Arc> _head;
  1639     typename Digraph::template ArcMap<Arc> _left;
  1640     typename Digraph::template ArcMap<Arc> _right;
  1641 
  1642     class ArcLess {
  1643       const Digraph &g;
  1644     public:
  1645       ArcLess(const Digraph &_g) : g(_g) {}
  1646       bool operator()(Arc a,Arc b) const
  1647       {
  1648         return g.target(a)<g.target(b);
  1649       }
  1650     };
  1651 
  1652   public:
  1653 
  1654     ///Constructor
  1655 
  1656     ///Constructor.
  1657     ///
  1658     ///It builds up the search database, which remains valid until the digraph
  1659     ///changes.
  1660     ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
  1661 
  1662   private:
  1663     Arc refreshRec(std::vector<Arc> &v,int a,int b)
  1664     {
  1665       int m=(a+b)/2;
  1666       Arc me=v[m];
  1667       _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
  1668       _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
  1669       return me;
  1670     }
  1671   public:
  1672     ///Refresh the search data structure at a node.
  1673 
  1674     ///Build up the search database of node \c n.
  1675     ///
  1676     ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
  1677     ///is the number of the outgoing arcs of \c n.
  1678     void refresh(Node n)
  1679     {
  1680       std::vector<Arc> v;
  1681       for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  1682       if(v.size()) {
  1683         std::sort(v.begin(),v.end(),ArcLess(_g));
  1684         _head[n]=refreshRec(v,0,v.size()-1);
  1685       }
  1686       else _head[n]=INVALID;
  1687     }
  1688     ///Refresh the full data structure.
  1689 
  1690     ///Build up the full search database. In fact, it simply calls
  1691     ///\ref refresh(Node) "refresh(n)" for each node \c n.
  1692     ///
  1693     ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
  1694     ///the number of the arcs in the digraph and <em>D</em> is the maximum
  1695     ///out-degree of the digraph.
  1696     void refresh()
  1697     {
  1698       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
  1699     }
  1700 
  1701     ///Find an arc between two nodes.
  1702 
  1703     ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
  1704     ///where <em>d</em> is the number of outgoing arcs of \c s.
  1705     ///\param s The source node.
  1706     ///\param t The target node.
  1707     ///\return An arc from \c s to \c t if there exists,
  1708     ///\ref INVALID otherwise.
  1709     ///
  1710     ///\warning If you change the digraph, refresh() must be called before using
  1711     ///this operator. If you change the outgoing arcs of
  1712     ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
  1713     Arc operator()(Node s, Node t) const
  1714     {
  1715       Arc e;
  1716       for(e=_head[s];
  1717           e!=INVALID&&_g.target(e)!=t;
  1718           e = t < _g.target(e)?_left[e]:_right[e]) ;
  1719       return e;
  1720     }
  1721 
  1722   };
  1723 
  1724   ///Fast look-up of all arcs between given endpoints.
  1725 
  1726   ///This class is the same as \ref ArcLookUp, with the addition
  1727   ///that it makes it possible to find all parallel arcs between given
  1728   ///endpoints.
  1729   ///
  1730   ///\warning This class is static, so you should call refresh() (or at
  1731   ///least refresh(Node)) to refresh this data structure whenever the
  1732   ///digraph changes. This is a time consuming (superlinearly proportional
  1733   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  1734   ///
  1735   ///\tparam G The type of the underlying digraph.
  1736   ///
  1737   ///\sa DynArcLookUp
  1738   ///\sa ArcLookUp
  1739   template<class G>
  1740   class AllArcLookUp : public ArcLookUp<G>
  1741   {
  1742     using ArcLookUp<G>::_g;
  1743     using ArcLookUp<G>::_right;
  1744     using ArcLookUp<G>::_left;
  1745     using ArcLookUp<G>::_head;
  1746 
  1747     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1748     typedef G Digraph;
  1749 
  1750     typename Digraph::template ArcMap<Arc> _next;
  1751 
  1752     Arc refreshNext(Arc head,Arc next=INVALID)
  1753     {
  1754       if(head==INVALID) return next;
  1755       else {
  1756         next=refreshNext(_right[head],next);
  1757         _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
  1758           ? next : INVALID;
  1759         return refreshNext(_left[head],head);
  1760       }
  1761     }
  1762 
  1763     void refreshNext()
  1764     {
  1765       for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
  1766     }
  1767 
  1768   public:
  1769     ///Constructor
  1770 
  1771     ///Constructor.
  1772     ///
  1773     ///It builds up the search database, which remains valid until the digraph
  1774     ///changes.
  1775     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
  1776 
  1777     ///Refresh the data structure at a node.
  1778 
  1779     ///Build up the search database of node \c n.
  1780     ///
  1781     ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
  1782     ///the number of the outgoing arcs of \c n.
  1783     void refresh(Node n)
  1784     {
  1785       ArcLookUp<G>::refresh(n);
  1786       refreshNext(_head[n]);
  1787     }
  1788 
  1789     ///Refresh the full data structure.
  1790 
  1791     ///Build up the full search database. In fact, it simply calls
  1792     ///\ref refresh(Node) "refresh(n)" for each node \c n.
  1793     ///
  1794     ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
  1795     ///the number of the arcs in the digraph and <em>D</em> is the maximum
  1796     ///out-degree of the digraph.
  1797     void refresh()
  1798     {
  1799       for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
  1800     }
  1801 
  1802     ///Find an arc between two nodes.
  1803 
  1804     ///Find an arc between two nodes.
  1805     ///\param s The source node.
  1806     ///\param t The target node.
  1807     ///\param prev The previous arc between \c s and \c t. It it is INVALID or
  1808     ///not given, the operator finds the first appropriate arc.
  1809     ///\return An arc from \c s to \c t after \c prev or
  1810     ///\ref INVALID if there is no more.
  1811     ///
  1812     ///For example, you can count the number of arcs from \c u to \c v in the
  1813     ///following way.
  1814     ///\code
  1815     ///AllArcLookUp<ListDigraph> ae(g);
  1816     ///...
  1817     ///int n = 0;
  1818     ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
  1819     ///\endcode
  1820     ///
  1821     ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
  1822     ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
  1823     ///consecutive arcs are found in constant time.
  1824     ///
  1825     ///\warning If you change the digraph, refresh() must be called before using
  1826     ///this operator. If you change the outgoing arcs of
  1827     ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
  1828     ///
  1829 #ifdef DOXYGEN
  1830     Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
  1831 #else
  1832     using ArcLookUp<G>::operator() ;
  1833     Arc operator()(Node s, Node t, Arc prev) const
  1834     {
  1835       return prev==INVALID?(*this)(s,t):_next[prev];
  1836     }
  1837 #endif
  1838 
  1839   };
  1840 
  1841   /// @}
  1842 
  1843 } //namespace lemon
  1844 
  1845 #endif