Changeset 989:ca95f8b5c931 in lemon-0.x for src
- Timestamp:
- 11/13/04 22:37:54 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1379
- Location:
- src
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/concept/graph.h
r987 r989 102 102 // bool operator!=(Node) const { return true; } 103 103 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 NodeIt109 // ///goes through the nodes.110 // ///\todo Possibly we don't need it.111 // bool operator<(Node) const { return true; }112 104 // }; 113 105 … … 189 181 // /// 190 182 // 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 NodeIt196 // ///goes through the nodes.197 // ///\todo Possibly we don't need it.198 // bool operator<(Edge) const { return true; }199 183 // }; 200 184 … … 340 324 // EdgeIt& operator++() { return *this; } 341 325 // }; 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 366 326 // ///Gives back the target node of an edge. 367 327 … … 374 334 // /// 375 335 // 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. 403 337 404 338 // /// \ingroup concept 405 // /// Reference map of the nodes to type \c T.339 // /// ReadWrite map of the nodes to type \c T. 406 340 // /// \sa Reference 407 341 // /// \warning Making maps that can handle bool type (NodeMap<bool>) 408 342 // /// 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 > 410 345 // { 411 346 // public: … … 417 352 418 353 // ///Copy constructor 419 // template<typename TT> NodeMap(const NodeMap<TT>&) { }354 // NodeMap(const NodeMap&) { } 420 355 // ///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. 426 361 427 362 // /// \ingroup concept … … 430 365 // /// \warning Making maps that can handle bool type (EdgeMap<bool>) 431 366 // /// needs some extra attention! 432 // template<class T> class EdgeMap433 // : public ReferenceMap<Edge,T>367 // template<class T> 368 // class EdgeMap : public ReadWriteMap<Edge,T> 434 369 // { 435 370 // public: … … 439 374 // ///\e 440 375 // EdgeMap(const StaticGraph&, T) { } 441 442 376 // ///Copy constructor 443 // template<typename TT> EdgeMap(const EdgeMap<TT>&) { }377 // EdgeMap(const EdgeMap&) { } 444 378 // ///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 447 381 // }; 448 382 // }; 449 383 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 the458 // ///\ref lemon::concept::StaticGraph "StaticGraph" concept459 // 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 conversion486 // 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 conversion506 // 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 conversion520 // 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 conversion534 // 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 tests545 // { Node n; int i=G.id(n); i=i; }546 // { Edge e; int i=G.id(e); i=i; }547 // //NodeMap tests548 // {549 // Node k;550 // typename Graph::template NodeMap<int> m(G);551 // //Const map552 // typename Graph::template NodeMap<int> const &cm = m;553 // //Inicialize with default value554 // typename Graph::template NodeMap<int> mdef(G,12);555 // //Copy556 // typename Graph::template NodeMap<int> mm(cm);557 // //Copy from another type558 // typename Graph::template NodeMap<double> dm(cm);559 // //Copy to more complex type560 // 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 type567 // em=cm; //Copy to more complex type568 // {569 // //Check the typedef's570 // 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 NodeMap577 // Node k;578 // typename Graph::template NodeMap<bool> m(G);579 // typename Graph::template NodeMap<bool> const &cm = m; //Const map580 // //Inicialize with default value581 // typename Graph::template NodeMap<bool> mdef(G,12);582 // typename Graph::template NodeMap<bool> mm(cm); //Copy583 // typename Graph::template NodeMap<int> dm(cm); //Copy from another type584 // 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 type590 // m=dm; //Copy to another type591 592 // {593 // //Check the typedef's594 // 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 tests601 // {602 // Edge k;603 // typename Graph::template EdgeMap<int> m(G);604 // typename Graph::template EdgeMap<int> const &cm = m; //Const map605 // //Inicialize with default value606 // typename Graph::template EdgeMap<int> mdef(G,12);607 // typename Graph::template EdgeMap<int> mm(cm); //Copy608 // typename Graph::template EdgeMap<double> dm(cm);//Copy from another type609 // 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 type615 // {616 // //Check the typedef's617 // 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 EdgeMap624 // Edge k;625 // typename Graph::template EdgeMap<bool> m(G);626 // typename Graph::template EdgeMap<bool> const &cm = m; //Const map627 // //Inicialize with default value628 // typename Graph::template EdgeMap<bool> mdef(G,12);629 // typename Graph::template EdgeMap<bool> mm(cm); //Copy630 // typename Graph::template EdgeMap<int> dm(cm); //Copy from another type631 // 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 type637 // m=dm; //Copy to another type638 // {639 // //Check the typedef's640 // 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 648 384 // /// An empty non-static graph class. 649 385 … … 666 402 // ///Add a new edge to the graph. 667 403 668 // ///Add a new edge to the graph with source node \c t669 // ///and target node \c h.404 // ///Add a new edge to the graph with source node \c s 405 // ///and target node \c t. 670 406 // ///\return the new edge. 671 // Edge addEdge(Node h, Node t) { return INVALID; }407 // Edge addEdge(Node s, Node t) { return INVALID; } 672 408 673 409 // /// Resets the graph. … … 678 414 // void clear() { } 679 415 // }; 680 681 682 // ///\brief Checks whether \c G meets the683 // ///\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept684 // 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 704 416 705 417 // /// An empty erasable graph class. … … 726 438 // void erase(Edge e) { } 727 439 // }; 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 765 442 /************* New GraphBase stuff **************/ 766 443 … … 816 493 817 494 template<typename T> 818 class NodeMap : public GraphMap< Node, T, GraphBase> {};495 class NodeMap : public GraphMap<GraphBase, Node, T> {}; 819 496 820 497 template<typename T> 821 class EdgeMap : public GraphMap< Edge, T, GraphBase> {};498 class EdgeMap : public GraphMap<GraphBase, Node, T> {}; 822 499 }; 823 500 … … 834 511 typedef BaseGraphComponent::Node Node; 835 512 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 }; 844 521 }; 845 522 … … 850 527 typedef BaseGraphComponent::Node Node; 851 528 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 }; 861 538 }; 862 539 … … 867 544 typedef BaseGraphComponent::Node Node; 868 545 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 }; 877 554 }; 878 555 -
src/lemon/concept/graph_component.h
r987 r989 38 38 /// with character 'n' and for Edge with 'e'. 39 39 40 template<char Ch>40 template<char _selector> 41 41 class GraphItem { 42 42 public: 43 /// Default constructor. 44 45 /// @warning The default constructor sets the item 46 /// to an undefined value. 43 47 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. 44 57 GraphItem(Invalid) {} 45 46 // We explicitely list these: 47 GraphItem(GraphItem const&) {} 58 /// Assign operator for nodes. 59 60 /// The nodes are assignable. 61 /// 48 62 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. 50 67 bool operator==(GraphItem) const { return false; } 68 /// Inequality operator. 69 70 /// \sa operator==(const Node& n) 71 /// 51 72 bool operator!=(GraphItem) const { return false; } 52 73 53 74 // 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 }; 123 97 124 98 /// An empty base graph class. … … 140 114 /// This class represents the Nodes of the graph. 141 115 /// 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; 191 117 192 118 /// Edge class of the graph. … … 194 120 /// This class represents the Edges of the graph. 195 121 /// 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; 244 123 245 124 ///Gives back the target node of an edge. … … 254 133 /// 255 134 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 }; 281 155 }; 282 156 … … 341 215 /// 342 216 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 }; 376 246 }; 377 247 … … 382 252 /// The most of the base graphs should be conform to this concept. 383 253 /// The id's are unique and immutable. 384 385 254 class IDableGraphComponent : virtual public BaseGraphComponent { 386 255 public: … … 400 269 /// 401 270 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 }; 423 287 }; 424 288 … … 444 308 /// 445 309 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 }; 464 324 }; 465 325 … … 491 351 } 492 352 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 }; 510 365 }; 511 366 … … 533 388 void erase(const Edge&) {} 534 389 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 }; 552 402 }; 553 403 … … 565 415 /// 566 416 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. 572 433 /// 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 { 586 583 587 584 public: … … 592 589 typedef BaseGraphComponent::Edge Edge; 593 590 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; 650 611 }; 651 612 652 template <typename Graph>653 struct IterableGraphComponentConcept{613 template <typename _Graph> 614 struct Constraints { 654 615 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. 663 661 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. 672 665 class MappableGraphComponent : virtual public BaseGraphComponent { 673 666 public: … … 678 671 typedef BaseGraphComponent::Edge Edge; 679 672 673 /// ReadWrite map of the nodes. 674 675 /// ReadWrite map of the nodes. 676 /// 680 677 template <typename _Value> 681 class NodeMap : public ReferenceMap<Node, _Value> { 678 class NodeMap : public GraphMap<Graph, Node, _Value> { 679 private: 680 NodeMap(); 682 681 public: 683 NodeMap(const Graph&) {} 682 // \todo call the right parent class constructor 683 explicit NodeMap(const Graph&) {} 684 684 NodeMap(const Graph&, const _Value&) {} 685 685 NodeMap(const NodeMap&) {} 686 686 687 687 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 /// 691 695 template <typename _Value> 692 class EdgeMap : public ReferenceMap<Edge, _Value> { 696 class EdgeMap : public GraphMap<Graph, Edge, _Value> { 697 private: 698 EdgeMap(); 693 699 public: 694 EdgeMap(const Graph&) {} 700 // \todo call the right parent class constructor 701 explicit EdgeMap(const Graph&) {} 695 702 EdgeMap(const Graph&, const _Value&) {} 696 703 EdgeMap(const EdgeMap&) {} 697 704 698 705 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 }; 739 745 }; 740 746 … … 756 762 } 757 763 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 }; 772 776 class ErasableGraphComponent : virtual public BaseGraphComponent { 773 777 public: … … 781 785 void erase(const Edge&) {} 782 786 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 }; 796 799 }; 797 800 … … 806 809 void clear() {} 807 810 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 }; 817 820 }; 818 821 -
src/lemon/concept/maps.h
r987 r989 41 41 typedef T Value; 42 42 43 // \bug Value don't need to be default constructible. 43 44 /// Returns the value associated with a key. 44 Value operator[](const Key & k) const {return Value();}45 Value operator[](const Key &) const {return Value();} 45 46 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 48 65 }; 49 66 … … 64 81 ///Default constructor 65 82 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 }; 66 103 }; 67 104 … … 82 119 void set(const Key &k,const Value &t) {} 83 120 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 }; 86 128 }; 87 129 88 130 89 131 ///Dereferable map concept 90 template<typename K, typename T >132 template<typename K, typename T, typename R, typename CR> 91 133 class ReferenceMap : public ReadWriteMap<K,T> 92 134 { … … 96 138 /// Map's value type. (The type of objects associated with the keys). 97 139 typedef T Value; 140 /// Map's reference type. 141 typedef R Reference; 142 /// Map's const reference type. 143 typedef CR ConstReference; 98 144 99 145 protected: 100 146 Value tmp; 101 147 public: 102 typedef Value& Reference;103 /// Map's const reference type.104 typedef const Value& ConstReference;105 148 106 149 ///Returns a reference to the value associated to a key. … … 112 155 void set(const Key &k,const Value &t) { operator[](k)=t; } 113 156 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 }; 116 181 }; 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 have122 // reference maps! --klao123 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 initializing131 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 generic138 // 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 GraphMapConceptCheck220 221 template<typename GraphMap, typename Graph>222 struct GraphMapConcept {223 void constraints() {224 function_requires< ReadWriteMapConcept<GraphMap> >();225 // Construction with a graph parameter226 GraphMap a(g);227 // Ctor with a graph and a default value parameter228 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 241 182 242 183 // @} -
src/lemon/concept/undir_graph.h
r986 r989 39 39 typedef typename Graph::Edge Edge; 40 40 typedef typename Graph::Node Node; 41 41 42 void constraints() { 42 function_requires< BaseIterableGraphComponentConcept<Graph>>();43 function_requires< GraphItemConcept<UndirEdge>>();43 checkConcept<BaseIterableGraphComponent, Graph>(); 44 checkConcept<GraphItem<'u'>, UndirEdge >(); 44 45 45 46 /// \bug this should be base_and_derived: … … 61 62 struct IterableUndirGraphConcept { 62 63 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 > (); 65 67 66 68 typedef typename Graph::UndirEdge UndirEdge; 67 69 typedef typename Graph::UndirEdgeIt UndirEdgeIt; 68 70 69 function_requires< 70 GraphIteratorConcept<UndirEdgeIt, Graph, UndirEdge> >(); 71 checkConcept< GraphIterator<Graph, UndirEdge>, UndirEdgeIt >(); 71 72 } 72 73 }; -
src/lemon/concept_check.h
r986 r989 40 40 } 41 41 42 template <typename Concept, typename Type> 43 inline void checkConcept() { 44 function_requires<typename Concept::template Constraints<Type> >(); 45 } 46 42 47 #define BOOST_CLASS_REQUIRE(type_var, ns, concept) \ 43 48 typedef void (ns::concept <type_var>::* func##type_var##concept)(); \ -
src/test/graph_test.cc
r980 r989 21 21 ///\file 22 22 { // checking graph components 23 function_requires<BaseGraphComponentConcept<BaseGraphComponent>>();23 checkConcept<BaseGraphComponent, BaseGraphComponent >(); 24 24 25 function_requires<BaseIterableGraphComponentConcept<BaseIterableGraphComponent>>();25 checkConcept<BaseIterableGraphComponent, BaseIterableGraphComponent >(); 26 26 27 function_requires<IDableGraphComponentConcept<IDableGraphComponent>>();28 function_requires<MaxIDableGraphComponentConcept<MaxIDableGraphComponent>>();27 checkConcept<IDableGraphComponent, IDableGraphComponent >(); 28 checkConcept<MaxIDableGraphComponent, MaxIDableGraphComponent >(); 29 29 30 function_requires<BaseExtendableGraphComponentConcept<BaseExtendableGraphComponent>>();31 function_requires<BaseErasableGraphComponentConcept<BaseErasableGraphComponent>>();32 function_requires<BaseClearableGraphComponentConcept<BaseClearableGraphComponent>>();30 checkConcept<BaseExtendableGraphComponent, BaseExtendableGraphComponent >(); 31 checkConcept<BaseErasableGraphComponent, BaseErasableGraphComponent >(); 32 checkConcept<BaseClearableGraphComponent, BaseClearableGraphComponent >(); 33 33 34 function_requires<IterableGraphComponentConcept<IterableGraphComponent>>();34 checkConcept<IterableGraphComponent, IterableGraphComponent >(); 35 35 36 function_requires<MappableGraphComponentConcept<MappableGraphComponent>>();36 checkConcept<MappableGraphComponent, MappableGraphComponent >(); 37 37 38 function_requires<ExtendableGraphComponentConcept<ExtendableGraphComponent>>();39 function_requires<ErasableGraphComponentConcept<ErasableGraphComponent>>();40 function_requires<ClearableGraphComponentConcept<ClearableGraphComponent>>();38 checkConcept<ExtendableGraphComponent, ExtendableGraphComponent >(); 39 checkConcept<ErasableGraphComponent, ErasableGraphComponent >(); 40 checkConcept<ClearableGraphComponent, ClearableGraphComponent >(); 41 41 } 42 42 { // checking skeleton graphs 43 function_requires<StaticGraphConcept<StaticGraph>>();44 function_requires<ExtendableGraphConcept<ExtendableGraph>>();45 function_requires<ErasableGraphConcept<ErasableGraph>>();43 checkConcept<StaticGraph, StaticGraph >(); 44 checkConcept<ExtendableGraph, ExtendableGraph >(); 45 checkConcept<ErasableGraph, ErasableGraph >(); 46 46 } 47 47 { // checking list graph 48 function_requires<ErasableGraphConcept<ListGraph>>();48 checkConcept<ErasableGraph, ListGraph >(); 49 49 50 50 checkGraph<ListGraph>(); … … 53 53 } 54 54 { // checking smart graph 55 function_requires<ExtendableGraphConcept<SmartGraph>>();55 checkConcept<ExtendableGraph, SmartGraph >(); 56 56 57 57 checkGraph<SmartGraph>(); … … 60 60 } 61 61 { // checking full graph 62 function_requires<StaticGraphConcept<FullGraph>>();62 checkConcept<StaticGraph, FullGraph >(); 63 63 } 64 64 -
src/test/graph_wrapper_test.cc
r970 r989 39 39 40 40 41 typedef SmartGraph Graph;42 43 41 44 42 int main() 45 43 { 46 44 { 47 function_requires<StaticGraphConcept<GraphWrapper<Graph>> >();45 checkConcept<StaticGraph, GraphWrapper<StaticGraph> >(); 48 46 49 47 // function_requires<StaticGraphConcept<RevGraphWrapper<Graph> > >();
Note: See TracChangeset
for help on using the changeset viewer.