Changeset 961:289d80c33f04 in lemon0.x for src/lemon/concept/graph_component.h
 Timestamp:
 11/04/04 23:04:51 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1344
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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