template <typename _Graph>

   class NewEdgeSetAdaptorBase {

   public:

     typedef _Graph Graph;

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

   protected:

     struct NodeT {

       int first_out, first_in;

       NodeT() : first_out(-1), first_in(-1) {}

     };

     class NodesImpl : protected Graph::template NodeMap<NodeT> {

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

       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;

       Adaptor& adaptor;

     public:

       NodesImpl(Adaptor& _adaptor, const Graph& _graph) 

 	: Parent(_graph), adaptor(_adaptor) {}

       virtual ~NodesImpl() {}

       virtual void build() {

 	Parent::build();

       }

       virtual void clear() {

 	adaptor._clear();

 	Parent::clear();

       }

       virtual void add(const Node& node) {

 	Parent::add(node);

 	adaptor._add(node);

       }

       virtual void erase(const Node& node) {

 	adaptor._erase(node);

 	Parent::erase(node);

       }

       NodeT& operator[](const Node& node) {

 	return Parent::operator[](node);

       }

       const NodeT& operator[](const Node& node) const {

 	return Parent::operator[](node);

       }

     };

     NodesImpl* nodes;

     struct EdgeT {

       Node source, target;

       int next_out, next_in;

       int prev_out, prev_in;

       EdgeT() : prev_out(-1), prev_in(-1) {}

     };

     std::vector<EdgeT> edges;

     int first_edge;

     int first_free_edge;

     virtual void _clear() = 0;

     virtual void _add(const Node& node) = 0;

     virtual void _erase(const Node& node) = 0;

     const Graph* graph;

     void initalize(const Graph& _graph, NodesImpl& _nodes) {

       graph = &_graph;

       nodes = &_nodes;

     }

   public:

     class Edge {

       friend class NewEdgeSetAdaptorBase<Graph>;

     protected:

       Edge(int _id) : id(_id) {}

       int id;

     public:

       Edge() {}

       Edge(Invalid) : id(-1) {}

       bool operator==(const Edge& edge) const { return id == edge.id; }

       bool operator!=(const Edge& edge) const { return id != edge.id; }

       bool operator<(const Edge& edge) const { return id < edge.id; }

     };

     NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 

     virtual ~NewEdgeSetAdaptorBase() {}

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

       int n;

       if (first_free_edge == -1) {

 	n = edges.size();

 	edges.push_back(EdgeT());

       } else {

 	n = first_free_edge;

 	first_free_edge = edges[first_free_edge].next_in;

       }

       edges[n].next_in = (*nodes)[target].first_in;

       (*nodes)[target].first_in = n;

       edges[n].next_out = (*nodes)[source].first_out;

       (*nodes)[source].first_out = n;

       edges[n].source = source;

       edges[n].target = target;

       return Edge(n);

     }

     void erase(const Edge& edge) {

       int n = edge.id;

       if (edges[n].prev_in != -1) {

 	edges[edges[n].prev_in].next_in = edges[n].next_in;

       } else {

 	(*nodes)[edges[n].target].first_in = edges[n].next_in;

       }

       if (edges[n].next_in != -1) {

 	edges[edges[n].next_in].prev_in = edges[n].prev_in;

       }

       if (edges[n].prev_out != -1) {

 	edges[edges[n].prev_out].next_out = edges[n].next_out;

       } else {

 	(*nodes)[edges[n].source].first_out = edges[n].next_out;

       }

       if (edges[n].next_out != -1) {

 	edges[edges[n].next_out].prev_out = edges[n].prev_out;

       }

     }

     void first(Node& node) const {

       graph->first(node);

     }

     void next(Node& node) const {

       graph->next(node);

     }

     void first(Edge& edge) const {

       Node node;

       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 

 	   next(node));

       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

     }

     void next(Edge& edge) const {

       if (edges[edge.id].next_in != -1) {

 	edge.id = edges[edge.id].next_in;

       } else {

 	Node node = edges[edge.id].target;

 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 

 	     next(node));

 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

       }      

     }

     void firstOut(Edge& edge, const Node& node) const {

       edge.id = (*nodes)[node].first_out;    

     }

     void nextOut(Edge& edge) const {

       edge.id = edges[edge.id].next_out;        

     }

     void firstIn(Edge& edge, const Node& node) const {

       edge.id = (*nodes)[node].first_in;          

     }

     void nextIn(Edge& edge) const {

       edge.id = edges[edge.id].next_in;    

     }

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

     int id(const Edge& edge) const { return edge.id; }

     Node nodeFromId(int id) const { return graph->fromId(id, Node()); }

     Edge edgeFromId(int id) const { return Edge(id); }

     int maxNodeId() const { return graph->maxId(Node()); };

     int maxEdgeId() const { return edges.size() - 1; }

     Node source(const Edge& edge) const { return edges[edge.id].source;}

     Node target(const Edge& edge) const { return edges[edge.id].target;}

   };

   /// \brief Graph adaptor using a node set of another graph and an

   /// own edge set.

   ///

   /// This structure can be used to establish another graph over a node set

   /// of an existing one. The node iterator will go through the nodes of the

   /// original graph.

   ///

   /// \param _Graph The type of the graph which shares its node set with 

   /// this class. Its interface must conform to the \ref concept::StaticGraph

   /// "StaticGraph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.

   template <typename _Graph>

   class NewEdgeSetAdaptor :

     public ErasableGraphExtender<

     ClearableGraphExtender<

     ExtendableGraphExtender<

     MappableGraphExtender<

     IterableGraphExtender<

     AlterableGraphExtender<

     GraphExtender<

     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {

   public:

     typedef ErasableGraphExtender<

       ClearableGraphExtender<

       ExtendableGraphExtender<

       MappableGraphExtender<

       IterableGraphExtender<

       AlterableGraphExtender<

       GraphExtender<

       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   private:

     virtual void _clear() {

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

       Parent::getNotifier(Edge()).clear();

       Parent::getNotifier(Node()).clear();

     }

     virtual void _add(const Node& node) {

       Parent::getNotifier(Node()).add(node);

     }

     virtual void _erase(const Node& node) {

       Edge edge;

       Parent::firstOut(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstOut(edge, node);

       }

       Parent::firstIn(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstIn(edge, node);

       }

       Parent::getNotifier(Node()).erase(node);

     }

     typedef typename Parent::NodesImpl NodesImpl;

     NodesImpl nodes;

   public:

     /// \brief Constructor of the adaptor.

     /// 

     /// Constructor of the adaptor.

     NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {

       Parent::initalize(_graph, nodes);

     }

     void clear() {

       Parent::getNotifier(Edge()).clear();      

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

     }

   };

   /// \brief Graph adaptor using a node set of another graph and an

   /// own undir edge set.

   ///

   /// This structure can be used to establish another undirected graph over 

   /// a node set of an existing one. The node iterator will go through the 

   /// nodes of the original graph.

   ///

   /// \param _Graph The type of the graph which shares its node set with 

   /// this class. Its interface must conform to the \ref concept::StaticGraph

   /// "StaticGraph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.

   template <typename _Graph>

   class NewUndirEdgeSetAdaptor :

     public ErasableUndirGraphExtender<

     ClearableUndirGraphExtender<

     ExtendableUndirGraphExtender<

     MappableUndirGraphExtender<

     IterableUndirGraphExtender<

     AlterableUndirGraphExtender<

     UndirGraphExtender<

     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {

   public:

     typedef ErasableUndirGraphExtender<

       ClearableUndirGraphExtender<

       ExtendableUndirGraphExtender<

       MappableUndirGraphExtender<

       IterableUndirGraphExtender<

       AlterableUndirGraphExtender<

       UndirGraphExtender<

       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef typename Parent::UndirEdge UndirEdge;

   private:

     virtual void _clear() {

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

       Parent::getNotifier(Edge()).clear();

       Parent::getNotifier(Node()).clear();

     }

     virtual void _add(const Node& node) {

       Parent::getNotifier(Node()).add(node);

     }

     virtual void _erase(const Node& node) {

       Edge edge;

       Parent::firstOut(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstOut(edge, node);

       }

       Parent::firstIn(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstIn(edge, node);

       }

       Parent::getNotifier(Node()).erase(node);

     }

     typedef typename Parent::NodesImpl NodesImpl;

     NodesImpl nodes;

   public:

     /// \brief Constructor of the adaptor.

     /// 

     /// Constructor of the adaptor.

     NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {

       Parent::initalize(_graph, nodes);

     }

     void clear() {

       Parent::getNotifier(Edge()).clear();      

       Parent::getNotifier(UndirEdge()).clear();      

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

     }

   };