lemon/graph_utils.h
author alpar
Sat, 27 Aug 2005 09:32:34 +0000
changeset 1659 ab1e97b7b2b7
parent 1591 03aa0a6c8dca
child 1674 648aa2f33dc8
permissions -rw-r--r--
Dependency problem (guipixbufs.h) is solved.
     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 
    24 #include <lemon/invalid.h>
    25 #include <lemon/utility.h>
    26 #include <lemon/maps.h>
    27 #include <lemon/bits/alteration_notifier.h>
    28 
    29 ///\ingroup gutils
    30 ///\file
    31 ///\brief Graph utilities.
    32 ///
    33 ///
    34 
    35 
    36 namespace lemon {
    37 
    38   /// \addtogroup gutils
    39   /// @{
    40 
    41   /// \brief Function to count the items in the graph.
    42   ///
    43   /// This function counts the items (nodes, edges etc) in the graph.
    44   /// The complexity of the function is O(n) because
    45   /// it iterates on all of the items.
    46 
    47   template <typename Graph, typename ItemIt>
    48   inline int countItems(const Graph& g) {
    49     int num = 0;
    50     for (ItemIt it(g); it != INVALID; ++it) {
    51       ++num;
    52     }
    53     return num;
    54   }
    55 
    56   // Node counting:
    57 
    58   template <typename Graph>
    59   inline
    60   typename enable_if<typename Graph::NodeNumTag, int>::type
    61   _countNodes(const Graph &g) {
    62     return g.nodeNum();
    63   }
    64 
    65   template <typename Graph>
    66   inline int _countNodes(Wrap<Graph> w) {
    67     return countItems<Graph, typename Graph::NodeIt>(w.value);
    68   }
    69 
    70   /// \brief Function to count the nodes in the graph.
    71   ///
    72   /// This function counts the nodes in the graph.
    73   /// The complexity of the function is O(n) but for some
    74   /// graph structures it is specialized to run in O(1).
    75   ///
    76   /// \todo refer how to specialize it
    77 
    78   template <typename Graph>
    79   inline int countNodes(const Graph& g) {
    80     return _countNodes<Graph>(g);
    81   }
    82 
    83   // Edge counting:
    84 
    85   template <typename Graph>
    86   inline
    87   typename enable_if<typename Graph::EdgeNumTag, int>::type
    88   _countEdges(const Graph &g) {
    89     return g.edgeNum();
    90   }
    91 
    92   template <typename Graph>
    93   inline int _countEdges(Wrap<Graph> w) {
    94     return countItems<Graph, typename Graph::EdgeIt>(w.value);
    95   }
    96 
    97   /// \brief Function to count the edges in the graph.
    98   ///
    99   /// This function counts the edges in the graph.
   100   /// The complexity of the function is O(e) but for some
   101   /// graph structures it is specialized to run in O(1).
   102 
   103   template <typename Graph>
   104   inline int countEdges(const Graph& g) {
   105     return _countEdges<Graph>(g);
   106   }
   107 
   108   // Undirected edge counting:
   109 
   110   template <typename Graph>
   111   inline
   112   typename enable_if<typename Graph::EdgeNumTag, int>::type
   113   _countUndirEdges(const Graph &g) {
   114     return g.undirEdgeNum();
   115   }
   116 
   117   template <typename Graph>
   118   inline int _countUndirEdges(Wrap<Graph> w) {
   119     return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
   120   }
   121 
   122   /// \brief Function to count the undirected edges in the graph.
   123   ///
   124   /// This function counts the undirected edges in the graph.
   125   /// The complexity of the function is O(e) but for some
   126   /// graph structures it is specialized to run in O(1).
   127 
   128   template <typename Graph>
   129   inline int countUndirEdges(const Graph& g) {
   130     return _countUndirEdges<Graph>(g);
   131   }
   132 
   133 
   134 
   135   template <typename Graph, typename DegIt>
   136   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   137     int num = 0;
   138     for (DegIt it(_g, _n); it != INVALID; ++it) {
   139       ++num;
   140     }
   141     return num;
   142   }
   143 
   144   /// \brief Function to count the number of the out-edges from node \c n.
   145   ///
   146   /// This function counts the number of the out-edges from node \c n
   147   /// in the graph.  
   148   template <typename Graph>
   149   inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
   150     return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
   151   }
   152 
   153   /// \brief Function to count the number of the in-edges to node \c n.
   154   ///
   155   /// This function counts the number of the in-edges to node \c n
   156   /// in the graph.  
   157   template <typename Graph>
   158   inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
   159     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
   160   }
   161 
   162 
   163   template <typename Graph>
   164   inline
   165   typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 
   166   _findEdge(const Graph &g,
   167 	    typename Graph::Node u, typename Graph::Node v,
   168 	    typename Graph::Edge prev = INVALID) {
   169     return g.findEdge(u, v, prev);
   170   }
   171 
   172   template <typename Graph>
   173   inline typename Graph::Edge 
   174   _findEdge(Wrap<Graph> w,
   175 	    typename Graph::Node u, 
   176 	    typename Graph::Node v,
   177 	    typename Graph::Edge prev = INVALID) {
   178     const Graph& g = w.value;
   179     if (prev == INVALID) {
   180       typename Graph::OutEdgeIt e(g, u);
   181       while (e != INVALID && g.target(e) != v) ++e;
   182       return e;
   183     } else {
   184       typename Graph::OutEdgeIt e(g, prev); ++e;
   185       while (e != INVALID && g.target(e) != v) ++e;
   186       return e;
   187     }
   188   }
   189 
   190   /// \brief Finds an edge between two nodes of a graph.
   191   ///
   192   /// Finds an edge from node \c u to node \c v in graph \c g.
   193   ///
   194   /// If \c prev is \ref INVALID (this is the default value), then
   195   /// it finds the first edge from \c u to \c v. Otherwise it looks for
   196   /// the next edge from \c u to \c v after \c prev.
   197   /// \return The found edge or \ref INVALID if there is no such an edge.
   198   ///
   199   /// Thus you can iterate through each edge from \c u to \c v as it follows.
   200   /// \code
   201   /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
   202   ///   ...
   203   /// }
   204   /// \endcode
   205   // /// \todo We may want to use the "GraphBase" 
   206   // /// interface here...
   207   // /// It would not work with the undirected graphs.
   208   template <typename Graph>
   209   inline typename Graph::Edge findEdge(const Graph &g,
   210 				       typename Graph::Node u, 
   211 				       typename Graph::Node v,
   212 				       typename Graph::Edge prev = INVALID) {
   213     return _findEdge<Graph>(g, u, v, prev);
   214   }
   215 
   216   /// \brief Iterator for iterating on edges connected the same nodes.
   217   ///
   218   /// Iterator for iterating on edges connected the same nodes. It is 
   219   /// higher level interface for the findEdge() function. You can
   220   /// use it the following way:
   221   /// \code
   222   /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
   223   ///   ...
   224   /// }
   225   /// \endcode
   226   ///
   227   /// \author Balazs Dezso 
   228   template <typename _Graph>
   229   class ConEdgeIt : public _Graph::Edge {
   230   public:
   231 
   232     typedef _Graph Graph;
   233     typedef typename Graph::Edge Parent;
   234 
   235     typedef typename Graph::Edge Edge;
   236     typedef typename Graph::Node Node;
   237 
   238     /// \brief Constructor.
   239     ///
   240     /// Construct a new ConEdgeIt iterating on the edges which
   241     /// connects the \c u and \c v node.
   242     ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
   243       Parent::operator=(findEdge(graph, u, v));
   244     }
   245 
   246     /// \brief Constructor.
   247     ///
   248     /// Construct a new ConEdgeIt which continues the iterating from 
   249     /// the \c e edge.
   250     ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
   251     
   252     /// \brief Increment operator.
   253     ///
   254     /// It increments the iterator and gives back the next edge.
   255     ConEdgeIt& operator++() {
   256       Parent::operator=(findEdge(graph, graph.source(*this), 
   257 				 graph.target(*this), *this));
   258       return *this;
   259     }
   260   private:
   261     const Graph& graph;
   262   };
   263 
   264   /// \brief Copy a map.
   265   ///
   266   /// This function copies the \c source map to the \c target map. It uses the
   267   /// given iterator to iterate on the data structure and it uses the \c ref
   268   /// mapping to convert the source's keys to the target's keys.
   269   template <typename Target, typename Source, 
   270 	    typename ItemIt, typename Ref>	    
   271   void copyMap(Target& target, const Source& source, 
   272 	       ItemIt it, const Ref& ref) {
   273     for (; it != INVALID; ++it) {
   274       target[ref[it]] = source[it];
   275     }
   276   }
   277 
   278   /// \brief Copy the source map to the target map.
   279   ///
   280   /// Copy the \c source map to the \c target map. It uses the given iterator
   281   /// to iterate on the data structure.
   282   template <typename Target, typename Source, 
   283 	    typename ItemIt>	    
   284   void copyMap(Target& target, const Source& source, ItemIt it) {
   285     for (; it != INVALID; ++it) {
   286       target[it] = source[it];
   287     }
   288   }
   289 
   290 
   291   /// \brief Class to copy a graph.
   292   ///
   293   /// Class to copy a graph to an other graph (duplicate a graph). The
   294   /// simplest way of using it is through the \c copyGraph() function.
   295   template <typename Target, typename Source>
   296   class GraphCopy {
   297   public: 
   298     typedef typename Source::Node Node;
   299     typedef typename Source::NodeIt NodeIt;
   300     typedef typename Source::Edge Edge;
   301     typedef typename Source::EdgeIt EdgeIt;
   302 
   303     typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
   304     typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
   305 
   306     /// \brief Constructor for the GraphCopy.
   307     ///
   308     /// It copies the content of the \c _source graph into the
   309     /// \c _target graph. It creates also two references, one beetween
   310     /// the two nodeset and one beetween the two edgesets.
   311     GraphCopy(Target& _target, const Source& _source) 
   312       : source(_source), target(_target), 
   313 	nodeRefMap(_source), edgeRefMap(_source) {
   314       for (NodeIt it(source); it != INVALID; ++it) {
   315 	nodeRefMap[it] = target.addNode();
   316       }
   317       for (EdgeIt it(source); it != INVALID; ++it) {
   318 	edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
   319 					nodeRefMap[source.target(it)]);
   320       }
   321     }
   322 
   323     /// \brief Copies the node references into the given map.
   324     ///
   325     /// Copies the node references into the given map.
   326     template <typename NodeRef>
   327     const GraphCopy& nodeRef(NodeRef& map) const {
   328       for (NodeIt it(source); it != INVALID; ++it) {
   329 	map.set(it, nodeRefMap[it]);
   330       }
   331       return *this;
   332     }
   333 
   334     /// \brief Reverse and copies the node references into the given map.
   335     ///
   336     /// Reverse and copies the node references into the given map.
   337     template <typename NodeRef>
   338     const GraphCopy& nodeCrossRef(NodeRef& map) const {
   339       for (NodeIt it(source); it != INVALID; ++it) {
   340 	map.set(nodeRefMap[it], it);
   341       }
   342       return *this;
   343     }
   344 
   345     /// \brief Copies the edge references into the given map.
   346     ///
   347     /// Copies the edge references into the given map.
   348     template <typename EdgeRef>
   349     const GraphCopy& edgeRef(EdgeRef& map) const {
   350       for (EdgeIt it(source); it != INVALID; ++it) {
   351 	map.set(it, edgeRefMap[it]);
   352       }
   353       return *this;
   354     }
   355 
   356     /// \brief Reverse and copies the edge references into the given map.
   357     ///
   358     /// Reverse and copies the edge references into the given map.
   359     template <typename EdgeRef>
   360     const GraphCopy& edgeCrossRef(EdgeRef& map) const {
   361       for (EdgeIt it(source); it != INVALID; ++it) {
   362 	map.set(edgeRefMap[it], it);
   363       }
   364       return *this;
   365     }
   366 
   367     /// \brief Make copy of the given map.
   368     ///
   369     /// Makes copy of the given map for the newly created graph. 
   370     /// The new map's key type is the target graph's node type,
   371     /// and the copied map's key type is the source graph's node
   372     /// type.  
   373     template <typename TargetMap, typename SourceMap>
   374     const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
   375       copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
   376       return *this;
   377     }
   378 
   379     /// \brief Make copy of the given map.
   380     ///
   381     /// Makes copy of the given map for the newly created graph. 
   382     /// The new map's key type is the target graph's edge type,
   383     /// and the copied map's key type is the source graph's edge
   384     /// type.  
   385     template <typename TargetMap, typename SourceMap>
   386     const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
   387       copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
   388       return *this;
   389     }
   390 
   391     /// \brief Gives back the stored node references.
   392     ///
   393     /// Gives back the stored node references.
   394     const NodeRefMap& nodeRef() const {
   395       return nodeRefMap;
   396     }
   397 
   398     /// \brief Gives back the stored edge references.
   399     ///
   400     /// Gives back the stored edge references.
   401     const EdgeRefMap& edgeRef() const {
   402       return edgeRefMap;
   403     }
   404 
   405   private:
   406     
   407     const Source& source;
   408     Target& target;
   409 
   410     NodeRefMap nodeRefMap;
   411     EdgeRefMap edgeRefMap;
   412   };
   413 
   414   /// \brief Copy a graph to an other graph.
   415   ///
   416   /// Copy a graph to an other graph.
   417   /// The usage of the function:
   418   /// 
   419   /// \code
   420   /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
   421   /// \endcode
   422   /// 
   423   /// After the copy the \c nr map will contain the mapping from the
   424   /// source graph's nodes to the target graph's nodes and the \c ecr will
   425   /// contain the mapping from the target graph's edges to the source's
   426   /// edges.
   427   template <typename Target, typename Source>
   428   GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
   429     return GraphCopy<Target, Source>(target, source);
   430   }
   431 
   432   template <typename _Graph, typename _Item>
   433   class ItemSetTraits {};
   434   
   435   template <typename _Graph>
   436   class ItemSetTraits<_Graph, typename _Graph::Node> {
   437   public:
   438     
   439     typedef _Graph Graph;
   440 
   441     typedef typename Graph::Node Item;
   442     typedef typename Graph::NodeIt ItemIt;
   443 
   444     template <typename _Value>
   445     class Map : public Graph::template NodeMap<_Value> {
   446     public:
   447       typedef typename Graph::template NodeMap<_Value> Parent; 
   448       typedef typename Parent::Value Value;
   449 
   450       Map(const Graph& _graph) : Parent(_graph) {}
   451       Map(const Graph& _graph, const Value& _value) 
   452 	: Parent(_graph, _value) {}
   453     };
   454 
   455   };
   456 
   457   template <typename _Graph>
   458   class ItemSetTraits<_Graph, typename _Graph::Edge> {
   459   public:
   460     
   461     typedef _Graph Graph;
   462 
   463     typedef typename Graph::Edge Item;
   464     typedef typename Graph::EdgeIt ItemIt;
   465 
   466     template <typename _Value>
   467     class Map : public Graph::template EdgeMap<_Value> {
   468     public:
   469       typedef typename Graph::template EdgeMap<_Value> Parent; 
   470       typedef typename Parent::Value Value;
   471 
   472       Map(const Graph& _graph) : Parent(_graph) {}
   473       Map(const Graph& _graph, const Value& _value) 
   474 	: Parent(_graph, _value) {}
   475     };
   476 
   477   };
   478 
   479   template <typename _Graph>
   480   class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
   481   public:
   482     
   483     typedef _Graph Graph;
   484 
   485     typedef typename Graph::UndirEdge Item;
   486     typedef typename Graph::UndirEdgeIt ItemIt;
   487 
   488     template <typename _Value>
   489     class Map : public Graph::template UndirEdgeMap<_Value> {
   490     public:
   491       typedef typename Graph::template UndirEdgeMap<_Value> Parent; 
   492       typedef typename Parent::Value Value;
   493 
   494       Map(const Graph& _graph) : Parent(_graph) {}
   495       Map(const Graph& _graph, const Value& _value) 
   496 	: Parent(_graph, _value) {}
   497     };
   498 
   499   };
   500 
   501   /// @}
   502 
   503   /// \addtogroup graph_maps
   504   /// @{
   505 
   506   template <typename Map, typename Enable = void>
   507   struct ReferenceMapTraits {
   508     typedef typename Map::Value Value;
   509     typedef typename Map::Value& Reference;
   510     typedef const typename Map::Value& ConstReference;
   511     typedef typename Map::Value* Pointer;
   512     typedef const typename Map::Value* ConstPointer;
   513   };
   514 
   515   template <typename Map>
   516   struct ReferenceMapTraits<
   517     Map, 
   518     typename enable_if<typename Map::FullTypeTag, void>::type
   519   > {
   520     typedef typename Map::Value Value;
   521     typedef typename Map::Reference Reference;
   522     typedef typename Map::ConstReference ConstReference;
   523     typedef typename Map::Pointer Pointer;
   524     typedef typename Map::ConstPointer ConstPointer;
   525   };
   526 
   527   /// Provides an immutable and unique id for each item in the graph.
   528 
   529   /// The IdMap class provides a unique and immutable id for each item of the
   530   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
   531   /// different items (nodes) get different ids <li>\b immutable: the id of an
   532   /// item (node) does not change (even if you delete other nodes).  </ul>
   533   /// Through this map you get access (i.e. can read) the inner id values of
   534   /// the items stored in the graph. This map can be inverted with its member
   535   /// class \c InverseMap.
   536   ///
   537   template <typename _Graph, typename _Item>
   538   class IdMap {
   539   public:
   540     typedef _Graph Graph;
   541     typedef int Value;
   542     typedef _Item Item;
   543     typedef _Item Key;
   544 
   545     typedef True NeedCopy;
   546 
   547     /// \brief Constructor.
   548     ///
   549     /// Constructor for creating id map.
   550     IdMap(const Graph& _graph) : graph(&_graph) {}
   551 
   552     /// \brief Gives back the \e id of the item.
   553     ///
   554     /// Gives back the immutable and unique \e id of the map.
   555     int operator[](const Item& item) const { return graph->id(item);}
   556 
   557 
   558   private:
   559     const Graph* graph;
   560 
   561   public:
   562 
   563     /// \brief The class represents the inverse of its owner (IdMap).
   564     ///
   565     /// The class represents the inverse of its owner (IdMap).
   566     /// \see inverse()
   567     class InverseMap {
   568     public:
   569 
   570       typedef True NeedCopy;
   571 
   572       /// \brief Constructor.
   573       ///
   574       /// Constructor for creating an id-to-item map.
   575       InverseMap(const Graph& _graph) : graph(&_graph) {}
   576 
   577       /// \brief Constructor.
   578       ///
   579       /// Constructor for creating an id-to-item map.
   580       InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
   581 
   582       /// \brief Gives back the given item from its id.
   583       ///
   584       /// Gives back the given item from its id.
   585       /// 
   586       Item operator[](int id) const { return graph->fromId(id, Item());}
   587     private:
   588       const Graph* graph;
   589     };
   590 
   591     /// \brief Gives back the inverse of the map.
   592     ///
   593     /// Gives back the inverse of the IdMap.
   594     InverseMap inverse() const { return InverseMap(*graph);} 
   595 
   596   };
   597 
   598   
   599   /// \brief General invertable graph-map type.
   600 
   601   /// This type provides simple invertable graph-maps. 
   602   /// The InvertableMap wraps an arbitrary ReadWriteMap 
   603   /// and if a key is set to a new value then store it
   604   /// in the inverse map.
   605   /// \param _Graph The graph type.
   606   /// \param _Map The map to extend with invertable functionality. 
   607   template <
   608     typename _Graph,
   609     typename _Item, 
   610     typename _Value,
   611     typename _Map 
   612     = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent 
   613   >
   614   class InvertableMap : protected _Map {
   615 
   616   public:
   617  
   618     typedef _Map Map;
   619     typedef _Graph Graph;
   620 
   621     /// The key type of InvertableMap (Node, Edge, UndirEdge).
   622     typedef typename _Map::Key Key;
   623     /// The value type of the InvertableMap.
   624     typedef typename _Map::Value Value;
   625 
   626     /// \brief Constructor.
   627     ///
   628     /// Construct a new InvertableMap for the graph.
   629     ///
   630     InvertableMap(const Graph& graph) : Map(graph) {} 
   631     
   632     /// \brief The setter function of the map.
   633     ///
   634     /// Sets the mapped value.
   635     void set(const Key& key, const Value& val) {
   636       Value oldval = Map::operator[](key);
   637       typename Container::iterator it = invMap.find(oldval);
   638       if (it != invMap.end() && it->second == key) {
   639 	invMap.erase(it);
   640       }      
   641       invMap.insert(make_pair(val, key));
   642       Map::set(key, val);
   643     }
   644 
   645     /// \brief The getter function of the map.
   646     ///
   647     /// It gives back the value associated with the key.
   648     const Value operator[](const Key& key) const {
   649       return Map::operator[](key);
   650     }
   651 
   652   protected:
   653 
   654     /// \brief Add a new key to the map.
   655     ///
   656     /// Add a new key to the map. It is called by the
   657     /// \c AlterationNotifier.
   658     virtual void add(const Key& key) {
   659       Map::add(key);
   660     }
   661 
   662     /// \brief Erase the key from the map.
   663     ///
   664     /// Erase the key to the map. It is called by the
   665     /// \c AlterationNotifier.
   666     virtual void erase(const Key& key) {
   667       Value val = Map::operator[](key);
   668       typename Container::iterator it = invMap.find(val);
   669       if (it != invMap.end() && it->second == key) {
   670 	invMap.erase(it);
   671       }
   672       Map::erase(key);
   673     }
   674 
   675     /// \brief Clear the keys from the map and inverse map.
   676     ///
   677     /// Clear the keys from the map and inverse map. It is called by the
   678     /// \c AlterationNotifier.
   679     virtual void clear() {
   680       invMap.clear();
   681       Map::clear();
   682     }
   683 
   684   private:
   685     
   686     typedef std::map<Value, Key> Container;
   687     Container invMap;    
   688 
   689   public:
   690 
   691     /// \brief The inverse map type.
   692     ///
   693     /// The inverse of this map. The subscript operator of the map
   694     /// gives back always the item what was last assigned to the value. 
   695     class InverseMap {
   696     public:
   697       /// \brief Constructor of the InverseMap.
   698       ///
   699       /// Constructor of the InverseMap.
   700       InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
   701 
   702       /// The value type of the InverseMap.
   703       typedef typename InvertableMap::Key Value;
   704       /// The key type of the InverseMap.
   705       typedef typename InvertableMap::Value Key; 
   706 
   707       /// \brief Subscript operator. 
   708       ///
   709       /// Subscript operator. It gives back always the item 
   710       /// what was last assigned to the value.
   711       Value operator[](const Key& key) const {
   712 	typename Container::const_iterator it = inverted.invMap.find(key);
   713 	return it->second;
   714       }
   715       
   716     private:
   717       const InvertableMap& inverted;
   718     };
   719 
   720     /// \brief It gives back the just readeable inverse map.
   721     ///
   722     /// It gives back the just readeable inverse map.
   723     InverseMap inverse() const {
   724       return InverseMap(*this);
   725     } 
   726 
   727 
   728     
   729   };
   730 
   731   /// \brief Provides a mutable, continuous and unique descriptor for each 
   732   /// item in the graph.
   733   ///
   734   /// The DescriptorMap class provides a unique and continuous (but mutable)
   735   /// descriptor (id) for each item of the same type (e.g. node) in the
   736   /// graph. This id is <ul><li>\b unique: different items (nodes) get
   737   /// different ids <li>\b continuous: the range of the ids is the set of
   738   /// integers between 0 and \c n-1, where \c n is the number of the items of
   739   /// this type (e.g. nodes) (so the id of a node can change if you delete an
   740   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
   741   /// with its member class \c InverseMap.
   742   ///
   743   /// \param _Graph The graph class the \c DescriptorMap belongs to.
   744   /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
   745   /// UndirEdge.
   746   /// \param _Map A ReadWriteMap mapping from the item type to integer.
   747   template <
   748     typename _Graph,   
   749     typename _Item,
   750     typename _Map 
   751     = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
   752   >
   753   class DescriptorMap : protected _Map {
   754 
   755     typedef _Item Item;
   756     typedef _Map Map;
   757 
   758   public:
   759     /// The graph class of DescriptorMap.
   760     typedef _Graph Graph;
   761 
   762     /// The key type of DescriptorMap (Node, Edge, UndirEdge).
   763     typedef typename _Map::Key Key;
   764     /// The value type of DescriptorMap.
   765     typedef typename _Map::Value Value;
   766 
   767     /// \brief Constructor.
   768     ///
   769     /// Constructor for descriptor map.
   770     DescriptorMap(const Graph& _graph) : Map(_graph) {
   771       build();
   772     }
   773 
   774   protected:
   775 
   776     /// \brief Add a new key to the map.
   777     ///
   778     /// Add a new key to the map. It is called by the
   779     /// \c AlterationNotifier.
   780     virtual void add(const Item& item) {
   781       Map::add(item);
   782       Map::set(item, invMap.size());
   783       invMap.push_back(item);
   784     }
   785 
   786     /// \brief Erase the key from the map.
   787     ///
   788     /// Erase the key to the map. It is called by the
   789     /// \c AlterationNotifier.
   790     virtual void erase(const Item& item) {
   791       Map::set(invMap.back(), Map::operator[](item));
   792       invMap[Map::operator[](item)] = invMap.back();
   793       invMap.pop_back();
   794       Map::erase(item);
   795     }
   796 
   797     /// \brief Build the unique map.
   798     ///
   799     /// Build the unique map. It is called by the
   800     /// \c AlterationNotifier.
   801     virtual void build() {
   802       Map::build();
   803       Item it;
   804       const typename Map::Graph* graph = Map::getGraph(); 
   805       for (graph->first(it); it != INVALID; graph->next(it)) {
   806 	Map::set(it, invMap.size());
   807 	invMap.push_back(it);	
   808       }      
   809     }
   810     
   811     /// \brief Clear the keys from the map.
   812     ///
   813     /// Clear the keys from the map. It is called by the
   814     /// \c AlterationNotifier.
   815     virtual void clear() {
   816       invMap.clear();
   817       Map::clear();
   818     }
   819 
   820   public:
   821 
   822     /// \brief Swaps the position of the two items in the map.
   823     ///
   824     /// Swaps the position of the two items in the map.
   825     void swap(const Item& p, const Item& q) {
   826       int pi = Map::operator[](p);
   827       int qi = Map::operator[](q);
   828       Map::set(p, qi);
   829       invMap[qi] = p;
   830       Map::set(q, pi);
   831       invMap[pi] = q;
   832     }
   833 
   834     /// \brief Gives back the \e descriptor of the item.
   835     ///
   836     /// Gives back the mutable and unique \e descriptor of the map.
   837     int operator[](const Item& item) const {
   838       return Map::operator[](item);
   839     }
   840     
   841   private:
   842 
   843     typedef std::vector<Item> Container;
   844     Container invMap;
   845 
   846   public:
   847     /// \brief The inverse map type of DescriptorMap.
   848     ///
   849     /// The inverse map type of DescriptorMap.
   850     class InverseMap {
   851     public:
   852       /// \brief Constructor of the InverseMap.
   853       ///
   854       /// Constructor of the InverseMap.
   855       InverseMap(const DescriptorMap& _inverted) 
   856 	: inverted(_inverted) {}
   857 
   858 
   859       /// The value type of the InverseMap.
   860       typedef typename DescriptorMap::Key Value;
   861       /// The key type of the InverseMap.
   862       typedef typename DescriptorMap::Value Key; 
   863 
   864       /// \brief Subscript operator. 
   865       ///
   866       /// Subscript operator. It gives back the item 
   867       /// that the descriptor belongs to currently.
   868       Value operator[](const Key& key) const {
   869 	return inverted.invMap[key];
   870       }
   871 
   872       /// \brief Size of the map.
   873       ///
   874       /// Returns the size of the map.
   875       int size() const {
   876 	return inverted.invMap.size();
   877       }
   878       
   879     private:
   880       const DescriptorMap& inverted;
   881     };
   882 
   883     /// \brief Gives back the inverse of the map.
   884     ///
   885     /// Gives back the inverse of the map.
   886     const InverseMap inverse() const {
   887       return InverseMap(*this);
   888     }
   889   };
   890 
   891   /// \brief Returns the source of the given edge.
   892   ///
   893   /// The SourceMap gives back the source Node of the given edge. 
   894   /// \author Balazs Dezso
   895   template <typename Graph>
   896   class SourceMap {
   897   public:
   898 
   899     typedef True NeedCopy;
   900 
   901     typedef typename Graph::Node Value;
   902     typedef typename Graph::Edge Key;
   903 
   904     /// \brief Constructor
   905     ///
   906     /// Constructor
   907     /// \param _graph The graph that the map belongs to.
   908     SourceMap(const Graph& _graph) : graph(_graph) {}
   909 
   910     /// \brief The subscript operator.
   911     ///
   912     /// The subscript operator.
   913     /// \param edge The edge 
   914     /// \return The source of the edge 
   915     Value operator[](const Key& edge) {
   916       return graph.source(edge);
   917     }
   918 
   919   private:
   920     const Graph& graph;
   921   };
   922 
   923   /// \brief Returns a \ref SourceMap class
   924   ///
   925   /// This function just returns an \ref SourceMap class.
   926   /// \relates SourceMap
   927   template <typename Graph>
   928   inline SourceMap<Graph> sourceMap(const Graph& graph) {
   929     return SourceMap<Graph>(graph);
   930   } 
   931 
   932   /// \brief Returns the target of the given edge.
   933   ///
   934   /// The TargetMap gives back the target Node of the given edge. 
   935   /// \author Balazs Dezso
   936   template <typename Graph>
   937   class TargetMap {
   938   public:
   939 
   940     typedef True NeedCopy;
   941 
   942     typedef typename Graph::Node Value;
   943     typedef typename Graph::Edge Key;
   944 
   945     /// \brief Constructor
   946     ///
   947     /// Constructor
   948     /// \param _graph The graph that the map belongs to.
   949     TargetMap(const Graph& _graph) : graph(_graph) {}
   950 
   951     /// \brief The subscript operator.
   952     ///
   953     /// The subscript operator.
   954     /// \param e The edge 
   955     /// \return The target of the edge 
   956     Value operator[](const Key& e) {
   957       return graph.target(e);
   958     }
   959 
   960   private:
   961     const Graph& graph;
   962   };
   963 
   964   /// \brief Returns a \ref TargetMap class
   965   ///
   966   /// This function just returns a \ref TargetMap class.
   967   /// \relates TargetMap
   968   template <typename Graph>
   969   inline TargetMap<Graph> targetMap(const Graph& graph) {
   970     return TargetMap<Graph>(graph);
   971   }
   972 
   973   /// \brief Returns the "forward" directed edge view of an undirected edge.
   974   ///
   975   /// Returns the "forward" directed edge view of an undirected edge.
   976   /// \author Balazs Dezso
   977   template <typename Graph>
   978   class ForwardMap {
   979   public:
   980 
   981     typedef True NeedCopy;
   982 
   983     typedef typename Graph::Edge Value;
   984     typedef typename Graph::UndirEdge Key;
   985 
   986     /// \brief Constructor
   987     ///
   988     /// Constructor
   989     /// \param _graph The graph that the map belongs to.
   990     ForwardMap(const Graph& _graph) : graph(_graph) {}
   991 
   992     /// \brief The subscript operator.
   993     ///
   994     /// The subscript operator.
   995     /// \param key An undirected edge 
   996     /// \return The "forward" directed edge view of undirected edge 
   997     Value operator[](const Key& key) const {
   998       return graph.direct(key, true);
   999     }
  1000 
  1001   private:
  1002     const Graph& graph;
  1003   };
  1004 
  1005   /// \brief Returns a \ref ForwardMap class
  1006   ///
  1007   /// This function just returns an \ref ForwardMap class.
  1008   /// \relates ForwardMap
  1009   template <typename Graph>
  1010   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
  1011     return ForwardMap<Graph>(graph);
  1012   }
  1013 
  1014   /// \brief Returns the "backward" directed edge view of an undirected edge.
  1015   ///
  1016   /// Returns the "backward" directed edge view of an undirected edge.
  1017   /// \author Balazs Dezso
  1018   template <typename Graph>
  1019   class BackwardMap {
  1020   public:
  1021     typedef True NeedCopy;
  1022 
  1023     typedef typename Graph::Edge Value;
  1024     typedef typename Graph::UndirEdge Key;
  1025 
  1026     /// \brief Constructor
  1027     ///
  1028     /// Constructor
  1029     /// \param _graph The graph that the map belongs to.
  1030     BackwardMap(const Graph& _graph) : graph(_graph) {}
  1031 
  1032     /// \brief The subscript operator.
  1033     ///
  1034     /// The subscript operator.
  1035     /// \param key An undirected edge 
  1036     /// \return The "backward" directed edge view of undirected edge 
  1037     Value operator[](const Key& key) const {
  1038       return graph.direct(key, false);
  1039     }
  1040 
  1041   private:
  1042     const Graph& graph;
  1043   };
  1044 
  1045   /// \brief Returns a \ref BackwardMap class
  1046 
  1047   /// This function just returns a \ref BackwardMap class.
  1048   /// \relates BackwardMap
  1049   template <typename Graph>
  1050   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
  1051     return BackwardMap<Graph>(graph);
  1052   }
  1053 
  1054   template <typename _Graph>
  1055   class DegMapBase {
  1056   public:
  1057     
  1058     typedef _Graph Graph;
  1059 
  1060   protected:
  1061 
  1062     typedef typename Graph::template NodeMap<int> IntNodeMap;
  1063     
  1064   };
  1065 
  1066   /// \brief Map of the node in-degrees.
  1067   ///
  1068   /// This map returns the in-degree of a node. Once it is constructed,
  1069   /// the degrees are stored in a standard NodeMap, so each query is done
  1070   /// in constant time. On the other hand, the values are updated automatically
  1071   /// whenever the graph changes.
  1072   ///
  1073   /// \sa OutDegMap
  1074 
  1075   template <typename _Graph>
  1076   class InDegMap  
  1077     : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
  1078 
  1079   public:
  1080     
  1081     typedef _Graph Graph;
  1082     typedef int Value;
  1083     typedef typename Graph::Node Key;
  1084 
  1085   private:
  1086 
  1087     class AutoNodeMap : public Graph::template NodeMap<int> {
  1088     public:
  1089 
  1090       typedef typename Graph::template NodeMap<int> Parent;
  1091 
  1092       typedef typename Parent::Key Key;
  1093       typedef typename Parent::Value Value;
  1094       
  1095       AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
  1096       
  1097       void add(const Key& key) {
  1098 	Parent::add(key);
  1099 	Parent::set(key, 0);
  1100       }
  1101     };
  1102 
  1103   public:
  1104 
  1105     /// \brief Constructor.
  1106     ///
  1107     /// Constructor for creating in-degree map.
  1108     InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
  1109       AlterationNotifier<typename _Graph::Edge>
  1110 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
  1111       
  1112       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1113 	deg[it] = countInEdges(graph, it);
  1114       }
  1115     }
  1116 
  1117     virtual ~InDegMap() {
  1118       AlterationNotifier<typename _Graph::Edge>::
  1119 	ObserverBase::detach();
  1120     }
  1121     
  1122     /// Gives back the in-degree of a Node.
  1123     int operator[](const Key& key) const {
  1124       return deg[key];
  1125     }
  1126 
  1127   protected:
  1128     
  1129     typedef typename Graph::Edge Edge;
  1130 
  1131     virtual void add(const Edge& edge) {
  1132       ++deg[graph.target(edge)];
  1133     }
  1134 
  1135     virtual void erase(const Edge& edge) {
  1136       --deg[graph.target(edge)];
  1137     }
  1138 
  1139 
  1140     virtual void build() {
  1141       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1142 	deg[it] = countInEdges(graph, it);
  1143       }      
  1144     }
  1145 
  1146     virtual void clear() {
  1147       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1148 	deg[it] = 0;
  1149       }
  1150     }
  1151   private:
  1152     
  1153     const _Graph& graph;
  1154     AutoNodeMap deg;
  1155   };
  1156 
  1157 
  1158   /// \brief Map of the node out-degrees.
  1159   ///
  1160   /// This map returns the out-degree of a node. Once it is constructed,
  1161   /// the degrees are stored in a standard NodeMap, so each query is done
  1162   /// in constant time. On the other hand, the values are updated automatically
  1163   /// whenever the graph changes.
  1164   ///
  1165   /// \sa InDegMap
  1166 
  1167   template <typename _Graph>
  1168   class OutDegMap  
  1169     : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
  1170 
  1171   public:
  1172     
  1173     typedef _Graph Graph;
  1174     typedef int Value;
  1175     typedef typename Graph::Node Key;
  1176 
  1177   private:
  1178 
  1179     class AutoNodeMap : public Graph::template NodeMap<int> {
  1180     public:
  1181 
  1182       typedef typename Graph::template NodeMap<int> Parent;
  1183 
  1184       typedef typename Parent::Key Key;
  1185       typedef typename Parent::Value Value;
  1186       
  1187       AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
  1188       
  1189       void add(const Key& key) {
  1190 	Parent::add(key);
  1191 	Parent::set(key, 0);
  1192       }
  1193     };
  1194 
  1195   public:
  1196 
  1197     /// \brief Constructor.
  1198     ///
  1199     /// Constructor for creating out-degree map.
  1200     OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
  1201       AlterationNotifier<typename _Graph::Edge>
  1202 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
  1203       
  1204       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1205 	deg[it] = countOutEdges(graph, it);
  1206       }
  1207     }
  1208 
  1209     virtual ~OutDegMap() {
  1210       AlterationNotifier<typename _Graph::Edge>::
  1211 	ObserverBase::detach();
  1212     }
  1213     
  1214     /// Gives back the in-degree of a Node.
  1215     int operator[](const Key& key) const {
  1216       return deg[key];
  1217     }
  1218 
  1219   protected:
  1220     
  1221     typedef typename Graph::Edge Edge;
  1222 
  1223     virtual void add(const Edge& edge) {
  1224       ++deg[graph.source(edge)];
  1225     }
  1226 
  1227     virtual void erase(const Edge& edge) {
  1228       --deg[graph.source(edge)];
  1229     }
  1230 
  1231 
  1232     virtual void build() {
  1233       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1234 	deg[it] = countOutEdges(graph, it);
  1235       }      
  1236     }
  1237 
  1238     virtual void clear() {
  1239       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1240 	deg[it] = 0;
  1241       }
  1242     }
  1243   private:
  1244     
  1245     const _Graph& graph;
  1246     AutoNodeMap deg;
  1247   };
  1248 
  1249   /// @}
  1250 
  1251 } //END OF NAMESPACE LEMON
  1252 
  1253 #endif