diff -r 908a1a6f0752 -r 289d80c33f04 src/lemon/concept/graph_component.h
--- a/src/lemon/concept/graph_component.h	Thu Nov 04 21:28:55 2004 +0000
+++ b/src/lemon/concept/graph_component.h	Thu Nov 04 22:04:51 2004 +0000
@@ -28,10 +28,107 @@
 namespace lemon {
   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 {
     public:
@@ -70,14 +167,14 @@
 
 	/// 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;}
 
 
 	/// Inequality operator.
 	
 	/// \sa operator==(const Node& n)
 	///
-	bool operator!=(const Node&) { return true;}
+	bool operator!=(const Node&) const { return true;}
 
  	/// Comparison operator.
 
@@ -85,7 +182,7 @@
 	///
 	/// 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;}
       };
 
       /// Edge class of the graph.
@@ -120,14 +217,14 @@
 
 	/// 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;}
 
 
 	/// Inequality operator.
 	
 	/// \sa operator==(const Edge& n)
 	///
-	bool operator!=(const Edge&) { return true;}
+	bool operator!=(const Edge&) const { return true;}
 
  	/// Comparison operator.
 
@@ -135,7 +232,7 @@
 	///
 	/// 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;}
       };
 
       ///Gives back the head node of an edge.
@@ -151,6 +248,7 @@
       Node tail(const Edge&) const { return INVALID;}
     };
 
+
     /// Concept check structure for BaseGraph.
 
     /// Concept check structure for BaseGraph.
@@ -162,24 +260,8 @@
       typedef typename Graph::Edge Edge;
       
       void constraints() {
-	{
-	  Node ni; 
-	  Node nj(ni); 
-	  Node nk(INVALID);
-	  ni = nj;
-	  bool b; b = true;
-	  b = (ni == INVALID); b = (ni != INVALID);
-	  b = (ni==nj); b = (ni != nj); b=( ni < nj);
-	}
-	{
-	  Edge ei; 
-	  Edge ej(ei); 
-	  Edge ek(INVALID);
-	  ei = ej;
-	  bool b; b = true;
-	  b = (ei == INVALID); b = (ei != INVALID);
-	  b = (ei==ej); b = (ei != ej); b=( ei < ej);
-	}
+	function_requires< GraphItemConcept<Node> >();
+	function_requires< GraphItemConcept<Edge> >();
 	{
 	  const Graph& const_graph = graph;
 	  Node n;
@@ -262,29 +344,29 @@
     template <typename Graph>
     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;
     };
 
     /// An empty idable base graph class.
@@ -322,16 +404,16 @@
     struct IDableGraphComponentConcept {
 
       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);
+	int eid = graph.id(edge);
+	eid = graph.id(edge);
       }
 
-      Graph& graph;
+      const Graph& graph;
     };
 
 
@@ -365,14 +447,14 @@
     struct MaxIDableGraphComponentConcept {
 
       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;
     };
 
     /// An empty extendable base graph class.
@@ -411,6 +493,7 @@
     template <typename Graph>
     struct BaseExtendableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node_a, node_b;
 	node_a = graph.addNode();
 	typename Graph::Edge edge;
@@ -452,6 +535,7 @@
     template <typename Graph>
     struct BaseErasableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node;
 	graph.erase(node);
 	typename Graph::Edge edge;
@@ -483,6 +567,7 @@
     template <typename Graph>
     struct BaseClearableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	graph.clear();
       }
 
@@ -490,7 +575,8 @@
     };
 
 
-    class IterableGraphComponent : virtual public BaseGraphComponent {
+    class IterableGraphComponent :
+      virtual public BaseIterableGraphComponent {
 
     public:
     
@@ -503,52 +589,56 @@
       public:
 	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;}
       };
 
       class EdgeIt : public Edge {
       public:
 	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;}
       };
 
       class InEdgeIt : public Edge {
       public:
 	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;}
       };
 
       class OutEdgeIt : public Edge {
       public:
 	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;}
       };
 
     };
@@ -557,7 +647,8 @@
     struct IterableGraphComponentConcept {
 
       void constraints() {
-  
+  	function_requires< BaseIterableGraphComponentConcept<Graph> >();
+
 	typedef typename Graph::Node Node;
 	typedef typename Graph::NodeIt NodeIt;
 	typedef typename Graph::Edge Edge;
@@ -565,68 +656,10 @@
 	typedef typename Graph::InEdgeIt InEdgeIt;
 	typedef typename Graph::OutEdgeIt OutEdgeIt;
   
-	{
-	  NodeIt it; 
-	  NodeIt jt(it); 
-	  NodeIt kt(INVALID); 
-	  NodeIt lt(graph);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Node node = it;
-	  node = it;
-	}
-	{
-	  EdgeIt it; 
-	  EdgeIt jt(it); 
-	  EdgeIt kt(INVALID); 
-	  EdgeIt lt(graph);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Edge edge = it;
-	  edge = it;
-	}
-	{
-	  InEdgeIt it; 
-	  InEdgeIt jt(it); 
-	  InEdgeIt kt(INVALID); 
-	  Node node;
-	  InEdgeIt lt(graph, node);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Edge edge = it;
-	  edge = it;
-	}
-	{
-	  OutEdgeIt it; 
-	  OutEdgeIt jt(it); 
-	  OutEdgeIt kt(INVALID); 
-	  Node node;
-	  OutEdgeIt lt(graph, node);
-	  it = jt;
-	  jt = ++it;
-	  bool b;
-	  b = (it == INVALID); 
-	  b = (it != INVALID);
-	  b = (it == jt); 
-	  b = (it != jt);
-	  Edge edge = it;
-	  edge = it;
-	}
+	function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
+	function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
+	function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
+	function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
       }
       Graph& graph;
     };
@@ -636,11 +669,11 @@
 
       typedef IdMappableGraphComponent Graph;
 
+    public:
+
       typedef BaseGraphComponent::Node Node;
       typedef BaseGraphComponent::Edge Edge;
 
-    public:
-
       class NodeIdMap : public ReadMap<Node, int> {
       public:
 	NodeIdMap(const Graph&) {}
@@ -658,6 +691,7 @@
     template <typename Graph>
     struct IdMappableGraphComponentConcept {
       void constraints() {	
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	{
 	  typedef typename Graph::EdgeIdMap EdgeIdMap;
 	  function_requires<ReadMapConcept<EdgeIdMap> >();
@@ -719,6 +753,7 @@
       };
 
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	{ // int map test
 	  typedef typename Graph::template NodeMap<int> IntNodeMap;
 	  function_requires<GraphMapConcept<IntNodeMap,Graph> >();
@@ -767,6 +802,7 @@
     template <typename Graph>
     struct ExtendableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node_a, node_b;
 	node_a = graph.addNode();
 	typename Graph::Edge edge;
@@ -791,6 +827,7 @@
     template <typename Graph>
     struct ErasableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	typename Graph::Node node;
 	graph.erase(node);
 	typename Graph::Edge edge;
@@ -815,6 +852,7 @@
     template <typename Graph>
     struct ClearableGraphComponentConcept {
       void constraints() {
+	function_requires< BaseGraphComponentConcept<Graph> >();
 	graph.clear();
       }
       Graph& graph;