/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * 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_ADAPTOR_H

#define LEMON_GRAPH_ADAPTOR_H

///\ingroup graph_adaptors

///\file

///\brief Several graph adaptors.

///

///This file contains several useful undirected graph adaptor classes.

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/bits/graph_adaptor_extender.h>

namespace lemon {

  template<typename _Graph>

  class GraphAdaptorBase {

  public:

    typedef _Graph Graph;

    typedef Graph ParentGraph;

  protected:

    Graph* _graph;

    GraphAdaptorBase() : _graph(0) {}

    void setGraph(Graph& graph) { _graph = &graph; }

  public:

    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}

    typedef typename Graph::Node Node;

    typedef typename Graph::Arc Arc;

    typedef typename Graph::Edge Edge;

    void first(Node& i) const { _graph->first(i); }

    void first(Arc& i) const { _graph->first(i); }

    void first(Edge& i) const { _graph->first(i); }

    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }

    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }

    void firstInc(Edge &i, bool &d, const Node &n) const {

      _graph->firstInc(i, d, n);

    }

    void next(Node& i) const { _graph->next(i); }

    void next(Arc& i) const { _graph->next(i); }

    void next(Edge& i) const { _graph->next(i); }

    void nextIn(Arc& i) const { _graph->nextIn(i); }

    void nextOut(Arc& i) const { _graph->nextOut(i); }

    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }

    Node u(const Edge& e) const { return _graph->u(e); }

    Node v(const Edge& e) const { return _graph->v(e); }

    Node source(const Arc& a) const { return _graph->source(a); }

    Node target(const Arc& a) const { return _graph->target(a); }

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

    int nodeNum() const { return _graph->nodeNum(); }

    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

    int arcNum() const { return _graph->arcNum(); }

    int edgeNum() const { return _graph->edgeNum(); }

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {

      return _graph->findArc(u, v, prev);

    }

    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {

      return _graph->findEdge(u, v, prev);

    }

    Node addNode() { return _graph->addNode(); }

    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }

    void erase(const Node& i) { _graph->erase(i); }

    void erase(const Edge& i) { _graph->erase(i); }

    void clear() { _graph->clear(); }

    bool direction(const Arc& a) const { return _graph->direction(a); }

    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }

    int id(const Node& v) const { return _graph->id(v); }

    int id(const Arc& a) const { return _graph->id(a); }

    int id(const Edge& e) const { return _graph->id(e); }

    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }

    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }

    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }

    int maxNodeId() const { return _graph->maxNodeId(); }

    int maxArcId() const { return _graph->maxArcId(); }

    int maxEdgeId() const { return _graph->maxEdgeId(); }

    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 

    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 

    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;

    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 

    template <typename _Value>

    class NodeMap : public Graph::template NodeMap<_Value> {

    public:

      typedef typename Graph::template NodeMap<_Value> Parent;

      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) 

	: Parent(*adapter._graph) {}

      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)

	: Parent(*adapter._graph, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

	return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public Graph::template ArcMap<_Value> {

    public:

      typedef typename Graph::template ArcMap<_Value> Parent;

      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) 

	: Parent(*adapter._graph) {}

      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)

	: Parent(*adapter._graph, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

	return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

	return *this;

      }

    };

    template <typename _Value>

    class EdgeMap : public Graph::template EdgeMap<_Value> {

    public:

      typedef typename Graph::template EdgeMap<_Value> Parent;

      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) 

	: Parent(*adapter._graph) {}

      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)

	: Parent(*adapter._graph, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

	return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  template <typename _Graph, typename NodeFilterMap, 

	    typename EdgeFilterMap, bool checked = true>

  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphAdaptorBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphAdaptorBase() 

      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

      _node_filter_map=&node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

      _edge_filter_map=&edge_filter_map;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    void first(Node& i) const { 

      Parent::first(i); 

      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 

    }

    void first(Arc& i) const { 

      Parent::first(i); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::source(i)]

	     || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i); 

    }

    void first(Edge& i) const { 

      Parent::first(i); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::u(i)]

	     || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i); 

    }

    void firstIn(Arc& i, const Node& n) const { 

      Parent::firstIn(i, n); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 

    }

    void firstOut(Arc& i, const Node& n) const { 

      Parent::firstOut(i, n); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 

    }

    void firstInc(Edge& i, bool& d, const Node& n) const { 

      Parent::firstInc(i, d, n); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

            || !(*_node_filter_map)[Parent::u(i)]

            || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); 

    }

    void next(Node& i) const { 

      Parent::next(i); 

      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 

    }

    void next(Arc& i) const { 

      Parent::next(i); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::source(i)]

	     || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i); 

    }

    void next(Edge& i) const { 

      Parent::next(i); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::u(i)]

	     || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i); 

    }

    void nextIn(Arc& i) const { 

      Parent::nextIn(i); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 

    }

    void nextOut(Arc& i) const { 

      Parent::nextOut(i); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

	     || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 

    }

    void nextInc(Edge& i, bool& d) const { 

      Parent::nextInc(i, d); 

      while (i!=INVALID && (!(*_edge_filter_map)[i]

            || !(*_node_filter_map)[Parent::u(i)]

            || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); 

    }

    void hide(const Node& n) const { _node_filter_map->set(n, false); }

    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }

    void unHide(const Node& n) const { _node_filter_map->set(n, true); }

    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }

    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

    Arc findArc(const Node& u, const Node& v, 

		  const Arc& prev = INVALID) {

      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(u, v, prev);

      while (arc != INVALID && !(*_edge_filter_map)[arc]) {

        arc = Parent::findArc(u, v, arc);

      }

      return arc;

    }

    Edge findEdge(const Node& u, const Node& v, 

		  const Edge& prev = INVALID) {

      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {

        return INVALID;

      }

      Edge edge = Parent::findEdge(u, v, prev);

      while (edge != INVALID && !(*_edge_filter_map)[edge]) {

        edge = Parent::findEdge(u, v, edge);

      }

      return edge;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor, 

        typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor) 

	: MapParent(adaptor) {}

      NodeMap(const Adaptor& adaptor, const Value& value) 

	: MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

	return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

	return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor, 

	typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor) 

	: MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value) 

	: MapParent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

	return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

	return *this;

      }

    };

    template <typename _Value>

    class EdgeMap : public SubMapExtender<Adaptor, 

        typename Parent::template EdgeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template EdgeMap<Value> > MapParent;

      EdgeMap(const Adaptor& adaptor) 

	: MapParent(adaptor) {}

      EdgeMap(const Adaptor& adaptor, const Value& value) 

	: MapParent(adaptor, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

	return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

	return *this;

      }

    };

  };

  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>

  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 

    : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphAdaptorBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphAdaptorBase() : Parent(), 

			    _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

      _node_filter_map=&node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

      _edge_filter_map=&edge_filter_map;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    void first(Node& i) const { 

      Parent::first(i); 

      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 

    }

    void first(Arc& i) const { 

      Parent::first(i); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 

    }

    void first(Edge& i) const { 

      Parent::first(i); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 

    }

    void firstIn(Arc& i, const Node& n) const { 

      Parent::firstIn(i, n); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 

    }

    void firstOut(Arc& i, const Node& n) const { 

      Parent::firstOut(i, n); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 

    }

    void firstInc(Edge& i, bool& d, const Node& n) const { 

      Parent::firstInc(i, d, n); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 

    }

    void next(Node& i) const { 

      Parent::next(i); 

      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 

    }

    void next(Arc& i) const { 

      Parent::next(i); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 

    }

    void next(Edge& i) const { 

      Parent::next(i); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 

    }

    void nextIn(Arc& i) const { 

      Parent::nextIn(i); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 

    }

    void nextOut(Arc& i) const { 

      Parent::nextOut(i); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 

    }

    void nextInc(Edge& i, bool& d) const { 

      Parent::nextInc(i, d); 

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 

    }

    void hide(const Node& n) const { _node_filter_map->set(n, false); }

    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }

    void unHide(const Node& n) const { _node_filter_map->set(n, true); }

    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }

    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

    Arc findArc(const Node& u, const Node& v, 

		  const Arc& prev = INVALID) {

      Arc arc = Parent::findArc(u, v, prev);

      while (arc != INVALID && !(*_edge_filter_map)[arc]) {

        arc = Parent::findArc(u, v, arc);

      }

      return arc;

    }

    Edge findEdge(const Node& u, const Node& v, 

		  const Edge& prev = INVALID) {

      Edge edge = Parent::findEdge(u, v, prev);

      while (edge != INVALID && !(*_edge_filter_map)[edge]) {

        edge = Parent::findEdge(u, v, edge);

      }

      return edge;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor, 

        typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor) 

	: MapParent(adaptor) {}

      NodeMap(const Adaptor& adaptor, const Value& value) 

	: MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

	return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

	return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor, 

	typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor) 

	: MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value) 

	: MapParent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

	return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

	return *this;

      }

    };

    template <typename _Value>

    class EdgeMap : public SubMapExtender<Adaptor, 

        typename Parent::template EdgeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template EdgeMap<Value> > MapParent;

      EdgeMap(const Adaptor& adaptor) 

	: MapParent(adaptor) {}

      EdgeMap(const Adaptor& adaptor, const _Value& value) 

	: MapParent(adaptor, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

	return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

	return *this;

      }

    };

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief A graph adaptor for hiding nodes and edges from an

  /// undirected graph.

  /// 

  /// SubGraphAdaptor shows the graph with filtered node-set and

  /// edge-set. If the \c checked parameter is true then it filters

  /// the edge-set to do not get invalid edges which incident node is

  /// filtered.

  /// 

  /// If the \c checked template parameter is false then we have to

  /// note that the node-iterator cares only the filter on the

  /// node-set, and the edge-iterator cares only the filter on the

  /// edge-set.  This way the edge-map should filter all arcs which

  /// has filtered end node.

  template<typename _Graph, typename NodeFilterMap, 

	   typename EdgeFilterMap, bool checked = true>

  class SubGraphAdaptor : 

    public GraphAdaptorExtender<

    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {

  public:

    typedef _Graph Graph;

    typedef GraphAdaptorExtender<

      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

    typedef typename Parent::Node Node;

    typedef typename Parent::Edge Edge;

  protected:

    SubGraphAdaptor() { }

  public:

    /// \brief Constructor

    ///

    /// Creates a sub-graph-adaptor for the given graph with

    /// given node and edge map filters.

    SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map, 

		    EdgeFilterMap& edge_filter_map) { 

      setGraph(_graph);

      setNodeFilterMap(node_filter_map);

      setEdgeFilterMap(edge_filter_map);

    }

    /// \brief Hides the node of the graph

    ///

    /// This function hides \c n in the digraph, i.e. the iteration 

    /// jumps over it. This is done by simply setting the value of \c n  

    /// to be false in the corresponding node-map.

    void hide(const Node& n) const { Parent::hide(n); }

    /// \brief Hides the edge of the graph

    ///

    /// This function hides \c e in the digraph, i.e. the iteration 

    /// jumps over it. This is done by simply setting the value of \c e

    /// to be false in the corresponding edge-map.

    void hide(const Edge& e) const { Parent::hide(e); }

    /// \brief Unhides the node of the graph

    ///

    /// The value of \c n is set to be true in the node-map which stores 

    /// hide information. If \c n was hidden previuosly, then it is shown 

    /// again

    void unHide(const Node& n) const { Parent::unHide(n); }

    /// \brief Unhides the edge of the graph

    ///

    /// The value of \c e is set to be true in the edge-map which stores 

    /// hide information. If \c e was hidden previuosly, then it is shown 

    /// again

    void unHide(const Edge& e) const { Parent::unHide(e); }

    /// \brief Returns true if \c n is hidden.

    ///

    /// Returns true if \c n is hidden.

    ///

    bool hidden(const Node& n) const { return Parent::hidden(n); }

    /// \brief Returns true if \c e is hidden.

    ///

    /// Returns true if \c e is hidden.

    ///

    bool hidden(const Edge& e) const { return Parent::hidden(e); }

  };

  /// \brief Just gives back a sub-graph adaptor

  ///

  /// Just gives back a sub-graph adaptor

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>

  subGraphAdaptor(const Graph& graph, 

                   NodeFilterMap& nfm, ArcFilterMap& efm) {

    return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>

      (graph, nfm, efm);

  }

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>

  subGraphAdaptor(const Graph& graph, 

                   NodeFilterMap& nfm, ArcFilterMap& efm) {

    return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>

      (graph, nfm, efm);

  }

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>

  subGraphAdaptor(const Graph& graph, 

                   NodeFilterMap& nfm, ArcFilterMap& efm) {

    return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>

      (graph, nfm, efm);

  }

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>

  subGraphAdaptor(const Graph& graph, 

                   NodeFilterMap& nfm, ArcFilterMap& efm) {

    return SubGraphAdaptor<const Graph, const NodeFilterMap, 

      const ArcFilterMap>(graph, nfm, efm);

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief An adaptor for hiding nodes from an graph.

  ///

  /// An adaptor for hiding nodes from an graph.  This

  /// adaptor specializes SubGraphAdaptor in the way that only the

  /// node-set can be filtered. In usual case the checked parameter is

  /// true, we get the induced subgraph. But if the checked parameter

  /// is false then we can filter only isolated nodes.

  template<typename _Graph, typename _NodeFilterMap, bool checked = true>

  class NodeSubGraphAdaptor : 

    public SubGraphAdaptor<_Graph, _NodeFilterMap, 

			   ConstMap<typename _Graph::Edge, bool>, checked> {

  public:

    typedef _Graph Graph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef SubGraphAdaptor<Graph, NodeFilterMap, 

			    ConstMap<typename Graph::Edge, bool> > Parent;

    typedef typename Parent::Node Node;

  protected:

    ConstMap<typename Graph::Edge, bool> const_true_map;

    NodeSubGraphAdaptor() : const_true_map(true) {

      Parent::setEdgeFilterMap(const_true_map);

    }

  public:

    /// \brief Constructor

    ///

    /// Creates a node-sub-graph-adaptor for the given graph with

    /// given node map filters.

    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) : 

      Parent(), const_true_map(true) { 

      Parent::setGraph(_graph);

      Parent::setNodeFilterMap(node_filter_map);

      Parent::setEdgeFilterMap(const_true_map);

    }

    /// \brief Hides the node of the graph

    ///

    /// This function hides \c n in the digraph, i.e. the iteration 

    /// jumps over it. This is done by simply setting the value of \c n  

    /// to be false in the corresponding node-map.

    void hide(const Node& n) const { Parent::hide(n); }

    /// \brief Unhides the node of the graph

    ///

    /// The value of \c n is set to be true in the node-map which stores 

    /// hide information. If \c n was hidden previuosly, then it is shown 

    /// again

    void unHide(const Node& n) const { Parent::unHide(n); }

    /// \brief Returns true if \c n is hidden.

    ///

    /// Returns true if \c n is hidden.

    ///

    bool hidden(const Node& n) const { return Parent::hidden(n); }

  };

  /// \brief Just gives back a node-sub-graph adaptor

  ///

  /// Just gives back a node-sub-graph adaptor

  template<typename Graph, typename NodeFilterMap>

  NodeSubGraphAdaptor<const Graph, NodeFilterMap>

  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {

    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);

  }

  template<typename Graph, typename NodeFilterMap>

  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>

  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {

    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief An adaptor for hiding edges from an graph.

  ///

  /// \warning Graph adaptors are in even more experimental state

  /// than the other parts of the lib. Use them at you own risk.

  ///

  /// An adaptor for hiding edges from an graph.

  /// This adaptor specializes SubGraphAdaptor in the way that

  /// only the arc-set 

  /// can be filtered.

  template<typename _Graph, typename _EdgeFilterMap>

  class EdgeSubGraphAdaptor : 

    public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>, 

                           _EdgeFilterMap, false> {

  public:

    typedef _Graph Graph;

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 

			    EdgeFilterMap, false> Parent;

    typedef typename Parent::Edge Edge;

  protected:

    ConstMap<typename Graph::Node, bool> const_true_map;

    EdgeSubGraphAdaptor() : const_true_map(true) {

      Parent::setNodeFilterMap(const_true_map);

    }

  public:

    /// \brief Constructor

    ///

    /// Creates a edge-sub-graph-adaptor for the given graph with

    /// given node map filters.

    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) : 

      Parent(), const_true_map(true) { 

      Parent::setGraph(_graph);

      Parent::setNodeFilterMap(const_true_map);

      Parent::setEdgeFilterMap(edge_filter_map);

    }

    /// \brief Hides the edge of the graph

    ///

    /// This function hides \c e in the digraph, i.e. the iteration 

    /// jumps over it. This is done by simply setting the value of \c e

    /// to be false in the corresponding edge-map.

    void hide(const Edge& e) const { Parent::hide(e); }

    /// \brief Unhides the edge of the graph

    ///

    /// The value of \c e is set to be true in the edge-map which stores 

    /// hide information. If \c e was hidden previuosly, then it is shown 

    /// again

    void unHide(const Edge& e) const { Parent::unHide(e); }

    /// \brief Returns true if \c e is hidden.

    ///

    /// Returns true if \c e is hidden.

    ///

    bool hidden(const Edge& e) const { return Parent::hidden(e); }

  };

  /// \brief Just gives back an edge-sub-graph adaptor

  ///

  /// Just gives back an edge-sub-graph adaptor

  template<typename Graph, typename EdgeFilterMap>

  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>

  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {

    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);

  }

  template<typename Graph, typename EdgeFilterMap>

  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>

  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {

    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);

  }

  template <typename _Graph, typename _DirectionMap>

  class DirGraphAdaptorBase {

  public:

    typedef _Graph Graph;

    typedef _DirectionMap DirectionMap;

    typedef typename Graph::Node Node;

    typedef typename Graph::Edge Arc;

    /// \brief Reverse arc

    /// 

    /// It reverse the given arc. It simply negate the direction in the map.

    void reverseArc(const Arc& arc) {

      _direction->set(arc, !(*_direction)[arc]);

    }

    void first(Node& i) const { _graph->first(i); }

    void first(Arc& i) const { _graph->first(i); }

    void firstIn(Arc& i, const Node& n) const {

      bool d;

      _graph->firstInc(i, d, n);

      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

    }

    void firstOut(Arc& i, const Node& n ) const { 

      bool d;

      _graph->firstInc(i, d, n);

      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

    }

    void next(Node& i) const { _graph->next(i); }

    void next(Arc& i) const { _graph->next(i); }

    void nextIn(Arc& i) const {

      bool d = !(*_direction)[i];

      _graph->nextInc(i, d);

      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

    }

    void nextOut(Arc& i) const {

      bool d = (*_direction)[i];

      _graph->nextInc(i, d);

      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

    }

    Node source(const Arc& e) const { 

      return (*_direction)[e] ? _graph->u(e) : _graph->v(e); 

    }

    Node target(const Arc& e) const { 

      return (*_direction)[e] ? _graph->v(e) : _graph->u(e); 

    }

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

    int nodeNum() const { return _graph->nodeNum(); }

    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

    int arcNum() const { return _graph->edgeNum(); }

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

    Arc findArc(const Node& u, const Node& v, 

		  const Arc& prev = INVALID) {

      Arc arc = prev;

      bool d = arc == INVALID ? true : (*_direction)[arc];

      if (d) {

        arc = _graph->findEdge(u, v, arc);

        while (arc != INVALID && !(*_direction)[arc]) {

          _graph->findEdge(u, v, arc);

        }

        if (arc != INVALID) return arc;

      }

      _graph->findEdge(v, u, arc);

      while (arc != INVALID && (*_direction)[arc]) {

        _graph->findEdge(u, v, arc);

      }

      return arc;

    }

    Node addNode() { 

      return Node(_graph->addNode()); 

    }

    Arc addArc(const Node& u, const Node& v) {

      Arc arc = _graph->addArc(u, v);

      _direction->set(arc, _graph->source(arc) == u);

      return arc; 

    }

    void erase(const Node& i) { _graph->erase(i); }

    void erase(const Arc& i) { _graph->erase(i); }

    void clear() { _graph->clear(); }

    int id(const Node& v) const { return _graph->id(v); }

    int id(const Arc& e) const { return _graph->id(e); }

    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }

    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }

    int maxNodeId() const { return _graph->maxNodeId(); }

    int maxArcId() const { return _graph->maxEdgeId(); }

    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 

    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 

    template <typename _Value>

    class NodeMap : public _Graph::template NodeMap<_Value> {

    public:

      typedef typename _Graph::template NodeMap<_Value> Parent;

      explicit NodeMap(const DirGraphAdaptorBase& adapter) 

	: Parent(*adapter._graph) {}

      NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)

	: Parent(*adapter._graph, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>