/* -*- C++ -*-

  *

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

  *

  * Copyright (C) 2003-2006

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

 #define LEMON_UGRAPH_ADAPTOR_H

 ///\ingroup graph_adaptors

 ///\file

 ///\brief Several graph adaptors.

 ///

 ///This file contains several useful ugraph adaptor functions.

 ///

 ///\author Balazs Dezso

 #include <lemon/invalid.h>

 #include <lemon/maps.h>

 #include <lemon/bits/graph_adaptor_extender.h>

 #include <lemon/traits.h>

 #include <iostream>

 namespace lemon {

   /// \ingroup graph_adaptors

   ///

   /// \brief Base type for the Graph Adaptors

   ///

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

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

   ///

   /// This is the base type for most of LEMON graph adaptors. 

   /// This class implements a trivial graph adaptor i.e. it only wraps the 

   /// functions and types of the graph. The purpose of this class is to 

   /// make easier implementing graph adaptors. E.g. if an adaptor is 

   /// considered which differs from the wrapped graph only in some of its 

   /// functions or types, then it can be derived from GraphAdaptor, and only 

   /// the differences should be implemented.

   ///

   /// \author Balazs Dezso 

   template<typename _UGraph>

   class UGraphAdaptorBase {

   public:

     typedef _UGraph Graph;

     typedef Graph ParentGraph;

   protected:

     Graph* graph;

     UGraphAdaptorBase() : graph(0) {}

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

     Graph& getGraph() { return *graph; }

     const Graph& getGraph() const { return *graph; }

   public:

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

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::UEdge UEdge;

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

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

     void first(UEdge& i) const { graph->first(i); }

     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }

     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

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

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

     }

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

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

     void next(UEdge& i) const { graph->next(i); }

     void nextIn(Edge& i) const { graph->nextIn(i); }

     void nextOut(Edge& i) const { graph->nextOut(i); }

     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }

     Node source(const UEdge& e) const { return graph->source(e); }

     Node target(const UEdge& e) const { return graph->target(e); }

     Node source(const Edge& e) const { return graph->source(e); }

     Node target(const Edge& e) const { return graph->target(e); }

     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& source, const Node& target, 

 		  const Edge& prev = INVALID) {

       return graph->findEdge(source, target, prev);

     }

     UEdge findUEdge(const Node& source, const Node& target, 

                     const UEdge& prev = INVALID) {

       return graph->findUEdge(source, target, prev);

     }

     Node addNode() const { return graph->addNode(); }

     UEdge addEdge(const Node& source, const Node& target) const { 

       return graph->addEdge(source, target); 

     }

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

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

     void clear() const { graph->clear(); }

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

     int id(const UEdge& e) const { return graph->id(e); }

     bool direction(const Edge& e) const { return graph->direction(e); }

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

     Edge direct(const UEdge& e, const Node& n) const { 

       return graph->direct(e, n); 

     }

     Node oppositeNode(const Node& n, const Edge& e) const { 

       return graph->oppositeNode(n, e); 

     }

     Edge oppositeEdge(const Edge& e) const { 

       return graph->oppositeEdge(e); 

     }

     template <typename _Value>

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

     public:

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

       explicit NodeMap(const UGraphAdaptorBase<Graph>& ga) 

 	: Parent(*ga.graph) {}

       NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)

 	: Parent(*ga.graph, value) {}

       NodeMap& operator=(const NodeMap& cmap) {

 	return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();

 	const typename Parent::Graph* graph = Parent::getGraph();

 	Node it;

 	for (graph->first(it); it != INVALID; graph->next(it)) {

 	  Parent::set(it, cmap[it]);

 	}

 	return *this;

       }

     };

     template <typename _Value>

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

     public:

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

       explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga) 

 	: Parent(*ga.graph) {}

       EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)

 	: Parent(*ga.graph, value) {}

       EdgeMap& operator=(const EdgeMap& cmap) {

 	return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();

 	const typename Parent::Graph* graph = Parent::getGraph();

 	Edge it;

 	for (graph->first(it); it != INVALID; graph->next(it)) {

 	  Parent::set(it, cmap[it]);

 	}

 	return *this;

       }

     };

     template <typename _Value>

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

     public:

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

       explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga) 

 	: Parent(*ga.graph) {}

       UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)

 	: Parent(*ga.graph, value) {}

       UEdgeMap& operator=(const UEdgeMap& cmap) {

 	return operator=<UEdgeMap>(cmap);

       }

       template <typename CMap>

       UEdgeMap& operator=(const CMap& cmap) {

 	checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();

 	const typename Parent::Graph* graph = Parent::getGraph();

 	UEdge it;

 	for (graph->first(it); it != INVALID; graph->next(it)) {

 	  Parent::set(it, cmap[it]);

 	}

 	return *this;

       }

     };

   };

   /// \ingroup graph_adaptors

   template <typename _UGraph>

   class UGraphAdaptor 

     : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > { 

   public:

     typedef _UGraph Graph;

     typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;

   protected:

     UGraphAdaptor() : Parent() {}

   public:

     explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }

   };

   template <typename _UGraph, typename NodeFilterMap, 

 	    typename UEdgeFilterMap, bool checked = true>

   class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {

   public:

     typedef _UGraph Graph;

     typedef UGraphAdaptorBase<_UGraph> Parent;

   protected:

     NodeFilterMap* node_filter_map;

     UEdgeFilterMap* uedge_filter_map;

     SubUGraphAdaptorBase() 

       : Parent(), node_filter_map(0), uedge_filter_map(0) { }

     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

       node_filter_map=&_node_filter_map;

     }

     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

       uedge_filter_map=&_uedge_filter_map;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef typename Parent::UEdge UEdge;

     void first(Node& i) const { 

       Parent::first(i); 

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

     }

     void first(Edge& i) const { 

       Parent::first(i); 

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

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

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

     }

     void first(UEdge& i) const { 

       Parent::first(i); 

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

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

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

     }

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

       Parent::firstIn(i, n); 

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

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

     }

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

       Parent::firstOut(i, n); 

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

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

     }

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

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

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

             || !(*node_filter_map)[Parent::target(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(Edge& i) const { 

       Parent::next(i); 

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

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

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

     }

     void next(UEdge& i) const { 

       Parent::next(i); 

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

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

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

     }

     void nextIn(Edge& i) const { 

       Parent::nextIn(i); 

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

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

     }

     void nextOut(Edge& i) const { 

       Parent::nextOut(i); 

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

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

     }

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

       Parent::nextInc(i, d); 

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

             || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d); 

     }

     ///\e

     /// This function hides \c n in the graph, 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 { node_filter_map->set(n, false); }

     ///\e

     /// This function hides \c e in the graph, 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 UEdge& e) const { uedge_filter_map->set(e, false); }

     ///\e

     /// 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 { node_filter_map->set(n, true); }

     ///\e

     /// 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 UEdge& e) const { uedge_filter_map->set(e, true); }

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

     ///\e

     ///

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

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

     ///\e

     ///

     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

   };

   template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>

   class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false> 

     : public UGraphAdaptorBase<_UGraph> {

   public:

     typedef _UGraph Graph;

     typedef UGraphAdaptorBase<_UGraph> Parent;

   protected:

     NodeFilterMap* node_filter_map;

     UEdgeFilterMap* uedge_filter_map;

     SubUGraphAdaptorBase() : Parent(), 

 			    node_filter_map(0), uedge_filter_map(0) { }

     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

       node_filter_map=&_node_filter_map;

     }

     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

       uedge_filter_map=&_uedge_filter_map;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef typename Parent::UEdge UEdge;

     void first(Node& i) const { 

       Parent::first(i); 

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

     }

     void first(Edge& i) const { 

       Parent::first(i); 

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

     }

     void first(UEdge& i) const { 

       Parent::first(i); 

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

     }

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

       Parent::firstIn(i, n); 

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

     }

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

       Parent::firstOut(i, n); 

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

     }

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

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

       while (i!=INVALID && !(*uedge_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(Edge& i) const { 

       Parent::next(i); 

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

     }

     void next(UEdge& i) const { 

       Parent::next(i); 

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

     }

     void nextIn(Edge& i) const { 

       Parent::nextIn(i); 

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

     }

     void nextOut(Edge& i) const { 

       Parent::nextOut(i); 

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

     }

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

       Parent::nextInc(i, d); 

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

     }

     ///\e

     /// This function hides \c n in the graph, 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 { node_filter_map->set(n, false); }

     ///\e

     /// This function hides \c e in the graph, 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 UEdge& e) const { uedge_filter_map->set(e, false); }

     ///\e

     /// 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 { node_filter_map->set(n, true); }

     ///\e

     /// 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 UEdge& e) const { uedge_filter_map->set(e, true); }

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

     ///\e

     ///

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

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

     ///\e

     ///

     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

   };

   /// \ingroup graph_adaptors

   ///

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

   /// graph.

   /// 

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

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

   /// 

   /// SubUGraphAdaptor shows the undirected graph with filtered node-set and 

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

   /// to do not get invalid edges without source or target.

   /// 

   /// 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 edges which's source or target is filtered by the 

   /// node-filter.

   ///

   /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to

   /// \c Graph::Node that is why \c g.id(n) can be applied.

   /// 

   /// For examples see also the documentation of NodeSubUGraphAdaptor and 

   /// EdgeSubUGraphAdaptor.

   /// 

   /// \author Marton Makai

   template<typename _UGraph, typename NodeFilterMap, 

 	   typename UEdgeFilterMap, bool checked = true>

   class SubUGraphAdaptor : 

     public UGraphAdaptorExtender<

     SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {

   public:

     typedef _UGraph Graph;

     typedef UGraphAdaptorExtender<

       SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;

   protected:

     SubUGraphAdaptor() { }

   public:

     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map, 

 		    UEdgeFilterMap& _uedge_filter_map) { 

       setGraph(_graph);

       setNodeFilterMap(_node_filter_map);

       setUEdgeFilterMap(_uedge_filter_map);

     }

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief An adaptor for hiding nodes from an undorected 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 nodes from an undirected graph.

   /// This adaptor specializes SubUGraphAdaptor 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 only

   /// filter only isolated nodes.

   /// \author Marton Makai

   template<typename _UGraph, typename NodeFilterMap, bool checked = true>

   class NodeSubUGraphAdaptor : 

     public SubUGraphAdaptor<_UGraph, NodeFilterMap, 

                             ConstMap<typename _UGraph::UEdge, bool>, checked> {

   public:

     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap, 

                              ConstMap<typename _UGraph::UEdge, bool> > Parent;

     typedef _UGraph Graph;

   protected:

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

   public:

     NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 

       Parent(), const_true_map(true) { 

       Parent::setGraph(_graph);

       Parent::setNodeFilterMap(_node_filter_map);

       Parent::setUEdgeFilterMap(const_true_map);

     }

   };

   template<typename UGraph, typename NodeFilterMap>

   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>

   nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {

     return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);

   }

   template<typename UGraph, typename NodeFilterMap>

   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>

   nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {

     return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);

   }

   /// \brief An adaptor for hiding undirected edges from an undirected 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 undirected edges from an undirected graph.

   /// This adaptor specializes SubUGraphAdaptor in the way that

   /// only the edge-set 

   /// can be filtered.

   ///

   ///\author Marton Makai

   template<typename _UGraph, typename UEdgeFilterMap>

   class EdgeSubUGraphAdaptor : 

     public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 

                             UEdgeFilterMap, false> {

   public:

     typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 

                              UEdgeFilterMap, false> Parent;

     typedef _UGraph Graph;

   protected:

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

   public:

     EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : 

       Parent(), const_true_map(true) { 

       Parent::setGraph(_graph);

       Parent::setNodeFilterMap(const_true_map);

       Parent::setUEdgeFilterMap(_uedge_filter_map);

     }

   };

   template<typename UGraph, typename EdgeFilterMap>

   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>

   edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {

     return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);

   }

   template<typename UGraph, typename EdgeFilterMap>

   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>

   edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {

     return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);

   }

   template <typename _UGraph, typename _DirectionMap>

   class DirectUGraphAdaptorBase {

   public:

     typedef _UGraph Graph;

     typedef _DirectionMap DirectionMap;

     typedef typename _UGraph::Node Node;

     typedef typename _UGraph::UEdge Edge;

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

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

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

       bool d;

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

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

     }

     void firstOut(Edge& 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(Edge& i) const { graph->next(i); }

     void nextIn(Edge& i) const {

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

       graph->nextInc(i, d);

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

     }

     void nextOut(Edge& i) const {

       bool d = (*direction)[i];

       graph->nextInc(i, d);

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

     }

     Node source(const Edge& e) const { 

       return (*direction)[e] ? graph->source(e) : graph->target(e); 

     }

     Node target(const Edge& e) const { 

       return (*direction)[e] ? graph->target(e) : graph->source(e); 

     }

     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

     int edgeNum() const { return graph->uEdgeNum(); }

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& source, const Node& target, 

 		  const Edge& prev = INVALID) {

       Edge edge = prev;

       bool d = edge == INVALID ? true : (*direction)[edge];

       if (d) {

         edge = graph->findUEdge(source, target, edge);

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

           graph->findUEdge(source, target, edge);

         }

         if (edge != INVALID) return edge;

       }

       graph->findUEdge(target, source, edge);

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

         graph->findUEdge(source, target, edge);

       }

       return edge;

     }

     Node addNode() const { 

       return Node(graph->addNode()); 

     }

     Edge addEdge(const Node& source, const Node& target) const {

       Edge edge = graph->addEdge(source, target);

       (*direction)[edge] = graph->source(edge) == source;

       return edge; 

     }

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

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

     void clear() const { graph->clear(); }

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

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

     void reverseEdge(const Edge& edge) {

       direction->set(edge, !(*direction)[edge]);

     }

     template <typename _Value>

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

     public:

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

       explicit NodeMap(const DirectUGraphAdaptorBase& ga) 

 	: Parent(*ga.graph) { }

       NodeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)

 	: Parent(*ga.graph, value) { }

     };

     template <typename _Value>

     class EdgeMap : public _UGraph::template UEdgeMap<_Value> {

     public:

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

       explicit EdgeMap(const DirectUGraphAdaptorBase& ga) 

 	: Parent(*ga.graph) { }

       EdgeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)

 	: Parent(*ga.graph, value) { }

     };

   protected:

     Graph* graph;

     DirectionMap* direction;

     void setDirectionMap(DirectionMap& _direction) {

       direction = &_direction;

     }

     void setGraph(Graph& _graph) {

       graph = &_graph;

     }

   };

   template<typename _Graph, typename DirectionMap> 

   class DirectUGraphAdaptor : 

     public GraphAdaptorExtender<

     DirectUGraphAdaptorBase<_Graph, DirectionMap> > {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorExtender<

       DirectUGraphAdaptorBase<_Graph, DirectionMap> > Parent;

   protected:

     DirectUGraphAdaptor() { }

   public:

     DirectUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 

       setGraph(_graph);

       setDirectionMap(_direction_map);

     }

   };

   template<typename UGraph, typename DirectionMap>

   DirectUGraphAdaptor<const UGraph, DirectionMap>

   directUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {

     return DirectUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);

   }

   template<typename UGraph, typename DirectionMap>

   DirectUGraphAdaptor<const UGraph, const DirectionMap>

   directUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {

     return DirectUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);

   }

 }

 #endif