diff -r c35afa9e89e7 -r ef88c0a30f85 lemon/edge_set.h
--- a/lemon/edge_set.h	Mon Jan 12 23:11:39 2009 +0100
+++ b/lemon/edge_set.h	Thu Nov 05 15:48:01 2009 +0100
@@ -22,20 +22,19 @@
 #include <lemon/core.h>
 #include <lemon/bits/edge_set_extender.h>
 
-/// \ingroup semi_adaptors
+/// \ingroup graphs
 /// \file
 /// \brief ArcSet and EdgeSet classes.
 ///
 /// Graphs which use another graph's node-set as own.
 namespace lemon {
 
-  template <typename _Graph>
+  template <typename GR>
   class ListArcSetBase {
   public:
 
-    typedef _Graph Graph;
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
+    typedef typename GR::Node Node;
+    typedef typename GR::NodeIt NodeIt;
 
   protected:
 
@@ -44,10 +43,10 @@
       NodeT() : first_out(-1), first_in(-1) {}
     };
 
-    typedef typename ItemSetTraits<Graph, Node>::
+    typedef typename ItemSetTraits<GR, Node>::
     template Map<NodeT>::Type NodesImplBase;
 
-    NodesImplBase* nodes;
+    NodesImplBase* _nodes;
 
     struct ArcT {
       Node source, target;
@@ -61,17 +60,17 @@
     int first_arc;
     int first_free_arc;
 
-    const Graph* graph;
+    const GR* _graph;
 
-    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
-      graph = &_graph;
-      nodes = &_nodes;
+    void initalize(const GR& graph, NodesImplBase& nodes) {
+      _graph = &graph;
+      _nodes = &nodes;
     }
 
   public:
 
     class Arc {
-      friend class ListArcSetBase<Graph>;
+      friend class ListArcSetBase<GR>;
     protected:
       Arc(int _id) : id(_id) {}
       int id;
@@ -85,6 +84,12 @@
 
     ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Arc addArc(const Node& u, const Node& v) {
       int n;
       if (first_free_arc == -1) {
@@ -94,16 +99,16 @@
         n = first_free_arc;
         first_free_arc = arcs[first_free_arc].next_in;
       }
-      arcs[n].next_in = (*nodes)[v].first_in;
-      if ((*nodes)[v].first_in != -1) {
-        arcs[(*nodes)[v].first_in].prev_in = n;
+      arcs[n].next_in = (*_nodes)[v].first_in;
+      if ((*_nodes)[v].first_in != -1) {
+        arcs[(*_nodes)[v].first_in].prev_in = n;
       }
-      (*nodes)[v].first_in = n;
-      arcs[n].next_out = (*nodes)[u].first_out;
-      if ((*nodes)[u].first_out != -1) {
-        arcs[(*nodes)[u].first_out].prev_out = n;
+      (*_nodes)[v].first_in = n;
+      arcs[n].next_out = (*_nodes)[u].first_out;
+      if ((*_nodes)[u].first_out != -1) {
+        arcs[(*_nodes)[u].first_out].prev_out = n;
       }
-      (*nodes)[u].first_out = n;
+      (*_nodes)[u].first_out = n;
       arcs[n].source = u;
       arcs[n].target = v;
       return Arc(n);
@@ -114,7 +119,7 @@
       if (arcs[n].prev_in != -1) {
         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
       } else {
-        (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
+        (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
       }
       if (arcs[n].next_in != -1) {
         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
@@ -123,7 +128,7 @@
       if (arcs[n].prev_out != -1) {
         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
       } else {
-        (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
+        (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
       }
       if (arcs[n].next_out != -1) {
         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
@@ -134,8 +139,8 @@
     void clear() {
       Node node;
       for (first(node); node != INVALID; next(node)) {
-        (*nodes)[node].first_in = -1;
-        (*nodes)[node].first_out = -1;
+        (*_nodes)[node].first_in = -1;
+        (*_nodes)[node].first_out = -1;
       }
       arcs.clear();
       first_arc = -1;
@@ -143,20 +148,20 @@
     }
 
     void first(Node& node) const {
-      graph->first(node);
+      _graph->first(node);
     }
 
     void next(Node& node) const {
-      graph->next(node);
+      _graph->next(node);
     }
 
     void first(Arc& arc) const {
       Node node;
       first(node);
-      while (node != INVALID && (*nodes)[node].first_in == -1) {
+      while (node != INVALID && (*_nodes)[node].first_in == -1) {
         next(node);
       }
-      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
+      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
     }
 
     void next(Arc& arc) const {
@@ -165,15 +170,15 @@
       } else {
         Node node = arcs[arc.id].target;
         next(node);
-        while (node != INVALID && (*nodes)[node].first_in == -1) {
+        while (node != INVALID && (*_nodes)[node].first_in == -1) {
           next(node);
         }
-        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
+        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
       }
     }
 
     void firstOut(Arc& arc, const Node& node) const {
-      arc.id = (*nodes)[node].first_out;
+      arc.id = (*_nodes)[node].first_out;
     }
 
     void nextOut(Arc& arc) const {
@@ -181,42 +186,42 @@
     }
 
     void firstIn(Arc& arc, const Node& node) const {
-      arc.id = (*nodes)[node].first_in;
+      arc.id = (*_nodes)[node].first_in;
     }
 
     void nextIn(Arc& arc) const {
       arc.id = arcs[arc.id].next_in;
     }
 
-    int id(const Node& node) const { return graph->id(node); }
+    int id(const Node& node) const { return _graph->id(node); }
     int id(const Arc& arc) const { return arc.id; }
 
-    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
+    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
     Arc arcFromId(int ix) const { return Arc(ix); }
 
-    int maxNodeId() const { return graph->maxNodeId(); };
+    int maxNodeId() const { return _graph->maxNodeId(); };
     int maxArcId() const { return arcs.size() - 1; }
 
     Node source(const Arc& arc) const { return arcs[arc.id].source;}
     Node target(const Arc& arc) const { return arcs[arc.id].target;}
 
-    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
     NodeNotifier& notifier(Node) const {
-      return graph->notifier(Node());
+      return _graph->notifier(Node());
     }
 
-    template <typename _Value>
-    class NodeMap : public Graph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
+
     public:
 
-      typedef typename _Graph::template NodeMap<_Value> Parent;
+      explicit NodeMap(const ListArcSetBase<GR>& arcset)
+        : Parent(*arcset._graph) {}
 
-      explicit NodeMap(const ListArcSetBase<Graph>& arcset)
-        : Parent(*arcset.graph) {}
-
-      NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
-        : Parent(*arcset.graph, value) {}
+      NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
+        : Parent(*arcset._graph, value) {}
 
       NodeMap& operator=(const NodeMap& cmap) {
         return operator=<NodeMap>(cmap);
@@ -231,7 +236,7 @@
 
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Digraph using a node set of another digraph or graph and
   /// an own arc set.
@@ -250,26 +255,22 @@
   /// that node can be removed from the underlying graph, in this case
   /// all arcs incident to the given node is erased from the arc set.
   ///
-  /// \param _Graph The type of the graph which shares its node set with
+  /// \param GR The type of the graph which shares its node set with
   /// this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   /// concept.
   ///
-  /// This class is fully conform to the \ref concepts::Digraph
+  /// This class fully conforms to the \ref concepts::Digraph
   /// "Digraph" concept.
-  template <typename _Graph>
-  class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
+  template <typename GR>
+  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
+    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
 
   public:
 
-    typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;
 
-    typedef _Graph Graph;
-
-
     typedef typename Parent::NodesImplBase NodesImplBase;
 
     void eraseNode(const Node& node) {
@@ -292,10 +293,10 @@
     }
 
     class NodesImpl : public NodesImplBase {
-    public:
       typedef NodesImplBase Parent;
 
-      NodesImpl(const Graph& graph, ListArcSet& arcset)
+    public:
+      NodesImpl(const GR& graph, ListArcSet& arcset)
         : Parent(graph), _arcset(arcset) {}
 
       virtual ~NodesImpl() {}
@@ -321,22 +322,22 @@
       ListArcSet& _arcset;
     };
 
-    NodesImpl nodes;
+    NodesImpl _nodes;
 
   public:
 
     /// \brief Constructor of the ArcSet.
     ///
     /// Constructor of the ArcSet.
-    ListArcSet(const Graph& graph) : nodes(graph, *this) {
-      Parent::initalize(graph, nodes);
+    ListArcSet(const GR& graph) : _nodes(graph, *this) {
+      Parent::initalize(graph, _nodes);
     }
 
     /// \brief Add a new arc to the digraph.
     ///
     /// Add a new arc to the digraph with source node \c s
     /// and target node \c t.
-    /// \return the new arc.
+    /// \return The new arc.
     Arc addArc(const Node& s, const Node& t) {
       return Parent::addArc(s, t);
     }
@@ -350,13 +351,12 @@
 
   };
 
-  template <typename _Graph>
+  template <typename GR>
   class ListEdgeSetBase {
   public:
 
-    typedef _Graph Graph;
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
+    typedef typename GR::Node Node;
+    typedef typename GR::NodeIt NodeIt;
 
   protected:
 
@@ -365,10 +365,10 @@
       NodeT() : first_out(-1) {}
     };
 
-    typedef typename ItemSetTraits<Graph, Node>::
+    typedef typename ItemSetTraits<GR, Node>::
     template Map<NodeT>::Type NodesImplBase;
 
-    NodesImplBase* nodes;
+    NodesImplBase* _nodes;
 
     struct ArcT {
       Node target;
@@ -381,11 +381,11 @@
     int first_arc;
     int first_free_arc;
 
-    const Graph* graph;
+    const GR* _graph;
 
-    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
-      graph = &_graph;
-      nodes = &_nodes;
+    void initalize(const GR& graph, NodesImplBase& nodes) {
+      _graph = &graph;
+      _nodes = &nodes;
     }
 
   public:
@@ -422,6 +422,12 @@
 
     ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Edge addEdge(const Node& u, const Node& v) {
       int n;
 
@@ -437,18 +443,18 @@
       arcs[n].target = u;
       arcs[n | 1].target = v;
 
-      arcs[n].next_out = (*nodes)[v].first_out;
-      if ((*nodes)[v].first_out != -1) {
-        arcs[(*nodes)[v].first_out].prev_out = n;
+      arcs[n].next_out = (*_nodes)[v].first_out;
+      if ((*_nodes)[v].first_out != -1) {
+        arcs[(*_nodes)[v].first_out].prev_out = n;
       }
-      (*nodes)[v].first_out = n;
+      (*_nodes)[v].first_out = n;
       arcs[n].prev_out = -1;
 
-      if ((*nodes)[u].first_out != -1) {
-        arcs[(*nodes)[u].first_out].prev_out = (n | 1);
+      if ((*_nodes)[u].first_out != -1) {
+        arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
       }
-      arcs[n | 1].next_out = (*nodes)[u].first_out;
-      (*nodes)[u].first_out = (n | 1);
+      arcs[n | 1].next_out = (*_nodes)[u].first_out;
+      (*_nodes)[u].first_out = (n | 1);
       arcs[n | 1].prev_out = -1;
 
       return Edge(n / 2);
@@ -464,7 +470,7 @@
       if (arcs[n].prev_out != -1) {
         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
       } else {
-        (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
+        (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
       }
 
       if (arcs[n | 1].next_out != -1) {
@@ -474,7 +480,7 @@
       if (arcs[n | 1].prev_out != -1) {
         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
       } else {
-        (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
+        (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
       }
 
       arcs[n].next_out = first_free_arc;
@@ -485,7 +491,7 @@
     void clear() {
       Node node;
       for (first(node); node != INVALID; next(node)) {
-        (*nodes)[node].first_out = -1;
+        (*_nodes)[node].first_out = -1;
       }
       arcs.clear();
       first_arc = -1;
@@ -493,20 +499,20 @@
     }
 
     void first(Node& node) const {
-      graph->first(node);
+      _graph->first(node);
     }
 
     void next(Node& node) const {
-      graph->next(node);
+      _graph->next(node);
     }
 
     void first(Arc& arc) const {
       Node node;
       first(node);
-      while (node != INVALID && (*nodes)[node].first_out == -1) {
+      while (node != INVALID && (*_nodes)[node].first_out == -1) {
         next(node);
       }
-      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
+      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
     }
 
     void next(Arc& arc) const {
@@ -515,10 +521,10 @@
       } else {
         Node node = arcs[arc.id ^ 1].target;
         next(node);
-        while(node != INVALID && (*nodes)[node].first_out == -1) {
+        while(node != INVALID && (*_nodes)[node].first_out == -1) {
           next(node);
         }
-        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
+        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
       }
     }
 
@@ -526,7 +532,7 @@
       Node node;
       first(node);
       while (node != INVALID) {
-        edge.id = (*nodes)[node].first_out;
+        edge.id = (*_nodes)[node].first_out;
         while ((edge.id & 1) != 1) {
           edge.id = arcs[edge.id].next_out;
         }
@@ -551,7 +557,7 @@
       }
       next(node);
       while (node != INVALID) {
-        edge.id = (*nodes)[node].first_out;
+        edge.id = (*_nodes)[node].first_out;
         while ((edge.id & 1) != 1) {
           edge.id = arcs[edge.id].next_out;
         }
@@ -565,7 +571,7 @@
     }
 
     void firstOut(Arc& arc, const Node& node) const {
-      arc.id = (*nodes)[node].first_out;
+      arc.id = (*_nodes)[node].first_out;
     }
 
     void nextOut(Arc& arc) const {
@@ -573,7 +579,7 @@
     }
 
     void firstIn(Arc& arc, const Node& node) const {
-      arc.id = (((*nodes)[node].first_out) ^ 1);
+      arc.id = (((*_nodes)[node].first_out) ^ 1);
       if (arc.id == -2) arc.id = -1;
     }
 
@@ -583,7 +589,7 @@
     }
 
     void firstInc(Edge &arc, bool& dir, const Node& node) const {
-      int de = (*nodes)[node].first_out;
+      int de = (*_nodes)[node].first_out;
       if (de != -1 ) {
         arc.id = de / 2;
         dir = ((de & 1) == 1);
@@ -611,15 +617,15 @@
       return Arc(edge.id * 2 + (dir ? 1 : 0));
     }
 
-    int id(const Node& node) const { return graph->id(node); }
+    int id(const Node& node) const { return _graph->id(node); }
     static int id(Arc e) { return e.id; }
     static int id(Edge e) { return e.id; }
 
-    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
+    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
     static Arc arcFromId(int id) { return Arc(id);}
     static Edge edgeFromId(int id) { return Edge(id);}
 
-    int maxNodeId() const { return graph->maxNodeId(); };
+    int maxNodeId() const { return _graph->maxNodeId(); };
     int maxEdgeId() const { return arcs.size() / 2 - 1; }
     int maxArcId() const { return arcs.size()-1; }
 
@@ -629,23 +635,23 @@
     Node u(Edge e) const { return arcs[2 * e.id].target; }
     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 
-    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
     NodeNotifier& notifier(Node) const {
-      return graph->notifier(Node());
+      return _graph->notifier(Node());
     }
 
-    template <typename _Value>
-    class NodeMap : public Graph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
+
     public:
 
-      typedef typename _Graph::template NodeMap<_Value> Parent;
+      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
+        : Parent(*arcset._graph) {}
 
-      explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
-        : Parent(*arcset.graph) {}
-
-      NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
-        : Parent(*arcset.graph, value) {}
+      NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
+        : Parent(*arcset._graph, value) {}
 
       NodeMap& operator=(const NodeMap& cmap) {
         return operator=<NodeMap>(cmap);
@@ -660,7 +666,7 @@
 
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Graph using a node set of another digraph or graph and an
   /// own edge set.
@@ -679,27 +685,23 @@
   /// be removed from the underlying graph, in this case all edges
   /// incident to the given node is erased from the arc set.
   ///
-  /// \param _Graph The type of the graph which shares its node set
+  /// \param GR The type of the graph which shares its node set
   /// with this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   /// concept.
   ///
-  /// This class is fully conform to the \ref concepts::Graph "Graph"
+  /// This class fully conforms to the \ref concepts::Graph "Graph"
   /// concept.
-  template <typename _Graph>
-  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
+  template <typename GR>
+  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
+    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
 
   public:
 
-    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;
     typedef typename Parent::Edge Edge;
 
-    typedef _Graph Graph;
-
-
     typedef typename Parent::NodesImplBase NodesImplBase;
 
     void eraseNode(const Node& node) {
@@ -717,10 +719,10 @@
     }
 
     class NodesImpl : public NodesImplBase {
-    public:
       typedef NodesImplBase Parent;
 
-      NodesImpl(const Graph& graph, ListEdgeSet& arcset)
+    public:
+      NodesImpl(const GR& graph, ListEdgeSet& arcset)
         : Parent(graph), _arcset(arcset) {}
 
       virtual ~NodesImpl() {}
@@ -746,22 +748,22 @@
       ListEdgeSet& _arcset;
     };
 
-    NodesImpl nodes;
+    NodesImpl _nodes;
 
   public:
 
     /// \brief Constructor of the EdgeSet.
     ///
     /// Constructor of the EdgeSet.
-    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
-      Parent::initalize(graph, nodes);
+    ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
+      Parent::initalize(graph, _nodes);
     }
 
     /// \brief Add a new edge to the graph.
     ///
     /// Add a new edge to the graph with node \c u
     /// and node \c v endpoints.
-    /// \return the new edge.
+    /// \return The new edge.
     Edge addEdge(const Node& u, const Node& v) {
       return Parent::addEdge(u, v);
     }
@@ -775,13 +777,12 @@
 
   };
 
-  template <typename _Graph>
+  template <typename GR>
   class SmartArcSetBase {
   public:
 
-    typedef _Graph Graph;
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
+    typedef typename GR::Node Node;
+    typedef typename GR::NodeIt NodeIt;
 
   protected:
 
@@ -790,10 +791,10 @@
       NodeT() : first_out(-1), first_in(-1) {}
     };
 
-    typedef typename ItemSetTraits<Graph, Node>::
+    typedef typename ItemSetTraits<GR, Node>::
     template Map<NodeT>::Type NodesImplBase;
 
-    NodesImplBase* nodes;
+    NodesImplBase* _nodes;
 
     struct ArcT {
       Node source, target;
@@ -803,17 +804,17 @@
 
     std::vector<ArcT> arcs;
 
-    const Graph* graph;
+    const GR* _graph;
 
-    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
-      graph = &_graph;
-      nodes = &_nodes;
+    void initalize(const GR& graph, NodesImplBase& nodes) {
+      _graph = &graph;
+      _nodes = &nodes;
     }
 
   public:
 
     class Arc {
-      friend class SmartArcSetBase<Graph>;
+      friend class SmartArcSetBase<GR>;
     protected:
       Arc(int _id) : id(_id) {}
       int id;
@@ -827,13 +828,19 @@
 
     SmartArcSetBase() {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Arc addArc(const Node& u, const Node& v) {
       int n = arcs.size();
       arcs.push_back(ArcT());
-      arcs[n].next_in = (*nodes)[v].first_in;
-      (*nodes)[v].first_in = n;
-      arcs[n].next_out = (*nodes)[u].first_out;
-      (*nodes)[u].first_out = n;
+      arcs[n].next_in = (*_nodes)[v].first_in;
+      (*_nodes)[v].first_in = n;
+      arcs[n].next_out = (*_nodes)[u].first_out;
+      (*_nodes)[u].first_out = n;
       arcs[n].source = u;
       arcs[n].target = v;
       return Arc(n);
@@ -842,30 +849,30 @@
     void clear() {
       Node node;
       for (first(node); node != INVALID; next(node)) {
-        (*nodes)[node].first_in = -1;
-        (*nodes)[node].first_out = -1;
+        (*_nodes)[node].first_in = -1;
+        (*_nodes)[node].first_out = -1;
       }
       arcs.clear();
     }
 
     void first(Node& node) const {
-      graph->first(node);
+      _graph->first(node);
     }
 
     void next(Node& node) const {
-      graph->next(node);
+      _graph->next(node);
     }
 
     void first(Arc& arc) const {
       arc.id = arcs.size() - 1;
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
 
     void firstOut(Arc& arc, const Node& node) const {
-      arc.id = (*nodes)[node].first_out;
+      arc.id = (*_nodes)[node].first_out;
     }
 
     void nextOut(Arc& arc) const {
@@ -873,42 +880,42 @@
     }
 
     void firstIn(Arc& arc, const Node& node) const {
-      arc.id = (*nodes)[node].first_in;
+      arc.id = (*_nodes)[node].first_in;
     }
 
     void nextIn(Arc& arc) const {
       arc.id = arcs[arc.id].next_in;
     }
 
-    int id(const Node& node) const { return graph->id(node); }
+    int id(const Node& node) const { return _graph->id(node); }
     int id(const Arc& arc) const { return arc.id; }
 
-    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
+    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
     Arc arcFromId(int ix) const { return Arc(ix); }
 
-    int maxNodeId() const { return graph->maxNodeId(); };
+    int maxNodeId() const { return _graph->maxNodeId(); };
     int maxArcId() const { return arcs.size() - 1; }
 
     Node source(const Arc& arc) const { return arcs[arc.id].source;}
     Node target(const Arc& arc) const { return arcs[arc.id].target;}
 
-    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
     NodeNotifier& notifier(Node) const {
-      return graph->notifier(Node());
+      return _graph->notifier(Node());
     }
 
-    template <typename _Value>
-    class NodeMap : public Graph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
+
     public:
 
-      typedef typename _Graph::template NodeMap<_Value> Parent;
+      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
+        : Parent(*arcset._graph) { }
 
-      explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
-        : Parent(*arcset.graph) { }
-
-      NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
-        : Parent(*arcset.graph, value) { }
+      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
+        : Parent(*arcset._graph, value) { }
 
       NodeMap& operator=(const NodeMap& cmap) {
         return operator=<NodeMap>(cmap);
@@ -924,7 +931,7 @@
   };
 
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Digraph using a node set of another digraph or graph and
   /// an own arc set.
@@ -937,7 +944,7 @@
   /// class. The node handling functions (id handling, observing, and
   /// iterators) works equivalently as in the original graph.
   ///
-  /// \param _Graph The type of the graph which shares its node set with
+  /// \param GR The type of the graph which shares its node set with
   /// this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   /// concept.
@@ -952,20 +959,17 @@
   /// the arc set is invalidated, and it cannot be used anymore. The
   /// validity can be checked with the \c valid() member function.
   ///
-  /// This class is fully conform to the \ref concepts::Digraph
+  /// This class fully conforms to the \ref concepts::Digraph
   /// "Digraph" concept.
-  template <typename _Graph>
-  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
+  template <typename GR>
+  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
+    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
 
   public:
 
-    typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;
 
-    typedef _Graph Graph;
-
   protected:
 
     typedef typename Parent::NodesImplBase NodesImplBase;
@@ -983,10 +987,10 @@
     }
 
     class NodesImpl : public NodesImplBase {
-    public:
       typedef NodesImplBase Parent;
 
-      NodesImpl(const Graph& graph, SmartArcSet& arcset)
+    public:
+      NodesImpl(const GR& graph, SmartArcSet& arcset)
         : Parent(graph), _arcset(arcset) {}
 
       virtual ~NodesImpl() {}
@@ -1026,22 +1030,22 @@
       SmartArcSet& _arcset;
     };
 
-    NodesImpl nodes;
+    NodesImpl _nodes;
 
   public:
 
     /// \brief Constructor of the ArcSet.
     ///
     /// Constructor of the ArcSet.
-    SmartArcSet(const Graph& graph) : nodes(graph, *this) {
-      Parent::initalize(graph, nodes);
+    SmartArcSet(const GR& graph) : _nodes(graph, *this) {
+      Parent::initalize(graph, _nodes);
     }
 
     /// \brief Add a new arc to the digraph.
     ///
     /// Add a new arc to the digraph with source node \c s
     /// and target node \c t.
-    /// \return the new arc.
+    /// \return The new arc.
     Arc addArc(const Node& s, const Node& t) {
       return Parent::addArc(s, t);
     }
@@ -1052,19 +1056,18 @@
     /// invalidated. It occurs when a node in the underlying graph is
     /// erased and it is not isolated in the ArcSet.
     bool valid() const {
-      return nodes.attached();
+      return _nodes.attached();
     }
 
   };
 
 
-  template <typename _Graph>
+  template <typename GR>
   class SmartEdgeSetBase {
   public:
 
-    typedef _Graph Graph;
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
+    typedef typename GR::Node Node;
+    typedef typename GR::NodeIt NodeIt;
 
   protected:
 
@@ -1073,10 +1076,10 @@
       NodeT() : first_out(-1) {}
     };
 
-    typedef typename ItemSetTraits<Graph, Node>::
+    typedef typename ItemSetTraits<GR, Node>::
     template Map<NodeT>::Type NodesImplBase;
 
-    NodesImplBase* nodes;
+    NodesImplBase* _nodes;
 
     struct ArcT {
       Node target;
@@ -1086,11 +1089,11 @@
 
     std::vector<ArcT> arcs;
 
-    const Graph* graph;
+    const GR* _graph;
 
-    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
-      graph = &_graph;
-      nodes = &_nodes;
+    void initalize(const GR& graph, NodesImplBase& nodes) {
+      _graph = &graph;
+      _nodes = &nodes;
     }
 
   public:
@@ -1127,6 +1130,12 @@
 
     SmartEdgeSetBase() {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Edge addEdge(const Node& u, const Node& v) {
       int n = arcs.size();
       arcs.push_back(ArcT());
@@ -1135,11 +1144,11 @@
       arcs[n].target = u;
       arcs[n | 1].target = v;
 
-      arcs[n].next_out = (*nodes)[v].first_out;
-      (*nodes)[v].first_out = n;
+      arcs[n].next_out = (*_nodes)[v].first_out;
+      (*_nodes)[v].first_out = n;
 
-      arcs[n | 1].next_out = (*nodes)[u].first_out;
-      (*nodes)[u].first_out = (n | 1);
+      arcs[n | 1].next_out = (*_nodes)[u].first_out;
+      (*_nodes)[u].first_out = (n | 1);
 
       return Edge(n / 2);
     }
@@ -1147,24 +1156,24 @@
     void clear() {
       Node node;
       for (first(node); node != INVALID; next(node)) {
-        (*nodes)[node].first_out = -1;
+        (*_nodes)[node].first_out = -1;
       }
       arcs.clear();
     }
 
     void first(Node& node) const {
-      graph->first(node);
+      _graph->first(node);
     }
 
     void next(Node& node) const {
-      graph->next(node);
+      _graph->next(node);
     }
 
     void first(Arc& arc) const {
       arc.id = arcs.size() - 1;
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
 
@@ -1172,12 +1181,12 @@
       arc.id = arcs.size() / 2 - 1;
     }
 
-    void next(Edge& arc) const {
+    static void next(Edge& arc) {
       --arc.id;
     }
 
     void firstOut(Arc& arc, const Node& node) const {
-      arc.id = (*nodes)[node].first_out;
+      arc.id = (*_nodes)[node].first_out;
     }
 
     void nextOut(Arc& arc) const {
@@ -1185,7 +1194,7 @@
     }
 
     void firstIn(Arc& arc, const Node& node) const {
-      arc.id = (((*nodes)[node].first_out) ^ 1);
+      arc.id = (((*_nodes)[node].first_out) ^ 1);
       if (arc.id == -2) arc.id = -1;
     }
 
@@ -1195,7 +1204,7 @@
     }
 
     void firstInc(Edge &arc, bool& dir, const Node& node) const {
-      int de = (*nodes)[node].first_out;
+      int de = (*_nodes)[node].first_out;
       if (de != -1 ) {
         arc.id = de / 2;
         dir = ((de & 1) == 1);
@@ -1223,15 +1232,15 @@
       return Arc(edge.id * 2 + (dir ? 1 : 0));
     }
 
-    int id(Node node) const { return graph->id(node); }
+    int id(Node node) const { return _graph->id(node); }
     static int id(Arc arc) { return arc.id; }
     static int id(Edge arc) { return arc.id; }
 
-    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
+    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
     static Arc arcFromId(int id) { return Arc(id); }
     static Edge edgeFromId(int id) { return Edge(id);}
 
-    int maxNodeId() const { return graph->maxNodeId(); };
+    int maxNodeId() const { return _graph->maxNodeId(); };
     int maxArcId() const { return arcs.size() - 1; }
     int maxEdgeId() const { return arcs.size() / 2 - 1; }
 
@@ -1241,23 +1250,23 @@
     Node u(Edge e) const { return arcs[2 * e.id].target; }
     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 
-    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 
     NodeNotifier& notifier(Node) const {
-      return graph->notifier(Node());
+      return _graph->notifier(Node());
     }
 
-    template <typename _Value>
-    class NodeMap : public Graph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
+
     public:
 
-      typedef typename _Graph::template NodeMap<_Value> Parent;
+      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
+        : Parent(*arcset._graph) { }
 
-      explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
-        : Parent(*arcset.graph) { }
-
-      NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
-        : Parent(*arcset.graph, value) { }
+      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
+        : Parent(*arcset._graph, value) { }
 
       NodeMap& operator=(const NodeMap& cmap) {
         return operator=<NodeMap>(cmap);
@@ -1272,7 +1281,7 @@
 
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Graph using a node set of another digraph or graph and an
   /// own edge set.
@@ -1285,7 +1294,7 @@
   /// node handling functions (id handling, observing, and iterators)
   /// works equivalently as in the original graph.
   ///
-  /// \param _Graph The type of the graph which shares its node set
+  /// \param GR The type of the graph which shares its node set
   /// with this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   ///  concept.
@@ -1300,21 +1309,18 @@
   /// is invalidated, and it cannot be used anymore. The validity can
   /// be checked with the \c valid() member function.
   ///
-  /// This class is fully conform to the \ref concepts::Graph
+  /// This class fully conforms to the \ref concepts::Graph
   /// "Graph" concept.
-  template <typename _Graph>
-  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
+  template <typename GR>
+  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
+    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
 
   public:
 
-    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;
     typedef typename Parent::Edge Edge;
 
-    typedef _Graph Graph;
-
   protected:
 
     typedef typename Parent::NodesImplBase NodesImplBase;
@@ -1331,10 +1337,10 @@
     }
 
     class NodesImpl : public NodesImplBase {
-    public:
       typedef NodesImplBase Parent;
 
-      NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
+    public:
+      NodesImpl(const GR& graph, SmartEdgeSet& arcset)
         : Parent(graph), _arcset(arcset) {}
 
       virtual ~NodesImpl() {}
@@ -1374,22 +1380,22 @@
       SmartEdgeSet& _arcset;
     };
 
-    NodesImpl nodes;
+    NodesImpl _nodes;
 
   public:
 
     /// \brief Constructor of the EdgeSet.
     ///
     /// Constructor of the EdgeSet.
-    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
-      Parent::initalize(graph, nodes);
+    SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
+      Parent::initalize(graph, _nodes);
     }
 
     /// \brief Add a new edge to the graph.
     ///
     /// Add a new edge to the graph with node \c u
     /// and node \c v endpoints.
-    /// \return the new edge.
+    /// \return The new edge.
     Edge addEdge(const Node& u, const Node& v) {
       return Parent::addEdge(u, v);
     }
@@ -1400,7 +1406,7 @@
     /// invalidated. It occurs when a node in the underlying graph is
     /// erased and it is not isolated in the EdgeSet.
     bool valid() const {
-      return nodes.attached();
+      return _nodes.attached();
     }
 
   };