# HG changeset patch
# User klao
# Date 1098916730 0
# Node ID c94ef40a22ce54a7535456ad38d8026346e1420a
# Parent  f2ea4aac9ada0181dbd64d5ba35fa7e29515287a
The graph_factory branch (@ 1321) has been merged to trunk.

diff -r f2ea4aac9ada -r c94ef40a22ce src/benchmark/hcube.cc
--- a/src/benchmark/hcube.cc	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/benchmark/hcube.cc	Wed Oct 27 22:38:50 2004 +0000
@@ -66,12 +66,15 @@
     for(int i=0;i<dim*(1<<dim);i++) P();
     
     //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
-    Edge te;
-    for(int i=0;i<dim*(1<<dim);i++) {
-      te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
-      //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
-      map[te]=P();
-    }
+
+    ///\todo It must have been commented out because of
+    ///setToId
+//     Edge te;
+//     for(int i=0;i<dim*(1<<dim);i++) {
+//       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
+//       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
+//       map[te]=P();
+//     }
     
 //     for(int i=0;i<(1<<dim);i++) {
 //       int mul= (1<<(numOfZeros(i,dim)/4));
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/Makefile.am
--- a/src/lemon/Makefile.am	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/Makefile.am	Wed Oct 27 22:38:50 2004 +0000
@@ -10,13 +10,12 @@
 	fib_heap.h							\
 	full_graph.h							\
 	graph_wrapper.h							\
+	graph_utils.h							\
 	invalid.h							\
 	kruskal.h							\
 	list_graph.h							\
-	map_defines.h                                                   \
 	map_iterator.h                                                  \
-	map_registry.h                                                  \
-	map_bits.h							\
+	alteration_observer_registry.h                                  \
 	maps.h								\
 	min_cost_flow.h                                                 \
 	suurballe.h                                                     \
@@ -26,10 +25,19 @@
 	time_measure.h							\
 	unionfind.h							\
 	vector_map.h                                                    \
-	xy.h
+	xy.h								\
+	concept_check.h							\
+	map_defines.h							\
+	map_bits.h							\
+	iterable_graph_extender.h					\
+	idmappable_graph_extender.h				   	\
+	extendable_graph_extender.h					\
+	clearable_graph_extender.h					\
+	erasable_graph_extender.h
 
 noinst_HEADERS =							\
 	skeletons/graph.h						\
+	skeletons/graph_component.h					\
 	skeletons/sym_graph.h                                           \
 	skeletons/maps.h                                                \
 	skeletons/path.h
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/alteration_observer_registry.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/alteration_observer_registry.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,339 @@
+/* -*- C++ -*-
+ * src/lemon/observer_registry.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, 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_ALTERATION_OBSERVER_REGISTRY_H
+#define LEMON_ALTERATION_OBSERVER_REGISTRY_H
+
+#include <vector>
+#include <algorithm>
+
+///\ingroup graphmaps
+///\file
+///\brief Observer registry for graph alteration observers.
+
+using namespace std;
+
+namespace lemon {
+
+  /// \addtogroup graphmaps
+  /// @{
+
+  /// Registry class to register objects observes alterations in the graph.
+
+  /// This class is a registry for the objects which observe the
+  /// alterations in a container. The alteration observers can be attached
+  /// to and detached from the registry. The observers have to inherit
+  /// from the \ref AlterationObserverRegistry::ObserverBase and override
+  /// the virtual functions in that.
+  ///
+  /// The most important application of the alteration observing is the
+  /// dynamic map implementation when the observers are observing the
+  /// alterations in the graph.
+  ///
+  /// \param _Item The item type what the observers are observing, usually
+  /// edge or node.
+  ///
+  /// \author Balazs Dezso
+
+  template <typename _Item>
+  class AlterationObserverRegistry {
+  public:
+    typedef _Item Item;
+
+    /// ObserverBase is the base class for the observers.
+	
+    /// ObserverBase is the abstract base class for the observers.
+    /// It will be notified about an item was inserted into or
+    /// erased from the graph.
+    ///
+    /// The observer interface contains some pure virtual functions
+    /// to override. The add() and erase() functions are
+    /// to notify the oberver when one item is added or
+    /// erased.
+    ///
+    /// The build() and clear() members are to notify the observer
+    /// about the container is builded from an empty container or
+    /// is cleared to an empty container. 
+    /// 
+    /// \author Balazs Dezso
+
+    class ObserverBase {
+    protected:
+      typedef AlterationObserverRegistry Registry;
+
+      friend class Registry;
+
+      /// Default constructor.
+
+      /// Default constructor for ObserverBase.
+      /// 
+      ObserverBase() : registry(0) {}
+
+      virtual ~ObserverBase() {}
+
+      /// Attaches the observer into an AlterationObserverRegistry.
+
+      /// This member attaches the observer into an AlterationObserverRegistry.
+      ///
+      void attach(AlterationObserverRegistry& r) {
+	registry = &r;
+	registry->attach(*this);
+      }
+
+      /// Detaches the observer into an AlterationObserverRegistry.
+
+      /// This member detaches the observer from an AlterationObserverRegistry.
+      ///
+      void detach() {
+	if (registry) {
+	  registry->detach(*this);
+	}
+      }
+	
+
+      /// Gives back a pointer to the registry what the map attached into.
+
+      /// This function gives back a pointer to the registry what the map
+      /// attached into.
+      ///
+      Registry* getRegistry() const { return const_cast<Registry*>(registry); }
+      
+      /// Gives back true when the observer is attached into a registry.
+      bool attached() const { return registry != 0; }
+	
+    private:
+
+      ObserverBase(const ObserverBase& copy);
+      ObserverBase& operator=(const ObserverBase& copy);
+
+    protected:
+      
+      Registry* registry;
+      int registry_index;
+
+    public:
+
+      /// \brief The member function to notificate the observer about an
+      /// item is added to the container.
+      ///
+      /// The add() member function notificates the observer about an item
+      /// is added to the container. It have to be overrided in the
+      /// subclasses.
+	
+      virtual void add(const Item&) = 0;	
+
+
+      /// \brief The member function to notificate the observer about an
+      /// item is erased from the container.
+      ///
+      /// The erase() member function notificates the observer about an
+      /// item is erased from the container. It have to be overrided in
+      /// the subclasses.
+	
+      virtual void erase(const Item&) = 0;
+
+      /// \brief The member function to notificate the observer about the
+      /// container is builded.
+      ///
+      /// The build() member function notificates the observer about the
+      /// container is builded from an empty container. It have to be
+      /// overrided in the subclasses.
+
+      virtual void build() = 0;
+
+      /// \brief The member function to notificate the observer about all
+      /// items are erased from the container.
+      ///
+      /// The clear() member function notificates the observer about all
+      /// items are erased from the container. It have to be overrided in
+      /// the subclasses.
+      
+      virtual void clear() = 0;
+
+    };
+	
+  protected:
+	
+
+    typedef std::vector<ObserverBase*> Container; 
+
+    Container container;
+
+		
+  public:
+
+    /// Default constructor.
+	
+    ///
+    /// The default constructor of the AlterationObserverRegistry. 
+    /// It creates an empty registry.
+    AlterationObserverRegistry() {}
+
+    /// Copy Constructor of the AlterationObserverRegistry. 
+	
+    /// Copy constructor of the AlterationObserverRegistry. 
+    /// It creates only an empty registry because the copiable
+    /// registry's observers have to be registered still into that registry.
+    AlterationObserverRegistry(const AlterationObserverRegistry&) {}
+
+    /// Assign operator.
+		
+    /// Assign operator for the AlterationObserverRegistry. 
+    /// It makes the registry only empty because the copiable
+    /// registry's observers have to be registered still into that registry.
+    AlterationObserverRegistry& operator=(const AlterationObserverRegistry&) {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->registry = 0;
+      }
+    }
+
+    /// Destructor.
+				
+    /// Destructor of the AlterationObserverRegistry.
+    ///
+    ~AlterationObserverRegistry() {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->registry = 0;
+      }
+    }
+	
+	
+  protected:
+
+    void attach(ObserverBase& observer) {
+      container.push_back(&observer);
+      observer.registry = this;
+      observer.registry_index = container.size()-1;
+    } 
+
+    void detach(ObserverBase& base) {
+      container.back()->registry_index = base.registry_index; 
+      container[base.registry_index] = container.back();
+      container.pop_back();
+      base.registry = 0;
+    }
+
+  public:
+	
+    /// Notifies all the registered observers about an Item added to the container.
+		
+    /// It notifies all the registered observers about an Item added to the container.
+    /// 
+    void add(const Item& key) {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->add(key);
+      }
+    }	
+
+    /// Notifies all the registered observers about an Item erased from the container.
+		
+    /// It notifies all the registered observers about an Item erased from the container.
+    /// 
+    void erase(const Item& key) {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->erase(key);
+      }
+    }
+    
+
+    /// Notifies all the registered observers about the container is builded.
+		
+    /// Notifies all the registered observers about the container is builded
+    /// from an empty container.
+    void build() {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->build();
+      }
+    }
+
+
+    /// Notifies all the registered observers about all Items are erased.
+
+    /// Notifies all the registered observers about all Items are erased
+    /// from the container.
+    void clear() {
+      typename Container::iterator it;
+      for (it = container.begin(); it != container.end(); ++it) {
+	(*it)->clear();
+      }
+    }
+  };
+
+
+  /// Class to extend a graph functionality with the possibility of alteration observing.
+
+  /// AlterableGraphExtender extends the _Base graphs functionality with the possibility of 
+  /// alteration observing. It defines two observer registrys for the nodes and mapes.
+  ///
+  /// \param _Base is the base class to extend.
+  ///
+  /// \pre _Base is conform to the BaseGraphComponent concept.
+  ///
+  /// \post AlterableGraphExtender<_Base> is conform to the AlterableGraphComponent concept.
+  ///
+  /// \author Balazs Dezso
+
+  template <typename _Base> 
+  class AlterableGraphExtender : public _Base {
+  public:
+
+    typedef AlterableGraphExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    /// The node observer registry.
+    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
+    /// The edge observer registry.
+    typedef AlterationObserverRegistry<Node> NodeObserverRegistry;
+
+
+  protected:
+
+    mutable EdgeObserverRegistry edge_observers;
+
+    mutable NodeObserverRegistry node_observers;
+
+  public:
+
+    EdgeObserverRegistry& getEdgeObserverRegistry() const {
+      return edge_observers;
+    }
+
+    NodeObserverRegistry& getNodeObserverRegistry() const {
+      return node_observers;
+    }
+
+    ~AlterableGraphExtender() {
+      node_observers.clear();
+      edge_observers.clear();
+    }
+    
+  };
+
+  
+/// @}
+  
+
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/array_map.h
--- a/src/lemon/array_map.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/array_map.h	Wed Oct 27 22:38:50 2004 +0000
@@ -20,7 +20,6 @@
 #include <memory>
 
 #include <lemon/map_iterator.h>
-#include <lemon/map_bits.h>
 
 ///\ingroup graphmaps
 ///\file
@@ -42,22 +41,32 @@
    *  will belong to and the ValueType.
    */
 
-  template <typename MapRegistry, typename Value> 
-  class ArrayMap : public MapRegistry::MapBase {
+  template <typename _Graph, 
+	    typename _Item,
+	    typename _ItemIt,
+	    typename _IdMap,
+	    typename _Value>
+  class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
 
-    template <typename MR, typename V> friend class ArrayMap;
-		
   public:
 		
     /// The graph type of the maps. 
-    typedef typename MapRegistry::Graph Graph;
+    typedef _Graph Graph;
     /// The key type of the maps.
-    typedef typename MapRegistry::KeyType KeyType;
+    typedef _Item KeyType;
+
+    typedef AlterationObserverRegistry<_Item> Registry;
+
+  private:
     /// The iterator to iterate on the keys.
-    typedef typename MapRegistry::KeyIt KeyIt;
+    typedef _ItemIt KeyIt;
+
+    typedef _IdMap IdMap;
+
+    typedef _Value Value;
 
     /// The MapBase of the Map which imlements the core regisitry function.
-    typedef typename MapRegistry::MapBase MapBase;
+    typedef typename Registry::ObserverBase Parent;
 		
     
   public:
@@ -77,52 +86,47 @@
     typedef const Value* ConstPointerType;
 
 
+  private:
     typedef std::allocator<Value> Allocator;
 
-	
+
+  public:
+
     /** Graph and Registry initialized map constructor.
      */
-    ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
+    ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {
+      attach(_r);
       allocate_memory();
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+      for (KeyIt it(*graph); it != INVALID; ++it) {
+	int id = IdMap(*graph)[it];
 	allocator.construct(&(values[id]), Value());
       }								
     }
 
-    /** Constructor to use default value to initialize the map. 
-     */
-    ArrayMap(const Graph& g, MapRegistry& r, const Value& v) 
-      : MapBase(g, r) {
+    /// Constructor to use default value to initialize the map. 
+
+    /// It constrates a map and initialize all of the the map. 
+
+    ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {
+      attach(_r);
       allocate_memory();
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
-	allocator.construct(&(values[id]), v);
+      for (KeyIt it(*graph); it != INVALID; ++it) {
+	int id = IdMap(*graph)[it];
+	allocator.construct(&(values[id]), _v);
       }								
     }
 
     /** Constructor to copy a map of the same map type.
      */
-    ArrayMap(const ArrayMap& copy) : MapBase(copy) {
+    ArrayMap(const ArrayMap& copy) {
+      if (copy.attached()) {
+	attach(*copy.getRegistry());
+      }
       capacity = copy.capacity;
       if (capacity == 0) return;
       values = allocator.allocate(capacity);
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
-	allocator.construct(&(values[id]), copy.values[id]);
-      }
-    }
-
-    /** Constructor to copy a map of an other map type.
-     */
-    template <typename TT>
-    ArrayMap(const ArrayMap<MapRegistry, TT>& copy) 
-      : MapBase(copy) {
-      capacity = copy.capacity;
-      if (capacity == 0) return;
-      values = allocator.allocate(capacity);
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+      for (KeyIt it(*graph); it != INVALID; ++it) {
+	int id = IdMap(*graph)[it];
 	allocator.construct(&(values[id]), copy.values[id]);
       }
     }
@@ -132,58 +136,33 @@
     ArrayMap& operator=(const ArrayMap& copy) {
       if (&copy == this) return *this;
       
-      if (MapBase::getGraph() != copy.getGraph()) {
-	if (capacity != 0) {
-	  MapBase::destroy();
-	  allocator.deallocate(values, capacity);
+      if (graph != copy.graph) {
+	if (attached()) {
+	  clear();
+	  detach();
 	}
-
-	MapBase::operator=(copy);
+	if (copy.attached()) {
+	  attach(*copy.getRegistry());
+	}
 	capacity = copy.capacity;
 	if (capacity == 0) return *this;
 	values = allocator.allocate(capacity);      
       }
 
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+      for (KeyIt it(*graph); it != INVALID; ++it) {
+	int id = IdMap(*graph)[it];
 	allocator.construct(&(values[id]), copy.values[id]);
       }
 
       return *this;
     }
 
-    /** Assign operator to copy a map of an other map type.
-     */
-    template <typename TT>
-    ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {
-
-      if (MapBase::getGraph() != copy.getGraph()) {
-	if (capacity != 0) {
-	  MapBase::destroy();
-	  allocator.deallocate(values, capacity);
-	}
-
-	MapBase::operator=(copy);
-
-	capacity = copy.capacity;
-	if (capacity == 0) return *this;
-	values = allocator.allocate(capacity);
-      }
-
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
-	allocator.construct(&(values[id]), copy.values[id]);
-      }
-
-      return *this;
-    }
-				
     /** The destructor of the map.
      */
-    virtual ~ArrayMap() {
-      if (capacity != 0) {
-	MapBase::destroy();
-	allocator.deallocate(values, capacity);
+    virtual ~ArrayMap() {      
+      if (attached()) {
+	clear();
+	detach();
       }
     }
 	
@@ -193,7 +172,7 @@
      * actual keys of the graph. 
      */
     ReferenceType operator[](const KeyType& key) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      int id = IdMap(*graph)[key];
       return values[id];
     } 
 		
@@ -202,7 +181,7 @@
      * actual keys of the graph. 
      */
     ConstReferenceType operator[](const KeyType& key) const {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      int id = IdMap(*graph)[key];
       return values[id];
     }
 	
@@ -210,22 +189,21 @@
      *  This is a compatibility feature with the not dereferable maps.
      */
     void set(const KeyType& key, const ValueType& val) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
-      values[id] = val;
+      (*this)[key] = val;
     }
 		
     /** Add a new key to the map. It called by the map registry.
      */
     void add(const KeyType& key) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      int id = IdMap(*graph)[key];
       if (id >= capacity) {
 	int new_capacity = (capacity == 0 ? 1 : capacity);
 	while (new_capacity <= id) {
 	  new_capacity <<= 1;
 	}
-	Value* new_values = allocator.allocate(new_capacity);;
-	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	  int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	Value* new_values = allocator.allocate(new_capacity);
+	for (KeyIt it(*graph); it != INVALID; ++it) {
+	  int jd = IdMap(*graph)[it];
 	  if (id != jd) {
 	    allocator.construct(&(new_values[jd]), values[jd]);
 	    allocator.destroy(&(values[jd]));
@@ -241,77 +219,86 @@
     /** Erase a key from the map. It called by the map registry.
      */
     void erase(const KeyType& key) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      int id = IdMap(*graph)[key];
       allocator.destroy(&(values[id]));
     }
 
-    /** Clear the data structure.
-     */
+    void build() {
+      allocate_memory();
+      for (KeyIt it(*graph); it != INVALID; ++it) {
+	int id = IdMap(*graph)[it];
+	allocator.construct(&(values[id]), Value());
+      }								
+    }
+
     void clear() {	
       if (capacity != 0) {
-	MapBase::destroy();
+	for (KeyIt it(*graph); it != INVALID; ++it) {
+	  int id = IdMap(*graph)[it];
+	  allocator.destroy(&(values[id]));
+	}								
 	allocator.deallocate(values, capacity);
 	capacity = 0;
       }
     }
 
-    /// The stl compatible pair iterator of the map.
-    typedef MapIterator<ArrayMap> Iterator;
-    /// The stl compatible const pair iterator of the map.
-    typedef MapConstIterator<ArrayMap> ConstIterator;
+//     /// The stl compatible pair iterator of the map.
+//     typedef MapIterator<ArrayMap> Iterator;
+//     /// The stl compatible const pair iterator of the map.
+//     typedef MapConstIterator<ArrayMap> ConstIterator;
 
-    /** Returns the begin iterator of the map.
-     */
-    Iterator begin() {
-      return Iterator(*this, KeyIt(*MapBase::getGraph()));
-    }
+//     /** Returns the begin iterator of the map.
+//      */
+//     Iterator begin() {
+//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
+//     }
 
-    /** Returns the end iterator of the map.
-     */
-    Iterator end() {
-      return Iterator(*this, INVALID);
-    }
+//     /** Returns the end iterator of the map.
+//      */
+//     Iterator end() {
+//       return Iterator(*this, INVALID);
+//     }
 
-    /** Returns the begin ConstIterator of the map.
-     */
-    ConstIterator begin() const {
-      return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
-    }
+//     /** Returns the begin ConstIterator of the map.
+//      */
+//     ConstIterator begin() const {
+//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
+//     }
 
-    /** Returns the end const_iterator of the map.
-     */
-    ConstIterator end() const {
-      return ConstIterator(*this, INVALID);
-    }
+//     /** Returns the end const_iterator of the map.
+//      */
+//     ConstIterator end() const {
+//       return ConstIterator(*this, INVALID);
+//     }
 
-    /// The KeySet of the Map.
-    typedef MapConstKeySet<ArrayMap> ConstKeySet;
+//     /// The KeySet of the Map.
+//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
 
-    /// KeySet getter function.
-    ConstKeySet keySet() const {
-      return ConstKeySet(*this); 
-    }
+//     /// KeySet getter function.
+//     ConstKeySet keySet() const {
+//       return ConstKeySet(*this); 
+//     }
 
-    /// The ConstValueSet of the Map.
-    typedef MapConstValueSet<ArrayMap> ConstValueSet;
+//     /// The ConstValueSet of the Map.
+//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
 
-    /// ConstValueSet getter function.
-    ConstValueSet valueSet() const {
-      return ConstValueSet(*this);
-    }
+//     /// ConstValueSet getter function.
+//     ConstValueSet valueSet() const {
+//       return ConstValueSet(*this);
+//     }
 
-    /// The ValueSet of the Map.
-    typedef MapValueSet<ArrayMap> ValueSet;
+//     /// The ValueSet of the Map.
+//     typedef MapValueSet<ArrayMap> ValueSet;
 
-    /// ValueSet getter function.
-    ValueSet valueSet() {
-      return ValueSet(*this);
-    }
+//     /// ValueSet getter function.
+//     ValueSet valueSet() {
+//       return ValueSet(*this);
+//     }
 
   private:
       
     void allocate_memory() {
-      int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
+      int max_id = IdMap(*graph).maxId();
       if (max_id == -1) {
 	capacity = 0;
 	values = 0;
@@ -324,24 +311,88 @@
       values = allocator.allocate(capacity);	
     }      
 
+    const Graph* graph;
     int capacity;
     Value* values;
     Allocator allocator;
 
   public:
-    // STL  compatibility typedefs.
-    typedef Iterator iterator;
-    typedef ConstIterator const_iterator;
-    typedef typename Iterator::PairValueType value_type;
-    typedef typename Iterator::KeyType key_type;
-    typedef typename Iterator::ValueType data_type;
-    typedef typename Iterator::PairReferenceType reference;
-    typedef typename Iterator::PairPointerType pointer;
-    typedef typename ConstIterator::PairReferenceType const_reference;
-    typedef typename ConstIterator::PairPointerType const_pointer;
-    typedef int difference_type;		
+//     // STL  compatibility typedefs.
+//     typedef Iterator iterator;
+//     typedef ConstIterator const_iterator;
+//     typedef typename Iterator::PairValueType value_type;
+//     typedef typename Iterator::KeyType key_type;
+//     typedef typename Iterator::ValueType data_type;
+//     typedef typename Iterator::PairReferenceType reference;
+//     typedef typename Iterator::PairPointerType pointer;
+//     typedef typename ConstIterator::PairReferenceType const_reference;
+//     typedef typename ConstIterator::PairPointerType const_pointer;
+//     typedef int difference_type;		
   };		
 
+  template <typename _Base> 
+  class ArrayMappableGraphExtender : public _Base {
+  public:
+
+    typedef ArrayMappableGraphExtender<_Base> Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::NodeIt NodeIt;
+    typedef typename Parent::NodeIdMap NodeIdMap;
+    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
+
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::EdgeIt EdgeIt;
+    typedef typename Parent::EdgeIdMap EdgeIdMap;
+    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
+
+    
+
+    template <typename _Value>
+    class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
+    public:
+      typedef ArrayMappableGraphExtender<_Base> Graph;
+
+      typedef typename Graph::Node Node;
+      typedef typename Graph::NodeIt NodeIt;
+      typedef typename Graph::NodeIdMap NodeIdMap;
+
+      typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
+
+      typedef typename Parent::Graph Graph;
+      typedef typename Parent::Value Value;
+
+      NodeMap(const Graph& g) 
+	: Parent(g, g.getNodeObserverRegistry()) {}
+      NodeMap(const Graph& g, const Value& v) 
+	: Parent(g, g.getNodeObserverRegistry(), v) {}
+
+    };
+
+    template <typename _Value>
+    class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
+    public:
+      typedef ArrayMappableGraphExtender<_Base> Graph;
+
+      typedef typename Graph::Edge Edge;
+      typedef typename Graph::EdgeIt EdgeIt;
+      typedef typename Graph::EdgeIdMap EdgeIdMap;
+
+      typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
+
+      typedef typename Parent::Graph Graph;
+      typedef typename Parent::Value Value;
+
+      EdgeMap(const Graph& g) 
+	: Parent(g, g.getEdgeObserverRegistry()) {}
+      EdgeMap(const Graph& g, const Value& v) 
+	: Parent(g, g.getEdgeObserverRegistry(), v) {}
+
+    };
+    
+  };
+
 /// @}
 
 }
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/bfs.h
--- a/src/lemon/bfs.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/bfs.h	Wed Oct 27 22:38:50 2004 +0000
@@ -195,7 +195,7 @@
 	pred_node->set(u,INVALID);
       }
       
-      int N=G->nodeNum();
+      int N = countNodes(*G);
       std::vector<typename Graph::Node> Q(N);
       int Qh=0;
       int Qt=0;
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/clearable_graph_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/clearable_graph_extender.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,28 @@
+// -*- c++ -*-
+
+#ifndef LEMON_CLEARABLE_GRAPH_EXTENDER_H
+#define LEMON_CLEARABLE_GRAPH_EXTENDER_H
+
+#include <lemon/invalid.h>
+
+
+namespace lemon {
+
+  template <typename _Base> 
+  class ClearableGraphExtender : public _Base {
+  public:
+
+    typedef ClearableGraphExtender Graph;
+    typedef _Base Parent;
+
+    void clear() {
+      Parent::getNodeObserverRegistry().clear();
+      Parent::getEdgeObserverRegistry().clear();
+      Parent::clear();
+    }
+
+  };
+
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/concept_check.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/concept_check.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,80 @@
+// -*- C++ -*-
+// Modified for use in LEMON.
+// We should really consider using Boost...
+
+
+//
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// Revision History:
+//   05 May   2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
+//   02 April 2001: Removed limits header altogether. (Jeremy Siek)
+//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
+//
+
+// See http://www.boost.org/libs/concept_check for documentation.
+
+#ifndef LEMON_BOOST_CONCEPT_CHECKS_HPP
+#define LEMON_BOOST_CONCEPT_CHECKS_HPP
+
+namespace lemon {
+
+  /*
+    "inline" is used for ignore_unused_variable_warning()
+    and function_requires() to make sure there is no
+    overhead with g++.
+  */
+
+  template <class T> inline void ignore_unused_variable_warning(const T&) { }
+
+  template <class Concept>
+  inline void function_requires()
+  {
+#if !defined(NDEBUG)
+    void (Concept::*x)() = & Concept::constraints;
+    ignore_unused_variable_warning(x);
+#endif
+  }
+
+#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
+  typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
+  template <func##type_var##concept Tp1_> \
+  struct concept_checking_##type_var##concept { }; \
+  typedef concept_checking_##type_var##concept< \
+    BOOST_FPTR ns::concept<type_var>::constraints> \
+    concept_checking_typedef_##type_var##concept
+
+#define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \
+  typedef void (ns::concept <type_var1,type_var2>::* \
+     func##type_var1##type_var2##concept)(); \
+  template <func##type_var1##type_var2##concept Tp1_> \
+  struct concept_checking_##type_var1##type_var2##concept { }; \
+  typedef concept_checking_##type_var1##type_var2##concept< \
+    BOOST_FPTR ns::concept<type_var1,type_var2>::constraints> \
+    concept_checking_typedef_##type_var1##type_var2##concept
+
+#define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \
+  typedef void (ns::concept <tv1,tv2,tv3>::* \
+     func##tv1##tv2##tv3##concept)(); \
+  template <func##tv1##tv2##tv3##concept Tp1_> \
+  struct concept_checking_##tv1##tv2##tv3##concept { }; \
+  typedef concept_checking_##tv1##tv2##tv3##concept< \
+    BOOST_FPTR ns::concept<tv1,tv2,tv3>::constraints> \
+    concept_checking_typedef_##tv1##tv2##tv3##concept
+
+#define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \
+  typedef void (ns::concept <tv1,tv2,tv3,tv4>::* \
+     func##tv1##tv2##tv3##tv4##concept)(); \
+  template <func##tv1##tv2##tv3##tv4##concept Tp1_> \
+  struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \
+  typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \
+    BOOST_FPTR ns::concept<tv1,tv2,tv3,tv4>::constraints> \
+    concept_checking_typedef_##tv1##tv2##tv3##tv4##concept
+
+
+} // namespace lemon
+
+#endif // LEMON_BOOST_CONCEPT_CHECKS_HPP
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/default_map.h
--- a/src/lemon/default_map.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/default_map.h	Wed Oct 27 22:38:50 2004 +0000
@@ -23,7 +23,7 @@
 
 ///\ingroup graphmaps
 ///\file
-///\brief Graph maps that construates and destruates
+///\brief Graph maps that construct and destruct
 ///their elements dynamically.
 
 namespace lemon {
@@ -41,100 +41,185 @@
    */
 
 
-  /** Macro to implement the DefaultMap.
-   */
-#define DEFAULT_MAP_BODY(DynMap, Value) \
-{ \
-\
-public: \
-\
-typedef DynMap<MapRegistry, Value> Parent; \
-\
-typedef typename MapRegistry::Graph Graph; \
-\
-DefaultMap(const Graph& g, MapRegistry& r) : Parent(g, r) {} \
-DefaultMap(const Graph& g, MapRegistry& r, const Value& v) \
-  : Parent(g, r, v) {} \
-DefaultMap(const DefaultMap& copy) \
-  : Parent(static_cast<const Parent&>(copy)) {} \
-template <typename TT> \
-DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \
-  : Parent(*copy.getGraph()) { \
-  if (Parent::getGraph()) { \
-    for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
-      Parent::operator[](it) = copy[it]; \
-    } \
-  } \
-} \
-DefaultMap& operator=(const DefaultMap& copy) { \
-  Parent::operator=(static_cast<const Parent&>(copy)); \
-  return *this; \
-} \
-template <typename TT> \
-DefaultMap& operator=(const DefaultMap<MapRegistry, TT>& copy) { \
-  if (Parent::getGraph() != copy.getGraph()) { \
-    Parent::clear(); \
-    Parent::MapBase::operator=(copy); \
-    Parent::construct(); \
-  } \
-  if (Parent::getGraph()) { \
-    for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
-      Parent::operator[](it) = copy[it]; \
-    } \
-  } \
-  return *this; \
-} \
-};
 
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap, typename _Value>
+  struct DefaultMapSelector {
+    typedef ArrayMap<_Graph, _Item, _ItemIt, _IdMap, _Value> Map;
+  };
 
-  template <typename MapRegistry, typename Type>
-  class DefaultMap : public ArrayMap<MapRegistry, Type> 
-  DEFAULT_MAP_BODY(ArrayMap, Type);
+  // bool
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, bool> {
+    typedef VectorMap<_Graph, _Item, _IdMap, bool> Map;
+  };
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, bool> 
-    : public VectorMap<MapRegistry, bool> 
-  DEFAULT_MAP_BODY(VectorMap, bool);
+  // char
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, char> {
+    typedef VectorMap<_Graph, _Item, _IdMap, char> Map;
+  };
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, char> 
-    : public VectorMap<MapRegistry, char> 
-  DEFAULT_MAP_BODY(VectorMap, char);
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed char> {
+    typedef VectorMap<_Graph, _Item, _IdMap, signed char> Map;
+  };
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, int> 
-    : public VectorMap<MapRegistry, int> 
-  DEFAULT_MAP_BODY(VectorMap, int);
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned char> {
+    typedef VectorMap<_Graph, _Item, _IdMap, unsigned char> Map;
+  };
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, short> 
-    : public VectorMap<MapRegistry, short> 
-  DEFAULT_MAP_BODY(VectorMap, short);
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, long> 
-    : public VectorMap<MapRegistry, long> 
-  DEFAULT_MAP_BODY(VectorMap, long);
+  // int
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed int> {
+    typedef VectorMap<_Graph, _Item, _IdMap, signed int> Map;
+  };
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, float> 
-    : public VectorMap<MapRegistry, float> 
-  DEFAULT_MAP_BODY(VectorMap, float);
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned int> {
+    typedef VectorMap<_Graph, _Item, _IdMap, unsigned int> Map;
+  };
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, double> 
-    : public VectorMap<MapRegistry, double> 
-  DEFAULT_MAP_BODY(VectorMap, double);
 
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, long double> 
-    : public VectorMap<MapRegistry, long double> 
-  DEFAULT_MAP_BODY(VectorMap, long double);
+  // short
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed short> {
+    typedef VectorMap<_Graph, _Item, _IdMap, signed short> Map;
+  };
 
-  template <typename MapRegistry, typename Type>
-  class DefaultMap<MapRegistry, Type*>
-    : public VectorMap<MapRegistry, Type*> 
-  DEFAULT_MAP_BODY(VectorMap, Type*);
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned short> {
+    typedef VectorMap<_Graph, _Item, _IdMap, unsigned short> Map;
+  };
+
+
+  // long
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed long> {
+    typedef VectorMap<_Graph, _Item, _IdMap, signed long> Map;
+  };
+
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned long> {
+    typedef VectorMap<_Graph, _Item, _IdMap, unsigned long> Map;
+  };
+
+  // \todo handling long long type
+
+
+  // float
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, float> {
+    typedef VectorMap<_Graph, _Item, _IdMap, float> Map;
+  };
+
+
+  // double
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, double> {
+    typedef VectorMap<_Graph, _Item, _IdMap,  double> Map;
+  };
+
+
+  // long double
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, long double> {
+    typedef VectorMap<_Graph, _Item, _IdMap, long double> Map;
+  };
+
+
+  // pointer
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap, typename _Ptr>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Ptr*> {
+    typedef VectorMap<_Graph, _Item, _IdMap, _Ptr*> Map;
+  };
+
+
+
+  template <typename _Graph, 
+	    typename _Item,
+	    typename _ItemIt,
+	    typename _IdMap,
+	    typename _Value>
+  class DefaultMap : public DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map {
+  public:
+    typedef typename DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map Parent;
+    typedef DefaultMap<_Graph, _Item, _ItemIt, _IdMap, bool> Map;
+    
+    typedef typename Parent::Graph Graph;
+    typedef typename Parent::Registry Registry;
+    typedef typename Parent::ValueType ValueType;
+
+    DefaultMap(const Graph& _g, Registry& _r) : Parent(_g, _r) {}
+    DefaultMap(const Graph& _g, Registry& _r, const ValueType& _v) : Parent(_g, _r, _v) {}
+  };
+
+
+
+  template <typename _Base> 
+  class DefaultMappableGraphExtender : public _Base {
+  public:
+
+    typedef DefaultMappableGraphExtender<_Base> Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::NodeIt NodeIt;
+    typedef typename Parent::NodeIdMap NodeIdMap;
+    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
+
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::EdgeIt EdgeIt;
+    typedef typename Parent::EdgeIdMap EdgeIdMap;
+    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
+
+    
+
+    template <typename _Value>
+    class NodeMap : public DefaultMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
+    public:
+      typedef DefaultMappableGraphExtender<_Base> Graph;
+
+      typedef typename Graph::Node Node;
+      typedef typename Graph::NodeIt NodeIt;
+      typedef typename Graph::NodeIdMap NodeIdMap;
+
+      typedef DefaultMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
+
+      typedef typename Parent::Graph Graph;
+      typedef typename Parent::ValueType ValueType;
+
+      NodeMap(const Graph& g) 
+	: Parent(g, g.getNodeObserverRegistry()) {}
+      NodeMap(const Graph& g, const ValueType& v) 
+	: Parent(g, g.getNodeObserverRegistry(), v) {}
+
+    };
+
+    template <typename _Value>
+    class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
+    public:
+      typedef DefaultMappableGraphExtender<_Base> Graph;
+
+      typedef typename Graph::Edge Edge;
+      typedef typename Graph::EdgeIt EdgeIt;
+      typedef typename Graph::EdgeIdMap EdgeIdMap;
+
+      typedef DefaultMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
+
+      typedef typename Parent::Graph Graph;
+      typedef typename Parent::ValueType ValueType;
+
+      EdgeMap(const Graph& g) 
+	: Parent(g, g.getEdgeObserverRegistry()) {}
+      EdgeMap(const Graph& g, const ValueType& v) 
+	: Parent(g, g.getEdgeObserverRegistry(), v) {}
+
+    };
+    
+  };
+
 
 }
 
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/dfs.h
--- a/src/lemon/dfs.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/dfs.h	Wed Oct 27 22:38:50 2004 +0000
@@ -23,7 +23,7 @@
 ///
 ///\todo Revise Manual.
 
-#include <lemon/bin_heap.h>
+#include <lemon/graph_utils.h>
 #include <lemon/invalid.h>
 
 namespace lemon {
@@ -193,12 +193,12 @@
 	pred_node->set(u,INVALID);
       }
       
-      int N=G->nodeNum();
+      int N = countNodes(*G);
       std::vector<typename Graph::OutEdgeIt> Q(N);
 
       int Qh=0;
       
-      G->first(Q[Qh],s);
+      Q[Qh] = OutEdgeIt(*G, s);
       distance->set(s, 0);
 
       Node n=s;
@@ -209,7 +209,7 @@
 	  if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) {
 	    predecessor->set(m,e);
 	    pred_node->set(m,n);
-	    G->first(Q[++Qh],m);
+	    Q[++Qh] = OutEdgeIt(*G, m);
 	    distance->set(m,Qh);
 	    n=m;
 	  }
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/erasable_graph_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/erasable_graph_extender.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,48 @@
+// -*- c++ -*-
+
+#ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H
+#define LEMON_ERASABLE_GRAPH_EXTENDER_H
+
+#include <lemon/invalid.h>
+
+
+namespace lemon {
+
+  template <typename _Base> 
+  class ErasableGraphExtender : public _Base {
+  public:
+
+    typedef ErasableGraphExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    void erase(const Node& node) {
+      Edge edge;
+      Parent::firstOut(edge, node);
+      while (edge != INVALID ) {
+	erase(edge);
+	Parent::firstOut(edge, node);
+      } 
+
+      Parent::firstIn(edge, node);
+      while (edge != INVALID ) {
+	erase(edge);
+	Parent::firstIn(edge, node);
+      }
+
+      Parent::getNodeObserverRegistry().erase(node);
+      Parent::erase(node);
+    }
+    
+    void erase(const Edge& edge) {
+      Parent::getEdgeObserverRegistry().erase(edge);
+      Parent::erase(edge);
+    }
+
+  };
+
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/extendable_graph_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/extendable_graph_extender.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,34 @@
+// -*- c++ -*-
+
+#ifndef LEMON_EXTENDABLE_GRAPH_EXTENDER_H
+#define LEMON_EXTENDABLE_GRAPH_EXTENDER_H
+
+namespace lemon {
+
+  template <typename _Base> 
+  class ExtendableGraphExtender : public _Base {
+  public:
+
+    typedef ExtendableGraphExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    Node addNode() {
+      Node node = Parent::addNode();
+      Parent::getNodeObserverRegistry().add(node);
+      return node;
+    }
+    
+    Edge addEdge(const Node& from, const Node& to) {
+      Edge edge = Parent::addEdge(from, to);
+      Parent::getEdgeObserverRegistry().add(edge);
+      return edge;
+    }
+
+  };
+
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/full_graph.h
--- a/src/lemon/full_graph.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/full_graph.h	Wed Oct 27 22:38:50 2004 +0000
@@ -17,20 +17,21 @@
 #ifndef LEMON_FULL_GRAPH_H
 #define LEMON_FULL_GRAPH_H
 
+
+#include <lemon/idmappable_graph_extender.h>
+
+#include <lemon/iterable_graph_extender.h>
+
+#include <lemon/alteration_observer_registry.h>
+#include <lemon/default_map.h>
+
 ///\ingroup graphs
 ///\file
 ///\brief FullGraph and SymFullGraph classes.
 
-#include <vector>
-#include <climits>
 
 #include <lemon/invalid.h>
 
-#include <lemon/map_registry.h>
-#include <lemon/array_map.h>
-
-#include <lemon/map_defines.h>
-
 namespace lemon {
 
 /// \addtogroup graphs
@@ -48,34 +49,26 @@
   ///\todo Don't we need SymEdgeMap?
   ///
   ///\author Alpar Juttner
-  class FullGraph {
+  class FullGraphBase {
     int NodeNum;
     int EdgeNum;
   public:
 
-    typedef FullGraph Graph;
+    typedef FullGraphBase Graph;
 
     class Node;
     class Edge;
 
-    class NodeIt;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-    
-
-    // Create map registries.
-    CREATE_MAP_REGISTRIES;
-    // Create node and edge maps.
-    CREATE_MAPS(ArrayMap);
-    
   public:
 
+    FullGraphBase() {}
+
+
     ///Creates a full graph with \c n nodes.
-    FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
+    void construct(int n) { NodeNum = n; EdgeNum = n * n; }
     ///
-    FullGraph(const FullGraph &_g)
-      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
+    //    FullGraphBase(const FullGraphBase &_g)
+    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
     
     ///Number of nodes.
     int nodeNum() const { return NodeNum; }
@@ -93,17 +86,9 @@
     ///\sa id(Edge)
     int maxEdgeId() const { return EdgeNum-1; }
 
-    Node tail(Edge e) const { return e.n%NodeNum; }
-    Node head(Edge e) const { return e.n/NodeNum; }
+    Node tail(Edge e) const { return e.id % NodeNum; }
+    Node head(Edge e) const { return e.id / NodeNum; }
 
-    NodeIt& first(NodeIt& v) const {
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
 
     /// Node ID.
     
@@ -113,7 +98,8 @@
     ///
     /// The ID of the \ref INVALID node is -1.
     ///\return The ID of the node \c v. 
-    static int id(Node v) { return v.n; }
+
+    static int id(Node v) { return v.id; }
     /// Edge ID.
     
     /// The ID of a valid Edge is a nonnegative integer not greater than
@@ -122,7 +108,7 @@
     ///
     /// The ID of the \ref INVALID edge is -1.
     ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.n; }
+    static int id(Edge e) { return e.id; }
 
     /// Finds an edge between two nodes.
     
@@ -134,110 +120,102 @@
     /// \return The found edge or INVALID if there is no such an edge.
     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
     {
-      return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
+      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
     }
     
       
     class Node {
-      friend class FullGraph;
-      template <typename T> friend class NodeMap;
-
-      friend class Edge;
-      friend class OutEdgeIt;
-      friend class InEdgeIt;
-      friend class SymEdge;
+      friend class FullGraphBase;
 
     protected:
-      int n;
-      friend int FullGraph::id(Node v); 
-      Node(int nn) {n=nn;}
+      int id;
+      Node(int _id) { id = _id;}
     public:
       Node() {}
-      Node (Invalid) { n=-1; }
-      bool operator==(const Node i) const {return n==i.n;}
-      bool operator!=(const Node i) const {return n!=i.n;}
-      bool operator<(const Node i) const {return n<i.n;}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node node) const {return id == node.id;}
+      bool operator!=(const Node node) const {return id != node.id;}
+      bool operator<(const Node node) const {return id < node.id;}
     };
     
-    class NodeIt : public Node {
-      const FullGraph *G;
-      friend class FullGraph;
+
+
+    class Edge {
+      friend class FullGraphBase;
+      
+    protected:
+      int id;  // NodeNum * head + tail;
+
+      Edge(int _id) : id(_id) {}
+
+      Edge(const FullGraphBase& _graph, int tail, int head) 
+	: id(_graph.NodeNum * head+tail) {}
     public:
-      NodeIt() : Node() { }
-      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
-      NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
-      ///\todo Undocumented conversion Node -\> NodeIt.
-      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
+      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;}
     };
 
-    class Edge {
-      friend class FullGraph;
-      template <typename T> friend class EdgeMap;
-      
-      friend class Node;
-      friend class NodeIt;
-    protected:
-      int n; //NodeNum*head+tail;
-      friend int FullGraph::id(Edge e);
+    void first(Node& node) const {
+      node.id = NodeNum-1;
+    }
 
-      Edge(int nn) : n(nn) {}
-      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
-    public:
-      Edge() { }
-      Edge (Invalid) { n=-1; }
-      bool operator==(const Edge i) const {return n==i.n;}
-      bool operator!=(const Edge i) const {return n!=i.n;}
-      bool operator<(const Edge i) const {return n<i.n;}
-      ///\bug This is a workaround until somebody tells me how to
-      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
-      int &idref() {return n;}
-      const int &idref() const {return n;}
-    };
+    static void next(Node& node) {
+      --node.id;
+    }
+
+    void first(Edge& edge) const {
+      edge.id = EdgeNum-1;
+    }
+
+    static void next(Edge& edge) {
+      --edge.id;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge.id = EdgeNum + node.id - NodeNum;
+    }
+
+    void nextOut(Edge& edge) const {
+      edge.id -= NodeNum;
+      if (edge.id < 0) edge.id = -1;
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge.id = node.id * NodeNum;
+    }
     
-    class EdgeIt : public Edge {
-      friend class FullGraph;
-    public:
-      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
-      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
-      EdgeIt (Invalid i) : Edge(i) { }
-      EdgeIt() : Edge() { }
-      EdgeIt& operator++() { --n; return *this; }
-
-      ///\bug This is a workaround until somebody tells me how to
-      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
-      int &idref() {return n;}
-    };
-    
-    class OutEdgeIt : public Edge {
-      const FullGraph *G;
-      friend class FullGraph;
-    public: 
-      OutEdgeIt() : Edge() { }
-      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      OutEdgeIt (Invalid i) : Edge(i) { }
-
-      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
-      
-      OutEdgeIt& operator++()
-      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
-
-    };
-    
-    class InEdgeIt : public Edge {
-      const FullGraph *G;
-      friend class FullGraph;
-    public: 
-      InEdgeIt() : Edge() { }
-      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
-      InEdgeIt& operator++()
-      { if(!((++n)%G->NodeNum)) n=-1; return *this; }
-    };
+    void nextIn(Edge& edge) const {
+      ++edge.id;
+      if (edge.id % NodeNum == 0) edge.id = -1;
+    }
 
   };
 
+
+  typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
+  typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
+  typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase;
+  typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase;
+
+  class FullGraph : public MappableFullGraphBase {
+  public:
+
+    FullGraph(int n) { construct(n); }
+  };
+
+  template <>
+  int countNodes<FullGraph>(const FullGraph& graph) {
+    return graph.nodeNum();
+  }
+
+  template <>
+  int countEdges<FullGraph>(const FullGraph& graph) {
+    return graph.edgeNum();
+  }
+
   /// @}  
 
 } //namespace lemon
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/graph_utils.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/graph_utils.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,174 @@
+/* -*- C++ -*-
+ * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, 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_GRAPH_UTILS_H
+#define LEMON_GRAPH_UTILS_H
+
+#include <iterator>
+
+#include <lemon/invalid.h>
+
+///\ingroup utils
+///\file
+///\brief Graph utils.
+///
+
+
+namespace lemon {
+
+  // counters in the graph
+  /// \brief Function to count the items in the graph.
+  ///
+  /// This function counts the items in the graph.
+  /// The complexity of the function is O(n) because
+  /// it iterates on all of the items.
+
+  template <typename Graph, typename ItemIt>
+  inline int countItems(const Graph& _g) {
+    int num = 0;
+    for (ItemIt it(_g); it != INVALID; ++it) {
+      ++num;
+    }
+    return num;
+  }
+
+  /// \brief Function to count the nodes in the graph.
+  ///
+  /// This function counts the nodes in the graph.
+  /// The complexity of the function is O(n) but for some
+  /// graph structure it is specialized to O(1).
+
+  template <typename Graph>
+  inline int countNodes(const Graph& _g) {
+    return countItems<Graph, typename Graph::NodeIt>(_g);
+  }
+
+  /// \brief Function to count the edges in the graph.
+  ///
+  /// This function counts the edges in the graph.
+  /// The complexity of the function is O(e) but for some
+  /// graph structure it is specialized to O(1).
+  template <typename Graph>
+  inline int countEdges(const Graph& _g) {
+    return countItems<Graph, typename Graph::EdgeIt>(_g);
+  }
+
+  /// \brief Function to count the symmetric edges in the graph.
+  ///
+  /// This function counts the symmetric edges in the graph.
+  /// The complexity of the function is O(e) but for some
+  /// graph structure it is specialized to O(1).
+  template <typename Graph>
+  inline int countSymEdges(const Graph& _g) {
+    return countItems<Graph, typename Graph::SymEdgeIt>(_g);
+  }
+
+  template <typename Graph, typename DegIt>
+  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
+    int num = 0;
+    for (DegIt it(_g, _n); it != INVALID; ++it) {
+      ++num;
+    }
+    return num;
+  }
+
+  template <typename Graph>
+  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
+    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
+  }
+
+  template <typename Graph>
+  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
+    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
+  }
+
+  // graph copy
+
+  template <
+    typename DestinationGraph, 
+    typename SourceGraph, 
+    typename NodeBijection>
+  void copyNodes(DestinationGraph& _d, const SourceGraph& _s, 
+		 NodeBijection& _nb) {    
+    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
+      _nb[it] = _d.addNode();
+    }
+  }
+
+  template <
+    typename DestinationGraph, 
+    typename SourceGraph, 
+    typename NodeBijection,
+    typename EdgeBijection>
+  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
+		 const NodeBijection& _nb, EdgeBijection& _eb) {    
+    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
+      _eb[it] = _d.addEdge(_nb[_s.tail(it)], _nb[_s.head(it)]);
+    }
+  }
+
+  template <
+    typename DestinationGraph, 
+    typename SourceGraph, 
+    typename NodeBijection,
+    typename EdgeBijection>
+  void copyGraph(DestinationGraph& _d, const SourceGraph& _s, 
+		 NodeBijection& _nb, EdgeBijection& _eb) {
+    nodeCopy(_d, _s, _nb);
+    edgeCopy(_d, _s, _nb, _eb);
+  }
+ 
+   template <
+    typename _DestinationGraph, 
+    typename _SourceGraph, 
+    typename _NodeBijection 
+    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
+    typename _EdgeBijection 
+    =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
+   >
+   class GraphCopy {
+   public:
+
+     typedef _DestinationGraph DestinationGraph;
+     typedef _SourceGraph SourceGraph;
+
+     typedef _NodeBijection NodeBijection;
+     typedef _EdgeBijection EdgeBijection;
+
+   protected:          
+
+     NodeBijection node_bijection;
+     EdgeBijection edge_bijection;     
+
+   public:
+     
+     GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
+       copyGraph(_d, _s, node_bijection, edge_bijection);
+     }
+
+     const NodeBijection& getNodeBijection() const {
+       return node_bijection;
+     }
+
+     const EdgeBijection& getEdgeBijection() const {
+       return edge_bijection;
+     }
+     
+   };
+		   		  		 		
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/idmappable_graph_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/idmappable_graph_extender.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,52 @@
+// -*- c++ -*-
+
+#ifndef LEMON_IDMAPPABLE_GRAPH_EXTENDER_H
+#define LEMON_IDMAPPABLE_GRAPH_EXTENDER_H
+
+
+namespace lemon {
+
+  template <typename Base> 
+  class IdMappableGraphExtender : public Base {
+  public:
+
+    typedef IdMappableGraphExtender Graph;
+    typedef Base Parent;
+ 
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+
+  public:
+
+    class NodeIdMap {
+    private:
+      const Graph* graph;
+
+    public:
+      NodeIdMap(const Graph& g) : graph(&g) {}
+
+      int operator[](const Node& node) const { return graph->id(node); }
+
+      int maxId() const {return graph->maxNodeId(); }
+
+    };
+
+    class EdgeIdMap {
+    private:
+      const Graph* graph;
+
+    public:
+      EdgeIdMap(const Graph& g) : graph(&g) {}
+
+      int operator[](const Edge& edge) const { return graph->id(edge); }
+
+      int maxId() const {return graph->maxEdgeId(); }
+
+    };
+
+  };
+
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/iterable_graph_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/iterable_graph_extender.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,131 @@
+// -*- c++ -*-
+#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
+#define LEMON_ITERABLE_GRAPH_EXTENDER_H
+
+#include <lemon/invalid.h>
+
+namespace lemon {
+  
+  template <typename _Base>
+  class IterableGraphExtender : public _Base {
+
+    typedef _Base Parent;
+    typedef IterableGraphExtender<_Base> Graph;
+
+  public:
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+
+    class NodeIt : public Node { 
+      const Graph* graph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Graph& _graph) : Node(), graph(&_graph) {
+	_graph.first(*static_cast<Node*>(this));
+      }
+
+      NodeIt(const Graph& _graph, const Node& node) 
+	: Node(node), graph(&_graph) {}
+
+      NodeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class EdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const Graph& _graph) : Edge(), graph(&_graph) {
+	_graph.first(*static_cast<Edge*>(this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& e) : 
+	Edge(e), graph(&_graph) { }
+
+      EdgeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class OutEdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      OutEdgeIt() { }
+
+      OutEdgeIt(Invalid i) : Edge(i) { }
+
+      OutEdgeIt(const Graph& _graph, const Node& node) 
+	: Edge(), graph(&_graph) {
+	_graph.firstOut(*this, node);
+      }
+
+      OutEdgeIt(const Graph& _graph, const Edge& edge) 
+	: Edge(edge), graph(&_graph) {}
+
+      OutEdgeIt& operator++() { 
+	graph->nextOut(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class InEdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      InEdgeIt() { }
+
+      InEdgeIt(Invalid i) : Edge(i) { }
+
+      InEdgeIt(const Graph& _graph, const Node& node) 
+	: Edge(), graph(&_graph) {
+	_graph.firstIn(*this, node);
+      }
+
+      InEdgeIt(const Graph& _graph, const Edge& edge) : 
+	Edge(edge), graph(&_graph) {}
+
+      InEdgeIt& operator++() { 
+	graph->nextIn(*this);
+	return *this; 
+      }
+
+    };
+
+    using Parent::first;
+
+  private:
+
+    /// \todo When (and if) we change the iterators concept to use operator*,
+    /// then the following shadowed methods will become superfluous.
+    /// But for now these are important safety measures.
+
+    void first(NodeIt &) const;
+    void first(EdgeIt &) const;
+    void first(OutEdgeIt &) const;
+    void first(InEdgeIt &) const;
+
+  };
+  
+}
+
+#endif // LEMON_GRAPH_EXTENDER_H
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/list_graph.h
--- a/src/lemon/list_graph.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/list_graph.h	Wed Oct 27 22:38:50 2004 +0000
@@ -1,117 +1,87 @@
-/* -*- C++ -*-
- * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Combinatorial Optimization Research Group, 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.
- *
- */
+// -*- c++ -*-
 
 #ifndef LEMON_LIST_GRAPH_H
 #define LEMON_LIST_GRAPH_H
 
-///\ingroup graphs
-///\file
-///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
+#include <lemon/erasable_graph_extender.h>
+#include <lemon/clearable_graph_extender.h>
+#include <lemon/extendable_graph_extender.h>
 
-#include <vector>
-#include <climits>
+#include <lemon/idmappable_graph_extender.h>
 
-#include <lemon/invalid.h>
+#include <lemon/iterable_graph_extender.h>
 
-#include <lemon/map_registry.h>
-#include <lemon/array_map.h>
+#include <lemon/alteration_observer_registry.h>
 
-#include <lemon/map_defines.h>
+#include <lemon/default_map.h>
 
 
 namespace lemon {
 
-/// \addtogroup graphs
-/// @{
+  class ListGraphBase {
 
-  ///A list graph class.
-
-  ///This is a simple and fast erasable graph implementation.
-  ///
-  ///It conforms to the
-  ///\ref skeleton::ErasableGraph "ErasableGraph" concept.
-  ///\sa skeleton::ErasableGraph.
-  class ListGraph {
-
-    //Nodes are double linked.
-    //The free nodes are only single linked using the "next" field.
-    struct NodeT 
-    {
+    struct NodeT {
       int first_in,first_out;
       int prev, next;
     };
-    //Edges are double linked.
-    //The free edges are only single linked using the "next_in" field.
-    struct EdgeT 
-    {
+ 
+    struct EdgeT {
       int head, tail;
       int prev_in, prev_out;
       int next_in, next_out;
     };
 
     std::vector<NodeT> nodes;
-    //The first node
+
     int first_node;
-    //The first free node
+
     int first_free_node;
+
     std::vector<EdgeT> edges;
-    //The first free edge
+
     int first_free_edge;
     
   public:
     
-    typedef ListGraph Graph;
+    typedef ListGraphBase Graph;
     
-    class Node;
-    class Edge;
+    class Node {
+      friend class Graph;
+    protected:
 
-    
-  public:
+      int id;
+      Node(int pid) { id = pid;}
 
-    class NodeIt;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node& node) const {return id == node.id;}
+      bool operator!=(const Node& node) const {return id != node.id;}
+      bool operator<(const Node& node) const {return id < node.id;}
+    };
 
-    // Create map registries.
-    CREATE_MAP_REGISTRIES;
-    // Create node and edge maps.
-    CREATE_MAPS(ArrayMap);
+    class Edge {
+      friend class Graph;
+    protected:
 
-  public:
+      int id;
+      Edge(int pid) { id = pid;}
 
-    ListGraph() 
+    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;}
+    };
+
+
+
+    ListGraphBase()
       : nodes(), first_node(-1),
 	first_free_node(-1), edges(), first_free_edge(-1) {}
 
-    ListGraph(const ListGraph &_g) 
-      : nodes(_g.nodes), first_node(_g.first_node),
-	first_free_node(_g.first_free_node), edges(_g.edges),
-	first_free_edge(_g.first_free_edge) {}
     
-    /// \bug In the vector can be hole if a node is erased from the graph.
-    ///Number of nodes.
-    int nodeNum() const { return nodes.size(); }
-    ///Number of edges.
-    int edgeNum() const { return edges.size(); }
-
-    ///Set the expected maximum number of edges.
-
-    ///With this function, it is possible to set the expected number of edges.
-    ///The use of this fasten the building of the graph and makes
     ///it possible to avoid the superfluous memory allocation.
     void reserveEdge(int n) { edges.reserve(n); };
     
@@ -120,56 +90,75 @@
     /// Maximum node ID.
     ///\sa id(Node)
     int maxNodeId() const { return nodes.size()-1; } 
+
     /// Maximum edge ID.
     
     /// Maximum edge ID.
     ///\sa id(Edge)
     int maxEdgeId() const { return edges.size()-1; }
 
-    Node tail(Edge e) const { return edges[e.n].tail; }
-    Node head(Edge e) const { return edges[e.n].head; }
+    Node tail(Edge e) const { return edges[e.id].tail; }
+    Node head(Edge e) const { return edges[e.id].head; }
 
-    NodeIt& first(NodeIt& v) const { 
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
 
-    /// Node ID.
+    void first(Node& node) const { 
+      node.id = first_node;
+    }
+
+    void next(Node& node) const {
+      node.id = nodes[node.id].next;
+    }
+
+
+    void first(Edge& e) const { 
+      int n;
+      for(n = first_node; 
+	  n!=-1 && nodes[n].first_in == -1; 
+	  n = nodes[n].next);
+      e.id = (n == -1) ? -1 : nodes[n].first_in;
+    }
+
+    void next(Edge& edge) const {
+      if (edges[edge.id].next_in != -1) {
+	edge.id = edges[edge.id].next_in;
+      } else {
+	int n;
+	for(n = nodes[edges[edge.id].head].next;
+	  n!=-1 && nodes[n].first_in == -1; 
+	  n = nodes[n].next);
+	edge.id = (n == -1) ? -1 : nodes[n].first_in;
+      }      
+    }
+
+    void firstOut(Edge &e, const Node& v) const {
+      e.id = nodes[v.id].first_out;
+    }
+    void nextOut(Edge &e) const {
+      e.id=edges[e.id].next_out;
+    }
+
+    void firstIn(Edge &e, const Node& v) const {
+      e.id = nodes[v.id].first_in;
+    }
+    void nextIn(Edge &e) const {
+      e.id=edges[e.id].next_in;
+    }
+
     
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    ///\return The ID of the node \c v. 
-    static int id(Node v) { return v.n; }
-    /// Edge ID.
-    
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.n; }
+    static int id(Node v) { return v.id; }
+    static int id(Edge e) { return e.id; }
 
     /// Adds a new node to the graph.
 
     /// \warning It adds the new node to the front of the list.
     /// (i.e. the lastly added node becomes the first.)
-    Node addNode() {
+    Node addNode() {     
       int n;
       
-      if(first_free_node==-1)
-	{
-	  n = nodes.size();
-	  nodes.push_back(NodeT());
-	}
-      else {
+      if(first_free_node==-1) {
+	n = nodes.size();
+	nodes.push_back(NodeT());
+      } else {
 	n = first_free_node;
 	first_free_node = nodes[n].next;
       }
@@ -181,1319 +170,108 @@
       
       nodes[n].first_in = nodes[n].first_out = -1;
       
-      Node nn; nn.n=n;
-
-      //Update dynamic maps
-      node_maps.add(nn);
-
-      return nn;
+      return Node(n);
     }
     
     Edge addEdge(Node u, Node v) {
-      int n;
-      
-      if(first_free_edge==-1)
-	{
-	  n = edges.size();
-	  edges.push_back(EdgeT());
-	}
-      else {
+      int n;      
+
+      if (first_free_edge == -1) {
+	n = edges.size();
+	edges.push_back(EdgeT());
+      } else {
 	n = first_free_edge;
 	first_free_edge = edges[n].next_in;
       }
       
-      edges[n].tail = u.n; edges[n].head = v.n;
+      edges[n].tail = u.id; 
+      edges[n].head = v.id;
 
-      edges[n].next_out = nodes[u.n].first_out;
-      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
-      edges[n].next_in = nodes[v.n].first_in;
-      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
+      edges[n].next_out = nodes[u.id].first_out;
+      if(nodes[u.id].first_out != -1) {
+	edges[nodes[u.id].first_out].prev_out = n;
+      }
+      
+      edges[n].next_in = nodes[v.id].first_in;
+      if(nodes[v.id].first_in != -1) {
+	edges[nodes[v.id].first_in].prev_in = n;
+      }
+      
       edges[n].prev_in = edges[n].prev_out = -1;
 	
-      nodes[u.n].first_out = nodes[v.n].first_in = n;
+      nodes[u.id].first_out = nodes[v.id].first_in = n;
 
-      Edge e; e.n=n;
-
-      //Update dynamic maps
-      edge_maps.add(e);
-
-      return e;
+      return Edge(n);
     }
     
-    /// Finds an edge between two nodes.
+    void erase(const Node& node) {
+      int n = node.id;
+      
+      if(nodes[n].next != -1) {
+	nodes[nodes[n].next].prev = nodes[n].prev;
+      }
+      
+      if(nodes[n].prev != -1) {
+	nodes[nodes[n].prev].next = nodes[n].next;
+      } else {
+	first_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_free_node;
+      first_free_node = n;
 
-    /// Finds an edge from node \c u to node \c v.
-    ///
-    /// If \c prev is \ref INVALID (this is the default value), then
-    /// It finds the first edge from \c u to \c v. Otherwise it looks for
-    /// the next edge from \c u to \c v after \c prev.
-    /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
-    {
-      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
-      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
-      prev.n=e;
-      return prev;
     }
     
-  private:
-    void eraseEdge(int n) {
+    void erase(const Edge& edge) {
+      int n = edge.id;
       
-      if(edges[n].next_in!=-1)
+      if(edges[n].next_in!=-1) {
 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
-      if(edges[n].prev_in!=-1)
+      }
+
+      if(edges[n].prev_in!=-1) {
 	edges[edges[n].prev_in].next_in = edges[n].next_in;
-      else nodes[edges[n].head].first_in = edges[n].next_in;
+      } else {
+	nodes[edges[n].head].first_in = edges[n].next_in;
+      }
+
       
-      if(edges[n].next_out!=-1)
+      if(edges[n].next_out!=-1) {
 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
-      if(edges[n].prev_out!=-1)
+      } 
+
+      if(edges[n].prev_out!=-1) {
 	edges[edges[n].prev_out].next_out = edges[n].next_out;
-      else nodes[edges[n].tail].first_out = edges[n].next_out;
+      } else {
+	nodes[edges[n].tail].first_out = edges[n].next_out;
+      }
       
       edges[n].next_in = first_free_edge;
       first_free_edge = n;      
 
-      //Update dynamic maps
-      Edge e; e.n=n;
-      edge_maps.erase(e);
-
     }
-      
-  public:
-
-    void erase(Node nn) {
-      int n=nn.n;
-      
-      int m;
-      while((m=nodes[n].first_in)!=-1) eraseEdge(m);
-      while((m=nodes[n].first_out)!=-1) eraseEdge(m);
-
-      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
-      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
-      else first_node = nodes[n].next;
-      
-      nodes[n].next = first_free_node;
-      first_free_node = n;
-
-      //Update dynamic maps
-      node_maps.erase(nn);
-
-    }
-    
-    void erase(Edge e) { eraseEdge(e.n); }
 
     void clear() {
-      edge_maps.clear();
       edges.clear();
-      node_maps.clear();
       nodes.clear();
-      first_node=first_free_node=first_free_edge=-1;
-    }
-
-    class Node {
-      friend class ListGraph;
-      template <typename T> friend class NodeMap;
-       
-      friend class Edge;
-      friend class OutEdgeIt;
-      friend class InEdgeIt;
-      friend class SymEdge;
-
-    protected:
-      int n;
-      friend int ListGraph::id(Node v); 
-      Node(int nn) {n=nn;}
-    public:
-      Node() {}
-      Node (Invalid) { n=-1; }
-      bool operator==(const Node i) const {return n==i.n;}
-      bool operator!=(const Node i) const {return n!=i.n;}
-      bool operator<(const Node i) const {return n<i.n;}
-      //      ///Validity check
-      //      operator bool() { return n!=-1; }
-    };
-    
-    class NodeIt : public Node {
-      const ListGraph *G;
-      friend class ListGraph;
-    public:
-      NodeIt() : Node() { }
-      NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
-      NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
-      NodeIt &operator++() {
-	n=G->nodes[n].next; 
-	return *this; 
-      }
-      //      ///Validity check
-      //      operator bool() { return Node::operator bool(); }      
-    };
-
-    class Edge {
-      friend class ListGraph;
-      template <typename T> friend class EdgeMap;
-
-      friend class SymListGraph;
-      
-      friend class Node;
-      friend class NodeIt;
-    protected:
-      int n;
-      friend int ListGraph::id(Edge e);
-
-    public:
-      /// An Edge with id \c n.
-
-      /// \bug It should be
-      /// obtained by a member function of the Graph.
-      Edge(int nn) {n=nn;}
-
-      Edge() { }
-      Edge (Invalid) { n=-1; }
-      bool operator==(const Edge i) const {return n==i.n;}
-      bool operator!=(const Edge i) const {return n!=i.n;}
-      bool operator<(const Edge i) const {return n<i.n;}
-      //      ///Validity check
-      //      operator bool() { return n!=-1; }
-   };
-    
-    class EdgeIt : public Edge {
-      const ListGraph *G;
-      friend class ListGraph;
-    public:
-      EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
-      	int m;
-	for(m=_G.first_node;
-	    m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
-	n = (m==-1)?-1:_G.nodes[m].first_in;
-      }
-      EdgeIt (Invalid i) : Edge(i) { }
-      EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      EdgeIt() : Edge() { }
-      EdgeIt &operator++() {
-	if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
-	else {
-	  int nn;
-	  for(nn=G->nodes[G->edges[n].head].next;
-	      nn!=-1 && G->nodes[nn].first_in == -1;
-	      nn = G->nodes[nn].next) ;
-	  n = (nn==-1)?-1:G->nodes[nn].first_in;
-	}
-	return *this;
-      }
-      //      ///Validity check
-      //      operator bool() { return Edge::operator bool(); }      
-    };
-    
-    class OutEdgeIt : public Edge {
-      const ListGraph *G;
-      friend class ListGraph;
-    public: 
-      OutEdgeIt() : Edge() { }
-      OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      OutEdgeIt (Invalid i) : Edge(i) { }
-
-      OutEdgeIt(const ListGraph& _G,const Node v)
-	: Edge(_G.nodes[v.n].first_out), G(&_G) {}
-      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
-      //      ///Validity check
-      //      operator bool() { return Edge::operator bool(); }      
-    };
-    
-    class InEdgeIt : public Edge {
-      const ListGraph *G;
-      friend class ListGraph;
-    public: 
-      InEdgeIt() : Edge() { }
-      InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const ListGraph& _G,Node v)
-	: Edge(_G.nodes[v.n].first_in), G(&_G) { }
-      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
-      //      ///Validity check
-      //      operator bool() { return Edge::operator bool(); }      
-    };
-  };
-
-  ///Graph for bidirectional edges.
-
-  ///The purpose of this graph structure is to handle graphs
-  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
-  ///of oppositely directed edges.
-  ///There is a new edge map type called
-  ///\ref lemon::SymListGraph::SymEdgeMap "SymEdgeMap"
-  ///that complements this
-  ///feature by
-  ///storing shared values for the edge pairs. The usual
-  ///\ref lemon::skeleton::StaticGraph::EdgeMap "EdgeMap"
-  ///can be used
-  ///as well.
-  ///
-  ///The oppositely directed edge can also be obtained easily
-  ///using \ref lemon::SymListGraph::opposite() "opposite()" member function.
-  ///
-  ///Here erase(Edge) deletes a pair of edges.
-  ///
-  ///\todo this date structure need some reconsiderations. Maybe it
-  ///should be implemented independently from ListGraph.
-  /*  
-  class SymListGraph : public ListGraph
-  {
-  public:
-
-    typedef SymListGraph Graph;
-
-    // Create symmetric map registry.
-    CREATE_SYM_EDGE_MAP_REGISTRY;
-    // Create symmetric edge map.
-    CREATE_SYM_EDGE_MAP(ArrayMap);
-
-    SymListGraph() : ListGraph() { }
-    SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
-    ///Adds a pair of oppositely directed edges to the graph.
-    Edge addEdge(Node u, Node v)
-    {
-      Edge e = ListGraph::addEdge(u,v);
-      Edge f = ListGraph::addEdge(v,u);
-      sym_edge_maps.add(e);
-      sym_edge_maps.add(f);
-      
-      return e;
-    }
-
-    void erase(Node n) { ListGraph::erase(n);}
-    ///The oppositely directed edge.
-
-    ///Returns the oppositely directed
-    ///pair of the edge \c e.
-    static Edge opposite(Edge e)
-    {
-      Edge f;
-      f.n = e.n - 2*(e.n%2) + 1;
-      return f;
-    }
-    
-    ///Removes a pair of oppositely directed edges to the graph.
-    void erase(Edge e) {
-      Edge f = opposite(e);
-      sym_edge_maps.erase(e);
-      sym_edge_maps.erase(f);
-      ListGraph::erase(f);
-      ListGraph::erase(e);
-    }    
-    };*/
-
-  class SymListGraph : public ListGraph {
-    typedef ListGraph Parent;
-  public:
-
-    typedef SymListGraph Graph;
-
-    typedef ListGraph::Node Node;
-    typedef ListGraph::NodeIt NodeIt;
-
-    class SymEdge;
-    class SymEdgeIt;
-
-    class Edge;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-
-    template <typename Value>
-    class NodeMap : public Parent::NodeMap<Value> {      
-    public:
-      NodeMap(const SymListGraph& g) 
-	: SymListGraph::Parent::NodeMap<Value>(g) {}
-      NodeMap(const SymListGraph& g, Value v) 
-	: SymListGraph::Parent::NodeMap<Value>(g, v) {}
-      template<typename TT> 
-      NodeMap(const NodeMap<TT>& copy) 
-	: SymListGraph::Parent::NodeMap<Value>(copy) { }            
-    };
-
-    template <typename Value>
-    class SymEdgeMap : public Parent::EdgeMap<Value> {
-    public:
-      typedef SymEdge KeyType;
-
-      SymEdgeMap(const SymListGraph& g) 
-	: SymListGraph::Parent::EdgeMap<Value>(g) {}
-      SymEdgeMap(const SymListGraph& g, Value v) 
-	: SymListGraph::Parent::EdgeMap<Value>(g, v) {}
-      template<typename TT> 
-      SymEdgeMap(const SymEdgeMap<TT>& copy) 
-	: SymListGraph::Parent::EdgeMap<Value>(copy) { }
-      
-    };
-
-    // Create edge map registry.
-    CREATE_EDGE_MAP_REGISTRY;
-    // Create edge maps.
-    CREATE_EDGE_MAP(ArrayMap);
-
-    class Edge {
-      friend class SymListGraph;
-      friend class SymListGraph::EdgeIt;
-      friend class SymListGraph::OutEdgeIt;
-      friend class SymListGraph::InEdgeIt;
-      
-    protected:
-      int id;
-
-      Edge(int pid) { id = pid; }
-
-    public:
-      /// An Edge with id \c n.
-
-      Edge() { }
-      Edge (Invalid) { id = -1; }
-
-      operator SymEdge(){ return SymEdge(id >> 1);}
-      
-      bool operator==(const Edge i) const {return id == i.id;}
-      bool operator!=(const Edge i) const {return id != i.id;}
-      bool operator<(const Edge i) const {return id < i.id;}
-      //      ///Validity check
-      //      operator bool() { return n!=-1; }
-    };
-
-    class SymEdge : public ListGraph::Edge {
-      friend class SymListGraph;
-      friend class SymListGraph::Edge;
-      typedef ListGraph::Edge Parent;
-
-    protected:      
-      SymEdge(int pid) : Parent(pid) {}
-    public:
-
-      SymEdge() { }
-      SymEdge(const ListGraph::Edge& i) : Parent(i) {} 
-      SymEdge (Invalid) : Parent(INVALID) {}
-
-    };
-
-    class OutEdgeIt {
-      Parent::OutEdgeIt out;
-      Parent::InEdgeIt in;      
-    public: 
-      OutEdgeIt() {}
-      OutEdgeIt(const SymListGraph& g, Edge e) { 
-	if ((e.id & 1) == 0) {	
-	  out = Parent::OutEdgeIt(g, SymEdge(e));
-	  in = Parent::InEdgeIt(g, g.tail(e));
-	} else {
-	  out = Parent::OutEdgeIt(INVALID);
-	  in = Parent::InEdgeIt(g, SymEdge(e));
-	}
-      }
-      OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
-
-      OutEdgeIt(const SymListGraph& g, const Node v)
-	: out(g, v), in(g, v) {}
-      OutEdgeIt &operator++() { 
-	if (out != INVALID) {
-	  ++out;
-	} else {
-	  ++in;
-	}
-	return *this; 
-      }
-
-      operator Edge() const {
-	if (out == INVALID && in == INVALID) return INVALID;
-	return out != INVALID ? forward(out) : backward(in);
-      }
-
-      bool operator==(const Edge i) const {return Edge(*this) == i;}
-      bool operator!=(const Edge i) const {return Edge(*this) != i;}
-      bool operator<(const Edge i) const {return Edge(*this) < i;}
-    };
-
-    class InEdgeIt {
-      Parent::OutEdgeIt out;
-      Parent::InEdgeIt in;      
-    public: 
-      InEdgeIt() {}
-      InEdgeIt(const SymListGraph& g, Edge e) { 
-	if ((e.id & 1) == 0) {	
-	  out = Parent::OutEdgeIt(g, SymEdge(e));
-	  in = Parent::InEdgeIt(g, g.tail(e));
-	} else {
-	  out = Parent::OutEdgeIt(INVALID);
-	  in = Parent::InEdgeIt(g, SymEdge(e));
-	}
-      }
-      InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
-
-      InEdgeIt(const SymListGraph& g, const Node v)
-	: out(g, v), in(g, v) {}
-
-      InEdgeIt &operator++() { 
-	if (out != INVALID) {
-	  ++out;
-	} else {
-	  ++in;
-	}
-	return *this; 
-      }
-
-      operator Edge() const {
-	if (out == INVALID && in == INVALID) return INVALID;
-	return out != INVALID ? backward(out) : forward(in);
-      }
-
-      bool operator==(const Edge i) const {return Edge(*this) == i;}
-      bool operator!=(const Edge i) const {return Edge(*this) != i;}
-      bool operator<(const Edge i) const {return Edge(*this) < i;}
-    };
-
-    class SymEdgeIt : public Parent::EdgeIt {
-
-    public:
-      SymEdgeIt() {}
-
-      SymEdgeIt(const SymListGraph& g) 
-	: SymListGraph::Parent::EdgeIt(g) {}
-
-      SymEdgeIt(const SymListGraph& g, SymEdge e) 
-	: SymListGraph::Parent::EdgeIt(g, e) {}
-
-      SymEdgeIt(Invalid i) 
-	: SymListGraph::Parent::EdgeIt(INVALID) {}
-
-      SymEdgeIt& operator++() {
-	SymListGraph::Parent::EdgeIt::operator++();
-	return *this;
-      }
-
-      operator SymEdge() const {
-	return SymEdge
-	  (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
-      }
-      bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
-      bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
-      bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
-    };
-
-    class EdgeIt {
-      SymEdgeIt it;
-      bool fw;
-    public:
-      EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
-      EdgeIt (Invalid i) : it(i) { }
-      EdgeIt(const SymListGraph& g, Edge e) 
-	: it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
-      EdgeIt() { }
-      EdgeIt& operator++() {
-	fw = !fw;
-	if (fw) ++it;
-	return *this;
-      }
-      operator Edge() const {
-	if (it == INVALID) return INVALID;
-	return fw ? forward(it) : backward(it);
-      }
-      bool operator==(const Edge i) const {return Edge(*this) == i;}
-      bool operator!=(const Edge i) const {return Edge(*this) != i;}
-      bool operator<(const Edge i) const {return Edge(*this) < i;}
-
-    };
-
-    ///Number of nodes.
-    int nodeNum() const { return Parent::nodeNum(); }
-    ///Number of edges.
-    int edgeNum() const { return 2*Parent::edgeNum(); }
-    ///Number of symmetric edges.
-    int symEdgeNum() const { return Parent::edgeNum(); }
-
-    ///Set the expected maximum number of edges.
-
-    ///With this function, it is possible to set the expected number of edges.
-    ///The use of this fasten the building of the graph and makes
-    ///it possible to avoid the superfluous memory allocation.
-    void reserveSymEdge(int n) { Parent::reserveEdge(n); };
-    
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
-    int maxNodeId() const { return Parent::maxNodeId(); } 
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
-    int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
-    /// Maximum symmetric edge ID.
-    
-    /// Maximum symmetric edge ID.
-    ///\sa id(SymEdge)
-    int maxSymEdgeId() const { return Parent::maxEdgeId(); }
-
-
-    Node tail(Edge e) const { 
-      return (e.id & 1) == 0 ? 
-	Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); 
-    }
-
-    Node head(Edge e) const { 
-      return (e.id & 1) == 0 ? 
-	Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); 
-    }
-
-    Node tail(SymEdge e) const { 
-      return Parent::tail(e); 
-    }
-
-    Node head(SymEdge e) const { 
-      return Parent::head(e); 
-    }
-
-    NodeIt& first(NodeIt& v) const { 
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    SymEdgeIt& first(SymEdgeIt& e) const {
-      e=SymEdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
-
-    /// Node ID.
-    
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    ///\return The ID of the node \c v. 
-    static int id(Node v) { return Parent::id(v); }
-    /// Edge ID.
-    
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.id; }
-
-    /// The ID of a valid SymEdge is a nonnegative integer not greater than
-    /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
-    ///
-    /// The ID of the \ref INVALID symmetric edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(SymEdge e) { return Parent::id(e); }
-
-    /// Adds a new node to the graph.
-
-    /// \warning It adds the new node to the front of the list.
-    /// (i.e. the lastly added node becomes the first.)
-    Node addNode() {
-      return Parent::addNode();
-    }
-    
-    SymEdge addEdge(Node u, Node v) {
-      SymEdge se = Parent::addEdge(u, v);
-      edge_maps.add(forward(se));
-      edge_maps.add(backward(se));
-      return se;
-    }
-    
-    /// Finds an edge between two nodes.
-
-    /// Finds an edge from node \c u to node \c v.
-    ///
-    /// If \c prev is \ref INVALID (this is the default value), then
-    /// It finds the first edge from \c u to \c v. Otherwise it looks for
-    /// the next edge from \c u to \c v after \c prev.
-    /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u, Node v, Edge prev = INVALID) 
-    {     
-      if (prev == INVALID || id(prev) & 1 == 0) {
-	SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
-	if (se != INVALID) return forward(se);
-      } else {
-	SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
-	if (se != INVALID) return backward(se);	
-      }
-      return INVALID;
-    }
-
-//     /// Finds an symmetric edge between two nodes.
-
-//     /// Finds an symmetric edge from node \c u to node \c v.
-//     ///
-//     /// If \c prev is \ref INVALID (this is the default value), then
-//     /// It finds the first edge from \c u to \c v. Otherwise it looks for
-//     /// the next edge from \c u to \c v after \c prev.
-//     /// \return The found edge or INVALID if there is no such an edge.
-
-//     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) 
-//     {     
-//       if (prev == INVALID || id(prev) & 1 == 0) {
-// 	SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
-// 	if (se != INVALID) return se;
-//       } else {
-// 	SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
-// 	if (se != INVALID) return se;	
-//       }
-//       return INVALID;
-//     }
-    
-  public:
-
-    void erase(Node n) {      
-      for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
-	edge_maps.erase(it);
-	edge_maps.erase(opposite(it));
-      }
-      Parent::erase(n);
-    }
-    
-    void erase(SymEdge e) { 
-      edge_maps.erase(forward(e));
-      edge_maps.erase(backward(e));
-      Parent::erase(e); 
-    };
-
-    void clear() {
-      edge_maps.clear();
-      Parent::clear();
-    }
-
-    static Edge opposite(Edge e) {
-      return Edge(id(e) ^ 1);
-    }
-
-    static Edge forward(SymEdge e) {
-      return Edge(id(e) << 1);
-    }
-
-    static Edge backward(SymEdge e) {
-      return Edge((id(e) << 1) | 1);
+      first_node = first_free_node = first_free_edge = -1;
     }
 
   };
 
-  ///A graph class containing only nodes.
+  typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
+  typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
+  typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase;
+  typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase;
+  typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
+  typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
+  typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
 
-  ///This class implements a graph structure without edges.
-  ///The most useful application of this class is to be the node set of an
-  ///\ref EdgeSet class.
-  ///
-  ///It conforms to 
-  ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept
-  ///with the exception that you cannot
-  ///add (or delete) edges. The usual edge iterators are exists, but they are
-  ///always \ref INVALID.
-  ///\sa skeleton::ExtendableGraph
-  ///\sa EdgeSet
-  class NodeSet {
+  typedef ErasableListGraphBase ListGraph;
 
-    //Nodes are double linked.
-    //The free nodes are only single linked using the "next" field.
-    struct NodeT 
-    {
-      int first_in,first_out;
-      int prev, next;
-      //      NodeT() {}
-    };
+}
 
-    std::vector<NodeT> nodes;
-    //The first node
-    int first_node;
-    //The first free node
-    int first_free_node;
-    
-  public:
 
-    typedef NodeSet Graph;
-    
-    class Node;
-    class Edge;
+  
 
-  public:
-
-    class NodeIt;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-    
-    // Create node map registry.
-    CREATE_NODE_MAP_REGISTRY;
-    // Create node maps.
-    CREATE_NODE_MAP(ArrayMap);
-
-    /// Creating empty map structure for edges.
-    template <typename Value>
-    class EdgeMap {
-    public:
-      EdgeMap(const Graph&) {}
-      EdgeMap(const Graph&, const Value&) {}
-
-      EdgeMap(const EdgeMap&) {}
-      template <typename CMap> EdgeMap(const CMap&) {}
-
-      EdgeMap& operator=(const EdgeMap&) {}
-      template <typename CMap> EdgeMap& operator=(const CMap&) {}
-      
-      class ConstIterator {
-      public:
-	bool operator==(const ConstIterator&) {return true;}
-	bool operator!=(const ConstIterator&) {return false;}
-      };
-
-      typedef ConstIterator Iterator;
-      
-      Iterator begin() { return Iterator();}
-      Iterator end() { return Iterator();}
-
-      ConstIterator begin() const { return ConstIterator();}
-      ConstIterator end() const { return ConstIterator();}
-
-    };
-    
-  public:
-
-    ///Default constructor
-    NodeSet() 
-      : nodes(), first_node(-1), first_free_node(-1) {}
-    ///Copy constructor
-    NodeSet(const NodeSet &_g) 
-      : nodes(_g.nodes), first_node(_g.first_node),
-	first_free_node(_g.first_free_node) {}
-    
-    ///Number of nodes.
-    int nodeNum() const { return nodes.size(); }
-    ///Number of edges.
-    int edgeNum() const { return 0; }
-
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
-    int maxNodeId() const { return nodes.size()-1; }
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
-    int maxEdgeId() const { return 0; }
-
-    Node tail(Edge e) const { return INVALID; }
-    Node head(Edge e) const { return INVALID; }
-
-    NodeIt& first(NodeIt& v) const { 
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
-
-    /// Node ID.
-    
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    ///\return The ID of the node \c v. 
-    static int id(Node v) { return v.n; }
-    /// Edge ID.
-    
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return -1; }
-
-    /// Adds a new node to the graph.
-
-    /// \warning It adds the new node to the front of the list.
-    /// (i.e. the lastly added node becomes the first.)
-    Node addNode() {
-      int n;
-      
-      if(first_free_node==-1)
-	{
-	  n = nodes.size();
-	  nodes.push_back(NodeT());
-	}
-      else {
-	n = first_free_node;
-	first_free_node = nodes[n].next;
-      }
-      
-      nodes[n].next = first_node;
-      if(first_node != -1) nodes[first_node].prev = n;
-      first_node = n;
-      nodes[n].prev = -1;
-      
-      nodes[n].first_in = nodes[n].first_out = -1;
-      
-      Node nn; nn.n=n;
-
-      //Update dynamic maps
-      node_maps.add(nn);
-
-      return nn;
-    }
-    
-    void erase(Node nn) {
-      int n=nn.n;
-      
-      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
-      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
-      else first_node = nodes[n].next;
-      
-      nodes[n].next = first_free_node;
-      first_free_node = n;
-
-      //Update dynamic maps
-      node_maps.erase(nn);
-    }
-    
-        
-    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
-    {
-      return INVALID;
-    }
-    
-    void clear() {
-      node_maps.clear();
-      nodes.clear();
-      first_node = first_free_node = -1;
-    }
-
-    class Node {
-      friend class NodeSet;
-      template <typename T> friend class NodeMap;
-      
-      friend class Edge;
-      friend class OutEdgeIt;
-      friend class InEdgeIt;
-
-    protected:
-      int n;
-      friend int NodeSet::id(Node v); 
-      Node(int nn) {n=nn;}
-    public:
-      Node() {}
-      Node (Invalid i) { n=-1; }
-      bool operator==(const Node i) const {return n==i.n;}
-      bool operator!=(const Node i) const {return n!=i.n;}
-      bool operator<(const Node i) const {return n<i.n;}
-    };
-    
-    class NodeIt : public Node {
-      const NodeSet *G;
-      friend class NodeSet;
-    public:
-      NodeIt() : Node() { }
-      NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
-      NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
-      NodeIt &operator++() {
-	n=G->nodes[n].next; 
-	return *this; 
-      }
-    };
-
-    class Edge {
-    public:
-      Edge() { }
-      Edge (Invalid) { }
-      bool operator==(const Edge i) const {return true;}
-      bool operator!=(const Edge i) const {return false;}
-      bool operator<(const Edge i) const {return false;}
-    };
-    
-    class EdgeIt : public Edge {
-    public:
-      EdgeIt(const NodeSet& G) : Edge() { }
-      EdgeIt(const NodeSet&, Edge) : Edge() { }
-      EdgeIt (Invalid i) : Edge(i) { }
-      EdgeIt() : Edge() { }
-      EdgeIt operator++() { return INVALID; }
-    };
-    
-    class OutEdgeIt : public Edge {
-      friend class NodeSet;
-    public: 
-      OutEdgeIt() : Edge() { }
-      OutEdgeIt(const NodeSet&, Edge) : Edge() { }
-      OutEdgeIt (Invalid i) : Edge(i) { }
-      OutEdgeIt(const NodeSet& G,const Node v)	: Edge() {}
-      OutEdgeIt operator++() { return INVALID; }
-    };
-    
-    class InEdgeIt : public Edge {
-      friend class NodeSet;
-    public: 
-      InEdgeIt() : Edge() { }
-      InEdgeIt(const NodeSet&, Edge) : Edge() { }
-      InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
-      InEdgeIt operator++() { return INVALID; }
-    };
-
-  };
-
-
-
-  ///Graph structure using a node set of another graph.
-
-  ///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, and the NodeMap's of both graphs will convert to
-  /// each other.
-  ///
-  ///\warning Adding or deleting nodes from the graph is not safe if an
-  ///\ref EdgeSet is currently attached to it!
-  ///
-  ///\todo Make it possible to add/delete edges from the base graph
-  ///(and from \ref EdgeSet, as well)
-  ///
-  ///\param GG The type of the graph which shares its node set with this class.
-  ///Its interface must conform to the
-  ///\ref skeleton::StaticGraph "StaticGraph" concept.
-  ///
-  ///It conforms to the 
-  ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept.
-  ///\sa skeleton::ExtendableGraph.
-  ///\sa NodeSet.
-  template<typename GG>
-  class EdgeSet {
-
-    typedef GG NodeGraphType;
-
-    NodeGraphType &G;
-
-  public:
-
-    class Node;
-    class Edge;
-    class OutEdgeIt;
-    class InEdgeIt;
-    class SymEdge;
-
-    typedef EdgeSet Graph;
-
-    int id(Node v) const; 
-
-    class Node : public NodeGraphType::Node {
-      friend class EdgeSet;
-      
-      friend class Edge;
-      friend class OutEdgeIt;
-      friend class InEdgeIt;
-      friend class SymEdge;
-
-    public:
-      friend int EdgeSet::id(Node v) const; 
-    public:
-      Node() : NodeGraphType::Node() {}
-      Node (Invalid i) : NodeGraphType::Node(i) {}
-      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
-    };
-    
-    class NodeIt : public NodeGraphType::NodeIt {
-      friend class EdgeSet;
-    public:
-      NodeIt() : NodeGraphType::NodeIt() { }
-      NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
-      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
-      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
-      NodeIt(const typename NodeGraphType::NodeIt &n)
-	: NodeGraphType::NodeIt(n) {}
-
-      operator Node() { return Node(*this);}
-      NodeIt &operator++()
-      { this->NodeGraphType::NodeIt::operator++(); return *this;} 
-    };
-
-  private:
-    //Edges are double linked.
-    //The free edges are only single linked using the "next_in" field.
-    struct NodeT 
-    {
-      int first_in,first_out;
-      NodeT() : first_in(-1), first_out(-1) { }
-    };
-
-    struct EdgeT 
-    {
-      Node head, tail;
-      int prev_in, prev_out;
-      int next_in, next_out;
-    };
-
-    
-    typename NodeGraphType::template NodeMap<NodeT> nodes;
-    
-    std::vector<EdgeT> edges;
-    //The first free edge
-    int first_free_edge;
-    
-  public:
-    
-    class Node;
-    class Edge;
-
-    class NodeIt;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-
-
-    // Create edge map registry.
-    CREATE_EDGE_MAP_REGISTRY;
-    // Create edge maps.
-    CREATE_EDGE_MAP(ArrayMap);
-
-    // Import node maps from the NodeGraphType.
-    IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
-    
-    
-  public:
-
-    ///Constructor
-    
-    ///Construates a new graph based on the nodeset of an existing one.
-    ///\param _G the base graph.
-    explicit EdgeSet(NodeGraphType &_G) 
-      : G(_G), nodes(_G), edges(),
-	first_free_edge(-1) {}
-    ///Copy constructor
-
-    ///Makes a copy of an EdgeSet.
-    ///It will be based on the same graph.
-    explicit EdgeSet(const EdgeSet &_g) 
-      : G(_g.G), nodes(_g.G), edges(_g.edges),
-	first_free_edge(_g.first_free_edge) {}
-    
-    ///Number of nodes.
-    int nodeNum() const { return G.nodeNum(); }
-    ///Number of edges.
-    int edgeNum() const { return edges.size(); }
-
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
-    int maxNodeId() const { return G.maxNodeId(); }
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
-    int maxEdgeId() const { return edges.size()-1; }
-
-    Node tail(Edge e) const { return edges[e.n].tail; }
-    Node head(Edge e) const { return edges[e.n].head; }
-
-    NodeIt& first(NodeIt& v) const { 
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
-
-    /// Node ID.
-    
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    ///\return The ID of the node \c v. 
-    int id(Node v) { return G.id(v); }
-    /// Edge ID.
-    
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.n; }
-
-    /// Adds a new node to the graph.
-    Node addNode() { return G.addNode(); }
-    
-    Edge addEdge(Node u, Node v) {
-      int n;
-      
-      if(first_free_edge==-1)
-	{
-	  n = edges.size();
-	  edges.push_back(EdgeT());
-	}
-      else {
-	n = first_free_edge;
-	first_free_edge = edges[n].next_in;
-      }
-      
-      edges[n].tail = u; edges[n].head = v;
-
-      edges[n].next_out = nodes[u].first_out;
-      if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
-      edges[n].next_in = nodes[v].first_in;
-      if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
-      edges[n].prev_in = edges[n].prev_out = -1;
-	
-      nodes[u].first_out = nodes[v].first_in = n;
-
-      Edge e; e.n=n;
-
-      //Update dynamic maps
-      edge_maps.add(e);
-
-      return e;
-    }
-
-    /// Finds an edge between two nodes.
-
-    /// Finds an edge from node \c u to node \c v.
-    ///
-    /// If \c prev is \ref INVALID (this is the default value), then
-    /// It finds the first edge from \c u to \c v. Otherwise it looks for
-    /// the next edge from \c u to \c v after \c prev.
-    /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
-    {
-      int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
-      while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
-      prev.n=e;
-      return prev;
-    }
-    
-  private:
-    void eraseEdge(int n) {
-      
-      if(edges[n].next_in!=-1)
-	edges[edges[n].next_in].prev_in = edges[n].prev_in;
-      if(edges[n].prev_in!=-1)
-	edges[edges[n].prev_in].next_in = edges[n].next_in;
-      else nodes[edges[n].head].first_in = edges[n].next_in;
-      
-      if(edges[n].next_out!=-1)
-	edges[edges[n].next_out].prev_out = edges[n].prev_out;
-      if(edges[n].prev_out!=-1)
-	edges[edges[n].prev_out].next_out = edges[n].next_out;
-      else nodes[edges[n].tail].first_out = edges[n].next_out;
-      
-      edges[n].next_in = first_free_edge;
-      first_free_edge = -1;      
-
-      //Update dynamic maps
-      Edge e; e.n = n;
-      edge_maps.erase(e);
-    }
-      
-  public:
-
-    void erase(Edge e) { eraseEdge(e.n); }
-
-    ///Clear all edges. (Doesn't clear the nodes!)
-    void clear() {
-      edge_maps.clear();
-      edges.clear();
-      first_free_edge=-1;
-    }
-
-
-    class Edge {
-    public:
-      friend class EdgeSet;
-      template <typename T> friend class EdgeMap;
-
-      friend class Node;
-      friend class NodeIt;
-    protected:
-      int n;
-      friend int EdgeSet::id(Edge e) const;
-
-      Edge(int nn) {n=nn;}
-    public:
-      Edge() { }
-      Edge (Invalid) { n=-1; }
-      bool operator==(const Edge i) const {return n==i.n;}
-      bool operator!=(const Edge i) const {return n!=i.n;}
-      bool operator<(const Edge i) const {return n<i.n;}
-    };
-    
-    class EdgeIt : public Edge {
-      friend class EdgeSet;
-      template <typename T> friend class EdgeMap;
-    
-      const EdgeSet *G;
-    public:
-      EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
-        NodeIt m;
-	for(G->first(m);
-	    m!=INVALID && G->nodes[m].first_in == -1;  ++m);
-	///\bug AJJAJ! This is a non sense!!!!!!!
-	this->n = m!=INVALID?-1:G->nodes[m].first_in;
-      }
-      EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
-      EdgeIt (Invalid i) : Edge(i) { }
-      EdgeIt() : Edge() { }
-      ///.
-      
-      ///\bug UNIMPLEMENTED!!!!!
-      //
-      EdgeIt &operator++() {
-	return *this;
-      }
-    };
-    
-    class OutEdgeIt : public Edge {
-      const EdgeSet *G;
-      friend class EdgeSet;
-    public: 
-      OutEdgeIt() : Edge() { }
-      OutEdgeIt (Invalid i) : Edge(i) { }
-      OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
-
-      OutEdgeIt(const EdgeSet& _G,const Node v) :
-	Edge(_G.nodes[v].first_out), G(&_G) { }
-      OutEdgeIt &operator++() { 
-	Edge::n = G->edges[Edge::n].next_out;
-	return *this; 
-      }
-    };
-    
-    class InEdgeIt : public Edge {
-      const EdgeSet *G;
-      friend class EdgeSet;
-    public: 
-      InEdgeIt() : Edge() { }
-      InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
-      InEdgeIt(const EdgeSet& _G,Node v)
-	: Edge(_G.nodes[v].first_in), G(&_G) { }
-      InEdgeIt &operator++() { 
-	Edge::n = G->edges[Edge::n].next_in; 
-	return *this; 
-      }
-    };
-    
-  };
-
-  template<typename GG>
-  inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
-
-/// @}  
-
-} //namespace lemon
-
-#endif //LEMON_LIST_GRAPH_H
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/map_registry.h
--- a/src/lemon/map_registry.h	Mon Oct 25 13:29:46 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,359 +0,0 @@
-/* -*- C++ -*-
- * src/lemon/map_registry.h - Part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Combinatorial Optimization Research Group, 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_MAP_REGISTRY_H
-#define LEMON_MAP_REGISTRY_H
-
-#include <vector>
-
-///\ingroup graphmapfactory
-///\file
-///\brief Map registry for graph maps.
-
-namespace lemon {
-
-  /// \addtogroup graphmapfactory
-  /// @{
-
-  /// Map registry for graph maps.
-
-  /** 
-   * Registry class to register edge or node maps into the graph. The
-   * registry helps you to implement an observer pattern. If you add
-   * or erase an edge or node you must notify all the maps about the
-   * event.
-   *
-   * \param G The graph type to register maps.
-   * \param K The key type of the maps registered into the registry.
-   * \param KIt The key iterator type iterates on the keys.
-   *
-   * \author Balazs Dezso
-   */
-
-  template <typename G, typename K, typename KIt>
-  class MapRegistry {
-  public:
-    typedef G Graph;
-    typedef K KeyType;
-    typedef KIt KeyIt;
-
-    /// MapBase is the base class of the dynamic maps.
-	
-    /**
-     * MapBase is the base class of the dynamic maps.
-     * It defines the core modification operations on the maps and
-     * implements some helper functions. 
-     */
-    class MapBase {
-    public:
-      typedef G Graph;
-      typedef K KeyType;
-      typedef KIt KeyIt;
-
-      typedef MapRegistry<G, K, KIt> Registry;
-	
-      friend class MapRegistry<G, K, KIt>;
-
-      /// Default constructor.
-
-      /**
-       * Default constructor for MapBase.
-       */
-
-      MapBase() : graph(0), registry(0) {}
-
-      /// Constructor to register map into a graph registry.
-		
-      /** 
-       * Simple constructor to register dynamic map into a graph registry.
-      */
-	
-      MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) {
-	r.attach(*this);
-      }
-
-      /// Copy constructor.
-
-      /** 
-       * Copy constructor to register into the registry.
-       * If the copiable map is registered into a registry
-       * the construated map will be registered to the same registry.
-      */	
-	
-      MapBase(const MapBase& copy) : graph(copy.graph), registry(0) {
-	if (copy.registry) {
-	  copy.registry->attach(*this);
-	}
-      } 
-
-      /// Assign operator.
-	
-      /** 
-       * Assign operator. This member detach first the map
-       * from the current registry and then it attach to the
-       * copiable map's registry if it exists.
-      */	
-      const MapBase& operator=(const MapBase& copy) {
-	if (registry) {
-	  registry->detach(*this);
-	}
-	graph = copy.graph;
-	if (copy.registry) {
-	  copy.registry->attach(*this);
-	}
-	return *this;
-      }
-	
-      /// Destructor
-
-      /** 
-       * This member detach the map from the its registry if the
-       * registry exists.
-      */		
-
-      virtual ~MapBase() {
-	if (registry) {
-	  registry->detach(*this);
-	}
-      }
-
-      /// The graph of the map.
-
-      /*
-       * Returns the graph that the map belongs to.
-      */
-
-      const Graph* getGraph() const { return graph; }
-	
-    protected:
-		
-      const Graph* graph;     
-      Registry* registry;
-
-      int registry_index;
-
-    protected:
-
-      /// Helper function to implement constructors in the subclasses.
-	
-      /**
-       * Helper function to implement constructors in the subclasses.
-       * It adds all of the nodes or edges to the map via the 
-       * \ref MapRegistry::MapBase::add add
-       * member function.
-      */
-	
-      virtual void init() {
-	for (KeyIt it(*graph); it != INVALID; ++it) {
-	  add(it);
-	}
-      }
-	
-
-      /// Helper function to implement destructors in the subclasses.
-	
-      /**
-       * Helper function to implement destructors in the subclasses.
-       * It erases all of the nodes or edges of the map via the 
-       * \ref MapRegistry::MapBase::erase erase
-       * member function. It can be used by the clear function also.
-      */
-	
-      virtual void destroy() {
-	for (KeyIt it(*getGraph()); it != INVALID; ++it) {
-	  erase(it);
-	}
-      }
-
-      /// The member function to add new node or edge to the map.
-	
-      /** 
-	  The add member function should be overloaded in the subclasses.
-	  \e Add extends the map with the new node or edge.
-      */
-	
-      virtual void add(const KeyType&) = 0;	
-
-
-      /// The member function to erase a node or edge from the map.
-
-      /** 
-	  The erase member function should be overloaded in the subclasses.
-	  \e Erase removes the node or edge from the map.
-      */
-	
-      virtual void erase(const KeyType&) = 0;
-
-      /**
-       *  The clear member function should be overloaded in the subclasses.
-       *  \e Clear makes empty the data structure.
-       */
-
-      virtual void clear() = 0;
-
-      /// Exception class to throw at unsupported operation.
-	
-      /**
-       * Exception class to throw at unsupported operation.
-       * If the map does not support erasing or adding new
-       * node or key it must be throwed.
-      */
-	
-      class NotSupportedOperationException {};
-
-    };
-	
-  protected:
-	
-
-    typedef std::vector<MapBase*> Container; 
-
-    Container container;
-
-		
-  public:
-
-    /// Default constructor.
-	
-    /**
-     * Default constructor of the \e MapRegistry. 
-     * It creates an empty registry.
-     */
-    MapRegistry() {}
-
-    /// Copy Constructor of the MapRegistry. 
-	
-    /**
-     * Copy constructor of the \e MapRegistry. 
-     * The new registry does not steal
-     * the maps from the copiable registry. 
-     * The new registry will be empty.
-     */
-    MapRegistry(const MapRegistry&) {}
-
-    /// Assign operator.
-		
-    /**
-     * Assign operator. This registry does not steal the maps 
-     * from the copiable registry. This registry will be an empty registry.
-     * This operator will be called when a graph is assigned.
-     */
-    MapRegistry& operator=(const MapRegistry&) {
-      typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->clear();
-	(*it)->graph = 0;
-	(*it)->registry = 0;
-      }
-    }
-
-    /// Destructor.
-				
-    /**
-     * Destructor of the MapRegistry. It makes empty the attached map
-     * first then detachs them.
-     */
-    ~MapRegistry() {
-      typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->clear();
-	(*it)->registry = 0;
-	(*it)->graph = 0;
-      }
-    }
-	
-	
-    public:
-
-    /// Attachs a map to the \e MapRegistry.
-	
-    /**
-     * Attachs a map into thr registry. If the map has been attached
-     * into an other registry it is detached from that automaticly.
-     */
-    void attach(MapBase& map) {
-      if (map.registry) {
-	map.registry->detach(map);
-      }
-      container.push_back(&map);
-      map.registry = this;
-      map.registry_index = container.size()-1;
-    } 
-
-    /// Detachs a map from the \e MapRegistry.
-	
-    /**
-     * Detachs a map from the \e MapRegistry.
-     */
-    void detach(MapBase& map) {
-      container.back()->registry_index = map.registry_index; 
-      container[map.registry_index] = container.back();
-      container.pop_back();
-      map.registry = 0;
-      map.graph = 0;
-    }
-	
-    /// Notify all the registered maps about a Key added.
-		
-    /**
-     * Notify all the registered maps about a Key added.
-     * This member should be called whenever a node or edge
-     * is added to the graph.
-     */
-    void add(const KeyType& key) {
-      typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->add(key);
-      }
-    }	
-
-    /// Notify all the registered maps about a Key erased.
-		
-    /**
-     * Notify all the registered maps about a Key erased.
-     * This member should be called whenever a node or edge
-     * is erased from the graph.
-     */ 
-    void erase(const KeyType& key) {
-      typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->erase(key);
-      }
-    }
-
-
-    /// Notify all the registered maps about all the Keys are erased.
-
-    /**
-     * Notify all the registered maps about the map should be cleared.
-     * This member should be called whenever all of the nodes or edges
-     * are erased from the graph.
-     */ 
-    void clear() {
-      typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->clear();
-      }
-    }
-  };
-
-  
-/// @}
-  
-
-}
-
-#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/mappable_graph_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/mappable_graph_extender.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,97 @@
+// -*- c++ -*-
+
+#ifndef LEMON_MAPPABLE_GRAPH_EXTENDER_H
+#define LEMON_MAPPABLE_GRAPH_EXTENDER_H
+
+namespace lemon {
+
+  template <typename Base, template <class,class,class,class,class,class> class DynMap> 
+  class MappableGraphExtender : public Base {
+  public:
+
+    typedef MappableGraphExtender Graph;
+    typedef Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::NodeIt NodeIt;
+    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
+
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::EdgeIt EdgeIt;
+    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
+
+  public:
+
+    class NodeIdMap {
+    private:
+      const Graph* graph;
+
+    public:
+      NodeIdMap(const Graph& g) : graph(&g) {}
+
+      int operator[](const Node& node) { return graph->id(node); }
+
+      int maxId() const {return graph->maxNodeId(); }
+
+    };
+
+    //    template <typename Value>
+    //    friend class DynMap<NodeObserverRegistry, Graph, Node, NodeIt,
+    //		NodeIdMap, Value>;
+
+    class EdgeIdMap {
+    private:
+      const Graph* graph;
+
+    public:
+      EdgeIdMap(const Graph& g) : graph(&g) {}
+
+      int operator[](const Edge& edge) const { return graph->id(edge); }
+
+      int maxId() const {return graph->maxEdgeId(); }
+
+    };
+
+    //    template <typename Value>
+    //    friend class DynMap<EdgeObserverRegistry, Graph, Edge, EdgeIt,
+    //		EdgeIdMap, Value>;
+
+  public:
+    
+    template <typename Value>
+    class NodeMap 
+      : public DynMap<NodeObserverRegistry, Graph, Node, NodeIt,
+		      NodeIdMap, Value> {
+    public:
+      typedef DynMap<NodeObserverRegistry, Graph, Node, NodeIt,
+		     NodeIdMap, Value> Parent;
+
+      NodeMap(const Graph& g) 
+	: Parent(g, g.Graph::Parent::getNodeObserverRegistry()) {}
+      NodeMap(const Graph& g, const Value& v) 
+	: Parent(g, g.Graph::Parent::getNodeObserverRegistry(), v) {}
+
+    };
+
+    template <typename Value>
+    class EdgeMap 
+      : public DynMap<EdgeObserverRegistry, Graph, Edge, EdgeIt,
+		      EdgeIdMap, Value> {
+    public:
+      typedef DynMap<EdgeObserverRegistry, Graph, Edge, EdgeIt,
+		     EdgeIdMap, Value> Parent;
+
+      EdgeMap(const Graph& g) 
+	: Parent(g, g.Graph::Parent::getEdgeObserverRegistry()) {}
+      EdgeMap(const Graph& g, const Value& v) 
+	: Parent(g, g.Graph::Parent::getEdgeObserverRegistry(), v) {}
+
+    };
+
+    
+  };
+
+}
+
+#endif
+
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/preflow.h
--- a/src/lemon/preflow.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/preflow.h	Wed Oct 27 22:38:50 2004 +0000
@@ -140,7 +140,7 @@
       Preflow(const Graph& _G, Node _s, Node _t, 
 	      const CapMap& _capacity, FlowMap& _flow) :
 	g(&_G), s(_s), t(_t), capacity(&_capacity),
-	flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), 
+	flow(&_flow), n(countNodes(_G)), level(_G), excess(_G,0), 
 	flow_prop(NO_FLOW), status(AFTER_NOTHING) { }
 
 
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/skeletons/graph.h
--- a/src/lemon/skeletons/graph.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/skeletons/graph.h	Wed Oct 27 22:38:50 2004 +0000
@@ -23,6 +23,8 @@
 
 #include <lemon/invalid.h>
 #include <lemon/skeletons/maps.h>
+#include <lemon/concept_check.h>
+#include <lemon/skeletons/graph_component.h>
 
 namespace lemon {
   namespace skeleton {
@@ -30,734 +32,883 @@
     /// \addtogroup skeletons
     /// @{
 
-    /// An empty static graph class.
+//     /// An empty static graph class.
   
-    /// This class provides all the common features of a graph structure,
-    /// however completely without implementations and real data structures
-    /// behind the interface.
-    /// All graph algorithms should compile with this class, but it will not
-    /// run properly, of course.
-    ///
-    /// It can be used for checking the interface compatibility,
-    /// or it can serve as a skeleton of a new graph structure.
-    /// 
-    /// Also, you will find here the full documentation of a certain graph
-    /// feature, the documentation of a real graph imlementation
-    /// like @ref ListGraph or
-    /// @ref SmartGraph will just refer to this structure.
-    ///
-    /// \todo A pages describing the concept of concept description would
-    /// be nice.
-    class StaticGraph
-    {
+//     /// This class provides all the common features of a graph structure,
+//     /// however completely without implementations and real data structures
+//     /// behind the interface.
+//     /// All graph algorithms should compile with this class, but it will not
+//     /// run properly, of course.
+//     ///
+//     /// It can be used for checking the interface compatibility,
+//     /// or it can serve as a skeleton of a new graph structure.
+//     /// 
+//     /// Also, you will find here the full documentation of a certain graph
+//     /// feature, the documentation of a real graph imlementation
+//     /// like @ref ListGraph or
+//     /// @ref SmartGraph will just refer to this structure.
+//     ///
+//     /// \todo A pages describing the concept of concept description would
+//     /// be nice.
+//     class StaticGraph
+//     {
+//     public:
+//       /// Defalult constructor.
+
+//       /// Defalult constructor.
+//       ///
+//       StaticGraph() { }
+//       ///Copy consructor.
+
+// //       ///\todo It is not clear, what we expect from a copy constructor.
+// //       ///E.g. How to assign the nodes/edges to each other? What about maps?
+// //       StaticGraph(const StaticGraph& g) { }
+
+//       /// The base type of node iterators, 
+//       /// or in other words, the trivial node iterator.
+
+//       /// This is the base type of each node iterator,
+//       /// thus each kind of node iterator converts to this.
+//       /// More precisely each kind of node iterator should be inherited 
+//       /// from the trivial node iterator.
+//       class Node {
+//       public:
+// 	/// Default constructor
+
+// 	/// @warning The default constructor sets the iterator
+// 	/// to an undefined value.
+// 	Node() { }
+// 	/// Copy constructor.
+
+// 	/// Copy constructor.
+// 	///
+// 	Node(const Node&) { }
+
+// 	/// Invalid constructor \& conversion.
+
+// 	/// This constructor initializes the iterator to be invalid.
+// 	/// \sa Invalid for more details.
+// 	Node(Invalid) { }
+// 	/// Equality operator
+
+// 	/// Two iterators are equal if and only if they point to the
+// 	/// same object or both are invalid.
+// 	bool operator==(Node) const { return true; }
+
+// 	/// Inequality operator
+	
+// 	/// \sa operator==(Node n)
+// 	///
+// 	bool operator!=(Node) const { return true; }
+
+//  	///Comparison operator.
+
+// 	///This is a strict ordering between the nodes.
+// 	///
+// 	///This ordering can be different from the order in which NodeIt
+// 	///goes through the nodes.
+// 	///\todo Possibly we don't need it.
+// 	bool operator<(Node) const { return true; }
+//       };
+    
+//       /// This iterator goes through each node.
+
+//       /// This iterator goes through each node.
+//       /// Its usage is quite simple, for example you can count the number
+//       /// of nodes in graph \c g of type \c Graph like this:
+//       /// \code
+//       /// int count=0;
+//       /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
+//       /// \endcode
+//       class NodeIt : public Node {
+//       public:
+// 	/// Default constructor
+
+// 	/// @warning The default constructor sets the iterator
+// 	/// to an undefined value.
+// 	NodeIt() { }
+// 	/// Copy constructor.
+	
+// 	/// Copy constructor.
+// 	///
+// 	NodeIt(const NodeIt&) { }
+// 	/// Invalid constructor \& conversion.
+
+// 	/// Initialize the iterator to be invalid.
+// 	/// \sa Invalid for more details.
+// 	NodeIt(Invalid) { }
+// 	/// Sets the iterator to the first node.
+
+// 	/// Sets the iterator to the first node of \c g.
+// 	///
+// 	NodeIt(const StaticGraph& g) { }
+// 	/// Node -> NodeIt conversion.
+
+// 	/// Sets the iterator to the node of \c g pointed by the trivial 
+// 	/// iterator n.
+// 	/// This feature necessitates that each time we 
+// 	/// iterate the edge-set, the iteration order is the same.
+// 	NodeIt(const StaticGraph& g, const Node& n) { }
+// 	/// Next node.
+
+// 	/// Assign the iterator to the next node.
+// 	///
+// 	NodeIt& operator++() { return *this; }
+//       };
+    
+    
+//       /// The base type of the edge iterators.
+
+//       /// The base type of the edge iterators.
+//       ///
+//       class Edge {
+//       public:
+// 	/// Default constructor
+
+// 	/// @warning The default constructor sets the iterator
+// 	/// to an undefined value.
+// 	Edge() { }
+// 	/// Copy constructor.
+
+// 	/// Copy constructor.
+// 	///
+// 	Edge(const Edge&) { }
+// 	/// Initialize the iterator to be invalid.
+
+// 	/// Initialize the iterator to be invalid.
+// 	///
+// 	Edge(Invalid) { }
+// 	/// Equality operator
+
+// 	/// Two iterators are equal if and only if they point to the
+// 	/// same object or both are invalid.
+// 	bool operator==(Edge) const { return true; }
+// 	/// Inequality operator
+
+// 	/// \sa operator==(Node n)
+// 	///
+// 	bool operator!=(Edge) const { return true; }
+//  	///Comparison operator.
+
+// 	///This is a strict ordering between the nodes.
+// 	///
+// 	///This ordering can be different from the order in which NodeIt
+// 	///goes through the nodes.
+// 	///\todo Possibly we don't need it.
+//  	bool operator<(Edge) const { return true; }
+//       };
+    
+//       /// This iterator goes trough the outgoing edges of a node.
+
+//       /// This iterator goes trough the \e outgoing edges of a certain node
+//       /// of a graph.
+//       /// Its usage is quite simple, for example you can count the number
+//       /// of outgoing edges of a node \c n
+//       /// in graph \c g of type \c Graph as follows.
+//       /// \code
+//       /// int count=0;
+//       /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
+//       /// \endcode
+    
+//       class OutEdgeIt : public Edge {
+//       public:
+// 	/// Default constructor
+
+// 	/// @warning The default constructor sets the iterator
+// 	/// to an undefined value.
+// 	OutEdgeIt() { }
+// 	/// Copy constructor.
+
+// 	/// Copy constructor.
+// 	///
+// 	OutEdgeIt(const OutEdgeIt&) { }
+// 	/// Initialize the iterator to be invalid.
+
+// 	/// Initialize the iterator to be invalid.
+// 	///
+// 	OutEdgeIt(Invalid) { }
+// 	/// This constructor sets the iterator to first outgoing edge.
+    
+// 	/// This constructor set the iterator to the first outgoing edge of
+// 	/// node
+// 	///@param n the node
+// 	///@param g the graph
+// 	OutEdgeIt(const StaticGraph& g, const Node& n) { }
+// 	/// Edge -> OutEdgeIt conversion
+
+// 	/// Sets the iterator to the value of the trivial iterator \c e.
+// 	/// This feature necessitates that each time we 
+// 	/// iterate the edge-set, the iteration order is the same.
+// 	OutEdgeIt(const StaticGraph& g, const Edge& e) { }
+// 	///Next outgoing edge
+	
+// 	/// Assign the iterator to the next 
+// 	/// outgoing edge of the corresponding node.
+// 	OutEdgeIt& operator++() { return *this; }
+//       };
+
+//       /// This iterator goes trough the incoming edges of a node.
+
+//       /// This iterator goes trough the \e incoming edges of a certain node
+//       /// of a graph.
+//       /// Its usage is quite simple, for example you can count the number
+//       /// of outgoing edges of a node \c n
+//       /// in graph \c g of type \c Graph as follows.
+//       /// \code
+//       /// int count=0;
+//       /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
+//       /// \endcode
+
+//       class InEdgeIt : public Edge {
+//       public:
+// 	/// Default constructor
+
+// 	/// @warning The default constructor sets the iterator
+// 	/// to an undefined value.
+// 	InEdgeIt() { }
+// 	/// Copy constructor.
+
+// 	/// Copy constructor.
+// 	///
+// 	InEdgeIt(const InEdgeIt&) { }
+// 	/// Initialize the iterator to be invalid.
+
+// 	/// Initialize the iterator to be invalid.
+// 	///
+// 	InEdgeIt(Invalid) { }
+// 	/// This constructor sets the iterator to first incoming edge.
+    
+// 	/// This constructor set the iterator to the first incoming edge of
+// 	/// node
+// 	///@param n the node
+// 	///@param g the graph
+// 	InEdgeIt(const StaticGraph& g, const Node& n) { }
+// 	/// Edge -> InEdgeIt conversion
+
+// 	/// Sets the iterator to the value of the trivial iterator \c e.
+// 	/// This feature necessitates that each time we 
+// 	/// iterate the edge-set, the iteration order is the same.
+// 	InEdgeIt(const StaticGraph& g, const Edge& n) { }
+// 	/// Next incoming edge
+
+// 	/// Assign the iterator to the next inedge of the corresponding node.
+// 	///
+// 	InEdgeIt& operator++() { return *this; }
+//       };
+//       /// This iterator goes through each edge.
+
+//       /// This iterator goes through each edge of a graph.
+//       /// Its usage is quite simple, for example you can count the number
+//       /// of edges in a graph \c g of type \c Graph as follows:
+//       /// \code
+//       /// int count=0;
+//       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
+//       /// \endcode
+//       class EdgeIt : public Edge {
+//       public:
+// 	/// Default constructor
+
+// 	/// @warning The default constructor sets the iterator
+// 	/// to an undefined value.
+// 	EdgeIt() { }
+// 	/// Copy constructor.
+
+// 	/// Copy constructor.
+// 	///
+// 	EdgeIt(const EdgeIt&) { }
+// 	/// Initialize the iterator to be invalid.
+
+// 	/// Initialize the iterator to be invalid.
+// 	///
+// 	EdgeIt(Invalid) { }
+// 	/// This constructor sets the iterator to first edge.
+    
+// 	/// This constructor set the iterator to the first edge of
+// 	/// node
+// 	///@param g the graph
+// 	EdgeIt(const StaticGraph& g) { }
+// 	/// Edge -> EdgeIt conversion
+
+// 	/// Sets the iterator to the value of the trivial iterator \c e.
+// 	/// This feature necessitates that each time we 
+// 	/// iterate the edge-set, the iteration order is the same.
+// 	EdgeIt(const StaticGraph&, const Edge&) { } 
+//     	///Next edge
+	
+// 	/// Assign the iterator to the next 
+// 	/// edge of the corresponding node.
+// 	EdgeIt& operator++() { return *this; }
+//       };
+
+//       /// First node of the graph.
+
+//       /// \retval i the first node.
+//       /// \return the first node.
+//       ///
+//       NodeIt& first(NodeIt& i) const { return i; }
+
+//       /// The first incoming edge.
+
+//       /// The first incoming edge.
+//       ///
+//       InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
+//       /// The first outgoing edge.
+
+//       /// The first outgoing edge.
+//       ///
+//       OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
+//       /// The first edge of the Graph.
+
+//       /// The first edge of the Graph.
+//       ///
+//       EdgeIt& first(EdgeIt& i) const { return i; }
+
+//       ///Gives back the head node of an edge.
+
+//       ///Gives back the head node of an edge.
+//       ///
+//       Node head(Edge) const { return INVALID; }
+//       ///Gives back the tail node of an edge.
+
+//       ///Gives back the tail node of an edge.
+//       ///
+//       Node tail(Edge) const { return INVALID; }
+  
+//       ///Gives back the \e id of a node.
+
+//       ///\warning Not all graph structures provide this feature.
+//       ///
+//       ///\todo Should each graph provide \c id?
+//       int id(const Node&) const { return 0; }
+//       ///Gives back the \e id of an edge.
+
+//       ///\warning Not all graph structures provide this feature.
+//       ///
+//       ///\todo Should each graph provide \c id?
+//       int id(const Edge&) const { return 0; }
+
+//       ///\e
+      
+//       ///\todo Should it be in the concept?
+//       ///
+//       int nodeNum() const { return 0; }
+//       ///\e
+
+//       ///\todo Should it be in the concept?
+//       ///
+//       int edgeNum() const { return 0; }
+
+
+//       ///Reference map of the nodes to type \c T.
+
+//       /// \ingroup skeletons
+//       ///Reference map of the nodes to type \c T.
+//       /// \sa Reference
+//       /// \warning Making maps that can handle bool type (NodeMap<bool>)
+//       /// needs some extra attention!
+//       template<class T> class NodeMap : public ReferenceMap< Node, T >
+//       {
+//       public:
+
+// 	///\e
+// 	NodeMap(const StaticGraph&) { }
+// 	///\e
+// 	NodeMap(const StaticGraph&, T) { }
+
+// 	///Copy constructor
+// 	template<typename TT> NodeMap(const NodeMap<TT>&) { }
+// 	///Assignment operator
+// 	template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
+// 	{ return *this; }
+//       };
+
+//       ///Reference map of the edges to type \c T.
+
+//       /// \ingroup skeletons
+//       ///Reference map of the edges to type \c T.
+//       /// \sa Reference
+//       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
+//       /// needs some extra attention!
+//       template<class T> class EdgeMap
+// 	: public ReferenceMap<Edge,T>
+//       {
+//       public:
+
+// 	///\e
+// 	EdgeMap(const StaticGraph&) { }
+// 	///\e
+// 	EdgeMap(const StaticGraph&, T) { }
+    
+// 	///Copy constructor
+// 	template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
+// 	///Assignment operator
+// 	template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
+// 	{ return *this; }
+//       };
+//     };
+
+//     struct DummyType {
+//       int value;
+//       DummyType() {}
+//       DummyType(int p) : value(p) {}
+//       DummyType& operator=(int p) { value = p; return *this;}
+//     };
+    
+//     ///\brief Checks whether \c G meets the
+//     ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
+//     template<class Graph> void checkCompileStaticGraph(Graph &G) 
+//     {
+//       typedef typename Graph::Node Node;
+//       typedef typename Graph::NodeIt NodeIt;
+//       typedef typename Graph::Edge Edge;
+//       typedef typename Graph::EdgeIt EdgeIt;
+//       typedef typename Graph::InEdgeIt InEdgeIt;
+//       typedef typename Graph::OutEdgeIt OutEdgeIt;
+  
+//       {
+// 	Node i; Node j(i); Node k(INVALID);
+// 	i=j;
+// 	bool b; b=true;
+// 	b=(i==INVALID); b=(i!=INVALID);
+// 	b=(i==j); b=(i!=j); b=(i<j);
+//       }
+//       {
+// 	NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
+// 	i=j;
+// 	j=G.first(i);
+// 	j=++i;
+// 	bool b; b=true;
+// 	b=(i==INVALID); b=(i!=INVALID);
+// 	Node n(i);
+// 	n=i;
+// 	b=(i==j); b=(i!=j); b=(i<j);
+// 	//Node ->NodeIt conversion
+// 	NodeIt ni(G,n);
+//       }
+//       {
+// 	Edge i; Edge j(i); Edge k(INVALID);
+// 	i=j;
+// 	bool b; b=true;
+// 	b=(i==INVALID); b=(i!=INVALID);
+// 	b=(i==j); b=(i!=j); b=(i<j);
+//       }
+//       {
+// 	EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
+// 	i=j;
+// 	j=G.first(i);
+// 	j=++i;
+// 	bool b; b=true;
+// 	b=(i==INVALID); b=(i!=INVALID);
+// 	Edge e(i);
+// 	e=i;
+// 	b=(i==j); b=(i!=j); b=(i<j);
+// 	//Edge ->EdgeIt conversion
+// 	EdgeIt ei(G,e);
+//       }
+//       {
+// 	Node n;
+// 	InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
+// 	i=j;
+// 	j=G.first(i,n);
+// 	j=++i;
+// 	bool b; b=true;
+// 	b=(i==INVALID); b=(i!=INVALID);
+// 	Edge e(i);
+// 	e=i;
+// 	b=(i==j); b=(i!=j); b=(i<j);
+// 	//Edge ->InEdgeIt conversion
+// 	InEdgeIt ei(G,e);
+//       }
+//       {
+// 	Node n;
+// 	OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
+// 	i=j;
+// 	j=G.first(i,n);
+// 	j=++i;
+// 	bool b; b=true;
+// 	b=(i==INVALID); b=(i!=INVALID);
+// 	Edge e(i);
+// 	e=i;
+// 	b=(i==j); b=(i!=j); b=(i<j);
+// 	//Edge ->OutEdgeIt conversion
+// 	OutEdgeIt ei(G,e);
+//       }
+//       {
+// 	Node n,m;
+// 	n=m=INVALID;
+// 	Edge e;
+// 	e=INVALID;
+// 	n=G.tail(e);
+// 	n=G.head(e);
+//       }
+//       // id tests
+//       { Node n; int i=G.id(n); i=i; }
+//       { Edge e; int i=G.id(e); i=i; }
+//       //NodeMap tests
+//       {
+// 	Node k;
+// 	typename Graph::template NodeMap<int> m(G);
+// 	//Const map
+// 	typename Graph::template NodeMap<int> const &cm = m;
+// 	//Inicialize with default value
+// 	typename Graph::template NodeMap<int> mdef(G,12);
+// 	//Copy
+// 	typename Graph::template NodeMap<int> mm(cm);
+// 	//Copy from another type
+// 	typename Graph::template NodeMap<double> dm(cm);
+// 	//Copy to more complex type
+// 	typename Graph::template NodeMap<DummyType> em(cm);
+// 	int v;
+// 	v=m[k]; m[k]=v; m.set(k,v);
+// 	v=cm[k];
+    
+// 	m=cm;  
+// 	dm=cm; //Copy from another type  
+// 	em=cm; //Copy to more complex type
+// 	{
+// 	  //Check the typedef's
+// 	  typename Graph::template NodeMap<int>::ValueType val;
+// 	  val=1;
+// 	  typename Graph::template NodeMap<int>::KeyType key;
+// 	  key = typename Graph::NodeIt(G);
+// 	}
+//       }  
+//       { //bool NodeMap
+// 	Node k;
+// 	typename Graph::template NodeMap<bool> m(G);
+// 	typename Graph::template NodeMap<bool> const &cm = m;  //Const map
+// 	//Inicialize with default value
+// 	typename Graph::template NodeMap<bool> mdef(G,12);
+// 	typename Graph::template NodeMap<bool> mm(cm);   //Copy
+// 	typename Graph::template NodeMap<int> dm(cm); //Copy from another type
+// 	bool v;
+// 	v=m[k]; m[k]=v; m.set(k,v);
+// 	v=cm[k];
+    
+// 	m=cm;  
+// 	dm=cm; //Copy from another type
+// 	m=dm; //Copy to another type
+
+// 	{
+// 	  //Check the typedef's
+// 	  typename Graph::template NodeMap<bool>::ValueType val;
+// 	  val=true;
+// 	  typename Graph::template NodeMap<bool>::KeyType key;
+// 	  key= typename Graph::NodeIt(G);
+// 	}
+//       }
+//       //EdgeMap tests
+//       {
+// 	Edge k;
+// 	typename Graph::template EdgeMap<int> m(G);
+// 	typename Graph::template EdgeMap<int> const &cm = m;  //Const map
+// 	//Inicialize with default value
+// 	typename Graph::template EdgeMap<int> mdef(G,12);
+// 	typename Graph::template EdgeMap<int> mm(cm);   //Copy
+// 	typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
+// 	int v;
+// 	v=m[k]; m[k]=v; m.set(k,v);
+// 	v=cm[k];
+    
+// 	m=cm;  
+// 	dm=cm; //Copy from another type
+// 	{
+// 	  //Check the typedef's
+// 	  typename Graph::template EdgeMap<int>::ValueType val;
+// 	  val=1;
+// 	  typename Graph::template EdgeMap<int>::KeyType key;
+// 	  key= typename Graph::EdgeIt(G);
+// 	}
+//       }  
+//       { //bool EdgeMap
+// 	Edge k;
+// 	typename Graph::template EdgeMap<bool> m(G);
+// 	typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
+// 	//Inicialize with default value
+// 	typename Graph::template EdgeMap<bool> mdef(G,12);
+// 	typename Graph::template EdgeMap<bool> mm(cm);   //Copy
+// 	typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
+// 	bool v;
+// 	v=m[k]; m[k]=v; m.set(k,v);
+// 	v=cm[k];
+    
+// 	m=cm;  
+// 	dm=cm; //Copy from another type
+// 	m=dm; //Copy to another type
+// 	{
+// 	  //Check the typedef's
+// 	  typename Graph::template EdgeMap<bool>::ValueType val;
+// 	  val=true;
+// 	  typename Graph::template EdgeMap<bool>::KeyType key;
+// 	  key= typename Graph::EdgeIt(G);
+// 	}
+//       }
+//     }
+    
+//     /// An empty non-static graph class.
+    
+//     /// This class provides everything that \ref StaticGraph
+//     /// with additional functionality which enables to build a
+//     /// graph from scratch.
+//     class ExtendableGraph : public StaticGraph
+//     {
+//     public:
+//       /// Defalult constructor.
+
+//       /// Defalult constructor.
+//       ///
+//       ExtendableGraph() { }
+//       ///Add a new node to the graph.
+
+//       /// \return the new node.
+//       ///
+//       Node addNode() { return INVALID; }
+//       ///Add a new edge to the graph.
+
+//       ///Add a new edge to the graph with tail node \c t
+//       ///and head node \c h.
+//       ///\return the new edge.
+//       Edge addEdge(Node h, Node t) { return INVALID; }
+    
+//       /// Resets the graph.
+
+//       /// This function deletes all edges and nodes of the graph.
+//       /// It also frees the memory allocated to store them.
+//       /// \todo It might belong to \ref ErasableGraph.
+//       void clear() { }
+//     };
+
+    
+//     ///\brief Checks whether \c G meets the
+//     ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
+//     template<class Graph> void checkCompileExtendableGraph(Graph &G) 
+//     {
+//       checkCompileStaticGraph(G);
+
+//       typedef typename Graph::Node Node;
+//       typedef typename Graph::NodeIt NodeIt;
+//       typedef typename Graph::Edge Edge;
+//       typedef typename Graph::EdgeIt EdgeIt;
+//       typedef typename Graph::InEdgeIt InEdgeIt;
+//       typedef typename Graph::OutEdgeIt OutEdgeIt;
+  
+//       Node n,m;
+//       n=G.addNode();
+//       m=G.addNode();
+//       Edge e;
+//       e=G.addEdge(n,m); 
+  
+//       //  G.clear();
+//     }
+
+
+//     /// An empty erasable graph class.
+  
+//     /// This class is an extension of \ref ExtendableGraph. It also makes it
+//     /// possible to erase edges or nodes.
+//     class ErasableGraph : public ExtendableGraph
+//     {
+//     public:
+//       /// Defalult constructor.
+
+//       /// Defalult constructor.
+//       ///
+//       ErasableGraph() { }
+//       /// Deletes a node.
+
+//       /// Deletes node \c n node.
+//       ///
+//       void erase(Node n) { }
+//       /// Deletes an edge.
+
+//       /// Deletes edge \c e edge.
+//       ///
+//       void erase(Edge e) { }
+//     };
+    
+//     template<class Graph> void checkCompileGraphEraseEdge(Graph &G) 
+//     {
+//       typename Graph::Edge e;
+//       G.erase(e);
+//     }
+
+//     template<class Graph> void checkCompileGraphEraseNode(Graph &G) 
+//     {
+//       typename Graph::Node n;
+//       G.erase(n);
+//     }
+
+//     ///\brief Checks whether \c G meets the
+//     ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
+//     template<class Graph> void checkCompileErasableGraph(Graph &G) 
+//     {
+//       checkCompileExtendableGraph(G);
+//       checkCompileGraphEraseNode(G);
+//       checkCompileGraphEraseEdge(G);
+//     }
+
+//     ///Checks whether a graph has findEdge() member function.
+    
+//     ///\todo findEdge() might be a global function.
+//     ///
+//     template<class Graph> void checkCompileGraphFindEdge(Graph &G) 
+//     {
+//       typedef typename Graph::NodeIt Node;
+//       typedef typename Graph::NodeIt NodeIt;
+
+//       G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
+//       G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));  
+//     }
+
+
+
+    /************* New GraphBase stuff **************/
+
+
+    /// \bug The nodes and edges are not allowed to inherit from the
+    /// same baseclass.
+
+    class BaseGraphItem {
     public:
-      /// Defalult constructor.
+      BaseGraphItem() {}
+      BaseGraphItem(Invalid) {}
 
-      /// Defalult constructor.
-      ///
-      StaticGraph() { }
-      ///Copy consructor.
+      // We explicitely list these:
+      BaseGraphItem(BaseGraphItem const&) {}
+      BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
 
-//       ///\todo It is not clear, what we expect from a copy constructor.
-//       ///E.g. How to assign the nodes/edges to each other? What about maps?
-//       StaticGraph(const StaticGraph& g) { }
+      bool operator==(BaseGraphItem) const { return false; }
+      bool operator!=(BaseGraphItem) const { return false; }
 
-      /// The base type of node iterators, 
-      /// or in other words, the trivial node iterator.
-
-      /// This is the base type of each node iterator,
-      /// thus each kind of node iterator converts to this.
-      /// More precisely each kind of node iterator should be inherited 
-      /// from the trivial node iterator.
-      class Node {
-      public:
-	/// Default constructor
-
-	/// @warning The default constructor sets the iterator
-	/// to an undefined value.
-	Node() { }
-	/// Copy constructor.
-
-	/// Copy constructor.
-	///
-	Node(const Node&) { }
-
-	/// Invalid constructor \& conversion.
-
-	/// This constructor initializes the iterator to be invalid.
-	/// \sa Invalid for more details.
-	Node(Invalid) { }
-	/// Equality operator
-
-	/// Two iterators are equal if and only if they point to the
-	/// same object or both are invalid.
-	bool operator==(Node) const { return true; }
-
-	/// Inequality operator
-	
-	/// \sa operator==(Node n)
-	///
-	bool operator!=(Node) const { return true; }
-
- 	///Comparison operator.
-
-	///This is a strict ordering between the nodes.
-	///
-	///This ordering can be different from the order in which NodeIt
-	///goes through the nodes.
-	///\todo Possibly we don't need it.
-	bool operator<(Node) const { return true; }
-      };
-    
-      /// This iterator goes through each node.
-
-      /// This iterator goes through each node.
-      /// Its usage is quite simple, for example you can count the number
-      /// of nodes in graph \c g of type \c Graph like this:
-      /// \code
-      /// int count=0;
-      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
-      /// \endcode
-      class NodeIt : public Node {
-      public:
-	/// Default constructor
-
-	/// @warning The default constructor sets the iterator
-	/// to an undefined value.
-	NodeIt() { }
-	/// Copy constructor.
-	
-	/// Copy constructor.
-	///
-	NodeIt(const NodeIt&) { }
-	/// Invalid constructor \& conversion.
-
-	/// Initialize the iterator to be invalid.
-	/// \sa Invalid for more details.
-	NodeIt(Invalid) { }
-	/// Sets the iterator to the first node.
-
-	/// Sets the iterator to the first node of \c g.
-	///
-	NodeIt(const StaticGraph& g) { }
-	/// Node -> NodeIt conversion.
-
-	/// Sets the iterator to the node of \c g pointed by the trivial 
-	/// iterator n.
-	/// This feature necessitates that each time we 
-	/// iterate the edge-set, the iteration order is the same.
-	NodeIt(const StaticGraph& g, const Node& n) { }
-	/// Next node.
-
-	/// Assign the iterator to the next node.
-	///
-	NodeIt& operator++() { return *this; }
-      };
-    
-    
-      /// The base type of the edge iterators.
-
-      /// The base type of the edge iterators.
-      ///
-      class Edge {
-      public:
-	/// Default constructor
-
-	/// @warning The default constructor sets the iterator
-	/// to an undefined value.
-	Edge() { }
-	/// Copy constructor.
-
-	/// Copy constructor.
-	///
-	Edge(const Edge&) { }
-	/// Initialize the iterator to be invalid.
-
-	/// Initialize the iterator to be invalid.
-	///
-	Edge(Invalid) { }
-	/// Equality operator
-
-	/// Two iterators are equal if and only if they point to the
-	/// same object or both are invalid.
-	bool operator==(Edge) const { return true; }
-	/// Inequality operator
-
-	/// \sa operator==(Node n)
-	///
-	bool operator!=(Edge) const { return true; }
- 	///Comparison operator.
-
-	///This is a strict ordering between the nodes.
-	///
-	///This ordering can be different from the order in which NodeIt
-	///goes through the nodes.
-	///\todo Possibly we don't need it.
- 	bool operator<(Edge) const { return true; }
-      };
-    
-      /// This iterator goes trough the outgoing edges of a node.
-
-      /// This iterator goes trough the \e outgoing edges of a certain node
-      /// of a graph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of outgoing edges of a node \c n
-      /// in graph \c g of type \c Graph as follows.
-      /// \code
-      /// int count=0;
-      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
-      /// \endcode
-    
-      class OutEdgeIt : public Edge {
-      public:
-	/// Default constructor
-
-	/// @warning The default constructor sets the iterator
-	/// to an undefined value.
-	OutEdgeIt() { }
-	/// Copy constructor.
-
-	/// Copy constructor.
-	///
-	OutEdgeIt(const OutEdgeIt&) { }
-	/// Initialize the iterator to be invalid.
-
-	/// Initialize the iterator to be invalid.
-	///
-	OutEdgeIt(Invalid) { }
-	/// This constructor sets the iterator to first outgoing edge.
-    
-	/// This constructor set the iterator to the first outgoing edge of
-	/// node
-	///@param n the node
-	///@param g the graph
-	OutEdgeIt(const StaticGraph& g, const Node& n) { }
-	/// Edge -> OutEdgeIt conversion
-
-	/// Sets the iterator to the value of the trivial iterator \c e.
-	/// This feature necessitates that each time we 
-	/// iterate the edge-set, the iteration order is the same.
-	OutEdgeIt(const StaticGraph& g, const Edge& e) { }
-	///Next outgoing edge
-	
-	/// Assign the iterator to the next 
-	/// outgoing edge of the corresponding node.
-	OutEdgeIt& operator++() { return *this; }
-      };
-
-      /// This iterator goes trough the incoming edges of a node.
-
-      /// This iterator goes trough the \e incoming edges of a certain node
-      /// of a graph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of outgoing edges of a node \c n
-      /// in graph \c g of type \c Graph as follows.
-      /// \code
-      /// int count=0;
-      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
-      /// \endcode
-
-      class InEdgeIt : public Edge {
-      public:
-	/// Default constructor
-
-	/// @warning The default constructor sets the iterator
-	/// to an undefined value.
-	InEdgeIt() { }
-	/// Copy constructor.
-
-	/// Copy constructor.
-	///
-	InEdgeIt(const InEdgeIt&) { }
-	/// Initialize the iterator to be invalid.
-
-	/// Initialize the iterator to be invalid.
-	///
-	InEdgeIt(Invalid) { }
-	/// This constructor sets the iterator to first incoming edge.
-    
-	/// This constructor set the iterator to the first incoming edge of
-	/// node
-	///@param n the node
-	///@param g the graph
-	InEdgeIt(const StaticGraph& g, const Node& n) { }
-	/// Edge -> InEdgeIt conversion
-
-	/// Sets the iterator to the value of the trivial iterator \c e.
-	/// This feature necessitates that each time we 
-	/// iterate the edge-set, the iteration order is the same.
-	InEdgeIt(const StaticGraph& g, const Edge& n) { }
-	/// Next incoming edge
-
-	/// Assign the iterator to the next inedge of the corresponding node.
-	///
-	InEdgeIt& operator++() { return *this; }
-      };
-      /// This iterator goes through each edge.
-
-      /// This iterator goes through each edge of a graph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of edges in a graph \c g of type \c Graph as follows:
-      /// \code
-      /// int count=0;
-      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
-      /// \endcode
-      class EdgeIt : public Edge {
-      public:
-	/// Default constructor
-
-	/// @warning The default constructor sets the iterator
-	/// to an undefined value.
-	EdgeIt() { }
-	/// Copy constructor.
-
-	/// Copy constructor.
-	///
-	EdgeIt(const EdgeIt&) { }
-	/// Initialize the iterator to be invalid.
-
-	/// Initialize the iterator to be invalid.
-	///
-	EdgeIt(Invalid) { }
-	/// This constructor sets the iterator to first edge.
-    
-	/// This constructor set the iterator to the first edge of
-	/// node
-	///@param g the graph
-	EdgeIt(const StaticGraph& g) { }
-	/// Edge -> EdgeIt conversion
-
-	/// Sets the iterator to the value of the trivial iterator \c e.
-	/// This feature necessitates that each time we 
-	/// iterate the edge-set, the iteration order is the same.
-	EdgeIt(const StaticGraph&, const Edge&) { } 
-    	///Next edge
-	
-	/// Assign the iterator to the next 
-	/// edge of the corresponding node.
-	EdgeIt& operator++() { return *this; }
-      };
-
-      /// First node of the graph.
-
-      /// \retval i the first node.
-      /// \return the first node.
-      ///
-      NodeIt& first(NodeIt& i) const { return i; }
-
-      /// The first incoming edge.
-
-      /// The first incoming edge.
-      ///
-      InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
-      /// The first outgoing edge.
-
-      /// The first outgoing edge.
-      ///
-      OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
-      /// The first edge of the Graph.
-
-      /// The first edge of the Graph.
-      ///
-      EdgeIt& first(EdgeIt& i) const { return i; }
-
-      ///Gives back the head node of an edge.
-
-      ///Gives back the head node of an edge.
-      ///
-      Node head(Edge) const { return INVALID; }
-      ///Gives back the tail node of an edge.
-
-      ///Gives back the tail node of an edge.
-      ///
-      Node tail(Edge) const { return INVALID; }
-  
-      ///Gives back the \e id of a node.
-
-      ///\warning Not all graph structures provide this feature.
-      ///
-      ///\todo Should each graph provide \c id?
-      int id(const Node&) const { return 0; }
-      ///Gives back the \e id of an edge.
-
-      ///\warning Not all graph structures provide this feature.
-      ///
-      ///\todo Should each graph provide \c id?
-      int id(const Edge&) const { return 0; }
-
-      ///\e
-      
-      ///\todo Should it be in the concept?
-      ///
-      int nodeNum() const { return 0; }
-      ///\e
-
-      ///\todo Should it be in the concept?
-      ///
-      int edgeNum() const { return 0; }
-
-
-      ///Reference map of the nodes to type \c T.
-
-      /// \ingroup skeletons
-      ///Reference map of the nodes to type \c T.
-      /// \sa Reference
-      /// \warning Making maps that can handle bool type (NodeMap<bool>)
-      /// needs some extra attention!
-      template<class T> class NodeMap : public ReferenceMap< Node, T >
-      {
-      public:
-
-	///\e
-	NodeMap(const StaticGraph&) { }
-	///\e
-	NodeMap(const StaticGraph&, T) { }
-
-	///Copy constructor
-	template<typename TT> NodeMap(const NodeMap<TT>&) { }
-	///Assignment operator
-	template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
-	{ return *this; }
-      };
-
-      ///Reference map of the edges to type \c T.
-
-      /// \ingroup skeletons
-      ///Reference map of the edges to type \c T.
-      /// \sa Reference
-      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
-      /// needs some extra attention!
-      template<class T> class EdgeMap
-	: public ReferenceMap<Edge,T>
-      {
-      public:
-
-	///\e
-	EdgeMap(const StaticGraph&) { }
-	///\e
-	EdgeMap(const StaticGraph&, T) { }
-    
-	///Copy constructor
-	template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
-	///Assignment operator
-	template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
-	{ return *this; }
-      };
+      // Technical requirement. Do we really need this?
+      bool operator<(BaseGraphItem) const { return false; }
     };
 
-    struct DummyType {
-      int value;
-      DummyType() {}
-      DummyType(int p) : value(p) {}
-      DummyType& operator=(int p) { value = p; return *this;}
+
+    /// A minimal GraphBase concept
+
+    /// This class describes a minimal concept which can be extended to a
+    /// full-featured graph with \ref GraphFactory.
+    class GraphBase {
+    public:
+
+      GraphBase() {}
+
+
+      /// \bug Nodes and Edges are comparable each other
+      
+      class Node : public BaseGraphItem {};
+      class Edge : public BaseGraphItem {};
+
+      // Graph operation
+      void firstNode(Node &n) const { }
+      void firstEdge(Edge &e) const { }
+
+      void firstOutEdge(Edge &e, Node) const { }
+      void firstInEdge(Edge &e, Node) const { }
+
+      void nextNode(Node &n) const { }
+      void nextEdge(Edge &e) const { }
+
+
+      // Question: isn't it reasonable if this methods have a Node
+      // parameter? Like this:
+      // Edge& nextOut(Edge &e, Node) const { return e; }
+      void nextOutEdge(Edge &e) const { }
+      void nextInEdge(Edge &e) const { }
+
+      Node head(Edge) const { return Node(); }
+      Node tail(Edge) const { return Node(); }
+      
+
+      // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
+      // concept?
+
+
+      // Maps.
+      //
+      // We need a special slimer concept which does not provide maps (it
+      // wouldn't be strictly slimer, cause for map-factory id() & friends
+      // a required...)
+
+      template<typename T>
+      class NodeMap : public GraphMap<Node, T, GraphBase> {};
+
+      template<typename T>
+      class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
     };
-    
-    ///\brief Checks whether \c G meets the
-    ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
-    template<class Graph> void checkCompileStaticGraph(Graph &G) 
-    {
-      typedef typename Graph::Node Node;
-      typedef typename Graph::NodeIt NodeIt;
-      typedef typename Graph::Edge Edge;
-      typedef typename Graph::EdgeIt EdgeIt;
-      typedef typename Graph::InEdgeIt InEdgeIt;
-      typedef typename Graph::OutEdgeIt OutEdgeIt;
-  
-      {
-	Node i; Node j(i); Node k(INVALID);
-	i=j;
-	bool b; b=true;
-	b=(i==INVALID); b=(i!=INVALID);
-	b=(i==j); b=(i!=j); b=(i<j);
-      }
-      {
-	NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
-	i=j;
-	j=G.first(i);
-	j=++i;
-	bool b; b=true;
-	b=(i==INVALID); b=(i!=INVALID);
-	Node n(i);
-	n=i;
-	b=(i==j); b=(i!=j); b=(i<j);
-	//Node ->NodeIt conversion
-	NodeIt ni(G,n);
-      }
-      {
-	Edge i; Edge j(i); Edge k(INVALID);
-	i=j;
-	bool b; b=true;
-	b=(i==INVALID); b=(i!=INVALID);
-	b=(i==j); b=(i!=j); b=(i<j);
-      }
-      {
-	EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
-	i=j;
-	j=G.first(i);
-	j=++i;
-	bool b; b=true;
-	b=(i==INVALID); b=(i!=INVALID);
-	Edge e(i);
-	e=i;
-	b=(i==j); b=(i!=j); b=(i<j);
-	//Edge ->EdgeIt conversion
-	EdgeIt ei(G,e);
-      }
-      {
-	Node n;
-	InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
-	i=j;
-	j=G.first(i,n);
-	j=++i;
-	bool b; b=true;
-	b=(i==INVALID); b=(i!=INVALID);
-	Edge e(i);
-	e=i;
-	b=(i==j); b=(i!=j); b=(i<j);
-	//Edge ->InEdgeIt conversion
-	InEdgeIt ei(G,e);
-      }
-      {
-	Node n;
-	OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
-	i=j;
-	j=G.first(i,n);
-	j=++i;
-	bool b; b=true;
-	b=(i==INVALID); b=(i!=INVALID);
-	Edge e(i);
-	e=i;
-	b=(i==j); b=(i!=j); b=(i<j);
-	//Edge ->OutEdgeIt conversion
-	OutEdgeIt ei(G,e);
-      }
-      {
-	Node n,m;
-	n=m=INVALID;
-	Edge e;
-	e=INVALID;
-	n=G.tail(e);
-	n=G.head(e);
-      }
-      // id tests
-      { Node n; int i=G.id(n); i=i; }
-      { Edge e; int i=G.id(e); i=i; }
-      //NodeMap tests
-      {
-	Node k;
-	typename Graph::template NodeMap<int> m(G);
-	//Const map
-	typename Graph::template NodeMap<int> const &cm = m;
-	//Inicialize with default value
-	typename Graph::template NodeMap<int> mdef(G,12);
-	//Copy
-	typename Graph::template NodeMap<int> mm(cm);
-	//Copy from another type
-	typename Graph::template NodeMap<double> dm(cm);
-	//Copy to more complex type
-	typename Graph::template NodeMap<DummyType> em(cm);
-	int v;
-	v=m[k]; m[k]=v; m.set(k,v);
-	v=cm[k];
-    
-	m=cm;  
-	dm=cm; //Copy from another type  
-	em=cm; //Copy to more complex type
-	{
-	  //Check the typedef's
-	  typename Graph::template NodeMap<int>::ValueType val;
-	  val=1;
-	  typename Graph::template NodeMap<int>::KeyType key;
-	  key = typename Graph::NodeIt(G);
-	}
-      }  
-      { //bool NodeMap
-	Node k;
-	typename Graph::template NodeMap<bool> m(G);
-	typename Graph::template NodeMap<bool> const &cm = m;  //Const map
-	//Inicialize with default value
-	typename Graph::template NodeMap<bool> mdef(G,12);
-	typename Graph::template NodeMap<bool> mm(cm);   //Copy
-	typename Graph::template NodeMap<int> dm(cm); //Copy from another type
-	bool v;
-	v=m[k]; m[k]=v; m.set(k,v);
-	v=cm[k];
-    
-	m=cm;  
-	dm=cm; //Copy from another type
-	m=dm; //Copy to another type
 
-	{
-	  //Check the typedef's
-	  typename Graph::template NodeMap<bool>::ValueType val;
-	  val=true;
-	  typename Graph::template NodeMap<bool>::KeyType key;
-	  key= typename Graph::NodeIt(G);
+
+
+    /**************** Concept checking classes ****************/
+
+    template<typename BGI>
+    struct BaseGraphItemConcept {
+      void constraints() {
+	BGI i1;
+	BGI i2 = i1;
+	BGI i3 = INVALID;
+	
+	i1 = i3;
+	if( i1 == i3 ) {
+	  if ( i2 != i3 && i3 < i2 )
+	    return;
 	}
       }
-      //EdgeMap tests
-      {
-	Edge k;
-	typename Graph::template EdgeMap<int> m(G);
-	typename Graph::template EdgeMap<int> const &cm = m;  //Const map
-	//Inicialize with default value
-	typename Graph::template EdgeMap<int> mdef(G,12);
-	typename Graph::template EdgeMap<int> mm(cm);   //Copy
-	typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
-	int v;
-	v=m[k]; m[k]=v; m.set(k,v);
-	v=cm[k];
-    
-	m=cm;  
-	dm=cm; //Copy from another type
-	{
-	  //Check the typedef's
-	  typename Graph::template EdgeMap<int>::ValueType val;
-	  val=1;
-	  typename Graph::template EdgeMap<int>::KeyType key;
-	  key= typename Graph::EdgeIt(G);
-	}
-      }  
-      { //bool EdgeMap
-	Edge k;
-	typename Graph::template EdgeMap<bool> m(G);
-	typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
-	//Inicialize with default value
-	typename Graph::template EdgeMap<bool> mdef(G,12);
-	typename Graph::template EdgeMap<bool> mm(cm);   //Copy
-	typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
-	bool v;
-	v=m[k]; m[k]=v; m.set(k,v);
-	v=cm[k];
-    
-	m=cm;  
-	dm=cm; //Copy from another type
-	m=dm; //Copy to another type
-	{
-	  //Check the typedef's
-	  typename Graph::template EdgeMap<bool>::ValueType val;
-	  val=true;
-	  typename Graph::template EdgeMap<bool>::KeyType key;
-	  key= typename Graph::EdgeIt(G);
-	}
-      }
-    }
-    
-    /// An empty non-static graph class.
-    
-    /// This class provides everything that \ref StaticGraph
-    /// with additional functionality which enables to build a
-    /// graph from scratch.
-    class ExtendableGraph : public StaticGraph
-    {
-    public:
-      /// Defalult constructor.
-
-      /// Defalult constructor.
-      ///
-      ExtendableGraph() { }
-      ///Add a new node to the graph.
-
-      /// \return the new node.
-      ///
-      Node addNode() { return INVALID; }
-      ///Add a new edge to the graph.
-
-      ///Add a new edge to the graph with tail node \c t
-      ///and head node \c h.
-      ///\return the new edge.
-      Edge addEdge(Node h, Node t) { return INVALID; }
-    
-      /// Resets the graph.
-
-      /// This function deletes all edges and nodes of the graph.
-      /// It also frees the memory allocated to store them.
-      /// \todo It might belong to \ref ErasableGraph.
-      void clear() { }
     };
 
     
-    ///\brief Checks whether \c G meets the
-    ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
-    template<class Graph> void checkCompileExtendableGraph(Graph &G) 
-    {
-      checkCompileStaticGraph(G);
+    
+    class StaticGraph 
+      :  virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
+    public:
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+    };
 
-      typedef typename Graph::Node Node;
-      typedef typename Graph::NodeIt NodeIt;
-      typedef typename Graph::Edge Edge;
-      typedef typename Graph::EdgeIt EdgeIt;
-      typedef typename Graph::InEdgeIt InEdgeIt;
-      typedef typename Graph::OutEdgeIt OutEdgeIt;
-  
-      Node n,m;
-      n=G.addNode();
-      m=G.addNode();
-      Edge e;
-      e=G.addEdge(n,m); 
-  
-      //  G.clear();
-    }
+    template <typename Graph>
+    struct StaticGraphConcept {
+      void constraints() {
+	function_requires<BaseGraphComponentConcept<Graph> >();
+	function_requires<IterableGraphComponentConcept<Graph> >();
+	function_requires<MappableGraphComponentConcept<Graph> >();
+      }
+      Graph& graph;
+    };
 
+    class ExtendableGraph 
+      :  virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
+    public:
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+    };
 
-    /// An empty erasable graph class.
-  
-    /// This class is an extension of \ref ExtendableGraph. It also makes it
-    /// possible to erase edges or nodes.
-    class ErasableGraph : public ExtendableGraph
-    {
+    template <typename Graph>
+    struct ExtendableGraphConcept {
+      void constraints() {
+	function_requires<StaticGraphConcept<Graph> >();
+	function_requires<ExtendableGraphComponentConcept<Graph> >();
+	function_requires<ClearableGraphComponentConcept<Graph> >();
+      }
+      Graph& graph;
+    };
+
+    class ErasableGraph 
+      :  virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
     public:
-      /// Defalult constructor.
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+    };
 
-      /// Defalult constructor.
-      ///
-      ErasableGraph() { }
-      /// Deletes a node.
+    template <typename Graph>
+    struct ErasableGraphConcept {
+      void constraints() {
+	function_requires<ExtendableGraphConcept<Graph> >();
+	function_requires<ErasableGraphComponentConcept<Graph> >();
+      }
+      Graph& graph;
+    };
 
-      /// Deletes node \c n node.
-      ///
-      void erase(Node n) { }
-      /// Deletes an edge.
-
-      /// Deletes edge \c e edge.
-      ///
-      void erase(Edge e) { }
-    };
-    
-    template<class Graph> void checkCompileGraphEraseEdge(Graph &G) 
-    {
-      typename Graph::Edge e;
-      G.erase(e);
-    }
-
-    template<class Graph> void checkCompileGraphEraseNode(Graph &G) 
-    {
-      typename Graph::Node n;
-      G.erase(n);
-    }
-
-    ///\brief Checks whether \c G meets the
-    ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
-    template<class Graph> void checkCompileErasableGraph(Graph &G) 
-    {
-      checkCompileExtendableGraph(G);
-      checkCompileGraphEraseNode(G);
-      checkCompileGraphEraseEdge(G);
-    }
-
-    ///Checks whether a graph has findEdge() member function.
-    
-    ///\todo findEdge() might be a global function.
-    ///
-    template<class Graph> void checkCompileGraphFindEdge(Graph &G) 
-    {
-      typedef typename Graph::NodeIt Node;
-      typedef typename Graph::NodeIt NodeIt;
-
-      G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
-      G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));  
-    }
- 
     // @}
   } //namespace skeleton  
 } //namespace lemon
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/skeletons/graph_component.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/skeletons/graph_component.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,827 @@
+/* -*- C++ -*-
+ * src/lemon/skeletons/graph_component.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, 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.
+ *
+ */
+
+///\ingroup skeletons
+///\file
+///\brief The graph components.
+
+
+#ifndef LEMON_SKELETON_GRAPH_COMPONENT_H
+#define LEMON_SKELETON_GRAPH_COMPONENT_H
+
+#include <lemon/invalid.h>
+#include <lemon/skeletons/maps.h>
+
+namespace lemon {
+  namespace skeleton {
+
+    /// An empty base graph class.
+  
+    /// This class provides the most minimal features of a graph structure.
+    /// All the graph concepts have to be conform to this base graph.
+
+    class BaseGraphComponent {
+    public:
+
+      typedef BaseGraphComponent Graph;
+      
+      /// Node class of the graph.
+
+      /// This class represents the Nodes of the graph. 
+      ///
+      class Node {
+      public:
+
+	/// Default constructor.
+
+	/// @warning The default constructor sets the iterator
+	/// to an undefined value.
+
+	Node() {}
+	/// Copy constructor.
+
+	/// Copy constructor.
+	///
+	Node(const Node&) {}
+
+	/// Invalid constructor \& conversion.
+
+	/// This constructor initializes the iterator to be invalid.
+	/// \sa Invalid for more details.
+	Node(Invalid) {}
+
+
+	Node& operator=(const Node&) { return *this;}
+
+	/// Equality operator.
+
+	/// Two iterators are equal if and only if they represents the
+	/// same node in the graph or both are invalid.
+	bool operator==(const Node&) { return true;}
+
+
+	/// Inequality operator.
+	
+	/// \sa operator==(const Node& n)
+	///
+	bool operator!=(const Node&) { return true;}
+
+ 	/// Comparison operator.
+
+	/// This is a strict ordering between the nodes.
+	///
+	/// This ordering can be different from the iterating order of nodes.
+	/// \todo Possibly we don't need it.
+	bool operator<(const Node&) { return true;}
+      };
+
+      /// Edge class of the graph.
+
+      /// This class represents the Edges of the graph. 
+      ///
+      class Edge {
+      public:
+
+	/// Default constructor.
+
+	/// @warning The default constructor sets the iterator
+	/// to an undefined value.
+
+	Edge() {}
+	/// Copy constructor.
+
+	/// Copy constructor.
+	///
+	Edge(const Edge&) {}
+
+	/// Invalid constructor \& conversion.
+
+	/// This constructor initializes the iterator to be invalid.
+	/// \sa Invalid for more details.
+	Edge(Invalid) {}
+
+
+	Edge& operator=(const Edge&) { return *this;}
+
+	/// Equality operator.
+
+	/// Two iterators are equal if and only if they represents the
+	/// same edge in the graph or both are invalid.
+	bool operator==(const Edge&) { return true;}
+
+
+	/// Inequality operator.
+	
+	/// \sa operator==(const Edge& n)
+	///
+	bool operator!=(const Edge&) { return true;}
+
+ 	/// Comparison operator.
+
+	/// This is a strict ordering between the edges.
+	///
+	/// This ordering can be different from the iterating order of edges.
+	/// \todo Possibly we don't need it.
+	bool operator<(const Edge&) { return true;}
+      };
+
+      ///Gives back the head node of an edge.
+
+      ///Gives back the head node of an edge.
+      ///
+      Node head(const Edge&) const { return INVALID;}
+
+      ///Gives back the tail node of an edge.
+
+      ///Gives back the tail node of an edge.
+      ///
+      Node tail(const Edge&) const { return INVALID;}
+    };
+
+    /// Concept check structure for BaseGraph.
+
+    /// Concept check structure for BaseGraph.
+    ///
+
+    template <typename Graph>
+    struct BaseGraphComponentConcept {
+      typedef typename Graph::Node Node;
+      typedef typename Graph::Edge Edge;
+      
+      void constraints() {
+	{
+	  Node ni; 
+	  Node nj(ni); 
+	  Node nk(INVALID);
+	  ni = nj;
+	  bool b; b = true;
+	  b = (ni == INVALID); b = (ni != INVALID);
+	  b = (ni==nj); b = (ni != nj); b=( ni < nj);
+	}
+	{
+	  Edge ei; 
+	  Edge ej(ei); 
+	  Edge ek(INVALID);
+	  ei = ej;
+	  bool b; b = true;
+	  b = (ei == INVALID); b = (ei != INVALID);
+	  b = (ei==ej); b = (ei != ej); b=( ei < ej);
+	}
+	{
+	  const Graph& const_graph = graph;
+	  Node n;
+	  Edge e;
+	  n = const_graph.tail(e);
+	  n = const_graph.head(e);
+	}      
+      }
+      
+      Graph& graph;
+    };
+
+    /// An empty iterable base graph class.
+  
+    /// This class provides beside the core graph features
+    /// core iterable interface for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+
+    class BaseIterableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      /// Gives back the first Node in the iterating order.
+      
+      /// Gives back the first Node in the iterating order.
+      ///     
+      void first(Node&) const {}
+
+      /// Gives back the next Node in the iterating order.
+      
+      /// Gives back the next Node in the iterating order.
+      ///     
+      void next(Node&) const {}
+
+      /// Gives back the first Edge in the iterating order.
+      
+      /// Gives back the first Edge in the iterating order.
+      ///     
+      void first(Edge&) const {}
+      /// Gives back the next Edge in the iterating order.
+      
+      /// Gives back the next Edge in the iterating order.
+      ///     
+      void next(Edge&) const {}
+
+
+      /// Gives back the first of the Edges point to the given Node.
+      
+      /// Gives back the first of the Edges point to the given Node.
+      ///     
+      void firstIn(Edge&, const Node&) const {}
+
+      /// Gives back the next of the Edges points to the given Node.
+
+
+      /// Gives back the next of the Edges points to the given Node.
+      ///
+      void nextIn(Edge&) const {}
+
+      /// Gives back the first of the Edges start from the given Node.
+      
+      /// Gives back the first of the Edges start from the given Node.
+      ///     
+      void firstOut(Edge&, const Node&) const {}
+
+      /// Gives back the next of the Edges start from the given Node.
+      
+      /// Gives back the next of the Edges start from the given Node.
+      ///     
+      void nextOut(Edge&) const {}
+    };
+
+
+    /// Concept check structure for IterableBaseGraph.
+
+    /// Concept check structure for IterableBaseGraph.
+    ///
+    template <typename Graph>
+    struct BaseIterableGraphComponentConcept {
+      
+      void constraints() { 
+	const Graph& const_graph = graph;
+	typename Graph::Node node;      
+	typename Graph::Edge edge;
+	{
+	  const_graph.first(node);
+	  const_graph.next(node);
+	}
+	{
+	  const_graph.first(edge);
+	  const_graph.next(edge);
+	}
+	{
+	  const_graph.firstIn(edge, node);
+	  const_graph.nextIn(edge);
+	}
+	{
+	  const_graph.firstOut(edge, node);
+	  const_graph.nextOut(edge);
+	}
+      }
+
+      Graph& graph;
+    };
+
+    /// An empty idable base graph class.
+  
+    /// This class provides beside the core graph features
+    /// core id functions for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    /// The id's are unique and immutable.
+
+    class IDableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      /// Gives back an unique integer id for the Node. 
+
+      /// Gives back an unique integer id for the Node. 
+      ///
+      int id(const Node&) const { return -1;}
+
+      /// Gives back an unique integer id for the Edge. 
+
+      /// Gives back an unique integer id for the Edge. 
+      ///
+      int id(const Edge&) const { return -1;}
+    };
+
+
+    /// Concept check structure for IdableBaseGraph.
+
+    /// Concept check structure for IdableBaseGraph.
+    ///
+    template <typename Graph>
+    struct IDableGraphComponentConcept {
+
+      void constraints() {
+	const Graph& const_graph = graph;
+	typename Graph::Node node;
+	int nid = const_graph.id(node);
+	nid = const_graph.id(node);
+	typename Graph::Edge edge;
+	int eid = const_graph.id(edge);
+	eid = const_graph.id(edge);
+      }
+
+      Graph& graph;
+    };
+
+
+    /// An empty max-idable base graph class.
+  
+    /// This class provides beside the core graph features
+    /// core max id functions for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    /// The id's are unique and immutable.
+    class MaxIDableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      /// Gives back an integer greater or equal to the maximum Node id. 
+
+      /// Gives back an integer greater or equal to the maximum Node id. 
+      ///
+      int maxEdgeId() const { return -1;}
+
+      /// Gives back an integer greater or equal to the maximum Edge id. 
+
+      /// Gives back an integer greater or equal to the maximum Edge id. 
+      ///
+      int maxNodeId() const { return -1;}
+    };
+
+    /// Concept check structure for MaxIdableBaseGraph.
+
+    /// Concept check structure for MaxIdableBaseGraph.
+    ///
+    template <typename Graph>
+    struct MaxIDableGraphComponentConcept {
+
+      void constraints() {
+	const Graph& const_graph = graph;
+	int nid = const_graph.maxEdgeId();
+	ignore_unused_variable_warning(nid);
+	int eid = const_graph.maxNodeId();
+	ignore_unused_variable_warning(eid);
+      }
+
+      Graph& graph;
+    };
+
+    /// An empty extendable base graph class.
+  
+    /// This class provides beside the core graph features
+    /// core graph extend interface for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      /// Adds a new Node to the graph.
+
+      /// Adds a new Node to the graph.
+      ///
+      Node addNode() {
+	return INVALID;
+      }
+    
+      /// Adds a new Edge connects the two Nodes to the graph.
+
+      /// Adds a new Edge connects the two Nodes to the graph.
+      ///
+      Edge addEdge(const Node& from, const Node& to) {
+	return INVALID;
+      }
+
+    };
+
+    /// Concept check structure for ExtendableBaseGraph.
+
+    /// Concept check structure for ExtendableBaseGraph.
+    ///
+    template <typename Graph>
+    struct BaseExtendableGraphComponentConcept {
+      void constraints() {
+	typename Graph::Node node_a, node_b;
+	node_a = graph.addNode();
+	typename Graph::Edge edge;
+	edge = graph.addEdge(node_a, node_b);
+      }
+
+      Graph& graph;
+    };
+
+    /// An empty erasable base graph class.
+  
+    /// This class provides beside the core graph features
+    /// core erase functions for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    class BaseErasableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      /// Erase a Node from the graph.
+      
+      /// Erase a Node from the graph. This function should not
+      /// erase edges connecting to the Node.
+      void erase(const Node&) {}    
+
+      /// Erase an Edge from the graph.
+
+      /// Erase an Edge from the graph.
+      ///
+      void erase(const Edge&) {}
+
+    };
+
+    /// Concept check structure for ErasableBaseGraph.
+
+    /// Concept check structure for ErasableBaseGraph.
+    ///
+    template <typename Graph>
+    struct BaseErasableGraphComponentConcept {
+      void constraints() {
+	typename Graph::Node node;
+	graph.erase(node);
+	typename Graph::Edge edge;
+	graph.erase(edge);
+      }
+
+      Graph& graph;
+    };
+
+    /// An empty clearable base graph class.
+  
+    /// This class provides beside the core graph features
+    /// core clear functions for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    class BaseClearableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      /// Erase all the Nodes and Edges from the graph.
+
+      /// Erase all the Nodes and Edges from the graph.
+      ///
+      void clear() {}    
+    };
+
+    /// Concept check function for ErasableBaseGraph.
+
+    /// Concept check function for ErasableBaseGraph.
+    ///
+    template <typename Graph>
+    struct BaseClearableGraphComponentConcept {
+      void constraints() {
+	graph.clear();
+      }
+
+      Graph& graph;
+    };
+
+
+    class IterableGraphComponent : virtual public BaseGraphComponent {
+
+    public:
+    
+      typedef IterableGraphComponent Graph;
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      class NodeIt : public Node {
+      public:
+	NodeIt() {}
+	NodeIt(Invalid) {}
+	NodeIt(const Graph&) {}
+
+	NodeIt& operator++() { return *this; }
+	//	Node operator*() const { return INVALID; }
+
+	bool operator==(const NodeIt&) { return true;}
+	bool operator!=(const NodeIt&) { return true;}
+      };
+
+      class EdgeIt : public Edge {
+      public:
+	EdgeIt() {}
+	EdgeIt(Invalid) {}
+	EdgeIt(const Graph&) {}
+
+	EdgeIt& operator++() { return *this; }
+	//	Edge operator*() const { return INVALID; }
+
+	bool operator==(const EdgeIt&) { return true;}
+	bool operator!=(const EdgeIt&) { return true;}
+      };
+
+      class InEdgeIt : public Edge {
+      public:
+	InEdgeIt() {}
+	InEdgeIt(Invalid) {}
+	InEdgeIt(const Graph&, const Node&) {}
+
+	InEdgeIt& operator++() { return *this; }
+	//	Edge operator*() const { return INVALID; }
+
+	bool operator==(const InEdgeIt&) { return true;}
+	bool operator!=(const InEdgeIt&) { return true;}
+      };
+
+      class OutEdgeIt : public Edge {
+      public:
+	OutEdgeIt() {}
+	OutEdgeIt(Invalid) {}
+	OutEdgeIt(const Graph&, const Node&) {}
+
+	OutEdgeIt& operator++() { return *this; }
+	//	Edge operator*() const { return INVALID; }
+
+	bool operator==(const OutEdgeIt&) { return true;}
+	bool operator!=(const OutEdgeIt&) { return true;}
+      };
+
+    };
+    
+    template <typename Graph> 
+    struct IterableGraphComponentConcept {
+
+      void constraints() {
+  
+	typedef typename Graph::Node Node;
+	typedef typename Graph::NodeIt NodeIt;
+	typedef typename Graph::Edge Edge;
+	typedef typename Graph::EdgeIt EdgeIt;
+	typedef typename Graph::InEdgeIt InEdgeIt;
+	typedef typename Graph::OutEdgeIt OutEdgeIt;
+  
+	{
+	  NodeIt it; 
+	  NodeIt jt(it); 
+	  NodeIt kt(INVALID); 
+	  NodeIt lt(graph);
+	  it = jt;
+	  jt = ++it;
+	  bool b;
+	  b = (it == INVALID); 
+	  b = (it != INVALID);
+	  b = (it == jt); 
+	  b = (it != jt);
+	  Node node = it;
+	  node = it;
+	}
+	{
+	  EdgeIt it; 
+	  EdgeIt jt(it); 
+	  EdgeIt kt(INVALID); 
+	  EdgeIt lt(graph);
+	  it = jt;
+	  jt = ++it;
+	  bool b;
+	  b = (it == INVALID); 
+	  b = (it != INVALID);
+	  b = (it == jt); 
+	  b = (it != jt);
+	  Edge edge = it;
+	  edge = it;
+	}
+	{
+	  InEdgeIt it; 
+	  InEdgeIt jt(it); 
+	  InEdgeIt kt(INVALID); 
+	  Node node;
+	  InEdgeIt lt(graph, node);
+	  it = jt;
+	  jt = ++it;
+	  bool b;
+	  b = (it == INVALID); 
+	  b = (it != INVALID);
+	  b = (it == jt); 
+	  b = (it != jt);
+	  Edge edge = it;
+	  edge = it;
+	}
+	{
+	  OutEdgeIt it; 
+	  OutEdgeIt jt(it); 
+	  OutEdgeIt kt(INVALID); 
+	  Node node;
+	  OutEdgeIt lt(graph, node);
+	  it = jt;
+	  jt = ++it;
+	  bool b;
+	  b = (it == INVALID); 
+	  b = (it != INVALID);
+	  b = (it == jt); 
+	  b = (it != jt);
+	  Edge edge = it;
+	  edge = it;
+	}
+      }
+      Graph& graph;
+    };
+
+
+    class IdMappableGraphComponent : virtual public BaseGraphComponent {
+
+      typedef IdMappableGraphComponent Graph;
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+    public:
+
+      class NodeIdMap : public ReadMap<Node, int> {
+      public:
+	NodeIdMap(const Graph&) {}
+	int maxId() const { return -1;}
+      };
+
+      class EdgeIdMap : public ReadMap<Edge, int> {
+      public:
+	EdgeIdMap(const Graph&) {}
+	int maxId() const { return -1;}
+      };
+
+    };
+    
+    template <typename Graph>
+    struct IdMappableGraphComponentConcept {
+      void constraints() {	
+	{
+	  typedef typename Graph::EdgeIdMap EdgeIdMap;
+	  function_requires<ReadMapConcept<EdgeIdMap> >();
+	  EdgeIdMap edge_map(graph);
+	  int n = edge_map.maxId();
+	  ignore_unused_variable_warning(n);
+	}
+	{
+	  typedef typename Graph::NodeIdMap NodeIdMap;
+	  function_requires<ReadMapConcept<NodeIdMap> >();
+	  NodeIdMap node_map(graph);
+	  int n = node_map.maxId();
+	  ignore_unused_variable_warning(n);
+	}
+      }
+      Graph& graph;
+    };
+
+
+    class MappableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef MappableGraphComponent Graph;
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      template <typename Value>
+      class NodeMap : public ReferenceMap<Node, Value> {
+      public:
+	NodeMap(const Graph&) {}
+	NodeMap(const Graph&, const Value&) {}
+	NodeMap(const NodeMap&) {}
+
+	NodeMap& operator=(const NodeMap&) { return *this;}
+	
+      };
+
+      template <typename Value>
+      class EdgeMap : public ReferenceMap<Edge, Value> {
+      public:
+	EdgeMap(const Graph&) {}
+	EdgeMap(const Graph&, const Value&) {}
+	EdgeMap(const EdgeMap&) {}
+
+	EdgeMap& operator=(const EdgeMap&) { return *this;}
+	
+      };
+
+    };
+
+    template <typename Graph>
+    struct MappableGraphComponentConcept {
+
+      struct Type {
+	int value;
+	Type() : value(0) {}
+	Type(int _v) : value(_v) {}
+      };
+
+      void constraints() {
+	{ // int map test
+	  typedef typename Graph::template NodeMap<int> IntNodeMap;
+	  function_requires<GraphMapConcept<IntNodeMap,Graph> >();
+	} { // bool map test
+	  typedef typename Graph::template NodeMap<bool> BoolNodeMap;
+	  function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
+	} { // Type map test
+	  typedef typename Graph::template NodeMap<Type> TypeNodeMap;
+	  function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
+	} 
+
+	{ // int map test
+	  typedef typename Graph::template EdgeMap<int> IntEdgeMap;
+	  function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
+	} { // bool map test
+	  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
+	  function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
+	} { // Type map test
+	  typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
+	  function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
+	} 
+      }
+
+      Graph& graph;
+    };
+
+
+    class ExtendableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef ExtendableGraphComponent Graph;
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      Node addNode() {
+	return INVALID;
+      }
+    
+      Edge addEdge(const Node& from, const Node& to) {
+	return INVALID;
+      }
+
+    };
+
+    template <typename Graph>
+    struct ExtendableGraphComponentConcept {
+      void constraints() {
+	typename Graph::Node node_a, node_b;
+	node_a = graph.addNode();
+	typename Graph::Edge edge;
+	edge = graph.addEdge(node_a, node_b);      
+      }
+      Graph& graph;
+    };
+
+    class ErasableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef ErasableGraphComponent Graph;
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      void erase(const Node&) {}    
+      void erase(const Edge&) {}
+
+    };
+
+    template <typename Graph>
+    struct ErasableGraphComponentConcept {
+      void constraints() {
+	typename Graph::Node node;
+	graph.erase(node);
+	typename Graph::Edge edge;
+	graph.erase(edge);      
+      }
+
+      Graph& graph;
+    };
+
+    class ClearableGraphComponent : virtual public BaseGraphComponent {
+    public:
+
+      typedef ClearableGraphComponent Graph;
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+
+      void clear() {}    
+
+    };
+
+    template <typename Graph>
+    struct ClearableGraphComponentConcept {
+      void constraints() {
+	graph.clear();
+      }
+      Graph& graph;
+    };
+
+  }
+
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/skeletons/maps.h
--- a/src/lemon/skeletons/maps.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/skeletons/maps.h	Wed Oct 27 22:38:50 2004 +0000
@@ -17,6 +17,8 @@
 #ifndef LEMON_MAPSKELETON_H
 #define LEMON_MAPSKELETON_H
 
+#include <lemon/concept_check.h>
+
 ///\ingroup skeletons
 ///\file
 ///\brief Map concepts checking classes for testing and documenting.
@@ -113,6 +115,130 @@
       ReferenceMap() {}
     };
 
+
+    template<typename Item, typename T, typename Graph>
+    class GraphMap : public ReadWriteMap<Item, T> {
+      // I really, really don't like the idea that every graph should have
+      // reference maps! --klao
+
+    private:
+      // We state explicitly that graph maps have no default constructor?
+      GraphMap();
+
+    public:
+      explicit GraphMap(Graph const&) {}
+      // value for initializing
+      GraphMap(Graph const&, T) {}
+
+      // this probably should be required:
+      GraphMap(GraphMap const&) {}
+      GraphMap& operator=(GraphMap const&) { return *this; }
+
+      // but this is a absolute no-op! We should provide a more generic
+      // graph-map-copy operation.
+      //
+      // template<typename TT>
+      // GraphMap(GraphMap<TT> const&);
+      //
+      // template<typename TT>
+      // GraphMap& operator=(const GraphMap<TT>&);
+    };
+
+
+    /****************  Concept-checking classes  ****************/
+
+    template<typename ReadMap>
+    struct ReadMapConcept {
+      typedef typename ReadMap::KeyType KeyType;
+      typedef typename ReadMap::ValueType ValueType;
+
+      void constraints() {
+	// No constraints for constructor.
+
+	// What are the requirement for the ValueType?
+	// CopyConstructible? Assignable? None of these?
+	ValueType v = m[k];
+	v = m[k];
+
+	// FIXME:
+	ignore_unused_variable_warning(v);
+      }
+
+      ReadMap m;
+      KeyType k;
+    };
+
+    template<typename WriteMap>
+    struct WriteMapConcept {
+      typedef typename WriteMap::KeyType KeyType;
+      typedef typename WriteMap::ValueType ValueType;
+
+      void constraints() {
+	// No constraints for constructor.
+
+	m.set(k, v);
+      }
+
+      WriteMap m;
+      KeyType k;
+      ValueType v;
+    };
+
+    template<typename ReadWriteMap>
+    struct ReadWriteMapConcept {
+      void constraints() {
+	function_requires< ReadMapConcept<ReadWriteMap> >();
+	function_requires< WriteMapConcept<ReadWriteMap> >();
+      }
+    };
+
+    template<typename ReferenceMap>
+    struct ReferenceMapConcept {
+      typedef typename ReferenceMap::KeyType KeyType;
+      typedef typename ReferenceMap::ValueType ValueType;
+      typedef typename ReferenceMap::ReferenceType ReferenceType;
+
+      // What for is this?
+      typedef typename ReferenceMap::ConstReferenceType ConstReferenceType;
+
+      void constraints() {
+	function_requires< ReadWriteMapConcept<ReferenceMap> >();
+
+	m[k] = v;
+	// Or should we require real reference?
+	// Like this:
+	// ValueType &vv = m[k];
+	// ignore_unused_variable_warning(vv);
+      }
+
+      ReferenceMap m;
+      KeyType k;
+      ValueType v;
+    };
+
+    /// \todo GraphMapConceptCheck
+
+    template<typename GraphMap, typename Graph>
+    struct GraphMapConcept {
+      void constraints() {
+	function_requires< ReadWriteMapConcept<GraphMap> >();
+	// Construction with a graph parameter
+	GraphMap a(g);
+	// Ctor with a graph and a default value parameter
+	GraphMap a2(g,t);
+	// Copy ctor. Do we need it?
+	GraphMap b=c;
+	// Copy operator. Do we need it?
+	a=b;
+
+	ignore_unused_variable_warning(a2);
+      }
+      const GraphMap &c;
+      const Graph &g;
+      const typename GraphMap::ValueType &t;
+    };
+    
+
     // @}
 
   } //namespace skeleton
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/smart_graph.h
--- a/src/lemon/smart_graph.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/smart_graph.h	Wed Oct 27 22:38:50 2004 +0000
@@ -22,22 +22,28 @@
 ///\brief SmartGraph and SymSmartGraph classes.
 
 #include <vector>
-#include <climits>
 
 #include <lemon/invalid.h>
 
+#include <lemon/erasable_graph_extender.h>
+#include <lemon/clearable_graph_extender.h>
+#include <lemon/extendable_graph_extender.h>
 
-#include <lemon/array_map.h>
+#include <lemon/idmappable_graph_extender.h>
 
-#include <lemon/map_registry.h>
+#include <lemon/iterable_graph_extender.h>
 
-#include <lemon/map_defines.h>
+#include <lemon/alteration_observer_registry.h>
+#include <lemon/default_map.h>
+
+
+#include <lemon/graph_utils.h>
+
 
 namespace lemon {
 
-/// \addtogroup graphs
-/// @{
-//  class SymSmartGraph;
+  /// \addtogroup graphs
+  /// @{
 
   ///A smart graph class.
 
@@ -56,7 +62,7 @@
   ///Of course it should be used as a stack. (Maybe X is not necessary.)
   ///
   ///\author Alpar Juttner
-  class SmartGraph {
+  class SmartGraphBase {
 
     struct NodeT 
     {
@@ -77,25 +83,16 @@
     
   public:
 
-    typedef SmartGraph Graph;
+    typedef SmartGraphBase Graph;
 
     class Node;
     class Edge;
 
-    class NodeIt;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-    
-    // Create map registries.
-    CREATE_MAP_REGISTRIES;
-    // Create node and edge maps.
-    CREATE_MAPS(ArrayMap);
     
   public:
 
-    SmartGraph() : nodes(), edges() { }
-    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
+    SmartGraphBase() : nodes(), edges() { }
+    SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
     
     ///Number of nodes.
     int nodeNum() const { return nodes.size(); }
@@ -116,15 +113,6 @@
     Node tail(Edge e) const { return edges[e.n].tail; }
     Node head(Edge e) const { return edges[e.n].head; }
 
-    NodeIt& first(NodeIt& v) const { 
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
-
     /// Node ID.
     
     /// The ID of a valid Node is a nonnegative integer not greater than
@@ -147,9 +135,6 @@
     Node addNode() {
       Node n; n.n=nodes.size();
       nodes.push_back(NodeT()); //FIXME: Hmmm...
-
-      
-      node_maps.add(n);
       return n;
     }
     
@@ -160,8 +145,6 @@
       edges[e.n].next_in=nodes[v.n].first_in;
       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
 
-      edge_maps.add(e);
-
       return e;
     }
 
@@ -182,24 +165,16 @@
     }
     
     void clear() {
-      edge_maps.clear();
       edges.clear();
-      node_maps.clear();
       nodes.clear();
     }
 
+
     class Node {
-      friend class SmartGraph;
-      template <typename T> friend class NodeMap;
-      
-      friend class Edge;
-      friend class OutEdgeIt;
-      friend class InEdgeIt;
-      friend class SymEdge;
+      friend class SmartGraphBase;
 
     protected:
       int n;
-      friend int SmartGraph::id(Node v); 
       Node(int nn) {n=nn;}
     public:
       Node() {}
@@ -207,529 +182,77 @@
       bool operator==(const Node i) const {return n==i.n;}
       bool operator!=(const Node i) const {return n!=i.n;}
       bool operator<(const Node i) const {return n<i.n;}
-      //      ///Validity check
-      //      operator bool() { return n!=-1; }
     };
     
-    class NodeIt : public Node {
-      const SmartGraph *G;
-      friend class SmartGraph;
-    public:
-      NodeIt() : Node() { }
-      NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
-      NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
-      NodeIt &operator++() {
-	n=(n+2)%(G->nodes.size()+1)-1; 
-	return *this; 
-      }
-//       ///Validity check
-//       operator bool() { return Node::operator bool(); }      
-    };
 
     class Edge {
-      friend class SmartGraph;
-      template <typename T> friend class EdgeMap;
+      friend class SmartGraphBase;
 
-      friend class SymSmartGraph;
-      
-      friend class Node;
-      friend class NodeIt;
     protected:
       int n;
-      friend int SmartGraph::id(Edge e);
       Edge(int nn) {n=nn;}
     public:
-      /// An Edge with id \c n.
-
       Edge() { }
       Edge (Invalid) { n=-1; }
       bool operator==(const Edge i) const {return n==i.n;}
       bool operator!=(const Edge i) const {return n!=i.n;}
       bool operator<(const Edge i) const {return n<i.n;}
-//       ///Validity check
-//       operator bool() { return n!=-1; }
+    };
 
-      ///Set the edge to that have ID \c ID.
-      void setToId(int id) { n=id; }
-   };
+    void first(Node& node) const {
+      node.n = nodes.size() - 1;
+    }
+
+    static void next(Node& node) {
+      --node.n;
+    }
+
+    void first(Edge& edge) const {
+      edge.n = edges.size() - 1;
+    }
+
+    static void next(Edge& edge) {
+      --edge.n;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge.n = nodes[node.n].first_out;
+    }
+
+    void nextOut(Edge& edge) const {
+      edge.n = edges[edge.n].next_out;
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge.n = nodes[node.n].first_in;
+    }
     
-    class EdgeIt : public Edge {
-      const SmartGraph *G;
-      friend class SmartGraph;
-    public:
-      EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
-      EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      EdgeIt (Invalid i) : Edge(i) { }
-      EdgeIt() : Edge() { }
-      EdgeIt &operator++() { --n; return *this; }
-//       ///Validity check
-//       operator bool() { return Edge::operator bool(); }      
-    };
-    
-    class OutEdgeIt : public Edge {
-      const SmartGraph *G;
-      friend class SmartGraph;
-    public: 
-      OutEdgeIt() : Edge() { }
-      OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      OutEdgeIt (Invalid i) : Edge(i) { }
-
-      OutEdgeIt(const SmartGraph& _G,const Node v)
-	: Edge(_G.nodes[v.n].first_out), G(&_G) {}
-      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
-//       ///Validity check
-//       operator bool() { return Edge::operator bool(); }      
-    };
-    
-    class InEdgeIt : public Edge {
-      const SmartGraph *G;
-      friend class SmartGraph;
-    public: 
-      InEdgeIt() : Edge() { }
-      InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
-      InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const SmartGraph& _G,Node v)
-	: Edge(_G.nodes[v.n].first_in), G(&_G) { }
-      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
-//       ///Validity check
-//       operator bool() { return Edge::operator bool(); }      
-    };
+    void nextIn(Edge& edge) const {
+      edge.n = edges[edge.n].next_in;
+    }
 
   };
 
+  typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
+  typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
+  typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase;
+  typedef DefaultMappableGraphExtender<IdMappableSmartGraphBase> MappableSmartGraphBase;
+  typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
+  typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
 
+  typedef ClearableSmartGraphBase SmartGraph;
 
-  class SymSmartGraph : public SmartGraph {
-    typedef SmartGraph Parent;
-  public:
 
-    typedef SymSmartGraph Graph;
+  template <>
+  int countNodes<SmartGraph>(const SmartGraph& graph) {
+    return graph.nodeNum();
+  }
 
-    typedef SmartGraph::Node Node;
-    typedef SmartGraph::NodeIt NodeIt;
+  template <>
+  int countEdges<SmartGraph>(const SmartGraph& graph) {
+    return graph.edgeNum();
+  }
 
-    class SymEdge;
-    class SymEdgeIt;
-
-    class Edge;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-
-    template <typename Value>
-    class NodeMap : public Parent::NodeMap<Value> {      
-    public:
-      NodeMap(const SymSmartGraph& g) 
-	: SymSmartGraph::Parent::NodeMap<Value>(g) {}
-      NodeMap(const SymSmartGraph& g, Value v) 
-	: SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
-      template<typename TT> 
-      NodeMap(const NodeMap<TT>& copy) 
-	: SymSmartGraph::Parent::NodeMap<Value>(copy) { }            
-    };
-
-    template <typename Value>
-    class SymEdgeMap : public Parent::EdgeMap<Value> {
-    public:
-      typedef SymEdge KeyType;
-
-      SymEdgeMap(const SymSmartGraph& g) 
-	: SymSmartGraph::Parent::EdgeMap<Value>(g) {}
-      SymEdgeMap(const SymSmartGraph& g, Value v) 
-	: SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
-      template<typename TT> 
-      SymEdgeMap(const SymEdgeMap<TT>& copy) 
-	: SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
-      
-    };
-
-    // Create edge map registry.
-    CREATE_EDGE_MAP_REGISTRY;
-    // Create edge maps.
-    CREATE_EDGE_MAP(ArrayMap);
-
-    class Edge {
-      friend class SymSmartGraph;
-      friend class SymSmartGraph::EdgeIt;
-      friend class SymSmartGraph::OutEdgeIt;
-      friend class SymSmartGraph::InEdgeIt;
-      
-    protected:
-      int id;
-
-      Edge(int pid) { id = pid; }
-
-    public:
-      /// An Edge with id \c n.
-
-      Edge() { }
-      Edge (Invalid) { id = -1; }
-
-      operator SymEdge(){ return SymEdge(id >> 1);}
-      
-      bool operator==(const Edge i) const {return id == i.id;}
-      bool operator!=(const Edge i) const {return id != i.id;}
-      bool operator<(const Edge i) const {return id < i.id;}
-      //      ///Validity check
-      //      operator bool() { return n!=-1; }
-    };
-
-    class SymEdge : public SmartGraph::Edge {
-      friend class SymSmartGraph;
-      friend class SymSmartGraph::Edge;
-      typedef SmartGraph::Edge Parent;
-
-    protected:      
-      SymEdge(int pid) : Parent(pid) {}
-    public:
-
-      SymEdge() { }
-      SymEdge(const SmartGraph::Edge& i) : Parent(i) {} 
-      SymEdge (Invalid) : Parent(INVALID) {}
-
-    };
-
-    class OutEdgeIt {
-      Parent::OutEdgeIt out;
-      Parent::InEdgeIt in;      
-    public: 
-      OutEdgeIt() {}
-      OutEdgeIt(const SymSmartGraph& g, Edge e) { 
-	if ((e.id & 1) == 0) {	
-	  out = Parent::OutEdgeIt(g, SymEdge(e));
-	  in = Parent::InEdgeIt(g, g.tail(e));
-	} else {
-	  out = Parent::OutEdgeIt(INVALID);
-	  in = Parent::InEdgeIt(g, SymEdge(e));
-	}
-      }
-      OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
-
-      OutEdgeIt(const SymSmartGraph& g, const Node v)
-	: out(g, v), in(g, v) {}
-      OutEdgeIt &operator++() { 
-	if (out != INVALID) {
-	  ++out;
-	} else {
-	  ++in;
-	}
-	return *this; 
-      }
-
-      operator Edge() const {
-	if (out == INVALID && in == INVALID) return INVALID;
-	return out != INVALID ? forward(out) : backward(in);
-      }
-
-      bool operator==(const Edge i) const {return Edge(*this) == i;}
-      bool operator!=(const Edge i) const {return Edge(*this) != i;}
-      bool operator<(const Edge i) const {return Edge(*this) < i;}
-    };
-
-    class InEdgeIt {
-      Parent::OutEdgeIt out;
-      Parent::InEdgeIt in;      
-    public: 
-      InEdgeIt() {}
-      InEdgeIt(const SymSmartGraph& g, Edge e) { 
-	if ((e.id & 1) == 0) {	
-	  out = Parent::OutEdgeIt(g, SymEdge(e));
-	  in = Parent::InEdgeIt(g, g.tail(e));
-	} else {
-	  out = Parent::OutEdgeIt(INVALID);
-	  in = Parent::InEdgeIt(g, SymEdge(e));
-	}
-      }
-      InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
-
-      InEdgeIt(const SymSmartGraph& g, const Node v)
-	: out(g, v), in(g, v) {}
-
-      InEdgeIt &operator++() { 
-	if (out != INVALID) {
-	  ++out;
-	} else {
-	  ++in;
-	}
-	return *this; 
-      }
-
-      operator Edge() const {
-	if (out == INVALID && in == INVALID) return INVALID;
-	return out != INVALID ? backward(out) : forward(in);
-      }
-
-      bool operator==(const Edge i) const {return Edge(*this) == i;}
-      bool operator!=(const Edge i) const {return Edge(*this) != i;}
-      bool operator<(const Edge i) const {return Edge(*this) < i;}
-    };
-
-    class SymEdgeIt : public Parent::EdgeIt {
-
-    public:
-      SymEdgeIt() {}
-
-      SymEdgeIt(const SymSmartGraph& g) 
-	: SymSmartGraph::Parent::EdgeIt(g) {}
-
-      SymEdgeIt(const SymSmartGraph& g, SymEdge e) 
-	: SymSmartGraph::Parent::EdgeIt(g, e) {}
-
-      SymEdgeIt(Invalid i) 
-	: SymSmartGraph::Parent::EdgeIt(INVALID) {}
-
-      SymEdgeIt& operator++() {
-	SymSmartGraph::Parent::EdgeIt::operator++();
-	return *this;
-      }
-
-      operator SymEdge() const {
-	return SymEdge
-	  (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
-      }
-      bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
-      bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
-      bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
-    };
-
-    class EdgeIt {
-      SymEdgeIt it;
-      bool fw;
-    public:
-      EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
-      EdgeIt (Invalid i) : it(i) { }
-      EdgeIt(const SymSmartGraph& g, Edge e) 
-	: it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
-      EdgeIt() { }
-      EdgeIt& operator++() {
-	fw = !fw;
-	if (fw) ++it;
-	return *this;
-      }
-      operator Edge() const {
-	if (it == INVALID) return INVALID;
-	return fw ? forward(it) : backward(it);
-      }
-      bool operator==(const Edge i) const {return Edge(*this) == i;}
-      bool operator!=(const Edge i) const {return Edge(*this) != i;}
-      bool operator<(const Edge i) const {return Edge(*this) < i;}
-
-    };
-
-    ///Number of nodes.
-    int nodeNum() const { return Parent::nodeNum(); }
-    ///Number of edges.
-    int edgeNum() const { return 2*Parent::edgeNum(); }
-    ///Number of symmetric edges.
-    int symEdgeNum() const { return Parent::edgeNum(); }
-
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
-    int maxNodeId() const { return Parent::maxNodeId(); } 
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
-    int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
-    /// Maximum symmetric edge ID.
-    
-    /// Maximum symmetric edge ID.
-    ///\sa id(SymEdge)
-    int maxSymEdgeId() const { return Parent::maxEdgeId(); }
-
-
-    Node tail(Edge e) const { 
-      return (e.id & 1) == 0 ? 
-	Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); 
-    }
-
-    Node head(Edge e) const { 
-      return (e.id & 1) == 0 ? 
-	Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); 
-    }
-
-    Node tail(SymEdge e) const { 
-      return Parent::tail(e); 
-    }
-
-    Node head(SymEdge e) const { 
-      return Parent::head(e); 
-    }
-
-    NodeIt& first(NodeIt& v) const { 
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    SymEdgeIt& first(SymEdgeIt& e) const {
-      e=SymEdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
-
-    /// Node ID.
-    
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    ///\return The ID of the node \c v. 
-    static int id(Node v) { return Parent::id(v); }
-    /// Edge ID.
-    
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.id; }
-
-    /// The ID of a valid SymEdge is a nonnegative integer not greater than
-    /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
-    ///
-    /// The ID of the \ref INVALID symmetric edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(SymEdge e) { return Parent::id(e); }
-
-    /// Adds a new node to the graph.
-
-    /// \warning It adds the new node to the front of the list.
-    /// (i.e. the lastly added node becomes the first.)
-    Node addNode() {
-      return Parent::addNode();
-    }
-    
-    SymEdge addEdge(Node u, Node v) {
-      SymEdge se = Parent::addEdge(u, v);
-      edge_maps.add(forward(se));
-      edge_maps.add(backward(se));
-      return se;
-    }
-    
-    /// Finds an edge between two nodes.
-
-    /// Finds an edge from node \c u to node \c v.
-    ///
-    /// If \c prev is \ref INVALID (this is the default value), then
-    /// It finds the first edge from \c u to \c v. Otherwise it looks for
-    /// the next edge from \c u to \c v after \c prev.
-    /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u, Node v, Edge prev = INVALID) 
-    {     
-      if (prev == INVALID || id(prev) & 1 == 0) {
-	SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
-	if (se != INVALID) return forward(se);
-      } else {
-	SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
-	if (se != INVALID) return backward(se);	
-      }
-      return INVALID;
-    }
-
-//     /// Finds an symmetric edge between two nodes.
-
-//     /// Finds an symmetric edge from node \c u to node \c v.
-//     ///
-//     /// If \c prev is \ref INVALID (this is the default value), then
-//     /// It finds the first edge from \c u to \c v. Otherwise it looks for
-//     /// the next edge from \c u to \c v after \c prev.
-//     /// \return The found edge or INVALID if there is no such an edge.
-
-//     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) 
-//     {     
-//       if (prev == INVALID || id(prev) & 1 == 0) {
-// 	SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
-// 	if (se != INVALID) return se;
-//       } else {
-// 	SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
-// 	if (se != INVALID) return se;	
-//       }
-//       return INVALID;
-//     }
-    
-  public:
-
-    void clear() {
-      edge_maps.clear();
-      Parent::clear();
-    }
-
-    static Edge opposite(Edge e) {
-      return Edge(id(e) ^ 1);
-    }
-
-    static Edge forward(SymEdge e) {
-      return Edge(id(e) << 1);
-    }
-
-    static Edge backward(SymEdge e) {
-      return Edge((id(e) << 1) | 1);
-    }
-
-  };
-  ///Graph for bidirectional edges.
-
-  ///The purpose of this graph structure is to handle graphs
-  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
-  ///of oppositely directed edges.
-  ///There is a new edge map type called
-  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
-  ///that complements this
-  ///feature by
-  ///storing shared values for the edge pairs. The usual
-  ///\ref Graph::EdgeMap "EdgeMap"
-  ///can be used
-  ///as well.
-  ///
-  ///The oppositely directed edge can also be obtained easily
-  ///using \ref opposite.
-  ///\warning It shares the similarity with \ref SmartGraph that
-  ///it is not possible to delete edges or nodes from the graph.
-  //\sa SmartGraph.
-
-  /*  class SymSmartGraph : public SmartGraph
-  {
-  public:
-    typedef SymSmartGraph Graph;
-
-    // Create symmetric map registry.
-    CREATE_SYM_EDGE_MAP_REGISTRY;
-    // Create symmetric edge map.
-    CREATE_SYM_EDGE_MAP(ArrayMap);
-
-
-    SymSmartGraph() : SmartGraph() { }
-    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
-    ///Adds a pair of oppositely directed edges to the graph.
-    Edge addEdge(Node u, Node v)
-    {
-      Edge e = SmartGraph::addEdge(u,v);
-      Edge f = SmartGraph::addEdge(v,u);
-      sym_edge_maps.add(e);
-      sym_edge_maps.add(f);
-      return e;
-    }
-
-    ///The oppositely directed edge.
-
-    ///Returns the oppositely directed
-    ///pair of the edge \c e.
-    static Edge opposite(Edge e)
-    {
-      Edge f;
-      f.n = e.n - 2*(e.n%2) + 1;
-      return f;
-    }
-    
-
-    };*/
-  
   /// @}  
 } //namespace lemon
 
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/suurballe.h
--- a/src/lemon/suurballe.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/suurballe.h	Wed Oct 27 22:38:50 2004 +0000
@@ -125,12 +125,10 @@
       paths.resize(k);
       for (int j=0; j<i; ++j){
 	Node n=s;
-	OutEdgeIt e;
 
 	while (n!=t){
 
-
-	  G.first(e,n);
+	  OutEdgeIt e(G, n);
 	  
 	  while (!reversed[e]){
 	    ++e;
diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/vector_map.h
--- a/src/lemon/vector_map.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/lemon/vector_map.h	Wed Oct 27 22:38:50 2004 +0000
@@ -18,9 +18,9 @@
 #define LEMON_VECTOR_MAP_H
 
 #include <vector>
+#include <algorithm>
 
-#include <lemon/map_iterator.h>
-#include <lemon/map_bits.h>
+#include <lemon/alteration_observer_registry.h>
 
 ///\ingroup graphmaps
 ///\file
@@ -31,34 +31,41 @@
   /// \addtogroup graphmaps
   /// @{
   
-  /** The VectorMap template class is graph map structure what
-   *  automatically updates the map when a key is added to or erased from
-   *  the map. This map factory uses the allocators to implement 
-   *  the container functionality. This map factory
-   *  uses the std::vector to implement the container function.
-   *
-   *  \param MapRegistry The MapRegistry that the maps will belong to.
-   *  \param Value The value type of the map.
-   * 
-   *  \author Balazs Dezso
-   */
-	
-  template <typename MapRegistry, typename Value>
-  class VectorMap : public MapRegistry::MapBase {
-    template <typename MR, typename T> friend class VectorMap;
+  /// The VectorMap template class is graph map structure what
+  /// automatically updates the map when a key is added to or erased from
+  /// the map. This map factory uses the allocators to implement 
+  /// the container functionality. This map factory
+  /// uses the std::vector to implement the container function.
+  ///
+  /// \param Registry The AlterationObserverRegistry that will notify this map.
+  /// \param IdMap The IdMap type of the graph items.
+  /// \param Value The value type of the map.
+  /// 
+  /// \author Balazs Dezso
+  	
+
+  template <typename _Graph, 
+	    typename _Item,
+	    typename _IdMap,
+	    typename _Value>
+  class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase {
   public:
 		
-    /// The graph type of the maps. 
-    typedef typename MapRegistry::Graph Graph;
-    /// The key type of the maps.
-    typedef typename MapRegistry::KeyType KeyType;
-    /// The iterator to iterate on the keys.
-    typedef typename MapRegistry::KeyIt KeyIt;
+    /// The graph type of the map. 
+    typedef _Graph Graph;
+    /// The key type of the map.
+    typedef _Item KeyType;
+    /// The id map type of the map.
+    typedef _IdMap IdMap;
+    /// The registry type of the map.
+    typedef AlterationObserverRegistry<_Item> Registry;
+    /// The value type of the map.
+    typedef _Value Value;
 
     /// The map type.
     typedef VectorMap Map;
-    /// The MapBase of the Map which implements the core regisitry function.
-    typedef typename MapRegistry::MapBase MapBase;
+    /// The base class of the map.
+    typedef typename Registry::ObserverBase Parent;
 
   private:
 		
@@ -67,7 +74,6 @@
 
   public:
 
-
     /// The value type of the map.
     typedef Value ValueType;
     /// The reference type of the map;
@@ -82,95 +88,98 @@
     /// The pointer type of the map;
     typedef typename Container::const_pointer ConstPointerType;
 
-    /// Constructor to attach the new map into a registry.
+    /// Constructor to attach the new map into the registry.
 
-    /** Constructor to attach the new map into a registry.
-     *  It adds all the nodes or edges of the graph to the map.
-     */
-    VectorMap(const Graph& g, MapRegistry& r) 
-      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
+    /// It construates a map and attachs it into the registry.
+    /// It adds all the items of the graph to the map.
+     
+    VectorMap(const Graph& _g, Registry& _r) : graph(&_g) {
+      attach(_r);
+      build();
+    }
 
     /// Constructor uses given value to initialize the map. 
 
-    /** Constructor uses given value to initialize the map. 
-     *  It adds all the nodes or edges of the graph to the map.
-     */
-    VectorMap(const Graph& g, MapRegistry& r, const Value& v) 
-      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
+    /// It construates a map uses a given value to initialize the map. 
+    /// It adds all the items of the graph to the map.
+     
+    VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) { 
+      attach(r);
+      container.resize(IdMap(*graph).maxId() + 1, v);
+    }
 
-    /// Assign operator to copy a map of an other map type.
-
-    /** Assign operator to copy a map of an other map type.
-     *  This map's value type must be assignable by the other
-     *  map type's value type.
-     */
-    template <typename TT>
-    VectorMap(const VectorMap<MapRegistry, TT>& c) 
-      : MapBase(c), container(c.container.size()) {
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
-	container[id] = c.container[id];
+    VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
+      if (copy.attached()) {
+	attach(*copy.getRegistry());
+	container = copy.container;
       }
     }
 
-    /// Assign operator to copy a map of an other map type.
 
-    /** Assign operator to copy a map of an other map type.
-     *  This map's value type must be assignable by the other
-     *  map type's value type.
+    /** Assign operator to copy a map of the same map type.
      */
-    template <typename TT>
-    VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
-      if (MapBase::getGraph() != c.getGraph()) {
-	MapBase::operator=(c);
-	container.resize(c.container.size());
+    VectorMap& operator=(const VectorMap& copy) {
+      if (&copy == this) return *this;
+      
+      if (graph != copy.graph) {
+	if (attached()) {
+	  detach();
+	}
+	if (copy.attached()) {
+	  attach(*copy.getRegistry());
+	}
       }
-      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
-	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
-	container[id] = c.container[id];
+      container = copy.container;
+
+      return *this;
+    }
+
+
+    virtual ~VectorMap() {
+      if (attached()) {
+	detach();
       }
-      return *this;
+    }
+
+    const Graph* getGraph() const {
+      return graph;
     }
 
     /// The subcript operator.
 
-    /**
-     * The subscript operator. The map can be subscripted by the
-     * actual keys of the graph. 
-     */
+    /// The subscript operator. The map can be subscripted by the
+    /// actual items of the graph. 
+     
     ReferenceType operator[](const KeyType& key) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
-      return container[id];
+      return container[IdMap(*graph)[key]];
     } 
 		
     /// The const subcript operator.
 
-    /**
-     * The const subscript operator. The map can be subscripted by the
-     * actual keys of the graph. 
-     */
+    /// The const subscript operator. The map can be subscripted by the
+    /// actual items of the graph. 
+     
     ConstReferenceType operator[](const KeyType& key) const {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
-      return container[id];
+      return container[IdMap(*graph)[key]];
     }
 
-    ///Setter function of the map.
 
-    /** Setter function of the map. Equivalent with map[key] = val.
-     *  This is a compatibility feature with the not dereferable maps.
-     */
-    void set(const KeyType& key, const ValueType& val) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
-      container[id] = val;
+    /// The setter function of the map.
+
+    /// It the same as operator[](key) = value expression.
+    ///
+     
+    void set(const KeyType& key, const ValueType& value) {
+      (*this)[key] = value;
     }
+
     /// Adds a new key to the map.
 		
-    /** Adds a new key to the map. It called by the map registry
-     *  and it overrides the \ref MapRegistry::MapBase MapBase's
-     *  add() member function.
-     */
+    /// It adds a new key to the map. It called by the observer registry
+    /// and it overrides the add() member function of the observer base.
+     
     void add(const KeyType& key) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      int id = IdMap(*graph)[key];
       if (id >= (int)container.size()) {
 	container.resize(id + 1);
       }
@@ -178,93 +187,94 @@
 
     /// Erases a key from the map.
 		
-    /** Erase a key from the map. It called by the map registry 
-     *  and it overrides the \ref MapRegistry::MapBase MapBase's
-     *  erase() member function.
-     */
+    /// Erase a key from the map. It called by the observer registry
+    /// and it overrides the erase() member function of the observer base.     
     void erase(const KeyType& key) {}
 
-    /// Makes empty the map.
+    /// Buildes the map.
+		
+    /// It buildes the map. It called by the observer registry
+    /// and it overrides the build() member function of the observer base.
 
-    /** Makes empty the map. It called by the map registry 
-     *  and it overrides the \ref MapRegistry::MapBase MapBase's
-     *  clear() member function.
-     */
+    void build() { 
+      container.resize(IdMap(*graph).maxId() + 1);
+    }
 
+    /// Clear the map.
+
+    /// It erase all items from the map. It called by the observer registry
+    /// and it overrides the clear() member function of the observer base.     
     void clear() { 
       container.clear();
     }
 
-    /// The stl compatible pair iterator of the map.
-    typedef MapIterator<VectorMap> Iterator;
-    /// The stl compatible const pair iterator of the map.
-    typedef MapConstIterator<VectorMap> ConstIterator;
-
-    /** Returns the begin iterator of the map.
-     */
-    Iterator begin() {
-      return Iterator(*this, KeyIt(*MapBase::getGraph()));
-    }
-
-    /** Returns the end iterator of the map.
-     */
-    Iterator end() {
-      return Iterator(*this, INVALID);
-    }
-
-    /** Returns the begin ConstIterator of the map.
-     */
-    ConstIterator begin() const {
-      return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
-    }
-
-    /** Returns the end const_iterator of the map.
-     */
-    ConstIterator end() const {
-      return ConstIterator(*this, INVALID);
-    }
-
-    /// The KeySet of the Map.
-    typedef MapConstKeySet<VectorMap> ConstKeySet;
-
-    /// KeySet getter function.
-    ConstKeySet keySet() const {
-      return ConstKeySet(*this); 
-    }
-
-    /// The ConstValueSet of the Map.
-    typedef MapConstValueSet<VectorMap> ConstValueSet;
-
-    /// ConstValueSet getter function.
-    ConstValueSet valueSet() const {
-      return ConstValueSet(*this);
-    }
-
-    /// The ValueSet of the Map.
-    typedef MapValueSet<VectorMap> ValueSet;
-
-    /// ValueSet getter function.
-    ValueSet valueSet() {
-      return ValueSet(*this);
-    }
-
-
   private:
 		
     Container container;
+    const Graph *graph;
 
+  };
+
+
+  template <typename _Base> 
+  class VectorMappableGraphExtender : public _Base {
   public:
-    // STL  compatibility typedefs.
-    typedef Iterator iterator;
-    typedef ConstIterator const_iterator;
-    typedef typename Iterator::PairValueType value_type;
-    typedef typename Iterator::KeyType key_type;
-    typedef typename Iterator::ValueType data_type;
-    typedef typename Iterator::PairReferenceType reference;
-    typedef typename Iterator::PairPointerType pointer;
-    typedef typename ConstIterator::PairReferenceType const_reference;
-    typedef typename ConstIterator::PairPointerType const_pointer;
-    typedef int difference_type;		
+
+    typedef VectorMappableGraphExtender<_Base> Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::NodeIt NodeIt;
+    typedef typename Parent::NodeIdMap NodeIdMap;
+    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
+
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::EdgeIt EdgeIt;
+    typedef typename Parent::EdgeIdMap EdgeIdMap;
+    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
+
+    
+
+    template <typename _Value>
+    class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> {
+    public:
+      typedef VectorMappableGraphExtender<_Base> Graph;
+
+      typedef typename Graph::Node Node;
+      typedef typename Graph::NodeIdMap NodeIdMap;
+
+      typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent;
+
+      typedef typename Parent::Graph Graph;
+      typedef typename Parent::Value Value;
+
+      NodeMap(const Graph& g) 
+	: Parent(g, g.getNodeObserverRegistry()) {}
+      NodeMap(const Graph& g, const Value& v) 
+	: Parent(g, g.getNodeObserverRegistry(), v) {}
+
+    };
+
+    template <typename _Value>
+    class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> {
+    public:
+      typedef VectorMappableGraphExtender<_Base> Graph;
+
+      typedef typename Graph::Edge Edge;
+      typedef typename Graph::EdgeIdMap EdgeIdMap;
+
+      typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent;
+
+      typedef typename Parent::Graph Graph;
+      typedef typename Parent::Value Value;
+
+      EdgeMap(const Graph& g) 
+	: Parent(g, g.getEdgeObserverRegistry()) {}
+      EdgeMap(const Graph& g, const Value& v) 
+	: Parent(g, g.getEdgeObserverRegistry(), v) {}
+
+    };
+    
   };
   
   /// @}
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/Makefile.am
--- a/src/test/Makefile.am	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/test/Makefile.am	Wed Oct 27 22:38:50 2004 +0000
@@ -2,17 +2,22 @@
 
 EXTRA_DIST = preflow_graph.dim #input file for preflow_test.cc
 
-noinst_HEADERS = test_tools.h graph_test.h sym_graph_test.h
+noinst_HEADERS = \
+	test_tools.h \
+	graph_test.h \
+	sym_graph_test.h \
+	map_test.h \
+	graph_utils_test.h
 
 check_PROGRAMS = \
 	bfs_test \
 	dfs_test \
 	dijkstra_test \
 	graph_test \
-	sym_graph_test \
-	graph_wrapper_test \
+	graph_utils_test \
 	kruskal_test \
 	min_cost_flow_test \
+	new_graph_test \
 	suurballe_test \
 	path_test \
 	preflow_test \
@@ -20,6 +25,7 @@
 	test_tools_pass \
 	time_measure_test \
 	unionfind_test \
+	graph_wrapper_test \
 	xy_test
 
 TESTS = $(check_PROGRAMS)
@@ -29,10 +35,11 @@
 dfs_test_SOURCES = dfs_test.cc
 dijkstra_test_SOURCES = dijkstra_test.cc
 graph_test_SOURCES = graph_test.cc
-sym_graph_test_SOURCES = sym_graph_test.cc
+graph_utils_test_SOURCES = graph_utils_test.cc
 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
 kruskal_test_SOURCES = kruskal_test.cc
 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
+new_graph_test_SOURCES = new_graph_test.cc
 suurballe_test_SOURCES = suurballe_test.cc
 path_test_SOURCES = path_test.cc
 preflow_test_SOURCES = preflow_test.cc
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_factory_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/graph_factory_test.cc	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,154 @@
+/* -*- C++ -*-
+ * src/test/graph_test.cc - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, 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.
+ *
+ */
+
+#include<iostream>
+#include<lemon/smart_graph.h>
+#include<lemon/skeletons/graph.h>
+#include<lemon/skeletons/maps.h>
+#include<lemon/list_graph_base.h>
+#include<lemon/full_graph.h>
+
+#include"test_tools.h"
+#include"graph_test.h"
+
+/**
+\file
+This test makes consistency checks of list graph structures.
+
+G.addNode(), G.addEdge(), G.tail(), G.head()
+
+\todo Checks for empty graphs and isolated points.
+conversion.
+*/
+
+using namespace lemon;
+
+template<class Graph> void bidirPetersen(Graph &G)
+{
+  typedef typename Graph::Edge Edge;
+  typedef typename Graph::EdgeIt EdgeIt;
+  
+  checkGraphEdgeList(G,15);
+  
+  std::vector<Edge> ee;
+  
+  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
+
+  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
+    G.addEdge(G.head(*p),G.tail(*p));
+}
+
+template<class Graph> void checkPetersen(Graph &G)
+{
+  typedef typename Graph::Node Node;
+
+  typedef typename Graph::EdgeIt EdgeIt;
+  typedef typename Graph::NodeIt NodeIt;
+
+  checkGraphNodeList(G,10);
+  checkGraphEdgeList(G,30);
+
+  for(NodeIt n(G);n!=INVALID;++n) {
+    checkGraphInEdgeList(G,n,3);
+    checkGraphOutEdgeList(G,n,3);
+  }  
+}
+
+//Compile Graph
+template void lemon::skeleton::checkCompileStaticGraph<skeleton::StaticGraph>
+(skeleton::StaticGraph &);
+
+template
+void lemon::skeleton::checkCompileExtendableGraph<skeleton::ExtendableGraph>
+(skeleton::ExtendableGraph &);
+
+template
+void lemon::skeleton::checkCompileErasableGraph<skeleton::ErasableGraph>
+(skeleton::ErasableGraph &);
+
+//Compile SmartGraph
+template
+void lemon::skeleton::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
+template
+void lemon::skeleton::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
+
+//Compile SymSmartGraph
+//template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
+//template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
+
+//Compile ListGraph
+template
+void lemon::skeleton::checkCompileExtendableGraph<ListGraph>(ListGraph &);
+template
+void lemon::skeleton::checkCompileErasableGraph<ListGraph>(ListGraph &);
+template
+void lemon::skeleton::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
+
+
+//Compile SymListGraph
+//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
+//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
+//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
+
+//Compile FullGraph
+template void lemon::skeleton::checkCompileStaticGraph<FullGraph>(FullGraph &);
+template
+void lemon::skeleton::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
+
+
+int main() 
+{
+  {
+    SmartGraph G;
+    addPetersen(G);
+    bidirPetersen(G);
+    checkPetersen(G);
+  }
+  {
+    ListGraph G;
+    addPetersen(G);
+    bidirPetersen(G);
+    checkPetersen(G);
+  }
+  {
+    //    SymSmartGraph G;
+    //    addPetersen(G);
+    //    checkPetersen(G);
+  }
+  {
+    //    SymListGraph G;
+    //    addPetersen(G);
+    //    checkPetersen(G);
+  }
+
+  ///\file
+  ///\todo map tests.
+  ///\todo copy constr tests.
+
+
+  // Some map tests.
+  // FIXME: These shouldn't be here.
+  using namespace skeleton;
+  function_requires< ReadMapConcept< ReadMap<int,int> > >();
+  function_requires< WriteMapConcept< WriteMap<int,int> > >();
+  function_requires< ReadWriteMapConcept< ReadWriteMap<int,int> > >();
+  function_requires< ReferenceMapConcept< ReferenceMap<int,int> > >();
+
+
+  std::cout << __FILE__ ": All tests passed.\n";
+
+  return 0;
+}
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_test.cc
--- a/src/test/graph_test.cc	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/test/graph_test.cc	Wed Oct 27 22:38:50 2004 +0000
@@ -1,157 +1,67 @@
-/* -*- C++ -*-
- * src/test/graph_test.cc - Part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Combinatorial Optimization Research Group, 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.
- *
- */
+// -*- c++ -*-
 
-#include<iostream>
-#include<lemon/smart_graph.h>
-#include<lemon/skeletons/graph.h>
-#include<lemon/list_graph.h>
-#include<lemon/full_graph.h>
+#include <iostream>
+#include <vector>
 
-#include"test_tools.h"
-#include"graph_test.h"
+#include <lemon/skeletons/graph.h>
+#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
+#include <lemon/full_graph.h>
 
-/**
-\file
-This test makes consistency checks of list graph structures.
+#include "test_tools.h"
+#include "graph_test.h"
+#include "map_test.h"
 
-G.addNode(), G.addEdge(), G.tail(), G.head()
-
-\todo Checks for empty graphs and isolated points.
-conversion.
-*/
 
 using namespace lemon;
+using namespace lemon::skeleton;
 
-template<class Graph> void bidirPetersen(Graph &G)
-{
-  typedef typename Graph::Edge Edge;
-  typedef typename Graph::EdgeIt EdgeIt;
-  
-  checkGraphEdgeList(G,15);
-  
-  std::vector<Edge> ee;
-  
-  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
 
-  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
-    G.addEdge(G.head(*p),G.tail(*p));
-}
+int main() {
+  ///\file
+  { // checking graph components
+    function_requires<BaseGraphComponentConcept<BaseGraphComponent> >();
 
-template<class Graph> void checkPetersen(Graph &G)
-{
-  typedef typename Graph::Node Node;
+    function_requires<BaseIterableGraphComponentConcept<BaseIterableGraphComponent> >();
 
-  typedef typename Graph::EdgeIt EdgeIt;
-  typedef typename Graph::NodeIt NodeIt;
+    function_requires<IDableGraphComponentConcept<IDableGraphComponent> >();
+    function_requires<MaxIDableGraphComponentConcept<MaxIDableGraphComponent> >();
 
-  checkGraphNodeList(G,10);
-  checkGraphEdgeList(G,30);
+    function_requires<BaseExtendableGraphComponentConcept<BaseExtendableGraphComponent> >();
+    function_requires<BaseErasableGraphComponentConcept<BaseErasableGraphComponent> >();
+    function_requires<BaseClearableGraphComponentConcept<BaseClearableGraphComponent> >();
 
-  for(NodeIt n(G);n!=INVALID;++n) {
-    checkGraphInEdgeList(G,n,3);
-    checkGraphOutEdgeList(G,n,3);
-  }  
-}
+    function_requires<IterableGraphComponentConcept<IterableGraphComponent> >();
 
-//Compile Graph
-template void lemon::skeleton::checkCompileStaticGraph<skeleton::StaticGraph>
-(skeleton::StaticGraph &);
+    function_requires<IdMappableGraphComponentConcept<IdMappableGraphComponent> >();
+    function_requires<MappableGraphComponentConcept<MappableGraphComponent> >();
 
-template
-void lemon::skeleton::checkCompileExtendableGraph<skeleton::ExtendableGraph>
-(skeleton::ExtendableGraph &);
+    function_requires<ExtendableGraphComponentConcept<ExtendableGraphComponent> >();
+    function_requires<ErasableGraphComponentConcept<ErasableGraphComponent> >();
+    function_requires<ClearableGraphComponentConcept<ClearableGraphComponent> >();
+  }
+  { // checking skeleton graphs
+    function_requires<StaticGraphConcept<StaticGraph> >();
+    function_requires<ExtendableGraphConcept<ExtendableGraph> >();
+    function_requires<ErasableGraphConcept<ErasableGraph> >();
+  }
+  { // checking list graph
+    function_requires<ErasableGraphConcept<ListGraph> >();
 
-template
-void lemon::skeleton::checkCompileErasableGraph<skeleton::ErasableGraph>
-(skeleton::ErasableGraph &);
+    checkGraph<ListGraph>();
+    checkGraphNodeMap<ListGraph>();
+    checkGraphEdgeMap<ListGraph>();
+  }
+  { // checking smart graph
+    function_requires<ExtendableGraphConcept<SmartGraph> >();
 
-//Compile SmartGraph
-template
-void lemon::skeleton::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
-template
-void lemon::skeleton::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
-
-//Compile SymSmartGraph
-//template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
-//template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
-
-//Compile ListGraph
-template
-void lemon::skeleton::checkCompileExtendableGraph<ListGraph>(ListGraph &);
-template
-void lemon::skeleton::checkCompileErasableGraph<ListGraph>(ListGraph &);
-template
-void lemon::skeleton::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
-
-
-//Compile SymListGraph
-//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
-//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
-//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
-
-//Compile FullGraph
-template void lemon::skeleton::checkCompileStaticGraph<FullGraph>(FullGraph &);
-template
-void lemon::skeleton::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
-
-//Compile EdgeSet <ListGraph>
-template void lemon::skeleton::checkCompileExtendableGraph<EdgeSet <ListGraph> >
-(EdgeSet <ListGraph> &);
-template void lemon::skeleton::checkCompileGraphEraseEdge<EdgeSet <ListGraph> >
-(EdgeSet <ListGraph> &);
-template void lemon::skeleton::checkCompileGraphFindEdge<EdgeSet <ListGraph> >
-(EdgeSet <ListGraph> &);
-
-//Compile EdgeSet <NodeSet>
-template void lemon::skeleton::checkCompileExtendableGraph<EdgeSet <NodeSet> >
-(EdgeSet <NodeSet> &);
-template void lemon::skeleton::checkCompileGraphEraseEdge<EdgeSet <NodeSet> >
-(EdgeSet <NodeSet> &);
-template void lemon::skeleton::checkCompileGraphFindEdge<EdgeSet <NodeSet> >
-(EdgeSet <NodeSet> &);
-
-
-int main() 
-{
-  {
-    SmartGraph G;
-    addPetersen(G);
-    bidirPetersen(G);
-    checkPetersen(G);
+    checkGraph<SmartGraph>();
+    checkGraphNodeMap<SmartGraph>();
+    checkGraphEdgeMap<SmartGraph>();
   }
-  {
-    ListGraph G;
-    addPetersen(G);
-    bidirPetersen(G);
-    checkPetersen(G);
+  { // checking full graph
+    function_requires<StaticGraphConcept<FullGraph> >();
   }
-  {
-    //    SymSmartGraph G;
-    //    addPetersen(G);
-    //    checkPetersen(G);
-  }
-  {
-    //    SymListGraph G;
-    //    addPetersen(G);
-    //    checkPetersen(G);
-  }
-
-  ///\file
-  ///\todo map tests.
-  ///\todo copy constr tests.
 
   std::cout << __FILE__ ": All tests passed.\n";
 
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_test.h
--- a/src/test/graph_test.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/test/graph_test.h	Wed Oct 27 22:38:50 2004 +0000
@@ -21,56 +21,64 @@
 
 //! \ingroup misc
 //! \file
-//! \brief Some utility to  test graph classes.
+//! \brief Some utility and test cases to test graph classes.
 namespace lemon {
 
   template<class Graph> void checkGraphNodeList(Graph &G, int nn)
-    {
-      typename Graph::NodeIt n(G);
-      for(int i=0;i<nn;i++) {
-	check(n!=INVALID,"Wrong Node list linking.");
-	++n;
-      }
-      check(n==INVALID,"Wrong Node list linking.");
+  {
+    typename Graph::NodeIt n(G);
+    for(int i=0;i<nn;i++) {
+      check(n!=INVALID,"Wrong Node list linking.");
+      ++n;
     }
+    check(n==INVALID,"Wrong Node list linking.");
+  }
 
-  template<class Graph> void checkGraphEdgeList(Graph &G, int nn)
-    {
-      typedef typename Graph::EdgeIt EdgeIt;
+  template<class Graph>
+  void checkGraphEdgeList(Graph &G, int nn)
+  {
+    typedef typename Graph::EdgeIt EdgeIt;
 
-      EdgeIt e(G);
-      for(int i=0;i<nn;i++) {
-	check(e!=INVALID,"Wrong Edge list linking.");
-	++e;
-      }
-      check(e==INVALID,"Wrong Edge list linking.");
+    EdgeIt e(G);
+    for(int i=0;i<nn;i++) {
+      check(e!=INVALID,"Wrong Edge list linking.");
+      ++e;
     }
+    check(e==INVALID,"Wrong Edge list linking.");
+  }
 
-  template<class Graph> void checkGraphOutEdgeList(Graph &G,
-						   typename Graph::Node n,
-						   int nn)
-    {
-      typename Graph::OutEdgeIt e(G,n);
-      for(int i=0;i<nn;i++) {
-	check(e!=INVALID,"Wrong OutEdge list linking.");
-	check(n==G.tail(e), "Wrong OutEdge list linking.");
-	++e;
-      }
-      check(e==INVALID,"Wrong OutEdge list linking.");
+  template<class Graph> 
+  void checkGraphOutEdgeList(Graph &G, typename Graph::Node n, int nn)
+  {
+    typename Graph::OutEdgeIt e(G,n);
+    for(int i=0;i<nn;i++) {
+      check(e!=INVALID,"Wrong OutEdge list linking.");
+      check(n==G.tail(e), "Wrong OutEdge list linking.");
+      ++e;
     }
+    check(e==INVALID,"Wrong OutEdge list linking.");
+  }
 
-  template<class Graph> void checkGraphInEdgeList(Graph &G,
-						  typename Graph::Node n,
-						  int nn)
-    {
-      typename Graph::InEdgeIt e(G,n);
-      for(int i=0;i<nn;i++) {
-	check(e!=INVALID,"Wrong InEdge list linking.");
-	check(n==G.head(e), "Wrong InEdge list linking.");
-	++e;
-      }
-      check(e==INVALID,"Wrong InEdge list linking.");
+  template<class Graph> void 
+  checkGraphInEdgeList(Graph &G, typename Graph::Node n, int nn)
+  {
+    typename Graph::InEdgeIt e(G,n);
+    for(int i=0;i<nn;i++) {
+      check(e!=INVALID,"Wrong InEdge list linking.");
+      check(n==G.head(e), "Wrong InEdge list linking.");
+      ++e;
     }
+    check(e==INVALID,"Wrong InEdge list linking.");
+  }
+
+  template <class Graph> 
+  void checkGraph() {
+    const int num = 5;
+    Graph G;
+    addPetersen(G, num);
+    bidirGraph(G);
+    checkBidirPetersen(G, num);
+  }
 
   ///\file
   ///\todo Check head(), tail() as well;
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_utils_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/graph_utils_test.cc	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,29 @@
+// -*- c++ -*-
+
+#include <iostream>
+#include <vector>
+
+#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
+#include <lemon/full_graph.h>
+
+#include "test_tools.h"
+#include "graph_utils_test.h"
+
+
+using namespace lemon;
+
+
+int main() {
+  ///\file
+  { // checking list graph
+    checkGraphCounters<ListGraph>();
+  }
+  { // checking smart graph
+    checkGraphCounters<SmartGraph>();
+  }
+
+  std::cout << __FILE__ ": All tests passed.\n";
+
+  return 0;
+}
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_utils_test.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/graph_utils_test.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,44 @@
+/* -*- C++ -*-
+ * src/test/graph_utils_test.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, 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_TEST_GRAPH_UTILS_TEST_H
+#define LEMON_TEST_GRAPH_UTILS_TEST_H
+
+
+#include "test_tools.h"
+
+//! \ingroup misc
+//! \file
+//! \brief Test cases for graph utils.
+namespace lemon {
+  
+  template <typename Graph>
+  void checkGraphCounters() {
+    const int num = 5;
+    Graph graph;
+    addPetersen(graph, num);
+    bidirGraph(graph);
+    check(countNodes(graph) == 2*num, "Wrong node counter.");
+    check(countEdges(graph) == 6*num, "Wrong edge counter.");    
+    for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
+      check(countOutEdges(graph, it) == 3, "Wrong out degree counter.");
+      check(countInEdges(graph, it) == 3, "Wrong in degree counter.");
+    }
+  }
+  
+} //namespace lemon
+
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_wrapper_test.cc
--- a/src/test/graph_wrapper_test.cc	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/test/graph_wrapper_test.cc	Wed Oct 27 22:38:50 2004 +0000
@@ -15,8 +15,11 @@
  */
 
 #include<iostream>
+#include<lemon/concept_check.h>
+
 #include<lemon/smart_graph.h>
 #include<lemon/skeletons/graph.h>
+
 #include<lemon/list_graph.h>
 #include<lemon/full_graph.h>
 #include<lemon/graph_wrapper.h>
@@ -32,66 +35,31 @@
 */
 
 using namespace lemon;
+using namespace lemon::skeleton;
 
 
 typedef SmartGraph Graph;
 
-//Compile GraphWrapper
-typedef GraphWrapper<Graph> GW;
-template void lemon::skeleton::checkCompileStaticGraph<GW>(GW &);
-
-//Compile RevGraphWrapper
-typedef RevGraphWrapper<Graph> RevGW;
-template void lemon::skeleton::checkCompileStaticGraph<RevGW>(RevGW &);
-
-//Compile SubGraphWrapper
-typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, 
-			Graph::EdgeMap<bool> > SubGW;
-template void lemon::skeleton::checkCompileStaticGraph<SubGW>(SubGW &);
-
-//Compile NodeSubGraphWrapper
-typedef NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > NodeSubGW;
-template void lemon::skeleton::checkCompileStaticGraph<NodeSubGW>(NodeSubGW &);
-
-//Compile EdgeSubGraphWrapper
-typedef EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > EdgeSubGW;
-template void lemon::skeleton::checkCompileStaticGraph<EdgeSubGW>(EdgeSubGW &);
-
-//Compile UndirGraphWrapper
-/// \bug UndirGraphWrapper cannot pass the StaticGraph test
-//typedef UndirGraphWrapper<Graph> UndirGW;
-//template void checkCompileStaticGraph<UndirGW>(UndirGW &);
-
-//Compile UndirGraph
-//typedef UndirGraph<Graph> UndirG;
-//template void checkCompileStaticGraph<UndirG>(UndirG &);
-
-//Compile SubBidirGraphWrapper
-typedef SubBidirGraphWrapper<Graph, Graph::EdgeMap<bool>, 
-			     Graph::EdgeMap<bool> > SubBDGW;
-template void lemon::skeleton::checkCompileStaticGraph<SubBDGW>(SubBDGW &);
-
-//Compile BidirGraphWrapper
-typedef BidirGraphWrapper<Graph> BidirGW;
-template void lemon::skeleton::checkCompileStaticGraph<BidirGW>(BidirGW &);
-
-//Compile BidirGraph
-typedef BidirGraph<Graph> BidirG;
-template void lemon::skeleton::checkCompileStaticGraph<BidirG>(BidirG &);
-
-//Compile ResGraphWrapper
-typedef ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, 
-			Graph::EdgeMap<int> > ResGW;
-template void lemon::skeleton::checkCompileStaticGraph<ResGW>(ResGW &);
-
-//Compile ErasingFirstGraphWrapper
-typedef ErasingFirstGraphWrapper<Graph, Graph::NodeMap<Graph::Edge> > ErasingFirstGW;
-template
-void lemon::skeleton::checkCompileStaticGraph<ErasingFirstGW>(ErasingFirstGW &);
-
 
 int main() 
 {
+  {
+    function_requires<StaticGraphConcept<GraphWrapper<Graph> > >();
+
+    function_requires<StaticGraphConcept<RevGraphWrapper<Graph> > >();
+
+    function_requires<StaticGraphConcept<SubGraphWrapper<Graph, Graph::NodeMap<bool> , Graph::EdgeMap<bool> > > >();
+    function_requires<StaticGraphConcept<NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > > >();
+    function_requires<StaticGraphConcept<EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > > >();
+
+    function_requires<StaticGraphConcept<SubBidirGraphWrapper<Graph, Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > > > ();
+
+    function_requires<StaticGraphConcept<BidirGraph<Graph> > >();
+
+    function_requires<StaticGraphConcept<ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > > >();
+
+    function_requires<StaticGraphConcept<ErasingFirstGraphWrapper<Graph, Graph::NodeMap<Graph::Edge> > > >();
+  }
   std::cout << __FILE__ ": All tests passed.\n";
 
   return 0;
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/map_test.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/map_test.h	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,95 @@
+/* -*- C++ -*-
+ * src/test/map_test.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, 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_TEST_MAP_TEST_H
+#define LEMON_TEST_MAP_TEST_H
+
+
+#include <vector>
+
+#include "test_tools.h"
+
+
+//! \ingroup misc
+//! \file
+//! \brief Some utility to test map classes.
+
+namespace lemon {
+
+
+  template <typename Graph>
+  void checkGraphNodeMap() {
+    Graph graph;
+    const int num = 16;
+    
+    typedef typename Graph::Node Node;
+
+    std::vector<Node> nodes;
+    for (int i = 0; i < num; ++i) {
+      nodes.push_back(graph.addNode());      
+    }
+    typedef typename Graph::template NodeMap<int> IntNodeMap;
+    IntNodeMap map(graph, 42);
+    for (int i = 0; i < (int)nodes.size(); ++i) {
+      check(map[nodes[i]] == 42, "Wrong map constructor.");      
+    }
+    for (int i = 0; i < num; ++i) {
+      nodes.push_back(graph.addNode());
+      map[nodes.back()] = 23;
+    }
+    graph.clear();
+    nodes.clear();
+  }
+
+  template <typename Graph>
+  void checkGraphEdgeMap() {
+    Graph graph;
+    const int num = 16;
+    
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
+    
+    std::vector<Node> nodes;
+    for (int i = 0; i < num; ++i) {
+      nodes.push_back(graph.addNode());
+    }
+    
+    std::vector<Edge> edges;
+    for (int i = 0; i < num; ++i) {
+      for (int j = 0; j < i; ++j) {
+	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
+      }
+    }
+    
+    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
+    IntEdgeMap map(graph, 42);
+    
+    for (int i = 0; i < (int)edges.size(); ++i) {
+      check(map[edges[i]] == 42, "Wrong map constructor.");      
+    }
+    
+    for (int i = 0; i < num; ++i) {
+      for (int j = i + 1; j < num; ++j) {
+	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
+	map[edges.back()] = 23;
+      }
+    }
+    graph.clear();
+    edges.clear();    
+  }
+
+}
+
+#endif
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/new_graph_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/new_graph_test.cc	Wed Oct 27 22:38:50 2004 +0000
@@ -0,0 +1,39 @@
+/* -*- C++ -*-
+ * src/test/new_graph_test.cc - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, 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.
+ *
+ */
+
+#include <lemon/skeletons/graph.h>
+// #include <boost/concept_check.hpp>
+
+using namespace lemon::skeleton;
+
+// Borrowed from boost:
+template <class T> inline void ignore_unused_variable_warning(const T&) { }
+
+int main()
+{
+  //    This is the "right" way to check a concept:
+  // boost::function_requires< BaseGraphItemConcept<BaseGraphItem> >();
+
+  //    which is equivalent (considering compile-time checks) to
+  // BaseGraphItemConcept<BaseGraphItem> bgic;
+  // bgic.constraints();
+  //    but not actually call or intatiates anything...
+  //    It's doing aproximately this:
+  typedef BaseGraphItemConcept<BaseGraphItem> CC;
+  void (CC::*x)() = &CC::constraints;
+  ignore_unused_variable_warning(x);
+  //    But even more hackish...
+}
diff -r f2ea4aac9ada -r c94ef40a22ce src/test/test_tools.h
--- a/src/test/test_tools.h	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/test/test_tools.h	Wed Oct 27 22:38:50 2004 +0000
@@ -70,7 +70,7 @@
 ///\return The nodes and edges of the generated graph.
 
 template<typename Graph>
-PetStruct<Graph> addPetersen(Graph &G,int num=5)
+PetStruct<Graph> addPetersen(Graph &G,int num = 5)
 {
   PetStruct<Graph> n;
 
@@ -81,12 +81,50 @@
 
  for(int i=0;i<num;i++) {
    n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
-   n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
-   n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
+   n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1) % num]));
+   n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2) % num]));
   }
  return n;
 }
 
+/// \brief Adds to the graph the reverse pair of all edge.
+///
+/// Adds to the graph the reverse pair of all edge.
+///
+template<class Graph> void bidirGraph(Graph &G)
+{
+  typedef typename Graph::Edge Edge;
+  typedef typename Graph::EdgeIt EdgeIt;
+  
+  std::vector<Edge> ee;
+  
+  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
+
+  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
+    G.addEdge(G.head(*p),G.tail(*p));
+}
+
+
+/// \brief Checks the bidirectioned Petersen graph.
+///
+///  Checks the bidirectioned Petersen graph.
+///
+template<class Graph> void checkBidirPetersen(Graph &G, int num = 5)
+{
+  typedef typename Graph::Node Node;
+
+  typedef typename Graph::EdgeIt EdgeIt;
+  typedef typename Graph::NodeIt NodeIt;
+
+  checkGraphNodeList(G, 2 * num);
+  checkGraphEdgeList(G, 6 * num);
+
+  for(NodeIt n(G);n!=INVALID;++n) {
+    checkGraphInEdgeList(G, n, 3);
+    checkGraphOutEdgeList(G, n, 3);
+  }  
+}
+
 ///Structure returned by \ref addSymPetersen().
 
 ///Structure returned by \ref addSymPetersen().
diff -r f2ea4aac9ada -r c94ef40a22ce src/work/klao/TODO
--- a/src/work/klao/TODO	Mon Oct 25 13:29:46 2004 +0000
+++ b/src/work/klao/TODO	Wed Oct 27 22:38:50 2004 +0000
@@ -1,1 +1,3 @@
+full_graph.h -t atnez(et)ni!
+
 megcsinalni, hogy mukodjon a kereses a doksiban