Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/skeletons
- Timestamp:
- 10/28/04 00:38:50 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
- Location:
- src/lemon/skeletons
- Files:
-
- 1 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/skeletons/graph.h
r938 r946 24 24 #include <lemon/invalid.h> 25 25 #include <lemon/skeletons/maps.h> 26 #include <lemon/concept_check.h> 27 #include <lemon/skeletons/graph_component.h> 26 28 27 29 namespace lemon { … … 31 33 /// @{ 32 34 33 /// An empty static graph class.35 // /// An empty static graph class. 34 36 35 /// This class provides all the common features of a graph structure, 36 /// however completely without implementations and real data structures 37 /// behind the interface. 38 /// All graph algorithms should compile with this class, but it will not 39 /// run properly, of course. 40 /// 41 /// It can be used for checking the interface compatibility, 42 /// or it can serve as a skeleton of a new graph structure. 43 /// 44 /// Also, you will find here the full documentation of a certain graph 45 /// feature, the documentation of a real graph imlementation 46 /// like @ref ListGraph or 47 /// @ref SmartGraph will just refer to this structure. 48 /// 49 /// \todo A pages describing the concept of concept description would 50 /// be nice. 51 class StaticGraph 52 { 37 // /// This class provides all the common features of a graph structure, 38 // /// however completely without implementations and real data structures 39 // /// behind the interface. 40 // /// All graph algorithms should compile with this class, but it will not 41 // /// run properly, of course. 42 // /// 43 // /// It can be used for checking the interface compatibility, 44 // /// or it can serve as a skeleton of a new graph structure. 45 // /// 46 // /// Also, you will find here the full documentation of a certain graph 47 // /// feature, the documentation of a real graph imlementation 48 // /// like @ref ListGraph or 49 // /// @ref SmartGraph will just refer to this structure. 50 // /// 51 // /// \todo A pages describing the concept of concept description would 52 // /// be nice. 53 // class StaticGraph 54 // { 55 // public: 56 // /// Defalult constructor. 57 58 // /// Defalult constructor. 59 // /// 60 // StaticGraph() { } 61 // ///Copy consructor. 62 63 // // ///\todo It is not clear, what we expect from a copy constructor. 64 // // ///E.g. How to assign the nodes/edges to each other? What about maps? 65 // // StaticGraph(const StaticGraph& g) { } 66 67 // /// The base type of node iterators, 68 // /// or in other words, the trivial node iterator. 69 70 // /// This is the base type of each node iterator, 71 // /// thus each kind of node iterator converts to this. 72 // /// More precisely each kind of node iterator should be inherited 73 // /// from the trivial node iterator. 74 // class Node { 75 // public: 76 // /// Default constructor 77 78 // /// @warning The default constructor sets the iterator 79 // /// to an undefined value. 80 // Node() { } 81 // /// Copy constructor. 82 83 // /// Copy constructor. 84 // /// 85 // Node(const Node&) { } 86 87 // /// Invalid constructor \& conversion. 88 89 // /// This constructor initializes the iterator to be invalid. 90 // /// \sa Invalid for more details. 91 // Node(Invalid) { } 92 // /// Equality operator 93 94 // /// Two iterators are equal if and only if they point to the 95 // /// same object or both are invalid. 96 // bool operator==(Node) const { return true; } 97 98 // /// Inequality operator 99 100 // /// \sa operator==(Node n) 101 // /// 102 // bool operator!=(Node) const { return true; } 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 NodeIt 109 // ///goes through the nodes. 110 // ///\todo Possibly we don't need it. 111 // bool operator<(Node) const { return true; } 112 // }; 113 114 // /// This iterator goes through each node. 115 116 // /// This iterator goes through each node. 117 // /// Its usage is quite simple, for example you can count the number 118 // /// of nodes in graph \c g of type \c Graph like this: 119 // /// \code 120 // /// int count=0; 121 // /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; 122 // /// \endcode 123 // class NodeIt : public Node { 124 // public: 125 // /// Default constructor 126 127 // /// @warning The default constructor sets the iterator 128 // /// to an undefined value. 129 // NodeIt() { } 130 // /// Copy constructor. 131 132 // /// Copy constructor. 133 // /// 134 // NodeIt(const NodeIt&) { } 135 // /// Invalid constructor \& conversion. 136 137 // /// Initialize the iterator to be invalid. 138 // /// \sa Invalid for more details. 139 // NodeIt(Invalid) { } 140 // /// Sets the iterator to the first node. 141 142 // /// Sets the iterator to the first node of \c g. 143 // /// 144 // NodeIt(const StaticGraph& g) { } 145 // /// Node -> NodeIt conversion. 146 147 // /// Sets the iterator to the node of \c g pointed by the trivial 148 // /// iterator n. 149 // /// This feature necessitates that each time we 150 // /// iterate the edge-set, the iteration order is the same. 151 // NodeIt(const StaticGraph& g, const Node& n) { } 152 // /// Next node. 153 154 // /// Assign the iterator to the next node. 155 // /// 156 // NodeIt& operator++() { return *this; } 157 // }; 158 159 160 // /// The base type of the edge iterators. 161 162 // /// The base type of the edge iterators. 163 // /// 164 // class Edge { 165 // public: 166 // /// Default constructor 167 168 // /// @warning The default constructor sets the iterator 169 // /// to an undefined value. 170 // Edge() { } 171 // /// Copy constructor. 172 173 // /// Copy constructor. 174 // /// 175 // Edge(const Edge&) { } 176 // /// Initialize the iterator to be invalid. 177 178 // /// Initialize the iterator to be invalid. 179 // /// 180 // Edge(Invalid) { } 181 // /// Equality operator 182 183 // /// Two iterators are equal if and only if they point to the 184 // /// same object or both are invalid. 185 // bool operator==(Edge) const { return true; } 186 // /// Inequality operator 187 188 // /// \sa operator==(Node n) 189 // /// 190 // 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; } 199 // }; 200 201 // /// This iterator goes trough the outgoing edges of a node. 202 203 // /// This iterator goes trough the \e outgoing edges of a certain node 204 // /// of a graph. 205 // /// Its usage is quite simple, for example you can count the number 206 // /// of outgoing edges of a node \c n 207 // /// in graph \c g of type \c Graph as follows. 208 // /// \code 209 // /// int count=0; 210 // /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; 211 // /// \endcode 212 213 // class OutEdgeIt : public Edge { 214 // public: 215 // /// Default constructor 216 217 // /// @warning The default constructor sets the iterator 218 // /// to an undefined value. 219 // OutEdgeIt() { } 220 // /// Copy constructor. 221 222 // /// Copy constructor. 223 // /// 224 // OutEdgeIt(const OutEdgeIt&) { } 225 // /// Initialize the iterator to be invalid. 226 227 // /// Initialize the iterator to be invalid. 228 // /// 229 // OutEdgeIt(Invalid) { } 230 // /// This constructor sets the iterator to first outgoing edge. 231 232 // /// This constructor set the iterator to the first outgoing edge of 233 // /// node 234 // ///@param n the node 235 // ///@param g the graph 236 // OutEdgeIt(const StaticGraph& g, const Node& n) { } 237 // /// Edge -> OutEdgeIt conversion 238 239 // /// Sets the iterator to the value of the trivial iterator \c e. 240 // /// This feature necessitates that each time we 241 // /// iterate the edge-set, the iteration order is the same. 242 // OutEdgeIt(const StaticGraph& g, const Edge& e) { } 243 // ///Next outgoing edge 244 245 // /// Assign the iterator to the next 246 // /// outgoing edge of the corresponding node. 247 // OutEdgeIt& operator++() { return *this; } 248 // }; 249 250 // /// This iterator goes trough the incoming edges of a node. 251 252 // /// This iterator goes trough the \e incoming edges of a certain node 253 // /// of a graph. 254 // /// Its usage is quite simple, for example you can count the number 255 // /// of outgoing edges of a node \c n 256 // /// in graph \c g of type \c Graph as follows. 257 // /// \code 258 // /// int count=0; 259 // /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; 260 // /// \endcode 261 262 // class InEdgeIt : public Edge { 263 // public: 264 // /// Default constructor 265 266 // /// @warning The default constructor sets the iterator 267 // /// to an undefined value. 268 // InEdgeIt() { } 269 // /// Copy constructor. 270 271 // /// Copy constructor. 272 // /// 273 // InEdgeIt(const InEdgeIt&) { } 274 // /// Initialize the iterator to be invalid. 275 276 // /// Initialize the iterator to be invalid. 277 // /// 278 // InEdgeIt(Invalid) { } 279 // /// This constructor sets the iterator to first incoming edge. 280 281 // /// This constructor set the iterator to the first incoming edge of 282 // /// node 283 // ///@param n the node 284 // ///@param g the graph 285 // InEdgeIt(const StaticGraph& g, const Node& n) { } 286 // /// Edge -> InEdgeIt conversion 287 288 // /// Sets the iterator to the value of the trivial iterator \c e. 289 // /// This feature necessitates that each time we 290 // /// iterate the edge-set, the iteration order is the same. 291 // InEdgeIt(const StaticGraph& g, const Edge& n) { } 292 // /// Next incoming edge 293 294 // /// Assign the iterator to the next inedge of the corresponding node. 295 // /// 296 // InEdgeIt& operator++() { return *this; } 297 // }; 298 // /// This iterator goes through each edge. 299 300 // /// This iterator goes through each edge of a graph. 301 // /// Its usage is quite simple, for example you can count the number 302 // /// of edges in a graph \c g of type \c Graph as follows: 303 // /// \code 304 // /// int count=0; 305 // /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; 306 // /// \endcode 307 // class EdgeIt : public Edge { 308 // public: 309 // /// Default constructor 310 311 // /// @warning The default constructor sets the iterator 312 // /// to an undefined value. 313 // EdgeIt() { } 314 // /// Copy constructor. 315 316 // /// Copy constructor. 317 // /// 318 // EdgeIt(const EdgeIt&) { } 319 // /// Initialize the iterator to be invalid. 320 321 // /// Initialize the iterator to be invalid. 322 // /// 323 // EdgeIt(Invalid) { } 324 // /// This constructor sets the iterator to first edge. 325 326 // /// This constructor set the iterator to the first edge of 327 // /// node 328 // ///@param g the graph 329 // EdgeIt(const StaticGraph& g) { } 330 // /// Edge -> EdgeIt conversion 331 332 // /// Sets the iterator to the value of the trivial iterator \c e. 333 // /// This feature necessitates that each time we 334 // /// iterate the edge-set, the iteration order is the same. 335 // EdgeIt(const StaticGraph&, const Edge&) { } 336 // ///Next edge 337 338 // /// Assign the iterator to the next 339 // /// edge of the corresponding node. 340 // EdgeIt& operator++() { return *this; } 341 // }; 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 // ///Gives back the head node of an edge. 367 368 // ///Gives back the head node of an edge. 369 // /// 370 // Node head(Edge) const { return INVALID; } 371 // ///Gives back the tail node of an edge. 372 373 // ///Gives back the tail node of an edge. 374 // /// 375 // Node tail(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. 403 404 // /// \ingroup skeletons 405 // ///Reference map of the nodes to type \c T. 406 // /// \sa Reference 407 // /// \warning Making maps that can handle bool type (NodeMap<bool>) 408 // /// needs some extra attention! 409 // template<class T> class NodeMap : public ReferenceMap< Node, T > 410 // { 411 // public: 412 413 // ///\e 414 // NodeMap(const StaticGraph&) { } 415 // ///\e 416 // NodeMap(const StaticGraph&, T) { } 417 418 // ///Copy constructor 419 // template<typename TT> NodeMap(const NodeMap<TT>&) { } 420 // ///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. 426 427 // /// \ingroup skeletons 428 // ///Reference map of the edges to type \c T. 429 // /// \sa Reference 430 // /// \warning Making maps that can handle bool type (EdgeMap<bool>) 431 // /// needs some extra attention! 432 // template<class T> class EdgeMap 433 // : public ReferenceMap<Edge,T> 434 // { 435 // public: 436 437 // ///\e 438 // EdgeMap(const StaticGraph&) { } 439 // ///\e 440 // EdgeMap(const StaticGraph&, T) { } 441 442 // ///Copy constructor 443 // template<typename TT> EdgeMap(const EdgeMap<TT>&) { } 444 // ///Assignment operator 445 // template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&) 446 // { return *this; } 447 // }; 448 // }; 449 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::skeleton::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.tail(e); 542 // n=G.head(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>::ValueType val; 571 // val=1; 572 // typename Graph::template NodeMap<int>::KeyType 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>::ValueType val; 595 // val=true; 596 // typename Graph::template NodeMap<bool>::KeyType 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>::ValueType val; 618 // val=1; 619 // typename Graph::template EdgeMap<int>::KeyType 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>::ValueType val; 641 // val=true; 642 // typename Graph::template EdgeMap<bool>::KeyType key; 643 // key= typename Graph::EdgeIt(G); 644 // } 645 // } 646 // } 647 648 // /// An empty non-static graph class. 649 650 // /// This class provides everything that \ref StaticGraph 651 // /// with additional functionality which enables to build a 652 // /// graph from scratch. 653 // class ExtendableGraph : public StaticGraph 654 // { 655 // public: 656 // /// Defalult constructor. 657 658 // /// Defalult constructor. 659 // /// 660 // ExtendableGraph() { } 661 // ///Add a new node to the graph. 662 663 // /// \return the new node. 664 // /// 665 // Node addNode() { return INVALID; } 666 // ///Add a new edge to the graph. 667 668 // ///Add a new edge to the graph with tail node \c t 669 // ///and head node \c h. 670 // ///\return the new edge. 671 // Edge addEdge(Node h, Node t) { return INVALID; } 672 673 // /// Resets the graph. 674 675 // /// This function deletes all edges and nodes of the graph. 676 // /// It also frees the memory allocated to store them. 677 // /// \todo It might belong to \ref ErasableGraph. 678 // void clear() { } 679 // }; 680 681 682 // ///\brief Checks whether \c G meets the 683 // ///\ref lemon::skeleton::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 704 705 // /// An empty erasable graph class. 706 707 // /// This class is an extension of \ref ExtendableGraph. It also makes it 708 // /// possible to erase edges or nodes. 709 // class ErasableGraph : public ExtendableGraph 710 // { 711 // public: 712 // /// Defalult constructor. 713 714 // /// Defalult constructor. 715 // /// 716 // ErasableGraph() { } 717 // /// Deletes a node. 718 719 // /// Deletes node \c n node. 720 // /// 721 // void erase(Node n) { } 722 // /// Deletes an edge. 723 724 // /// Deletes edge \c e edge. 725 // /// 726 // void erase(Edge e) { } 727 // }; 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::skeleton::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 765 /************* New GraphBase stuff **************/ 766 767 768 /// \bug The nodes and edges are not allowed to inherit from the 769 /// same baseclass. 770 771 class BaseGraphItem { 53 772 public: 54 /// Defalult constructor. 55 56 /// Defalult constructor. 57 /// 58 StaticGraph() { } 59 ///Copy consructor. 60 61 // ///\todo It is not clear, what we expect from a copy constructor. 62 // ///E.g. How to assign the nodes/edges to each other? What about maps? 63 // StaticGraph(const StaticGraph& g) { } 64 65 /// The base type of node iterators, 66 /// or in other words, the trivial node iterator. 67 68 /// This is the base type of each node iterator, 69 /// thus each kind of node iterator converts to this. 70 /// More precisely each kind of node iterator should be inherited 71 /// from the trivial node iterator. 72 class Node { 73 public: 74 /// Default constructor 75 76 /// @warning The default constructor sets the iterator 77 /// to an undefined value. 78 Node() { } 79 /// Copy constructor. 80 81 /// Copy constructor. 82 /// 83 Node(const Node&) { } 84 85 /// Invalid constructor \& conversion. 86 87 /// This constructor initializes the iterator to be invalid. 88 /// \sa Invalid for more details. 89 Node(Invalid) { } 90 /// Equality operator 91 92 /// Two iterators are equal if and only if they point to the 93 /// same object or both are invalid. 94 bool operator==(Node) const { return true; } 95 96 /// Inequality operator 773 BaseGraphItem() {} 774 BaseGraphItem(Invalid) {} 775 776 // We explicitely list these: 777 BaseGraphItem(BaseGraphItem const&) {} 778 BaseGraphItem& operator=(BaseGraphItem const&) { return *this; } 779 780 bool operator==(BaseGraphItem) const { return false; } 781 bool operator!=(BaseGraphItem) const { return false; } 782 783 // Technical requirement. Do we really need this? 784 bool operator<(BaseGraphItem) const { return false; } 785 }; 786 787 788 /// A minimal GraphBase concept 789 790 /// This class describes a minimal concept which can be extended to a 791 /// full-featured graph with \ref GraphFactory. 792 class GraphBase { 793 public: 794 795 GraphBase() {} 796 797 798 /// \bug Nodes and Edges are comparable each other 799 800 class Node : public BaseGraphItem {}; 801 class Edge : public BaseGraphItem {}; 802 803 // Graph operation 804 void firstNode(Node &n) const { } 805 void firstEdge(Edge &e) const { } 806 807 void firstOutEdge(Edge &e, Node) const { } 808 void firstInEdge(Edge &e, Node) const { } 809 810 void nextNode(Node &n) const { } 811 void nextEdge(Edge &e) const { } 812 813 814 // Question: isn't it reasonable if this methods have a Node 815 // parameter? Like this: 816 // Edge& nextOut(Edge &e, Node) const { return e; } 817 void nextOutEdge(Edge &e) const { } 818 void nextInEdge(Edge &e) const { } 819 820 Node head(Edge) const { return Node(); } 821 Node tail(Edge) const { return Node(); } 822 823 824 // Do we need id, nodeNum, edgeNum and co. in this basic graphbase 825 // concept? 826 827 828 // Maps. 829 // 830 // We need a special slimer concept which does not provide maps (it 831 // wouldn't be strictly slimer, cause for map-factory id() & friends 832 // a required...) 833 834 template<typename T> 835 class NodeMap : public GraphMap<Node, T, GraphBase> {}; 836 837 template<typename T> 838 class EdgeMap : public GraphMap<Edge, T, GraphBase> {}; 839 }; 840 841 842 843 /**************** Concept checking classes ****************/ 844 845 template<typename BGI> 846 struct BaseGraphItemConcept { 847 void constraints() { 848 BGI i1; 849 BGI i2 = i1; 850 BGI i3 = INVALID; 97 851 98 /// \sa operator==(Node n) 99 /// 100 bool operator!=(Node) const { return true; } 101 102 ///Comparison operator. 103 104 ///This is a strict ordering between the nodes. 105 /// 106 ///This ordering can be different from the order in which NodeIt 107 ///goes through the nodes. 108 ///\todo Possibly we don't need it. 109 bool operator<(Node) const { return true; } 110 }; 111 112 /// This iterator goes through each node. 113 114 /// This iterator goes through each node. 115 /// Its usage is quite simple, for example you can count the number 116 /// of nodes in graph \c g of type \c Graph like this: 117 /// \code 118 /// int count=0; 119 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; 120 /// \endcode 121 class NodeIt : public Node { 122 public: 123 /// Default constructor 124 125 /// @warning The default constructor sets the iterator 126 /// to an undefined value. 127 NodeIt() { } 128 /// Copy constructor. 129 130 /// Copy constructor. 131 /// 132 NodeIt(const NodeIt&) { } 133 /// Invalid constructor \& conversion. 134 135 /// Initialize the iterator to be invalid. 136 /// \sa Invalid for more details. 137 NodeIt(Invalid) { } 138 /// Sets the iterator to the first node. 139 140 /// Sets the iterator to the first node of \c g. 141 /// 142 NodeIt(const StaticGraph& g) { } 143 /// Node -> NodeIt conversion. 144 145 /// Sets the iterator to the node of \c g pointed by the trivial 146 /// iterator n. 147 /// This feature necessitates that each time we 148 /// iterate the edge-set, the iteration order is the same. 149 NodeIt(const StaticGraph& g, const Node& n) { } 150 /// Next node. 151 152 /// Assign the iterator to the next node. 153 /// 154 NodeIt& operator++() { return *this; } 155 }; 156 157 158 /// The base type of the edge iterators. 159 160 /// The base type of the edge iterators. 161 /// 162 class Edge { 163 public: 164 /// Default constructor 165 166 /// @warning The default constructor sets the iterator 167 /// to an undefined value. 168 Edge() { } 169 /// Copy constructor. 170 171 /// Copy constructor. 172 /// 173 Edge(const Edge&) { } 174 /// Initialize the iterator to be invalid. 175 176 /// Initialize the iterator to be invalid. 177 /// 178 Edge(Invalid) { } 179 /// Equality operator 180 181 /// Two iterators are equal if and only if they point to the 182 /// same object or both are invalid. 183 bool operator==(Edge) const { return true; } 184 /// Inequality operator 185 186 /// \sa operator==(Node n) 187 /// 188 bool operator!=(Edge) const { return true; } 189 ///Comparison operator. 190 191 ///This is a strict ordering between the nodes. 192 /// 193 ///This ordering can be different from the order in which NodeIt 194 ///goes through the nodes. 195 ///\todo Possibly we don't need it. 196 bool operator<(Edge) const { return true; } 197 }; 198 199 /// This iterator goes trough the outgoing edges of a node. 200 201 /// This iterator goes trough the \e outgoing edges of a certain node 202 /// of a graph. 203 /// Its usage is quite simple, for example you can count the number 204 /// of outgoing edges of a node \c n 205 /// in graph \c g of type \c Graph as follows. 206 /// \code 207 /// int count=0; 208 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; 209 /// \endcode 210 211 class OutEdgeIt : public Edge { 212 public: 213 /// Default constructor 214 215 /// @warning The default constructor sets the iterator 216 /// to an undefined value. 217 OutEdgeIt() { } 218 /// Copy constructor. 219 220 /// Copy constructor. 221 /// 222 OutEdgeIt(const OutEdgeIt&) { } 223 /// Initialize the iterator to be invalid. 224 225 /// Initialize the iterator to be invalid. 226 /// 227 OutEdgeIt(Invalid) { } 228 /// This constructor sets the iterator to first outgoing edge. 229 230 /// This constructor set the iterator to the first outgoing edge of 231 /// node 232 ///@param n the node 233 ///@param g the graph 234 OutEdgeIt(const StaticGraph& g, const Node& n) { } 235 /// Edge -> OutEdgeIt conversion 236 237 /// Sets the iterator to the value of the trivial iterator \c e. 238 /// This feature necessitates that each time we 239 /// iterate the edge-set, the iteration order is the same. 240 OutEdgeIt(const StaticGraph& g, const Edge& e) { } 241 ///Next outgoing edge 242 243 /// Assign the iterator to the next 244 /// outgoing edge of the corresponding node. 245 OutEdgeIt& operator++() { return *this; } 246 }; 247 248 /// This iterator goes trough the incoming edges of a node. 249 250 /// This iterator goes trough the \e incoming edges of a certain node 251 /// of a graph. 252 /// Its usage is quite simple, for example you can count the number 253 /// of outgoing edges of a node \c n 254 /// in graph \c g of type \c Graph as follows. 255 /// \code 256 /// int count=0; 257 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; 258 /// \endcode 259 260 class InEdgeIt : public Edge { 261 public: 262 /// Default constructor 263 264 /// @warning The default constructor sets the iterator 265 /// to an undefined value. 266 InEdgeIt() { } 267 /// Copy constructor. 268 269 /// Copy constructor. 270 /// 271 InEdgeIt(const InEdgeIt&) { } 272 /// Initialize the iterator to be invalid. 273 274 /// Initialize the iterator to be invalid. 275 /// 276 InEdgeIt(Invalid) { } 277 /// This constructor sets the iterator to first incoming edge. 278 279 /// This constructor set the iterator to the first incoming edge of 280 /// node 281 ///@param n the node 282 ///@param g the graph 283 InEdgeIt(const StaticGraph& g, const Node& n) { } 284 /// Edge -> InEdgeIt conversion 285 286 /// Sets the iterator to the value of the trivial iterator \c e. 287 /// This feature necessitates that each time we 288 /// iterate the edge-set, the iteration order is the same. 289 InEdgeIt(const StaticGraph& g, const Edge& n) { } 290 /// Next incoming edge 291 292 /// Assign the iterator to the next inedge of the corresponding node. 293 /// 294 InEdgeIt& operator++() { return *this; } 295 }; 296 /// This iterator goes through each edge. 297 298 /// This iterator goes through each edge of a graph. 299 /// Its usage is quite simple, for example you can count the number 300 /// of edges in a graph \c g of type \c Graph as follows: 301 /// \code 302 /// int count=0; 303 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; 304 /// \endcode 305 class EdgeIt : public Edge { 306 public: 307 /// Default constructor 308 309 /// @warning The default constructor sets the iterator 310 /// to an undefined value. 311 EdgeIt() { } 312 /// Copy constructor. 313 314 /// Copy constructor. 315 /// 316 EdgeIt(const EdgeIt&) { } 317 /// Initialize the iterator to be invalid. 318 319 /// Initialize the iterator to be invalid. 320 /// 321 EdgeIt(Invalid) { } 322 /// This constructor sets the iterator to first edge. 323 324 /// This constructor set the iterator to the first edge of 325 /// node 326 ///@param g the graph 327 EdgeIt(const StaticGraph& g) { } 328 /// Edge -> EdgeIt conversion 329 330 /// Sets the iterator to the value of the trivial iterator \c e. 331 /// This feature necessitates that each time we 332 /// iterate the edge-set, the iteration order is the same. 333 EdgeIt(const StaticGraph&, const Edge&) { } 334 ///Next edge 335 336 /// Assign the iterator to the next 337 /// edge of the corresponding node. 338 EdgeIt& operator++() { return *this; } 339 }; 340 341 /// First node of the graph. 342 343 /// \retval i the first node. 344 /// \return the first node. 345 /// 346 NodeIt& first(NodeIt& i) const { return i; } 347 348 /// The first incoming edge. 349 350 /// The first incoming edge. 351 /// 352 InEdgeIt& first(InEdgeIt &i, Node) const { return i; } 353 /// The first outgoing edge. 354 355 /// The first outgoing edge. 356 /// 357 OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } 358 /// The first edge of the Graph. 359 360 /// The first edge of the Graph. 361 /// 362 EdgeIt& first(EdgeIt& i) const { return i; } 363 364 ///Gives back the head node of an edge. 365 366 ///Gives back the head node of an edge. 367 /// 368 Node head(Edge) const { return INVALID; } 369 ///Gives back the tail node of an edge. 370 371 ///Gives back the tail node of an edge. 372 /// 373 Node tail(Edge) const { return INVALID; } 374 375 ///Gives back the \e id of a node. 376 377 ///\warning Not all graph structures provide this feature. 378 /// 379 ///\todo Should each graph provide \c id? 380 int id(const Node&) const { return 0; } 381 ///Gives back the \e id of an edge. 382 383 ///\warning Not all graph structures provide this feature. 384 /// 385 ///\todo Should each graph provide \c id? 386 int id(const Edge&) const { return 0; } 387 388 ///\e 389 390 ///\todo Should it be in the concept? 391 /// 392 int nodeNum() const { return 0; } 393 ///\e 394 395 ///\todo Should it be in the concept? 396 /// 397 int edgeNum() const { return 0; } 398 399 400 ///Reference map of the nodes to type \c T. 401 402 /// \ingroup skeletons 403 ///Reference map of the nodes to type \c T. 404 /// \sa Reference 405 /// \warning Making maps that can handle bool type (NodeMap<bool>) 406 /// needs some extra attention! 407 template<class T> class NodeMap : public ReferenceMap< Node, T > 408 { 409 public: 410 411 ///\e 412 NodeMap(const StaticGraph&) { } 413 ///\e 414 NodeMap(const StaticGraph&, T) { } 415 416 ///Copy constructor 417 template<typename TT> NodeMap(const NodeMap<TT>&) { } 418 ///Assignment operator 419 template<typename TT> NodeMap& operator=(const NodeMap<TT>&) 420 { return *this; } 421 }; 422 423 ///Reference map of the edges to type \c T. 424 425 /// \ingroup skeletons 426 ///Reference map of the edges to type \c T. 427 /// \sa Reference 428 /// \warning Making maps that can handle bool type (EdgeMap<bool>) 429 /// needs some extra attention! 430 template<class T> class EdgeMap 431 : public ReferenceMap<Edge,T> 432 { 433 public: 434 435 ///\e 436 EdgeMap(const StaticGraph&) { } 437 ///\e 438 EdgeMap(const StaticGraph&, T) { } 439 440 ///Copy constructor 441 template<typename TT> EdgeMap(const EdgeMap<TT>&) { } 442 ///Assignment operator 443 template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&) 444 { return *this; } 445 }; 446 }; 447 448 struct DummyType { 449 int value; 450 DummyType() {} 451 DummyType(int p) : value(p) {} 452 DummyType& operator=(int p) { value = p; return *this;} 453 }; 454 455 ///\brief Checks whether \c G meets the 456 ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept 457 template<class Graph> void checkCompileStaticGraph(Graph &G) 458 { 459 typedef typename Graph::Node Node; 460 typedef typename Graph::NodeIt NodeIt; 461 typedef typename Graph::Edge Edge; 462 typedef typename Graph::EdgeIt EdgeIt; 463 typedef typename Graph::InEdgeIt InEdgeIt; 464 typedef typename Graph::OutEdgeIt OutEdgeIt; 465 466 { 467 Node i; Node j(i); Node k(INVALID); 468 i=j; 469 bool b; b=true; 470 b=(i==INVALID); b=(i!=INVALID); 471 b=(i==j); b=(i!=j); b=(i<j); 472 } 473 { 474 NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); 475 i=j; 476 j=G.first(i); 477 j=++i; 478 bool b; b=true; 479 b=(i==INVALID); b=(i!=INVALID); 480 Node n(i); 481 n=i; 482 b=(i==j); b=(i!=j); b=(i<j); 483 //Node ->NodeIt conversion 484 NodeIt ni(G,n); 485 } 486 { 487 Edge i; Edge j(i); Edge k(INVALID); 488 i=j; 489 bool b; b=true; 490 b=(i==INVALID); b=(i!=INVALID); 491 b=(i==j); b=(i!=j); b=(i<j); 492 } 493 { 494 EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); 495 i=j; 496 j=G.first(i); 497 j=++i; 498 bool b; b=true; 499 b=(i==INVALID); b=(i!=INVALID); 500 Edge e(i); 501 e=i; 502 b=(i==j); b=(i!=j); b=(i<j); 503 //Edge ->EdgeIt conversion 504 EdgeIt ei(G,e); 505 } 506 { 507 Node n; 508 InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); 509 i=j; 510 j=G.first(i,n); 511 j=++i; 512 bool b; b=true; 513 b=(i==INVALID); b=(i!=INVALID); 514 Edge e(i); 515 e=i; 516 b=(i==j); b=(i!=j); b=(i<j); 517 //Edge ->InEdgeIt conversion 518 InEdgeIt ei(G,e); 519 } 520 { 521 Node n; 522 OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); 523 i=j; 524 j=G.first(i,n); 525 j=++i; 526 bool b; b=true; 527 b=(i==INVALID); b=(i!=INVALID); 528 Edge e(i); 529 e=i; 530 b=(i==j); b=(i!=j); b=(i<j); 531 //Edge ->OutEdgeIt conversion 532 OutEdgeIt ei(G,e); 533 } 534 { 535 Node n,m; 536 n=m=INVALID; 537 Edge e; 538 e=INVALID; 539 n=G.tail(e); 540 n=G.head(e); 541 } 542 // id tests 543 { Node n; int i=G.id(n); i=i; } 544 { Edge e; int i=G.id(e); i=i; } 545 //NodeMap tests 546 { 547 Node k; 548 typename Graph::template NodeMap<int> m(G); 549 //Const map 550 typename Graph::template NodeMap<int> const &cm = m; 551 //Inicialize with default value 552 typename Graph::template NodeMap<int> mdef(G,12); 553 //Copy 554 typename Graph::template NodeMap<int> mm(cm); 555 //Copy from another type 556 typename Graph::template NodeMap<double> dm(cm); 557 //Copy to more complex type 558 typename Graph::template NodeMap<DummyType> em(cm); 559 int v; 560 v=m[k]; m[k]=v; m.set(k,v); 561 v=cm[k]; 562 563 m=cm; 564 dm=cm; //Copy from another type 565 em=cm; //Copy to more complex type 566 { 567 //Check the typedef's 568 typename Graph::template NodeMap<int>::ValueType val; 569 val=1; 570 typename Graph::template NodeMap<int>::KeyType key; 571 key = typename Graph::NodeIt(G); 572 } 573 } 574 { //bool NodeMap 575 Node k; 576 typename Graph::template NodeMap<bool> m(G); 577 typename Graph::template NodeMap<bool> const &cm = m; //Const map 578 //Inicialize with default value 579 typename Graph::template NodeMap<bool> mdef(G,12); 580 typename Graph::template NodeMap<bool> mm(cm); //Copy 581 typename Graph::template NodeMap<int> dm(cm); //Copy from another type 582 bool v; 583 v=m[k]; m[k]=v; m.set(k,v); 584 v=cm[k]; 585 586 m=cm; 587 dm=cm; //Copy from another type 588 m=dm; //Copy to another type 589 590 { 591 //Check the typedef's 592 typename Graph::template NodeMap<bool>::ValueType val; 593 val=true; 594 typename Graph::template NodeMap<bool>::KeyType key; 595 key= typename Graph::NodeIt(G); 852 i1 = i3; 853 if( i1 == i3 ) { 854 if ( i2 != i3 && i3 < i2 ) 855 return; 596 856 } 597 857 } 598 //EdgeMap tests 599 { 600 Edge k; 601 typename Graph::template EdgeMap<int> m(G); 602 typename Graph::template EdgeMap<int> const &cm = m; //Const map 603 //Inicialize with default value 604 typename Graph::template EdgeMap<int> mdef(G,12); 605 typename Graph::template EdgeMap<int> mm(cm); //Copy 606 typename Graph::template EdgeMap<double> dm(cm);//Copy from another type 607 int v; 608 v=m[k]; m[k]=v; m.set(k,v); 609 v=cm[k]; 610 611 m=cm; 612 dm=cm; //Copy from another type 613 { 614 //Check the typedef's 615 typename Graph::template EdgeMap<int>::ValueType val; 616 val=1; 617 typename Graph::template EdgeMap<int>::KeyType key; 618 key= typename Graph::EdgeIt(G); 619 } 620 } 621 { //bool EdgeMap 622 Edge k; 623 typename Graph::template EdgeMap<bool> m(G); 624 typename Graph::template EdgeMap<bool> const &cm = m; //Const map 625 //Inicialize with default value 626 typename Graph::template EdgeMap<bool> mdef(G,12); 627 typename Graph::template EdgeMap<bool> mm(cm); //Copy 628 typename Graph::template EdgeMap<int> dm(cm); //Copy from another type 629 bool v; 630 v=m[k]; m[k]=v; m.set(k,v); 631 v=cm[k]; 632 633 m=cm; 634 dm=cm; //Copy from another type 635 m=dm; //Copy to another type 636 { 637 //Check the typedef's 638 typename Graph::template EdgeMap<bool>::ValueType val; 639 val=true; 640 typename Graph::template EdgeMap<bool>::KeyType key; 641 key= typename Graph::EdgeIt(G); 642 } 858 }; 859 860 861 862 class StaticGraph 863 : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { 864 public: 865 typedef BaseGraphComponent::Node Node; 866 typedef BaseGraphComponent::Edge Edge; 867 }; 868 869 template <typename Graph> 870 struct StaticGraphConcept { 871 void constraints() { 872 function_requires<BaseGraphComponentConcept<Graph> >(); 873 function_requires<IterableGraphComponentConcept<Graph> >(); 874 function_requires<MappableGraphComponentConcept<Graph> >(); 643 875 } 644 } 645 646 /// An empty non-static graph class. 647 648 /// This class provides everything that \ref StaticGraph 649 /// with additional functionality which enables to build a 650 /// graph from scratch. 651 class ExtendableGraph : public StaticGraph 652 { 876 Graph& graph; 877 }; 878 879 class ExtendableGraph 880 : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { 653 881 public: 654 /// Defalult constructor. 655 656 /// Defalult constructor. 657 /// 658 ExtendableGraph() { } 659 ///Add a new node to the graph. 660 661 /// \return the new node. 662 /// 663 Node addNode() { return INVALID; } 664 ///Add a new edge to the graph. 665 666 ///Add a new edge to the graph with tail node \c t 667 ///and head node \c h. 668 ///\return the new edge. 669 Edge addEdge(Node h, Node t) { return INVALID; } 670 671 /// Resets the graph. 672 673 /// This function deletes all edges and nodes of the graph. 674 /// It also frees the memory allocated to store them. 675 /// \todo It might belong to \ref ErasableGraph. 676 void clear() { } 882 typedef BaseGraphComponent::Node Node; 883 typedef BaseGraphComponent::Edge Edge; 677 884 }; 678 885 679 680 ///\brief Checks whether \c G meets the 681 ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept 682 template<class Graph> void checkCompileExtendableGraph(Graph &G) 683 { 684 checkCompileStaticGraph(G); 685 686 typedef typename Graph::Node Node; 687 typedef typename Graph::NodeIt NodeIt; 688 typedef typename Graph::Edge Edge; 689 typedef typename Graph::EdgeIt EdgeIt; 690 typedef typename Graph::InEdgeIt InEdgeIt; 691 typedef typename Graph::OutEdgeIt OutEdgeIt; 692 693 Node n,m; 694 n=G.addNode(); 695 m=G.addNode(); 696 Edge e; 697 e=G.addEdge(n,m); 698 699 // G.clear(); 700 } 701 702 703 /// An empty erasable graph class. 704 705 /// This class is an extension of \ref ExtendableGraph. It also makes it 706 /// possible to erase edges or nodes. 707 class ErasableGraph : public ExtendableGraph 708 { 886 template <typename Graph> 887 struct ExtendableGraphConcept { 888 void constraints() { 889 function_requires<StaticGraphConcept<Graph> >(); 890 function_requires<ExtendableGraphComponentConcept<Graph> >(); 891 function_requires<ClearableGraphComponentConcept<Graph> >(); 892 } 893 Graph& graph; 894 }; 895 896 class ErasableGraph 897 : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent { 709 898 public: 710 /// Defalult constructor. 711 712 /// Defalult constructor. 713 /// 714 ErasableGraph() { } 715 /// Deletes a node. 716 717 /// Deletes node \c n node. 718 /// 719 void erase(Node n) { } 720 /// Deletes an edge. 721 722 /// Deletes edge \c e edge. 723 /// 724 void erase(Edge e) { } 899 typedef BaseGraphComponent::Node Node; 900 typedef BaseGraphComponent::Edge Edge; 725 901 }; 726 727 template<class Graph> void checkCompileGraphEraseEdge(Graph &G) 728 { 729 typename Graph::Edge e; 730 G.erase(e); 731 } 732 733 template<class Graph> void checkCompileGraphEraseNode(Graph &G) 734 { 735 typename Graph::Node n; 736 G.erase(n); 737 } 738 739 ///\brief Checks whether \c G meets the 740 ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept 741 template<class Graph> void checkCompileErasableGraph(Graph &G) 742 { 743 checkCompileExtendableGraph(G); 744 checkCompileGraphEraseNode(G); 745 checkCompileGraphEraseEdge(G); 746 } 747 748 ///Checks whether a graph has findEdge() member function. 749 750 ///\todo findEdge() might be a global function. 751 /// 752 template<class Graph> void checkCompileGraphFindEdge(Graph &G) 753 { 754 typedef typename Graph::NodeIt Node; 755 typedef typename Graph::NodeIt NodeIt; 756 757 G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); 758 G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 759 } 760 902 903 template <typename Graph> 904 struct ErasableGraphConcept { 905 void constraints() { 906 function_requires<ExtendableGraphConcept<Graph> >(); 907 function_requires<ErasableGraphComponentConcept<Graph> >(); 908 } 909 Graph& graph; 910 }; 911 761 912 // @} 762 913 } //namespace skeleton -
src/lemon/skeletons/maps.h
r921 r946 17 17 #ifndef LEMON_MAPSKELETON_H 18 18 #define LEMON_MAPSKELETON_H 19 20 #include <lemon/concept_check.h> 19 21 20 22 ///\ingroup skeletons … … 114 116 }; 115 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::KeyType KeyType; 153 typedef typename ReadMap::ValueType ValueType; 154 155 void constraints() { 156 // No constraints for constructor. 157 158 // What are the requirement for the ValueType? 159 // CopyConstructible? Assignable? None of these? 160 ValueType v = m[k]; 161 v = m[k]; 162 163 // FIXME: 164 ignore_unused_variable_warning(v); 165 } 166 167 ReadMap m; 168 KeyType k; 169 }; 170 171 template<typename WriteMap> 172 struct WriteMapConcept { 173 typedef typename WriteMap::KeyType KeyType; 174 typedef typename WriteMap::ValueType ValueType; 175 176 void constraints() { 177 // No constraints for constructor. 178 179 m.set(k, v); 180 } 181 182 WriteMap m; 183 KeyType k; 184 ValueType 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::KeyType KeyType; 198 typedef typename ReferenceMap::ValueType ValueType; 199 typedef typename ReferenceMap::ReferenceType ReferenceType; 200 201 // What for is this? 202 typedef typename ReferenceMap::ConstReferenceType ConstReferenceType; 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 // ValueType &vv = m[k]; 211 // ignore_unused_variable_warning(vv); 212 } 213 214 ReferenceMap m; 215 KeyType k; 216 ValueType 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::ValueType &t; 239 }; 240 241 116 242 // @} 117 243
Note: See TracChangeset
for help on using the changeset viewer.