Index: src/lemon/concept/graph.h
===================================================================
--- src/lemon/concept/graph.h	(revision 959)
+++ src/lemon/concept/graph.h	(revision 961)
@@ -766,24 +766,4 @@
 
 
-    /// \bug The nodes and edges are not allowed to inherit from the
-    /// same baseclass.
-
-    class BaseGraphItem {
-    public:
-      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
 
@@ -795,9 +775,12 @@
       GraphBase() {}
 
-
-      /// \bug Nodes and Edges are comparable each other
-      
-      class Node : public BaseGraphItem {};
-      class Edge : public BaseGraphItem {};
+      /// \bug Should we demand that Node and Edge be subclasses of the
+      /// Graph class???
+
+      typedef GraphItem<'n'> Node;
+      typedef GraphItem<'e'> Edge;
+
+//       class Node : public BaseGraphItem<'n'> {};
+//       class Edge : public BaseGraphItem<'e'> {};
 
       // Graph operation
@@ -841,25 +824,11 @@
 
 
-    /**************** Concept checking classes ****************/
-
-    template<typename BGI>
-    struct BaseGraphItemConcept {
-      void constraints() {
-	BGI i1;
-	BGI i2 = i1;
-	BGI i3 = INVALID;
-	
-	i1 = i3;
-	if( i1 == i3 ) {
-	  if ( i2 != i3 && i3 < i2 )
-	    return;
-	}
-      }
-    };
-
-    
+
+    /**************** The full-featured graph concepts ****************/
+
     
     class StaticGraph 
-      :  virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
+      :  virtual public BaseGraphComponent,
+	 public IterableGraphComponent, public MappableGraphComponent {
     public:
       typedef BaseGraphComponent::Node Node;
@@ -870,13 +839,12 @@
     struct StaticGraphConcept {
       void constraints() {
-	function_requires<BaseGraphComponentConcept<Graph> >();
 	function_requires<IterableGraphComponentConcept<Graph> >();
 	function_requires<MappableGraphComponentConcept<Graph> >();
       }
-      Graph& graph;
     };
 
     class ExtendableGraph 
-      :  virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
+      :  virtual public BaseGraphComponent, public StaticGraph,
+	 public ExtendableGraphComponent, public ClearableGraphComponent {
     public:
       typedef BaseGraphComponent::Node Node;
@@ -891,9 +859,9 @@
 	function_requires<ClearableGraphComponentConcept<Graph> >();
       }
-      Graph& graph;
     };
 
     class ErasableGraph 
-      :  virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
+      :  virtual public BaseGraphComponent, public ExtendableGraph,
+	 public ErasableGraphComponent {
     public:
       typedef BaseGraphComponent::Node Node;
@@ -907,5 +875,4 @@
 	function_requires<ErasableGraphComponentConcept<Graph> >();
       }
-      Graph& graph;
     };
 
Index: src/lemon/concept/graph_component.h
===================================================================
--- src/lemon/concept/graph_component.h	(revision 959)
+++ src/lemon/concept/graph_component.h	(revision 961)
@@ -29,8 +29,105 @@
   namespace concept {
 
+
+    /****************   Graph iterator concepts   ****************/
+
+    /// Skeleton class for graph Node and Edge
+
+    /// \note Because Node and Edge are forbidden to inherit from the same
+    /// base class, this is a template. For Node you shoul instantiate it
+    /// with character 'n' and for Edge with 'e'.
+
+    template<char Ch>
+    class GraphItem {
+    public:
+      GraphItem() {}
+      GraphItem(Invalid) {}
+
+      // We explicitely list these:
+      GraphItem(GraphItem const&) {}
+      GraphItem& operator=(GraphItem const&) { return *this; }
+
+      bool operator==(GraphItem) const { return false; }
+      bool operator!=(GraphItem) const { return false; }
+
+      // Technical requirement. Do we really need this?
+      bool operator<(GraphItem) const { return false; }
+    };
+
+
+    template<typename GI>
+    struct GraphItemConcept {
+      void constraints() {
+	GI i1;
+	GI i2 = i1;
+	GI i3 = INVALID;
+	
+	i1 = i2 = i3;
+
+	bool b;
+	b = (ia == ib) && (ia != ib) && (ia < ib);
+	b = (ia == INVALID) && (ib != INVALID);
+      }
+
+      const GI &ia;
+      const GI &ib;
+    };
+
+
+    template<typename Iter, typename Graph, typename BaseItem>
+    struct GraphIteratorConcept {
+      void constraints() {
+	function_requires< GraphItemConcept<Iter> >();
+	Iter it1(g);
+
+	/// \todo Do we need NodeIt(Node) kind of constructor?
+	//	Iter it2(bj);
+	Iter it2;
+
+	it2 = ++it1;
+	++it2 = it1;
+	++(++it1);
+	/// \bug This should be: is_base_and_derived<BaseItem, Iter>
+	BaseItem bi = it1;
+	bi = it2;
+      }
+
+      BaseItem bj;
+      Graph g;
+    };
+
+    template<typename Iter, typename Graph>
+    struct GraphIncIteratorConcept {
+      typedef typename Graph::Node Node;
+      typedef typename Graph::Edge Edge;
+      void constraints() {
+	function_requires< GraphItemConcept<Iter> >();
+	Iter it1(graph, node);
+	/// \todo Do we need OutEdgeIt(Edge) kind of constructor?
+	//	Iter it2(edge);
+	Iter it2;
+
+	it2 = ++it1;
+	++it2 = it1;
+	++(++it1);
+	Edge e = it1;
+	e = it2;
+      }
+
+      Edge edge;
+      Node node;
+      Graph graph;
+    };
+
+
+
     /// An empty base graph class.
   
-    /// This class provides the most minimal features of a graph structure.
-    /// All the graph concepts have to be conform to this base graph.
+    /// This class provides the minimal set of features needed for a graph
+    /// structure. All graph concepts have to be conform to this base
+    /// graph.
+    ///
+    /// \bug This is not true. The minimal graph concept is the
+    /// BaseIterableGraphComponent.
 
     class BaseGraphComponent {
@@ -71,5 +168,5 @@
 	/// Two iterators are equal if and only if they represents the
 	/// same node in the graph or both are invalid.
-	bool operator==(const Node&) { return true;}
+	bool operator==(const Node&) const { return true;}
 
 
@@ -78,5 +175,5 @@
 	/// \sa operator==(const Node& n)
 	///
-	bool operator!=(const Node&) { return true;}
+	bool operator!=(const Node&) const { return true;}
 
  	/// Comparison operator.
@@ -86,5 +183,5 @@
 	/// This ordering can be different from the iterating order of nodes.
 	/// \todo Possibly we don't need it.
-	bool operator<(const Node&) { return true;}
+	bool operator<(const Node&) const { return true;}
       };
 
@@ -121,5 +218,5 @@
 	/// Two iterators are equal if and only if they represents the
 	/// same edge in the graph or both are invalid.
-	bool operator==(const Edge&) { return true;}
+	bool operator==(const Edge&) const { return true;}
 
 
@@ -128,5 +225,5 @@
 	/// \sa operator==(const Edge& n)
 	///
-	bool operator!=(const Edge&) { return true;}
+	bool operator!=(const Edge&) const { return true;}
 
  	/// Comparison operator.
@@ -136,5 +233,5 @@
 	/// This ordering can be different from the iterating order of edges.
 	/// \todo Possibly we don't need it.
-	bool operator<(const Edge&) { return true;}
+	bool operator<(const Edge&) const { return true;}
       };
 
@@ -151,4 +248,5 @@
       Node tail(const Edge&) const { return INVALID;}
     };
+
 
     /// Concept check structure for BaseGraph.
@@ -163,22 +261,6 @@
       
       void constraints() {
-	{
-	  Node ni; 
-	  Node nj(ni); 
-	  Node nk(INVALID);
-	  ni = nj;
-	  bool b; b = true;
-	  b = (ni == INVALID); b = (ni != INVALID);
-	  b = (ni==nj); b = (ni != nj); b=( ni < nj);
-	}
-	{
-	  Edge ei; 
-	  Edge ej(ei); 
-	  Edge ek(INVALID);
-	  ei = ej;
-	  bool b; b = true;
-	  b = (ei == INVALID); b = (ei != INVALID);
-	  b = (ei==ej); b = (ei != ej); b=( ei < ej);
-	}
+	function_requires< GraphItemConcept<Node> >();
+	function_requires< GraphItemConcept<Edge> >();
 	{
 	  const Graph& const_graph = graph;
@@ -263,27 +345,27 @@
     struct BaseIterableGraphComponentConcept {
       
-      void constraints() { 
-	const Graph& const_graph = graph;
+      void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node;      
 	typename Graph::Edge edge;
 	{
-	  const_graph.first(node);
-	  const_graph.next(node);
+	  graph.first(node);
+	  graph.next(node);
 	}
 	{
-	  const_graph.first(edge);
-	  const_graph.next(edge);
+	  graph.first(edge);
+	  graph.next(edge);
 	}
 	{
-	  const_graph.firstIn(edge, node);
-	  const_graph.nextIn(edge);
+	  graph.firstIn(edge, node);
+	  graph.nextIn(edge);
 	}
 	{
-	  const_graph.firstOut(edge, node);
-	  const_graph.nextOut(edge);
+	  graph.firstOut(edge, node);
+	  graph.nextOut(edge);
 	}
       }
 
-      Graph& graph;
+      const Graph& graph;
     };
 
@@ -323,14 +405,14 @@
 
       void constraints() {
-	const Graph& const_graph = graph;
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node;
-	int nid = const_graph.id(node);
-	nid = const_graph.id(node);
+	int nid = graph.id(node);
+	nid = graph.id(node);
 	typename Graph::Edge edge;
-	int eid = const_graph.id(edge);
-	eid = const_graph.id(edge);
-      }
-
-      Graph& graph;
+	int eid = graph.id(edge);
+	eid = graph.id(edge);
+      }
+
+      const Graph& graph;
     };
 
@@ -366,12 +448,12 @@
 
       void constraints() {
-	const Graph& const_graph = graph;
-	int nid = const_graph.maxEdgeId();
+	function_requires< BaseGraphComponentConcept<Graph> >();
+	int nid = graph.maxEdgeId();
 	ignore_unused_variable_warning(nid);
-	int eid = const_graph.maxNodeId();
+	int eid = graph.maxNodeId();
 	ignore_unused_variable_warning(eid);
       }
 
-      Graph& graph;
+      const Graph& graph;
     };
 
@@ -412,4 +494,5 @@
     struct BaseExtendableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node_a, node_b;
 	node_a = graph.addNode();
@@ -453,4 +536,5 @@
     struct BaseErasableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node;
 	graph.erase(node);
@@ -484,4 +568,5 @@
     struct BaseClearableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	graph.clear();
       }
@@ -491,5 +576,6 @@
 
 
-    class IterableGraphComponent : virtual public BaseGraphComponent {
+    class IterableGraphComponent :
+      virtual public BaseIterableGraphComponent {
 
     public:
@@ -504,11 +590,12 @@
 	NodeIt() {}
 	NodeIt(Invalid) {}
-	NodeIt(const Graph&) {}
+	// explicit NodeIt(Node) {}
+	explicit NodeIt(const Graph&) {}
 
 	NodeIt& operator++() { return *this; }
 	//	Node operator*() const { return INVALID; }
 
-	bool operator==(const NodeIt&) { return true;}
-	bool operator!=(const NodeIt&) { return true;}
+	bool operator==(const NodeIt&) const { return true;}
+	bool operator!=(const NodeIt&) const { return true;}
       };
 
@@ -517,11 +604,12 @@
 	EdgeIt() {}
 	EdgeIt(Invalid) {}
-	EdgeIt(const Graph&) {}
+	// explicit EdgeIt(Edge) {}
+	explicit EdgeIt(const Graph&) {}
 
 	EdgeIt& operator++() { return *this; }
 	//	Edge operator*() const { return INVALID; }
 
-	bool operator==(const EdgeIt&) { return true;}
-	bool operator!=(const EdgeIt&) { return true;}
+	bool operator==(const EdgeIt&) const { return true;}
+	bool operator!=(const EdgeIt&) const { return true;}
       };
 
@@ -530,11 +618,12 @@
 	InEdgeIt() {}
 	InEdgeIt(Invalid) {}
-	InEdgeIt(const Graph&, const Node&) {}
+	// explicit InEdgeIt(Edge) {}
+	explicit InEdgeIt(const Graph&, const Node&) {}
 
 	InEdgeIt& operator++() { return *this; }
 	//	Edge operator*() const { return INVALID; }
 
-	bool operator==(const InEdgeIt&) { return true;}
-	bool operator!=(const InEdgeIt&) { return true;}
+	bool operator==(const InEdgeIt&) const { return true;}
+	bool operator!=(const InEdgeIt&) const { return true;}
       };
 
@@ -543,11 +632,12 @@
 	OutEdgeIt() {}
 	OutEdgeIt(Invalid) {}
-	OutEdgeIt(const Graph&, const Node&) {}
+	// explicit OutEdgeIt(Edge) {}
+	explicit OutEdgeIt(const Graph&, const Node&) {}
 
 	OutEdgeIt& operator++() { return *this; }
 	//	Edge operator*() const { return INVALID; }
 
-	bool operator==(const OutEdgeIt&) { return true;}
-	bool operator!=(const OutEdgeIt&) { return true;}
+	bool operator==(const OutEdgeIt&) const { return true;}
+	bool operator!=(const OutEdgeIt&) const { return true;}
       };
 
@@ -558,5 +648,6 @@
 
       void constraints() {
-  
+  	function_requires< BaseIterableGraphComponentConcept<Graph> >();
+
 	typedef typename Graph::Node Node;
 	typedef typename Graph::NodeIt NodeIt;
@@ -566,66 +657,8 @@
 	typedef typename Graph::OutEdgeIt OutEdgeIt;
   
-	{
-	  NodeIt it; 
-	  NodeIt jt(it); 
-	  NodeIt kt(INVALID); 
-	  NodeIt lt(graph);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Node node = it;
-	  node = it;
-	}
-	{
-	  EdgeIt it; 
-	  EdgeIt jt(it); 
-	  EdgeIt kt(INVALID); 
-	  EdgeIt lt(graph);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Edge edge = it;
-	  edge = it;
-	}
-	{
-	  InEdgeIt it; 
-	  InEdgeIt jt(it); 
-	  InEdgeIt kt(INVALID); 
-	  Node node;
-	  InEdgeIt lt(graph, node);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Edge edge = it;
-	  edge = it;
-	}
-	{
-	  OutEdgeIt it; 
-	  OutEdgeIt jt(it); 
-	  OutEdgeIt kt(INVALID); 
-	  Node node;
-	  OutEdgeIt lt(graph, node);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Edge edge = it;
-	  edge = it;
-	}
+	function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
+	function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
+	function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
+	function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
       }
       Graph& graph;
@@ -637,8 +670,8 @@
       typedef IdMappableGraphComponent Graph;
 
-      typedef BaseGraphComponent::Node Node;
-      typedef BaseGraphComponent::Edge Edge;
-
-    public:
+    public:
+
+      typedef BaseGraphComponent::Node Node;
+      typedef BaseGraphComponent::Edge Edge;
 
       class NodeIdMap : public ReadMap<Node, int> {
@@ -659,4 +692,5 @@
     struct IdMappableGraphComponentConcept {
       void constraints() {	
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	{
 	  typedef typename Graph::EdgeIdMap EdgeIdMap;
@@ -720,4 +754,5 @@
 
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	{ // int map test
 	  typedef typename Graph::template NodeMap<int> IntNodeMap;
@@ -768,4 +803,5 @@
     struct ExtendableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node_a, node_b;
 	node_a = graph.addNode();
@@ -792,4 +828,5 @@
     struct ErasableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node;
 	graph.erase(node);
@@ -816,4 +853,5 @@
     struct ClearableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	graph.clear();
       }
