lemon/graph_utils.h
author deba
Mon, 20 Feb 2006 09:40:07 +0000
changeset 1975 64db671eda28
parent 1946 17eb3eaad9f8
child 1981 81c8efe92706
permissions -rw-r--r--
Second renaming of min cut

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