Changeset 961:289d80c33f04 in lemon0.x
 Timestamp:
 11/04/04 23:04:51 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1344
 Location:
 src
 Files:

 1 deleted
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/concept/graph.h
r959 r961 766 766 767 767 768 /// \bug The nodes and edges are not allowed to inherit from the769 /// same baseclass.770 771 class BaseGraphItem {772 public: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 768 /// A minimal GraphBase concept 789 769 … … 795 775 GraphBase() {} 796 776 797 798 /// \bug Nodes and Edges are comparable each other 799 800 class Node : public BaseGraphItem {}; 801 class Edge : public BaseGraphItem {}; 777 /// \bug Should we demand that Node and Edge be subclasses of the 778 /// Graph class??? 779 780 typedef GraphItem<'n'> Node; 781 typedef GraphItem<'e'> Edge; 782 783 // class Node : public BaseGraphItem<'n'> {}; 784 // class Edge : public BaseGraphItem<'e'> {}; 802 785 803 786 // Graph operation … … 841 824 842 825 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; 851 852 i1 = i3; 853 if( i1 == i3 ) { 854 if ( i2 != i3 && i3 < i2 ) 855 return; 856 } 857 } 858 }; 859 860 826 827 /**************** The fullfeatured graph concepts ****************/ 828 861 829 862 830 class StaticGraph 863 : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { 831 : virtual public BaseGraphComponent, 832 public IterableGraphComponent, public MappableGraphComponent { 864 833 public: 865 834 typedef BaseGraphComponent::Node Node; … … 870 839 struct StaticGraphConcept { 871 840 void constraints() { 872 function_requires<BaseGraphComponentConcept<Graph> >();873 841 function_requires<IterableGraphComponentConcept<Graph> >(); 874 842 function_requires<MappableGraphComponentConcept<Graph> >(); 875 843 } 876 Graph& graph;877 844 }; 878 845 879 846 class ExtendableGraph 880 : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { 847 : virtual public BaseGraphComponent, public StaticGraph, 848 public ExtendableGraphComponent, public ClearableGraphComponent { 881 849 public: 882 850 typedef BaseGraphComponent::Node Node; … … 891 859 function_requires<ClearableGraphComponentConcept<Graph> >(); 892 860 } 893 Graph& graph;894 861 }; 895 862 896 863 class ErasableGraph 897 : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent { 864 : virtual public BaseGraphComponent, public ExtendableGraph, 865 public ErasableGraphComponent { 898 866 public: 899 867 typedef BaseGraphComponent::Node Node; … … 907 875 function_requires<ErasableGraphComponentConcept<Graph> >(); 908 876 } 909 Graph& graph;910 877 }; 911 878 
src/lemon/concept/graph_component.h
r959 r961 29 29 namespace concept { 30 30 31 32 /**************** Graph iterator concepts ****************/ 33 34 /// Skeleton class for graph Node and Edge 35 36 /// \note Because Node and Edge are forbidden to inherit from the same 37 /// base class, this is a template. For Node you shoul instantiate it 38 /// with character 'n' and for Edge with 'e'. 39 40 template<char Ch> 41 class GraphItem { 42 public: 43 GraphItem() {} 44 GraphItem(Invalid) {} 45 46 // We explicitely list these: 47 GraphItem(GraphItem const&) {} 48 GraphItem& operator=(GraphItem const&) { return *this; } 49 50 bool operator==(GraphItem) const { return false; } 51 bool operator!=(GraphItem) const { return false; } 52 53 // 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 123 31 124 /// An empty base graph class. 32 125 33 /// This class provides the most minimal features of a graph structure. 34 /// All the graph concepts have to be conform to this base graph. 126 /// This class provides the minimal set of features needed for a graph 127 /// structure. All graph concepts have to be conform to this base 128 /// graph. 129 /// 130 /// \bug This is not true. The minimal graph concept is the 131 /// BaseIterableGraphComponent. 35 132 36 133 class BaseGraphComponent { … … 71 168 /// Two iterators are equal if and only if they represents the 72 169 /// same node in the graph or both are invalid. 73 bool operator==(const Node&) { return true;}170 bool operator==(const Node&) const { return true;} 74 171 75 172 … … 78 175 /// \sa operator==(const Node& n) 79 176 /// 80 bool operator!=(const Node&) { return true;}177 bool operator!=(const Node&) const { return true;} 81 178 82 179 /// Comparison operator. … … 86 183 /// This ordering can be different from the iterating order of nodes. 87 184 /// \todo Possibly we don't need it. 88 bool operator<(const Node&) { return true;}185 bool operator<(const Node&) const { return true;} 89 186 }; 90 187 … … 121 218 /// Two iterators are equal if and only if they represents the 122 219 /// same edge in the graph or both are invalid. 123 bool operator==(const Edge&) { return true;}220 bool operator==(const Edge&) const { return true;} 124 221 125 222 … … 128 225 /// \sa operator==(const Edge& n) 129 226 /// 130 bool operator!=(const Edge&) { return true;}227 bool operator!=(const Edge&) const { return true;} 131 228 132 229 /// Comparison operator. … … 136 233 /// This ordering can be different from the iterating order of edges. 137 234 /// \todo Possibly we don't need it. 138 bool operator<(const Edge&) { return true;}235 bool operator<(const Edge&) const { return true;} 139 236 }; 140 237 … … 151 248 Node tail(const Edge&) const { return INVALID;} 152 249 }; 250 153 251 154 252 /// Concept check structure for BaseGraph. … … 163 261 164 262 void constraints() { 165 { 166 Node ni; 167 Node nj(ni); 168 Node nk(INVALID); 169 ni = nj; 170 bool b; b = true; 171 b = (ni == INVALID); b = (ni != INVALID); 172 b = (ni==nj); b = (ni != nj); b=( ni < nj); 173 } 174 { 175 Edge ei; 176 Edge ej(ei); 177 Edge ek(INVALID); 178 ei = ej; 179 bool b; b = true; 180 b = (ei == INVALID); b = (ei != INVALID); 181 b = (ei==ej); b = (ei != ej); b=( ei < ej); 182 } 263 function_requires< GraphItemConcept<Node> >(); 264 function_requires< GraphItemConcept<Edge> >(); 183 265 { 184 266 const Graph& const_graph = graph; … … 263 345 struct BaseIterableGraphComponentConcept { 264 346 265 void constraints() { 266 const Graph& const_graph = graph;347 void constraints() { 348 function_requires< BaseGraphComponentConcept<Graph> >(); 267 349 typename Graph::Node node; 268 350 typename Graph::Edge edge; 269 351 { 270 const_graph.first(node);271 const_graph.next(node);352 graph.first(node); 353 graph.next(node); 272 354 } 273 355 { 274 const_graph.first(edge);275 const_graph.next(edge);356 graph.first(edge); 357 graph.next(edge); 276 358 } 277 359 { 278 const_graph.firstIn(edge, node);279 const_graph.nextIn(edge);360 graph.firstIn(edge, node); 361 graph.nextIn(edge); 280 362 } 281 363 { 282 const_graph.firstOut(edge, node);283 const_graph.nextOut(edge);364 graph.firstOut(edge, node); 365 graph.nextOut(edge); 284 366 } 285 367 } 286 368 287 Graph& graph;369 const Graph& graph; 288 370 }; 289 371 … … 323 405 324 406 void constraints() { 325 const Graph& const_graph = graph;407 function_requires< BaseGraphComponentConcept<Graph> >(); 326 408 typename Graph::Node node; 327 int nid = const_graph.id(node);328 nid = const_graph.id(node);409 int nid = graph.id(node); 410 nid = graph.id(node); 329 411 typename Graph::Edge edge; 330 int eid = const_graph.id(edge);331 eid = const_graph.id(edge);332 } 333 334 Graph& graph;412 int eid = graph.id(edge); 413 eid = graph.id(edge); 414 } 415 416 const Graph& graph; 335 417 }; 336 418 … … 366 448 367 449 void constraints() { 368 const Graph& const_graph = graph;369 int nid = const_graph.maxEdgeId();450 function_requires< BaseGraphComponentConcept<Graph> >(); 451 int nid = graph.maxEdgeId(); 370 452 ignore_unused_variable_warning(nid); 371 int eid = const_graph.maxNodeId();453 int eid = graph.maxNodeId(); 372 454 ignore_unused_variable_warning(eid); 373 455 } 374 456 375 Graph& graph;457 const Graph& graph; 376 458 }; 377 459 … … 412 494 struct BaseExtendableGraphComponentConcept { 413 495 void constraints() { 496 function_requires< BaseGraphComponentConcept<Graph> >(); 414 497 typename Graph::Node node_a, node_b; 415 498 node_a = graph.addNode(); … … 453 536 struct BaseErasableGraphComponentConcept { 454 537 void constraints() { 538 function_requires< BaseGraphComponentConcept<Graph> >(); 455 539 typename Graph::Node node; 456 540 graph.erase(node); … … 484 568 struct BaseClearableGraphComponentConcept { 485 569 void constraints() { 570 function_requires< BaseGraphComponentConcept<Graph> >(); 486 571 graph.clear(); 487 572 } … … 491 576 492 577 493 class IterableGraphComponent : virtual public BaseGraphComponent { 578 class IterableGraphComponent : 579 virtual public BaseIterableGraphComponent { 494 580 495 581 public: … … 504 590 NodeIt() {} 505 591 NodeIt(Invalid) {} 506 NodeIt(const Graph&) {} 592 // explicit NodeIt(Node) {} 593 explicit NodeIt(const Graph&) {} 507 594 508 595 NodeIt& operator++() { return *this; } 509 596 // Node operator*() const { return INVALID; } 510 597 511 bool operator==(const NodeIt&) { return true;}512 bool operator!=(const NodeIt&) { return true;}598 bool operator==(const NodeIt&) const { return true;} 599 bool operator!=(const NodeIt&) const { return true;} 513 600 }; 514 601 … … 517 604 EdgeIt() {} 518 605 EdgeIt(Invalid) {} 519 EdgeIt(const Graph&) {} 606 // explicit EdgeIt(Edge) {} 607 explicit EdgeIt(const Graph&) {} 520 608 521 609 EdgeIt& operator++() { return *this; } 522 610 // Edge operator*() const { return INVALID; } 523 611 524 bool operator==(const EdgeIt&) { return true;}525 bool operator!=(const EdgeIt&) { return true;}612 bool operator==(const EdgeIt&) const { return true;} 613 bool operator!=(const EdgeIt&) const { return true;} 526 614 }; 527 615 … … 530 618 InEdgeIt() {} 531 619 InEdgeIt(Invalid) {} 532 InEdgeIt(const Graph&, const Node&) {} 620 // explicit InEdgeIt(Edge) {} 621 explicit InEdgeIt(const Graph&, const Node&) {} 533 622 534 623 InEdgeIt& operator++() { return *this; } 535 624 // Edge operator*() const { return INVALID; } 536 625 537 bool operator==(const InEdgeIt&) { return true;}538 bool operator!=(const InEdgeIt&) { return true;}626 bool operator==(const InEdgeIt&) const { return true;} 627 bool operator!=(const InEdgeIt&) const { return true;} 539 628 }; 540 629 … … 543 632 OutEdgeIt() {} 544 633 OutEdgeIt(Invalid) {} 545 OutEdgeIt(const Graph&, const Node&) {} 634 // explicit OutEdgeIt(Edge) {} 635 explicit OutEdgeIt(const Graph&, const Node&) {} 546 636 547 637 OutEdgeIt& operator++() { return *this; } 548 638 // Edge operator*() const { return INVALID; } 549 639 550 bool operator==(const OutEdgeIt&) { return true;}551 bool operator!=(const OutEdgeIt&) { return true;}640 bool operator==(const OutEdgeIt&) const { return true;} 641 bool operator!=(const OutEdgeIt&) const { return true;} 552 642 }; 553 643 … … 558 648 559 649 void constraints() { 560 650 function_requires< BaseIterableGraphComponentConcept<Graph> >(); 651 561 652 typedef typename Graph::Node Node; 562 653 typedef typename Graph::NodeIt NodeIt; … … 566 657 typedef typename Graph::OutEdgeIt OutEdgeIt; 567 658 568 { 569 NodeIt it; 570 NodeIt jt(it); 571 NodeIt kt(INVALID); 572 NodeIt lt(graph); 573 it = jt; 574 jt = ++it; 575 bool b; 576 b = (it == INVALID); 577 b = (it != INVALID); 578 b = (it == jt); 579 b = (it != jt); 580 Node node = it; 581 node = it; 582 } 583 { 584 EdgeIt it; 585 EdgeIt jt(it); 586 EdgeIt kt(INVALID); 587 EdgeIt lt(graph); 588 it = jt; 589 jt = ++it; 590 bool b; 591 b = (it == INVALID); 592 b = (it != INVALID); 593 b = (it == jt); 594 b = (it != jt); 595 Edge edge = it; 596 edge = it; 597 } 598 { 599 InEdgeIt it; 600 InEdgeIt jt(it); 601 InEdgeIt kt(INVALID); 602 Node node; 603 InEdgeIt lt(graph, node); 604 it = jt; 605 jt = ++it; 606 bool b; 607 b = (it == INVALID); 608 b = (it != INVALID); 609 b = (it == jt); 610 b = (it != jt); 611 Edge edge = it; 612 edge = it; 613 } 614 { 615 OutEdgeIt it; 616 OutEdgeIt jt(it); 617 OutEdgeIt kt(INVALID); 618 Node node; 619 OutEdgeIt lt(graph, node); 620 it = jt; 621 jt = ++it; 622 bool b; 623 b = (it == INVALID); 624 b = (it != INVALID); 625 b = (it == jt); 626 b = (it != jt); 627 Edge edge = it; 628 edge = it; 629 } 659 function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >(); 660 function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >(); 661 function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >(); 662 function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >(); 630 663 } 631 664 Graph& graph; … … 637 670 typedef IdMappableGraphComponent Graph; 638 671 639 typedef BaseGraphComponent::Node Node;640 typedef BaseGraphComponent::Edge Edge; 641 642 public:672 public: 673 674 typedef BaseGraphComponent::Node Node; 675 typedef BaseGraphComponent::Edge Edge; 643 676 644 677 class NodeIdMap : public ReadMap<Node, int> { … … 659 692 struct IdMappableGraphComponentConcept { 660 693 void constraints() { 694 function_requires< BaseGraphComponentConcept<Graph> >(); 661 695 { 662 696 typedef typename Graph::EdgeIdMap EdgeIdMap; … … 720 754 721 755 void constraints() { 756 function_requires< BaseGraphComponentConcept<Graph> >(); 722 757 { // int map test 723 758 typedef typename Graph::template NodeMap<int> IntNodeMap; … … 768 803 struct ExtendableGraphComponentConcept { 769 804 void constraints() { 805 function_requires< BaseGraphComponentConcept<Graph> >(); 770 806 typename Graph::Node node_a, node_b; 771 807 node_a = graph.addNode(); … … 792 828 struct ErasableGraphComponentConcept { 793 829 void constraints() { 830 function_requires< BaseGraphComponentConcept<Graph> >(); 794 831 typename Graph::Node node; 795 832 graph.erase(node); … … 816 853 struct ClearableGraphComponentConcept { 817 854 void constraints() { 855 function_requires< BaseGraphComponentConcept<Graph> >(); 818 856 graph.clear(); 819 857 } 
src/test/Makefile.am
r946 r961 18 18 kruskal_test \ 19 19 min_cost_flow_test \ 20 new_graph_test \21 20 suurballe_test \ 22 21 path_test \ … … 26 25 time_measure_test \ 27 26 unionfind_test \ 28 graph_wrapper_test \29 27 xy_test 30 28 … … 40 38 kruskal_test_SOURCES = kruskal_test.cc 41 39 min_cost_flow_test_SOURCES = min_cost_flow_test.cc 42 new_graph_test_SOURCES = new_graph_test.cc43 40 suurballe_test_SOURCES = suurballe_test.cc 44 41 path_test_SOURCES = path_test.cc
Note: See TracChangeset
for help on using the changeset viewer.