# HG changeset patch
# User klao
# Date 1099605891 0
# Node ID 289d80c33f04b70a1ed3fa3f95daf59eed864d8e
# Parent  908a1a6f0752748cab01ac97ff121bf840b779c3
* Somewhat less redundant and a bit more correct graph concepts.
* graph_wrapper_test does not compile

diff -r 908a1a6f0752 -r 289d80c33f04 src/lemon/concept/graph.h
--- a/src/lemon/concept/graph.h	Thu Nov 04 21:28:55 2004 +0000
+++ b/src/lemon/concept/graph.h	Thu Nov 04 22:04:51 2004 +0000
@@ -765,26 +765,6 @@
     /************* New GraphBase stuff **************/
 
 
-    /// \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
 
     /// This class describes a minimal concept which can be extended to a
@@ -794,11 +774,14 @@
 
       GraphBase() {}
 
+      /// \bug Should we demand that Node and Edge be subclasses of the
+      /// Graph class???
 
-      /// \bug Nodes and Edges are comparable each other
-      
-      class Node : public BaseGraphItem {};
-      class Edge : public BaseGraphItem {};
+      typedef GraphItem<'n'> Node;
+      typedef GraphItem<'e'> Edge;
+
+//       class Node : public BaseGraphItem<'n'> {};
+//       class Edge : public BaseGraphItem<'e'> {};
 
       // Graph operation
       void firstNode(Node &n) const { }
@@ -840,27 +823,13 @@
 
 
 
-    /**************** 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;
       typedef BaseGraphComponent::Edge Edge;
@@ -869,15 +838,14 @@
     template <typename Graph>
     struct StaticGraphConcept {
       void constraints() {
-	function_requires<BaseGraphComponentConcept<Graph> >();
 	function_requires<IterableGraphComponentConcept<Graph> >();
 	function_requires<MappableGraphComponentConcept<Graph> >();
       }
-      Graph& graph;
     };
 
     class ExtendableGraph 
-      :  virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
+      :  virtual public BaseGraphComponent, public StaticGraph,
+	 public ExtendableGraphComponent, public ClearableGraphComponent {
     public:
       typedef BaseGraphComponent::Node Node;
       typedef BaseGraphComponent::Edge Edge;
@@ -890,11 +858,11 @@
 	function_requires<ExtendableGraphComponentConcept<Graph> >();
 	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;
       typedef BaseGraphComponent::Edge Edge;
@@ -906,7 +874,6 @@
 	function_requires<ExtendableGraphConcept<Graph> >();
 	function_requires<ErasableGraphComponentConcept<Graph> >();
       }
-      Graph& graph;
     };
 
     // @}
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;
diff -r 908a1a6f0752 -r 289d80c33f04 src/test/Makefile.am
--- a/src/test/Makefile.am	Thu Nov 04 21:28:55 2004 +0000
+++ b/src/test/Makefile.am	Thu Nov 04 22:04:51 2004 +0000
@@ -17,7 +17,6 @@
 	graph_utils_test \
 	kruskal_test \
 	min_cost_flow_test \
-	new_graph_test \
 	suurballe_test \
 	path_test \
 	preflow_test \
@@ -25,7 +24,6 @@
 	test_tools_pass \
 	time_measure_test \
 	unionfind_test \
-	graph_wrapper_test \
 	xy_test
 
 TESTS = $(check_PROGRAMS)
@@ -39,7 +37,6 @@
 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
 kruskal_test_SOURCES = kruskal_test.cc
 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
-new_graph_test_SOURCES = new_graph_test.cc
 suurballe_test_SOURCES = suurballe_test.cc
 path_test_SOURCES = path_test.cc
 preflow_test_SOURCES = preflow_test.cc
diff -r 908a1a6f0752 -r 289d80c33f04 src/test/new_graph_test.cc
--- a/src/test/new_graph_test.cc	Thu Nov 04 21:28:55 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-/* -*- C++ -*-
- * src/test/new_graph_test.cc - Part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Combinatorial Optimization Research Group, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#include <lemon/concept/graph.h>
-// #include <boost/concept_check.hpp>
-
-using namespace lemon::concept;
-
-// Borrowed from boost:
-template <class T> inline void ignore_unused_variable_warning(const T&) { }
-
-int main()
-{
-  //    This is the "right" way to check a concept:
-  // boost::function_requires< BaseGraphItemConcept<BaseGraphItem> >();
-
-  //    which is equivalent (considering compile-time checks) to
-  // BaseGraphItemConcept<BaseGraphItem> bgic;
-  // bgic.constraints();
-  //    but not actually call or intatiates anything...
-  //    It's doing aproximately this:
-  typedef BaseGraphItemConcept<BaseGraphItem> CC;
-  void (CC::*x)() = &CC::constraints;
-  ignore_unused_variable_warning(x);
-  //    But even more hackish...
-}