Changeset 989:ca95f8b5c931 in lemon-0.x for src/lemon/concept/graph.h
- Timestamp:
- 11/13/04 22:37:54 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1379
- File:
-
- 1 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
Note: See TracChangeset
for help on using the changeset viewer.