COIN-OR::LEMON - Graph Library

Changeset 989:ca95f8b5c931 in lemon-0.x for src/lemon


Ignore:
Timestamp:
11/13/04 22:37:54 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1379
Message:

XyzConcept? moved to Xyz::Constraints
use checkConcept in the next way:

checkConcept<ErasableGraph?, ListGraph?>();
checkConcept<ReadWriteMap?<Node, Node>, PredMap?>;

Location:
src/lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/concept/graph.h

    r987 r989  
    102102//      bool operator!=(Node) const { return true; }
    103103
    104 //      ///Comparison operator.
    105 
    106 //      ///This is a strict ordering between the nodes.
    107 //      ///
    108 //      ///This ordering can be different from the order in which NodeIt
    109 //      ///goes through the nodes.
    110 //      ///\todo Possibly we don't need it.
    111 //      bool operator<(Node) const { return true; }
    112104//       };
    113105   
     
    189181//      ///
    190182//      bool operator!=(Edge) const { return true; }
    191 //      ///Comparison operator.
    192 
    193 //      ///This is a strict ordering between the nodes.
    194 //      ///
    195 //      ///This ordering can be different from the order in which NodeIt
    196 //      ///goes through the nodes.
    197 //      ///\todo Possibly we don't need it.
    198 //      bool operator<(Edge) const { return true; }
    199183//       };
    200184   
     
    340324//      EdgeIt& operator++() { return *this; }
    341325//       };
    342 
    343 //       /// First node of the graph.
    344 
    345 //       /// \retval i the first node.
    346 //       /// \return the first node.
    347 //       ///
    348 //       NodeIt& first(NodeIt& i) const { return i; }
    349 
    350 //       /// The first incoming edge.
    351 
    352 //       /// The first incoming edge.
    353 //       ///
    354 //       InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
    355 //       /// The first outgoing edge.
    356 
    357 //       /// The first outgoing edge.
    358 //       ///
    359 //       OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
    360 //       /// The first edge of the Graph.
    361 
    362 //       /// The first edge of the Graph.
    363 //       ///
    364 //       EdgeIt& first(EdgeIt& i) const { return i; }
    365 
    366326//       ///Gives back the target node of an edge.
    367327
     
    374334//       ///
    375335//       Node source(Edge) const { return INVALID; }
    376  
    377 //       ///Gives back the \e id of a node.
    378 
    379 //       ///\warning Not all graph structures provide this feature.
    380 //       ///
    381 //       ///\todo Should each graph provide \c id?
    382 //       int id(const Node&) const { return 0; }
    383 //       ///Gives back the \e id of an edge.
    384 
    385 //       ///\warning Not all graph structures provide this feature.
    386 //       ///
    387 //       ///\todo Should each graph provide \c id?
    388 //       int id(const Edge&) const { return 0; }
    389 
    390 //       ///\e
    391      
    392 //       ///\todo Should it be in the concept?
    393 //       ///
    394 //       int nodeNum() const { return 0; }
    395 //       ///\e
    396 
    397 //       ///\todo Should it be in the concept?
    398 //       ///
    399 //       int edgeNum() const { return 0; }
    400 
    401 
    402 //       ///Reference map of the nodes to type \c T.
     336//       /// Read write map of the nodes to type \c T.
    403337
    404338//       /// \ingroup concept
    405 //       ///Reference map of the nodes to type \c T.
     339//       /// ReadWrite map of the nodes to type \c T.
    406340//       /// \sa Reference
    407341//       /// \warning Making maps that can handle bool type (NodeMap<bool>)
    408342//       /// needs some extra attention!
    409 //       template<class T> class NodeMap : public ReferenceMap< Node, T >
     343//       template<class T>
     344//       class NodeMap : public ReadWriteMap< Node, T >
    410345//       {
    411346//       public:
     
    417352
    418353//      ///Copy constructor
    419 //      template<typename TT> NodeMap(const NodeMap<TT>&) { }
     354//      NodeMap(const NodeMap&) { }
    420355//      ///Assignment operator
    421 //      template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
    422 //      { return *this; }
    423 //       };
    424 
    425 //       ///Reference map of the edges to type \c T.
     356//      NodeMap& operator=(const NodeMap&) { return *this; }
     357//      // \todo fix this concept
     358//       };
     359
     360//       /// Read write map of the edges to type \c T.
    426361
    427362//       /// \ingroup concept
     
    430365//       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
    431366//       /// needs some extra attention!
    432 //       template<class T> class EdgeMap
    433 //      : public ReferenceMap<Edge,T>
     367//       template<class T>
     368//       class EdgeMap : public ReadWriteMap<Edge,T>
    434369//       {
    435370//       public:
     
    439374//      ///\e
    440375//      EdgeMap(const StaticGraph&, T) { }
    441    
    442376//      ///Copy constructor
    443 //      template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
     377//      EdgeMap(const EdgeMap&) { }
    444378//      ///Assignment operator
    445 //      template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
    446 //      { return *this; }
     379//      EdgeMap& operator=(const EdgeMap&) { return *this; }
     380//      // \todo fix this concept   
    447381//       };
    448382//     };
    449383
    450 //     struct DummyType {
    451 //       int value;
    452 //       DummyType() {}
    453 //       DummyType(int p) : value(p) {}
    454 //       DummyType& operator=(int p) { value = p; return *this;}
    455 //     };
    456    
    457 //     ///\brief Checks whether \c G meets the
    458 //     ///\ref lemon::concept::StaticGraph "StaticGraph" concept
    459 //     template<class Graph> void checkCompileStaticGraph(Graph &G)
    460 //     {
    461 //       typedef typename Graph::Node Node;
    462 //       typedef typename Graph::NodeIt NodeIt;
    463 //       typedef typename Graph::Edge Edge;
    464 //       typedef typename Graph::EdgeIt EdgeIt;
    465 //       typedef typename Graph::InEdgeIt InEdgeIt;
    466 //       typedef typename Graph::OutEdgeIt OutEdgeIt;
    467  
    468 //       {
    469 //      Node i; Node j(i); Node k(INVALID);
    470 //      i=j;
    471 //      bool b; b=true;
    472 //      b=(i==INVALID); b=(i!=INVALID);
    473 //      b=(i==j); b=(i!=j); b=(i<j);
    474 //       }
    475 //       {
    476 //      NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
    477 //      i=j;
    478 //      j=G.first(i);
    479 //      j=++i;
    480 //      bool b; b=true;
    481 //      b=(i==INVALID); b=(i!=INVALID);
    482 //      Node n(i);
    483 //      n=i;
    484 //      b=(i==j); b=(i!=j); b=(i<j);
    485 //      //Node ->NodeIt conversion
    486 //      NodeIt ni(G,n);
    487 //       }
    488 //       {
    489 //      Edge i; Edge j(i); Edge k(INVALID);
    490 //      i=j;
    491 //      bool b; b=true;
    492 //      b=(i==INVALID); b=(i!=INVALID);
    493 //      b=(i==j); b=(i!=j); b=(i<j);
    494 //       }
    495 //       {
    496 //      EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
    497 //      i=j;
    498 //      j=G.first(i);
    499 //      j=++i;
    500 //      bool b; b=true;
    501 //      b=(i==INVALID); b=(i!=INVALID);
    502 //      Edge e(i);
    503 //      e=i;
    504 //      b=(i==j); b=(i!=j); b=(i<j);
    505 //      //Edge ->EdgeIt conversion
    506 //      EdgeIt ei(G,e);
    507 //       }
    508 //       {
    509 //      Node n;
    510 //      InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
    511 //      i=j;
    512 //      j=G.first(i,n);
    513 //      j=++i;
    514 //      bool b; b=true;
    515 //      b=(i==INVALID); b=(i!=INVALID);
    516 //      Edge e(i);
    517 //      e=i;
    518 //      b=(i==j); b=(i!=j); b=(i<j);
    519 //      //Edge ->InEdgeIt conversion
    520 //      InEdgeIt ei(G,e);
    521 //       }
    522 //       {
    523 //      Node n;
    524 //      OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
    525 //      i=j;
    526 //      j=G.first(i,n);
    527 //      j=++i;
    528 //      bool b; b=true;
    529 //      b=(i==INVALID); b=(i!=INVALID);
    530 //      Edge e(i);
    531 //      e=i;
    532 //      b=(i==j); b=(i!=j); b=(i<j);
    533 //      //Edge ->OutEdgeIt conversion
    534 //      OutEdgeIt ei(G,e);
    535 //       }
    536 //       {
    537 //      Node n,m;
    538 //      n=m=INVALID;
    539 //      Edge e;
    540 //      e=INVALID;
    541 //      n=G.source(e);
    542 //      n=G.target(e);
    543 //       }
    544 //       // id tests
    545 //       { Node n; int i=G.id(n); i=i; }
    546 //       { Edge e; int i=G.id(e); i=i; }
    547 //       //NodeMap tests
    548 //       {
    549 //      Node k;
    550 //      typename Graph::template NodeMap<int> m(G);
    551 //      //Const map
    552 //      typename Graph::template NodeMap<int> const &cm = m;
    553 //      //Inicialize with default value
    554 //      typename Graph::template NodeMap<int> mdef(G,12);
    555 //      //Copy
    556 //      typename Graph::template NodeMap<int> mm(cm);
    557 //      //Copy from another type
    558 //      typename Graph::template NodeMap<double> dm(cm);
    559 //      //Copy to more complex type
    560 //      typename Graph::template NodeMap<DummyType> em(cm);
    561 //      int v;
    562 //      v=m[k]; m[k]=v; m.set(k,v);
    563 //      v=cm[k];
    564    
    565 //      m=cm; 
    566 //      dm=cm; //Copy from another type 
    567 //      em=cm; //Copy to more complex type
    568 //      {
    569 //        //Check the typedef's
    570 //        typename Graph::template NodeMap<int>::Value val;
    571 //        val=1;
    572 //        typename Graph::template NodeMap<int>::Key key;
    573 //        key = typename Graph::NodeIt(G);
    574 //      }
    575 //       } 
    576 //       { //bool NodeMap
    577 //      Node k;
    578 //      typename Graph::template NodeMap<bool> m(G);
    579 //      typename Graph::template NodeMap<bool> const &cm = m;  //Const map
    580 //      //Inicialize with default value
    581 //      typename Graph::template NodeMap<bool> mdef(G,12);
    582 //      typename Graph::template NodeMap<bool> mm(cm);   //Copy
    583 //      typename Graph::template NodeMap<int> dm(cm); //Copy from another type
    584 //      bool v;
    585 //      v=m[k]; m[k]=v; m.set(k,v);
    586 //      v=cm[k];
    587    
    588 //      m=cm; 
    589 //      dm=cm; //Copy from another type
    590 //      m=dm; //Copy to another type
    591 
    592 //      {
    593 //        //Check the typedef's
    594 //        typename Graph::template NodeMap<bool>::Value val;
    595 //        val=true;
    596 //        typename Graph::template NodeMap<bool>::Key key;
    597 //        key= typename Graph::NodeIt(G);
    598 //      }
    599 //       }
    600 //       //EdgeMap tests
    601 //       {
    602 //      Edge k;
    603 //      typename Graph::template EdgeMap<int> m(G);
    604 //      typename Graph::template EdgeMap<int> const &cm = m;  //Const map
    605 //      //Inicialize with default value
    606 //      typename Graph::template EdgeMap<int> mdef(G,12);
    607 //      typename Graph::template EdgeMap<int> mm(cm);   //Copy
    608 //      typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
    609 //      int v;
    610 //      v=m[k]; m[k]=v; m.set(k,v);
    611 //      v=cm[k];
    612    
    613 //      m=cm; 
    614 //      dm=cm; //Copy from another type
    615 //      {
    616 //        //Check the typedef's
    617 //        typename Graph::template EdgeMap<int>::Value val;
    618 //        val=1;
    619 //        typename Graph::template EdgeMap<int>::Key key;
    620 //        key= typename Graph::EdgeIt(G);
    621 //      }
    622 //       } 
    623 //       { //bool EdgeMap
    624 //      Edge k;
    625 //      typename Graph::template EdgeMap<bool> m(G);
    626 //      typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
    627 //      //Inicialize with default value
    628 //      typename Graph::template EdgeMap<bool> mdef(G,12);
    629 //      typename Graph::template EdgeMap<bool> mm(cm);   //Copy
    630 //      typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
    631 //      bool v;
    632 //      v=m[k]; m[k]=v; m.set(k,v);
    633 //      v=cm[k];
    634    
    635 //      m=cm; 
    636 //      dm=cm; //Copy from another type
    637 //      m=dm; //Copy to another type
    638 //      {
    639 //        //Check the typedef's
    640 //        typename Graph::template EdgeMap<bool>::Value val;
    641 //        val=true;
    642 //        typename Graph::template EdgeMap<bool>::Key key;
    643 //        key= typename Graph::EdgeIt(G);
    644 //      }
    645 //       }
    646 //     }
    647    
    648384//     /// An empty non-static graph class.
    649385   
     
    666402//       ///Add a new edge to the graph.
    667403
    668 //       ///Add a new edge to the graph with source node \c t
    669 //       ///and target node \c h.
     404//       ///Add a new edge to the graph with source node \c s
     405//       ///and target node \c t.
    670406//       ///\return the new edge.
    671 //       Edge addEdge(Node h, Node t) { return INVALID; }
     407//       Edge addEdge(Node s, Node t) { return INVALID; }
    672408   
    673409//       /// Resets the graph.
     
    678414//       void clear() { }
    679415//     };
    680 
    681    
    682 //     ///\brief Checks whether \c G meets the
    683 //     ///\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept
    684 //     template<class Graph> void checkCompileExtendableGraph(Graph &G)
    685 //     {
    686 //       checkCompileStaticGraph(G);
    687 
    688 //       typedef typename Graph::Node Node;
    689 //       typedef typename Graph::NodeIt NodeIt;
    690 //       typedef typename Graph::Edge Edge;
    691 //       typedef typename Graph::EdgeIt EdgeIt;
    692 //       typedef typename Graph::InEdgeIt InEdgeIt;
    693 //       typedef typename Graph::OutEdgeIt OutEdgeIt;
    694  
    695 //       Node n,m;
    696 //       n=G.addNode();
    697 //       m=G.addNode();
    698 //       Edge e;
    699 //       e=G.addEdge(n,m);
    700  
    701 //       //  G.clear();
    702 //     }
    703 
    704416
    705417//     /// An empty erasable graph class.
     
    726438//       void erase(Edge e) { }
    727439//     };
    728    
    729 //     template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
    730 //     {
    731 //       typename Graph::Edge e;
    732 //       G.erase(e);
    733 //     }
    734 
    735 //     template<class Graph> void checkCompileGraphEraseNode(Graph &G)
    736 //     {
    737 //       typename Graph::Node n;
    738 //       G.erase(n);
    739 //     }
    740 
    741 //     ///\brief Checks whether \c G meets the
    742 //     ///\ref lemon::concept::EresableGraph "EresableGraph" concept
    743 //     template<class Graph> void checkCompileErasableGraph(Graph &G)
    744 //     {
    745 //       checkCompileExtendableGraph(G);
    746 //       checkCompileGraphEraseNode(G);
    747 //       checkCompileGraphEraseEdge(G);
    748 //     }
    749 
    750 //     ///Checks whether a graph has findEdge() member function.
    751    
    752 //     ///\todo findEdge() might be a global function.
    753 //     ///
    754 //     template<class Graph> void checkCompileGraphFindEdge(Graph &G)
    755 //     {
    756 //       typedef typename Graph::NodeIt Node;
    757 //       typedef typename Graph::NodeIt NodeIt;
    758 
    759 //       G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
    760 //       G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 
    761 //     }
    762 
    763 
    764 
     440
     441   
    765442    /************* New GraphBase stuff **************/
    766443
     
    816493
    817494      template<typename T>
    818       class NodeMap : public GraphMap<Node, T, GraphBase> {};
     495      class NodeMap : public GraphMap<GraphBase, Node, T> {};
    819496
    820497      template<typename T>
    821       class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
     498      class EdgeMap : public GraphMap<GraphBase, Node, T> {};
    822499    };
    823500
     
    834511      typedef BaseGraphComponent::Node Node;
    835512      typedef BaseGraphComponent::Edge Edge;
    836     };
    837 
    838     template <typename Graph>
    839     struct StaticGraphConcept {
    840       void constraints() {
    841         function_requires<IterableGraphComponentConcept<Graph> >();
    842         function_requires<MappableGraphComponentConcept<Graph> >();
    843       }
     513
     514      template <typename _Graph>
     515      struct Constraints {
     516        void constraints() {
     517          checkConcept<IterableGraphComponent, _Graph>();
     518          checkConcept<MappableGraphComponent, _Graph>();
     519        }
     520      };
    844521    };
    845522
     
    850527      typedef BaseGraphComponent::Node Node;
    851528      typedef BaseGraphComponent::Edge Edge;
    852     };
    853 
    854     template <typename Graph>
    855     struct ExtendableGraphConcept {
    856       void constraints() {
    857         function_requires<StaticGraphConcept<Graph> >();
    858         function_requires<ExtendableGraphComponentConcept<Graph> >();
    859         function_requires<ClearableGraphComponentConcept<Graph> >();
    860       }
     529
     530      template <typename _Graph>
     531      struct Constraints {
     532        void constraints() {
     533          checkConcept<StaticGraph, _Graph >();
     534          checkConcept<ExtendableGraphComponent, _Graph >();
     535          checkConcept<ClearableGraphComponent, _Graph >();
     536        }
     537      };
    861538    };
    862539
     
    867544      typedef BaseGraphComponent::Node Node;
    868545      typedef BaseGraphComponent::Edge Edge;
    869     };
    870 
    871     template <typename Graph>
    872     struct ErasableGraphConcept {
    873       void constraints() {
    874         function_requires<ExtendableGraphConcept<Graph> >();
    875         function_requires<ErasableGraphComponentConcept<Graph> >();
    876       }
     546
     547      template <typename _Graph>
     548      struct Constraints {
     549        void constraints() {
     550          checkConcept<ExtendableGraph, _Graph >();
     551          checkConcept<ErasableGraphComponent, _Graph >();
     552        }
     553      };
    877554    };
    878555
  • src/lemon/concept/graph_component.h

    r987 r989  
    3838    /// with character 'n' and for Edge with 'e'.
    3939
    40     template<char Ch>
     40    template<char _selector>
    4141    class GraphItem {
    4242    public:
     43      /// Default constructor.
     44     
     45      /// @warning The default constructor sets the item
     46      /// to an undefined value.
    4347      GraphItem() {}
     48      /// Copy constructor.
     49     
     50      /// Copy constructor.
     51      ///
     52      GraphItem(GraphItem const&) {}
     53      /// Invalid constructor \& conversion.
     54
     55      /// This constructor initializes the item to be invalid.
     56      /// \sa Invalid for more details.
    4457      GraphItem(Invalid) {}
    45 
    46       // We explicitely list these:
    47       GraphItem(GraphItem const&) {}
     58      /// Assign operator for nodes.
     59
     60      /// The nodes are assignable.
     61      ///
    4862      GraphItem& operator=(GraphItem const&) { return *this; }
    49 
     63      /// Equality operator.
     64     
     65      /// Two iterators are equal if and only if they represents the
     66      /// same node in the graph or both are invalid.
    5067      bool operator==(GraphItem) const { return false; }
     68      /// Inequality operator.
     69       
     70      /// \sa operator==(const Node& n)
     71      ///
    5172      bool operator!=(GraphItem) const { return false; }
    5273
    5374      // Technical requirement. Do we really need this?
    54       bool operator<(GraphItem) const { return false; }
    55     };
    56 
    57 
    58     template<typename GI>
    59     struct GraphItemConcept {
    60       void constraints() {
    61         GI i1;
    62         GI i2 = i1;
    63         GI i3 = INVALID;
    64        
    65         i1 = i2 = i3;
    66 
    67         bool b;
    68         b = (ia == ib) && (ia != ib) && (ia < ib);
    69         b = (ia == INVALID) && (ib != INVALID);
    70       }
    71 
    72       const GI &ia;
    73       const GI &ib;
    74     };
    75 
    76 
    77     template<typename Iter, typename Graph, typename BaseItem>
    78     struct GraphIteratorConcept {
    79       void constraints() {
    80         function_requires< GraphItemConcept<Iter> >();
    81         Iter it1(g);
    82 
    83         /// \todo Do we need NodeIt(Node) kind of constructor?
    84         //      Iter it2(bj);
    85         Iter it2;
    86 
    87         it2 = ++it1;
    88         ++it2 = it1;
    89         ++(++it1);
    90         /// \bug This should be: is_base_and_derived<BaseItem, Iter>
    91         BaseItem bi = it1;
    92         bi = it2;
    93       }
    94 
    95       BaseItem bj;
    96       Graph g;
    97     };
    98 
    99     template<typename Iter, typename Graph>
    100     struct GraphIncIteratorConcept {
    101       typedef typename Graph::Node Node;
    102       typedef typename Graph::Edge Edge;
    103       void constraints() {
    104         function_requires< GraphItemConcept<Iter> >();
    105         Iter it1(graph, node);
    106         /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
    107         //      Iter it2(edge);
    108         Iter it2;
    109 
    110         it2 = ++it1;
    111         ++it2 = it1;
    112         ++(++it1);
    113         Edge e = it1;
    114         e = it2;
    115       }
    116 
    117       Edge edge;
    118       Node node;
    119       Graph graph;
    120     };
    121 
    122 
     75      //      bool operator<(GraphItem) const { return false; }
     76
     77
     78      template<typename _GraphItem>
     79      struct Constraints {
     80        void constraints() {
     81          _GraphItem i1;
     82          _GraphItem i2 = i1;
     83          _GraphItem i3 = INVALID;
     84         
     85          i1 = i2 = i3;
     86
     87          bool b;
     88          //      b = (ia == ib) && (ia != ib) && (ia < ib);
     89          b = (ia == ib) && (ia != ib);
     90          b = (ia == INVALID) && (ib != INVALID);
     91        }
     92
     93        const _GraphItem &ia;
     94        const _GraphItem &ib;
     95      };
     96    };
    12397
    12498    /// An empty base graph class.
     
    140114      /// This class represents the Nodes of the graph.
    141115      ///
    142       class Node {
    143       public:
    144 
    145         /// Default constructor.
    146 
    147         /// @warning The default constructor sets the iterator
    148         /// to an undefined value.
    149 
    150         Node() {}
    151         /// Copy constructor.
    152 
    153         /// Copy constructor.
    154         ///
    155         Node(const Node&) {}
    156 
    157         /// Invalid constructor \& conversion.
    158 
    159         /// This constructor initializes the iterator to be invalid.
    160         /// \sa Invalid for more details.
    161         Node(Invalid) {}
    162 
    163 
    164         /// Assign operator for nodes.
    165 
    166         /// The nodes are assignable.
    167         ///
    168         Node& operator=(const Node&) { return *this;}
    169 
    170         /// Equality operator.
    171 
    172         /// Two iterators are equal if and only if they represents the
    173         /// same node in the graph or both are invalid.
    174         bool operator==(const Node&) const { return true;}
    175 
    176 
    177         /// Inequality operator.
    178        
    179         /// \sa operator==(const Node& n)
    180         ///
    181         bool operator!=(const Node&) const { return true;}
    182 
    183         /// Comparison operator.
    184 
    185         /// This is a strict ordering between the nodes.
    186         ///
    187         /// This ordering can be different from the iterating order of nodes.
    188         /// \todo Possibly we don't need it.
    189         bool operator<(const Node&) const { return true;}
    190       };
     116      typedef GraphItem<'n'> Node;
    191117
    192118      /// Edge class of the graph.
     
    194120      /// This class represents the Edges of the graph.
    195121      ///
    196       class Edge {
    197       public:
    198 
    199         /// Default constructor.
    200 
    201         /// @warning The default constructor sets the iterator
    202         /// to an undefined value.
    203 
    204         Edge() {}
    205         /// Copy constructor.
    206 
    207         /// Copy constructor.
    208         ///
    209         Edge(const Edge&) {}
    210 
    211         /// Invalid constructor \& conversion.
    212 
    213         /// This constructor initializes the iterator to be invalid.
    214         /// \sa Invalid for more details.
    215         Edge(Invalid) {}
    216 
    217         /// Assign operator for edges.
    218 
    219         /// The edges are assignable.
    220         ///
    221         Edge& operator=(const Edge&) { return *this;}
    222 
    223         /// Equality operator.
    224 
    225         /// Two iterators are equal if and only if they represents the
    226         /// same edge in the graph or both are invalid.
    227         bool operator==(const Edge&) const { return true;}
    228 
    229 
    230         /// Inequality operator.
    231        
    232         /// \sa operator==(const Edge& n)
    233         ///
    234         bool operator!=(const Edge&) const { return true;}
    235 
    236         /// Comparison operator.
    237 
    238         /// This is a strict ordering between the edges.
    239         ///
    240         /// This ordering can be different from the iterating order of edges.
    241         /// \todo Possibly we don't need it.
    242         bool operator<(const Edge&) const { return true;}
    243       };
     122      typedef GraphItem<'e'> Edge;
    244123
    245124      ///Gives back the target node of an edge.
     
    254133      ///
    255134      Node source(const Edge&) const { return INVALID;}
    256     };
    257 
    258 
    259     /// Concept check structure for BaseGraph.
    260 
    261     /// Concept check structure for BaseGraph.
    262     ///
    263 
    264     template <typename Graph>
    265     struct BaseGraphComponentConcept {
    266       typedef typename Graph::Node Node;
    267       typedef typename Graph::Edge Edge;
    268      
    269       void constraints() {
    270         function_requires< GraphItemConcept<Node> >();
    271         function_requires< GraphItemConcept<Edge> >();
    272         {
    273           Node n;
    274           Edge e;
    275           n = graph.source(e);
    276           n = graph.target(e);
    277         }     
    278       }
    279      
    280       const Graph& graph;
     135
     136
     137      template <typename _Graph>
     138      struct Constraints {
     139        typedef typename _Graph::Node Node;
     140        typedef typename _Graph::Edge Edge;
     141     
     142        void constraints() {
     143          checkConcept<GraphItem<'n'>, Node>();
     144          checkConcept<GraphItem<'e'>, Edge>();
     145          {
     146            Node n;
     147            Edge e;
     148            n = graph.source(e);
     149            n = graph.target(e);
     150          }     
     151        }
     152     
     153        const _Graph& graph;
     154      };
    281155    };
    282156
     
    341215      ///     
    342216      void nextOut(Edge&) const {}
    343     };
    344 
    345 
    346     /// Concept check structure for IterableBaseGraph.
    347 
    348     /// Concept check structure for IterableBaseGraph.
    349     ///
    350     template <typename Graph>
    351     struct BaseIterableGraphComponentConcept {
    352      
    353       void constraints() {
    354         function_requires< BaseGraphComponentConcept<Graph> >();
    355         typename Graph::Node node;     
    356         typename Graph::Edge edge;
    357         {
    358           graph.first(node);
    359           graph.next(node);
    360         }
    361         {
    362           graph.first(edge);
    363           graph.next(edge);
    364         }
    365         {
    366           graph.firstIn(edge, node);
    367           graph.nextIn(edge);
    368         }
    369         {
    370           graph.firstOut(edge, node);
    371           graph.nextOut(edge);
    372         }
    373       }
    374 
    375       const Graph& graph;
     217
     218
     219      template <typename _Graph>
     220      struct Constraints {
     221     
     222        void constraints() {
     223          checkConcept< BaseGraphComponent, _Graph >();
     224          typename _Graph::Node node;     
     225          typename _Graph::Edge edge;
     226          {
     227            graph.first(node);
     228            graph.next(node);
     229          }
     230          {
     231            graph.first(edge);
     232            graph.next(edge);
     233          }
     234          {
     235            graph.firstIn(edge, node);
     236            graph.nextIn(edge);
     237          }
     238          {
     239            graph.firstOut(edge, node);
     240            graph.nextOut(edge);
     241          }
     242        }
     243
     244        const _Graph& graph;
     245      };
    376246    };
    377247
     
    382252    /// The most of the base graphs should be conform to this concept.
    383253    /// The id's are unique and immutable.
    384 
    385254    class IDableGraphComponent : virtual public BaseGraphComponent {
    386255    public:
     
    400269      ///
    401270      int id(const Edge&) const { return -1;}
    402     };
    403 
    404 
    405     /// Concept check structure for IdableBaseGraph.
    406 
    407     /// Concept check structure for IdableBaseGraph.
    408     ///
    409     template <typename Graph>
    410     struct IDableGraphComponentConcept {
    411 
    412       void constraints() {
    413         function_requires< BaseGraphComponentConcept<Graph> >();
    414         typename Graph::Node node;
    415         int nid = graph.id(node);
    416         nid = graph.id(node);
    417         typename Graph::Edge edge;
    418         int eid = graph.id(edge);
    419         eid = graph.id(edge);
    420       }
    421 
    422       const Graph& graph;
     271
     272      template <typename _Graph>
     273      struct Constraints {
     274
     275        void constraints() {
     276          checkConcept< BaseGraphComponent, _Graph >();
     277          typename _Graph::Node node;
     278          int nid = graph.id(node);
     279          nid = graph.id(node);
     280          typename _Graph::Edge edge;
     281          int eid = graph.id(edge);
     282          eid = graph.id(edge);
     283        }
     284
     285        const _Graph& graph;
     286      };
    423287    };
    424288
     
    444308      ///
    445309      int maxId(Edge = INVALID) const { return -1;}
    446     };
    447 
    448     /// Concept check structure for MaxIdableBaseGraph.
    449 
    450     /// Concept check structure for MaxIdableBaseGraph.
    451     ///
    452     template <typename Graph>
    453     struct MaxIDableGraphComponentConcept {
    454 
    455       void constraints() {
    456         function_requires< BaseGraphComponentConcept<Graph> >();
    457         int nid = graph.maxId(typename Graph::Node());
    458         ignore_unused_variable_warning(nid);
    459         int eid = graph.maxId(typename Graph::Edge());
    460         ignore_unused_variable_warning(eid);
    461       }
    462 
    463       const Graph& graph;
     310
     311      template <typename _Graph>
     312      struct Constraints {
     313
     314        void constraints() {
     315          checkConcept<BaseGraphComponent, _Graph>();
     316          int nid = graph.maxId(typename _Graph::Node());
     317          ignore_unused_variable_warning(nid);
     318          int eid = graph.maxId(typename _Graph::Edge());
     319          ignore_unused_variable_warning(eid);
     320        }
     321     
     322        const _Graph& graph;
     323      };
    464324    };
    465325
     
    491351      }
    492352
    493     };
    494 
    495     /// Concept check structure for ExtendableBaseGraph.
    496 
    497     /// Concept check structure for ExtendableBaseGraph.
    498     ///
    499     template <typename Graph>
    500     struct BaseExtendableGraphComponentConcept {
    501       void constraints() {
    502         function_requires< BaseGraphComponentConcept<Graph> >();
    503         typename Graph::Node node_a, node_b;
    504         node_a = graph.addNode();
    505         typename Graph::Edge edge;
    506         edge = graph.addEdge(node_a, node_b);
    507       }
    508 
    509       Graph& graph;
     353      template <typename _Graph>
     354      struct Constraints {
     355        void constraints() {
     356          checkConcept<BaseGraphComponent, _Graph >();
     357          typename _Graph::Node node_a, node_b;
     358          node_a = graph.addNode();
     359          typename _Graph::Edge edge;
     360          edge = graph.addEdge(node_a, node_b);
     361        }
     362
     363        _Graph& graph;
     364      };
    510365    };
    511366
     
    533388      void erase(const Edge&) {}
    534389
    535     };
    536 
    537     /// Concept check structure for ErasableBaseGraph.
    538 
    539     /// Concept check structure for ErasableBaseGraph.
    540     ///
    541     template <typename Graph>
    542     struct BaseErasableGraphComponentConcept {
    543       void constraints() {
    544         function_requires< BaseGraphComponentConcept<Graph> >();
    545         typename Graph::Node node;
    546         graph.erase(node);
    547         typename Graph::Edge edge;
    548         graph.erase(edge);
    549       }
    550 
    551       Graph& graph;
     390      template <typename _Graph>
     391      struct Constraints {
     392        void constraints() {
     393          checkConcept<BaseGraphComponent, _Graph>();
     394          typename _Graph::Node node;
     395          graph.erase(node);
     396          typename _Graph::Edge edge;
     397          graph.erase(edge);
     398        }
     399
     400        _Graph& graph;
     401      };
    552402    };
    553403
     
    565415      ///
    566416      void clear() {}   
    567     };
    568 
    569     /// Concept check function for ErasableBaseGraph.
    570 
    571     /// Concept check function for ErasableBaseGraph.
     417
     418      template <typename _Graph>
     419      struct Constraints {
     420        void constraints() {
     421          checkConcept< BaseGraphComponent, _Graph>();
     422          graph.clear();
     423        }
     424
     425        _Graph& graph;
     426      };
     427    };
     428
     429
     430    /// Skeleton class for graph NodeIt and EdgeIt
     431
     432    /// Skeleton class for graph NodeIt and EdgeIt.
    572433    ///
    573     template <typename Graph>
    574     struct BaseClearableGraphComponentConcept {
    575       void constraints() {
    576         function_requires< BaseGraphComponentConcept<Graph> >();
    577         graph.clear();
    578       }
    579 
    580       Graph& graph;
    581     };
    582 
    583 
    584     class IterableGraphComponent :
    585       virtual public BaseIterableGraphComponent {
     434    template <typename _Graph, typename _Item>
     435    class GraphIterator : public _Item {
     436    public:
     437      /// \todo Don't we need the Item type as typedef?
     438
     439      /// Default constructor.
     440     
     441      /// @warning The default constructor sets the iterator
     442      /// to an undefined value.
     443      GraphIterator() {}
     444      /// Copy constructor.
     445     
     446      /// Copy constructor.
     447      ///
     448      GraphIterator(GraphIterator const&) {}
     449      /// Sets the iterator to the first item.
     450     
     451      /// Sets the iterator to the first item of \c the graph.
     452      ///
     453      explicit GraphIterator(const _Graph&) {}
     454      /// Invalid constructor \& conversion.
     455
     456      /// This constructor initializes the item to be invalid.
     457      /// \sa Invalid for more details.
     458      GraphIterator(Invalid) {}
     459      /// Assign operator for items.
     460
     461      /// The items are assignable.
     462      ///
     463      GraphIterator& operator=(GraphIterator const&) { return *this; }     
     464      /// Next item.
     465
     466      /// Assign the iterator to the next item.
     467      ///
     468      GraphIterator& operator++() { return *this; }
     469      //        Node operator*() const { return INVALID; }
     470      /// Equality operator
     471
     472      /// Two iterators are equal if and only if they point to the
     473      /// same object or both are invalid.
     474      bool operator==(const GraphIterator&) const { return true;}
     475      /// Inequality operator
     476       
     477      /// \sa operator==(Node n)
     478      ///
     479      bool operator!=(const GraphIterator&) const { return true;}
     480     
     481      template<typename _GraphIterator>
     482      struct Constraints {
     483        void constraints() {
     484          //      checkConcept< Item, _GraphIterator >();
     485          _GraphIterator it1(g);
     486       
     487          /// \todo Do we need NodeIt(Node) kind of constructor?
     488          //    _GraphIterator it2(bj);
     489          _GraphIterator it2;
     490
     491          it2 = ++it1;
     492          ++it2 = it1;
     493          ++(++it1);
     494          /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
     495          _Item bi = it1;
     496          bi = it2;
     497        }
     498        _Graph& g;
     499      };
     500    };
     501
     502    /// Skeleton class for graph InEdgeIt and OutEdgeIt
     503
     504    /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
     505    /// base class, the _selector is a additional template parameter. For
     506    /// InEdgeIt you should instantiate it with character 'i' and for
     507    /// OutEdgeIt with 'o'.
     508    /// \todo check the name of the concept GraphIncEdgeIterator
     509    template <typename _Graph, char _selector>
     510    class GraphIncEdgeIterator : public _Graph::Edge {
     511    public:
     512      /// Default constructor.
     513     
     514      /// @warning The default constructor sets the iterator
     515      /// to an undefined value.
     516      GraphIncEdgeIterator() {}
     517      /// Copy constructor.
     518     
     519      /// Copy constructor.
     520      ///
     521      GraphIncEdgeIterator(GraphIncEdgeIterator const&) {}
     522      /// Sets the iterator to the first edge incoming into or outgoing from the node.
     523     
     524      /// Sets the iterator to the first edge incoming into or outgoing from the node.
     525      ///
     526      explicit GraphIncEdgeIterator(const _Graph&, const typename _Graph::Node&) {}
     527      /// Invalid constructor \& conversion.
     528
     529      /// This constructor initializes the item to be invalid.
     530      /// \sa Invalid for more details.
     531      GraphIncEdgeIterator(Invalid) {}
     532      /// Assign operator for nodes.
     533
     534      /// The nodes are assignable.
     535      ///
     536      GraphIncEdgeIterator& operator=(GraphIncEdgeIterator const&) { return *this; }     
     537      /// Next edge.
     538
     539      /// Assign the iterator to the next node.
     540      ///
     541      GraphIncEdgeIterator& operator++() { return *this; }
     542      //        Node operator*() const { return INVALID; }
     543      /// Equality operator
     544
     545      /// Two iterators are equal if and only if they point to the
     546      /// same object or both are invalid.
     547      bool operator==(const GraphIncEdgeIterator&) const { return true;}
     548      /// Inequality operator
     549       
     550      /// \sa operator==(Node n)
     551      ///
     552      bool operator!=(const GraphIncEdgeIterator&) const { return true;}
     553
     554      template <typename _GraphIncEdgeIterator>
     555      struct Constraints {
     556        typedef typename _Graph::Node Node;
     557        typedef typename _Graph::Edge Edge;
     558        void constraints() {
     559          checkConcept<GraphItem<'e'>, _GraphIncEdgeIterator>();
     560          _GraphIncEdgeIterator it1(graph, node);
     561          /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
     562          //    _GraphIncEdgeIterator it2(edge);
     563          _GraphIncEdgeIterator it2;
     564
     565          it2 = ++it1;
     566          ++it2 = it1;
     567          ++(++it1);
     568          Edge e = it1;
     569          e = it2;
     570        }
     571
     572        Edge& edge;
     573        Node& node;
     574        _Graph& graph;
     575      };
     576    };
     577    /// An empty iterable base graph class.
     578 
     579    /// This class provides beside the core graph features
     580    /// iterator based iterable interface for the graph structure.
     581    /// This concept is part of the StaticGraphConcept.
     582    class IterableGraphComponent : virtual public BaseGraphComponent {
    586583
    587584    public:
     
    592589      typedef BaseGraphComponent::Edge Edge;
    593590
    594       class NodeIt : public Node {
    595       public:
    596         NodeIt() {}
    597         NodeIt(Invalid) {}
    598         // explicit NodeIt(Node) {}
    599         explicit NodeIt(const Graph&) {}
    600 
    601         NodeIt& operator++() { return *this; }
    602         //      Node operator*() const { return INVALID; }
    603 
    604         bool operator==(const NodeIt&) const { return true;}
    605         bool operator!=(const NodeIt&) const { return true;}
    606       };
    607 
    608       class EdgeIt : public Edge {
    609       public:
    610         EdgeIt() {}
    611         EdgeIt(Invalid) {}
    612         // explicit EdgeIt(Edge) {}
    613         explicit EdgeIt(const Graph&) {}
    614 
    615         EdgeIt& operator++() { return *this; }
    616         //      Edge operator*() const { return INVALID; }
    617 
    618         bool operator==(const EdgeIt&) const { return true;}
    619         bool operator!=(const EdgeIt&) const { return true;}
    620       };
    621 
    622       class InEdgeIt : public Edge {
    623       public:
    624         InEdgeIt() {}
    625         InEdgeIt(Invalid) {}
    626         // explicit InEdgeIt(Edge) {}
    627         explicit InEdgeIt(const Graph&, const Node&) {}
    628 
    629         InEdgeIt& operator++() { return *this; }
    630         //      Edge operator*() const { return INVALID; }
    631 
    632         bool operator==(const InEdgeIt&) const { return true;}
    633         bool operator!=(const InEdgeIt&) const { return true;}
    634       };
    635 
    636       class OutEdgeIt : public Edge {
    637       public:
    638         OutEdgeIt() {}
    639         OutEdgeIt(Invalid) {}
    640         // explicit OutEdgeIt(Edge) {}
    641         explicit OutEdgeIt(const Graph&, const Node&) {}
    642 
    643         OutEdgeIt& operator++() { return *this; }
    644         //      Edge operator*() const { return INVALID; }
    645 
    646         bool operator==(const OutEdgeIt&) const { return true;}
    647         bool operator!=(const OutEdgeIt&) const { return true;}
    648       };
    649 
     591      /// This iterator goes through each node.
     592
     593      /// This iterator goes through each node.
     594      ///
     595      typedef GraphIterator<Graph, Node> NodeIt;
     596      /// This iterator goes through each node.
     597
     598      /// This iterator goes through each node.
     599      ///
     600      typedef GraphIterator<Graph, Edge> EdgeIt;
     601      /// This iterator goes trough the incoming edges of a node.
     602
     603      /// This iterator goes trough the \e inccoming edges of a certain node
     604      /// of a graph.
     605      typedef GraphIncEdgeIterator<Graph, 'i'> InEdgeIt;
     606      /// This iterator goes trough the outgoing edges of a node.
     607
     608      /// This iterator goes trough the \e outgoing edges of a certain node
     609      /// of a graph.
     610      typedef GraphIncEdgeIterator<Graph, 'o'> OutEdgeIt;
    650611    };
    651612   
    652     template <typename Graph>
    653     struct IterableGraphComponentConcept {
     613    template <typename _Graph>
     614    struct Constraints {
    654615      void constraints() {
    655         function_requires< BaseIterableGraphComponentConcept<Graph> >();
    656 
    657         typedef typename Graph::Node Node;
    658         typedef typename Graph::NodeIt NodeIt;
    659         typedef typename Graph::Edge Edge;
    660         typedef typename Graph::EdgeIt EdgeIt;
    661         typedef typename Graph::InEdgeIt InEdgeIt;
    662         typedef typename Graph::OutEdgeIt OutEdgeIt;
     616        checkConcept< BaseGraphComponent, _Graph>();
     617
     618        checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
     619        checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
     620        checkConcept<GraphIncEdgeIterator<_Graph, 'i'>, typename _Graph::InEdgeIt >();
     621        checkConcept<GraphIncEdgeIterator<_Graph, 'o'>, typename _Graph::OutEdgeIt >();
     622      }
     623    };
     624
     625
     626    template <typename Graph, typename Item, typename _Value>
     627    class GraphMap : public ReadWriteMap<Item, _Value> {
     628    protected:     
     629      GraphMap() {}
     630    public:
     631      explicit GraphMap(const Graph&) {}
     632      GraphMap(const Graph&, const _Value&) {}
     633      GraphMap(const GraphMap&) {}
     634     
     635      GraphMap& operator=(const GraphMap&) { return *this;}
     636
     637      template<typename _Map>
     638      struct Constraints {
     639        void constraints() {
     640          checkConcept<ReadWriteMap<Item, _Value>, _Map >();
     641          // Construction with a graph parameter
     642          _Map a(g);
     643          // Constructor with a graph and a default value parameter
     644          _Map a2(g,t);
     645          // Copy constructor. Do we need it?
     646          _Map b=c;
     647          // Copy operator. Do we need it?
     648          a=b;
     649
     650          ignore_unused_variable_warning(a2);
     651        }
     652
     653        const _Map &c;
     654        const Graph &g;
     655        const typename GraphMap::Value &t;
     656      };
     657
     658    };
     659
     660    /// An empty mappable base graph class.
    663661 
    664         function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
    665         function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
    666         function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
    667         function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
    668       }
    669     };
    670 
    671 
     662    /// This class provides beside the core graph features
     663    /// map interface for the graph structure.
     664    /// This concept is part of the StaticGraphConcept.
    672665    class MappableGraphComponent : virtual public BaseGraphComponent {
    673666    public:
     
    678671      typedef BaseGraphComponent::Edge Edge;
    679672
     673      /// ReadWrite map of the nodes.
     674   
     675      /// ReadWrite map of the nodes.
     676      ///
    680677      template <typename _Value>
    681       class NodeMap : public ReferenceMap<Node, _Value> {
     678      class NodeMap : public GraphMap<Graph, Node, _Value> {
     679      private:
     680        NodeMap();
    682681      public:
    683         NodeMap(const Graph&) {}
     682        // \todo call the right parent class constructor
     683        explicit NodeMap(const Graph&) {}
    684684        NodeMap(const Graph&, const _Value&) {}
    685685        NodeMap(const NodeMap&) {}
    686686
    687687        NodeMap& operator=(const NodeMap&) { return *this;}
    688        
    689       };
    690 
     688
     689      };
     690
     691      /// ReadWrite map of the edges.
     692   
     693      /// ReadWrite map of the edges.
     694      ///
    691695      template <typename _Value>
    692       class EdgeMap : public ReferenceMap<Edge, _Value> {
     696      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
     697      private:
     698        EdgeMap();
    693699      public:
    694         EdgeMap(const Graph&) {}
     700        // \todo call the right parent class constructor
     701        explicit EdgeMap(const Graph&) {}
    695702        EdgeMap(const Graph&, const _Value&) {}
    696703        EdgeMap(const EdgeMap&) {}
    697704
    698705        EdgeMap& operator=(const EdgeMap&) { return *this;}
    699        
    700       };
    701 
    702     };
    703 
    704     template <typename Graph>
    705     struct MappableGraphComponentConcept {
    706 
    707       struct Type {
    708         int value;
    709         Type() : value(0) {}
    710         Type(int _v) : value(_v) {}
    711       };
    712 
    713       void constraints() {
    714         function_requires< BaseGraphComponentConcept<Graph> >();
    715         { // int map test
    716           typedef typename Graph::template NodeMap<int> IntNodeMap;
    717           function_requires<GraphMapConcept<IntNodeMap,Graph> >();
    718         } { // bool map test
    719           typedef typename Graph::template NodeMap<bool> BoolNodeMap;
    720           function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
    721         } { // Type map test
    722           typedef typename Graph::template NodeMap<Type> TypeNodeMap;
    723           function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
    724         }
    725 
    726         { // int map test
    727           typedef typename Graph::template EdgeMap<int> IntEdgeMap;
    728           function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
    729         } { // bool map test
    730           typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
    731           function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
    732         } { // Type map test
    733           typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
    734           function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
    735         }
    736       }
    737 
    738       Graph& graph;
     706
     707      };
     708
     709      template <typename _Graph>
     710      struct Constraints {
     711
     712        struct Type {
     713          int value;
     714          Type() : value(0) {}
     715          Type(int _v) : value(_v) {}
     716        };
     717
     718        void constraints() {
     719          checkConcept<BaseGraphComponent, _Graph>();
     720          { // int map test
     721            typedef typename _Graph::template NodeMap<int> IntNodeMap;
     722            checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, IntNodeMap >();
     723          } { // bool map test
     724            typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
     725            checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>, BoolNodeMap >();
     726          } { // Type map test
     727            typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
     728            checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>, TypeNodeMap >();
     729          }
     730
     731          { // int map test
     732            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
     733            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, IntEdgeMap >();
     734          } { // bool map test
     735            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
     736            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, BoolEdgeMap >();
     737          } { // Type map test
     738            typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
     739            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, TypeEdgeMap >();
     740          }
     741        }
     742
     743        _Graph& graph;
     744      };
    739745    };
    740746
     
    756762      }
    757763
    758     };
    759 
    760     template <typename Graph>
    761     struct ExtendableGraphComponentConcept {
    762       void constraints() {
    763         function_requires< BaseGraphComponentConcept<Graph> >();
    764         typename Graph::Node node_a, node_b;
    765         node_a = graph.addNode();
    766         typename Graph::Edge edge;
    767         edge = graph.addEdge(node_a, node_b);     
    768       }
    769       Graph& graph;
    770     };
    771 
     764      template <typename _Graph>
     765      struct Constraints {
     766        void constraints() {
     767          checkConcept<BaseGraphComponent, _Graph >();
     768          typename _Graph::Node node_a, node_b;
     769          node_a = graph.addNode();
     770          typename _Graph::Edge edge;
     771          edge = graph.addEdge(node_a, node_b);     
     772        }
     773        _Graph& graph;
     774      };
     775    };
    772776    class ErasableGraphComponent : virtual public BaseGraphComponent {
    773777    public:
     
    781785      void erase(const Edge&) {}
    782786
    783     };
    784 
    785     template <typename Graph>
    786     struct ErasableGraphComponentConcept {
    787       void constraints() {
    788         function_requires< BaseGraphComponentConcept<Graph> >();
    789         typename Graph::Node node;
    790         graph.erase(node);
    791         typename Graph::Edge edge;
    792         graph.erase(edge);     
    793       }
    794 
    795       Graph& graph;
     787      template <typename _Graph>
     788      struct Constraints {
     789        void constraints() {
     790          checkConcept<BaseGraphComponent, _Graph >();
     791          typename _Graph::Node node;
     792          graph.erase(node);
     793          typename _Graph::Edge edge;
     794          graph.erase(edge);     
     795        }
     796
     797        _Graph& graph;
     798      };
    796799    };
    797800
     
    806809      void clear() {}   
    807810
    808     };
    809 
    810     template <typename Graph>
    811     struct ClearableGraphComponentConcept {
    812       void constraints() {
    813         function_requires< BaseGraphComponentConcept<Graph> >();
    814         graph.clear();
    815       }
    816       Graph& graph;
     811
     812      template <typename _Graph>
     813      struct ClearableGraphComponentConcept {
     814        void constraints() {
     815          checkConcept< BaseGraphComponent, _Graph >();
     816          graph.clear();
     817        }
     818        _Graph& graph;
     819      };
    817820    };
    818821
  • src/lemon/concept/maps.h

    r987 r989  
    4141      typedef T Value;
    4242
     43      // \bug Value don't need to be default constructible.
    4344      /// Returns the value associated with a key.
    44       Value operator[](const Key &k) const {return Value();}
     45      Value operator[](const Key &) const {return Value();}
    4546
    46       ///Default constructor
    47       ReadMap() {}
     47      template<typename _ReadMap>
     48      struct Constraints {
     49
     50        void constraints() {
     51          Value val = m[key];
     52          val = m[key];
     53          typename _ReadMap::Value own_val = m[own_key];
     54          own_val = m[own_key];
     55
     56          ignore_unused_variable_warning(val);
     57          ignore_unused_variable_warning(own_val);
     58          ignore_unused_variable_warning(key);
     59        }
     60        Key& key;
     61        typename _ReadMap::Key& own_key;
     62        _ReadMap& m;
     63      };
     64     
    4865    };
    4966
     
    6481      ///Default constructor
    6582      WriteMap() {}
     83
     84      template <typename _WriteMap>
     85      struct Constraints {
     86        void constraints() {
     87          // No constraints for constructor.
     88          m.set(key, val);
     89          m.set(own_key, own_val);
     90          ignore_unused_variable(key);
     91          ignore_unused_variable(val);
     92          ignore_unused_variable(own_key);
     93          ignore_unused_variable(own_val);
     94        }
     95
     96        Value& val;
     97        typename _WriteMap::Value own_val;
     98        Key& key;
     99        typename _WriteMap::Key& own_key;
     100        WriteMap& m;
     101
     102      };
    66103    };
    67104
     
    82119      void set(const Key &k,const Value &t) {}
    83120
    84       ///Default constructor
    85       ReadWriteMap() {}
     121      template<typename _ReadWriteMap>
     122      struct Constraints {
     123        void constraints() {
     124          checkConcept<ReadMap<K, T>, _ReadWriteMap >();
     125          checkConcept<ReadMap<K, T>, _ReadWriteMap >();
     126        }
     127      };
    86128    };
    87129 
    88130 
    89131    ///Dereferable map concept
    90     template<typename K, typename T>
     132    template<typename K, typename T, typename R, typename CR>
    91133    class ReferenceMap : public ReadWriteMap<K,T>
    92134    {
     
    96138      /// Map's value type. (The type of objects associated with the keys).
    97139      typedef T Value;
     140      /// Map's reference type.
     141      typedef R Reference;
     142      /// Map's const reference type.
     143      typedef CR ConstReference;
    98144
    99145    protected:
    100146      Value tmp;
    101147    public:
    102       typedef Value& Reference;
    103       /// Map's const reference type.
    104       typedef const Value& ConstReference;
    105148
    106149      ///Returns a reference to the value associated to a key.
     
    112155      void set(const Key &k,const Value &t) { operator[](k)=t; }
    113156
    114       ///Default constructor
    115       ReferenceMap() {}
     157      // \todo rethink this concept
     158      template<typename _ReferenceMap>
     159      struct ReferenceMapConcept {
     160
     161        void constraints() {
     162          checkConcept<ReadWriteMap, _ReferenceMap >();
     163          m[key] = val;
     164          val  = m[key];
     165          m[key] = ref;
     166          ref = m[key];
     167          m[own_key] = own_val;
     168          own_val  = m[own_key];
     169          m[own_key] = own_ref;
     170          own_ref = m[own_key];           
     171        }
     172
     173        typename _ReferenceMap::Key& own_key;
     174        typename _ReferenceMap::Value& own_val;
     175        typename _ReferenceMap::Reference& own_ref;
     176        Key& key;
     177        Value& val;
     178        Reference& ref;
     179        ReferenceMap& m;
     180      };
    116181    };
    117 
    118 
    119     template<typename Item, typename T, typename Graph>
    120     class GraphMap : public ReadWriteMap<Item, T> {
    121       // I really, really don't like the idea that every graph should have
    122       // reference maps! --klao
    123 
    124     private:
    125       // We state explicitly that graph maps have no default constructor?
    126       GraphMap();
    127 
    128     public:
    129       explicit GraphMap(Graph const&) {}
    130       // value for initializing
    131       GraphMap(Graph const&, T) {}
    132 
    133       // this probably should be required:
    134       GraphMap(GraphMap const&) {}
    135       GraphMap& operator=(GraphMap const&) { return *this; }
    136 
    137       // but this is a absolute no-op! We should provide a more generic
    138       // graph-map-copy operation.
    139       //
    140       // template<typename TT>
    141       // GraphMap(GraphMap<TT> const&);
    142       //
    143       // template<typename TT>
    144       // GraphMap& operator=(const GraphMap<TT>&);
    145     };
    146 
    147 
    148     /****************  Concept-checking classes  ****************/
    149 
    150     template<typename ReadMap>
    151     struct ReadMapConcept {
    152       typedef typename ReadMap::Key Key;
    153       typedef typename ReadMap::Value Value;
    154 
    155       void constraints() {
    156         // No constraints for constructor.
    157 
    158         // What are the requirement for the Value?
    159         // CopyConstructible? Assignable? None of these?
    160         Value v = m[k];
    161         v = m[k];
    162 
    163         // FIXME:
    164         ignore_unused_variable_warning(v);
    165       }
    166 
    167       ReadMap m;
    168       Key k;
    169     };
    170 
    171     template<typename WriteMap>
    172     struct WriteMapConcept {
    173       typedef typename WriteMap::Key Key;
    174       typedef typename WriteMap::Value Value;
    175 
    176       void constraints() {
    177         // No constraints for constructor.
    178 
    179         m.set(k, v);
    180       }
    181 
    182       WriteMap m;
    183       Key k;
    184       Value v;
    185     };
    186 
    187     template<typename ReadWriteMap>
    188     struct ReadWriteMapConcept {
    189       void constraints() {
    190         function_requires< ReadMapConcept<ReadWriteMap> >();
    191         function_requires< WriteMapConcept<ReadWriteMap> >();
    192       }
    193     };
    194 
    195     template<typename ReferenceMap>
    196     struct ReferenceMapConcept {
    197       typedef typename ReferenceMap::Key Key;
    198       typedef typename ReferenceMap::Value Value;
    199       typedef typename ReferenceMap::Reference Reference;
    200 
    201       // What for is this?
    202       typedef typename ReferenceMap::ConstReference ConstReference;
    203 
    204       void constraints() {
    205         function_requires< ReadWriteMapConcept<ReferenceMap> >();
    206 
    207         m[k] = v;
    208         // Or should we require real reference?
    209         // Like this:
    210         // Value &vv = m[k];
    211         // ignore_unused_variable_warning(vv);
    212       }
    213 
    214       ReferenceMap m;
    215       Key k;
    216       Value v;
    217     };
    218 
    219     /// \todo GraphMapConceptCheck
    220 
    221     template<typename GraphMap, typename Graph>
    222     struct GraphMapConcept {
    223       void constraints() {
    224         function_requires< ReadWriteMapConcept<GraphMap> >();
    225         // Construction with a graph parameter
    226         GraphMap a(g);
    227         // Ctor with a graph and a default value parameter
    228         GraphMap a2(g,t);
    229         // Copy ctor. Do we need it?
    230         GraphMap b=c;
    231         // Copy operator. Do we need it?
    232         a=b;
    233 
    234         ignore_unused_variable_warning(a2);
    235       }
    236       const GraphMap &c;
    237       const Graph &g;
    238       const typename GraphMap::Value &t;
    239     };
    240    
    241182
    242183    // @}
  • src/lemon/concept/undir_graph.h

    r986 r989  
    3939      typedef typename Graph::Edge Edge;
    4040      typedef typename Graph::Node Node;
     41
    4142      void constraints() {
    42         function_requires< BaseIterableGraphComponentConcept<Graph> >();
    43         function_requires< GraphItemConcept<UndirEdge> >();
     43        checkConcept<BaseIterableGraphComponent, Graph>();
     44        checkConcept<GraphItem<'u'>, UndirEdge >();
    4445
    4546        /// \bug this should be base_and_derived:
     
    6162    struct IterableUndirGraphConcept {
    6263      void constraints() {
    63         function_requires< BaseIterableUndirGraphConcept<Graph> > ();
    64         function_requires< IterableGraphComponentConcept<Graph> > ();
     64        /// \todo we don't need the iterable component should base iterable     
     65        //      checkConcept< BaseIterableUndirGraph, Graph > ();
     66        checkConcept< IterableGraphComponent, Graph > ();
    6567
    6668        typedef typename Graph::UndirEdge UndirEdge;
    6769        typedef typename Graph::UndirEdgeIt UndirEdgeIt;
    6870
    69         function_requires<
    70           GraphIteratorConcept<UndirEdgeIt, Graph, UndirEdge> >();
     71        checkConcept< GraphIterator<Graph, UndirEdge>, UndirEdgeIt >();
    7172      }
    7273    };
  • src/lemon/concept_check.h

    r986 r989  
    4040  }
    4141
     42  template <typename Concept, typename Type>
     43  inline void checkConcept() {
     44    function_requires<typename Concept::template Constraints<Type> >();
     45  }
     46
    4247#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
    4348  typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
Note: See TracChangeset for help on using the changeset viewer.