lemon/graph_utils.h
author Balazs Dezso <deba@inf.elte.hu>
Tue, 25 Mar 2008 16:36:44 +0100
changeset 108 889d0c289d19
child 139 701c529ba737
permissions -rw-r--r--
Reworking assertions and moving to distinict file
     1 /* -*- C++ -*-
     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_GRAPH_UTILS_H
    20 #define LEMON_GRAPH_UTILS_H
    21 
    22 #include <iterator>
    23 #include <vector>
    24 #include <map>
    25 #include <cmath>
    26 #include <algorithm>
    27 
    28 #include <lemon/bits/invalid.h>
    29 #include <lemon/bits/utility.h>
    30 #include <lemon/maps.h>
    31 #include <lemon/bits/traits.h>
    32 
    33 #include <lemon/bits/alteration_notifier.h>
    34 #include <lemon/bits/default_map.h>
    35 
    36 ///\ingroup gutils
    37 ///\file
    38 ///\brief Digraph utilities.
    39 
    40 namespace lemon {
    41 
    42   /// \addtogroup gutils
    43   /// @{
    44 
    45   ///Creates convenience typedefs for the digraph types and iterators
    46 
    47   ///This \c \#define creates convenience typedefs for the following types
    48   ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    49   ///\c OutArcIt
    50   ///\note If \c G it a template parameter, it should be used in this way.
    51   ///\code
    52   ///  GRAPH_TYPEDEFS(typename G);
    53   ///\endcode
    54   ///
    55   ///\warning There are no typedefs for the digraph maps because of the lack of
    56   ///template typedefs in C++.
    57 #define GRAPH_TYPEDEFS(Digraph)				\
    58   typedef Digraph::     Node      Node;			\
    59     typedef Digraph::   NodeIt    NodeIt;			\
    60     typedef Digraph::   Arc      Arc;			\
    61     typedef Digraph::   ArcIt    ArcIt;			\
    62     typedef Digraph:: InArcIt  InArcIt;			\
    63     typedef Digraph::OutArcIt OutArcIt
    64 
    65   ///Creates convenience typedefs for the graph types and iterators
    66 
    67   ///This \c \#define creates the same convenience typedefs as defined by
    68   ///\ref GRAPH_TYPEDEFS(Digraph) and three more, namely it creates
    69   ///\c Edge, \c EdgeIt, \c IncArcIt,
    70   ///
    71   ///\note If \c G it a template parameter, it should be used in this way.
    72   ///\code
    73   ///  UGRAPH_TYPEDEFS(typename G);
    74   ///\endcode
    75   ///
    76   ///\warning There are no typedefs for the digraph maps because of the lack of
    77   ///template typedefs in C++.
    78 #define UGRAPH_TYPEDEFS(Digraph)				\
    79   GRAPH_TYPEDEFS(Digraph);				\
    80     typedef Digraph:: Edge   Edge;			\
    81     typedef Digraph:: EdgeIt EdgeIt;			\
    82     typedef Digraph:: IncArcIt   IncArcIt
    83 
    84   ///\brief Creates convenience typedefs for the bipartite digraph 
    85   ///types and iterators
    86 
    87   ///This \c \#define creates the same convenience typedefs as defined by
    88   ///\ref UGRAPH_TYPEDEFS(Digraph) and two more, namely it creates
    89   ///\c RedIt, \c BlueIt, 
    90   ///
    91   ///\note If \c G it a template parameter, it should be used in this way.
    92   ///\code
    93   ///  BPUGRAPH_TYPEDEFS(typename G);
    94   ///\endcode
    95   ///
    96   ///\warning There are no typedefs for the digraph maps because of the lack of
    97   ///template typedefs in C++.
    98 #define BPUGRAPH_TYPEDEFS(Digraph)            \
    99   UGRAPH_TYPEDEFS(Digraph);		    \
   100     typedef Digraph::Red Red;             \
   101     typedef Digraph::Blue Blue;             \
   102     typedef Digraph::RedIt RedIt;	    \
   103     typedef Digraph::BlueIt BlueIt
   104 
   105   /// \brief Function to count the items in the digraph.
   106   ///
   107   /// This function counts the items (nodes, arcs etc) in the digraph.
   108   /// The complexity of the function is O(n) because
   109   /// it iterates on all of the items.
   110 
   111   template <typename Digraph, typename Item>
   112   inline int countItems(const Digraph& g) {
   113     typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   114     int num = 0;
   115     for (ItemIt it(g); it != INVALID; ++it) {
   116       ++num;
   117     }
   118     return num;
   119   }
   120 
   121   // Node counting:
   122 
   123   namespace _digraph_utils_bits {
   124     
   125     template <typename Digraph, typename Enable = void>
   126     struct CountNodesSelector {
   127       static int count(const Digraph &g) {
   128         return countItems<Digraph, typename Digraph::Node>(g);
   129       }
   130     };
   131 
   132     template <typename Digraph>
   133     struct CountNodesSelector<
   134       Digraph, typename 
   135       enable_if<typename Digraph::NodeNumTag, void>::type> 
   136     {
   137       static int count(const Digraph &g) {
   138         return g.nodeNum();
   139       }
   140     };    
   141   }
   142 
   143   /// \brief Function to count the nodes in the digraph.
   144   ///
   145   /// This function counts the nodes in the digraph.
   146   /// The complexity of the function is O(n) but for some
   147   /// digraph structures it is specialized to run in O(1).
   148   ///
   149   /// If the digraph contains a \e nodeNum() member function and a 
   150   /// \e NodeNumTag tag then this function calls directly the member
   151   /// function to query the cardinality of the node set.
   152   template <typename Digraph>
   153   inline int countNodes(const Digraph& g) {
   154     return _digraph_utils_bits::CountNodesSelector<Digraph>::count(g);
   155   }
   156 
   157   namespace _digraph_utils_bits {
   158     
   159     template <typename Digraph, typename Enable = void>
   160     struct CountRedsSelector {
   161       static int count(const Digraph &g) {
   162         return countItems<Digraph, typename Digraph::Red>(g);
   163       }
   164     };
   165 
   166     template <typename Digraph>
   167     struct CountRedsSelector<
   168       Digraph, typename 
   169       enable_if<typename Digraph::NodeNumTag, void>::type> 
   170     {
   171       static int count(const Digraph &g) {
   172         return g.redNum();
   173       }
   174     };    
   175   }
   176 
   177   /// \brief Function to count the reds in the digraph.
   178   ///
   179   /// This function counts the reds in the digraph.
   180   /// The complexity of the function is O(an) but for some
   181   /// digraph structures it is specialized to run in O(1).
   182   ///
   183   /// If the digraph contains an \e redNum() member function and a 
   184   /// \e NodeNumTag tag then this function calls directly the member
   185   /// function to query the cardinality of the A-node set.
   186   template <typename Digraph>
   187   inline int countReds(const Digraph& g) {
   188     return _digraph_utils_bits::CountRedsSelector<Digraph>::count(g);
   189   }
   190 
   191   namespace _digraph_utils_bits {
   192     
   193     template <typename Digraph, typename Enable = void>
   194     struct CountBluesSelector {
   195       static int count(const Digraph &g) {
   196         return countItems<Digraph, typename Digraph::Blue>(g);
   197       }
   198     };
   199 
   200     template <typename Digraph>
   201     struct CountBluesSelector<
   202       Digraph, typename 
   203       enable_if<typename Digraph::NodeNumTag, void>::type> 
   204     {
   205       static int count(const Digraph &g) {
   206         return g.blueNum();
   207       }
   208     };    
   209   }
   210 
   211   /// \brief Function to count the blues in the digraph.
   212   ///
   213   /// This function counts the blues in the digraph.
   214   /// The complexity of the function is O(bn) but for some
   215   /// digraph structures it is specialized to run in O(1).
   216   ///
   217   /// If the digraph contains a \e blueNum() member function and a 
   218   /// \e NodeNumTag tag then this function calls directly the member
   219   /// function to query the cardinality of the B-node set.
   220   template <typename Digraph>
   221   inline int countBlues(const Digraph& g) {
   222     return _digraph_utils_bits::CountBluesSelector<Digraph>::count(g);
   223   }
   224 
   225 
   226   // Arc counting:
   227 
   228   namespace _digraph_utils_bits {
   229     
   230     template <typename Digraph, typename Enable = void>
   231     struct CountArcsSelector {
   232       static int count(const Digraph &g) {
   233         return countItems<Digraph, typename Digraph::Arc>(g);
   234       }
   235     };
   236 
   237     template <typename Digraph>
   238     struct CountArcsSelector<
   239       Digraph, 
   240       typename enable_if<typename Digraph::ArcNumTag, void>::type> 
   241     {
   242       static int count(const Digraph &g) {
   243         return g.arcNum();
   244       }
   245     };    
   246   }
   247 
   248   /// \brief Function to count the arcs in the digraph.
   249   ///
   250   /// This function counts the arcs in the digraph.
   251   /// The complexity of the function is O(e) but for some
   252   /// digraph structures it is specialized to run in O(1).
   253   ///
   254   /// If the digraph contains a \e arcNum() member function and a 
   255   /// \e ArcNumTag tag then this function calls directly the member
   256   /// function to query the cardinality of the arc set.
   257   template <typename Digraph>
   258   inline int countArcs(const Digraph& g) {
   259     return _digraph_utils_bits::CountArcsSelector<Digraph>::count(g);
   260   }
   261 
   262   // Undirected arc counting:
   263   namespace _digraph_utils_bits {
   264     
   265     template <typename Digraph, typename Enable = void>
   266     struct CountEdgesSelector {
   267       static int count(const Digraph &g) {
   268         return countItems<Digraph, typename Digraph::Edge>(g);
   269       }
   270     };
   271 
   272     template <typename Digraph>
   273     struct CountEdgesSelector<
   274       Digraph, 
   275       typename enable_if<typename Digraph::ArcNumTag, void>::type> 
   276     {
   277       static int count(const Digraph &g) {
   278         return g.edgeNum();
   279       }
   280     };    
   281   }
   282 
   283   /// \brief Function to count the edges in the digraph.
   284   ///
   285   /// This function counts the edges in the digraph.
   286   /// The complexity of the function is O(e) but for some
   287   /// digraph structures it is specialized to run in O(1).
   288   ///
   289   /// If the digraph contains a \e edgeNum() member function and a 
   290   /// \e ArcNumTag tag then this function calls directly the member
   291   /// function to query the cardinality of the edge set.
   292   template <typename Digraph>
   293   inline int countEdges(const Digraph& g) {
   294     return _digraph_utils_bits::CountEdgesSelector<Digraph>::count(g);
   295 
   296   }
   297 
   298 
   299   template <typename Digraph, typename DegIt>
   300   inline int countNodeDegree(const Digraph& _g, const typename Digraph::Node& _n) {
   301     int num = 0;
   302     for (DegIt it(_g, _n); it != INVALID; ++it) {
   303       ++num;
   304     }
   305     return num;
   306   }
   307 
   308   /// \brief Function to count the number of the out-arcs from node \c n.
   309   ///
   310   /// This function counts the number of the out-arcs from node \c n
   311   /// in the digraph.  
   312   template <typename Digraph>
   313   inline int countOutArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
   314     return countNodeDegree<Digraph, typename Digraph::OutArcIt>(_g, _n);
   315   }
   316 
   317   /// \brief Function to count the number of the in-arcs to node \c n.
   318   ///
   319   /// This function counts the number of the in-arcs to node \c n
   320   /// in the digraph.  
   321   template <typename Digraph>
   322   inline int countInArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
   323     return countNodeDegree<Digraph, typename Digraph::InArcIt>(_g, _n);
   324   }
   325 
   326   /// \brief Function to count the number of the inc-arcs to node \c n.
   327   ///
   328   /// This function counts the number of the inc-arcs to node \c n
   329   /// in the digraph.  
   330   template <typename Digraph>
   331   inline int countIncArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
   332     return countNodeDegree<Digraph, typename Digraph::IncArcIt>(_g, _n);
   333   }
   334 
   335   namespace _digraph_utils_bits {
   336     
   337     template <typename Digraph, typename Enable = void>
   338     struct FindArcSelector {
   339       typedef typename Digraph::Node Node;
   340       typedef typename Digraph::Arc Arc;
   341       static Arc find(const Digraph &g, Node u, Node v, Arc e) {
   342         if (e == INVALID) {
   343           g.firstOut(e, u);
   344         } else {
   345           g.nextOut(e);
   346         }
   347         while (e != INVALID && g.target(e) != v) {
   348           g.nextOut(e);
   349         }
   350         return e;
   351       }
   352     };
   353 
   354     template <typename Digraph>
   355     struct FindArcSelector<
   356       Digraph, 
   357       typename enable_if<typename Digraph::FindArcTag, void>::type> 
   358     {
   359       typedef typename Digraph::Node Node;
   360       typedef typename Digraph::Arc Arc;
   361       static Arc find(const Digraph &g, Node u, Node v, Arc prev) {
   362         return g.findArc(u, v, prev);
   363       }
   364     };    
   365   }
   366 
   367   /// \brief Finds an arc between two nodes of a digraph.
   368   ///
   369   /// Finds an arc from node \c u to node \c v in digraph \c g.
   370   ///
   371   /// If \c prev is \ref INVALID (this is the default value), then
   372   /// it finds the first arc from \c u to \c v. Otherwise it looks for
   373   /// the next arc from \c u to \c v after \c prev.
   374   /// \return The found arc or \ref INVALID if there is no such an arc.
   375   ///
   376   /// Thus you can iterate through each arc from \c u to \c v as it follows.
   377   ///\code
   378   /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
   379   ///   ...
   380   /// }
   381   ///\endcode
   382   ///
   383   ///\sa ArcLookUp
   384   ///\sa AllArcLookUp
   385   ///\sa DynArcLookUp
   386   ///\sa ConArcIt
   387   template <typename Digraph>
   388   inline typename Digraph::Arc 
   389   findArc(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
   390            typename Digraph::Arc prev = INVALID) {
   391     return _digraph_utils_bits::FindArcSelector<Digraph>::find(g, u, v, prev);
   392   }
   393 
   394   /// \brief Iterator for iterating on arcs connected the same nodes.
   395   ///
   396   /// Iterator for iterating on arcs connected the same nodes. It is 
   397   /// higher level interface for the findArc() function. You can
   398   /// use it the following way:
   399   ///\code
   400   /// for (ConArcIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
   401   ///   ...
   402   /// }
   403   ///\endcode
   404   /// 
   405   ///\sa findArc()
   406   ///\sa ArcLookUp
   407   ///\sa AllArcLookUp
   408   ///\sa DynArcLookUp
   409   ///
   410   /// \author Balazs Dezso 
   411   template <typename _Digraph>
   412   class ConArcIt : public _Digraph::Arc {
   413   public:
   414 
   415     typedef _Digraph Digraph;
   416     typedef typename Digraph::Arc Parent;
   417 
   418     typedef typename Digraph::Arc Arc;
   419     typedef typename Digraph::Node Node;
   420 
   421     /// \brief Constructor.
   422     ///
   423     /// Construct a new ConArcIt iterating on the arcs which
   424     /// connects the \c u and \c v node.
   425     ConArcIt(const Digraph& g, Node u, Node v) : digraph(g) {
   426       Parent::operator=(findArc(digraph, u, v));
   427     }
   428 
   429     /// \brief Constructor.
   430     ///
   431     /// Construct a new ConArcIt which continues the iterating from 
   432     /// the \c e arc.
   433     ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}
   434     
   435     /// \brief Increment operator.
   436     ///
   437     /// It increments the iterator and gives back the next arc.
   438     ConArcIt& operator++() {
   439       Parent::operator=(findArc(digraph, digraph.source(*this), 
   440 				 digraph.target(*this), *this));
   441       return *this;
   442     }
   443   private:
   444     const Digraph& digraph;
   445   };
   446 
   447   namespace _digraph_utils_bits {
   448     
   449     template <typename Digraph, typename Enable = void>
   450     struct FindEdgeSelector {
   451       typedef typename Digraph::Node Node;
   452       typedef typename Digraph::Edge Edge;
   453       static Edge find(const Digraph &g, Node u, Node v, Edge e) {
   454         bool b;
   455         if (u != v) {
   456           if (e == INVALID) {
   457             g.firstInc(e, b, u);
   458           } else {
   459             b = g.source(e) == u;
   460             g.nextInc(e, b);
   461           }
   462           while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
   463             g.nextInc(e, b);
   464           }
   465         } else {
   466           if (e == INVALID) {
   467             g.firstInc(e, b, u);
   468           } else {
   469             b = true;
   470             g.nextInc(e, b);
   471           }
   472           while (e != INVALID && (!b || g.target(e) != v)) {
   473             g.nextInc(e, b);
   474           }
   475         }
   476         return e;
   477       }
   478     };
   479 
   480     template <typename Digraph>
   481     struct FindEdgeSelector<
   482       Digraph, 
   483       typename enable_if<typename Digraph::FindArcTag, void>::type> 
   484     {
   485       typedef typename Digraph::Node Node;
   486       typedef typename Digraph::Edge Edge;
   487       static Edge find(const Digraph &g, Node u, Node v, Edge prev) {
   488         return g.findEdge(u, v, prev);
   489       }
   490     };    
   491   }
   492 
   493   /// \brief Finds an edge between two nodes of a digraph.
   494   ///
   495   /// Finds an edge from node \c u to node \c v in digraph \c g.
   496   /// If the node \c u and node \c v is equal then each loop arc
   497   /// will be enumerated.
   498   ///
   499   /// If \c prev is \ref INVALID (this is the default value), then
   500   /// it finds the first arc from \c u to \c v. Otherwise it looks for
   501   /// the next arc from \c u to \c v after \c prev.
   502   /// \return The found arc or \ref INVALID if there is no such an arc.
   503   ///
   504   /// Thus you can iterate through each arc from \c u to \c v as it follows.
   505   ///\code
   506   /// for(Edge e = findEdge(g,u,v); e != INVALID; 
   507   ///     e = findEdge(g,u,v,e)) {
   508   ///   ...
   509   /// }
   510   ///\endcode
   511   ///
   512   ///\sa ConArcIt
   513 
   514   template <typename Digraph>
   515   inline typename Digraph::Edge 
   516   findEdge(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
   517             typename Digraph::Edge p = INVALID) {
   518     return _digraph_utils_bits::FindEdgeSelector<Digraph>::find(g, u, v, p);
   519   }
   520 
   521   /// \brief Iterator for iterating on edges connected the same nodes.
   522   ///
   523   /// Iterator for iterating on edges connected the same nodes. It is 
   524   /// higher level interface for the findEdge() function. You can
   525   /// use it the following way:
   526   ///\code
   527   /// for (ConEdgeIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
   528   ///   ...
   529   /// }
   530   ///\endcode
   531   ///
   532   ///\sa findEdge()
   533   ///
   534   /// \author Balazs Dezso 
   535   template <typename _Digraph>
   536   class ConEdgeIt : public _Digraph::Edge {
   537   public:
   538 
   539     typedef _Digraph Digraph;
   540     typedef typename Digraph::Edge Parent;
   541 
   542     typedef typename Digraph::Edge Edge;
   543     typedef typename Digraph::Node Node;
   544 
   545     /// \brief Constructor.
   546     ///
   547     /// Construct a new ConEdgeIt iterating on the arcs which
   548     /// connects the \c u and \c v node.
   549     ConEdgeIt(const Digraph& g, Node u, Node v) : digraph(g) {
   550       Parent::operator=(findEdge(digraph, u, v));
   551     }
   552 
   553     /// \brief Constructor.
   554     ///
   555     /// Construct a new ConEdgeIt which continues the iterating from 
   556     /// the \c e arc.
   557     ConEdgeIt(const Digraph& g, Edge e) : Parent(e), digraph(g) {}
   558     
   559     /// \brief Increment operator.
   560     ///
   561     /// It increments the iterator and gives back the next arc.
   562     ConEdgeIt& operator++() {
   563       Parent::operator=(findEdge(digraph, digraph.source(*this), 
   564 				      digraph.target(*this), *this));
   565       return *this;
   566     }
   567   private:
   568     const Digraph& digraph;
   569   };
   570 
   571   /// \brief Copy a map.
   572   ///
   573   /// This function copies the \c from map to the \c to map. It uses the
   574   /// given iterator to iterate on the data structure and it uses the \c ref
   575   /// mapping to convert the from's keys to the to's keys.
   576   template <typename To, typename From, 
   577 	    typename ItemIt, typename Ref>	    
   578   void copyMap(To& to, const From& from, 
   579 	       ItemIt it, const Ref& ref) {
   580     for (; it != INVALID; ++it) {
   581       to[ref[it]] = from[it];
   582     }
   583   }
   584 
   585   /// \brief Copy the from map to the to map.
   586   ///
   587   /// Copy the \c from map to the \c to map. It uses the given iterator
   588   /// to iterate on the data structure.
   589   template <typename To, typename From, typename ItemIt>	    
   590   void copyMap(To& to, const From& from, ItemIt it) {
   591     for (; it != INVALID; ++it) {
   592       to[it] = from[it];
   593     }
   594   }
   595 
   596   namespace _digraph_utils_bits {
   597 
   598     template <typename Digraph, typename Item, typename RefMap>
   599     class MapCopyBase {
   600     public:
   601       virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
   602       
   603       virtual ~MapCopyBase() {}
   604     };
   605 
   606     template <typename Digraph, typename Item, typename RefMap, 
   607               typename ToMap, typename FromMap>
   608     class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
   609     public:
   610 
   611       MapCopy(ToMap& tmap, const FromMap& map) 
   612         : _tmap(tmap), _map(map) {}
   613       
   614       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   615         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   616         for (ItemIt it(digraph); it != INVALID; ++it) {
   617           _tmap.set(refMap[it], _map[it]);
   618         }
   619       }
   620 
   621     private:
   622       ToMap& _tmap;
   623       const FromMap& _map;
   624     };
   625 
   626     template <typename Digraph, typename Item, typename RefMap, typename It>
   627     class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
   628     public:
   629 
   630       ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
   631       
   632       virtual void copy(const Digraph&, const RefMap& refMap) {
   633         _it = refMap[_item];
   634       }
   635 
   636     private:
   637       It& _it;
   638       Item _item;
   639     };
   640 
   641     template <typename Digraph, typename Item, typename RefMap, typename Ref>
   642     class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   643     public:
   644 
   645       RefCopy(Ref& map) : _map(map) {}
   646       
   647       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   648         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   649         for (ItemIt it(digraph); it != INVALID; ++it) {
   650           _map.set(it, refMap[it]);
   651         }
   652       }
   653 
   654     private:
   655       Ref& _map;
   656     };
   657 
   658     template <typename Digraph, typename Item, typename RefMap, 
   659               typename CrossRef>
   660     class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
   661     public:
   662 
   663       CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
   664       
   665       virtual void copy(const Digraph& digraph, const RefMap& refMap) {
   666         typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
   667         for (ItemIt it(digraph); it != INVALID; ++it) {
   668           _cmap.set(refMap[it], it);
   669         }
   670       }
   671 
   672     private:
   673       CrossRef& _cmap;
   674     };
   675 
   676     template <typename Digraph, typename Enable = void>
   677     struct DigraphCopySelector {
   678       template <typename From, typename NodeRefMap, typename ArcRefMap>
   679       static void copy(Digraph &to, const From& from,
   680                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   681         for (typename From::NodeIt it(from); it != INVALID; ++it) {
   682           nodeRefMap[it] = to.addNode();
   683         }
   684         for (typename From::ArcIt it(from); it != INVALID; ++it) {
   685           arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
   686                                           nodeRefMap[from.target(it)]);
   687         }
   688       }
   689     };
   690 
   691     template <typename Digraph>
   692     struct DigraphCopySelector<
   693       Digraph, 
   694       typename enable_if<typename Digraph::BuildTag, void>::type> 
   695     {
   696       template <typename From, typename NodeRefMap, typename ArcRefMap>
   697       static void copy(Digraph &to, const From& from,
   698                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
   699         to.build(from, nodeRefMap, arcRefMap);
   700       }
   701     };
   702 
   703     template <typename Graph, typename Enable = void>
   704     struct GraphCopySelector {
   705       template <typename From, typename NodeRefMap, typename EdgeRefMap>
   706       static void copy(Graph &to, const From& from,
   707                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   708         for (typename From::NodeIt it(from); it != INVALID; ++it) {
   709           nodeRefMap[it] = to.addNode();
   710         }
   711         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
   712           edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
   713 				       nodeRefMap[from.target(it)]);
   714         }
   715       }
   716     };
   717 
   718     template <typename Graph>
   719     struct GraphCopySelector<
   720       Graph, 
   721       typename enable_if<typename Graph::BuildTag, void>::type> 
   722     {
   723       template <typename From, typename NodeRefMap, typename EdgeRefMap>
   724       static void copy(Graph &to, const From& from,
   725                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
   726         to.build(from, nodeRefMap, edgeRefMap);
   727       }
   728     };
   729 
   730     template <typename BpGraph, typename Enable = void>
   731     struct BpGraphCopySelector {
   732       template <typename From, typename RedRefMap, 
   733                 typename BlueRefMap, typename EdgeRefMap>
   734       static void copy(BpGraph &to, const From& from,
   735                        RedRefMap& redRefMap, BlueRefMap& blueRefMap,
   736                        EdgeRefMap& edgeRefMap) {
   737         for (typename From::RedIt it(from); it != INVALID; ++it) {
   738           redRefMap[it] = to.addRed();
   739         }
   740         for (typename From::BlueIt it(from); it != INVALID; ++it) {
   741           blueRefMap[it] = to.addBlue();
   742         }
   743         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
   744           edgeRefMap[it] = to.addArc(redRefMap[from.red(it)], 
   745                                            blueRefMap[from.blue(it)]);
   746         }
   747       }
   748     };
   749 
   750     template <typename BpGraph>
   751     struct BpGraphCopySelector<
   752       BpGraph, 
   753       typename enable_if<typename BpGraph::BuildTag, void>::type> 
   754     {
   755       template <typename From, typename RedRefMap, 
   756                 typename BlueRefMap, typename EdgeRefMap>
   757       static void copy(BpGraph &to, const From& from,
   758                        RedRefMap& redRefMap, BlueRefMap& blueRefMap,
   759                        EdgeRefMap& edgeRefMap) {
   760         to.build(from, redRefMap, blueRefMap, edgeRefMap);
   761       }
   762     };
   763     
   764 
   765   }
   766 
   767   /// \brief Class to copy a digraph.
   768   ///
   769   /// Class to copy a digraph to another digraph (duplicate a digraph). The
   770   /// simplest way of using it is through the \c copyDigraph() function.
   771   template <typename To, typename From>
   772   class DigraphCopy {
   773   private:
   774 
   775     typedef typename From::Node Node;
   776     typedef typename From::NodeIt NodeIt;
   777     typedef typename From::Arc Arc;
   778     typedef typename From::ArcIt ArcIt;
   779 
   780     typedef typename To::Node TNode;
   781     typedef typename To::Arc TArc;
   782 
   783     typedef typename From::template NodeMap<TNode> NodeRefMap;
   784     typedef typename From::template ArcMap<TArc> ArcRefMap;
   785     
   786     
   787   public: 
   788 
   789 
   790     /// \brief Constructor for the DigraphCopy.
   791     ///
   792     /// It copies the content of the \c _from digraph into the
   793     /// \c _to digraph.
   794     DigraphCopy(To& _to, const From& _from) 
   795       : from(_from), to(_to) {}
   796 
   797     /// \brief Destructor of the DigraphCopy
   798     ///
   799     /// Destructor of the DigraphCopy
   800     ~DigraphCopy() {
   801       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
   802         delete nodeMapCopies[i];
   803       }
   804       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
   805         delete arcMapCopies[i];
   806       }
   807 
   808     }
   809 
   810     /// \brief Copies the node references into the given map.
   811     ///
   812     /// Copies the node references into the given map.
   813     template <typename NodeRef>
   814     DigraphCopy& nodeRef(NodeRef& map) {
   815       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node, 
   816                               NodeRefMap, NodeRef>(map));
   817       return *this;
   818     }
   819 
   820     /// \brief Copies the node cross references into the given map.
   821     ///
   822     ///  Copies the node cross references (reverse references) into
   823     ///  the given map.
   824     template <typename NodeCrossRef>
   825     DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
   826       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
   827                               NodeRefMap, NodeCrossRef>(map));
   828       return *this;
   829     }
   830 
   831     /// \brief Make copy of the given map.
   832     ///
   833     /// Makes copy of the given map for the newly created digraph. 
   834     /// The new map's key type is the to digraph's node type,
   835     /// and the copied map's key type is the from digraph's node
   836     /// type.  
   837     template <typename ToMap, typename FromMap>
   838     DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
   839       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node, 
   840                               NodeRefMap, ToMap, FromMap>(tmap, map));
   841       return *this;
   842     }
   843 
   844     /// \brief Make a copy of the given node.
   845     ///
   846     /// Make a copy of the given node.
   847     DigraphCopy& node(TNode& tnode, const Node& snode) {
   848       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node, 
   849                               NodeRefMap, TNode>(tnode, snode));
   850       return *this;
   851     }
   852 
   853     /// \brief Copies the arc references into the given map.
   854     ///
   855     /// Copies the arc references into the given map.
   856     template <typename ArcRef>
   857     DigraphCopy& arcRef(ArcRef& map) {
   858       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc, 
   859                               ArcRefMap, ArcRef>(map));
   860       return *this;
   861     }
   862 
   863     /// \brief Copies the arc cross references into the given map.
   864     ///
   865     ///  Copies the arc cross references (reverse references) into
   866     ///  the given map.
   867     template <typename ArcCrossRef>
   868     DigraphCopy& arcCrossRef(ArcCrossRef& map) {
   869       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
   870                               ArcRefMap, ArcCrossRef>(map));
   871       return *this;
   872     }
   873 
   874     /// \brief Make copy of the given map.
   875     ///
   876     /// Makes copy of the given map for the newly created digraph. 
   877     /// The new map's key type is the to digraph's arc type,
   878     /// and the copied map's key type is the from digraph's arc
   879     /// type.  
   880     template <typename ToMap, typename FromMap>
   881     DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
   882       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc, 
   883                               ArcRefMap, ToMap, FromMap>(tmap, map));
   884       return *this;
   885     }
   886 
   887     /// \brief Make a copy of the given arc.
   888     ///
   889     /// Make a copy of the given arc.
   890     DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
   891       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc, 
   892                               ArcRefMap, TArc>(tarc, sarc));
   893       return *this;
   894     }
   895 
   896     /// \brief Executes the copies.
   897     ///
   898     /// Executes the copies.
   899     void run() {
   900       NodeRefMap nodeRefMap(from);
   901       ArcRefMap arcRefMap(from);
   902       _digraph_utils_bits::DigraphCopySelector<To>::
   903         copy(to, from, nodeRefMap, arcRefMap);
   904       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
   905         nodeMapCopies[i]->copy(from, nodeRefMap);
   906       }
   907       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
   908         arcMapCopies[i]->copy(from, arcRefMap);
   909       }      
   910     }
   911 
   912   protected:
   913 
   914 
   915     const From& from;
   916     To& to;
   917 
   918     std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 
   919     nodeMapCopies;
   920 
   921     std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
   922     arcMapCopies;
   923 
   924   };
   925 
   926   /// \brief Copy a digraph to another digraph.
   927   ///
   928   /// Copy a digraph to another digraph.
   929   /// The usage of the function:
   930   /// 
   931   ///\code
   932   /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
   933   ///\endcode
   934   /// 
   935   /// After the copy the \c nr map will contain the mapping from the
   936   /// nodes of the \c from digraph to the nodes of the \c to digraph and
   937   /// \c ecr will contain the mapping from the arcs of the \c to digraph
   938   /// to the arcs of the \c from digraph.
   939   ///
   940   /// \see DigraphCopy 
   941   template <typename To, typename From>
   942   DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
   943     return DigraphCopy<To, From>(to, from);
   944   }
   945 
   946   /// \brief Class to copy an graph.
   947   ///
   948   /// Class to copy an graph to another digraph (duplicate a digraph).
   949   /// The simplest way of using it is through the \c copyGraph() function.
   950   template <typename To, typename From>
   951   class GraphCopy {
   952   private:
   953 
   954     typedef typename From::Node Node;
   955     typedef typename From::NodeIt NodeIt;
   956     typedef typename From::Arc Arc;
   957     typedef typename From::ArcIt ArcIt;
   958     typedef typename From::Edge Edge;
   959     typedef typename From::EdgeIt EdgeIt;
   960 
   961     typedef typename To::Node TNode;
   962     typedef typename To::Arc TArc;
   963     typedef typename To::Edge TEdge;
   964 
   965     typedef typename From::template NodeMap<TNode> NodeRefMap;
   966     typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
   967 
   968     struct ArcRefMap {
   969       ArcRefMap(const To& _to, const From& _from,
   970                  const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref) 
   971         : to(_to), from(_from), 
   972           edge_ref(_edge_ref), node_ref(_node_ref) {}
   973 
   974       typedef typename From::Arc Key;
   975       typedef typename To::Arc Value;
   976 
   977       Value operator[](const Key& key) const {
   978         bool forward = 
   979           (from.direction(key) == 
   980            (node_ref[from.source(static_cast<const Edge&>(key))] == 
   981             to.source(edge_ref[static_cast<const Edge&>(key)])));
   982 	return to.direct(edge_ref[key], forward); 
   983       }
   984       
   985       const To& to;
   986       const From& from;
   987       const EdgeRefMap& edge_ref;
   988       const NodeRefMap& node_ref;
   989     };
   990 
   991     
   992   public: 
   993 
   994 
   995     /// \brief Constructor for the DigraphCopy.
   996     ///
   997     /// It copies the content of the \c _from digraph into the
   998     /// \c _to digraph.
   999     GraphCopy(To& _to, const From& _from) 
  1000       : from(_from), to(_to) {}
  1001 
  1002     /// \brief Destructor of the DigraphCopy
  1003     ///
  1004     /// Destructor of the DigraphCopy
  1005     ~GraphCopy() {
  1006       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
  1007         delete nodeMapCopies[i];
  1008       }
  1009       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
  1010         delete arcMapCopies[i];
  1011       }
  1012       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
  1013         delete edgeMapCopies[i];
  1014       }
  1015 
  1016     }
  1017 
  1018     /// \brief Copies the node references into the given map.
  1019     ///
  1020     /// Copies the node references into the given map.
  1021     template <typename NodeRef>
  1022     GraphCopy& nodeRef(NodeRef& map) {
  1023       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node, 
  1024                               NodeRefMap, NodeRef>(map));
  1025       return *this;
  1026     }
  1027 
  1028     /// \brief Copies the node cross references into the given map.
  1029     ///
  1030     ///  Copies the node cross references (reverse references) into
  1031     ///  the given map.
  1032     template <typename NodeCrossRef>
  1033     GraphCopy& nodeCrossRef(NodeCrossRef& map) {
  1034       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
  1035                               NodeRefMap, NodeCrossRef>(map));
  1036       return *this;
  1037     }
  1038 
  1039     /// \brief Make copy of the given map.
  1040     ///
  1041     /// Makes copy of the given map for the newly created digraph. 
  1042     /// The new map's key type is the to digraph's node type,
  1043     /// and the copied map's key type is the from digraph's node
  1044     /// type.  
  1045     template <typename ToMap, typename FromMap>
  1046     GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
  1047       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node, 
  1048                               NodeRefMap, ToMap, FromMap>(tmap, map));
  1049       return *this;
  1050     }
  1051 
  1052     /// \brief Make a copy of the given node.
  1053     ///
  1054     /// Make a copy of the given node.
  1055     GraphCopy& node(TNode& tnode, const Node& snode) {
  1056       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node, 
  1057                               NodeRefMap, TNode>(tnode, snode));
  1058       return *this;
  1059     }
  1060 
  1061     /// \brief Copies the arc references into the given map.
  1062     ///
  1063     /// Copies the arc references into the given map.
  1064     template <typename ArcRef>
  1065     GraphCopy& arcRef(ArcRef& map) {
  1066       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc, 
  1067                               ArcRefMap, ArcRef>(map));
  1068       return *this;
  1069     }
  1070 
  1071     /// \brief Copies the arc cross references into the given map.
  1072     ///
  1073     ///  Copies the arc cross references (reverse references) into
  1074     ///  the given map.
  1075     template <typename ArcCrossRef>
  1076     GraphCopy& arcCrossRef(ArcCrossRef& map) {
  1077       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
  1078                               ArcRefMap, ArcCrossRef>(map));
  1079       return *this;
  1080     }
  1081 
  1082     /// \brief Make copy of the given map.
  1083     ///
  1084     /// Makes copy of the given map for the newly created digraph. 
  1085     /// The new map's key type is the to digraph's arc type,
  1086     /// and the copied map's key type is the from digraph's arc
  1087     /// type.  
  1088     template <typename ToMap, typename FromMap>
  1089     GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
  1090       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc, 
  1091                               ArcRefMap, ToMap, FromMap>(tmap, map));
  1092       return *this;
  1093     }
  1094 
  1095     /// \brief Make a copy of the given arc.
  1096     ///
  1097     /// Make a copy of the given arc.
  1098     GraphCopy& arc(TArc& tarc, const Arc& sarc) {
  1099       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc, 
  1100                               ArcRefMap, TArc>(tarc, sarc));
  1101       return *this;
  1102     }
  1103 
  1104     /// \brief Copies the edge references into the given map.
  1105     ///
  1106     /// Copies the edge references into the given map.
  1107     template <typename EdgeRef>
  1108     GraphCopy& edgeRef(EdgeRef& map) {
  1109       edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge, 
  1110                                EdgeRefMap, EdgeRef>(map));
  1111       return *this;
  1112     }
  1113 
  1114     /// \brief Copies the edge cross references into the given map.
  1115     ///
  1116     /// Copies the edge cross references (reverse
  1117     /// references) into the given map.
  1118     template <typename EdgeCrossRef>
  1119     GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
  1120       edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, 
  1121                                Edge, EdgeRefMap, EdgeCrossRef>(map));
  1122       return *this;
  1123     }
  1124 
  1125     /// \brief Make copy of the given map.
  1126     ///
  1127     /// Makes copy of the given map for the newly created digraph. 
  1128     /// The new map's key type is the to digraph's edge type,
  1129     /// and the copied map's key type is the from digraph's edge
  1130     /// type.  
  1131     template <typename ToMap, typename FromMap>
  1132     GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
  1133       edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge, 
  1134                                EdgeRefMap, ToMap, FromMap>(tmap, map));
  1135       return *this;
  1136     }
  1137 
  1138     /// \brief Make a copy of the given edge.
  1139     ///
  1140     /// Make a copy of the given edge.
  1141     GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
  1142       edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge, 
  1143                                EdgeRefMap, TEdge>(tedge, sedge));
  1144       return *this;
  1145     }
  1146 
  1147     /// \brief Executes the copies.
  1148     ///
  1149     /// Executes the copies.
  1150     void run() {
  1151       NodeRefMap nodeRefMap(from);
  1152       EdgeRefMap edgeRefMap(from);
  1153       ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
  1154       _digraph_utils_bits::GraphCopySelector<To>::
  1155         copy(to, from, nodeRefMap, edgeRefMap);
  1156       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
  1157         nodeMapCopies[i]->copy(from, nodeRefMap);
  1158       }
  1159       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
  1160         edgeMapCopies[i]->copy(from, edgeRefMap);
  1161       }
  1162       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
  1163         arcMapCopies[i]->copy(from, arcRefMap);
  1164       }
  1165     }
  1166 
  1167   private:
  1168     
  1169     const From& from;
  1170     To& to;
  1171 
  1172     std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 
  1173     nodeMapCopies;
  1174 
  1175     std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
  1176     arcMapCopies;
  1177 
  1178     std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 
  1179     edgeMapCopies;
  1180 
  1181   };
  1182 
  1183   /// \brief Copy an graph to another digraph.
  1184   ///
  1185   /// Copy an graph to another digraph.
  1186   /// The usage of the function:
  1187   /// 
  1188   ///\code
  1189   /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
  1190   ///\endcode
  1191   /// 
  1192   /// After the copy the \c nr map will contain the mapping from the
  1193   /// nodes of the \c from digraph to the nodes of the \c to digraph and
  1194   /// \c ecr will contain the mapping from the arcs of the \c to digraph
  1195   /// to the arcs of the \c from digraph.
  1196   ///
  1197   /// \see GraphCopy 
  1198   template <typename To, typename From>
  1199   GraphCopy<To, From> 
  1200   copyGraph(To& to, const From& from) {
  1201     return GraphCopy<To, From>(to, from);
  1202   }
  1203 
  1204   /// \brief Class to copy a bipartite digraph.
  1205   ///
  1206   /// Class to copy a bipartite digraph to another digraph
  1207   /// (duplicate a digraph).  The simplest way of using it is through
  1208   /// the \c copyBpGraph() function.
  1209   template <typename To, typename From>
  1210   class BpGraphCopy {
  1211   private:
  1212 
  1213     typedef typename From::Node Node;
  1214     typedef typename From::Red Red;
  1215     typedef typename From::Blue Blue;
  1216     typedef typename From::NodeIt NodeIt;
  1217     typedef typename From::Arc Arc;
  1218     typedef typename From::ArcIt ArcIt;
  1219     typedef typename From::Edge Edge;
  1220     typedef typename From::EdgeIt EdgeIt;
  1221 
  1222     typedef typename To::Node TNode;
  1223     typedef typename To::Arc TArc;
  1224     typedef typename To::Edge TEdge;
  1225 
  1226     typedef typename From::template RedMap<TNode> RedRefMap;
  1227     typedef typename From::template BlueMap<TNode> BlueRefMap;
  1228     typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
  1229 
  1230     struct NodeRefMap {
  1231       NodeRefMap(const From& _from, const RedRefMap& _red_ref,
  1232                  const BlueRefMap& _blue_ref)
  1233         : from(_from), red_ref(_red_ref), blue_ref(_blue_ref) {}
  1234 
  1235       typedef typename From::Node Key;
  1236       typedef typename To::Node Value;
  1237 
  1238       Value operator[](const Key& key) const {
  1239 	return from.red(key) ? red_ref[key] : blue_ref[key]; 
  1240       }
  1241       
  1242       const From& from;
  1243       const RedRefMap& red_ref;
  1244       const BlueRefMap& blue_ref;
  1245     };
  1246 
  1247     struct ArcRefMap {
  1248       ArcRefMap(const To& _to, const From& _from,
  1249                  const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref) 
  1250         : to(_to), from(_from), 
  1251           edge_ref(_edge_ref), node_ref(_node_ref) {}
  1252 
  1253       typedef typename From::Arc Key;
  1254       typedef typename To::Arc Value;
  1255 
  1256       Value operator[](const Key& key) const {
  1257         bool forward = 
  1258           (from.direction(key) == 
  1259            (node_ref[from.source(static_cast<const Edge&>(key))] == 
  1260             to.source(edge_ref[static_cast<const Edge&>(key)])));
  1261 	return to.direct(edge_ref[key], forward); 
  1262       }
  1263       
  1264       const To& to;
  1265       const From& from;
  1266       const EdgeRefMap& edge_ref;
  1267       const NodeRefMap& node_ref;
  1268     };
  1269     
  1270   public: 
  1271 
  1272 
  1273     /// \brief Constructor for the DigraphCopy.
  1274     ///
  1275     /// It copies the content of the \c _from digraph into the
  1276     /// \c _to digraph.
  1277     BpGraphCopy(To& _to, const From& _from) 
  1278       : from(_from), to(_to) {}
  1279 
  1280     /// \brief Destructor of the DigraphCopy
  1281     ///
  1282     /// Destructor of the DigraphCopy
  1283     ~BpGraphCopy() {
  1284       for (int i = 0; i < int(redMapCopies.size()); ++i) {
  1285         delete redMapCopies[i];
  1286       }
  1287       for (int i = 0; i < int(blueMapCopies.size()); ++i) {
  1288         delete blueMapCopies[i];
  1289       }
  1290       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
  1291         delete nodeMapCopies[i];
  1292       }
  1293       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
  1294         delete arcMapCopies[i];
  1295       }
  1296       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
  1297         delete edgeMapCopies[i];
  1298       }
  1299 
  1300     }
  1301 
  1302     /// \brief Copies the A-node references into the given map.
  1303     ///
  1304     /// Copies the A-node references into the given map.
  1305     template <typename RedRef>
  1306     BpGraphCopy& redRef(RedRef& map) {
  1307       redMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Red, 
  1308                                RedRefMap, RedRef>(map));
  1309       return *this;
  1310     }
  1311 
  1312     /// \brief Copies the A-node cross references into the given map.
  1313     ///
  1314     /// Copies the A-node cross references (reverse references) into
  1315     /// the given map.
  1316     template <typename RedCrossRef>
  1317     BpGraphCopy& redCrossRef(RedCrossRef& map) {
  1318       redMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, 
  1319                                Red, RedRefMap, RedCrossRef>(map));
  1320       return *this;
  1321     }
  1322 
  1323     /// \brief Make copy of the given A-node map.
  1324     ///
  1325     /// Makes copy of the given map for the newly created digraph. 
  1326     /// The new map's key type is the to digraph's node type,
  1327     /// and the copied map's key type is the from digraph's node
  1328     /// type.  
  1329     template <typename ToMap, typename FromMap>
  1330     BpGraphCopy& redMap(ToMap& tmap, const FromMap& map) {
  1331       redMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Red, 
  1332                                RedRefMap, ToMap, FromMap>(tmap, map));
  1333       return *this;
  1334     }
  1335 
  1336     /// \brief Copies the B-node references into the given map.
  1337     ///
  1338     /// Copies the B-node references into the given map.
  1339     template <typename BlueRef>
  1340     BpGraphCopy& blueRef(BlueRef& map) {
  1341       blueMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Blue, 
  1342                                BlueRefMap, BlueRef>(map));
  1343       return *this;
  1344     }
  1345 
  1346     /// \brief Copies the B-node cross references into the given map.
  1347     ///
  1348     ///  Copies the B-node cross references (reverse references) into
  1349     ///  the given map.
  1350     template <typename BlueCrossRef>
  1351     BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
  1352       blueMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, 
  1353                               Blue, BlueRefMap, BlueCrossRef>(map));
  1354       return *this;
  1355     }
  1356 
  1357     /// \brief Make copy of the given B-node map.
  1358     ///
  1359     /// Makes copy of the given map for the newly created digraph. 
  1360     /// The new map's key type is the to digraph's node type,
  1361     /// and the copied map's key type is the from digraph's node
  1362     /// type.  
  1363     template <typename ToMap, typename FromMap>
  1364     BpGraphCopy& blueMap(ToMap& tmap, const FromMap& map) {
  1365       blueMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Blue, 
  1366                                BlueRefMap, ToMap, FromMap>(tmap, map));
  1367       return *this;
  1368     }
  1369     /// \brief Copies the node references into the given map.
  1370     ///
  1371     /// Copies the node references into the given map.
  1372     template <typename NodeRef>
  1373     BpGraphCopy& nodeRef(NodeRef& map) {
  1374       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node, 
  1375                               NodeRefMap, NodeRef>(map));
  1376       return *this;
  1377     }
  1378 
  1379     /// \brief Copies the node cross references into the given map.
  1380     ///
  1381     ///  Copies the node cross references (reverse references) into
  1382     ///  the given map.
  1383     template <typename NodeCrossRef>
  1384     BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
  1385       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
  1386                               NodeRefMap, NodeCrossRef>(map));
  1387       return *this;
  1388     }
  1389 
  1390     /// \brief Make copy of the given map.
  1391     ///
  1392     /// Makes copy of the given map for the newly created digraph. 
  1393     /// The new map's key type is the to digraph's node type,
  1394     /// and the copied map's key type is the from digraph's node
  1395     /// type.  
  1396     template <typename ToMap, typename FromMap>
  1397     BpGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
  1398       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node, 
  1399                               NodeRefMap, ToMap, FromMap>(tmap, map));
  1400       return *this;
  1401     }
  1402 
  1403     /// \brief Make a copy of the given node.
  1404     ///
  1405     /// Make a copy of the given node.
  1406     BpGraphCopy& node(TNode& tnode, const Node& snode) {
  1407       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node, 
  1408                               NodeRefMap, TNode>(tnode, snode));
  1409       return *this;
  1410     }
  1411 
  1412     /// \brief Copies the arc references into the given map.
  1413     ///
  1414     /// Copies the arc references into the given map.
  1415     template <typename ArcRef>
  1416     BpGraphCopy& arcRef(ArcRef& map) {
  1417       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc, 
  1418                               ArcRefMap, ArcRef>(map));
  1419       return *this;
  1420     }
  1421 
  1422     /// \brief Copies the arc cross references into the given map.
  1423     ///
  1424     ///  Copies the arc cross references (reverse references) into
  1425     ///  the given map.
  1426     template <typename ArcCrossRef>
  1427     BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
  1428       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
  1429                               ArcRefMap, ArcCrossRef>(map));
  1430       return *this;
  1431     }
  1432 
  1433     /// \brief Make copy of the given map.
  1434     ///
  1435     /// Makes copy of the given map for the newly created digraph. 
  1436     /// The new map's key type is the to digraph's arc type,
  1437     /// and the copied map's key type is the from digraph's arc
  1438     /// type.  
  1439     template <typename ToMap, typename FromMap>
  1440     BpGraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
  1441       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc, 
  1442                               ArcRefMap, ToMap, FromMap>(tmap, map));
  1443       return *this;
  1444     }
  1445 
  1446     /// \brief Make a copy of the given arc.
  1447     ///
  1448     /// Make a copy of the given arc.
  1449     BpGraphCopy& arc(TArc& tarc, const Arc& sarc) {
  1450       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc, 
  1451                               ArcRefMap, TArc>(tarc, sarc));
  1452       return *this;
  1453     }
  1454 
  1455     /// \brief Copies the edge references into the given map.
  1456     ///
  1457     /// Copies the edge references into the given map.
  1458     template <typename EdgeRef>
  1459     BpGraphCopy& edgeRef(EdgeRef& map) {
  1460       edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge, 
  1461                                EdgeRefMap, EdgeRef>(map));
  1462       return *this;
  1463     }
  1464 
  1465     /// \brief Copies the edge cross references into the given map.
  1466     ///
  1467     /// Copies the edge cross references (reverse
  1468     /// references) into the given map.
  1469     template <typename EdgeCrossRef>
  1470     BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
  1471       edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, 
  1472                                Edge, EdgeRefMap, EdgeCrossRef>(map));
  1473       return *this;
  1474     }
  1475 
  1476     /// \brief Make copy of the given map.
  1477     ///
  1478     /// Makes copy of the given map for the newly created digraph. 
  1479     /// The new map's key type is the to digraph's edge type,
  1480     /// and the copied map's key type is the from digraph's edge
  1481     /// type.  
  1482     template <typename ToMap, typename FromMap>
  1483     BpGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
  1484       edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge, 
  1485                                EdgeRefMap, ToMap, FromMap>(tmap, map));
  1486       return *this;
  1487     }
  1488 
  1489     /// \brief Make a copy of the given edge.
  1490     ///
  1491     /// Make a copy of the given edge.
  1492     BpGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
  1493       edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge, 
  1494                                EdgeRefMap, TEdge>(tedge, sedge));
  1495       return *this;
  1496     }
  1497 
  1498     /// \brief Executes the copies.
  1499     ///
  1500     /// Executes the copies.
  1501     void run() {
  1502       RedRefMap redRefMap(from);
  1503       BlueRefMap blueRefMap(from);
  1504       NodeRefMap nodeRefMap(from, redRefMap, blueRefMap);
  1505       EdgeRefMap edgeRefMap(from);
  1506       ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
  1507       _digraph_utils_bits::BpGraphCopySelector<To>::
  1508         copy(to, from, redRefMap, blueRefMap, edgeRefMap);
  1509       for (int i = 0; i < int(redMapCopies.size()); ++i) {
  1510         redMapCopies[i]->copy(from, redRefMap);
  1511       }
  1512       for (int i = 0; i < int(blueMapCopies.size()); ++i) {
  1513         blueMapCopies[i]->copy(from, blueRefMap);
  1514       }
  1515       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
  1516         nodeMapCopies[i]->copy(from, nodeRefMap);
  1517       }
  1518       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
  1519         edgeMapCopies[i]->copy(from, edgeRefMap);
  1520       }
  1521       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
  1522         arcMapCopies[i]->copy(from, arcRefMap);
  1523       }
  1524     }
  1525 
  1526   private:
  1527     
  1528     const From& from;
  1529     To& to;
  1530 
  1531     std::vector<_digraph_utils_bits::MapCopyBase<From, Red, RedRefMap>* > 
  1532     redMapCopies;
  1533 
  1534     std::vector<_digraph_utils_bits::MapCopyBase<From, Blue, BlueRefMap>* > 
  1535     blueMapCopies;
  1536 
  1537     std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 
  1538     nodeMapCopies;
  1539 
  1540     std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
  1541     arcMapCopies;
  1542 
  1543     std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 
  1544     edgeMapCopies;
  1545 
  1546   };
  1547 
  1548   /// \brief Copy a bipartite digraph to another digraph.
  1549   ///
  1550   /// Copy a bipartite digraph to another digraph.
  1551   /// The usage of the function:
  1552   /// 
  1553   ///\code
  1554   /// copyBpGraph(trg, src).redRef(anr).arcCrossRef(ecr).run();
  1555   ///\endcode
  1556   /// 
  1557   /// After the copy the \c nr map will contain the mapping from the
  1558   /// nodes of the \c from digraph to the nodes of the \c to digraph and
  1559   /// \c ecr will contain the mapping from the arcs of the \c to digraph
  1560   /// to the arcs of the \c from digraph.
  1561   ///
  1562   /// \see BpGraphCopy
  1563   template <typename To, typename From>
  1564   BpGraphCopy<To, From> 
  1565   copyBpGraph(To& to, const From& from) {
  1566     return BpGraphCopy<To, From>(to, from);
  1567   }
  1568 
  1569 
  1570   /// @}
  1571 
  1572   /// \addtogroup digraph_maps
  1573   /// @{
  1574 
  1575   /// Provides an immutable and unique id for each item in the digraph.
  1576 
  1577   /// The IdMap class provides a unique and immutable id for each item of the
  1578   /// same type (e.g. node) in the digraph. This id is <ul><li>\b unique:
  1579   /// different items (nodes) get different ids <li>\b immutable: the id of an
  1580   /// item (node) does not change (even if you delete other nodes).  </ul>
  1581   /// Through this map you get access (i.e. can read) the inner id values of
  1582   /// the items stored in the digraph. This map can be inverted with its member
  1583   /// class \c InverseMap.
  1584   ///
  1585   template <typename _Digraph, typename _Item>
  1586   class IdMap {
  1587   public:
  1588     typedef _Digraph Digraph;
  1589     typedef int Value;
  1590     typedef _Item Item;
  1591     typedef _Item Key;
  1592 
  1593     /// \brief Constructor.
  1594     ///
  1595     /// Constructor of the map.
  1596     explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}
  1597 
  1598     /// \brief Gives back the \e id of the item.
  1599     ///
  1600     /// Gives back the immutable and unique \e id of the item.
  1601     int operator[](const Item& item) const { return digraph->id(item);}
  1602 
  1603     /// \brief Gives back the item by its id.
  1604     ///
  1605     /// Gives back the item by its id.
  1606     Item operator()(int id) { return digraph->fromId(id, Item()); }
  1607 
  1608   private:
  1609     const Digraph* digraph;
  1610 
  1611   public:
  1612 
  1613     /// \brief The class represents the inverse of its owner (IdMap).
  1614     ///
  1615     /// The class represents the inverse of its owner (IdMap).
  1616     /// \see inverse()
  1617     class InverseMap {
  1618     public:
  1619 
  1620       /// \brief Constructor.
  1621       ///
  1622       /// Constructor for creating an id-to-item map.
  1623       explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}
  1624 
  1625       /// \brief Constructor.
  1626       ///
  1627       /// Constructor for creating an id-to-item map.
  1628       explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}
  1629 
  1630       /// \brief Gives back the given item from its id.
  1631       ///
  1632       /// Gives back the given item from its id.
  1633       /// 
  1634       Item operator[](int id) const { return digraph->fromId(id, Item());}
  1635 
  1636     private:
  1637       const Digraph* digraph;
  1638     };
  1639 
  1640     /// \brief Gives back the inverse of the map.
  1641     ///
  1642     /// Gives back the inverse of the IdMap.
  1643     InverseMap inverse() const { return InverseMap(*digraph);} 
  1644 
  1645   };
  1646 
  1647   
  1648   /// \brief General invertable digraph-map type.
  1649 
  1650   /// This type provides simple invertable digraph-maps. 
  1651   /// The InvertableMap wraps an arbitrary ReadWriteMap 
  1652   /// and if a key is set to a new value then store it
  1653   /// in the inverse map.
  1654   ///
  1655   /// The values of the map can be accessed
  1656   /// with stl compatible forward iterator.
  1657   ///
  1658   /// \param _Digraph The digraph type.
  1659   /// \param _Item The item type of the digraph.
  1660   /// \param _Value The value type of the map.
  1661   ///
  1662   /// \see IterableValueMap
  1663   template <typename _Digraph, typename _Item, typename _Value>
  1664   class InvertableMap : protected DefaultMap<_Digraph, _Item, _Value> {
  1665   private:
  1666     
  1667     typedef DefaultMap<_Digraph, _Item, _Value> Map;
  1668     typedef _Digraph Digraph;
  1669 
  1670     typedef std::map<_Value, _Item> Container;
  1671     Container invMap;    
  1672 
  1673   public:
  1674  
  1675     /// The key type of InvertableMap (Node, Arc, Edge).
  1676     typedef typename Map::Key Key;
  1677     /// The value type of the InvertableMap.
  1678     typedef typename Map::Value Value;
  1679 
  1680 
  1681 
  1682     /// \brief Constructor.
  1683     ///
  1684     /// Construct a new InvertableMap for the digraph.
  1685     ///
  1686     explicit InvertableMap(const Digraph& digraph) : Map(digraph) {} 
  1687 
  1688     /// \brief Forward iterator for values.
  1689     ///
  1690     /// This iterator is an stl compatible forward
  1691     /// iterator on the values of the map. The values can
  1692     /// be accessed in the [beginValue, endValue) range.
  1693     ///
  1694     class ValueIterator 
  1695       : public std::iterator<std::forward_iterator_tag, Value> {
  1696       friend class InvertableMap;
  1697     private:
  1698       ValueIterator(typename Container::const_iterator _it) 
  1699         : it(_it) {}
  1700     public:
  1701       
  1702       ValueIterator() {}
  1703 
  1704       ValueIterator& operator++() { ++it; return *this; }
  1705       ValueIterator operator++(int) { 
  1706         ValueIterator tmp(*this); 
  1707         operator++();
  1708         return tmp; 
  1709       }
  1710 
  1711       const Value& operator*() const { return it->first; }
  1712       const Value* operator->() const { return &(it->first); }
  1713 
  1714       bool operator==(ValueIterator jt) const { return it == jt.it; }
  1715       bool operator!=(ValueIterator jt) const { return it != jt.it; }
  1716       
  1717     private:
  1718       typename Container::const_iterator it;
  1719     };
  1720 
  1721     /// \brief Returns an iterator to the first value.
  1722     ///
  1723     /// Returns an stl compatible iterator to the 
  1724     /// first value of the map. The values of the
  1725     /// map can be accessed in the [beginValue, endValue)
  1726     /// range.
  1727     ValueIterator beginValue() const {
  1728       return ValueIterator(invMap.begin());
  1729     }
  1730 
  1731     /// \brief Returns an iterator after the last value.
  1732     ///
  1733     /// Returns an stl compatible iterator after the 
  1734     /// last value of the map. The values of the
  1735     /// map can be accessed in the [beginValue, endValue)
  1736     /// range.
  1737     ValueIterator endValue() const {
  1738       return ValueIterator(invMap.end());
  1739     }
  1740     
  1741     /// \brief The setter function of the map.
  1742     ///
  1743     /// Sets the mapped value.
  1744     void set(const Key& key, const Value& val) {
  1745       Value oldval = Map::operator[](key);
  1746       typename Container::iterator it = invMap.find(oldval);
  1747       if (it != invMap.end() && it->second == key) {
  1748 	invMap.erase(it);
  1749       }      
  1750       invMap.insert(make_pair(val, key));
  1751       Map::set(key, val);
  1752     }
  1753 
  1754     /// \brief The getter function of the map.
  1755     ///
  1756     /// It gives back the value associated with the key.
  1757     typename MapTraits<Map>::ConstReturnValue 
  1758     operator[](const Key& key) const {
  1759       return Map::operator[](key);
  1760     }
  1761 
  1762     /// \brief Gives back the item by its value.
  1763     ///
  1764     /// Gives back the item by its value.
  1765     Key operator()(const Value& key) const {
  1766       typename Container::const_iterator it = invMap.find(key);
  1767       return it != invMap.end() ? it->second : INVALID;
  1768     }
  1769 
  1770   protected:
  1771 
  1772     /// \brief Erase the key from the map.
  1773     ///
  1774     /// Erase the key to the map. It is called by the
  1775     /// \c AlterationNotifier.
  1776     virtual void erase(const Key& key) {
  1777       Value val = Map::operator[](key);
  1778       typename Container::iterator it = invMap.find(val);
  1779       if (it != invMap.end() && it->second == key) {
  1780 	invMap.erase(it);
  1781       }
  1782       Map::erase(key);
  1783     }
  1784 
  1785     /// \brief Erase more keys from the map.
  1786     ///
  1787     /// Erase more keys from the map. It is called by the
  1788     /// \c AlterationNotifier.
  1789     virtual void erase(const std::vector<Key>& keys) {
  1790       for (int i = 0; i < int(keys.size()); ++i) {
  1791 	Value val = Map::operator[](keys[i]);
  1792 	typename Container::iterator it = invMap.find(val);
  1793 	if (it != invMap.end() && it->second == keys[i]) {
  1794 	  invMap.erase(it);
  1795 	}
  1796       }
  1797       Map::erase(keys);
  1798     }
  1799 
  1800     /// \brief Clear the keys from the map and inverse map.
  1801     ///
  1802     /// Clear the keys from the map and inverse map. It is called by the
  1803     /// \c AlterationNotifier.
  1804     virtual void clear() {
  1805       invMap.clear();
  1806       Map::clear();
  1807     }
  1808 
  1809   public:
  1810 
  1811     /// \brief The inverse map type.
  1812     ///
  1813     /// The inverse of this map. The subscript operator of the map
  1814     /// gives back always the item what was last assigned to the value. 
  1815     class InverseMap {
  1816     public:
  1817       /// \brief Constructor of the InverseMap.
  1818       ///
  1819       /// Constructor of the InverseMap.
  1820       explicit InverseMap(const InvertableMap& _inverted) 
  1821         : inverted(_inverted) {}
  1822 
  1823       /// The value type of the InverseMap.
  1824       typedef typename InvertableMap::Key Value;
  1825       /// The key type of the InverseMap.
  1826       typedef typename InvertableMap::Value Key; 
  1827 
  1828       /// \brief Subscript operator. 
  1829       ///
  1830       /// Subscript operator. It gives back always the item 
  1831       /// what was last assigned to the value.
  1832       Value operator[](const Key& key) const {
  1833 	return inverted(key);
  1834       }
  1835       
  1836     private:
  1837       const InvertableMap& inverted;
  1838     };
  1839 
  1840     /// \brief It gives back the just readable inverse map.
  1841     ///
  1842     /// It gives back the just readable inverse map.
  1843     InverseMap inverse() const {
  1844       return InverseMap(*this);
  1845     } 
  1846 
  1847 
  1848     
  1849   };
  1850 
  1851   /// \brief Provides a mutable, continuous and unique descriptor for each 
  1852   /// item in the digraph.
  1853   ///
  1854   /// The DescriptorMap class provides a unique and continuous (but mutable)
  1855   /// descriptor (id) for each item of the same type (e.g. node) in the
  1856   /// digraph. This id is <ul><li>\b unique: different items (nodes) get
  1857   /// different ids <li>\b continuous: the range of the ids is the set of
  1858   /// integers between 0 and \c n-1, where \c n is the number of the items of
  1859   /// this type (e.g. nodes) (so the id of a node can change if you delete an
  1860   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  1861   /// with its member class \c InverseMap.
  1862   ///
  1863   /// \param _Digraph The digraph class the \c DescriptorMap belongs to.
  1864   /// \param _Item The Item is the Key of the Map. It may be Node, Arc or 
  1865   /// Edge.
  1866   template <typename _Digraph, typename _Item>
  1867   class DescriptorMap : protected DefaultMap<_Digraph, _Item, int> {
  1868 
  1869     typedef _Item Item;
  1870     typedef DefaultMap<_Digraph, _Item, int> Map;
  1871 
  1872   public:
  1873     /// The digraph class of DescriptorMap.
  1874     typedef _Digraph Digraph;
  1875 
  1876     /// The key type of DescriptorMap (Node, Arc, Edge).
  1877     typedef typename Map::Key Key;
  1878     /// The value type of DescriptorMap.
  1879     typedef typename Map::Value Value;
  1880 
  1881     /// \brief Constructor.
  1882     ///
  1883     /// Constructor for descriptor map.
  1884     explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {
  1885       Item it;
  1886       const typename Map::Notifier* nf = Map::notifier(); 
  1887       for (nf->first(it); it != INVALID; nf->next(it)) {
  1888 	Map::set(it, invMap.size());
  1889 	invMap.push_back(it);	
  1890       }      
  1891     }
  1892 
  1893   protected:
  1894 
  1895     /// \brief Add a new key to the map.
  1896     ///
  1897     /// Add a new key to the map. It is called by the
  1898     /// \c AlterationNotifier.
  1899     virtual void add(const Item& item) {
  1900       Map::add(item);
  1901       Map::set(item, invMap.size());
  1902       invMap.push_back(item);
  1903     }
  1904 
  1905     /// \brief Add more new keys to the map.
  1906     ///
  1907     /// Add more new keys to the map. It is called by the
  1908     /// \c AlterationNotifier.
  1909     virtual void add(const std::vector<Item>& items) {
  1910       Map::add(items);
  1911       for (int i = 0; i < int(items.size()); ++i) {
  1912 	Map::set(items[i], invMap.size());
  1913 	invMap.push_back(items[i]);
  1914       }
  1915     }
  1916 
  1917     /// \brief Erase the key from the map.
  1918     ///
  1919     /// Erase the key from the map. It is called by the
  1920     /// \c AlterationNotifier.
  1921     virtual void erase(const Item& item) {
  1922       Map::set(invMap.back(), Map::operator[](item));
  1923       invMap[Map::operator[](item)] = invMap.back();
  1924       invMap.pop_back();
  1925       Map::erase(item);
  1926     }
  1927 
  1928     /// \brief Erase more keys from the map.
  1929     ///
  1930     /// Erase more keys from the map. It is called by the
  1931     /// \c AlterationNotifier.
  1932     virtual void erase(const std::vector<Item>& items) {
  1933       for (int i = 0; i < int(items.size()); ++i) {
  1934 	Map::set(invMap.back(), Map::operator[](items[i]));
  1935 	invMap[Map::operator[](items[i])] = invMap.back();
  1936 	invMap.pop_back();
  1937       }
  1938       Map::erase(items);
  1939     }
  1940 
  1941     /// \brief Build the unique map.
  1942     ///
  1943     /// Build the unique map. It is called by the
  1944     /// \c AlterationNotifier.
  1945     virtual void build() {
  1946       Map::build();
  1947       Item it;
  1948       const typename Map::Notifier* nf = Map::notifier(); 
  1949       for (nf->first(it); it != INVALID; nf->next(it)) {
  1950 	Map::set(it, invMap.size());
  1951 	invMap.push_back(it);	
  1952       }      
  1953     }
  1954     
  1955     /// \brief Clear the keys from the map.
  1956     ///
  1957     /// Clear the keys from the map. It is called by the
  1958     /// \c AlterationNotifier.
  1959     virtual void clear() {
  1960       invMap.clear();
  1961       Map::clear();
  1962     }
  1963 
  1964   public:
  1965 
  1966     /// \brief Returns the maximal value plus one.
  1967     ///
  1968     /// Returns the maximal value plus one in the map.
  1969     unsigned int size() const {
  1970       return invMap.size();
  1971     }
  1972 
  1973     /// \brief Swaps the position of the two items in the map.
  1974     ///
  1975     /// Swaps the position of the two items in the map.
  1976     void swap(const Item& p, const Item& q) {
  1977       int pi = Map::operator[](p);
  1978       int qi = Map::operator[](q);
  1979       Map::set(p, qi);
  1980       invMap[qi] = p;
  1981       Map::set(q, pi);
  1982       invMap[pi] = q;
  1983     }
  1984 
  1985     /// \brief Gives back the \e descriptor of the item.
  1986     ///
  1987     /// Gives back the mutable and unique \e descriptor of the map.
  1988     int operator[](const Item& item) const {
  1989       return Map::operator[](item);
  1990     }
  1991 
  1992     /// \brief Gives back the item by its descriptor.
  1993     ///
  1994     /// Gives back th item by its descriptor.
  1995     Item operator()(int id) const {
  1996       return invMap[id];
  1997     }
  1998     
  1999   private:
  2000 
  2001     typedef std::vector<Item> Container;
  2002     Container invMap;
  2003 
  2004   public:
  2005     /// \brief The inverse map type of DescriptorMap.
  2006     ///
  2007     /// The inverse map type of DescriptorMap.
  2008     class InverseMap {
  2009     public:
  2010       /// \brief Constructor of the InverseMap.
  2011       ///
  2012       /// Constructor of the InverseMap.
  2013       explicit InverseMap(const DescriptorMap& _inverted) 
  2014 	: inverted(_inverted) {}
  2015 
  2016 
  2017       /// The value type of the InverseMap.
  2018       typedef typename DescriptorMap::Key Value;
  2019       /// The key type of the InverseMap.
  2020       typedef typename DescriptorMap::Value Key; 
  2021 
  2022       /// \brief Subscript operator. 
  2023       ///
  2024       /// Subscript operator. It gives back the item 
  2025       /// that the descriptor belongs to currently.
  2026       Value operator[](const Key& key) const {
  2027 	return inverted(key);
  2028       }
  2029 
  2030       /// \brief Size of the map.
  2031       ///
  2032       /// Returns the size of the map.
  2033       unsigned int size() const {
  2034 	return inverted.size();
  2035       }
  2036       
  2037     private:
  2038       const DescriptorMap& inverted;
  2039     };
  2040 
  2041     /// \brief Gives back the inverse of the map.
  2042     ///
  2043     /// Gives back the inverse of the map.
  2044     const InverseMap inverse() const {
  2045       return InverseMap(*this);
  2046     }
  2047   };
  2048 
  2049   /// \brief Returns the source of the given arc.
  2050   ///
  2051   /// The SourceMap gives back the source Node of the given arc. 
  2052   /// \see TargetMap
  2053   /// \author Balazs Dezso
  2054   template <typename Digraph>
  2055   class SourceMap {
  2056   public:
  2057 
  2058     typedef typename Digraph::Node Value;
  2059     typedef typename Digraph::Arc Key;
  2060 
  2061     /// \brief Constructor
  2062     ///
  2063     /// Constructor
  2064     /// \param _digraph The digraph that the map belongs to.
  2065     explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}
  2066 
  2067     /// \brief The subscript operator.
  2068     ///
  2069     /// The subscript operator.
  2070     /// \param arc The arc 
  2071     /// \return The source of the arc 
  2072     Value operator[](const Key& arc) const {
  2073       return digraph.source(arc);
  2074     }
  2075 
  2076   private:
  2077     const Digraph& digraph;
  2078   };
  2079 
  2080   /// \brief Returns a \ref SourceMap class.
  2081   ///
  2082   /// This function just returns an \ref SourceMap class.
  2083   /// \relates SourceMap
  2084   template <typename Digraph>
  2085   inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
  2086     return SourceMap<Digraph>(digraph);
  2087   } 
  2088 
  2089   /// \brief Returns the target of the given arc.
  2090   ///
  2091   /// The TargetMap gives back the target Node of the given arc. 
  2092   /// \see SourceMap
  2093   /// \author Balazs Dezso
  2094   template <typename Digraph>
  2095   class TargetMap {
  2096   public:
  2097 
  2098     typedef typename Digraph::Node Value;
  2099     typedef typename Digraph::Arc Key;
  2100 
  2101     /// \brief Constructor
  2102     ///
  2103     /// Constructor
  2104     /// \param _digraph The digraph that the map belongs to.
  2105     explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}
  2106 
  2107     /// \brief The subscript operator.
  2108     ///
  2109     /// The subscript operator.
  2110     /// \param e The arc 
  2111     /// \return The target of the arc 
  2112     Value operator[](const Key& e) const {
  2113       return digraph.target(e);
  2114     }
  2115 
  2116   private:
  2117     const Digraph& digraph;
  2118   };
  2119 
  2120   /// \brief Returns a \ref TargetMap class.
  2121   ///
  2122   /// This function just returns a \ref TargetMap class.
  2123   /// \relates TargetMap
  2124   template <typename Digraph>
  2125   inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
  2126     return TargetMap<Digraph>(digraph);
  2127   }
  2128 
  2129   /// \brief Returns the "forward" directed arc view of an edge.
  2130   ///
  2131   /// Returns the "forward" directed arc view of an edge.
  2132   /// \see BackwardMap
  2133   /// \author Balazs Dezso
  2134   template <typename Digraph>
  2135   class ForwardMap {
  2136   public:
  2137 
  2138     typedef typename Digraph::Arc Value;
  2139     typedef typename Digraph::Edge Key;
  2140 
  2141     /// \brief Constructor
  2142     ///
  2143     /// Constructor
  2144     /// \param _digraph The digraph that the map belongs to.
  2145     explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}
  2146 
  2147     /// \brief The subscript operator.
  2148     ///
  2149     /// The subscript operator.
  2150     /// \param key An edge 
  2151     /// \return The "forward" directed arc view of edge 
  2152     Value operator[](const Key& key) const {
  2153       return digraph.direct(key, true);
  2154     }
  2155 
  2156   private:
  2157     const Digraph& digraph;
  2158   };
  2159 
  2160   /// \brief Returns a \ref ForwardMap class.
  2161   ///
  2162   /// This function just returns an \ref ForwardMap class.
  2163   /// \relates ForwardMap
  2164   template <typename Digraph>
  2165   inline ForwardMap<Digraph> forwardMap(const Digraph& digraph) {
  2166     return ForwardMap<Digraph>(digraph);
  2167   }
  2168 
  2169   /// \brief Returns the "backward" directed arc view of an edge.
  2170   ///
  2171   /// Returns the "backward" directed arc view of an edge.
  2172   /// \see ForwardMap
  2173   /// \author Balazs Dezso
  2174   template <typename Digraph>
  2175   class BackwardMap {
  2176   public:
  2177 
  2178     typedef typename Digraph::Arc Value;
  2179     typedef typename Digraph::Edge Key;
  2180 
  2181     /// \brief Constructor
  2182     ///
  2183     /// Constructor
  2184     /// \param _digraph The digraph that the map belongs to.
  2185     explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}
  2186 
  2187     /// \brief The subscript operator.
  2188     ///
  2189     /// The subscript operator.
  2190     /// \param key An edge 
  2191     /// \return The "backward" directed arc view of edge 
  2192     Value operator[](const Key& key) const {
  2193       return digraph.direct(key, false);
  2194     }
  2195 
  2196   private:
  2197     const Digraph& digraph;
  2198   };
  2199 
  2200   /// \brief Returns a \ref BackwardMap class
  2201 
  2202   /// This function just returns a \ref BackwardMap class.
  2203   /// \relates BackwardMap
  2204   template <typename Digraph>
  2205   inline BackwardMap<Digraph> backwardMap(const Digraph& digraph) {
  2206     return BackwardMap<Digraph>(digraph);
  2207   }
  2208 
  2209   /// \brief Potential difference map
  2210   ///
  2211   /// If there is an potential map on the nodes then we
  2212   /// can get an arc map as we get the substraction of the
  2213   /// values of the target and source.
  2214   template <typename Digraph, typename NodeMap>
  2215   class PotentialDifferenceMap {
  2216   public:
  2217     typedef typename Digraph::Arc Key;
  2218     typedef typename NodeMap::Value Value;
  2219 
  2220     /// \brief Constructor
  2221     ///
  2222     /// Contructor of the map
  2223     explicit PotentialDifferenceMap(const Digraph& _digraph, 
  2224                                     const NodeMap& _potential) 
  2225       : digraph(_digraph), potential(_potential) {}
  2226 
  2227     /// \brief Const subscription operator
  2228     ///
  2229     /// Const subscription operator
  2230     Value operator[](const Key& arc) const {
  2231       return potential[digraph.target(arc)] - potential[digraph.source(arc)];
  2232     }
  2233 
  2234   private:
  2235     const Digraph& digraph;
  2236     const NodeMap& potential;
  2237   };
  2238 
  2239   /// \brief Returns a PotentialDifferenceMap.
  2240   ///
  2241   /// This function just returns a PotentialDifferenceMap.
  2242   /// \relates PotentialDifferenceMap
  2243   template <typename Digraph, typename NodeMap>
  2244   PotentialDifferenceMap<Digraph, NodeMap> 
  2245   potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
  2246     return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
  2247   }
  2248 
  2249   /// \brief Map of the node in-degrees.
  2250   ///
  2251   /// This map returns the in-degree of a node. Once it is constructed,
  2252   /// the degrees are stored in a standard NodeMap, so each query is done
  2253   /// in constant time. On the other hand, the values are updated automatically
  2254   /// whenever the digraph changes.
  2255   ///
  2256   /// \warning Besides addNode() and addArc(), a digraph structure may provide
  2257   /// alternative ways to modify the digraph. The correct behavior of InDegMap
  2258   /// is not guarantied if these additional features are used. For example
  2259   /// the functions \ref ListDigraph::changeSource() "changeSource()",
  2260   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2261   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2262   /// of \ref ListDigraph will \e not update the degree values correctly.
  2263   ///
  2264   /// \sa OutDegMap
  2265 
  2266   template <typename _Digraph>
  2267   class InDegMap  
  2268     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2269       ::ItemNotifier::ObserverBase {
  2270 
  2271   public:
  2272     
  2273     typedef _Digraph Digraph;
  2274     typedef int Value;
  2275     typedef typename Digraph::Node Key;
  2276 
  2277     typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2278     ::ItemNotifier::ObserverBase Parent;
  2279 
  2280   private:
  2281 
  2282     class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
  2283     public:
  2284 
  2285       typedef DefaultMap<_Digraph, Key, int> Parent;
  2286       typedef typename Parent::Digraph Digraph;
  2287 
  2288       AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
  2289       
  2290       virtual void add(const Key& key) {
  2291 	Parent::add(key);
  2292 	Parent::set(key, 0);
  2293       }
  2294 
  2295       virtual void add(const std::vector<Key>& keys) {
  2296 	Parent::add(keys);
  2297 	for (int i = 0; i < int(keys.size()); ++i) {
  2298 	  Parent::set(keys[i], 0);
  2299 	}
  2300       }
  2301 
  2302       virtual void build() {
  2303 	Parent::build();
  2304 	Key it;
  2305 	typename Parent::Notifier* nf = Parent::notifier();
  2306 	for (nf->first(it); it != INVALID; nf->next(it)) {
  2307 	  Parent::set(it, 0);
  2308 	}
  2309       }
  2310     };
  2311 
  2312   public:
  2313 
  2314     /// \brief Constructor.
  2315     ///
  2316     /// Constructor for creating in-degree map.
  2317     explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
  2318       Parent::attach(digraph.notifier(typename _Digraph::Arc()));
  2319       
  2320       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
  2321 	deg[it] = countInArcs(digraph, it);
  2322       }
  2323     }
  2324     
  2325     /// Gives back the in-degree of a Node.
  2326     int operator[](const Key& key) const {
  2327       return deg[key];
  2328     }
  2329 
  2330   protected:
  2331     
  2332     typedef typename Digraph::Arc Arc;
  2333 
  2334     virtual void add(const Arc& arc) {
  2335       ++deg[digraph.target(arc)];
  2336     }
  2337 
  2338     virtual void add(const std::vector<Arc>& arcs) {
  2339       for (int i = 0; i < int(arcs.size()); ++i) {
  2340         ++deg[digraph.target(arcs[i])];
  2341       }
  2342     }
  2343 
  2344     virtual void erase(const Arc& arc) {
  2345       --deg[digraph.target(arc)];
  2346     }
  2347 
  2348     virtual void erase(const std::vector<Arc>& arcs) {
  2349       for (int i = 0; i < int(arcs.size()); ++i) {
  2350         --deg[digraph.target(arcs[i])];
  2351       }
  2352     }
  2353 
  2354     virtual void build() {
  2355       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
  2356 	deg[it] = countInArcs(digraph, it);
  2357       }      
  2358     }
  2359 
  2360     virtual void clear() {
  2361       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
  2362 	deg[it] = 0;
  2363       }
  2364     }
  2365   private:
  2366     
  2367     const _Digraph& digraph;
  2368     AutoNodeMap deg;
  2369   };
  2370 
  2371   /// \brief Map of the node out-degrees.
  2372   ///
  2373   /// This map returns the out-degree of a node. Once it is constructed,
  2374   /// the degrees are stored in a standard NodeMap, so each query is done
  2375   /// in constant time. On the other hand, the values are updated automatically
  2376   /// whenever the digraph changes.
  2377   ///
  2378   /// \warning Besides addNode() and addArc(), a digraph structure may provide
  2379   /// alternative ways to modify the digraph. The correct behavior of OutDegMap
  2380   /// is not guarantied if these additional features are used. For example
  2381   /// the functions \ref ListDigraph::changeSource() "changeSource()",
  2382   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2383   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2384   /// of \ref ListDigraph will \e not update the degree values correctly.
  2385   ///
  2386   /// \sa InDegMap
  2387 
  2388   template <typename _Digraph>
  2389   class OutDegMap  
  2390     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2391       ::ItemNotifier::ObserverBase {
  2392 
  2393   public:
  2394 
  2395     typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2396     ::ItemNotifier::ObserverBase Parent;
  2397     
  2398     typedef _Digraph Digraph;
  2399     typedef int Value;
  2400     typedef typename Digraph::Node Key;
  2401 
  2402   private:
  2403 
  2404     class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
  2405     public:
  2406 
  2407       typedef DefaultMap<_Digraph, Key, int> Parent;
  2408       typedef typename Parent::Digraph Digraph;
  2409 
  2410       AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
  2411       
  2412       virtual void add(const Key& key) {
  2413 	Parent::add(key);
  2414 	Parent::set(key, 0);
  2415       }
  2416       virtual void add(const std::vector<Key>& keys) {
  2417 	Parent::add(keys);
  2418 	for (int i = 0; i < int(keys.size()); ++i) {
  2419 	  Parent::set(keys[i], 0);
  2420 	}
  2421       }
  2422       virtual void build() {
  2423 	Parent::build();
  2424 	Key it;
  2425 	typename Parent::Notifier* nf = Parent::notifier();
  2426 	for (nf->first(it); it != INVALID; nf->next(it)) {
  2427 	  Parent::set(it, 0);
  2428 	}
  2429       }
  2430     };
  2431 
  2432   public:
  2433 
  2434     /// \brief Constructor.
  2435     ///
  2436     /// Constructor for creating out-degree map.
  2437     explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
  2438       Parent::attach(digraph.notifier(typename _Digraph::Arc()));
  2439       
  2440       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
  2441 	deg[it] = countOutArcs(digraph, it);
  2442       }
  2443     }
  2444 
  2445     /// Gives back the out-degree of a Node.
  2446     int operator[](const Key& key) const {
  2447       return deg[key];
  2448     }
  2449 
  2450   protected:
  2451     
  2452     typedef typename Digraph::Arc Arc;
  2453 
  2454     virtual void add(const Arc& arc) {
  2455       ++deg[digraph.source(arc)];
  2456     }
  2457 
  2458     virtual void add(const std::vector<Arc>& arcs) {
  2459       for (int i = 0; i < int(arcs.size()); ++i) {
  2460         ++deg[digraph.source(arcs[i])];
  2461       }
  2462     }
  2463 
  2464     virtual void erase(const Arc& arc) {
  2465       --deg[digraph.source(arc)];
  2466     }
  2467 
  2468     virtual void erase(const std::vector<Arc>& arcs) {
  2469       for (int i = 0; i < int(arcs.size()); ++i) {
  2470         --deg[digraph.source(arcs[i])];
  2471       }
  2472     }
  2473 
  2474     virtual void build() {
  2475       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
  2476 	deg[it] = countOutArcs(digraph, it);
  2477       }      
  2478     }
  2479 
  2480     virtual void clear() {
  2481       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
  2482 	deg[it] = 0;
  2483       }
  2484     }
  2485   private:
  2486     
  2487     const _Digraph& digraph;
  2488     AutoNodeMap deg;
  2489   };
  2490 
  2491 
  2492   ///Dynamic arc look up between given endpoints.
  2493   
  2494   ///\ingroup gutils
  2495   ///Using this class, you can find an arc in a digraph from a given
  2496   ///source to a given target in amortized time <em>O(log d)</em>,
  2497   ///where <em>d</em> is the out-degree of the source node.
  2498   ///
  2499   ///It is possible to find \e all parallel arcs between two nodes with
  2500   ///the \c findFirst() and \c findNext() members.
  2501   ///
  2502   ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
  2503   ///digraph do not changed so frequently.
  2504   ///
  2505   ///This class uses a self-adjusting binary search tree, Sleator's
  2506   ///and Tarjan's Splay tree for guarantee the logarithmic amortized
  2507   ///time bound for arc lookups. This class also guarantees the
  2508   ///optimal time bound in a constant factor for any distribution of
  2509   ///queries.
  2510   ///
  2511   ///\param G The type of the underlying digraph.  
  2512   ///
  2513   ///\sa ArcLookUp  
  2514   ///\sa AllArcLookUp  
  2515   template<class G>
  2516   class DynArcLookUp 
  2517     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
  2518   {
  2519   public:
  2520     typedef typename ItemSetTraits<G, typename G::Arc>
  2521     ::ItemNotifier::ObserverBase Parent;
  2522 
  2523     GRAPH_TYPEDEFS(typename G);
  2524     typedef G Digraph;
  2525 
  2526   protected:
  2527 
  2528     class AutoNodeMap : public DefaultMap<G, Node, Arc> {
  2529     public:
  2530 
  2531       typedef DefaultMap<G, Node, Arc> Parent;
  2532 
  2533       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
  2534       
  2535       virtual void add(const Node& node) {
  2536 	Parent::add(node);
  2537 	Parent::set(node, INVALID);
  2538       }
  2539 
  2540       virtual void add(const std::vector<Node>& nodes) {
  2541 	Parent::add(nodes);
  2542 	for (int i = 0; i < int(nodes.size()); ++i) {
  2543 	  Parent::set(nodes[i], INVALID);
  2544 	}
  2545       }
  2546 
  2547       virtual void build() {
  2548 	Parent::build();
  2549 	Node it;
  2550 	typename Parent::Notifier* nf = Parent::notifier();
  2551 	for (nf->first(it); it != INVALID; nf->next(it)) {
  2552 	  Parent::set(it, INVALID);
  2553 	}
  2554       }
  2555     };
  2556 
  2557     const Digraph &_g;
  2558     AutoNodeMap _head;
  2559     typename Digraph::template ArcMap<Arc> _parent;
  2560     typename Digraph::template ArcMap<Arc> _left;
  2561     typename Digraph::template ArcMap<Arc> _right;
  2562     
  2563     class ArcLess {
  2564       const Digraph &g;
  2565     public:
  2566       ArcLess(const Digraph &_g) : g(_g) {}
  2567       bool operator()(Arc a,Arc b) const 
  2568       {
  2569 	return g.target(a)<g.target(b);
  2570       }
  2571     };
  2572     
  2573   public:
  2574     
  2575     ///Constructor
  2576 
  2577     ///Constructor.
  2578     ///
  2579     ///It builds up the search database.
  2580     DynArcLookUp(const Digraph &g) 
  2581       : _g(g),_head(g),_parent(g),_left(g),_right(g) 
  2582     { 
  2583       Parent::attach(_g.notifier(typename Digraph::Arc()));
  2584       refresh(); 
  2585     }
  2586     
  2587   protected:
  2588 
  2589     virtual void add(const Arc& arc) {
  2590       insert(arc);
  2591     }
  2592 
  2593     virtual void add(const std::vector<Arc>& arcs) {
  2594       for (int i = 0; i < int(arcs.size()); ++i) {
  2595 	insert(arcs[i]);
  2596       }
  2597     }
  2598 
  2599     virtual void erase(const Arc& arc) {
  2600       remove(arc);
  2601     }
  2602 
  2603     virtual void erase(const std::vector<Arc>& arcs) {
  2604       for (int i = 0; i < int(arcs.size()); ++i) {
  2605 	remove(arcs[i]);
  2606       }     
  2607     }
  2608 
  2609     virtual void build() {
  2610       refresh();
  2611     }
  2612 
  2613     virtual void clear() {
  2614       for(NodeIt n(_g);n!=INVALID;++n) {
  2615 	_head.set(n, INVALID);
  2616       }
  2617     }
  2618 
  2619     void insert(Arc arc) {
  2620       Node s = _g.source(arc);
  2621       Node t = _g.target(arc);
  2622       _left.set(arc, INVALID);
  2623       _right.set(arc, INVALID);
  2624       
  2625       Arc e = _head[s];
  2626       if (e == INVALID) {
  2627 	_head.set(s, arc);
  2628 	_parent.set(arc, INVALID);
  2629 	return;
  2630       }
  2631       while (true) {
  2632 	if (t < _g.target(e)) {
  2633 	  if (_left[e] == INVALID) {
  2634 	    _left.set(e, arc);
  2635 	    _parent.set(arc, e);
  2636 	    splay(arc);
  2637 	    return;
  2638 	  } else {
  2639 	    e = _left[e];
  2640 	  }
  2641 	} else {
  2642 	  if (_right[e] == INVALID) {
  2643 	    _right.set(e, arc);
  2644 	    _parent.set(arc, e);
  2645 	    splay(arc);
  2646 	    return;
  2647 	  } else {
  2648 	    e = _right[e];
  2649 	  }
  2650 	}
  2651       }
  2652     }
  2653 
  2654     void remove(Arc arc) {
  2655       if (_left[arc] == INVALID) {
  2656 	if (_right[arc] != INVALID) {
  2657 	  _parent.set(_right[arc], _parent[arc]);
  2658 	}
  2659 	if (_parent[arc] != INVALID) {
  2660 	  if (_left[_parent[arc]] == arc) {
  2661 	    _left.set(_parent[arc], _right[arc]);
  2662 	  } else {
  2663 	    _right.set(_parent[arc], _right[arc]);
  2664 	  }
  2665 	} else {
  2666 	  _head.set(_g.source(arc), _right[arc]);
  2667 	}
  2668       } else if (_right[arc] == INVALID) {
  2669 	_parent.set(_left[arc], _parent[arc]);
  2670 	if (_parent[arc] != INVALID) {
  2671 	  if (_left[_parent[arc]] == arc) {
  2672 	    _left.set(_parent[arc], _left[arc]);
  2673 	  } else {
  2674 	    _right.set(_parent[arc], _left[arc]);
  2675 	  }
  2676 	} else {
  2677 	  _head.set(_g.source(arc), _left[arc]);
  2678 	}
  2679       } else {
  2680 	Arc e = _left[arc];
  2681 	if (_right[e] != INVALID) {
  2682 	  e = _right[e];	  
  2683 	  while (_right[e] != INVALID) {
  2684 	    e = _right[e];
  2685 	  }
  2686 	  Arc s = _parent[e];
  2687 	  _right.set(_parent[e], _left[e]);
  2688 	  if (_left[e] != INVALID) {
  2689 	    _parent.set(_left[e], _parent[e]);
  2690 	  }
  2691 	  
  2692 	  _left.set(e, _left[arc]);
  2693 	  _parent.set(_left[arc], e);
  2694 	  _right.set(e, _right[arc]);
  2695 	  _parent.set(_right[arc], e);
  2696 
  2697 	  _parent.set(e, _parent[arc]);
  2698 	  if (_parent[arc] != INVALID) {
  2699 	    if (_left[_parent[arc]] == arc) {
  2700 	      _left.set(_parent[arc], e);
  2701 	    } else {
  2702 	      _right.set(_parent[arc], e);
  2703 	    }
  2704 	  }
  2705 	  splay(s);
  2706 	} else {
  2707 	  _right.set(e, _right[arc]);
  2708 	  _parent.set(_right[arc], e);
  2709 
  2710 	  if (_parent[arc] != INVALID) {
  2711 	    if (_left[_parent[arc]] == arc) {
  2712 	      _left.set(_parent[arc], e);
  2713 	    } else {
  2714 	      _right.set(_parent[arc], e);
  2715 	    }
  2716 	  } else {
  2717 	    _head.set(_g.source(arc), e);
  2718 	  }
  2719 	}
  2720       }
  2721     }
  2722 
  2723     Arc refreshRec(std::vector<Arc> &v,int a,int b) 
  2724     {
  2725       int m=(a+b)/2;
  2726       Arc me=v[m];
  2727       if (a < m) {
  2728 	Arc left = refreshRec(v,a,m-1);
  2729 	_left.set(me, left);
  2730 	_parent.set(left, me);
  2731       } else {
  2732 	_left.set(me, INVALID);
  2733       }
  2734       if (m < b) {
  2735 	Arc right = refreshRec(v,m+1,b);
  2736 	_right.set(me, right);
  2737 	_parent.set(right, me);
  2738       } else {
  2739 	_right.set(me, INVALID);
  2740       }
  2741       return me;
  2742     }
  2743 
  2744     void refresh() {
  2745       for(NodeIt n(_g);n!=INVALID;++n) {
  2746 	std::vector<Arc> v;
  2747 	for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  2748 	if(v.size()) {
  2749 	  std::sort(v.begin(),v.end(),ArcLess(_g));
  2750 	  Arc head = refreshRec(v,0,v.size()-1);
  2751 	  _head.set(n, head);
  2752 	  _parent.set(head, INVALID);
  2753 	}
  2754 	else _head.set(n, INVALID);
  2755       }
  2756     }
  2757 
  2758     void zig(Arc v) {        
  2759       Arc w = _parent[v];
  2760       _parent.set(v, _parent[w]);
  2761       _parent.set(w, v);
  2762       _left.set(w, _right[v]);
  2763       _right.set(v, w);
  2764       if (_parent[v] != INVALID) {
  2765 	if (_right[_parent[v]] == w) {
  2766 	  _right.set(_parent[v], v);
  2767 	} else {
  2768 	  _left.set(_parent[v], v);
  2769 	}
  2770       }
  2771       if (_left[w] != INVALID){
  2772 	_parent.set(_left[w], w);
  2773       }
  2774     }
  2775 
  2776     void zag(Arc v) {        
  2777       Arc w = _parent[v];
  2778       _parent.set(v, _parent[w]);
  2779       _parent.set(w, v);
  2780       _right.set(w, _left[v]);
  2781       _left.set(v, w);
  2782       if (_parent[v] != INVALID){
  2783 	if (_left[_parent[v]] == w) {
  2784 	  _left.set(_parent[v], v);
  2785 	} else {
  2786 	  _right.set(_parent[v], v);
  2787 	}
  2788       }
  2789       if (_right[w] != INVALID){
  2790 	_parent.set(_right[w], w);
  2791       }
  2792     }
  2793 
  2794     void splay(Arc v) {
  2795       while (_parent[v] != INVALID) {
  2796 	if (v == _left[_parent[v]]) {
  2797 	  if (_parent[_parent[v]] == INVALID) {
  2798 	    zig(v);
  2799 	  } else {
  2800 	    if (_parent[v] == _left[_parent[_parent[v]]]) {
  2801 	      zig(_parent[v]);
  2802 	      zig(v);
  2803 	    } else {
  2804 	      zig(v);
  2805 	      zag(v);
  2806 	    }
  2807 	  }
  2808 	} else {
  2809 	  if (_parent[_parent[v]] == INVALID) {
  2810 	    zag(v);
  2811 	  } else {
  2812 	    if (_parent[v] == _left[_parent[_parent[v]]]) {
  2813 	      zag(v);
  2814 	      zig(v);
  2815 	    } else {
  2816 	      zag(_parent[v]);
  2817 	      zag(v);
  2818 	    }
  2819 	  }
  2820 	}
  2821       }
  2822       _head[_g.source(v)] = v;
  2823     }
  2824 
  2825 
  2826   public:
  2827     
  2828     ///Find an arc between two nodes.
  2829     
  2830     ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
  2831     /// <em>d</em> is the number of outgoing arcs of \c s.
  2832     ///\param s The source node
  2833     ///\param t The target node
  2834     ///\return An arc from \c s to \c t if there exists,
  2835     ///\ref INVALID otherwise.
  2836     Arc operator()(Node s, Node t) const
  2837     {
  2838       Arc e = _head[s];
  2839       while (true) {
  2840 	if (_g.target(e) == t) {
  2841 	  const_cast<DynArcLookUp&>(*this).splay(e);
  2842 	  return e;
  2843 	} else if (t < _g.target(e)) {
  2844 	  if (_left[e] == INVALID) {
  2845 	    const_cast<DynArcLookUp&>(*this).splay(e);
  2846 	    return INVALID;
  2847 	  } else {
  2848 	    e = _left[e];
  2849 	  }
  2850 	} else  {
  2851 	  if (_right[e] == INVALID) {
  2852 	    const_cast<DynArcLookUp&>(*this).splay(e);
  2853 	    return INVALID;
  2854 	  } else {
  2855 	    e = _right[e];
  2856 	  }
  2857 	}
  2858       }
  2859     }
  2860 
  2861     ///Find the first arc between two nodes.
  2862     
  2863     ///Find the first arc between two nodes in time
  2864     /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
  2865     /// outgoing arcs of \c s.  
  2866     ///\param s The source node 
  2867     ///\param t The target node
  2868     ///\return An arc from \c s to \c t if there exists, \ref INVALID
  2869     /// otherwise.
  2870     Arc findFirst(Node s, Node t) const
  2871     {
  2872       Arc e = _head[s];
  2873       Arc r = INVALID;
  2874       while (true) {
  2875 	if (_g.target(e) < t) {
  2876 	  if (_right[e] == INVALID) {
  2877 	    const_cast<DynArcLookUp&>(*this).splay(e);
  2878 	    return r;
  2879 	  } else {
  2880 	    e = _right[e];
  2881 	  }
  2882 	} else {
  2883 	  if (_g.target(e) == t) {
  2884 	    r = e;
  2885 	  }
  2886 	  if (_left[e] == INVALID) {
  2887 	    const_cast<DynArcLookUp&>(*this).splay(e);
  2888 	    return r;
  2889 	  } else {
  2890 	    e = _left[e];
  2891 	  }
  2892 	}
  2893       }
  2894     }
  2895 
  2896     ///Find the next arc between two nodes.
  2897     
  2898     ///Find the next arc between two nodes in time
  2899     /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
  2900     /// outgoing arcs of \c s.  
  2901     ///\param s The source node 
  2902     ///\param t The target node
  2903     ///\return An arc from \c s to \c t if there exists, \ref INVALID
  2904     /// otherwise.
  2905 
  2906     ///\note If \c e is not the result of the previous \c findFirst()
  2907     ///operation then the amorized time bound can not be guaranteed.
  2908 #ifdef DOXYGEN
  2909     Arc findNext(Node s, Node t, Arc e) const
  2910 #else
  2911     Arc findNext(Node, Node t, Arc e) const
  2912 #endif
  2913     {
  2914       if (_right[e] != INVALID) {
  2915 	e = _right[e];
  2916 	while (_left[e] != INVALID) {
  2917 	  e = _left[e];
  2918 	}
  2919 	const_cast<DynArcLookUp&>(*this).splay(e);
  2920       } else {
  2921 	while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
  2922 	  e = _parent[e];
  2923 	}
  2924 	if (_parent[e] == INVALID) {
  2925 	  return INVALID;
  2926 	} else {
  2927 	  e = _parent[e];
  2928 	  const_cast<DynArcLookUp&>(*this).splay(e);
  2929 	}
  2930       }
  2931       if (_g.target(e) == t) return e;
  2932       else return INVALID;    
  2933     }
  2934 
  2935   };
  2936 
  2937   ///Fast arc look up between given endpoints.
  2938   
  2939   ///\ingroup gutils
  2940   ///Using this class, you can find an arc in a digraph from a given
  2941   ///source to a given target in time <em>O(log d)</em>,
  2942   ///where <em>d</em> is the out-degree of the source node.
  2943   ///
  2944   ///It is not possible to find \e all parallel arcs between two nodes.
  2945   ///Use \ref AllArcLookUp for this purpose.
  2946   ///
  2947   ///\warning This class is static, so you should refresh() (or at least
  2948   ///refresh(Node)) this data structure
  2949   ///whenever the digraph changes. This is a time consuming (superlinearly
  2950   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  2951   ///
  2952   ///\param G The type of the underlying digraph.
  2953   ///
  2954   ///\sa DynArcLookUp
  2955   ///\sa AllArcLookUp  
  2956   template<class G>
  2957   class ArcLookUp 
  2958   {
  2959   public:
  2960     GRAPH_TYPEDEFS(typename G);
  2961     typedef G Digraph;
  2962 
  2963   protected:
  2964     const Digraph &_g;
  2965     typename Digraph::template NodeMap<Arc> _head;
  2966     typename Digraph::template ArcMap<Arc> _left;
  2967     typename Digraph::template ArcMap<Arc> _right;
  2968     
  2969     class ArcLess {
  2970       const Digraph &g;
  2971     public:
  2972       ArcLess(const Digraph &_g) : g(_g) {}
  2973       bool operator()(Arc a,Arc b) const 
  2974       {
  2975 	return g.target(a)<g.target(b);
  2976       }
  2977     };
  2978     
  2979   public:
  2980     
  2981     ///Constructor
  2982 
  2983     ///Constructor.
  2984     ///
  2985     ///It builds up the search database, which remains valid until the digraph
  2986     ///changes.
  2987     ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
  2988     
  2989   private:
  2990     Arc refreshRec(std::vector<Arc> &v,int a,int b) 
  2991     {
  2992       int m=(a+b)/2;
  2993       Arc me=v[m];
  2994       _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
  2995       _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
  2996       return me;
  2997     }
  2998   public:
  2999     ///Refresh the data structure at a node.
  3000 
  3001     ///Build up the search database of node \c n.
  3002     ///
  3003     ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
  3004     ///the number of the outgoing arcs of \c n.
  3005     void refresh(Node n) 
  3006     {
  3007       std::vector<Arc> v;
  3008       for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  3009       if(v.size()) {
  3010 	std::sort(v.begin(),v.end(),ArcLess(_g));
  3011 	_head[n]=refreshRec(v,0,v.size()-1);
  3012       }
  3013       else _head[n]=INVALID;
  3014     }
  3015     ///Refresh the full data structure.
  3016 
  3017     ///Build up the full search database. In fact, it simply calls
  3018     ///\ref refresh(Node) "refresh(n)" for each node \c n.
  3019     ///
  3020     ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
  3021     ///the number of the arcs of \c n and <em>D</em> is the maximum
  3022     ///out-degree of the digraph.
  3023 
  3024     void refresh() 
  3025     {
  3026       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
  3027     }
  3028     
  3029     ///Find an arc between two nodes.
  3030     
  3031     ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
  3032     /// <em>d</em> is the number of outgoing arcs of \c s.
  3033     ///\param s The source node
  3034     ///\param t The target node
  3035     ///\return An arc from \c s to \c t if there exists,
  3036     ///\ref INVALID otherwise.
  3037     ///
  3038     ///\warning If you change the digraph, refresh() must be called before using
  3039     ///this operator. If you change the outgoing arcs of
  3040     ///a single node \c n, then
  3041     ///\ref refresh(Node) "refresh(n)" is enough.
  3042     ///
  3043     Arc operator()(Node s, Node t) const
  3044     {
  3045       Arc e;
  3046       for(e=_head[s];
  3047 	  e!=INVALID&&_g.target(e)!=t;
  3048 	  e = t < _g.target(e)?_left[e]:_right[e]) ;
  3049       return e;
  3050     }
  3051 
  3052   };
  3053 
  3054   ///Fast look up of all arcs between given endpoints.
  3055   
  3056   ///\ingroup gutils
  3057   ///This class is the same as \ref ArcLookUp, with the addition
  3058   ///that it makes it possible to find all arcs between given endpoints.
  3059   ///
  3060   ///\warning This class is static, so you should refresh() (or at least
  3061   ///refresh(Node)) this data structure
  3062   ///whenever the digraph changes. This is a time consuming (superlinearly
  3063   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  3064   ///
  3065   ///\param G The type of the underlying digraph.
  3066   ///
  3067   ///\sa DynArcLookUp
  3068   ///\sa ArcLookUp  
  3069   template<class G>
  3070   class AllArcLookUp : public ArcLookUp<G>
  3071   {
  3072     using ArcLookUp<G>::_g;
  3073     using ArcLookUp<G>::_right;
  3074     using ArcLookUp<G>::_left;
  3075     using ArcLookUp<G>::_head;
  3076 
  3077     GRAPH_TYPEDEFS(typename G);
  3078     typedef G Digraph;
  3079     
  3080     typename Digraph::template ArcMap<Arc> _next;
  3081     
  3082     Arc refreshNext(Arc head,Arc next=INVALID)
  3083     {
  3084       if(head==INVALID) return next;
  3085       else {
  3086 	next=refreshNext(_right[head],next);
  3087 // 	_next[head]=next;
  3088 	_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
  3089 	  ? next : INVALID;
  3090 	return refreshNext(_left[head],head);
  3091       }
  3092     }
  3093     
  3094     void refreshNext()
  3095     {
  3096       for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
  3097     }
  3098     
  3099   public:
  3100     ///Constructor
  3101 
  3102     ///Constructor.
  3103     ///
  3104     ///It builds up the search database, which remains valid until the digraph
  3105     ///changes.
  3106     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
  3107 
  3108     ///Refresh the data structure at a node.
  3109 
  3110     ///Build up the search database of node \c n.
  3111     ///
  3112     ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
  3113     ///the number of the outgoing arcs of \c n.
  3114     
  3115     void refresh(Node n) 
  3116     {
  3117       ArcLookUp<G>::refresh(n);
  3118       refreshNext(_head[n]);
  3119     }
  3120     
  3121     ///Refresh the full data structure.
  3122 
  3123     ///Build up the full search database. In fact, it simply calls
  3124     ///\ref refresh(Node) "refresh(n)" for each node \c n.
  3125     ///
  3126     ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
  3127     ///the number of the arcs of \c n and <em>D</em> is the maximum
  3128     ///out-degree of the digraph.
  3129 
  3130     void refresh() 
  3131     {
  3132       for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
  3133     }
  3134     
  3135     ///Find an arc between two nodes.
  3136     
  3137     ///Find an arc between two nodes.
  3138     ///\param s The source node
  3139     ///\param t The target node
  3140     ///\param prev The previous arc between \c s and \c t. It it is INVALID or
  3141     ///not given, the operator finds the first appropriate arc.
  3142     ///\return An arc from \c s to \c t after \c prev or
  3143     ///\ref INVALID if there is no more.
  3144     ///
  3145     ///For example, you can count the number of arcs from \c u to \c v in the
  3146     ///following way.
  3147     ///\code
  3148     ///AllArcLookUp<ListDigraph> ae(g);
  3149     ///...
  3150     ///int n=0;
  3151     ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
  3152     ///\endcode
  3153     ///
  3154     ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
  3155     /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
  3156     ///consecutive arcs are found in constant time.
  3157     ///
  3158     ///\warning If you change the digraph, refresh() must be called before using
  3159     ///this operator. If you change the outgoing arcs of
  3160     ///a single node \c n, then
  3161     ///\ref refresh(Node) "refresh(n)" is enough.
  3162     ///
  3163 #ifdef DOXYGEN
  3164     Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
  3165 #else
  3166     using ArcLookUp<G>::operator() ;
  3167     Arc operator()(Node s, Node t, Arc prev) const
  3168     {
  3169       return prev==INVALID?(*this)(s,t):_next[prev];
  3170     }
  3171 #endif
  3172       
  3173   };
  3174 
  3175   /// @}
  3176 
  3177 } //END OF NAMESPACE LEMON
  3178 
  3179 #endif