lemon/graph_utils.h
changeset 121 91c0fed3181e
child 139 701c529ba737
equal deleted inserted replaced
-1:000000000000 0:16827ada2380
       
     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