337 |
321 |
338 // /// Assign the iterator to the next |
322 // /// Assign the iterator to the next |
339 // /// edge of the corresponding node. |
323 // /// edge of the corresponding node. |
340 // EdgeIt& operator++() { return *this; } |
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 // ///Gives back the target node of an edge. |
326 // ///Gives back the target node of an edge. |
367 |
327 |
368 // ///Gives back the target node of an edge. |
328 // ///Gives back the target node of an edge. |
369 // /// |
329 // /// |
370 // Node target(Edge) const { return INVALID; } |
330 // Node target(Edge) const { return INVALID; } |
371 // ///Gives back the source node of an edge. |
331 // ///Gives back the source node of an edge. |
372 |
332 |
373 // ///Gives back the source node of an edge. |
333 // ///Gives back the source node of an edge. |
374 // /// |
334 // /// |
375 // Node source(Edge) const { return INVALID; } |
335 // Node source(Edge) const { return INVALID; } |
376 |
336 // /// Read write map of the nodes to type \c T. |
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 |
337 |
404 // /// \ingroup concept |
338 // /// \ingroup concept |
405 // ///Reference map of the nodes to type \c T. |
339 // /// ReadWrite map of the nodes to type \c T. |
406 // /// \sa Reference |
340 // /// \sa Reference |
407 // /// \warning Making maps that can handle bool type (NodeMap<bool>) |
341 // /// \warning Making maps that can handle bool type (NodeMap<bool>) |
408 // /// needs some extra attention! |
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 // public: |
346 // public: |
412 |
347 |
413 // ///\e |
348 // ///\e |
414 // NodeMap(const StaticGraph&) { } |
349 // NodeMap(const StaticGraph&) { } |
415 // ///\e |
350 // ///\e |
416 // NodeMap(const StaticGraph&, T) { } |
351 // NodeMap(const StaticGraph&, T) { } |
417 |
352 |
418 // ///Copy constructor |
353 // ///Copy constructor |
419 // template<typename TT> NodeMap(const NodeMap<TT>&) { } |
354 // NodeMap(const NodeMap&) { } |
420 // ///Assignment operator |
355 // ///Assignment operator |
421 // template<typename TT> NodeMap& operator=(const NodeMap<TT>&) |
356 // NodeMap& operator=(const NodeMap&) { return *this; } |
422 // { return *this; } |
357 // // \todo fix this concept |
423 // }; |
358 // }; |
424 |
359 |
425 // ///Reference map of the edges to type \c T. |
360 // /// Read write map of the edges to type \c T. |
426 |
361 |
427 // /// \ingroup concept |
362 // /// \ingroup concept |
428 // ///Reference map of the edges to type \c T. |
363 // ///Reference map of the edges to type \c T. |
429 // /// \sa Reference |
364 // /// \sa Reference |
430 // /// \warning Making maps that can handle bool type (EdgeMap<bool>) |
365 // /// \warning Making maps that can handle bool type (EdgeMap<bool>) |
431 // /// needs some extra attention! |
366 // /// needs some extra attention! |
432 // template<class T> class EdgeMap |
367 // template<class T> |
433 // : public ReferenceMap<Edge,T> |
368 // class EdgeMap : public ReadWriteMap<Edge,T> |
434 // { |
369 // { |
435 // public: |
370 // public: |
436 |
371 |
437 // ///\e |
372 // ///\e |
438 // EdgeMap(const StaticGraph&) { } |
373 // EdgeMap(const StaticGraph&) { } |
439 // ///\e |
374 // ///\e |
440 // EdgeMap(const StaticGraph&, T) { } |
375 // EdgeMap(const StaticGraph&, T) { } |
441 |
|
442 // ///Copy constructor |
376 // ///Copy constructor |
443 // template<typename TT> EdgeMap(const EdgeMap<TT>&) { } |
377 // EdgeMap(const EdgeMap&) { } |
444 // ///Assignment operator |
378 // ///Assignment operator |
445 // template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&) |
379 // EdgeMap& operator=(const EdgeMap&) { return *this; } |
446 // { 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 the |
|
458 // ///\ref lemon::concept::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.source(e); |
|
542 // n=G.target(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>::Value val; |
|
571 // val=1; |
|
572 // typename Graph::template NodeMap<int>::Key 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>::Value val; |
|
595 // val=true; |
|
596 // typename Graph::template NodeMap<bool>::Key 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>::Value val; |
|
618 // val=1; |
|
619 // typename Graph::template EdgeMap<int>::Key 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>::Value val; |
|
641 // val=true; |
|
642 // typename Graph::template EdgeMap<bool>::Key key; |
|
643 // key= typename Graph::EdgeIt(G); |
|
644 // } |
|
645 // } |
|
646 // } |
|
647 |
|
648 // /// An empty non-static graph class. |
384 // /// An empty non-static graph class. |
649 |
385 |
650 // /// This class provides everything that \ref StaticGraph |
386 // /// This class provides everything that \ref StaticGraph |
651 // /// with additional functionality which enables to build a |
387 // /// with additional functionality which enables to build a |
652 // /// graph from scratch. |
388 // /// graph from scratch. |
831 : virtual public BaseGraphComponent, |
508 : virtual public BaseGraphComponent, |
832 public IterableGraphComponent, public MappableGraphComponent { |
509 public IterableGraphComponent, public MappableGraphComponent { |
833 public: |
510 public: |
834 typedef BaseGraphComponent::Node Node; |
511 typedef BaseGraphComponent::Node Node; |
835 typedef BaseGraphComponent::Edge Edge; |
512 typedef BaseGraphComponent::Edge Edge; |
836 }; |
513 |
837 |
514 template <typename _Graph> |
838 template <typename Graph> |
515 struct Constraints { |
839 struct StaticGraphConcept { |
516 void constraints() { |
840 void constraints() { |
517 checkConcept<IterableGraphComponent, _Graph>(); |
841 function_requires<IterableGraphComponentConcept<Graph> >(); |
518 checkConcept<MappableGraphComponent, _Graph>(); |
842 function_requires<MappableGraphComponentConcept<Graph> >(); |
519 } |
843 } |
520 }; |
844 }; |
521 }; |
845 |
522 |
846 class ExtendableGraph |
523 class ExtendableGraph |
847 : virtual public BaseGraphComponent, public StaticGraph, |
524 : virtual public BaseGraphComponent, public StaticGraph, |
848 public ExtendableGraphComponent, public ClearableGraphComponent { |
525 public ExtendableGraphComponent, public ClearableGraphComponent { |
849 public: |
526 public: |
850 typedef BaseGraphComponent::Node Node; |
527 typedef BaseGraphComponent::Node Node; |
851 typedef BaseGraphComponent::Edge Edge; |
528 typedef BaseGraphComponent::Edge Edge; |
852 }; |
529 |
853 |
530 template <typename _Graph> |
854 template <typename Graph> |
531 struct Constraints { |
855 struct ExtendableGraphConcept { |
532 void constraints() { |
856 void constraints() { |
533 checkConcept<StaticGraph, _Graph >(); |
857 function_requires<StaticGraphConcept<Graph> >(); |
534 checkConcept<ExtendableGraphComponent, _Graph >(); |
858 function_requires<ExtendableGraphComponentConcept<Graph> >(); |
535 checkConcept<ClearableGraphComponent, _Graph >(); |
859 function_requires<ClearableGraphComponentConcept<Graph> >(); |
536 } |
860 } |
537 }; |
861 }; |
538 }; |
862 |
539 |
863 class ErasableGraph |
540 class ErasableGraph |
864 : virtual public BaseGraphComponent, public ExtendableGraph, |
541 : virtual public BaseGraphComponent, public ExtendableGraph, |
865 public ErasableGraphComponent { |
542 public ErasableGraphComponent { |
866 public: |
543 public: |
867 typedef BaseGraphComponent::Node Node; |
544 typedef BaseGraphComponent::Node Node; |
868 typedef BaseGraphComponent::Edge Edge; |
545 typedef BaseGraphComponent::Edge Edge; |
869 }; |
546 |
870 |
547 template <typename _Graph> |
871 template <typename Graph> |
548 struct Constraints { |
872 struct ErasableGraphConcept { |
549 void constraints() { |
873 void constraints() { |
550 checkConcept<ExtendableGraph, _Graph >(); |
874 function_requires<ExtendableGraphConcept<Graph> >(); |
551 checkConcept<ErasableGraphComponent, _Graph >(); |
875 function_requires<ErasableGraphComponentConcept<Graph> >(); |
552 } |
876 } |
553 }; |
877 }; |
554 }; |
878 |
555 |
879 // @} |
556 // @} |
880 } //namespace concept |
557 } //namespace concept |
881 } //namespace lemon |
558 } //namespace lemon |