lemon/core.h
changeset 228 b6732e0d38c5
child 229 aebc0161f6e5
equal deleted inserted replaced
-1:000000000000 0:2205e112b6a6
       
     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