Changeset 1991:d7442141d9ef in lemon-0.x for lemon/graph_adaptor.h

Timestamp:

03/01/06 11:25:30 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2593

Message:

The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor?, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor? is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor?<UndirGraphAdaptor?<Graph>>.

The ResGraphAdaptor? is based on this composition.

File:

• lemon/graph_adaptor.h (modified) (27 diffs)

lemon/graph_adaptor.h

@@ -114 +114 @@
     int id(const Node& v) const { return graph->id(v); }
     int id(const Edge& e) const { return graph->id(e); }
+
+    int maxNodeId() const {
+      return graph->maxNodeId();
+    }
+
+    int maxEdgeId() const {
+      return graph->maxEdgeId();
+    }
+
+    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+
+    NodeNotifier& getNotifier(Node) const {
+      return graph->getNotifier(Node());
+    } 
+
+    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
+
+    EdgeNotifier& getNotifier(Edge) const {
+      return graph->getNotifier(Edge());
+    } 
     
     template <typename _Value>
@@ -119 +139 @@
     public:
       typedef typename _Graph::template NodeMap<_Value> Parent;
-      explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) 
-        : Parent(*gw.graph) { }
-      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
-        : Parent(*gw.graph, value) { }
+      explicit NodeMap(const GraphAdaptorBase<_Graph>& ga) 
+        : Parent(*ga.graph) { }
+      NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
+        : Parent(*ga.graph, value) { }
     };
 
@@ -129 +149 @@
     public:
       typedef typename _Graph::template EdgeMap<_Value> Parent;
-      explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw) 
-        : Parent(*gw.graph) { }
-      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
-        : Parent(*gw.graph, value) { }
+      explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga) 
+        : Parent(*ga.graph) { }
+      EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
+        : Parent(*ga.graph, value) { }
     };
 
@@ -150 +170 @@
   };
 
+  /// \brief Just gives back a graph adaptor
+  ///
+  /// Just gives back a graph adaptor which 
+  /// should be provide original graph
+  template<typename Graph>
+  GraphAdaptor<const Graph>
+  graphAdaptor(const Graph& graph) {
+    return GraphAdaptor<const Graph>(graph);
+  }
+
+
   template <typename _Graph>
   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
@@ -169 +200 @@
     Node source(const Edge& e) const { return Parent::target(e); }
     Node target(const Edge& e) const { return Parent::source(e); }
+
+    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+    Edge findEdge(const Node& source, const Node& target, 
+                  const Edge& prev = INVALID) {
+      return Parent::findEdge(target, source, prev);
+    }
+
   };
     
@@ -185 +223 @@
   /// then
   ///\code
-  /// RevGraphAdaptor<ListGraph> gw(g);
+  /// RevGraphAdaptor<ListGraph> ga(g);
   ///\endcode
   ///implements the graph obtained from \c g by 
@@ -203 +241 @@
   };
 
-  
+  /// \brief Just gives back a reverse graph adaptor
+  ///
+  /// Just gives back a reverse graph adaptor
+  template<typename Graph>
+  RevGraphAdaptor<const Graph>
+  revGraphAdaptor(const Graph& graph) {
+    return RevGraphAdaptor<const Graph>(graph);
+  }
+
   template <typename _Graph, typename NodeFilterMap, 
             typename EdgeFilterMap, bool checked = true>
@@ -316 +362 @@
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 
-    typedef False FindEdgeTag;
     typedef False NodeNumTag;
     typedef False EdgeNumTag;
+
+    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+    Edge findEdge(const Node& source, const Node& target, 
+                  const Edge& prev = INVALID) {
+      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
+        return INVALID;
+      }
+      Edge edge = Parent::findEdge(source, target, prev);
+      while (edge != INVALID && !(*edge_filter_map)[edge]) {
+        edge = Parent::findEdge(source, target, edge);
+      }
+      return edge;
+    }
   };
 
@@ -423 +481 @@
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 
-    typedef False FindEdgeTag;
     typedef False NodeNumTag;
     typedef False EdgeNumTag;
+
+    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+    Edge findEdge(const Node& source, const Node& target, 
+                  const Edge& prev = INVALID) {
+      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
+        return INVALID;
+      }
+      Edge edge = Parent::findEdge(source, target, prev);
+      while (edge != INVALID && !(*edge_filter_map)[edge]) {
+        edge = Parent::findEdge(source, target, edge);
+      }
+      return edge;
+    }
   };
 
@@ -469 +539 @@
   /// Graph::EdgeMap<bool> em(g, true);
   /// em.set(e, false);
-  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
-  /// SubGW gw(g, nm, em);
-  /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
+  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
+  /// SubGA ga(g, nm, em);
+  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
   /// std::cout << ":-)" << std::endl;
-  /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
+  /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
   ///\endcode
   /// The output of the above code is the following.
@@ -481 +551 @@
   /// 1
   ///\endcode
-  /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
+  /// 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.
   /// 
@@ -508 +578 @@
     }
   };
+
+  /// \brief Just gives back a sub graph adaptor
+  ///
+  /// Just gives back a sub graph adaptor
+  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
+  subGraphAdaptor(const Graph& graph, 
+                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
+    return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
+      (graph, nfm, efm);
+  }
+
+  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
+  subGraphAdaptor(const Graph& graph, 
+                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
+    return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
+      (graph, nfm, efm);
+  }
+
+  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
+  subGraphAdaptor(const Graph& graph, 
+                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
+    return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
+      (graph, nfm, efm);
+  }
+
+  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
+  subGraphAdaptor(const Graph& graph, 
+                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
+    return SubGraphAdaptor<const Graph, const NodeFilterMap, 
+      const EdgeFilterMap>(graph, nfm, efm);
+  }
 
 
@@ -534 +639 @@
   protected:
     ConstMap<typename Graph::Edge, bool> const_true_map;
+
+    NodeSubGraphAdaptor() : const_true_map(true) {
+      Parent::setEdgeFilterMap(const_true_map);
+    }
+
   public:
     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
@@ -543 +653 @@
   };
 
+
+  /// \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);
+  }
 
   ///\brief An adaptor for hiding edges from a graph.
@@ -631 +756 @@
   ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
   ///
-  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
-  ///SubGW gw(g, tight_edge_filter);
+  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
+  ///SubGA ga(g, tight_edge_filter);
   ///\endcode
   ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
@@ -640 +765 @@
   ///Graph::EdgeMap<int> flow(g, 0);
   ///
-  ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
-  ///  preflow(gw, s, t, const_1_map, flow);
+  ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
+  ///  preflow(ga, s, t, const_1_map, flow);
   ///preflow.run();
   ///\endcode
@@ -689 +814 @@
   protected:
     ConstMap<typename Graph::Node, bool> const_true_map;
+
+    EdgeSubGraphAdaptor() : const_true_map(true) {
+      Parent::setNodeFilterMap(const_true_map);
+    }
+
   public:
     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
@@ -698 +828 @@
   };
 
-  template <typename _Graph>
+  /// \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 Enable = void>
   class UndirGraphAdaptorBase : 
     public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
@@ -704 +849 @@
     typedef _Graph Graph;
     typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
+
   protected:
-    UndirGraphAdaptorBase() : Parent() { }
-  public:
+
+    UndirGraphAdaptorBase() : Parent() {}
+
+  public:
+
     typedef typename Parent::UEdge UEdge;
     typedef typename Parent::Edge Edge;
+
     
-    template <typename T>
+    template <typename _Value>
     class EdgeMap {
+    private:
+      
+      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
+      
+    public:
+
+      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
+
+      typedef _Value Value;
+      typedef Edge Key;
+      
+      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
+        forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
+
+      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a) 
+        : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
+      
+      void set(const Edge& e, const Value& a) { 
+        if (Parent::direction(e)) {
+          forward_map.set(e, a); 
+        } else { 
+          backward_map.set(e, a);
+        } 
+      }
+
+      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const { 
+        if (Parent::direction(e)) {
+          return forward_map[e]; 
+        } else { 
+          return backward_map[e]; 
+        }
+      }
+
+      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) { 
+        if (Parent::direction(e)) {
+          return forward_map[e]; 
+        } else { 
+          return backward_map[e]; 
+        }
+      }
+
     protected:
-      const UndirGraphAdaptorBase<_Graph>* g;
-      template <typename TT> friend class EdgeMap;
-      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
-    public:
-      typedef T Value;
-      typedef Edge Key;
-      
-      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g), 
-        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
-
-      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
-        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
-      
-      void set(Edge e, T a) { 
-        if (g->direction(e)) 
-          forward_map.set(e, a); 
-        else 
-          backward_map.set(e, a); 
-      }
-
-      T operator[](Edge e) const { 
-        if (g->direction(e)) 
-          return forward_map[e]; 
-        else 
-          return backward_map[e]; 
-      }
+
+      MapImpl forward_map, backward_map; 
+
     };
         
-    template <typename T>
-    class UEdgeMap {
-      template <typename TT> friend class UEdgeMap;
-      typename _Graph::template EdgeMap<T> map; 
+    template <typename _Value>
+    class UEdgeMap : public _Graph::template EdgeMap<_Value> {
     public:
-      typedef T Value;
-      typedef UEdge Key;
-      
-      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) : 
-        map(*(g.graph)) { }
-
-      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) : 
-        map(*(g.graph), a) { }
-      
-      void set(UEdge e, T a) { 
-        map.set(e, a); 
-      }
-
-      T operator[](UEdge e) const { 
-        return map[e]; 
-      }
+
+      typedef typename _Graph::template EdgeMap<_Value> Parent; 
+
+      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) 
+        : Parent(*(g.graph)) {}
+
+      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a) 
+        : Parent(*(g.graph), a) {}
+      
+    };
+      
+  };
+
+  template <typename _Graph>
+  class UndirGraphAdaptorBase<
+    _Graph, typename enable_if<
+    typename _Graph::EdgeNotifier::Notifier>::type > 
+      : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
+  public:
+
+    typedef _Graph Graph;
+    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
+
+  protected:
+
+    UndirGraphAdaptorBase() 
+      : Parent(), edge_notifier(), edge_notifier_proxy(edge_notifier) {}
+
+    void setGraph(_Graph& graph) {
+      Parent::setGraph(graph);
+      edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
+    }
+
+  public:
+
+    ~UndirGraphAdaptorBase() {
+      getNotifier(Edge()).clear();
+    }
+
+
+    typedef typename Parent::UEdge UEdge;
+    typedef typename Parent::Edge Edge;
+
+    typedef typename Parent::EdgeNotifier UEdgeNotifier;
+
+    using Parent::getNotifier;
+
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
+
+  protected:
+
+    class NotifierProxy : public UEdgeNotifier::ObserverBase {
+    public:
+
+      typedef typename UEdgeNotifier::ObserverBase Parent;
+      typedef UndirGraphAdaptorBase AdaptorBase;
+      
+      NotifierProxy(EdgeNotifier& _edge_notifier)
+        : Parent(), edge_notifier(_edge_notifier) {
+      }
+
+      virtual ~NotifierProxy() {
+        if (Parent::attached()) {
+          Parent::detach();
+        }
+      }
+
+      void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
+        Parent::attach(_uedge_notifier);
+      }
+
+      
+    protected:
+
+      virtual void add(const UEdge& uedge) {
+        std::vector<Edge> edges;
+        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
+        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
+        edge_notifier.add(edges);
+      }
+      virtual void add(const std::vector<UEdge>& uedges) {
+        std::vector<Edge> edges;
+        for (int i = 0; i < (int)uedges.size(); ++i) { 
+          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
+          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
+        }
+        edge_notifier.add(edges);
+      }
+      virtual void erase(const UEdge& uedge) {
+        std::vector<Edge> edges;
+        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
+        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
+        edge_notifier.erase(edges);
+      }
+      virtual void erase(const std::vector<UEdge>& uedges) {
+        std::vector<Edge> edges;
+        for (int i = 0; i < (int)uedges.size(); ++i) { 
+          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
+          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
+        }
+        edge_notifier.erase(edges);
+      }
+      virtual void build() {
+        edge_notifier.build();
+      }
+      virtual void clear() {
+        edge_notifier.clear();
+      }
+
+      EdgeNotifier& edge_notifier;
+    };
+
+
+    mutable EdgeNotifier edge_notifier;
+    NotifierProxy edge_notifier_proxy;
+
+  public:
+    
+    
+    template <typename _Value>
+    class EdgeMap {
+    private:
+      
+      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
+      
+    public:
+
+      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
+
+      typedef _Value Value;
+      typedef Edge Key;
+      
+      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
+        forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
+
+      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a) 
+        : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
+      
+      void set(const Edge& e, const Value& a) { 
+        if (Parent::direction(e)) {
+          forward_map.set(e, a); 
+        } else { 
+          backward_map.set(e, a);
+        } 
+      }
+
+      typename MapTraits<MapImpl>::ConstReturnValue 
+      operator[](const Edge& e) const { 
+        if (Parent::direction(e)) {
+          return forward_map[e]; 
+        } else { 
+          return backward_map[e]; 
+        }
+      }
+
+      typename MapTraits<MapImpl>::ReturnValue 
+      operator[](const Edge& e) { 
+        if (Parent::direction(e)) {
+          return forward_map[e]; 
+        } else { 
+          return backward_map[e]; 
+        }
+      }
+
+    protected:
+
+      MapImpl forward_map, backward_map; 
+
+    };
+        
+    template <typename _Value>
+    class UEdgeMap : public _Graph::template EdgeMap<_Value> {
+    public:
+
+      typedef typename _Graph::template EdgeMap<_Value> Parent; 
+
+      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) 
+        : Parent(*(g.graph)) {}
+
+      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a) 
+        : Parent(*(g.graph), a) {}
+      
     };
       
@@ -787 +1120 @@
       setGraph(_graph);
     }
+
+    template <typename _ForwardMap, typename _BackwardMap>
+    class CombinedEdgeMap {
+    public:
+      
+      typedef _ForwardMap ForwardMap;
+      typedef _BackwardMap BackwardMap;
+
+      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
+
+      typedef typename ForwardMap::Value Value;
+      typedef typename Parent::Edge Key;
+      
+      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
+
+      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map) 
+        : forward_map(&_forward_map), backward_map(&_backward_map) {}
+      
+      void set(const Key& e, const Value& a) { 
+        if (Parent::direction(e)) {
+          forward_map->set(e, a); 
+        } else { 
+          backward_map->set(e, a);
+        } 
+      }
+
+      typename MapTraits<ForwardMap>::ConstReturnValue 
+      operator[](const Key& e) const { 
+        if (Parent::direction(e)) {
+          return (*forward_map)[e]; 
+        } else { 
+          return (*backward_map)[e]; 
+        }
+      }
+
+      typename MapTraits<ForwardMap>::ReturnValue 
+      operator[](const Key& e) { 
+        if (Parent::direction(e)) {
+          return (*forward_map)[e]; 
+        } else { 
+          return (*backward_map)[e]; 
+        }
+      }
+
+      void setForwardMap(ForwardMap& _forward_map) {
+        forward_map = &_forward_map;
+      }
+
+      void setBackwardMap(BackwardMap& _backward_map) {
+        backward_map = &_backward_map;
+      }
+
+    protected:
+
+      ForwardMap* forward_map;
+      BackwardMap* backward_map; 
+
+    };
+
   };
 
-  
-  template <typename _Graph, 
-            typename ForwardFilterMap, typename BackwardFilterMap>
-  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
-  public:
-    typedef _Graph Graph;
-    typedef GraphAdaptorBase<_Graph> Parent;
-  protected:
-    ForwardFilterMap* forward_filter;
-    BackwardFilterMap* backward_filter;
-    SubBidirGraphAdaptorBase() : Parent(), 
-                                 forward_filter(0), backward_filter(0) { }
-
-    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
-      forward_filter=&_forward_filter;
-    }
-    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
-      backward_filter=&_backward_filter;
-    }
-
-  public:
-//     SubGraphAdaptorBase(Graph& _graph, 
-//                      NodeFilterMap& _node_filter_map, 
-//                      EdgeFilterMap& _edge_filter_map) : 
-//       Parent(&_graph), 
-//       node_filter_map(&node_filter_map), 
-//       edge_filter_map(&edge_filter_map) { }
-
-    typedef typename Parent::Node Node;
-    typedef typename _Graph::Edge GraphEdge;
-    template <typename T> class EdgeMap;
-    // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 
-    // _Graph::Edge. It contains an extra bool flag which is true 
-    // if and only if the 
-    // edge is the backward version of the original edge.
-    class Edge : public _Graph::Edge {
-      friend class SubBidirGraphAdaptorBase<
-        Graph, ForwardFilterMap, BackwardFilterMap>;
-      template<typename T> friend class EdgeMap;
-    protected:
-      bool backward; //true, iff backward
-    public:
-      Edge() { }
-      // \todo =false is needed, or causes problems?
-      // If \c _backward is false, then we get an edge corresponding to the 
-      // original one, otherwise its oppositely directed pair is obtained.
-      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
-        _Graph::Edge(e), backward(_backward) { }
-      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
-      bool operator==(const Edge& v) const { 
-        return (this->backward==v.backward && 
-                static_cast<typename _Graph::Edge>(*this)==
-                static_cast<typename _Graph::Edge>(v));
-      } 
-      bool operator!=(const Edge& v) const { 
-        return (this->backward!=v.backward || 
-                static_cast<typename _Graph::Edge>(*this)!=
-                static_cast<typename _Graph::Edge>(v));
-      }
-    };
-
-    void first(Node& i) const { 
-      Parent::first(i); 
-    }
-
-    void first(Edge& i) const { 
-      Parent::first(i); 
-      i.backward=false;
-      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-             !(*forward_filter)[i]) Parent::next(i);
-      if (*static_cast<GraphEdge*>(&i)==INVALID) {
-        Parent::first(i); 
-        i.backward=true;
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*backward_filter)[i]) Parent::next(i);
-      }
-    }
-
-    void firstIn(Edge& i, const Node& n) const { 
-      Parent::firstIn(i, n); 
-      i.backward=false;
-      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-             !(*forward_filter)[i]) Parent::nextIn(i);
-      if (*static_cast<GraphEdge*>(&i)==INVALID) {
-        Parent::firstOut(i, n); 
-        i.backward=true;
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*backward_filter)[i]) Parent::nextOut(i);
-      }
-    }
-
-    void firstOut(Edge& i, const Node& n) const { 
-      Parent::firstOut(i, n); 
-      i.backward=false;
-      while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-             !(*forward_filter)[i]) Parent::nextOut(i);
-      if (*static_cast<GraphEdge*>(&i)==INVALID) {
-        Parent::firstIn(i, n); 
-        i.backward=true;
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*backward_filter)[i]) Parent::nextIn(i);
-      }
-    }
-
-    void next(Node& i) const { 
-      Parent::next(i); 
-    }
-
-    void next(Edge& i) const { 
-      if (!(i.backward)) {
-        Parent::next(i);
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*forward_filter)[i]) Parent::next(i);
-        if (*static_cast<GraphEdge*>(&i)==INVALID) {
-          Parent::first(i); 
-          i.backward=true;
-          while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-                 !(*backward_filter)[i]) Parent::next(i);
-        }
-      } else {
-        Parent::next(i);
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*backward_filter)[i]) Parent::next(i);
-      }
-    }
-
-    void nextIn(Edge& i) const { 
-      if (!(i.backward)) {
-        Node n=Parent::target(i);
-        Parent::nextIn(i);
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*forward_filter)[i]) Parent::nextIn(i);
-        if (*static_cast<GraphEdge*>(&i)==INVALID) {
-          Parent::firstOut(i, n); 
-          i.backward=true;
-          while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-                 !(*backward_filter)[i]) Parent::nextOut(i);
-        }
-      } else {
-        Parent::nextOut(i);
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*backward_filter)[i]) Parent::nextOut(i);
-      }
-    }
-
-    void nextOut(Edge& i) const { 
-      if (!(i.backward)) {
-        Node n=Parent::source(i);
-        Parent::nextOut(i);
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*forward_filter)[i]) Parent::nextOut(i);
-        if (*static_cast<GraphEdge*>(&i)==INVALID) {
-          Parent::firstIn(i, n); 
-          i.backward=true;
-          while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-                 !(*backward_filter)[i]) Parent::nextIn(i);
-        }
-      } else {
-        Parent::nextIn(i);
-        while (*static_cast<GraphEdge*>(&i)!=INVALID && 
-               !(*backward_filter)[i]) Parent::nextIn(i);
-      }
-    }
-
-    Node source(Edge e) const { 
-      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
-    Node target(Edge e) const { 
-      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
-
-    /// Gives back the opposite edge.
-
-    ///\e
-    ///
-    Edge opposite(const Edge& e) const { 
-      Edge f=e;
-      f.backward=!f.backward;
-      return f;
-    }
-
-    ///\e
-
-    /// \warning This is a linear time operation and works only if 
-    /// \c Graph::EdgeIt is defined.
-    /// \todo hmm
-    int edgeNum() const { 
-      int i=0;
-      Edge e;
-      for (first(e); e!=INVALID; next(e)) ++i;
-      return i; 
-    }
-
-    bool forward(const Edge& e) const { return !e.backward; }
-    bool backward(const Edge& e) const { return e.backward; }
-
-    ///\e
-
-    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 
-    /// _Graph::EdgeMap one for the forward edges and 
-    /// one for the backward edges.
-    template <typename T>
-    class EdgeMap {
-      template <typename TT> friend class EdgeMap;
-      typename _Graph::template EdgeMap<T> forward_map, backward_map; 
-    public:
-      typedef T Value;
-      typedef Edge Key;
-
-      EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
-              ForwardFilterMap, BackwardFilterMap>& g) : 
-        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
-
-      EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
-              ForwardFilterMap, BackwardFilterMap>& g, T a) : 
-        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
-      
-      void set(Edge e, T a) { 
-        if (!e.backward) 
-          forward_map.set(e, a); 
-        else 
-          backward_map.set(e, a); 
-      }
-
-//       typename _Graph::template EdgeMap<T>::ConstReference 
-//       operator[](Edge e) const { 
-//      if (!e.backward) 
-//        return forward_map[e]; 
-//      else 
-//        return backward_map[e]; 
-//       }
-
-//      typename _Graph::template EdgeMap<T>::Reference 
-      T operator[](Edge e) const { 
-        if (!e.backward) 
-          return forward_map[e]; 
-        else 
-          return backward_map[e]; 
-      }
-
-      void update() { 
-        forward_map.update(); 
-        backward_map.update();
-      }
-    };
-
-  };
-
-
-  ///\brief An adaptor for composing a subgraph of a 
-  /// bidirected graph made from a directed one. 
-  ///\ingroup graph_adaptors
-  ///
-  /// An adaptor for composing a subgraph of a 
-  /// bidirected graph made from a directed one. 
-  ///
-  ///\warning Graph adaptors are in even more experimental state
-  ///than the other
-  ///parts of the lib. Use them at you own risk.
-  ///
-  /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge 
-  ///\f$ e\in A \f$, let \f$ \bar e \f$ denote the edge obtained by
-  /// reversing its orientation. We are given moreover two bool valued 
-  /// maps on the edge-set, 
-  ///\f$ forward\_filter \f$, and \f$ backward\_filter \f$. 
-  /// SubBidirGraphAdaptor implements the graph structure with node-set 
-  ///\f$ V \f$ and edge-set 
-  ///\f$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} \f$. 
-  /// The purpose of writing + instead of union is because parallel 
-  /// edges can arise. (Similarly, antiparallel edges also can arise).
-  /// In other words, a subgraph of the bidirected graph obtained, which 
-  /// is given by orienting the edges of the original graph in both directions.
-  /// As the oppositely directed edges are logically different, 
-  /// the maps are able to attach different values for them. 
-  ///
-  /// An example for such a construction is \c RevGraphAdaptor where the 
-  /// forward_filter is everywhere false and the backward_filter is 
-  /// everywhere true. We note that for sake of efficiency, 
-  /// \c RevGraphAdaptor is implemented in a different way. 
-  /// But BidirGraphAdaptor is obtained from 
-  /// SubBidirGraphAdaptor by considering everywhere true 
-  /// valued maps both for forward_filter and backward_filter. 
-  ///
-  /// The most important application of SubBidirGraphAdaptor 
-  /// is ResGraphAdaptor, which stands for the residual graph in directed 
-  /// flow and circulation problems. 
-  /// As adaptors usually, the SubBidirGraphAdaptor implements the 
-  /// above mentioned graph structure without its physical storage, 
-  /// that is the whole stuff is stored in constant memory. 
-  template<typename _Graph, 
-           typename ForwardFilterMap, typename BackwardFilterMap>
-  class SubBidirGraphAdaptor : 
-    public GraphAdaptorExtender<
-    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
-  public:
-    typedef _Graph Graph;
-    typedef GraphAdaptorExtender<
-      SubBidirGraphAdaptorBase<
-      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
-  protected:
-    SubBidirGraphAdaptor() { }
-  public:
-    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, 
-                         BackwardFilterMap& _backward_filter) { 
-      setGraph(_graph);
-      setForwardFilterMap(_forward_filter);
-      setBackwardFilterMap(_backward_filter);
-    }
-  };
-
-
-
-  ///\brief An adaptor for composing bidirected graph from a directed one. 
-  ///\ingroup graph_adaptors
-  ///
-  ///\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 composing bidirected graph from a directed one. 
-  /// A bidirected graph is composed over the directed one without physical 
-  /// storage. As the oppositely directed edges are logically different ones 
-  /// the maps are able to attach different values for them.
+  /// \brief Just gives back an undir graph adaptor
+  ///
+  /// Just gives back an undir graph adaptor
   template<typename Graph>
-  class BidirGraphAdaptor : 
-    public SubBidirGraphAdaptor<
-    Graph, 
-    ConstMap<typename Graph::Edge, bool>, 
-    ConstMap<typename Graph::Edge, bool> > {
-  public:
-    typedef  SubBidirGraphAdaptor<
-      Graph, 
-      ConstMap<typename Graph::Edge, bool>, 
-      ConstMap<typename Graph::Edge, bool> > Parent; 
-  protected:
-    ConstMap<typename Graph::Edge, bool> cm;
-
-    BidirGraphAdaptor() : Parent(), cm(true) { 
-      Parent::setForwardFilterMap(cm);
-      Parent::setBackwardFilterMap(cm);
-    }
-  public:
-    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 
-      Parent::setGraph(_graph);
-      Parent::setForwardFilterMap(cm);
-      Parent::setBackwardFilterMap(cm);
-    }
-
-    int edgeNum() const { 
-      return 2*this->graph->edgeNum();
-    }
-  };
-
+  UndirGraphAdaptor<const Graph>
+  undirGraphAdaptor(const Graph& graph) {
+    return UndirGraphAdaptor<const Graph>(graph);
+  }
 
   template<typename Graph, typename Number,
            typename CapacityMap, typename FlowMap>
   class ResForwardFilter {
-    //    const Graph* graph;
     const CapacityMap* capacity;
     const FlowMap* flow;
   public:
-    ResForwardFilter(/*const Graph& _graph, */
-                     const CapacityMap& _capacity, const FlowMap& _flow) :
-      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
-    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
-    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
-    void setFlow(const FlowMap& _flow) { flow=&_flow; }
+    typedef typename Graph::Edge Key;
+    typedef bool Value;
+
+    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 
+      : capacity(&_capacity), flow(&_flow) { }
+    ResForwardFilter() : capacity(0), flow(0) { }
+    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
+    void setFlow(const FlowMap& _flow) { flow = &_flow; }
     bool operator[](const typename Graph::Edge& e) const {
       return (Number((*flow)[e]) < Number((*capacity)[e]));
@@ -1165 +1215 @@
     const FlowMap* flow;
   public:
-    ResBackwardFilter(/*const Graph& _graph,*/ 
-                      const CapacityMap& _capacity, const FlowMap& _flow) :
-      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
-    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
-    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
-    void setFlow(const FlowMap& _flow) { flow=&_flow; }
+    typedef typename Graph::Edge Key;
+    typedef bool Value;
+
+    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 
+      : capacity(&_capacity), flow(&_flow) { }
+    ResBackwardFilter() : capacity(0), flow(0) { }
+    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
+    void setFlow(const FlowMap& _flow) { flow = &_flow; }
     bool operator[](const typename Graph::Edge& e) const {
       return (Number(0) < Number((*flow)[e]));
@@ -1208 +1260 @@
   ///Graph::EdgeMap<int> f(g);
   ///Graph::EdgeMap<int> c(g);
-  ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
+  ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
   ///\endcode
   ///\author Marton Makai
@@ -1215 +1267 @@
            typename CapacityMap, typename FlowMap>
   class ResGraphAdaptor : 
-    public SubBidirGraphAdaptor< 
-    Graph, 
+    public EdgeSubGraphAdaptor< 
+    UndirGraphAdaptor<Graph>, 
+    typename UndirGraphAdaptor<Graph>::template CombinedEdgeMap<
     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
-    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
-  public:
-    typedef SubBidirGraphAdaptor< 
-      Graph, 
-      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
-      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
+    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > > {
+  public:
+
+    typedef UndirGraphAdaptor<Graph> UGraph;
+
+    typedef ResForwardFilter<Graph, Number, CapacityMap, FlowMap> 
+    ForwardFilter;
+
+    typedef ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> 
+    BackwardFilter;
+
+    typedef typename UGraph::
+    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
+    EdgeFilter;
+
+    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
+
   protected:
+
     const CapacityMap* capacity;
     FlowMap* flow;
-    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
-    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
-    ResGraphAdaptor() : Parent(), 
-                        capacity(0), flow(0) { }
+
+    UGraph ugraph;
+    ForwardFilter forward_filter;
+    BackwardFilter backward_filter;
+    EdgeFilter edge_filter;
+
     void setCapacityMap(const CapacityMap& _capacity) {
       capacity=&_capacity;
@@ -1236 +1303 @@
       backward_filter.setCapacity(_capacity);
     }
+
     void setFlowMap(FlowMap& _flow) {
       flow=&_flow;
@@ -1241 +1309 @@
       backward_filter.setFlow(_flow);
     }
-  public:
+
+  public:
+
     ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity, 
-                       FlowMap& _flow) : 
-      Parent(), capacity(&_capacity), flow(&_flow), 
-      forward_filter(/*_graph,*/ _capacity, _flow), 
-      backward_filter(/*_graph,*/ _capacity, _flow) {
-      Parent::setGraph(_graph);
-      Parent::setForwardFilterMap(forward_filter);
-      Parent::setBackwardFilterMap(backward_filter);
+                    FlowMap& _flow) 
+      : Parent(), capacity(&_capacity), flow(&_flow),
+        ugraph(_graph),
+        forward_filter(_capacity, _flow), 
+        backward_filter(_capacity, _flow),
+        edge_filter(forward_filter, backward_filter) {
+      Parent::setGraph(ugraph);
+      Parent::setEdgeFilterMap(edge_filter);
     }
 
@@ -1255 +1326 @@
 
     void augment(const Edge& e, Number a) const {
-      if (Parent::forward(e))  
+      if (UGraph::direction(e)) {
         flow->set(e, (*flow)[e]+a);
-      else  
+      } else {  
         flow->set(e, (*flow)[e]-a);
-    }
+      }
+    }
+
+    static bool forward(const Edge& e) {
+      return UGraph::direction(e);
+    }
+
+    static bool backward(const Edge& e) {
+      return !UGraph::direction(e);
+    }
+
+    static Edge forward(const typename Graph::Edge& e) {
+      return UGraph::direct(e, true);
+    }
+
+    static Edge backward(const typename Graph::Edge& e) {
+      return UGraph::direct(e, false);
+    }
+
 
     /// \brief Residual capacity map.
@@ -1267 +1356 @@
     class ResCap {
     protected:
-      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
+      const ResGraphAdaptor* res_graph;
     public:
       typedef Number Value;
       typedef Edge Key;
-      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>& 
-             _res_graph) : res_graph(&_res_graph) { }
+      ResCap(const ResGraphAdaptor& _res_graph) 
+        : res_graph(&_res_graph) {}
+      
       Number operator[](const Edge& e) const { 
-        if (res_graph->forward(e)) 
+        if (ResGraphAdaptor::direction(e)) 
           return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
         else 
           return (*(res_graph->flow))[e]; 
       }
+      
     };
 
-    //    KEEP_MAPS(Parent, ResGraphAdaptor);
   };