COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
11/13/04 22:37:54 (15 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?>;

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.