/* -*- C++ -*-

 * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_GRAPH_UTILS_H

#define LEMON_GRAPH_UTILS_H

#include <iterator>

#include <vector>

#include <map>

#include <cmath>

#include <lemon/invalid.h>

#include <lemon/utility.h>

#include <lemon/maps.h>

#include <lemon/traits.h>

#include <lemon/bits/alteration_notifier.h>

///\ingroup gutils

///\file

///\brief Graph utilities.

///

///

namespace lemon {

  /// \addtogroup gutils

  /// @{

  /// \brief Function to count the items in the graph.

  ///

  /// This function counts the items (nodes, edges etc) in the graph.

  /// The complexity of the function is O(n) because

  /// it iterates on all of the items.

  template <typename Graph, typename ItemIt>

  inline int countItems(const Graph& g) {

    int num = 0;

    for (ItemIt it(g); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  // Node counting:

  template <typename Graph>

  inline

  typename enable_if<typename Graph::NodeNumTag, int>::type

  _countNodes(const Graph &g) {

    return g.nodeNum();

  }

  template <typename Graph>

  inline int _countNodes(Wrap<Graph> w) {

    return countItems<Graph, typename Graph::NodeIt>(w.value);

  }

  /// \brief Function to count the nodes in the graph.

  ///

  /// This function counts the nodes in the graph.

  /// The complexity of the function is O(n) but for some

  /// graph structures it is specialized to run in O(1).

  ///

  /// \todo refer how to specialize it

  template <typename Graph>

  inline int countNodes(const Graph& g) {

    return _countNodes<Graph>(g);

  }

  // Edge counting:

  template <typename Graph>

  inline

  typename enable_if<typename Graph::EdgeNumTag, int>::type

  _countEdges(const Graph &g) {

    return g.edgeNum();

  }

  template <typename Graph>

  inline int _countEdges(Wrap<Graph> w) {

    return countItems<Graph, typename Graph::EdgeIt>(w.value);

  }

  /// \brief Function to count the edges in the graph.

  ///

  /// This function counts the edges in the graph.

  /// The complexity of the function is O(e) but for some

  /// graph structures it is specialized to run in O(1).

  template <typename Graph>

  inline int countEdges(const Graph& g) {

    return _countEdges<Graph>(g);

  }

  // Undirected edge counting:

  template <typename Graph>

  inline

  typename enable_if<typename Graph::EdgeNumTag, int>::type

  _countUndirEdges(const Graph &g) {

    return g.undirEdgeNum();

  }

  template <typename Graph>

  inline int _countUndirEdges(Wrap<Graph> w) {

    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);

  }

  /// \brief Function to count the undirected edges in the graph.

  ///

  /// This function counts the undirected edges in the graph.

  /// The complexity of the function is O(e) but for some

  /// graph structures it is specialized to run in O(1).

  template <typename Graph>

  inline int countUndirEdges(const Graph& g) {

    return _countUndirEdges<Graph>(g);

  }

  template <typename Graph, typename DegIt>

  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {

    int num = 0;

    for (DegIt it(_g, _n); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  /// \brief Function to count the number of the out-edges from node \c n.

  ///

  /// This function counts the number of the out-edges from node \c n

  /// in the graph.  

  template <typename Graph>

  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {

    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);

  }

  /// \brief Function to count the number of the in-edges to node \c n.

  ///

  /// This function counts the number of the in-edges to node \c n

  /// in the graph.  

  template <typename Graph>

  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {

    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);

  }

  /// \brief Function to count the number of the inc-edges to node \c n.

  ///

  /// This function counts the number of the inc-edges to node \c n

  /// in the graph.  

  template <typename Graph>

  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {

    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);

  }

  template <typename Graph>

  inline

  typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 

  _findEdge(const Graph &g,

	    typename Graph::Node u, typename Graph::Node v,

	    typename Graph::Edge prev = INVALID) {

    return g.findEdge(u, v, prev);

  }

  template <typename Graph>

  inline typename Graph::Edge 

  _findEdge(Wrap<Graph> w,

	    typename Graph::Node u, 

	    typename Graph::Node v,

	    typename Graph::Edge prev = INVALID) {

    const Graph& g = w.value;

    if (prev == INVALID) {

      typename Graph::OutEdgeIt e(g, u);

      while (e != INVALID && g.target(e) != v) ++e;

      return e;

    } else {

      typename Graph::OutEdgeIt e(g, prev); ++e;

      while (e != INVALID && g.target(e) != v) ++e;

      return e;

    }

  }

  /// \brief Finds an edge between two nodes of a graph.

  ///

  /// Finds an edge from node \c u to node \c v in graph \c g.

  ///

  /// If \c prev is \ref INVALID (this is the default value), then

  /// it finds the first edge from \c u to \c v. Otherwise it looks for

  /// the next edge from \c u to \c v after \c prev.

  /// \return The found edge or \ref INVALID if there is no such an edge.

  ///

  /// Thus you can iterate through each edge from \c u to \c v as it follows.

  /// \code

  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {

  ///   ...

  /// }

  /// \endcode

  // /// \todo We may want to use the "GraphBase" 

  // /// interface here...

  template <typename Graph>

  inline typename Graph::Edge findEdge(const Graph &g,

				       typename Graph::Node u, 

				       typename Graph::Node v,

				       typename Graph::Edge prev = INVALID) {

    return _findEdge<Graph>(g, u, v, prev);

  }

  /// \brief Iterator for iterating on edges connected the same nodes.

  ///

  /// Iterator for iterating on edges connected the same nodes. It is 

  /// higher level interface for the findEdge() function. You can

  /// use it the following way:

  /// \code

  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {

  ///   ...

  /// }

  /// \endcode

  ///

  /// \author Balazs Dezso 

  template <typename _Graph>

  class ConEdgeIt : public _Graph::Edge {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Edge Parent;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::Node Node;

    /// \brief Constructor.

    ///

    /// Construct a new ConEdgeIt iterating on the edges which

    /// connects the \c u and \c v node.

    ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {

      Parent::operator=(findEdge(graph, u, v));

    }

    /// \brief Constructor.

    ///

    /// Construct a new ConEdgeIt which continues the iterating from 

    /// the \c e edge.

    ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}

    /// \brief Increment operator.

    ///

    /// It increments the iterator and gives back the next edge.

    ConEdgeIt& operator++() {

      Parent::operator=(findEdge(graph, graph.source(*this), 

				 graph.target(*this), *this));

      return *this;

    }

  private:

    const Graph& graph;

  };

  template <typename Graph>

  inline

  typename enable_if<

    typename Graph::FindEdgeTag, 

    typename Graph::UndirEdge>::type 

  _findUndirEdge(const Graph &g,

	    typename Graph::Node u, typename Graph::Node v,

	    typename Graph::UndirEdge prev = INVALID) {

    return g.findUndirEdge(u, v, prev);

  }

  template <typename Graph>

  inline typename Graph::UndirEdge 

  _findUndirEdge(Wrap<Graph> w,

	    typename Graph::Node u, 

	    typename Graph::Node v,

	    typename Graph::UndirEdge prev = INVALID) {

    const Graph& g = w.value;

    if (prev == INVALID) {

      typename Graph::OutEdgeIt e(g, u);

      while (e != INVALID && g.target(e) != v) ++e;

      return e;

    } else {

      typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;

      while (e != INVALID && g.target(e) != v) ++e;

      return e;

    }

  }

  /// \brief Finds an undir edge between two nodes of a graph.

  ///

  /// Finds an undir edge from node \c u to node \c v in graph \c g.

  ///

  /// If \c prev is \ref INVALID (this is the default value), then

  /// it finds the first edge from \c u to \c v. Otherwise it looks for

  /// the next edge from \c u to \c v after \c prev.

  /// \return The found edge or \ref INVALID if there is no such an edge.

  ///

  /// Thus you can iterate through each edge from \c u to \c v as it follows.

  /// \code

  /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID; 

  ///     e = findUndirEdge(g,u,v,e)) {

  ///   ...

  /// }

  /// \endcode

  // /// \todo We may want to use the "GraphBase" 

  // /// interface here...

  template <typename Graph>

  inline typename Graph::UndirEdge 

  findUndirEdge(const Graph &g,

		typename Graph::Node u, 

		typename Graph::Node v,

		typename Graph::UndirEdge prev = INVALID) {

    return _findUndirEdge<Graph>(g, u, v, prev);

  }

  /// \brief Iterator for iterating on undir edges connected the same nodes.

  ///

  /// Iterator for iterating on undir edges connected the same nodes. It is 

  /// higher level interface for the findUndirEdge() function. You can

  /// use it the following way:

  /// \code

  /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {

  ///   ...

  /// }

  /// \endcode

  ///

  /// \author Balazs Dezso 

  template <typename _Graph>

  class ConUndirEdgeIt : public _Graph::UndirEdge {

  public:

    typedef _Graph Graph;

    typedef typename Graph::UndirEdge Parent;

    typedef typename Graph::UndirEdge UndirEdge;

    typedef typename Graph::Node Node;

    /// \brief Constructor.

    ///

    /// Construct a new ConUndirEdgeIt iterating on the edges which

    /// connects the \c u and \c v node.

    ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {

      Parent::operator=(findUndirEdge(graph, u, v));

    }

    /// \brief Constructor.

    ///

    /// Construct a new ConUndirEdgeIt which continues the iterating from 

    /// the \c e edge.

    ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}

    /// \brief Increment operator.

    ///

    /// It increments the iterator and gives back the next edge.

    ConUndirEdgeIt& operator++() {

      Parent::operator=(findUndirEdge(graph, graph.source(*this), 

				 graph.target(*this), *this));

      return *this;

    }

  private:

    const Graph& graph;

  };

  /// \brief Copy a map.

  ///

  /// This function copies the \c source map to the \c target map. It uses the

  /// given iterator to iterate on the data structure and it uses the \c ref

  /// mapping to convert the source's keys to the target's keys.

  template <typename Target, typename Source, 

	    typename ItemIt, typename Ref>	    

  void copyMap(Target& target, const Source& source, 

	       ItemIt it, const Ref& ref) {

    for (; it != INVALID; ++it) {

      target[ref[it]] = source[it];

    }

  }

  /// \brief Copy the source map to the target map.

  ///

  /// Copy the \c source map to the \c target map. It uses the given iterator

  /// to iterate on the data structure.

  template <typename Target, typename Source, 

	    typename ItemIt>	    

  void copyMap(Target& target, const Source& source, ItemIt it) {

    for (; it != INVALID; ++it) {

      target[it] = source[it];

    }

  }

  /// \brief Class to copy a graph.

  ///

  /// Class to copy a graph to an other graph (duplicate a graph). The

  /// simplest way of using it is through the \c copyGraph() function.

  template <typename Target, typename Source>

  class GraphCopy {

  public: 

    typedef typename Source::Node Node;

    typedef typename Source::NodeIt NodeIt;

    typedef typename Source::Edge Edge;

    typedef typename Source::EdgeIt EdgeIt;

    typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;

    typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;

    /// \brief Constructor for the GraphCopy.

    ///

    /// It copies the content of the \c _source graph into the

    /// \c _target graph. It creates also two references, one beetween

    /// the two nodeset and one beetween the two edgesets.

    GraphCopy(Target& _target, const Source& _source) 

      : source(_source), target(_target), 

	nodeRefMap(_source), edgeRefMap(_source) {

      for (NodeIt it(source); it != INVALID; ++it) {

	nodeRefMap[it] = target.addNode();

      }

      for (EdgeIt it(source); it != INVALID; ++it) {

	edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 

					nodeRefMap[source.target(it)]);

      }

    }

    /// \brief Copies the node references into the given map.

    ///

    /// Copies the node references into the given map.

    template <typename NodeRef>

    const GraphCopy& nodeRef(NodeRef& map) const {

      for (NodeIt it(source); it != INVALID; ++it) {

	map.set(it, nodeRefMap[it]);

      }

      return *this;

    }

    /// \brief Reverse and copies the node references into the given map.

    ///

    /// Reverse and copies the node references into the given map.

    template <typename NodeRef>

    const GraphCopy& nodeCrossRef(NodeRef& map) const {

      for (NodeIt it(source); it != INVALID; ++it) {

	map.set(nodeRefMap[it], it);

      }

      return *this;

    }

    /// \brief Copies the edge references into the given map.

    ///

    /// Copies the edge references into the given map.

    template <typename EdgeRef>

    const GraphCopy& edgeRef(EdgeRef& map) const {

      for (EdgeIt it(source); it != INVALID; ++it) {

	map.set(it, edgeRefMap[it]);

      }

      return *this;

    }

    /// \brief Reverse and copies the edge references into the given map.

    ///

    /// Reverse and copies the edge references into the given map.

    template <typename EdgeRef>

    const GraphCopy& edgeCrossRef(EdgeRef& map) const {

      for (EdgeIt it(source); it != INVALID; ++it) {

	map.set(edgeRefMap[it], it);

      }

      return *this;

    }

    /// \brief Make copy of the given map.

    ///

    /// Makes copy of the given map for the newly created graph. 

    /// The new map's key type is the target graph's node type,

    /// and the copied map's key type is the source graph's node

    /// type.  

    template <typename TargetMap, typename SourceMap>

    const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {

      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);

      return *this;

    }

    /// \brief Make copy of the given map.

    ///

    /// Makes copy of the given map for the newly created graph. 

    /// The new map's key type is the target graph's edge type,

    /// and the copied map's key type is the source graph's edge

    /// type.  

    template <typename TargetMap, typename SourceMap>

    const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {

      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);

      return *this;

    }

    /// \brief Gives back the stored node references.

    ///

    /// Gives back the stored node references.

    const NodeRefMap& nodeRef() const {

      return nodeRefMap;

    }

    /// \brief Gives back the stored edge references.

    ///

    /// Gives back the stored edge references.

    const EdgeRefMap& edgeRef() const {

      return edgeRefMap;

    }

    void run() {}

  private:

    const Source& source;

    Target& target;

    NodeRefMap nodeRefMap;

    EdgeRefMap edgeRefMap;

  };

  /// \brief Copy a graph to an other graph.

  ///

  /// Copy a graph to an other graph.

  /// The usage of the function:

  /// 

  /// \code

  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);

  /// \endcode

  /// 

  /// After the copy the \c nr map will contain the mapping from the

  /// source graph's nodes to the target graph's nodes and the \c ecr will

  /// contain the mapping from the target graph's edges to the source's

  /// edges.

  template <typename Target, typename Source>

  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {

    return GraphCopy<Target, Source>(target, source);

  }

  /// \brief Class to copy an undirected graph.

  ///

  /// Class to copy an undirected graph to an other graph (duplicate a graph).

  /// The simplest way of using it is through the \c copyUndirGraph() function.

  template <typename Target, typename Source>

  class UndirGraphCopy {

  public: 

    typedef typename Source::Node Node;

    typedef typename Source::NodeIt NodeIt;

    typedef typename Source::Edge Edge;

    typedef typename Source::EdgeIt EdgeIt;

    typedef typename Source::UndirEdge UndirEdge;

    typedef typename Source::UndirEdgeIt UndirEdgeIt;

    typedef typename Source::

    template NodeMap<typename Target::Node> NodeRefMap;

    typedef typename Source::

    template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;

  private:

    struct EdgeRefMap {

      EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}

      typedef typename Source::Edge Key;

      typedef typename Target::Edge Value;

      Value operator[](const Key& key) {

	return gc.target.direct(gc.undirEdgeRef[key], 

				gc.target.direction(key));

      }

      UndirGraphCopy& gc;

    };

  public:

    /// \brief Constructor for the UndirGraphCopy.

    ///

    /// It copies the content of the \c _source graph into the

    /// \c _target graph. It creates also two references, one beetween

    /// the two nodeset and one beetween the two edgesets.

    UndirGraphCopy(Target& _target, const Source& _source) 

      : source(_source), target(_target), 

	nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {

      for (NodeIt it(source); it != INVALID; ++it) {

	nodeRefMap[it] = target.addNode();

      }

      for (UndirEdgeIt it(source); it != INVALID; ++it) {

	undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 

					nodeRefMap[source.target(it)]);

      }

    }

    /// \brief Copies the node references into the given map.

    ///

    /// Copies the node references into the given map.

    template <typename NodeRef>

    const UndirGraphCopy& nodeRef(NodeRef& map) const {

      for (NodeIt it(source); it != INVALID; ++it) {

	map.set(it, nodeRefMap[it]);

      }

      return *this;

    }

    /// \brief Reverse and copies the node references into the given map.

    ///

    /// Reverse and copies the node references into the given map.

    template <typename NodeRef>

    const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {

      for (NodeIt it(source); it != INVALID; ++it) {

	map.set(nodeRefMap[it], it);

      }

      return *this;

    }

    /// \brief Copies the edge references into the given map.

    ///

    /// Copies the edge references into the given map.

    template <typename EdgeRef>

    const UndirGraphCopy& edgeRef(EdgeRef& map) const {

      for (EdgeIt it(source); it != INVALID; ++it) {

	map.set(edgeRefMap[it], it);

      }

      return *this;

    }

    /// \brief Reverse and copies the undirected edge references into the 

    /// given map.

    ///

    /// Reverse and copies the undirected edge references into the given map.

    template <typename EdgeRef>

    const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {

      for (EdgeIt it(source); it != INVALID; ++it) {

	map.set(it, edgeRefMap[it]);

      }

      return *this;

    }

    /// \brief Copies the undirected edge references into the given map.

    ///

    /// Copies the undirected edge references into the given map.

    template <typename EdgeRef>

    const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {

      for (UndirEdgeIt it(source); it != INVALID; ++it) {

	map.set(it, undirEdgeRefMap[it]);

      }

      return *this;

    }

    /// \brief Reverse and copies the undirected edge references into the 

    /// given map.

    ///

    /// Reverse and copies the undirected edge references into the given map.

    template <typename EdgeRef>

    const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {

      for (UndirEdgeIt it(source); it != INVALID; ++it) {

	map.set(undirEdgeRefMap[it], it);

      }

      return *this;

    }

    /// \brief Make copy of the given map.

    ///

    /// Makes copy of the given map for the newly created graph. 

    /// The new map's key type is the target graph's node type,

    /// and the copied map's key type is the source graph's node

    /// type.  

    template <typename TargetMap, typename SourceMap>

    const UndirGraphCopy& nodeMap(TargetMap& tMap, 

				  const SourceMap& sMap) const {

      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);

      return *this;

    }

    /// \brief Make copy of the given map.

    ///

    /// Makes copy of the given map for the newly created graph. 

    /// The new map's key type is the target graph's edge type,

    /// and the copied map's key type is the source graph's edge

    /// type.  

    template <typename TargetMap, typename SourceMap>

    const UndirGraphCopy& edgeMap(TargetMap& tMap, 

				  const SourceMap& sMap) const {

      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);

      return *this;

    }

    /// \brief Make copy of the given map.

    ///

    /// Makes copy of the given map for the newly created graph. 

    /// The new map's key type is the target graph's edge type,

    /// and the copied map's key type is the source graph's edge

    /// type.  

    template <typename TargetMap, typename SourceMap>

    const UndirGraphCopy& undirEdgeMap(TargetMap& tMap, 

				  const SourceMap& sMap) const {

      copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);

      return *this;

    }

    /// \brief Gives back the stored node references.

    ///

    /// Gives back the stored node references.

    const NodeRefMap& nodeRef() const {

      return nodeRefMap;

    }

    /// \brief Gives back the stored edge references.

    ///

    /// Gives back the stored edge references.

    const EdgeRefMap& edgeRef() const {

      return edgeRefMap;

    }

    /// \brief Gives back the stored undir edge references.

    ///

    /// Gives back the stored undir edge references.

    const UndirEdgeRefMap& undirEdgeRef() const {

      return undirEdgeRefMap;

    }

    void run() {}

  private:

    const Source& source;

    Target& target;

    NodeRefMap nodeRefMap;

    EdgeRefMap edgeRefMap;

    UndirEdgeRefMap undirEdgeRefMap;

  };

  /// \brief Copy a graph to an other graph.

  ///

  /// Copy a graph to an other graph.

  /// The usage of the function:

  /// 

  /// \code

  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);

  /// \endcode

  /// 

  /// After the copy the \c nr map will contain the mapping from the

  /// source graph's nodes to the target graph's nodes and the \c ecr will

  /// contain the mapping from the target graph's edges to the source's

  /// edges.

  template <typename Target, typename Source>

  UndirGraphCopy<Target, Source> 

  copyUndirGraph(Target& target, const Source& source) {

    return UndirGraphCopy<Target, Source>(target, source);

  }

  /// @}

  /// \addtogroup graph_maps

  /// @{

  /// Provides an immutable and unique id for each item in the graph.

  /// The IdMap class provides a unique and immutable id for each item of the

  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:

  /// different items (nodes) get different ids <li>\b immutable: the id of an

  /// item (node) does not change (even if you delete other nodes).  </ul>

  /// Through this map you get access (i.e. can read) the inner id values of

  /// the items stored in the graph. This map can be inverted with its member

  /// class \c InverseMap.

  ///

  template <typename _Graph, typename _Item>

  class IdMap {

  public:

    typedef _Graph Graph;

    typedef int Value;

    typedef _Item Item;

    typedef _Item Key;

    /// \brief Constructor.

    ///

    /// Constructor for creating id map.

    IdMap(const Graph& _graph) : graph(&_graph) {}

    /// \brief Gives back the \e id of the item.

    ///

    /// Gives back the immutable and unique \e id of the map.

    int operator[](const Item& item) const { return graph->id(item);}

  private:

    const Graph* graph;

  public:

    /// \brief The class represents the inverse of its owner (IdMap).

    ///

    /// The class represents the inverse of its owner (IdMap).

    /// \see inverse()

    class InverseMap {

    public:

      /// \brief Constructor.

      ///

      /// Constructor for creating an id-to-item map.

      InverseMap(const Graph& _graph) : graph(&_graph) {}

      /// \brief Constructor.

      ///

      /// Constructor for creating an id-to-item map.

      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}

      /// \brief Gives back the given item from its id.

      ///

      /// Gives back the given item from its id.

      /// 

      Item operator[](int id) const { return graph->fromId(id, Item());}

    private:

      const Graph* graph;

    };

    /// \brief Gives back the inverse of the map.

    ///

    /// Gives back the inverse of the IdMap.

    InverseMap inverse() const { return InverseMap(*graph);} 

  };

  /// \brief General invertable graph-map type.

  /// This type provides simple invertable graph-maps. 

  /// The InvertableMap wraps an arbitrary ReadWriteMap 

  /// and if a key is set to a new value then store it

  /// in the inverse map.

  /// \param _Graph The graph type.

  /// \param _Map The map to extend with invertable functionality. 

  template <

    typename _Graph,

    typename _Item, 

    typename _Value,

    typename _Map 

    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent 

  >

  class InvertableMap : protected _Map {

  public:

    typedef _Map Map;

    typedef _Graph Graph;

    /// The key type of InvertableMap (Node, Edge, UndirEdge).

    typedef typename _Map::Key Key;

    /// The value type of the InvertableMap.

    typedef typename _Map::Value Value;

    /// \brief Constructor.

    ///

    /// Construct a new InvertableMap for the graph.

    ///

    InvertableMap(const Graph& graph) : Map(graph) {} 

    /// \brief The setter function of the map.

    ///

    /// Sets the mapped value.

    void set(const Key& key, const Value& val) {

      Value oldval = Map::operator[](key);

      typename Container::iterator it = invMap.find(oldval);

      if (it != invMap.end() && it->second == key) {

	invMap.erase(it);

      }      

      invMap.insert(make_pair(val, key));

      Map::set(key, val);

    }

    /// \brief The getter function of the map.

    ///

    /// It gives back the value associated with the key.

    Value operator[](const Key& key) const {

      return Map::operator[](key);

    }

  protected:

    /// \brief Add a new key to the map.

    ///

    /// Add a new key to the map. It is called by the

    /// \c AlterationNotifier.

    virtual void add(const Key& key) {

      Map::add(key);

    }

    /// \brief Erase the key from the map.

    ///

    /// Erase the key to the map. It is called by the

    /// \c AlterationNotifier.

    virtual void erase(const Key& key) {

      Value val = Map::operator[](key);

      typename Container::iterator it = invMap.find(val);

      if (it != invMap.end() && it->second == key) {

	invMap.erase(it);

      }

      Map::erase(key);

    }

    /// \brief Clear the keys from the map and inverse map.

    ///

    /// Clear the keys from the map and inverse map. It is called by the

    /// \c AlterationNotifier.

    virtual void clear() {

      invMap.clear();

      Map::clear();

    }

  private:

    typedef std::map<Value, Key> Container;

    Container invMap;    

  public:

    /// \brief The inverse map type.

    ///

    /// The inverse of this map. The subscript operator of the map

    /// gives back always the item what was last assigned to the value. 

    class InverseMap {

    public:

      /// \brief Constructor of the InverseMap.

      ///

      /// Constructor of the InverseMap.

      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}

      /// The value type of the InverseMap.

      typedef typename InvertableMap::Key Value;

      /// The key type of the InverseMap.

      typedef typename InvertableMap::Value Key; 

      /// \brief Subscript operator. 

      ///

      /// Subscript operator. It gives back always the item 

      /// what was last assigned to the value.

      Value operator[](const Key& key) const {

	typename Container::const_iterator it = inverted.invMap.find(key);

	return it->second;

      }

    private:

      const InvertableMap& inverted;

    };

    /// \brief It gives back the just readeable inverse map.

    ///

    /// It gives back the just readeable inverse map.

    InverseMap inverse() const {

      return InverseMap(*this);

    } 

  };

  /// \brief Provides a mutable, continuous and unique descriptor for each 

  /// item in the graph.

  ///

  /// The DescriptorMap class provides a unique and continuous (but mutable)

  /// descriptor (id) for each item of the same type (e.g. node) in the

  /// graph. This id is <ul><li>\b unique: different items (nodes) get

  /// different ids <li>\b continuous: the range of the ids is the set of

  /// integers between 0 and \c n-1, where \c n is the number of the items of

  /// this type (e.g. nodes) (so the id of a node can change if you delete an

  /// other node, i.e. this id is mutable).  </ul> This map can be inverted

  /// with its member class \c InverseMap.

  ///

  /// \param _Graph The graph class the \c DescriptorMap belongs to.

  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 

  /// UndirEdge.

  /// \param _Map A ReadWriteMap mapping from the item type to integer.

  template <

    typename _Graph,   

    typename _Item,

    typename _Map 

    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent

  >

  class DescriptorMap : protected _Map {

    typedef _Item Item;

    typedef _Map Map;

  public: