Changeset 961:289d80c33f04 in lemon-0.x for src/lemon/concept

Timestamp:

11/04/04 23:04:51 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

• Somewhat less redundant and a bit more correct graph concepts.
• graph_wrapper_test does not compile

Location:

src/lemon/concept

Files:

• graph.h (modified) (6 diffs)
• graph_component.h (modified) (28 diffs)

src/lemon/concept/graph.h

@@ -766 +766 @@
 
 
-    /// \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 +775 @@
       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 +824 @@
 
 
-    /**************** 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 +839 @@
     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 +859 @@
         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 +875 @@
         function_requires<ErasableGraphComponentConcept<Graph> >();
       }
-      Graph& graph;
     };
 

src/lemon/concept/graph_component.h

@@ -29 +29 @@
   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 +168 @@
         /// 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 +175 @@
         /// \sa operator==(const Node& n)
         ///
-        bool operator!=(const Node&) { return true;}
+        bool operator!=(const Node&) const { return true;}
 
         /// Comparison operator.
@@ -86 +183 @@
         /// 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 +218 @@
         /// 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 +225 @@
         /// \sa operator==(const Edge& n)
         ///
-        bool operator!=(const Edge&) { return true;}
+        bool operator!=(const Edge&) const { return true;}
 
         /// Comparison operator.
@@ -136 +233 @@
         /// 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 +248 @@
       Node tail(const Edge&) const { return INVALID;}
     };
+
 
     /// Concept check structure for BaseGraph.
@@ -163 +261 @@
       
       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 +345 @@
     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 +405 @@
 
       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 +448 @@
 
       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 +494 @@
     struct BaseExtendableGraphComponentConcept {
       void constraints() {
+        function_requires< BaseGraphComponentConcept<Graph> >();
         typename Graph::Node node_a, node_b;
         node_a = graph.addNode();
@@ -453 +536 @@
     struct BaseErasableGraphComponentConcept {
       void constraints() {
+        function_requires< BaseGraphComponentConcept<Graph> >();
         typename Graph::Node node;
         graph.erase(node);
@@ -484 +568 @@
     struct BaseClearableGraphComponentConcept {
       void constraints() {
+        function_requires< BaseGraphComponentConcept<Graph> >();
         graph.clear();
       }
@@ -491 +576 @@
 
 
-    class IterableGraphComponent : virtual public BaseGraphComponent {
+    class IterableGraphComponent :
+      virtual public BaseIterableGraphComponent {
 
     public:
@@ -504 +590 @@
         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 +604 @@
         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 +618 @@
         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 +632 @@
         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 +648 @@
 
       void constraints() {
-  
+        function_requires< BaseIterableGraphComponentConcept<Graph> >();
+
         typedef typename Graph::Node Node;
         typedef typename Graph::NodeIt NodeIt;
@@ -566 +657 @@
         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 +670 @@
       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 +692 @@
     struct IdMappableGraphComponentConcept {
       void constraints() {      
+        function_requires< BaseGraphComponentConcept<Graph> >();
         {
           typedef typename Graph::EdgeIdMap EdgeIdMap;
@@ -720 +754 @@
 
       void constraints() {
+        function_requires< BaseGraphComponentConcept<Graph> >();
         { // int map test
           typedef typename Graph::template NodeMap<int> IntNodeMap;
@@ -768 +803 @@
     struct ExtendableGraphComponentConcept {
       void constraints() {
+        function_requires< BaseGraphComponentConcept<Graph> >();
         typename Graph::Node node_a, node_b;
         node_a = graph.addNode();
@@ -792 +828 @@
     struct ErasableGraphComponentConcept {
       void constraints() {
+        function_requires< BaseGraphComponentConcept<Graph> >();
         typename Graph::Node node;
         graph.erase(node);
@@ -816 +853 @@
     struct ClearableGraphComponentConcept {
       void constraints() {
+        function_requires< BaseGraphComponentConcept<Graph> >();
         graph.clear();
       }