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