Changeset 946:c94ef40a22ce in lemon-0.x for src

Timestamp:

10/28/04 00:38:50 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322

Message:

The graph_factory branch (@ 1321) has been merged to trunk.

Location:

src

Files:

• benchmark/hcube.cc (modified) (1 diff)
• lemon/Makefile.am (modified) (2 diffs)
• lemon/alteration_observer_registry.h (added)
• lemon/array_map.h (modified) (16 diffs)
• lemon/bfs.h (modified) (1 diff)
• lemon/clearable_graph_extender.h (added)
• lemon/concept_check.h (added)
• lemon/default_map.h (modified) (2 diffs)
• lemon/dfs.h (modified) (3 diffs)
• lemon/erasable_graph_extender.h (added)
• lemon/extendable_graph_extender.h (added)
• lemon/full_graph.h (modified) (6 diffs)
• lemon/graph_utils.h (added)
• lemon/idmappable_graph_extender.h (added)
• lemon/iterable_graph_extender.h (added)
• lemon/list_graph.h (modified) (6 diffs)
• lemon/map_registry.h (deleted)
• lemon/mappable_graph_extender.h (added)
• lemon/preflow.h (modified) (1 diff)
• lemon/skeletons/graph.h (modified) (2 diffs)
• lemon/skeletons/graph_component.h (added)
• lemon/skeletons/maps.h (modified) (2 diffs)
• lemon/smart_graph.h (modified) (9 diffs)
• lemon/suurballe.h (modified) (1 diff)
• lemon/vector_map.h (modified) (5 diffs)
• test/Makefile.am (modified) (4 diffs)
• test/graph_factory_test.cc (added)
• test/graph_test.cc (modified) (1 diff)
• test/graph_test.h (modified) (1 diff)
• test/graph_utils_test.cc (added)
• test/graph_utils_test.h (added)
• test/graph_wrapper_test.cc (modified) (2 diffs)
• test/map_test.h (added)
• test/new_graph_test.cc (added)
• test/test_tools.h (modified) (2 diffs)
• work/klao/TODO (modified) (1 diff)

src/benchmark/hcube.cc

@@ -67 +67 @@
     
     //  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++) {

src/lemon/Makefile.am

@@ -11 +11 @@
         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                                                 \
@@ -27 +26 @@
         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                                                \

src/lemon/array_map.h

@@ -21 +21 @@
 
 #include <lemon/map_iterator.h>
-#include <lemon/map_bits.h>
 
 ///\ingroup graphmaps
@@ -43 +42 @@
    */
 
-  template <typename MapRegistry, typename Value> 
-  class ArrayMap : public MapRegistry::MapBase {
-
-    template <typename MR, typename V> friend class ArrayMap;
-                
+  template <typename _Graph, 
+            typename _Item,
+            typename _ItemIt,
+            typename _IdMap,
+            typename _Value>
+  class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
+
   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;
                 
     
@@ -78 +87 @@
 
 
+  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);
       }                                                         
     }
@@ -104 +119 @@
     /** 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]);
       }
@@ -133 +137 @@
       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;
@@ -145 +150 @@
       }
 
-      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]);
       }
@@ -153 +158 @@
     }
 
-    /** 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();
       }
     }
@@ -194 +173 @@
      */
     ReferenceType operator[](const KeyType& key) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      int id = IdMap(*graph)[key];
       return values[id];
     } 
@@ -203 +182 @@
      */
     ConstReferenceType operator[](const KeyType& key) const {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      int id = IdMap(*graph)[key];
       return values[id];
     }
@@ -211 +190 @@
      */
     void set(const KeyType& key, const ValueType& val) {
-      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
-      values[id] = val;
+      (*this)[key] = val;
     }
                 
@@ -218 +196 @@
      */
     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);
@@ -224 +202 @@
           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]);
@@ -242 +220 @@
      */
     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;
@@ -256 +243 @@
     }
 
-    /// 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 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<ArrayMap> ConstKeySet;
-
-    /// KeySet getter function.
-    ConstKeySet keySet() const {
-      return ConstKeySet(*this); 
-    }
-
-    /// The ConstValueSet of the Map.
-    typedef MapConstValueSet<ArrayMap> ConstValueSet;
-
-    /// ConstValueSet getter function.
-    ConstValueSet valueSet() const {
-      return ConstValueSet(*this);
-    }
-
-    /// The ValueSet of the Map.
-    typedef MapValueSet<ArrayMap> ValueSet;
-
-    /// ValueSet getter function.
-    ValueSet valueSet() {
-      return ValueSet(*this);
-    }
+//     /// 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 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<ArrayMap> ConstKeySet;
+
+//     /// KeySet getter function.
+//     ConstKeySet keySet() const {
+//       return ConstKeySet(*this); 
+//     }
+
+//     /// The ConstValueSet of the Map.
+//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
+
+//     /// ConstValueSet getter function.
+//     ConstValueSet valueSet() const {
+//       return ConstValueSet(*this);
+//     }
+
+//     /// The ValueSet of the Map.
+//     typedef MapValueSet<ArrayMap> ValueSet;
+
+//     /// 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;
@@ -325 +312 @@
     }      
 
+    const Graph* graph;
     int capacity;
     Value* values;
@@ -330 +318 @@
 
   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) {}
+
+    };
+    
+  };
+
 /// @}
 

src/lemon/bfs.h

@@ -196 +196 @@
       }
       
-      int N=G->nodeNum();
+      int N = countNodes(*G);
       std::vector<typename Graph::Node> Q(N);
       int Qh=0;

src/lemon/default_map.h

@@ -24 +24 @@
 ///\ingroup graphmaps
 ///\file
-///\brief Graph maps that construates and destruates
+///\brief Graph maps that construct and destruct
 ///their elements dynamically.
 
@@ -42 +42 @@
 
 
-  /** 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 MapRegistry, typename Type>
-  class DefaultMap : public ArrayMap<MapRegistry, Type> 
-  DEFAULT_MAP_BODY(ArrayMap, Type);
-
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, bool> 
-    : public VectorMap<MapRegistry, bool> 
-  DEFAULT_MAP_BODY(VectorMap, bool);
-
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, char> 
-    : public VectorMap<MapRegistry, char> 
-  DEFAULT_MAP_BODY(VectorMap, char);
-
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, int> 
-    : public VectorMap<MapRegistry, int> 
-  DEFAULT_MAP_BODY(VectorMap, int);
-
-  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);
-
-  template <typename MapRegistry>
-  class DefaultMap<MapRegistry, float> 
-    : public VectorMap<MapRegistry, float> 
-  DEFAULT_MAP_BODY(VectorMap, float);
-
-  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);
-
-  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, typename _Value>
+  struct DefaultMapSelector {
+    typedef ArrayMap<_Graph, _Item, _ItemIt, _IdMap, _Value> Map;
+  };
+
+  // bool
+  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, bool> {
+    typedef VectorMap<_Graph, _Item, _IdMap, bool> Map;
+  };
+
+  // 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 _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 _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned char> {
+    typedef VectorMap<_Graph, _Item, _IdMap, unsigned char> Map;
+  };
+
+
+  // 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 _Graph, typename _Item, typename _ItemIt, typename _IdMap>
+  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned int> {
+    typedef VectorMap<_Graph, _Item, _IdMap, unsigned int> Map;
+  };
+
+
+  // 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 _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) {}
+
+    };
+    
+  };
+
 
 }

src/lemon/dfs.h

@@ -24 +24 @@
 ///\todo Revise Manual.
 
-#include <lemon/bin_heap.h>
+#include <lemon/graph_utils.h>
 #include <lemon/invalid.h>
 
@@ -194 +194 @@
       }
       
-      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);
 
@@ -210 +210 @@
             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;

src/lemon/full_graph.h

@@ -18 +18 @@
 #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 {
@@ -49 +50 @@
   ///
   ///\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) { }
-    ///
-    FullGraph(const FullGraph &_g)
-      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
+    void construct(int n) { NodeNum = n; EdgeNum = n * n; }
+    ///
+    //    FullGraphBase(const FullGraphBase &_g)
+    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
     
     ///Number of nodes.
@@ -94 +87 @@
     int maxEdgeId() const { return EdgeNum-1; }
 
-    Node tail(Edge e) const { return e.n%NodeNum; }
-    Node head(Edge e) const { return e.n/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 tail(Edge e) const { return e.id % NodeNum; }
+    Node head(Edge e) const { return e.id / NodeNum; }
+
 
     /// Node ID.
@@ -114 +99 @@
     /// 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.
     
@@ -123 +109 @@
     /// 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.
@@ -135 +121 @@
     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;
-    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; }
-    };
+
 
     class Edge {
-      friend class FullGraph;
-      template <typename T> friend class EdgeMap;
+      friend class FullGraphBase;
       
-      friend class Node;
-      friend class NodeIt;
     protected:
-      int n; //NodeNum*head+tail;
-      friend int FullGraph::id(Edge e);
-
-      Edge(int nn) : n(nn) {}
-      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
+      int id;  // NodeNum * head + tail;
+
+      Edge(int _id) : id(_id) {}
+
+      Edge(const FullGraphBase& _graph, int tail, int head) 
+        : id(_graph.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;}
+      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 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 first(Node& node) const {
+      node.id = NodeNum-1;
+    }
+
+    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;
+    }
+    
+    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();
+  }
+
   /// @}  
 

src/lemon/list_graph.h

@@ -1 @@
-/* -*- 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 <vector>
-#include <climits>
-
-#include <lemon/invalid.h>
-
-#include <lemon/map_registry.h>
-#include <lemon/array_map.h>
-
-#include <lemon/map_defines.h>
+#include <lemon/erasable_graph_extender.h>
+#include <lemon/clearable_graph_extender.h>
+#include <lemon/extendable_graph_extender.h>
+
+#include <lemon/idmappable_graph_extender.h>
+
+#include <lemon/iterable_graph_extender.h>
+
+#include <lemon/alteration_observer_registry.h>
+
+#include <lemon/default_map.h>
 
 
 namespace lemon {
 
-/// \addtogroup graphs
-/// @{
-
-  ///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 
-    {
+  class ListGraphBase {
+
+    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;
@@ -64 +33 @@
 
     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;
-    
-    class Node;
-    class Edge;
-
-    
-  public:
-
-    class NodeIt;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-
-    // Create map registries.
-    CREATE_MAP_REGISTRIES;
-    // Create node and edge maps.
-    CREATE_MAPS(ArrayMap);
-
-  public:
-
-    ListGraph() 
+    typedef ListGraphBase Graph;
+    
+    class Node {
+      friend class Graph;
+    protected:
+
+      int id;
+      Node(int pid) { id = pid;}
+
+    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;}
+    };
+
+    class Edge {
+      friend class Graph;
+    protected:
+
+      int id;
+      Edge(int pid) { id = pid;}
+
+    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); };
@@ -121 +91 @@
     ///\sa id(Node)
     int maxNodeId() const { return nodes.size()-1; } 
+
     /// Maximum edge ID.
     
@@ -127 +98 @@
     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. 
-    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; }
+    Node tail(Edge e) const { return edges[e.id].tail; }
+    Node head(Edge e) const { return edges[e.id].head; }
+
+
+    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;
+    }
+
+    
+    static int id(Node v) { return v.id; }
+    static int id(Edge e) { return e.id; }
 
     /// Adds a new node to the graph.
@@ -162 +153 @@
     /// \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;
@@ -182 +171 @@
       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].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].tail = u.id; 
+      edges[n].head = v.id;
+
+      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;
-
-      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.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) {
-      
-      if(edges[n].next_in!=-1)
+      nodes[u.id].first_out = nodes[v.id].first_in = n;
+
+      return Edge(n);
+    }
+    
+    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;
+
+    }
+    
+    void erase(const Edge& edge) {
+      int n = edge.id;
+      
+      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;
-      
-      if(edges[n].next_out!=-1)
+      } 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)
+      } 
+
+      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(); }      
-    };
+      first_node = first_free_node = first_free_edge = -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 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);
-    }
-
-  };
-
-  ///A graph class containing only nodes.
-
-  ///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 {
-
-    //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
+  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;
+
+  typedef ErasableListGraphBase ListGraph;
+
+}
+
+
+  
+
+#endif

src/lemon/preflow.h

@@ -141 +141 @@
               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) { }
 

src/lemon/skeletons/graph.h

@@ -24 +24 @@
 #include <lemon/invalid.h>
 #include <lemon/skeletons/maps.h>
+#include <lemon/concept_check.h>
+#include <lemon/skeletons/graph_component.h>
 
 namespace lemon {
@@ -31 +33 @@
     /// @{
 
-    /// 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.
-
-      /// 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
+      BaseGraphItem() {}
+      BaseGraphItem(Invalid) {}
+
+      // We explicitely list these:
+      BaseGraphItem(BaseGraphItem const&) {}
+      BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
+
+      bool operator==(BaseGraphItem) const { return false; }
+      bool operator!=(BaseGraphItem) const { return false; }
+
+      // Technical requirement. Do we really need this?
+      bool operator<(BaseGraphItem) const { return false; }
+    };
+
+
+    /// 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> {};
+    };
+
+
+
+    /**************** Concept checking classes ****************/
+
+    template<typename BGI>
+    struct BaseGraphItemConcept {
+      void constraints() {
+        BGI i1;
+        BGI i2 = i1;
+        BGI i3 = INVALID;
         
-        /// \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);
+        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);
-        }
+    };
+
+    
+    
+    class StaticGraph 
+      :  virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
+    public:
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
+    };
+
+    template <typename Graph>
+    struct StaticGraphConcept {
+      void constraints() {
+        function_requires<BaseGraphComponentConcept<Graph> >();
+        function_requires<IterableGraphComponentConcept<Graph> >();
+        function_requires<MappableGraphComponentConcept<Graph> >();
       }
-    }
-    
-    /// 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
-    {
+      Graph& graph;
+    };
+
+    class ExtendableGraph 
+      :  virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
     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() { }
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
     };
 
-    
-    ///\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
-    {
+    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.
-
-      /// 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) { }
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
     };
-    
-    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()));  
-    }
- 
+
+    template <typename Graph>
+    struct ErasableGraphConcept {
+      void constraints() {
+        function_requires<ExtendableGraphConcept<Graph> >();
+        function_requires<ErasableGraphComponentConcept<Graph> >();
+      }
+      Graph& graph;
+    };
+
     // @}
   } //namespace skeleton  

src/lemon/skeletons/maps.h

@@ -17 +17 @@
 #ifndef LEMON_MAPSKELETON_H
 #define LEMON_MAPSKELETON_H
+
+#include <lemon/concept_check.h>
 
 ///\ingroup skeletons
@@ -114 +116 @@
     };
 
+
+    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;
+    };
+    
+
     // @}
 

src/lemon/smart_graph.h

@@ -23 +23 @@
 
 #include <vector>
-#include <climits>
 
 #include <lemon/invalid.h>
 
-
-#include <lemon/array_map.h>
-
-#include <lemon/map_registry.h>
-
-#include <lemon/map_defines.h>
+#include <lemon/erasable_graph_extender.h>
+#include <lemon/clearable_graph_extender.h>
+#include <lemon/extendable_graph_extender.h>
+
+#include <lemon/idmappable_graph_extender.h>
+
+#include <lemon/iterable_graph_extender.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.
@@ -57 +63 @@
   ///
   ///\author Alpar Juttner
-  class SmartGraph {
+  class SmartGraphBase {
 
     struct NodeT 
@@ -78 +84 @@
   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.
@@ -116 +113 @@
     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.
@@ -148 +136 @@
       Node n; n.n=nodes.size();
       nodes.push_back(NodeT()); //FIXME: Hmmm...
-
-      
-      node_maps.add(n);
       return n;
     }
@@ -160 +145 @@
       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;
@@ -183 +166 @@
     
     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:
@@ -208 +183 @@
       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 SymSmartGraph;
-      
-      friend class Node;
-      friend class NodeIt;
+      friend class SmartGraphBase;
+
     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; }
@@ -248 +198 @@
       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; }
-   };
-    
-    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 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;
+    }
+    
+    void nextIn(Edge& edge) const {
+      edge.n = edges[edge.n].next_in;
+    }
 
   };
 
-
-
-  class SymSmartGraph : public SmartGraph {
-    typedef SmartGraph Parent;
-  public:
-
-    typedef SymSmartGraph Graph;
-
-    typedef SmartGraph::Node Node;
-    typedef SmartGraph::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 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;
-    }
-    
-
-    };*/
-  
+  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;
+
+
+  template <>
+  int countNodes<SmartGraph>(const SmartGraph& graph) {
+    return graph.nodeNum();
+  }
+
+  template <>
+  int countEdges<SmartGraph>(const SmartGraph& graph) {
+    return graph.edgeNum();
+  }
+
   /// @}  
 } //namespace lemon

src/lemon/suurballe.h

@@ -126 +126 @@
       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]){

src/lemon/vector_map.h

@@ -19 +19 @@
 
 #include <vector>
-
-#include <lemon/map_iterator.h>
-#include <lemon/map_bits.h>
+#include <algorithm>
+
+#include <lemon/alteration_observer_registry.h>
 
 ///\ingroup graphmaps
@@ -32 +32 @@
   /// @{
   
-  /** 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 +74 @@
 
   public:
-
 
     /// The value type of the map.
@@ -83 +89 @@
     typedef typename Container::const_pointer ConstPointerType;
 
-    /// Constructor to attach the new map into a registry.
-
-    /** Constructor to attach the new map into a registry.
-     *  It adds all the nodes or edges of the graph to the map.
+    /// Constructor to attach the new map into the registry.
+
+    /// 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. 
+
+    /// 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);
+    }
+
+    VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
+      if (copy.attached()) {
+        attach(*copy.getRegistry());
+        container = copy.container;
+      }
+    }
+
+
+    /** Assign operator to copy a map of the same map type.
      */
-    VectorMap(const Graph& g, MapRegistry& r) 
-      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
-
-    /// 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) {}
-
-    /// 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];
-      }
-    }
-
-    /// 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& operator=(const VectorMap<MapRegistry, TT>& c) {
-      if (MapBase::getGraph() != c.getGraph()) {
-        MapBase::operator=(c);
-        container.resize(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& operator=(const VectorMap& copy) {
+      if (&copy == this) return *this;
+      
+      if (graph != copy.graph) {
+        if (attached()) {
+          detach();
+        }
+        if (copy.attached()) {
+          attach(*copy.getRegistry());
+        }
+      }
+      container = copy.container;
+
       return *this;
     }
 
+
+    virtual ~VectorMap() {
+      if (attached()) {
+        detach();
+      }
+    }
+
+    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];
-    }
-
-    ///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;
-    }
+      return container[IdMap(*graph)[key]];
+    }
+
+
+    /// 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);
@@ -179 +188 @@
     /// 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.
-
-    /** Makes empty the map. It called by the map registry 
-     *  and it overrides the \ref MapRegistry::MapBase MapBase's
-     *  clear() member function.
-     */
-
+    /// Buildes the map.
+                
+    /// It buildes the map. It called by the observer registry
+    /// and it overrides the build() member function of the observer base.
+
+    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) {}
+
+    };
+    
   };
   

src/test/Makefile.am

@@ -3 +3 @@
 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 = \
@@ -10 +15 @@
         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 \
@@ -21 +26 @@
         time_measure_test \
         unionfind_test \
+        graph_wrapper_test \
         xy_test
 
@@ -30 +36 @@
 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

src/test/graph_test.cc

@@ -1 @@
-/* -*- 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;
-
-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 &);
+using namespace lemon::skeleton;
 
 
-//Compile SymListGraph
-//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
-//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
-//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
+int main() {
+  ///\file
+  { // checking graph components
+    function_requires<BaseGraphComponentConcept<BaseGraphComponent> >();
 
-//Compile FullGraph
-template void lemon::skeleton::checkCompileStaticGraph<FullGraph>(FullGraph &);
-template
-void lemon::skeleton::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
+    function_requires<BaseIterableGraphComponentConcept<BaseIterableGraphComponent> >();
 
-//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> &);
+    function_requires<IDableGraphComponentConcept<IDableGraphComponent> >();
+    function_requires<MaxIDableGraphComponentConcept<MaxIDableGraphComponent> >();
 
-//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> &);
+    function_requires<BaseExtendableGraphComponentConcept<BaseExtendableGraphComponent> >();
+    function_requires<BaseErasableGraphComponentConcept<BaseErasableGraphComponent> >();
+    function_requires<BaseClearableGraphComponentConcept<BaseClearableGraphComponent> >();
 
+    function_requires<IterableGraphComponentConcept<IterableGraphComponent> >();
 
-int main() 
-{
-  {
-    SmartGraph G;
-    addPetersen(G);
-    bidirPetersen(G);
-    checkPetersen(G);
+    function_requires<IdMappableGraphComponentConcept<IdMappableGraphComponent> >();
+    function_requires<MappableGraphComponentConcept<MappableGraphComponent> >();
+
+    function_requires<ExtendableGraphComponentConcept<ExtendableGraphComponent> >();
+    function_requires<ErasableGraphComponentConcept<ErasableGraphComponent> >();
+    function_requires<ClearableGraphComponentConcept<ClearableGraphComponent> >();
   }
-  {
-    ListGraph G;
-    addPetersen(G);
-    bidirPetersen(G);
-    checkPetersen(G);
+  { // checking skeleton graphs
+    function_requires<StaticGraphConcept<StaticGraph> >();
+    function_requires<ExtendableGraphConcept<ExtendableGraph> >();
+    function_requires<ErasableGraphConcept<ErasableGraph> >();
   }
-  {
-    //    SymSmartGraph G;
-    //    addPetersen(G);
-    //    checkPetersen(G);
+  { // checking list graph
+    function_requires<ErasableGraphConcept<ListGraph> >();
+
+    checkGraph<ListGraph>();
+    checkGraphNodeMap<ListGraph>();
+    checkGraphEdgeMap<ListGraph>();
   }
-  {
-    //    SymListGraph G;
-    //    addPetersen(G);
-    //    checkPetersen(G);
+  { // checking smart graph
+    function_requires<ExtendableGraphConcept<SmartGraph> >();
+
+    checkGraph<SmartGraph>();
+    checkGraphNodeMap<SmartGraph>();
+    checkGraphEdgeMap<SmartGraph>();
   }
-
-  ///\file
-  ///\todo map tests.
-  ///\todo copy constr tests.
+  { // checking full graph
+    function_requires<StaticGraphConcept<FullGraph> >();
+  }
 
   std::cout << __FILE__ ": All tests passed.\n";

src/test/graph_test.h

@@ -22 +22 @@
 //! \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

src/test/graph_wrapper_test.cc

@@ -16 +16 @@
 
 #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>
@@ -33 +36 @@
 
 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";
 

src/test/test_tools.h

@@ -71 +71 @@
 
 template<typename Graph>
-PetStruct<Graph> addPetersen(Graph &G,int num=5)
+PetStruct<Graph> addPetersen(Graph &G,int num = 5)
 {
   PetStruct<Graph> n;
@@ -82 +82 @@
  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);
+  }  
 }
 

src/work/klao/TODO

@@ +1 @@
+full_graph.h -t atnez(et)ni!
+
 megcsinalni, hogy mukodjon a kereses a doksiban