# HG changeset patch
# User deba
# Date 1135004289 0
# Node ID c2de2ed28e599caa27c092563db488adab293857
# Parent  dcefd1d1377f862c8169fd01f28ed83a4d0ebd98
New file and data structures: sub_graph
Moved to new group with the edge_sets

diff -r dcefd1d1377f -r c2de2ed28e59 doc/groups.dox
--- a/doc/groups.dox	Mon Dec 19 09:47:10 2005 +0000
+++ b/doc/groups.dox	Mon Dec 19 14:58:09 2005 +0000
@@ -40,6 +40,16 @@
 */
 
 /**
+@defgroup semi_adaptors Semi-Adaptors Classes for Graphs
+@ingroup graphs
+\brief Graph types between real graphs and graph adaptors.
+
+Graph types between real graphs and graph adaptors. These classes
+wrap graphs to give new functionality as the adaptors do it. But the
+other way they are not light-weigth structures as the adaptors.
+*/
+
+/**
 @defgroup maps Maps 
 @ingroup datas
 \brief Some special purpose map to make life easier.
@@ -48,7 +58,6 @@
 new maps from existing ones.
 */
 
-
 /**
 @defgroup graph_maps Graph Maps 
 @ingroup maps
diff -r dcefd1d1377f -r c2de2ed28e59 lemon/Makefile.am
--- a/lemon/Makefile.am	Mon Dec 19 09:47:10 2005 +0000
+++ b/lemon/Makefile.am	Mon Dec 19 14:58:09 2005 +0000
@@ -62,6 +62,7 @@
 	radix_heap.h \
 	radix_sort.h \
 	smart_graph.h \
+	sub_graph.h \
 	time_measure.h \
 	topology.h \
 	traits.h \
diff -r dcefd1d1377f -r c2de2ed28e59 lemon/edge_set.h
--- a/lemon/edge_set.h	Mon Dec 19 09:47:10 2005 +0000
+++ b/lemon/edge_set.h	Mon Dec 19 14:58:09 2005 +0000
@@ -192,7 +192,7 @@
 
   };
 
-  /// \ingroup graphs
+  /// \ingroup semi_adaptors
   ///
   /// \brief Graph using a node set of another graph and an
   /// own edge set.
@@ -291,7 +291,7 @@
     
   };
 
-  /// \ingroup graphs
+  /// \ingroup semi_adaptors
   ///
   /// \brief Graph using a node set of another graph and an
   /// own undir edge set.
@@ -363,6 +363,12 @@
 	_edgeset.eraseNode(node);
 	Parent::erase(node);
       }
+      virtual void erase(const std::vector<Node>& nodes) {
+	for (int i = 0; i < nodes.size(); ++i) {
+	  _edgeset.eraseNode(nodes[i]);
+	}
+	Parent::erase(nodes);
+      }
       virtual void clear() {
 	_edgeset.clearNodes();
 	Parent::clear();
diff -r dcefd1d1377f -r c2de2ed28e59 lemon/sub_graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/sub_graph.h	Mon Dec 19 14:58:09 2005 +0000
@@ -0,0 +1,805 @@
+/* -*- C++ -*-
+ * lemon/sub_graph.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_SUB_GRAPH_H
+#define LEMON_SUB_GRAPH_H
+
+#include <lemon/graph_adaptor.h>
+
+namespace lemon {
+
+  /// \brief Base for the SubGraph.
+  ///
+  /// Base for the SubGraph.
+  template <typename _Graph>
+  class SubGraphBase : public GraphAdaptorBase<const _Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef SubGraphBase<_Graph> SubGraph;
+    typedef GraphAdaptorBase<const _Graph> Parent;
+    typedef Parent Base;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+
+  protected:
+
+    class NodesImpl;
+    class EdgesImpl;
+
+    SubGraphBase() {}
+
+    void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
+      Parent::setGraph(_graph);
+      nodes = &_nodes;
+      edges = &_edges;
+      firstNode = INVALID;
+
+      Node node;
+      Parent::first(node);
+      while (node != INVALID) {
+	(*nodes)[node].prev = node;
+	(*nodes)[node].firstIn = INVALID;
+	(*nodes)[node].firstOut = INVALID;
+	Parent::next(node);
+      }
+
+      Edge edge;
+      Parent::first(edge);
+      while (edge != INVALID) {
+	(*edges)[edge].prevOut = edge;
+	Parent::next(edge);
+      }
+    }
+
+  public:
+
+    void first(Node& node) const {
+      node = firstNode;
+    }
+    void next(Node& node) const {
+      node = (*nodes)[node].next;
+    }
+
+    void first(Edge& edge) const {
+      Node node = firstNode;
+      while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
+	node = (*nodes)[node].next;
+      }
+      if (node == INVALID) {
+	edge = INVALID;
+      } else {
+	edge = (*nodes)[node].firstOut;
+      }
+    }
+    void next(Edge& edge) const {
+      if ((*edges)[edge].nextOut != INVALID) {
+	edge = (*edges)[edge].nextOut;
+      } else {
+	Node node = (*nodes)[source(edge)].next;
+	while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
+	  node = (*nodes)[node].next;
+	}
+	if (node == INVALID) {
+	  edge = INVALID;
+	} else {
+	  edge = (*nodes)[node].firstOut;
+	}
+      }
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge = (*nodes)[node].firstOut;
+    }
+    void nextOut(Edge& edge) const {
+      edge = (*edges)[edge].nextOut;
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge = (*nodes)[node].firstIn;
+    }
+    void nextIn(Edge& edge) const {
+      edge = (*edges)[edge].nextIn;
+    }
+
+    /// \brief Returns true when the given node is hidden.
+    ///
+    /// Returns true when the given node is hidden.
+    bool hidden(const Node& node) const {
+      return (*nodes)[node].prev == node;
+    }
+
+    /// \brief Hide the given node in the sub-graph.
+    ///
+    /// Hide the given node in the sub graph. It just lace out from
+    /// the linked lists the given node. If there are incoming or outgoing
+    /// edges into or from this node then all of these will be hidden.
+    void hide(const Node& node) {
+      if (hidden(node)) return;
+      Edge edge;
+      firstOut(edge, node);
+      while (edge != INVALID) {
+	hide(edge);
+	firstOut(edge, node);
+      }
+
+      firstOut(edge, node);
+      while (edge != INVALID) {
+	hide(edge);
+	firstOut(edge, node);
+      }
+      if ((*nodes)[node].prev != INVALID) {
+	(*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
+      } else {
+	firstNode = (*nodes)[node].next;
+      }
+      if ((*nodes)[node].next != INVALID) {
+	(*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
+      }
+      (*nodes)[node].prev = node;
+      (*nodes)[node].firstIn = INVALID;
+      (*nodes)[node].firstOut = INVALID;
+    }
+
+    /// \brief Unhide the given node in the sub-graph.
+    ///
+    /// Unhide the given node in the sub graph. It just lace in the given
+    /// node into the linked lists.
+    void unHide(const Node& node) {
+      if (!hidden(node)) return;
+      (*nodes)[node].next = firstNode;
+      (*nodes)[node].prev = INVALID;
+      if ((*nodes)[node].next != INVALID) {
+	(*nodes)[(*nodes)[node].next].prev = node;
+      }
+      firstNode = node;
+    }
+
+    /// \brief Returns true when the given edge is hidden.
+    ///
+    /// Returns true when the given edge is hidden.
+    bool hidden(const Edge& edge) const {
+      return (*edges)[edge].prevOut == edge;
+    }
+
+    /// \brief Hide the given edge in the sub-graph.
+    ///
+    /// Hide the given edge in the sub graph. It just lace out from
+    /// the linked lists the given edge.
+    void hide(const Edge& edge) {
+      if (hidden(edge)) return;
+      if ((*edges)[edge].prevOut == edge) return;
+      if ((*edges)[edge].prevOut != INVALID) {
+	(*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
+      } else {
+	(*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
+      }
+      if ((*edges)[edge].nextOut != INVALID) {
+	(*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
+      }
+
+      if ((*edges)[edge].prevIn != INVALID) {
+	(*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
+      } else {
+	(*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
+      }
+      if ((*edges)[edge].nextIn != INVALID) {
+	(*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
+      }
+      (*edges)[edge].next = edge;
+    }
+
+    /// \brief Unhide the given edge in the sub-graph.
+    ///
+    /// Unhide the given edge in the sub graph. It just lace in the given
+    /// edge into the linked lists. If the source or the target of the
+    /// node is hidden then it will unhide it.
+    void unHide(const Edge& edge) {
+      if (!hidden(edge)) return;
+
+      Node node;
+
+      node = Parent::source(edge);
+      unHide(node);
+      (*edges)[edge].nextOut = (*nodes)[node].firstOut;
+      (*edges)[edge].prevOut = INVALID;
+      if ((*edges)[edge].nextOut != INVALID) {
+	(*edges)[(*edges)[edge].nextOut].prevOut = edge;
+      }
+      (*nodes)[node].firstOut = edge;
+
+      node = Parent::target(edge);
+      unHide(node);
+      (*edges)[edge].nextIn = (*nodes)[node].firstIn;
+      (*edges)[edge].prevIn = INVALID;
+      if ((*edges)[edge].nextIn != INVALID) {
+	(*edges)[(*edges)[edge].nextIn].prevIn = edge;
+      }
+      (*nodes)[node].firstIn = edge;      
+    }
+    
+    typedef False NodeNumTag;
+    typedef False EdgeNumTag;
+
+  protected:
+    struct NodeT {
+      Node prev, next;
+      Edge firstIn, firstOut;
+    };
+    class NodesImpl : public Graph::template NodeMap<NodeT> {
+      friend class SubGraphBase;
+    public:
+      typedef typename Graph::template NodeMap<NodeT> Parent;
+
+      NodesImpl(SubGraph& _adaptor, const Graph& _graph) 
+	: Parent(_graph), adaptor(_adaptor) {}
+
+      virtual ~NodesImpl() {}
+
+      virtual void build() {
+	Parent::build();
+	Node node;
+	adaptor.Base::first(node);
+	while (node != INVALID) {
+	  Parent::operator[](node).prev = node;
+	  Parent::operator[](node).firstIn = INVALID;
+	  Parent::operator[](node).firstOut = INVALID;
+	  adaptor.Base::next(node);
+	}
+      }
+
+      virtual void clear() {
+	adaptor.firstNode = INVALID;
+	Parent::clear();
+      }
+
+      virtual void add(const Node& node) {
+	Parent::add(node);
+	Parent::operator[](node).prev = node;
+	Parent::operator[](node).firstIn = INVALID;
+	Parent::operator[](node).firstOut = INVALID;
+      }
+      virtual void add(const std::vector<Node>& nodes) {
+	Parent::add(nodes);
+	for (int i = 0; i < (int)nodes.size(); ++i) {
+	  Parent::operator[](nodes[i]).prev = nodes[i];
+	  Parent::operator[](nodes[i]).firstIn = INVALID;
+	  Parent::operator[](nodes[i]).firstOut = INVALID;
+	}
+      } 
+
+      virtual void erase(const Node& node) {
+	adaptor.hide(node);
+	Parent::erase(node);
+      }
+
+      virtual void erase(const std::vector<Node>& nodes) {
+	for (int i = 0; i < (int)nodes.size(); ++i) {
+	  adaptor.hide(nodes[i]);
+	}
+	Parent::erase(nodes);
+      }
+
+    private:
+      SubGraph& adaptor;
+    };
+
+    struct EdgeT {
+      Edge prevOut, nextOut;
+      Edge prevIn, nextIn;
+    };
+    class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
+      friend class SubGraphBase;
+    public:
+      typedef typename Graph::template EdgeMap<EdgeT> Parent;
+
+      EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 
+	: Parent(_graph), adaptor(_adaptor) {}
+
+      virtual ~EdgesImpl() {}
+
+      virtual void build() {
+	Parent::build();
+	Edge edge;
+	adaptor.Base::first(edge);
+	while (edge != INVALID) {
+	  Parent::operator[](edge).prevOut = edge;
+	  adaptor.Base::next(edge);
+	}
+      }
+
+      virtual void clear() {
+	Node node;
+	adaptor.first(node);
+	while (node != INVALID) {
+	  (*adaptor.nodes).firstIn = INVALID;
+	  (*adaptor.nodes).firstOut = INVALID;
+	  adaptor.next(node);
+	}
+	Parent::clear();
+      }
+
+      virtual void add(const Edge& edge) {
+	Parent::add(edge);
+	Parent::operator[](edge).prevOut = edge;
+      }
+
+      virtual void add(const std::vector<Edge>& edges) {
+	Parent::add(edges);
+	for (int i = 0; i < (int)edges.size(); ++i) {
+	  Parent::operator[](edges[i]).prevOut = edges[i];
+	}
+      }
+
+      virtual void erase(const Edge& edge) {
+	adaptor.hide(edge);
+	Parent::erase(edge);
+      }
+
+      virtual void erase(const std::vector<Edge>& edges) {
+	for (int i = 0; i < (int)edges.size(); ++i) {
+	  adaptor.hide(edges[i]);
+	}
+	Parent::erase(edge);
+      }
+
+    private:
+      SubGraph& adaptor;
+    };
+
+    NodesImpl* nodes;
+    EdgesImpl* edges;
+    Node firstNode;
+  };
+
+  /// \ingroup semi_adaptors
+  ///
+  /// \brief Graph which uses a subset of an other graph's nodes and edges.
+  ///
+  /// Graph which uses a subset of an other graph's nodes and edges. This class
+  /// is an alternative to the SubGraphAdaptor which is created for the
+  /// same reason. The main difference between the two class that it
+  /// makes linked lists on the unhidden nodes and edges what cause that
+  /// on sparse subgraphs the algorithms can be more efficient and some times
+  /// provide better time complexity. On other way this implemetation is
+  /// less efficient in most case when the subgraph filters out only
+  /// a few nodes or edges.
+  /// 
+  /// \see SubGraphAdaptor
+  /// \see EdgeSubGraphBase
+  template <typename Graph>
+  class SubGraph 
+    : public IterableGraphExtender< SubGraphBase<Graph> > {
+  public:
+    typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
+  public:
+    /// \brief Constructor for sub-graph.
+    ///
+    /// Constructor for sub-graph. Initially all the edges and nodes
+    /// are hidden in the graph.
+    SubGraph(const Graph& _graph) 
+      : Parent(), nodes(*this, _graph), edges(*this, _graph) { 
+      Parent::construct(_graph, nodes, edges);
+    }
+  private:
+    typename Parent::NodesImpl nodes;
+    typename Parent::EdgesImpl edges;
+  };
+
+  /// \brief Base for the EdgeSubGraph.
+  ///
+  /// Base for the EdgeSubGraph.
+  template <typename _Graph>
+  class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef EdgeSubGraphBase<_Graph> SubGraph;
+    typedef GraphAdaptorBase<const _Graph> Parent;
+    typedef Parent Base;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+
+  protected:
+
+    class NodesImpl;
+    class EdgesImpl;
+
+    EdgeSubGraphBase() {}
+
+    void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
+      Parent::setGraph(_graph);
+      nodes = &_nodes;
+      edges = &_edges;
+
+      Node node;
+      Parent::first(node);
+      while (node != INVALID) {
+	(*nodes)[node].firstIn = INVALID;
+	(*nodes)[node].firstOut = INVALID;
+	Parent::next(node);
+      }
+
+      Edge edge;
+      Parent::first(edge);
+      while (edge != INVALID) {
+	(*edges)[edge].prevOut = edge;
+	Parent::next(edge);
+      }
+    }
+
+  public:
+
+    void first(Node& node) const {
+      Parent::first(node);
+    }
+    void next(Node& node) const {
+      Parent::next(node);
+    }
+
+    void first(Edge& edge) const {
+      Node node;
+      Parent::first(node);
+      while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
+	Parent::next(node);
+      }
+      if (node == INVALID) {
+	edge = INVALID;
+      } else {
+	edge = (*nodes)[node].firstOut;
+      }
+    }
+    void next(Edge& edge) const {
+      if ((*edges)[edge].nextOut != INVALID) {
+	edge = (*edges)[edge].nextOut;
+      } else {
+	Node node = source(edge);
+	Parent::next(node);
+	while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
+	  Parent::next(node);
+	}
+	if (node == INVALID) {
+	  edge = INVALID;
+	} else {
+	  edge = (*nodes)[node].firstOut;
+	}
+      }
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge = (*nodes)[node].firstOut;
+    }
+    void nextOut(Edge& edge) const {
+      edge = (*edges)[edge].nextOut;
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge = (*nodes)[node].firstIn;
+    }
+    void nextIn(Edge& edge) const {
+      edge = (*edges)[edge].nextIn;
+    }
+
+    /// \brief Returns true when the given edge is hidden.
+    ///
+    /// Returns true when the given edge is hidden.
+    bool hidden(const Edge& edge) const {
+      return (*edges)[edge].prevOut == edge;
+    }
+
+    /// \brief Hide the given edge in the sub-graph.
+    ///
+    /// Hide the given edge in the sub graph. It just lace out from
+    /// the linked lists the given edge.
+    void hide(const Edge& edge) {
+      if (hidden(edge)) return;
+      if ((*edges)[edge].prevOut != INVALID) {
+	(*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
+      } else {
+	(*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
+      }
+      if ((*edges)[edge].nextOut != INVALID) {
+	(*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
+      }
+
+      if ((*edges)[edge].prevIn != INVALID) {
+	(*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
+      } else {
+	(*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
+      }
+      if ((*edges)[edge].nextIn != INVALID) {
+	(*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
+      }
+      (*edges)[edge].prevOut = edge;
+    }
+
+    /// \brief Unhide the given edge in the sub-graph.
+    ///
+    /// Unhide the given edge in the sub graph. It just lace in the given
+    /// edge into the linked lists.
+    void unHide(const Edge& edge) {
+      if (!hidden(edge)) return;
+      Node node;
+
+      node = Parent::source(edge);
+      (*edges)[edge].nextOut = (*nodes)[node].firstOut;
+      (*edges)[edge].prevOut = INVALID;
+      if ((*edges)[edge].nextOut != INVALID) {
+	(*edges)[(*edges)[edge].nextOut].prevOut = edge;
+      }
+      (*nodes)[node].firstOut = edge;
+
+      node = Parent::target(edge);
+      (*edges)[edge].nextIn = (*nodes)[node].firstIn;
+      (*edges)[edge].prevIn = INVALID;
+      if ((*edges)[edge].nextIn != INVALID) {
+	(*edges)[(*edges)[edge].nextIn].prevIn = edge;
+      }
+      (*nodes)[node].firstIn = edge;      
+    }
+    
+  protected:
+    struct NodeT {
+      Edge firstIn, firstOut;
+    };
+    class NodesImpl : public Graph::template NodeMap<NodeT> {
+      friend class EdgeSubGraphBase;
+    public:
+      typedef typename Graph::template NodeMap<NodeT> Parent;
+
+      NodesImpl(SubGraph& _adaptor, const Graph& _graph) 
+	: Parent(_graph), adaptor(_adaptor) {}
+
+      virtual ~NodesImpl() {}
+
+      virtual void build() {
+	Parent::build();
+	Node node;
+	adaptor.Base::first(node);
+	while (node != INVALID) {
+	  Parent::operator[](node).firstIn = INVALID;
+	  Parent::operator[](node).firstOut = INVALID;
+	  adaptor.Base::next(node);
+	}
+      }
+
+      virtual void add(const Node& node) {
+	Parent::add(node);
+	Parent::operator[](node).firstIn = INVALID;
+	Parent::operator[](node).firstOut = INVALID;
+      }
+
+    private:
+      SubGraph& adaptor;
+    };
+
+    struct EdgeT {
+      Edge prevOut, nextOut;
+      Edge prevIn, nextIn;
+    };
+    class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
+      friend class EdgeSubGraphBase;
+    public:
+      typedef typename Graph::template EdgeMap<EdgeT> Parent;
+
+      EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 
+	: Parent(_graph), adaptor(_adaptor) {}
+
+      virtual ~EdgesImpl() {}
+
+      virtual void build() {
+	Parent::build();
+	Edge edge;
+	adaptor.Base::first(edge);
+	while (edge != INVALID) {
+	  Parent::operator[](edge).prevOut = edge;
+	  adaptor.Base::next(edge);
+	}
+      }
+
+      virtual void clear() {
+	Node node;
+	adaptor.Base::first(node);
+	while (node != INVALID) {
+	  (*adaptor.nodes)[node].firstIn = INVALID;
+	  (*adaptor.nodes)[node].firstOut = INVALID;
+	  adaptor.Base::next(node);
+	}
+	Parent::clear();
+      }
+
+      virtual void add(const Edge& edge) {
+	Parent::add(edge);
+	Parent::operator[](edge).prevOut = edge;
+      }
+
+      virtual void add(const std::vector<Edge>& edges) {
+	Parent::add(edges);
+	for (int i = 0; i < (int)edges.size(); ++i) {
+	  Parent::operator[](edges[i]).prevOut = edges[i];
+	}
+      }
+
+      virtual void erase(const Edge& edge) {
+	adaptor.hide(edge);
+	Parent::erase(edge);
+      }
+
+      virtual void erase(const std::vector<Edge>& edges) {
+	for (int i = 0; i < (int)edges.size(); ++i) {
+	  adaptor.hide(edges[i]);
+	}
+	Parent::erase(edge);
+      }
+
+    private:
+      SubGraph& adaptor;
+    };
+
+    NodesImpl* nodes;
+    EdgesImpl* edges;
+  };
+
+  /// \ingroup semi_adaptors
+  ///
+  /// \brief Graph which uses a subset of an other graph's edges.
+  ///
+  /// Graph which uses a subset of an other graph's edges. This class
+  /// is an alternative to the EdgeSubGraphAdaptor which is created for the
+  /// same reason. The main difference between the two class that it
+  /// makes linked lists on the unhidden edges what cause that
+  /// on sparse subgraphs the algorithms can be more efficient and some times
+  /// provide better time complexity. On other way this implemetation is
+  /// less efficient in most case when the subgraph filters out only
+  /// a few edges.
+  /// 
+  /// \see EdgeSubGraphAdaptor
+  /// \see EdgeSubGraphBase
+  template <typename Graph>
+  class EdgeSubGraph 
+    : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
+  public:
+    typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
+  public:
+    /// \brief Constructor for sub-graph.
+    ///
+    /// Constructor for sub-graph. Initially all the edges are hidden in the 
+    /// graph.
+    EdgeSubGraph(const Graph& _graph) 
+      : Parent(), nodes(*this, _graph), edges(*this, _graph) { 
+      Parent::construct(_graph, nodes, edges);
+    }
+  private:
+    typename Parent::NodesImpl nodes;
+    typename Parent::EdgesImpl edges;
+  };
+
+
+//   template<typename Graph, typename Number, 
+// 	   typename CapacityMap, typename FlowMap>
+//   class ResGraph
+//     : public IterableGraphExtender<EdgeSubGraphBase<
+//     UndirGraphAdaptor<Graph> > > {
+//   public:
+//     typedef IterableGraphExtender<EdgeSubGraphBase<
+//       UndirGraphAdaptor<Graph> > > Parent;
+
+//   protected:
+//     UndirGraphAdaptor<Graph> undir;
+
+//     const CapacityMap* capacity;
+//     FlowMap* flow;
+
+//     typename Parent::NodesImpl nodes;
+//     typename Parent::EdgesImpl edges;
+
+//     void setCapacityMap(const CapacityMap& _capacity) {
+//       capacity=&_capacity;
+//     }
+
+//     void setFlowMap(FlowMap& _flow) {
+//       flow=&_flow;
+//     }
+
+//   public:
+
+//     typedef typename UndirGraphAdaptor<Graph>::Node Node;
+//     typedef typename UndirGraphAdaptor<Graph>::Edge Edge;
+//     typedef typename UndirGraphAdaptor<Graph>::UndirEdge UndirEdge;
+
+//     ResGraphAdaptor(Graph& _graph, 
+// 		    const CapacityMap& _capacity, FlowMap& _flow) 
+//       : Parent(), undir(_graph), capacity(&_capacity), flow(&_flow),
+// 	nodes(*this, _graph), edges(*this, _graph) {
+//       Parent::construct(undir, nodes, edges);
+//       setFlowMap(_flow);
+//       setCapacityMap(_capacity);
+//       typename Graph::Edge edge; 
+//       for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
+// 	if ((*flow)[edge] != (*capacity)[edge]) {
+// 	  Parent::unHide(direct(edge, true));
+// 	}
+// 	if ((*flow)[edge] != 0) {
+// 	  Parent::unHide(direct(edge, false));
+// 	}
+//       }
+//     }
+
+//     void augment(const Edge& e, Number a) {
+//       if (direction(e)) {
+// 	flow->set(e, (*flow)[e]+a);
+//       } else { 
+// 	flow->set(e, (*flow)[e]-a);
+//       }
+//       if ((*flow)[e] == (*capacity)[e]) {
+// 	Parent::hide(e);
+//       } else {
+// 	Parent::unHide(e);
+//       }
+//       if ((*flow)[e] == 0) {
+// 	Parent::hide(oppositeEdge(e));
+//       } else {
+// 	Parent::unHide(oppositeEdge(e));
+//       }
+//     }
+
+//     Number resCap(const Edge& e) {
+//       if (direction(e)) { 
+// 	return (*capacity)[e]-(*flow)[e]; 
+//       } else { 
+// 	return (*flow)[e];
+//       }
+//     }
+    
+//     bool direction(const Edge& edge) const {
+//       return Parent::getGraph().direction(edge);
+//     }
+
+//     Edge direct(const UndirEdge& edge, bool direction) const {
+//       return Parent::getGraph().direct(edge, direction);
+//     }
+
+//     Edge direct(const UndirEdge& edge, const Node& node) const {
+//       return Parent::getGraph().direct(edge, node);
+//     }
+
+//     Edge oppositeEdge(const Edge& edge) const {
+//       return Parent::getGraph().oppositeEdge(edge);
+//     }
+
+//     /// \brief Residual capacity map.
+//     ///
+//     /// In generic residual graphs the residual capacity can be obtained 
+//     /// as a map. 
+//     class ResCap {
+//     protected:
+//       const ResGraphAdaptor* res_graph;
+//     public:
+//       typedef Number Value;
+//       typedef Edge Key;
+//       ResCap(const ResGraphAdaptor& _res_graph) 
+// 	: res_graph(&_res_graph) {}
+//       Number operator[](const Edge& e) const {
+// 	return res_graph->resCap(e);
+//       }
+//     };
+//   };
+
+}
+
+#endif