Index: lemon/list_graph.h
===================================================================
--- lemon/list_graph.h	(revision 73)
+++ lemon/list_graph.h	(revision 149)
@@ -153,4 +153,14 @@
     static Arc arcFromId(int id) { return Arc(id);}
 
+    bool valid(Node n) const { 
+      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 
+	nodes[n.id].prev != -2;
+    }
+
+    bool valid(Arc a) const { 
+      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 
+	arcs[a.id].prev_in != -2;
+    }
+
     Node addNode() {     
       int n;
@@ -220,4 +230,5 @@
       nodes[n].next = first_free_node;
       first_free_node = n;
+      nodes[n].prev = -2;
 
     }
@@ -248,6 +259,6 @@
       
       arcs[n].next_in = first_free_arc;
-      first_free_arc = n;      
-
+      first_free_arc = n;
+      arcs[n].prev_in = -2;
     }
 
@@ -350,4 +361,24 @@
       return Parent::addArc(s, t); 
     }
+
+    /// Node validity check
+
+    /// This function gives back true if the given node is valid,
+    /// ie. it is a real node of the graph.  
+    ///
+    /// \warning A Node pointing to a removed item
+    /// could become valid again later if new nodes are
+    /// added to the graph.
+    bool valid(Node n) const { return Parent::valid(n); }
+
+    /// Arc validity check
+
+    /// This function gives back true if the given arc is valid,
+    /// ie. it is a real arc of the graph.  
+    ///
+    /// \warning An Arc pointing to a removed item
+    /// could become valid again later if new nodes are
+    /// added to the graph.
+    bool valid(Arc a) const { return Parent::valid(a); }
 
     /// Change the target of \c e to \c n
@@ -946,4 +977,19 @@
     static Edge edgeFromId(int id) { return Edge(id);}
 
+    bool valid(Node n) const { 
+      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 
+	nodes[n.id].prev != -2;
+    }
+
+    bool valid(Arc a) const { 
+      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 
+	arcs[a.id].prev_out != -2;
+    }
+
+    bool valid(Edge e) const { 
+      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 
+	arcs[2 * e.id].prev_out != -2;
+    }
+
     Node addNode() {     
       int n;
@@ -1014,5 +1060,5 @@
       nodes[n].next = first_free_node;
       first_free_node = n;
-
+      nodes[n].prev = -2;
     }
     
@@ -1042,4 +1088,6 @@
       arcs[n].next_out = first_free_arc;
       first_free_arc = n;      
+      arcs[n].prev_out = -2;
+      arcs[n | 1].prev_out = -2;
 
     }
@@ -1158,4 +1206,31 @@
       return Parent::addEdge(s, t); 
     }
+    /// Node validity check
+
+    /// This function gives back true if the given node is valid,
+    /// ie. it is a real node of the graph.  
+    ///
+    /// \warning A Node pointing to a removed item
+    /// could become valid again later if new nodes are
+    /// added to the graph.
+    bool valid(Node n) const { return Parent::valid(n); }
+    /// Arc validity check
+
+    /// This function gives back true if the given arc is valid,
+    /// ie. it is a real arc of the graph.  
+    ///
+    /// \warning An Arc pointing to a removed item
+    /// could become valid again later if new edges are
+    /// added to the graph.
+    bool valid(Arc a) const { return Parent::valid(a); }
+    /// Edge validity check
+
+    /// This function gives back true if the given edge is valid,
+    /// ie. it is a real arc of the graph.  
+    ///
+    /// \warning A Edge pointing to a removed item
+    /// could become valid again later if new edges are
+    /// added to the graph.
+    bool valid(Edge e) const { return Parent::valid(e); }
     /// \brief Change the source of \c e to \c n
     ///
Index: lemon/smart_graph.h
===================================================================
--- lemon/smart_graph.h	(revision 139)
+++ lemon/smart_graph.h	(revision 149)
@@ -116,4 +116,11 @@
     static Arc arcFromId(int id) { return Arc(id);}
 
+    bool valid(Node n) const { 
+      return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 
+    }
+    bool valid(Arc a) const { 
+      return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 
+    }
+
     class Node {
       friend class SmartDigraphBase;
@@ -261,4 +268,22 @@
     /// \sa reserveNode
     void reserveArc(int m) { arcs.reserve(m); };
+
+    /// \brief Node validity check
+    ///
+    /// This function gives back true if the given node is valid,
+    /// ie. it is a real node of the graph.  
+    ///
+    /// \warning A removed node (using Snapshot) could become valid again
+    /// when new nodes are added to the graph.
+    bool valid(Node n) const { return Parent::valid(n); }
+
+    /// \brief Arc validity check
+    ///
+    /// This function gives back true if the given arc is valid,
+    /// ie. it is a real arc of the graph.  
+    ///
+    /// \warning A removed arc (using Snapshot) could become valid again
+    /// when new arcs are added to the graph.
+    bool valid(Arc a) const { return Parent::valid(a); }
 
     ///Clear the digraph.
@@ -551,4 +576,14 @@
     static Edge edgeFromId(int id) { return Edge(id);}
 
+    bool valid(Node n) const { 
+      return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 
+    }
+    bool valid(Arc a) const { 
+      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+    }
+    bool valid(Edge e) const { 
+      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 
+    }
+
     Node addNode() {     
       int n = nodes.size();
@@ -642,4 +677,31 @@
       return Parent::addEdge(s, t); 
     }
+
+    /// \brief Node validity check
+    ///
+    /// This function gives back true if the given node is valid,
+    /// ie. it is a real node of the graph.  
+    ///
+    /// \warning A removed node (using Snapshot) could become valid again
+    /// when new nodes are added to the graph.
+    bool valid(Node n) const { return Parent::valid(n); }
+
+    /// \brief Arc validity check
+    ///
+    /// This function gives back true if the given arc is valid,
+    /// ie. it is a real arc of the graph.  
+    ///
+    /// \warning A removed arc (using Snapshot) could become valid again
+    /// when new edges are added to the graph.
+    bool valid(Arc a) const { return Parent::valid(a); }
+
+    /// \brief Edge validity check
+    ///
+    /// This function gives back true if the given edge is valid,
+    /// ie. it is a real edge of the graph.  
+    ///
+    /// \warning A removed edge (using Snapshot) could become valid again
+    /// when new edges are added to the graph.
+    bool valid(Edge e) const { return Parent::valid(e); }
 
     ///Clear the graph.
