lemon/graph_utils.h
author deba
Mon, 06 Mar 2006 17:32:35 +0000
changeset 2000 ebcc93ead7da
parent 1993 2115143eceea
child 2002 9ff31b5090bd
permissions -rw-r--r--
Checking missing section reader
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     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 
    27 #include <lemon/bits/invalid.h>
    28 #include <lemon/bits/utility.h>
    29 #include <lemon/maps.h>
    30 #include <lemon/bits/traits.h>
    31 
    32 #include <lemon/bits/alteration_notifier.h>
    33 #include <lemon/bits/default_map.h>
    34 
    35 ///\ingroup gutils
    36 ///\file
    37 ///\brief Graph utilities.
    38 ///
    39 ///
    40 
    41 
    42 namespace lemon {
    43 
    44   /// \addtogroup gutils
    45   /// @{
    46 
    47   ///Creates convenience typedefs for the graph types and iterators
    48 
    49   ///This \c \#define creates convenience typedefs for the following types
    50   ///of \c Graph: \c Node,  \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
    51   ///\c OutEdgeIt,  \c BoolNodeMap,  \c IntNodeMap,  \c DoubleNodeMap,
    52   ///\c BoolEdgeMap, \c IntEdgeMap,  \c DoubleEdgeMap.  
    53   ///\note If \c G it a template parameter, it should be used in this way.
    54   ///\code
    55   ///  GRAPH_TYPEDEFS(typename G)
    56   ///\endcode
    57   ///
    58   ///\warning There are no typedefs for the graph maps because of the lack of
    59   ///template typedefs in C++.
    60 #define GRAPH_TYPEDEFS(Graph)				\
    61   typedef Graph::     Node      Node;			\
    62     typedef Graph::   NodeIt    NodeIt;			\
    63     typedef Graph::   Edge      Edge;			\
    64     typedef Graph::   EdgeIt    EdgeIt;			\
    65     typedef Graph:: InEdgeIt  InEdgeIt;			\
    66     typedef Graph::OutEdgeIt OutEdgeIt;			
    67 //     typedef Graph::template NodeMap<bool> BoolNodeMap;	       
    68 //     typedef Graph::template NodeMap<int> IntNodeMap;	       
    69 //     typedef Graph::template NodeMap<double> DoubleNodeMap;  
    70 //     typedef Graph::template EdgeMap<bool> BoolEdgeMap;	       
    71 //     typedef Graph::template EdgeMap<int> IntEdgeMap;	       
    72 //     typedef Graph::template EdgeMap<double> DoubleEdgeMap;
    73   
    74   ///Creates convenience typedefs for the undirected graph types and iterators
    75 
    76   ///This \c \#define creates the same convenience typedefs as defined by
    77   ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
    78   ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
    79   ///\c BoolUEdgeMap, \c IntUEdgeMap,  \c DoubleUEdgeMap.  
    80   ///
    81   ///\note If \c G it a template parameter, it should be used in this way.
    82   ///\code
    83   ///  UGRAPH_TYPEDEFS(typename G)
    84   ///\endcode
    85   ///
    86   ///\warning There are no typedefs for the graph maps because of the lack of
    87   ///template typedefs in C++.
    88 #define UGRAPH_TYPEDEFS(Graph)				\
    89   GRAPH_TYPEDEFS(Graph)						\
    90     typedef Graph:: UEdge   UEdge;			\
    91     typedef Graph:: UEdgeIt UEdgeIt;			\
    92     typedef Graph:: IncEdgeIt   IncEdgeIt;		       
    93 //     typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;	 
    94 //     typedef Graph::template UEdgeMap<int> IntUEdgeMap;
    95 //     typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
    96   
    97 
    98 
    99   /// \brief Function to count the items in the graph.
   100   ///
   101   /// This function counts the items (nodes, edges etc) in the graph.
   102   /// The complexity of the function is O(n) because
   103   /// it iterates on all of the items.
   104 
   105   template <typename Graph, typename ItemIt>
   106   inline int countItems(const Graph& g) {
   107     int num = 0;
   108     for (ItemIt it(g); it != INVALID; ++it) {
   109       ++num;
   110     }
   111     return num;
   112   }
   113 
   114   // Node counting:
   115 
   116   template <typename Graph>
   117   inline typename enable_if<typename Graph::NodeNumTag, int>::type
   118   _countNodes(const Graph &g) {
   119     return g.nodeNum();
   120   }
   121 
   122   template <typename Graph>
   123   inline int _countNodes(Wrap<Graph> w) {
   124     return countItems<Graph, typename Graph::NodeIt>(w.value);
   125   }
   126 
   127   /// \brief Function to count the nodes in the graph.
   128   ///
   129   /// This function counts the nodes in the graph.
   130   /// The complexity of the function is O(n) but for some
   131   /// graph structures it is specialized to run in O(1).
   132   ///
   133   /// \todo refer how to specialize it
   134 
   135   template <typename Graph>
   136   inline int countNodes(const Graph& g) {
   137     return _countNodes<Graph>(g);
   138   }
   139 
   140   // Edge counting:
   141 
   142   template <typename Graph>
   143   inline typename enable_if<typename Graph::EdgeNumTag, int>::type
   144   _countEdges(const Graph &g) {
   145     return g.edgeNum();
   146   }
   147 
   148   template <typename Graph>
   149   inline int _countEdges(Wrap<Graph> w) {
   150     return countItems<Graph, typename Graph::EdgeIt>(w.value);
   151   }
   152 
   153   /// \brief Function to count the edges in the graph.
   154   ///
   155   /// This function counts the edges in the graph.
   156   /// The complexity of the function is O(e) but for some
   157   /// graph structures it is specialized to run in O(1).
   158 
   159   template <typename Graph>
   160   inline int countEdges(const Graph& g) {
   161     return _countEdges<Graph>(g);
   162   }
   163 
   164   // Undirected edge counting:
   165 
   166   template <typename Graph>
   167   inline
   168   typename enable_if<typename Graph::EdgeNumTag, int>::type
   169   _countUEdges(const Graph &g) {
   170     return g.uEdgeNum();
   171   }
   172 
   173   template <typename Graph>
   174   inline int _countUEdges(Wrap<Graph> w) {
   175     return countItems<Graph, typename Graph::UEdgeIt>(w.value);
   176   }
   177 
   178   /// \brief Function to count the undirected edges in the graph.
   179   ///
   180   /// This function counts the undirected edges in the graph.
   181   /// The complexity of the function is O(e) but for some
   182   /// graph structures it is specialized to run in O(1).
   183 
   184   template <typename Graph>
   185   inline int countUEdges(const Graph& g) {
   186     return _countUEdges<Graph>(g);
   187   }
   188 
   189 
   190 
   191   template <typename Graph, typename DegIt>
   192   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   193     int num = 0;
   194     for (DegIt it(_g, _n); it != INVALID; ++it) {
   195       ++num;
   196     }
   197     return num;
   198   }
   199 
   200   /// \brief Function to count the number of the out-edges from node \c n.
   201   ///
   202   /// This function counts the number of the out-edges from node \c n
   203   /// in the graph.  
   204   template <typename Graph>
   205   inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
   206     return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
   207   }
   208 
   209   /// \brief Function to count the number of the in-edges to node \c n.
   210   ///
   211   /// This function counts the number of the in-edges to node \c n
   212   /// in the graph.  
   213   template <typename Graph>
   214   inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
   215     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
   216   }
   217 
   218   /// \brief Function to count the number of the inc-edges to node \c n.
   219   ///
   220   /// This function counts the number of the inc-edges to node \c n
   221   /// in the graph.  
   222   template <typename Graph>
   223   inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
   224     return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
   225   }
   226 
   227 
   228   template <typename Graph>
   229   inline
   230   typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 
   231   _findEdge(const Graph &g,
   232 	    typename Graph::Node u, typename Graph::Node v,
   233 	    typename Graph::Edge prev = INVALID) {
   234     return g.findEdge(u, v, prev);
   235   }
   236 
   237   template <typename Graph>
   238   inline typename Graph::Edge 
   239   _findEdge(Wrap<Graph> w,
   240 	    typename Graph::Node u, 
   241 	    typename Graph::Node v,
   242 	    typename Graph::Edge prev = INVALID) {
   243     const Graph& g = w.value;
   244     if (prev == INVALID) {
   245       typename Graph::OutEdgeIt e(g, u);
   246       while (e != INVALID && g.target(e) != v) ++e;
   247       return e;
   248     } else {
   249       typename Graph::OutEdgeIt e(g, prev); ++e;
   250       while (e != INVALID && g.target(e) != v) ++e;
   251       return e;
   252     }
   253   }
   254 
   255   /// \brief Finds an edge between two nodes of a graph.
   256   ///
   257   /// Finds an edge from node \c u to node \c v in graph \c g.
   258   ///
   259   /// If \c prev is \ref INVALID (this is the default value), then
   260   /// it finds the first edge from \c u to \c v. Otherwise it looks for
   261   /// the next edge from \c u to \c v after \c prev.
   262   /// \return The found edge or \ref INVALID if there is no such an edge.
   263   ///
   264   /// Thus you can iterate through each edge from \c u to \c v as it follows.
   265   ///\code
   266   /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
   267   ///   ...
   268   /// }
   269   ///\endcode
   270   // /// \todo We may want to use the "GraphBase" 
   271   // /// interface here...
   272   template <typename Graph>
   273   inline typename Graph::Edge findEdge(const Graph &g,
   274 				       typename Graph::Node u, 
   275 				       typename Graph::Node v,
   276 				       typename Graph::Edge prev = INVALID) {
   277     return _findEdge<Graph>(g, u, v, prev);
   278   }
   279 
   280   /// \brief Iterator for iterating on edges connected the same nodes.
   281   ///
   282   /// Iterator for iterating on edges connected the same nodes. It is 
   283   /// higher level interface for the findEdge() function. You can
   284   /// use it the following way:
   285   ///\code
   286   /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
   287   ///   ...
   288   /// }
   289   ///\endcode
   290   ///
   291   /// \author Balazs Dezso 
   292   template <typename _Graph>
   293   class ConEdgeIt : public _Graph::Edge {
   294   public:
   295 
   296     typedef _Graph Graph;
   297     typedef typename Graph::Edge Parent;
   298 
   299     typedef typename Graph::Edge Edge;
   300     typedef typename Graph::Node Node;
   301 
   302     /// \brief Constructor.
   303     ///
   304     /// Construct a new ConEdgeIt iterating on the edges which
   305     /// connects the \c u and \c v node.
   306     ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
   307       Parent::operator=(findEdge(graph, u, v));
   308     }
   309 
   310     /// \brief Constructor.
   311     ///
   312     /// Construct a new ConEdgeIt which continues the iterating from 
   313     /// the \c e edge.
   314     ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
   315     
   316     /// \brief Increment operator.
   317     ///
   318     /// It increments the iterator and gives back the next edge.
   319     ConEdgeIt& operator++() {
   320       Parent::operator=(findEdge(graph, graph.source(*this), 
   321 				 graph.target(*this), *this));
   322       return *this;
   323     }
   324   private:
   325     const Graph& graph;
   326   };
   327 
   328   template <typename Graph>
   329   inline
   330   typename enable_if<
   331     typename Graph::FindEdgeTag, 
   332     typename Graph::UEdge>::type 
   333   _findUEdge(const Graph &g,
   334 	    typename Graph::Node u, typename Graph::Node v,
   335 	    typename Graph::UEdge prev = INVALID) {
   336     return g.findUEdge(u, v, prev);
   337   }
   338 
   339   template <typename Graph>
   340   inline typename Graph::UEdge 
   341   _findUEdge(Wrap<Graph> w,
   342 	    typename Graph::Node u, 
   343 	    typename Graph::Node v,
   344 	    typename Graph::UEdge prev = INVALID) {
   345     const Graph& g = w.value;
   346     if (prev == INVALID) {
   347       typename Graph::OutEdgeIt e(g, u);
   348       while (e != INVALID && g.target(e) != v) ++e;
   349       return e;
   350     } else {
   351       typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
   352       while (e != INVALID && g.target(e) != v) ++e;
   353       return e;
   354     }
   355   }
   356 
   357   /// \brief Finds an uedge between two nodes of a graph.
   358   ///
   359   /// Finds an uedge from node \c u to node \c v in graph \c g.
   360   ///
   361   /// If \c prev is \ref INVALID (this is the default value), then
   362   /// it finds the first edge from \c u to \c v. Otherwise it looks for
   363   /// the next edge from \c u to \c v after \c prev.
   364   /// \return The found edge or \ref INVALID if there is no such an edge.
   365   ///
   366   /// Thus you can iterate through each edge from \c u to \c v as it follows.
   367   ///\code
   368   /// for(UEdge e = findUEdge(g,u,v); e != INVALID; 
   369   ///     e = findUEdge(g,u,v,e)) {
   370   ///   ...
   371   /// }
   372   ///\endcode
   373   // /// \todo We may want to use the "GraphBase" 
   374   // /// interface here...
   375   template <typename Graph>
   376   inline typename Graph::UEdge 
   377   findUEdge(const Graph &g,
   378 		typename Graph::Node u, 
   379 		typename Graph::Node v,
   380 		typename Graph::UEdge prev = INVALID) {
   381     return _findUEdge<Graph>(g, u, v, prev);
   382   }
   383 
   384   /// \brief Iterator for iterating on uedges connected the same nodes.
   385   ///
   386   /// Iterator for iterating on uedges connected the same nodes. It is 
   387   /// higher level interface for the findUEdge() function. You can
   388   /// use it the following way:
   389   ///\code
   390   /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
   391   ///   ...
   392   /// }
   393   ///\endcode
   394   ///
   395   /// \author Balazs Dezso 
   396   template <typename _Graph>
   397   class ConUEdgeIt : public _Graph::UEdge {
   398   public:
   399 
   400     typedef _Graph Graph;
   401     typedef typename Graph::UEdge Parent;
   402 
   403     typedef typename Graph::UEdge UEdge;
   404     typedef typename Graph::Node Node;
   405 
   406     /// \brief Constructor.
   407     ///
   408     /// Construct a new ConUEdgeIt iterating on the edges which
   409     /// connects the \c u and \c v node.
   410     ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
   411       Parent::operator=(findUEdge(graph, u, v));
   412     }
   413 
   414     /// \brief Constructor.
   415     ///
   416     /// Construct a new ConUEdgeIt which continues the iterating from 
   417     /// the \c e edge.
   418     ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
   419     
   420     /// \brief Increment operator.
   421     ///
   422     /// It increments the iterator and gives back the next edge.
   423     ConUEdgeIt& operator++() {
   424       Parent::operator=(findUEdge(graph, graph.source(*this), 
   425 				      graph.target(*this), *this));
   426       return *this;
   427     }
   428   private:
   429     const Graph& graph;
   430   };
   431 
   432   /// \brief Copy a map.
   433   ///
   434   /// This function copies the \c source map to the \c target map. It uses the
   435   /// given iterator to iterate on the data structure and it uses the \c ref
   436   /// mapping to convert the source's keys to the target's keys.
   437   template <typename Target, typename Source, 
   438 	    typename ItemIt, typename Ref>	    
   439   void copyMap(Target& target, const Source& source, 
   440 	       ItemIt it, const Ref& ref) {
   441     for (; it != INVALID; ++it) {
   442       target[ref[it]] = source[it];
   443     }
   444   }
   445 
   446   /// \brief Copy the source map to the target map.
   447   ///
   448   /// Copy the \c source map to the \c target map. It uses the given iterator
   449   /// to iterate on the data structure.
   450   template <typename Target, typename Source, typename ItemIt>	    
   451   void copyMap(Target& target, const Source& source, ItemIt it) {
   452     for (; it != INVALID; ++it) {
   453       target[it] = source[it];
   454     }
   455   }
   456 
   457   /// \brief Class to copy a graph.
   458   ///
   459   /// Class to copy a graph to an other graph (duplicate a graph). The
   460   /// simplest way of using it is through the \c copyGraph() function.
   461   template <typename Target, typename Source>
   462   class GraphCopy {
   463   public: 
   464     typedef typename Source::Node Node;
   465     typedef typename Source::NodeIt NodeIt;
   466     typedef typename Source::Edge Edge;
   467     typedef typename Source::EdgeIt EdgeIt;
   468 
   469     typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
   470     typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
   471 
   472     /// \brief Constructor for the GraphCopy.
   473     ///
   474     /// It copies the content of the \c _source graph into the
   475     /// \c _target graph. It creates also two references, one beetween
   476     /// the two nodeset and one beetween the two edgesets.
   477     GraphCopy(Target& _target, const Source& _source) 
   478       : source(_source), target(_target), 
   479 	nodeRefMap(_source), edgeRefMap(_source) {
   480       for (NodeIt it(source); it != INVALID; ++it) {
   481 	nodeRefMap[it] = target.addNode();
   482       }
   483       for (EdgeIt it(source); it != INVALID; ++it) {
   484 	edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
   485 					nodeRefMap[source.target(it)]);
   486       }
   487     }
   488 
   489     /// \brief Copies the node references into the given map.
   490     ///
   491     /// Copies the node references into the given map.
   492     template <typename NodeRef>
   493     const GraphCopy& nodeRef(NodeRef& map) const {
   494       for (NodeIt it(source); it != INVALID; ++it) {
   495 	map.set(it, nodeRefMap[it]);
   496       }
   497       return *this;
   498     }
   499 
   500     /// \brief Reverse and copies the node references into the given map.
   501     ///
   502     /// Reverse and copies the node references into the given map.
   503     template <typename NodeRef>
   504     const GraphCopy& nodeCrossRef(NodeRef& map) const {
   505       for (NodeIt it(source); it != INVALID; ++it) {
   506 	map.set(nodeRefMap[it], it);
   507       }
   508       return *this;
   509     }
   510 
   511     /// \brief Copies the edge references into the given map.
   512     ///
   513     /// Copies the edge references into the given map.
   514     template <typename EdgeRef>
   515     const GraphCopy& edgeRef(EdgeRef& map) const {
   516       for (EdgeIt it(source); it != INVALID; ++it) {
   517 	map.set(it, edgeRefMap[it]);
   518       }
   519       return *this;
   520     }
   521 
   522     /// \brief Reverse and copies the edge references into the given map.
   523     ///
   524     /// Reverse and copies the edge references into the given map.
   525     template <typename EdgeRef>
   526     const GraphCopy& edgeCrossRef(EdgeRef& map) const {
   527       for (EdgeIt it(source); it != INVALID; ++it) {
   528 	map.set(edgeRefMap[it], it);
   529       }
   530       return *this;
   531     }
   532 
   533     /// \brief Make copy of the given map.
   534     ///
   535     /// Makes copy of the given map for the newly created graph. 
   536     /// The new map's key type is the target graph's node type,
   537     /// and the copied map's key type is the source graph's node
   538     /// type.  
   539     template <typename TargetMap, typename SourceMap>
   540     const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
   541       copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
   542       return *this;
   543     }
   544 
   545     /// \brief Make copy of the given map.
   546     ///
   547     /// Makes copy of the given map for the newly created graph. 
   548     /// The new map's key type is the target graph's edge type,
   549     /// and the copied map's key type is the source graph's edge
   550     /// type.  
   551     template <typename TargetMap, typename SourceMap>
   552     const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
   553       copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
   554       return *this;
   555     }
   556 
   557     /// \brief Gives back the stored node references.
   558     ///
   559     /// Gives back the stored node references.
   560     const NodeRefMap& nodeRef() const {
   561       return nodeRefMap;
   562     }
   563 
   564     /// \brief Gives back the stored edge references.
   565     ///
   566     /// Gives back the stored edge references.
   567     const EdgeRefMap& edgeRef() const {
   568       return edgeRefMap;
   569     }
   570 
   571     void run() const {}
   572 
   573   private:
   574     
   575     const Source& source;
   576     Target& target;
   577 
   578     NodeRefMap nodeRefMap;
   579     EdgeRefMap edgeRefMap;
   580   };
   581 
   582   /// \brief Copy a graph to an other graph.
   583   ///
   584   /// Copy a graph to an other graph.
   585   /// The usage of the function:
   586   /// 
   587   ///\code
   588   /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
   589   ///\endcode
   590   /// 
   591   /// After the copy the \c nr map will contain the mapping from the
   592   /// source graph's nodes to the target graph's nodes and the \c ecr will
   593   /// contain the mapping from the target graph's edges to the source's
   594   /// edges.
   595   template <typename Target, typename Source>
   596   GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
   597     return GraphCopy<Target, Source>(target, source);
   598   }
   599 
   600   /// \brief Class to copy an undirected graph.
   601   ///
   602   /// Class to copy an undirected graph to an other graph (duplicate a graph).
   603   /// The simplest way of using it is through the \c copyUGraph() function.
   604   template <typename Target, typename Source>
   605   class UGraphCopy {
   606   public: 
   607     typedef typename Source::Node Node;
   608     typedef typename Source::NodeIt NodeIt;
   609     typedef typename Source::Edge Edge;
   610     typedef typename Source::EdgeIt EdgeIt;
   611     typedef typename Source::UEdge UEdge;
   612     typedef typename Source::UEdgeIt UEdgeIt;
   613 
   614     typedef typename Source::
   615     template NodeMap<typename Target::Node> NodeRefMap;
   616     
   617     typedef typename Source::
   618     template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
   619 
   620   private:
   621 
   622     struct EdgeRefMap {
   623       EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
   624       typedef typename Source::Edge Key;
   625       typedef typename Target::Edge Value;
   626 
   627       Value operator[](const Key& key) {
   628 	return gc.target.direct(gc.uEdgeRef[key], 
   629 				gc.target.direction(key));
   630       }
   631       
   632       UGraphCopy& gc;
   633     };
   634     
   635   public:
   636 
   637     /// \brief Constructor for the UGraphCopy.
   638     ///
   639     /// It copies the content of the \c _source graph into the
   640     /// \c _target graph. It creates also two references, one beetween
   641     /// the two nodeset and one beetween the two edgesets.
   642     UGraphCopy(Target& _target, const Source& _source) 
   643       : source(_source), target(_target), 
   644 	nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
   645       for (NodeIt it(source); it != INVALID; ++it) {
   646 	nodeRefMap[it] = target.addNode();
   647       }
   648       for (UEdgeIt it(source); it != INVALID; ++it) {
   649 	uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
   650 					nodeRefMap[source.target(it)]);
   651       }
   652     }
   653 
   654     /// \brief Copies the node references into the given map.
   655     ///
   656     /// Copies the node references into the given map.
   657     template <typename NodeRef>
   658     const UGraphCopy& nodeRef(NodeRef& map) const {
   659       for (NodeIt it(source); it != INVALID; ++it) {
   660 	map.set(it, nodeRefMap[it]);
   661       }
   662       return *this;
   663     }
   664 
   665     /// \brief Reverse and copies the node references into the given map.
   666     ///
   667     /// Reverse and copies the node references into the given map.
   668     template <typename NodeRef>
   669     const UGraphCopy& nodeCrossRef(NodeRef& map) const {
   670       for (NodeIt it(source); it != INVALID; ++it) {
   671 	map.set(nodeRefMap[it], it);
   672       }
   673       return *this;
   674     }
   675 
   676     /// \brief Copies the edge references into the given map.
   677     ///
   678     /// Copies the edge references into the given map.
   679     template <typename EdgeRef>
   680     const UGraphCopy& edgeRef(EdgeRef& map) const {
   681       for (EdgeIt it(source); it != INVALID; ++it) {
   682 	map.set(edgeRefMap[it], it);
   683       }
   684       return *this;
   685     }
   686 
   687     /// \brief Reverse and copies the undirected edge references into the 
   688     /// given map.
   689     ///
   690     /// Reverse and copies the undirected edge references into the given map.
   691     template <typename EdgeRef>
   692     const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
   693       for (EdgeIt it(source); it != INVALID; ++it) {
   694 	map.set(it, edgeRefMap[it]);
   695       }
   696       return *this;
   697     }
   698 
   699     /// \brief Copies the undirected edge references into the given map.
   700     ///
   701     /// Copies the undirected edge references into the given map.
   702     template <typename EdgeRef>
   703     const UGraphCopy& uEdgeRef(EdgeRef& map) const {
   704       for (UEdgeIt it(source); it != INVALID; ++it) {
   705 	map.set(it, uEdgeRefMap[it]);
   706       }
   707       return *this;
   708     }
   709 
   710     /// \brief Reverse and copies the undirected edge references into the 
   711     /// given map.
   712     ///
   713     /// Reverse and copies the undirected edge references into the given map.
   714     template <typename EdgeRef>
   715     const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
   716       for (UEdgeIt it(source); it != INVALID; ++it) {
   717 	map.set(uEdgeRefMap[it], it);
   718       }
   719       return *this;
   720     }
   721 
   722     /// \brief Make copy of the given map.
   723     ///
   724     /// Makes copy of the given map for the newly created graph. 
   725     /// The new map's key type is the target graph's node type,
   726     /// and the copied map's key type is the source graph's node
   727     /// type.  
   728     template <typename TargetMap, typename SourceMap>
   729     const UGraphCopy& nodeMap(TargetMap& tMap, 
   730 				  const SourceMap& sMap) const {
   731       copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
   732       return *this;
   733     }
   734 
   735     /// \brief Make copy of the given map.
   736     ///
   737     /// Makes copy of the given map for the newly created graph. 
   738     /// The new map's key type is the target graph's edge type,
   739     /// and the copied map's key type is the source graph's edge
   740     /// type.  
   741     template <typename TargetMap, typename SourceMap>
   742     const UGraphCopy& edgeMap(TargetMap& tMap, 
   743 				  const SourceMap& sMap) const {
   744       copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
   745       return *this;
   746     }
   747 
   748     /// \brief Make copy of the given map.
   749     ///
   750     /// Makes copy of the given map for the newly created graph. 
   751     /// The new map's key type is the target graph's edge type,
   752     /// and the copied map's key type is the source graph's edge
   753     /// type.  
   754     template <typename TargetMap, typename SourceMap>
   755     const UGraphCopy& uEdgeMap(TargetMap& tMap, 
   756 				  const SourceMap& sMap) const {
   757       copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
   758       return *this;
   759     }
   760 
   761     /// \brief Gives back the stored node references.
   762     ///
   763     /// Gives back the stored node references.
   764     const NodeRefMap& nodeRef() const {
   765       return nodeRefMap;
   766     }
   767 
   768     /// \brief Gives back the stored edge references.
   769     ///
   770     /// Gives back the stored edge references.
   771     const EdgeRefMap& edgeRef() const {
   772       return edgeRefMap;
   773     }
   774 
   775     /// \brief Gives back the stored uedge references.
   776     ///
   777     /// Gives back the stored uedge references.
   778     const UEdgeRefMap& uEdgeRef() const {
   779       return uEdgeRefMap;
   780     }
   781 
   782     void run() const {}
   783 
   784   private:
   785     
   786     const Source& source;
   787     Target& target;
   788 
   789     NodeRefMap nodeRefMap;
   790     EdgeRefMap edgeRefMap;
   791     UEdgeRefMap uEdgeRefMap;
   792   };
   793 
   794   /// \brief Copy a graph to an other graph.
   795   ///
   796   /// Copy a graph to an other graph.
   797   /// The usage of the function:
   798   /// 
   799   ///\code
   800   /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
   801   ///\endcode
   802   /// 
   803   /// After the copy the \c nr map will contain the mapping from the
   804   /// source graph's nodes to the target graph's nodes and the \c ecr will
   805   /// contain the mapping from the target graph's edges to the source's
   806   /// edges.
   807   template <typename Target, typename Source>
   808   UGraphCopy<Target, Source> 
   809   copyUGraph(Target& target, const Source& source) {
   810     return UGraphCopy<Target, Source>(target, source);
   811   }
   812 
   813 
   814   /// @}
   815 
   816   /// \addtogroup graph_maps
   817   /// @{
   818 
   819   /// Provides an immutable and unique id for each item in the graph.
   820 
   821   /// The IdMap class provides a unique and immutable id for each item of the
   822   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
   823   /// different items (nodes) get different ids <li>\b immutable: the id of an
   824   /// item (node) does not change (even if you delete other nodes).  </ul>
   825   /// Through this map you get access (i.e. can read) the inner id values of
   826   /// the items stored in the graph. This map can be inverted with its member
   827   /// class \c InverseMap.
   828   ///
   829   template <typename _Graph, typename _Item>
   830   class IdMap {
   831   public:
   832     typedef _Graph Graph;
   833     typedef int Value;
   834     typedef _Item Item;
   835     typedef _Item Key;
   836 
   837     /// \brief Constructor.
   838     ///
   839     /// Constructor for creating id map.
   840     IdMap(const Graph& _graph) : graph(&_graph) {}
   841 
   842     /// \brief Gives back the \e id of the item.
   843     ///
   844     /// Gives back the immutable and unique \e id of the map.
   845     int operator[](const Item& item) const { return graph->id(item);}
   846 
   847 
   848   private:
   849     const Graph* graph;
   850 
   851   public:
   852 
   853     /// \brief The class represents the inverse of its owner (IdMap).
   854     ///
   855     /// The class represents the inverse of its owner (IdMap).
   856     /// \see inverse()
   857     class InverseMap {
   858     public:
   859 
   860       /// \brief Constructor.
   861       ///
   862       /// Constructor for creating an id-to-item map.
   863       InverseMap(const Graph& _graph) : graph(&_graph) {}
   864 
   865       /// \brief Constructor.
   866       ///
   867       /// Constructor for creating an id-to-item map.
   868       InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
   869 
   870       /// \brief Gives back the given item from its id.
   871       ///
   872       /// Gives back the given item from its id.
   873       /// 
   874       Item operator[](int id) const { return graph->fromId(id, Item());}
   875     private:
   876       const Graph* graph;
   877     };
   878 
   879     /// \brief Gives back the inverse of the map.
   880     ///
   881     /// Gives back the inverse of the IdMap.
   882     InverseMap inverse() const { return InverseMap(*graph);} 
   883 
   884   };
   885 
   886   
   887   /// \brief General invertable graph-map type.
   888 
   889   /// This type provides simple invertable graph-maps. 
   890   /// The InvertableMap wraps an arbitrary ReadWriteMap 
   891   /// and if a key is set to a new value then store it
   892   /// in the inverse map.
   893   ///
   894   /// The values of the map can be accessed
   895   /// with stl compatible forward iterator.
   896   ///
   897   /// \param _Graph The graph type.
   898   /// \param _Item The item type of the graph.
   899   /// \param _Value The value type of the map.
   900   ///
   901   /// \see IterableValueMap
   902 #ifndef DOXYGEN
   903   /// \param _Map A ReadWriteMap mapping from the item type to integer.
   904   template <
   905     typename _Graph, typename _Item, typename _Value, 
   906     typename _Map = DefaultMap<_Graph, _Item, _Value>
   907   >
   908 #else
   909   template <typename _Graph, typename _Item, typename _Value>
   910 #endif
   911   class InvertableMap : protected _Map {
   912   public:
   913 
   914     /// The key type of InvertableMap (Node, Edge, UEdge).
   915     typedef typename _Map::Key Key;
   916     /// The value type of the InvertableMap.
   917     typedef typename _Map::Value Value;
   918 
   919   private:
   920     
   921     typedef _Map Map;
   922     typedef _Graph Graph;
   923 
   924     typedef std::map<Value, Key> Container;
   925     Container invMap;    
   926 
   927   public:
   928  
   929 
   930 
   931     /// \brief Constructor.
   932     ///
   933     /// Construct a new InvertableMap for the graph.
   934     ///
   935     InvertableMap(const Graph& graph) : Map(graph) {} 
   936 
   937     /// \brief Forward iterator for values.
   938     ///
   939     /// This iterator is an stl compatible forward
   940     /// iterator on the values of the map. The values can
   941     /// be accessed in the [beginValue, endValue) range.
   942     ///
   943     class ValueIterator 
   944       : public std::iterator<std::forward_iterator_tag, Value> {
   945       friend class InvertableMap;
   946     private:
   947       ValueIterator(typename Container::const_iterator _it) 
   948         : it(_it) {}
   949     public:
   950       
   951       ValueIterator() {}
   952 
   953       ValueIterator& operator++() { ++it; return *this; }
   954       ValueIterator operator++(int) { 
   955         ValueIterator tmp(*this); 
   956         operator++();
   957         return tmp; 
   958       }
   959 
   960       const Value& operator*() const { return it->first; }
   961       const Value* operator->() const { return &(it->first); }
   962 
   963       bool operator==(ValueIterator jt) const { return it == jt.it; }
   964       bool operator!=(ValueIterator jt) const { return it != jt.it; }
   965       
   966     private:
   967       typename Container::const_iterator it;
   968     };
   969 
   970     /// \brief Returns an iterator to the first value.
   971     ///
   972     /// Returns an stl compatible iterator to the 
   973     /// first value of the map. The values of the
   974     /// map can be accessed in the [beginValue, endValue)
   975     /// range.
   976     ValueIterator beginValue() const {
   977       return ValueIterator(invMap.begin());
   978     }
   979 
   980     /// \brief Returns an iterator after the last value.
   981     ///
   982     /// Returns an stl compatible iterator after the 
   983     /// last value of the map. The values of the
   984     /// map can be accessed in the [beginValue, endValue)
   985     /// range.
   986     ValueIterator endValue() const {
   987       return ValueIterator(invMap.end());
   988     }
   989     
   990     /// \brief The setter function of the map.
   991     ///
   992     /// Sets the mapped value.
   993     void set(const Key& key, const Value& val) {
   994       Value oldval = Map::operator[](key);
   995       typename Container::iterator it = invMap.find(oldval);
   996       if (it != invMap.end() && it->second == key) {
   997 	invMap.erase(it);
   998       }      
   999       invMap.insert(make_pair(val, key));
  1000       Map::set(key, val);
  1001     }
  1002 
  1003     /// \brief The getter function of the map.
  1004     ///
  1005     /// It gives back the value associated with the key.
  1006     typename MapTraits<Map>::ConstReturnValue 
  1007     operator[](const Key& key) const {
  1008       return Map::operator[](key);
  1009     }
  1010 
  1011   protected:
  1012 
  1013     /// \brief Erase the key from the map.
  1014     ///
  1015     /// Erase the key to the map. It is called by the
  1016     /// \c AlterationNotifier.
  1017     virtual void erase(const Key& key) {
  1018       Value val = Map::operator[](key);
  1019       typename Container::iterator it = invMap.find(val);
  1020       if (it != invMap.end() && it->second == key) {
  1021 	invMap.erase(it);
  1022       }
  1023       Map::erase(key);
  1024     }
  1025 
  1026     /// \brief Erase more keys from the map.
  1027     ///
  1028     /// Erase more keys from the map. It is called by the
  1029     /// \c AlterationNotifier.
  1030     virtual void erase(const std::vector<Key>& keys) {
  1031       for (int i = 0; i < (int)keys.size(); ++i) {
  1032 	Value val = Map::operator[](keys[i]);
  1033 	typename Container::iterator it = invMap.find(val);
  1034 	if (it != invMap.end() && it->second == keys[i]) {
  1035 	  invMap.erase(it);
  1036 	}
  1037       }
  1038       Map::erase(keys);
  1039     }
  1040 
  1041     /// \brief Clear the keys from the map and inverse map.
  1042     ///
  1043     /// Clear the keys from the map and inverse map. It is called by the
  1044     /// \c AlterationNotifier.
  1045     virtual void clear() {
  1046       invMap.clear();
  1047       Map::clear();
  1048     }
  1049 
  1050   public:
  1051 
  1052     /// \brief The inverse map type.
  1053     ///
  1054     /// The inverse of this map. The subscript operator of the map
  1055     /// gives back always the item what was last assigned to the value. 
  1056     class InverseMap {
  1057     public:
  1058       /// \brief Constructor of the InverseMap.
  1059       ///
  1060       /// Constructor of the InverseMap.
  1061       InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
  1062 
  1063       /// The value type of the InverseMap.
  1064       typedef typename InvertableMap::Key Value;
  1065       /// The key type of the InverseMap.
  1066       typedef typename InvertableMap::Value Key; 
  1067 
  1068       /// \brief Subscript operator. 
  1069       ///
  1070       /// Subscript operator. It gives back always the item 
  1071       /// what was last assigned to the value.
  1072       Value operator[](const Key& key) const {
  1073 	typename Container::const_iterator it = inverted.invMap.find(key);
  1074 	return it->second;
  1075       }
  1076       
  1077     private:
  1078       const InvertableMap& inverted;
  1079     };
  1080 
  1081     /// \brief It gives back the just readeable inverse map.
  1082     ///
  1083     /// It gives back the just readeable inverse map.
  1084     InverseMap inverse() const {
  1085       return InverseMap(*this);
  1086     } 
  1087 
  1088 
  1089     
  1090   };
  1091 
  1092   /// \brief Provides a mutable, continuous and unique descriptor for each 
  1093   /// item in the graph.
  1094   ///
  1095   /// The DescriptorMap class provides a unique and continuous (but mutable)
  1096   /// descriptor (id) for each item of the same type (e.g. node) in the
  1097   /// graph. This id is <ul><li>\b unique: different items (nodes) get
  1098   /// different ids <li>\b continuous: the range of the ids is the set of
  1099   /// integers between 0 and \c n-1, where \c n is the number of the items of
  1100   /// this type (e.g. nodes) (so the id of a node can change if you delete an
  1101   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  1102   /// with its member class \c InverseMap.
  1103   ///
  1104   /// \param _Graph The graph class the \c DescriptorMap belongs to.
  1105   /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
  1106   /// UEdge.
  1107 #ifndef DOXYGEN
  1108   /// \param _Map A ReadWriteMap mapping from the item type to integer.
  1109   template <
  1110     typename _Graph, typename _Item,
  1111     typename _Map = DefaultMap<_Graph, _Item, int>
  1112   >
  1113 #else
  1114   template <typename _Graph, typename _Item>
  1115 #endif
  1116   class DescriptorMap : protected _Map {
  1117 
  1118     typedef _Item Item;
  1119     typedef _Map Map;
  1120 
  1121   public:
  1122     /// The graph class of DescriptorMap.
  1123     typedef _Graph Graph;
  1124 
  1125     /// The key type of DescriptorMap (Node, Edge, UEdge).
  1126     typedef typename _Map::Key Key;
  1127     /// The value type of DescriptorMap.
  1128     typedef typename _Map::Value Value;
  1129 
  1130     /// \brief Constructor.
  1131     ///
  1132     /// Constructor for descriptor map.
  1133     DescriptorMap(const Graph& _graph) : Map(_graph) {
  1134       build();
  1135     }
  1136 
  1137   protected:
  1138 
  1139     /// \brief Add a new key to the map.
  1140     ///
  1141     /// Add a new key to the map. It is called by the
  1142     /// \c AlterationNotifier.
  1143     virtual void add(const Item& item) {
  1144       Map::add(item);
  1145       Map::set(item, invMap.size());
  1146       invMap.push_back(item);
  1147     }
  1148 
  1149     /// \brief Add more new keys to the map.
  1150     ///
  1151     /// Add more new keys to the map. It is called by the
  1152     /// \c AlterationNotifier.
  1153     virtual void add(const std::vector<Item>& items) {
  1154       Map::add(items);
  1155       for (int i = 0; i < (int)items.size(); ++i) {
  1156 	Map::set(items[i], invMap.size());
  1157 	invMap.push_back(items[i]);
  1158       }
  1159     }
  1160 
  1161     /// \brief Erase the key from the map.
  1162     ///
  1163     /// Erase the key from the map. It is called by the
  1164     /// \c AlterationNotifier.
  1165     virtual void erase(const Item& item) {
  1166       Map::set(invMap.back(), Map::operator[](item));
  1167       invMap[Map::operator[](item)] = invMap.back();
  1168       invMap.pop_back();
  1169       Map::erase(item);
  1170     }
  1171 
  1172     /// \brief Erase more keys from the map.
  1173     ///
  1174     /// Erase more keys from the map. It is called by the
  1175     /// \c AlterationNotifier.
  1176     virtual void erase(const std::vector<Item>& items) {
  1177       for (int i = 0; i < (int)items.size(); ++i) {
  1178 	Map::set(invMap.back(), Map::operator[](items[i]));
  1179 	invMap[Map::operator[](items[i])] = invMap.back();
  1180 	invMap.pop_back();
  1181       }
  1182       Map::erase(items);
  1183     }
  1184 
  1185     /// \brief Build the unique map.
  1186     ///
  1187     /// Build the unique map. It is called by the
  1188     /// \c AlterationNotifier.
  1189     virtual void build() {
  1190       Map::build();
  1191       Item it;
  1192       const typename Map::Notifier* notifier = Map::getNotifier(); 
  1193       for (notifier->first(it); it != INVALID; notifier->next(it)) {
  1194 	Map::set(it, invMap.size());
  1195 	invMap.push_back(it);	
  1196       }      
  1197     }
  1198     
  1199     /// \brief Clear the keys from the map.
  1200     ///
  1201     /// Clear the keys from the map. It is called by the
  1202     /// \c AlterationNotifier.
  1203     virtual void clear() {
  1204       invMap.clear();
  1205       Map::clear();
  1206     }
  1207 
  1208   public:
  1209 
  1210     /// \brief Returns the maximal value plus one.
  1211     ///
  1212     /// Returns the maximal value plus one in the map.
  1213     unsigned int size() const {
  1214       return invMap.size();
  1215     }
  1216 
  1217     /// \brief Swaps the position of the two items in the map.
  1218     ///
  1219     /// Swaps the position of the two items in the map.
  1220     void swap(const Item& p, const Item& q) {
  1221       int pi = Map::operator[](p);
  1222       int qi = Map::operator[](q);
  1223       Map::set(p, qi);
  1224       invMap[qi] = p;
  1225       Map::set(q, pi);
  1226       invMap[pi] = q;
  1227     }
  1228 
  1229     /// \brief Gives back the \e descriptor of the item.
  1230     ///
  1231     /// Gives back the mutable and unique \e descriptor of the map.
  1232     int operator[](const Item& item) const {
  1233       return Map::operator[](item);
  1234     }
  1235     
  1236   private:
  1237 
  1238     typedef std::vector<Item> Container;
  1239     Container invMap;
  1240 
  1241   public:
  1242     /// \brief The inverse map type of DescriptorMap.
  1243     ///
  1244     /// The inverse map type of DescriptorMap.
  1245     class InverseMap {
  1246     public:
  1247       /// \brief Constructor of the InverseMap.
  1248       ///
  1249       /// Constructor of the InverseMap.
  1250       InverseMap(const DescriptorMap& _inverted) 
  1251 	: inverted(_inverted) {}
  1252 
  1253 
  1254       /// The value type of the InverseMap.
  1255       typedef typename DescriptorMap::Key Value;
  1256       /// The key type of the InverseMap.
  1257       typedef typename DescriptorMap::Value Key; 
  1258 
  1259       /// \brief Subscript operator. 
  1260       ///
  1261       /// Subscript operator. It gives back the item 
  1262       /// that the descriptor belongs to currently.
  1263       Value operator[](const Key& key) const {
  1264 	return inverted.invMap[key];
  1265       }
  1266 
  1267       /// \brief Size of the map.
  1268       ///
  1269       /// Returns the size of the map.
  1270       unsigned int size() const {
  1271 	return inverted.invMap.size();
  1272       }
  1273       
  1274     private:
  1275       const DescriptorMap& inverted;
  1276     };
  1277 
  1278     /// \brief Gives back the inverse of the map.
  1279     ///
  1280     /// Gives back the inverse of the map.
  1281     const InverseMap inverse() const {
  1282       return InverseMap(*this);
  1283     }
  1284   };
  1285 
  1286   /// \brief Returns the source of the given edge.
  1287   ///
  1288   /// The SourceMap gives back the source Node of the given edge. 
  1289   /// \author Balazs Dezso
  1290   template <typename Graph>
  1291   class SourceMap {
  1292   public:
  1293 
  1294     typedef typename Graph::Node Value;
  1295     typedef typename Graph::Edge Key;
  1296 
  1297     /// \brief Constructor
  1298     ///
  1299     /// Constructor
  1300     /// \param _graph The graph that the map belongs to.
  1301     SourceMap(const Graph& _graph) : graph(_graph) {}
  1302 
  1303     /// \brief The subscript operator.
  1304     ///
  1305     /// The subscript operator.
  1306     /// \param edge The edge 
  1307     /// \return The source of the edge 
  1308     Value operator[](const Key& edge) const {
  1309       return graph.source(edge);
  1310     }
  1311 
  1312   private:
  1313     const Graph& graph;
  1314   };
  1315 
  1316   /// \brief Returns a \ref SourceMap class
  1317   ///
  1318   /// This function just returns an \ref SourceMap class.
  1319   /// \relates SourceMap
  1320   template <typename Graph>
  1321   inline SourceMap<Graph> sourceMap(const Graph& graph) {
  1322     return SourceMap<Graph>(graph);
  1323   } 
  1324 
  1325   /// \brief Returns the target of the given edge.
  1326   ///
  1327   /// The TargetMap gives back the target Node of the given edge. 
  1328   /// \author Balazs Dezso
  1329   template <typename Graph>
  1330   class TargetMap {
  1331   public:
  1332 
  1333     typedef typename Graph::Node Value;
  1334     typedef typename Graph::Edge Key;
  1335 
  1336     /// \brief Constructor
  1337     ///
  1338     /// Constructor
  1339     /// \param _graph The graph that the map belongs to.
  1340     TargetMap(const Graph& _graph) : graph(_graph) {}
  1341 
  1342     /// \brief The subscript operator.
  1343     ///
  1344     /// The subscript operator.
  1345     /// \param e The edge 
  1346     /// \return The target of the edge 
  1347     Value operator[](const Key& e) const {
  1348       return graph.target(e);
  1349     }
  1350 
  1351   private:
  1352     const Graph& graph;
  1353   };
  1354 
  1355   /// \brief Returns a \ref TargetMap class
  1356   ///
  1357   /// This function just returns a \ref TargetMap class.
  1358   /// \relates TargetMap
  1359   template <typename Graph>
  1360   inline TargetMap<Graph> targetMap(const Graph& graph) {
  1361     return TargetMap<Graph>(graph);
  1362   }
  1363 
  1364   /// \brief Returns the "forward" directed edge view of an undirected edge.
  1365   ///
  1366   /// Returns the "forward" directed edge view of an undirected edge.
  1367   /// \author Balazs Dezso
  1368   template <typename Graph>
  1369   class ForwardMap {
  1370   public:
  1371 
  1372     typedef typename Graph::Edge Value;
  1373     typedef typename Graph::UEdge Key;
  1374 
  1375     /// \brief Constructor
  1376     ///
  1377     /// Constructor
  1378     /// \param _graph The graph that the map belongs to.
  1379     ForwardMap(const Graph& _graph) : graph(_graph) {}
  1380 
  1381     /// \brief The subscript operator.
  1382     ///
  1383     /// The subscript operator.
  1384     /// \param key An undirected edge 
  1385     /// \return The "forward" directed edge view of undirected edge 
  1386     Value operator[](const Key& key) const {
  1387       return graph.direct(key, true);
  1388     }
  1389 
  1390   private:
  1391     const Graph& graph;
  1392   };
  1393 
  1394   /// \brief Returns a \ref ForwardMap class
  1395   ///
  1396   /// This function just returns an \ref ForwardMap class.
  1397   /// \relates ForwardMap
  1398   template <typename Graph>
  1399   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
  1400     return ForwardMap<Graph>(graph);
  1401   }
  1402 
  1403   /// \brief Returns the "backward" directed edge view of an undirected edge.
  1404   ///
  1405   /// Returns the "backward" directed edge view of an undirected edge.
  1406   /// \author Balazs Dezso
  1407   template <typename Graph>
  1408   class BackwardMap {
  1409   public:
  1410 
  1411     typedef typename Graph::Edge Value;
  1412     typedef typename Graph::UEdge Key;
  1413 
  1414     /// \brief Constructor
  1415     ///
  1416     /// Constructor
  1417     /// \param _graph The graph that the map belongs to.
  1418     BackwardMap(const Graph& _graph) : graph(_graph) {}
  1419 
  1420     /// \brief The subscript operator.
  1421     ///
  1422     /// The subscript operator.
  1423     /// \param key An undirected edge 
  1424     /// \return The "backward" directed edge view of undirected edge 
  1425     Value operator[](const Key& key) const {
  1426       return graph.direct(key, false);
  1427     }
  1428 
  1429   private:
  1430     const Graph& graph;
  1431   };
  1432 
  1433   /// \brief Returns a \ref BackwardMap class
  1434 
  1435   /// This function just returns a \ref BackwardMap class.
  1436   /// \relates BackwardMap
  1437   template <typename Graph>
  1438   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
  1439     return BackwardMap<Graph>(graph);
  1440   }
  1441 
  1442   /// \brief Potential difference map
  1443   ///
  1444   /// If there is an potential map on the nodes then we
  1445   /// can get an edge map as we get the substraction of the
  1446   /// values of the target and source.
  1447   template <typename Graph, typename NodeMap>
  1448   class PotentialDifferenceMap {
  1449   public:
  1450     typedef typename Graph::Edge Key;
  1451     typedef typename NodeMap::Value Value;
  1452 
  1453     /// \brief Constructor
  1454     ///
  1455     /// Contructor of the map
  1456     PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential) 
  1457       : graph(_graph), potential(_potential) {}
  1458 
  1459     /// \brief Const subscription operator
  1460     ///
  1461     /// Const subscription operator
  1462     Value operator[](const Key& edge) const {
  1463       return potential[graph.target(edge)] - potential[graph.source(edge)];
  1464     }
  1465 
  1466   private:
  1467     const Graph& graph;
  1468     const NodeMap& potential;
  1469   };
  1470 
  1471   /// \brief Just returns a PotentialDifferenceMap
  1472   ///
  1473   /// Just returns a PotentialDifferenceMap
  1474   /// \relates PotentialDifferenceMap
  1475   template <typename Graph, typename NodeMap>
  1476   PotentialDifferenceMap<Graph, NodeMap> 
  1477   potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
  1478     return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
  1479   }
  1480 
  1481   /// \brief Map of the node in-degrees.
  1482   ///
  1483   /// This map returns the in-degree of a node. Once it is constructed,
  1484   /// the degrees are stored in a standard NodeMap, so each query is done
  1485   /// in constant time. On the other hand, the values are updated automatically
  1486   /// whenever the graph changes.
  1487   ///
  1488   /// \warning Besides addNode() and addEdge(), a graph structure may provide
  1489   /// alternative ways to modify the graph. The correct behavior of InDegMap
  1490   /// is not guarantied if these additional features are used. For example
  1491   /// the functions \ref ListGraph::changeSource() "changeSource()",
  1492   /// \ref ListGraph::changeTarget() "changeTarget()" and
  1493   /// \ref ListGraph::reverseEdge() "reverseEdge()"
  1494   /// of \ref ListGraph will \e not update the degree values correctly.
  1495   ///
  1496   /// \sa OutDegMap
  1497 
  1498   template <typename _Graph>
  1499   class InDegMap  
  1500     : protected ItemSetTraits<_Graph, typename _Graph::Edge>
  1501       ::ItemNotifier::ObserverBase {
  1502 
  1503   public:
  1504     
  1505     typedef _Graph Graph;
  1506     typedef int Value;
  1507     typedef typename Graph::Node Key;
  1508 
  1509     typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
  1510     ::ItemNotifier::ObserverBase Parent;
  1511 
  1512   private:
  1513 
  1514     class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
  1515     public:
  1516 
  1517       typedef DefaultMap<_Graph, Key, int> Parent;
  1518 
  1519       AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
  1520       
  1521       virtual void add(const Key& key) {
  1522 	Parent::add(key);
  1523 	Parent::set(key, 0);
  1524       }
  1525 
  1526       virtual void add(const std::vector<Key>& keys) {
  1527 	Parent::add(keys);
  1528 	for (int i = 0; i < (int)keys.size(); ++i) {
  1529 	  Parent::set(keys[i], 0);
  1530 	}
  1531       }
  1532     };
  1533 
  1534   public:
  1535 
  1536     /// \brief Constructor.
  1537     ///
  1538     /// Constructor for creating in-degree map.
  1539     InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
  1540       Parent::attach(graph.getNotifier(typename _Graph::Edge()));
  1541       
  1542       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1543 	deg[it] = countInEdges(graph, it);
  1544       }
  1545     }
  1546     
  1547     /// Gives back the in-degree of a Node.
  1548     int operator[](const Key& key) const {
  1549       return deg[key];
  1550     }
  1551 
  1552   protected:
  1553     
  1554     typedef typename Graph::Edge Edge;
  1555 
  1556     virtual void add(const Edge& edge) {
  1557       ++deg[graph.target(edge)];
  1558     }
  1559 
  1560     virtual void add(const std::vector<Edge>& edges) {
  1561       for (int i = 0; i < (int)edges.size(); ++i) {
  1562         ++deg[graph.target(edges[i])];
  1563       }
  1564     }
  1565 
  1566     virtual void erase(const Edge& edge) {
  1567       --deg[graph.target(edge)];
  1568     }
  1569 
  1570     virtual void erase(const std::vector<Edge>& edges) {
  1571       for (int i = 0; i < (int)edges.size(); ++i) {
  1572         --deg[graph.target(edges[i])];
  1573       }
  1574     }
  1575 
  1576     virtual void build() {
  1577       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1578 	deg[it] = countInEdges(graph, it);
  1579       }      
  1580     }
  1581 
  1582     virtual void clear() {
  1583       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1584 	deg[it] = 0;
  1585       }
  1586     }
  1587   private:
  1588     
  1589     const _Graph& graph;
  1590     AutoNodeMap deg;
  1591   };
  1592 
  1593   /// \brief Map of the node out-degrees.
  1594   ///
  1595   /// This map returns the out-degree of a node. Once it is constructed,
  1596   /// the degrees are stored in a standard NodeMap, so each query is done
  1597   /// in constant time. On the other hand, the values are updated automatically
  1598   /// whenever the graph changes.
  1599   ///
  1600   /// \warning Besides addNode() and addEdge(), a graph structure may provide
  1601   /// alternative ways to modify the graph. The correct behavior of OutDegMap
  1602   /// is not guarantied if these additional features are used. For example
  1603   /// the functions \ref ListGraph::changeSource() "changeSource()",
  1604   /// \ref ListGraph::changeTarget() "changeTarget()" and
  1605   /// \ref ListGraph::reverseEdge() "reverseEdge()"
  1606   /// of \ref ListGraph will \e not update the degree values correctly.
  1607   ///
  1608   /// \sa InDegMap
  1609 
  1610   template <typename _Graph>
  1611   class OutDegMap  
  1612     : protected ItemSetTraits<_Graph, typename _Graph::Edge>
  1613       ::ItemNotifier::ObserverBase {
  1614 
  1615   public:
  1616 
  1617     typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
  1618     ::ItemNotifier::ObserverBase Parent;
  1619     
  1620     typedef _Graph Graph;
  1621     typedef int Value;
  1622     typedef typename Graph::Node Key;
  1623 
  1624   private:
  1625 
  1626     class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
  1627     public:
  1628 
  1629       typedef DefaultMap<_Graph, Key, int> Parent;
  1630 
  1631       AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
  1632       
  1633       virtual void add(const Key& key) {
  1634 	Parent::add(key);
  1635 	Parent::set(key, 0);
  1636       }
  1637       virtual void add(const std::vector<Key>& keys) {
  1638 	Parent::add(keys);
  1639 	for (int i = 0; i < (int)keys.size(); ++i) {
  1640 	  Parent::set(keys[i], 0);
  1641 	}
  1642       }
  1643     };
  1644 
  1645   public:
  1646 
  1647     /// \brief Constructor.
  1648     ///
  1649     /// Constructor for creating out-degree map.
  1650     OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
  1651       Parent::attach(graph.getNotifier(typename _Graph::Edge()));
  1652       
  1653       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1654 	deg[it] = countOutEdges(graph, it);
  1655       }
  1656     }
  1657 
  1658     /// Gives back the out-degree of a Node.
  1659     int operator[](const Key& key) const {
  1660       return deg[key];
  1661     }
  1662 
  1663   protected:
  1664     
  1665     typedef typename Graph::Edge Edge;
  1666 
  1667     virtual void add(const Edge& edge) {
  1668       ++deg[graph.source(edge)];
  1669     }
  1670 
  1671     virtual void add(const std::vector<Edge>& edges) {
  1672       for (int i = 0; i < (int)edges.size(); ++i) {
  1673         ++deg[graph.source(edges[i])];
  1674       }
  1675     }
  1676 
  1677     virtual void erase(const Edge& edge) {
  1678       --deg[graph.source(edge)];
  1679     }
  1680 
  1681     virtual void erase(const std::vector<Edge>& edges) {
  1682       for (int i = 0; i < (int)edges.size(); ++i) {
  1683         --deg[graph.source(edges[i])];
  1684       }
  1685     }
  1686 
  1687     virtual void build() {
  1688       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1689 	deg[it] = countOutEdges(graph, it);
  1690       }      
  1691     }
  1692 
  1693     virtual void clear() {
  1694       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1695 	deg[it] = 0;
  1696       }
  1697     }
  1698   private:
  1699     
  1700     const _Graph& graph;
  1701     AutoNodeMap deg;
  1702   };
  1703 
  1704 
  1705   /// @}
  1706 
  1707 } //END OF NAMESPACE LEMON
  1708 
  1709 #endif