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