COIN-OR::LEMON - Graph Library

Changeset 989:ca95f8b5c931 in lemon-0.x for src/lemon/concept/graph.h


Ignore:
Timestamp:
11/13/04 22:37:54 (17 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1379
Message:

XyzConcept? moved to Xyz::Constraints
use checkConcept in the next way:

checkConcept<ErasableGraph?, ListGraph?>();
checkConcept<ReadWriteMap?<Node, Node>, PredMap?>;

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/concept/graph.h

    r987 r989  
    102102//      bool operator!=(Node) const { return true; }
    103103
    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; }
    112104//       };
    113105   
     
    189181//      ///
    190182//      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; }
    199183//       };
    200184   
     
    340324//      EdgeIt& operator++() { return *this; }
    341325//       };
    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 
    366326//       ///Gives back the target node of an edge.
    367327
     
    374334//       ///
    375335//       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.
    403337
    404338//       /// \ingroup concept
    405 //       ///Reference map of the nodes to type \c T.
     339//       /// ReadWrite map of the nodes to type \c T.
    406340//       /// \sa Reference
    407341//       /// \warning Making maps that can handle bool type (NodeMap<bool>)
    408342//       /// 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 >
    410345//       {
    411346//       public:
     
    417352
    418353//      ///Copy constructor
    419 //      template<typename TT> NodeMap(const NodeMap<TT>&) { }
     354//      NodeMap(const NodeMap&) { }
    420355//      ///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.
    426361
    427362//       /// \ingroup concept
     
    430365//       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
    431366//       /// needs some extra attention!
    432 //       template<class T> class EdgeMap
    433 //      : public ReferenceMap<Edge,T>
     367//       template<class T>
     368//       class EdgeMap : public ReadWriteMap<Edge,T>
    434369//       {
    435370//       public:
     
    439374//      ///\e
    440375//      EdgeMap(const StaticGraph&, T) { }
    441    
    442376//      ///Copy constructor
    443 //      template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
     377//      EdgeMap(const EdgeMap&) { }
    444378//      ///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   
    447381//       };
    448382//     };
    449383
    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    
    648384//     /// An empty non-static graph class.
    649385   
     
    666402//       ///Add a new edge to the graph.
    667403
    668 //       ///Add a new edge to the graph with source node \c t
    669 //       ///and target node \c h.
     404//       ///Add a new edge to the graph with source node \c s
     405//       ///and target node \c t.
    670406//       ///\return the new edge.
    671 //       Edge addEdge(Node h, Node t) { return INVALID; }
     407//       Edge addEdge(Node s, Node t) { return INVALID; }
    672408   
    673409//       /// Resets the graph.
     
    678414//       void clear() { }
    679415//     };
    680 
    681    
    682 //     ///\brief Checks whether \c G meets the
    683 //     ///\ref lemon::concept::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 
    704416
    705417//     /// An empty erasable graph class.
     
    726438//       void erase(Edge e) { }
    727439//     };
    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   
    765442    /************* New GraphBase stuff **************/
    766443
     
    816493
    817494      template<typename T>
    818       class NodeMap : public GraphMap<Node, T, GraphBase> {};
     495      class NodeMap : public GraphMap<GraphBase, Node, T> {};
    819496
    820497      template<typename T>
    821       class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
     498      class EdgeMap : public GraphMap<GraphBase, Node, T> {};
    822499    };
    823500
     
    834511      typedef BaseGraphComponent::Node Node;
    835512      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      };
    844521    };
    845522
     
    850527      typedef BaseGraphComponent::Node Node;
    851528      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      };
    861538    };
    862539
     
    867544      typedef BaseGraphComponent::Node Node;
    868545      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      };
    877554    };
    878555
Note: See TracChangeset for help on using the changeset viewer.