diff -r ef2d00e46897 -r c2992fd74dad lemon/ugraph_adaptor.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/ugraph_adaptor.h	Wed Feb 22 18:26:56 2006 +0000
@@ -0,0 +1,803 @@
+/* -*- 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