COIN-OR::LEMON - Graph Library

Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/skeletons


Ignore:
Timestamp:
10/28/04 00:38:50 (16 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
Message:

The graph_factory branch (@ 1321) has been merged to trunk.

Location:
src/lemon/skeletons
Files:
1 added
2 edited

Legend:

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

    r938 r946  
    2424#include <lemon/invalid.h>
    2525#include <lemon/skeletons/maps.h>
     26#include <lemon/concept_check.h>
     27#include <lemon/skeletons/graph_component.h>
    2628
    2729namespace lemon {
     
    3133    /// @{
    3234
    33     /// An empty static graph class.
     35//     /// An empty static graph class.
    3436 
    35     /// This class provides all the common features of a graph structure,
    36     /// however completely without implementations and real data structures
    37     /// behind the interface.
    38     /// All graph algorithms should compile with this class, but it will not
    39     /// run properly, of course.
    40     ///
    41     /// It can be used for checking the interface compatibility,
    42     /// or it can serve as a skeleton of a new graph structure.
    43     ///
    44     /// Also, you will find here the full documentation of a certain graph
    45     /// feature, the documentation of a real graph imlementation
    46     /// like @ref ListGraph or
    47     /// @ref SmartGraph will just refer to this structure.
    48     ///
    49     /// \todo A pages describing the concept of concept description would
    50     /// be nice.
    51     class StaticGraph
    52     {
     37//     /// This class provides all the common features of a graph structure,
     38//     /// however completely without implementations and real data structures
     39//     /// behind the interface.
     40//     /// All graph algorithms should compile with this class, but it will not
     41//     /// run properly, of course.
     42//     ///
     43//     /// It can be used for checking the interface compatibility,
     44//     /// or it can serve as a skeleton of a new graph structure.
     45//     ///
     46//     /// Also, you will find here the full documentation of a certain graph
     47//     /// feature, the documentation of a real graph imlementation
     48//     /// like @ref ListGraph or
     49//     /// @ref SmartGraph will just refer to this structure.
     50//     ///
     51//     /// \todo A pages describing the concept of concept description would
     52//     /// be nice.
     53//     class StaticGraph
     54//     {
     55//     public:
     56//       /// Defalult constructor.
     57
     58//       /// Defalult constructor.
     59//       ///
     60//       StaticGraph() { }
     61//       ///Copy consructor.
     62
     63// //       ///\todo It is not clear, what we expect from a copy constructor.
     64// //       ///E.g. How to assign the nodes/edges to each other? What about maps?
     65// //       StaticGraph(const StaticGraph& g) { }
     66
     67//       /// The base type of node iterators,
     68//       /// or in other words, the trivial node iterator.
     69
     70//       /// This is the base type of each node iterator,
     71//       /// thus each kind of node iterator converts to this.
     72//       /// More precisely each kind of node iterator should be inherited
     73//       /// from the trivial node iterator.
     74//       class Node {
     75//       public:
     76//      /// Default constructor
     77
     78//      /// @warning The default constructor sets the iterator
     79//      /// to an undefined value.
     80//      Node() { }
     81//      /// Copy constructor.
     82
     83//      /// Copy constructor.
     84//      ///
     85//      Node(const Node&) { }
     86
     87//      /// Invalid constructor \& conversion.
     88
     89//      /// This constructor initializes the iterator to be invalid.
     90//      /// \sa Invalid for more details.
     91//      Node(Invalid) { }
     92//      /// Equality operator
     93
     94//      /// Two iterators are equal if and only if they point to the
     95//      /// same object or both are invalid.
     96//      bool operator==(Node) const { return true; }
     97
     98//      /// Inequality operator
     99       
     100//      /// \sa operator==(Node n)
     101//      ///
     102//      bool operator!=(Node) const { return true; }
     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 NodeIt
     109//      ///goes through the nodes.
     110//      ///\todo Possibly we don't need it.
     111//      bool operator<(Node) const { return true; }
     112//       };
     113   
     114//       /// This iterator goes through each node.
     115
     116//       /// This iterator goes through each node.
     117//       /// Its usage is quite simple, for example you can count the number
     118//       /// of nodes in graph \c g of type \c Graph like this:
     119//       /// \code
     120//       /// int count=0;
     121//       /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
     122//       /// \endcode
     123//       class NodeIt : public Node {
     124//       public:
     125//      /// Default constructor
     126
     127//      /// @warning The default constructor sets the iterator
     128//      /// to an undefined value.
     129//      NodeIt() { }
     130//      /// Copy constructor.
     131       
     132//      /// Copy constructor.
     133//      ///
     134//      NodeIt(const NodeIt&) { }
     135//      /// Invalid constructor \& conversion.
     136
     137//      /// Initialize the iterator to be invalid.
     138//      /// \sa Invalid for more details.
     139//      NodeIt(Invalid) { }
     140//      /// Sets the iterator to the first node.
     141
     142//      /// Sets the iterator to the first node of \c g.
     143//      ///
     144//      NodeIt(const StaticGraph& g) { }
     145//      /// Node -> NodeIt conversion.
     146
     147//      /// Sets the iterator to the node of \c g pointed by the trivial
     148//      /// iterator n.
     149//      /// This feature necessitates that each time we
     150//      /// iterate the edge-set, the iteration order is the same.
     151//      NodeIt(const StaticGraph& g, const Node& n) { }
     152//      /// Next node.
     153
     154//      /// Assign the iterator to the next node.
     155//      ///
     156//      NodeIt& operator++() { return *this; }
     157//       };
     158   
     159   
     160//       /// The base type of the edge iterators.
     161
     162//       /// The base type of the edge iterators.
     163//       ///
     164//       class Edge {
     165//       public:
     166//      /// Default constructor
     167
     168//      /// @warning The default constructor sets the iterator
     169//      /// to an undefined value.
     170//      Edge() { }
     171//      /// Copy constructor.
     172
     173//      /// Copy constructor.
     174//      ///
     175//      Edge(const Edge&) { }
     176//      /// Initialize the iterator to be invalid.
     177
     178//      /// Initialize the iterator to be invalid.
     179//      ///
     180//      Edge(Invalid) { }
     181//      /// Equality operator
     182
     183//      /// Two iterators are equal if and only if they point to the
     184//      /// same object or both are invalid.
     185//      bool operator==(Edge) const { return true; }
     186//      /// Inequality operator
     187
     188//      /// \sa operator==(Node n)
     189//      ///
     190//      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; }
     199//       };
     200   
     201//       /// This iterator goes trough the outgoing edges of a node.
     202
     203//       /// This iterator goes trough the \e outgoing edges of a certain node
     204//       /// of a graph.
     205//       /// Its usage is quite simple, for example you can count the number
     206//       /// of outgoing edges of a node \c n
     207//       /// in graph \c g of type \c Graph as follows.
     208//       /// \code
     209//       /// int count=0;
     210//       /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     211//       /// \endcode
     212   
     213//       class OutEdgeIt : public Edge {
     214//       public:
     215//      /// Default constructor
     216
     217//      /// @warning The default constructor sets the iterator
     218//      /// to an undefined value.
     219//      OutEdgeIt() { }
     220//      /// Copy constructor.
     221
     222//      /// Copy constructor.
     223//      ///
     224//      OutEdgeIt(const OutEdgeIt&) { }
     225//      /// Initialize the iterator to be invalid.
     226
     227//      /// Initialize the iterator to be invalid.
     228//      ///
     229//      OutEdgeIt(Invalid) { }
     230//      /// This constructor sets the iterator to first outgoing edge.
     231   
     232//      /// This constructor set the iterator to the first outgoing edge of
     233//      /// node
     234//      ///@param n the node
     235//      ///@param g the graph
     236//      OutEdgeIt(const StaticGraph& g, const Node& n) { }
     237//      /// Edge -> OutEdgeIt conversion
     238
     239//      /// Sets the iterator to the value of the trivial iterator \c e.
     240//      /// This feature necessitates that each time we
     241//      /// iterate the edge-set, the iteration order is the same.
     242//      OutEdgeIt(const StaticGraph& g, const Edge& e) { }
     243//      ///Next outgoing edge
     244       
     245//      /// Assign the iterator to the next
     246//      /// outgoing edge of the corresponding node.
     247//      OutEdgeIt& operator++() { return *this; }
     248//       };
     249
     250//       /// This iterator goes trough the incoming edges of a node.
     251
     252//       /// This iterator goes trough the \e incoming edges of a certain node
     253//       /// of a graph.
     254//       /// Its usage is quite simple, for example you can count the number
     255//       /// of outgoing edges of a node \c n
     256//       /// in graph \c g of type \c Graph as follows.
     257//       /// \code
     258//       /// int count=0;
     259//       /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     260//       /// \endcode
     261
     262//       class InEdgeIt : public Edge {
     263//       public:
     264//      /// Default constructor
     265
     266//      /// @warning The default constructor sets the iterator
     267//      /// to an undefined value.
     268//      InEdgeIt() { }
     269//      /// Copy constructor.
     270
     271//      /// Copy constructor.
     272//      ///
     273//      InEdgeIt(const InEdgeIt&) { }
     274//      /// Initialize the iterator to be invalid.
     275
     276//      /// Initialize the iterator to be invalid.
     277//      ///
     278//      InEdgeIt(Invalid) { }
     279//      /// This constructor sets the iterator to first incoming edge.
     280   
     281//      /// This constructor set the iterator to the first incoming edge of
     282//      /// node
     283//      ///@param n the node
     284//      ///@param g the graph
     285//      InEdgeIt(const StaticGraph& g, const Node& n) { }
     286//      /// Edge -> InEdgeIt conversion
     287
     288//      /// Sets the iterator to the value of the trivial iterator \c e.
     289//      /// This feature necessitates that each time we
     290//      /// iterate the edge-set, the iteration order is the same.
     291//      InEdgeIt(const StaticGraph& g, const Edge& n) { }
     292//      /// Next incoming edge
     293
     294//      /// Assign the iterator to the next inedge of the corresponding node.
     295//      ///
     296//      InEdgeIt& operator++() { return *this; }
     297//       };
     298//       /// This iterator goes through each edge.
     299
     300//       /// This iterator goes through each edge of a graph.
     301//       /// Its usage is quite simple, for example you can count the number
     302//       /// of edges in a graph \c g of type \c Graph as follows:
     303//       /// \code
     304//       /// int count=0;
     305//       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
     306//       /// \endcode
     307//       class EdgeIt : public Edge {
     308//       public:
     309//      /// Default constructor
     310
     311//      /// @warning The default constructor sets the iterator
     312//      /// to an undefined value.
     313//      EdgeIt() { }
     314//      /// Copy constructor.
     315
     316//      /// Copy constructor.
     317//      ///
     318//      EdgeIt(const EdgeIt&) { }
     319//      /// Initialize the iterator to be invalid.
     320
     321//      /// Initialize the iterator to be invalid.
     322//      ///
     323//      EdgeIt(Invalid) { }
     324//      /// This constructor sets the iterator to first edge.
     325   
     326//      /// This constructor set the iterator to the first edge of
     327//      /// node
     328//      ///@param g the graph
     329//      EdgeIt(const StaticGraph& g) { }
     330//      /// Edge -> EdgeIt conversion
     331
     332//      /// Sets the iterator to the value of the trivial iterator \c e.
     333//      /// This feature necessitates that each time we
     334//      /// iterate the edge-set, the iteration order is the same.
     335//      EdgeIt(const StaticGraph&, const Edge&) { }
     336//      ///Next edge
     337       
     338//      /// Assign the iterator to the next
     339//      /// edge of the corresponding node.
     340//      EdgeIt& operator++() { return *this; }
     341//       };
     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 head node of an edge.
     367
     368//       ///Gives back the head node of an edge.
     369//       ///
     370//       Node head(Edge) const { return INVALID; }
     371//       ///Gives back the tail node of an edge.
     372
     373//       ///Gives back the tail node of an edge.
     374//       ///
     375//       Node tail(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.
     403
     404//       /// \ingroup skeletons
     405//       ///Reference map of the nodes to type \c T.
     406//       /// \sa Reference
     407//       /// \warning Making maps that can handle bool type (NodeMap<bool>)
     408//       /// needs some extra attention!
     409//       template<class T> class NodeMap : public ReferenceMap< Node, T >
     410//       {
     411//       public:
     412
     413//      ///\e
     414//      NodeMap(const StaticGraph&) { }
     415//      ///\e
     416//      NodeMap(const StaticGraph&, T) { }
     417
     418//      ///Copy constructor
     419//      template<typename TT> NodeMap(const NodeMap<TT>&) { }
     420//      ///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.
     426
     427//       /// \ingroup skeletons
     428//       ///Reference map of the edges to type \c T.
     429//       /// \sa Reference
     430//       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
     431//       /// needs some extra attention!
     432//       template<class T> class EdgeMap
     433//      : public ReferenceMap<Edge,T>
     434//       {
     435//       public:
     436
     437//      ///\e
     438//      EdgeMap(const StaticGraph&) { }
     439//      ///\e
     440//      EdgeMap(const StaticGraph&, T) { }
     441   
     442//      ///Copy constructor
     443//      template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
     444//      ///Assignment operator
     445//      template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
     446//      { return *this; }
     447//       };
     448//     };
     449
     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::skeleton::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.tail(e);
     542//      n=G.head(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>::ValueType val;
     571//        val=1;
     572//        typename Graph::template NodeMap<int>::KeyType 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>::ValueType val;
     595//        val=true;
     596//        typename Graph::template NodeMap<bool>::KeyType 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>::ValueType val;
     618//        val=1;
     619//        typename Graph::template EdgeMap<int>::KeyType 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>::ValueType val;
     641//        val=true;
     642//        typename Graph::template EdgeMap<bool>::KeyType key;
     643//        key= typename Graph::EdgeIt(G);
     644//      }
     645//       }
     646//     }
     647   
     648//     /// An empty non-static graph class.
     649   
     650//     /// This class provides everything that \ref StaticGraph
     651//     /// with additional functionality which enables to build a
     652//     /// graph from scratch.
     653//     class ExtendableGraph : public StaticGraph
     654//     {
     655//     public:
     656//       /// Defalult constructor.
     657
     658//       /// Defalult constructor.
     659//       ///
     660//       ExtendableGraph() { }
     661//       ///Add a new node to the graph.
     662
     663//       /// \return the new node.
     664//       ///
     665//       Node addNode() { return INVALID; }
     666//       ///Add a new edge to the graph.
     667
     668//       ///Add a new edge to the graph with tail node \c t
     669//       ///and head node \c h.
     670//       ///\return the new edge.
     671//       Edge addEdge(Node h, Node t) { return INVALID; }
     672   
     673//       /// Resets the graph.
     674
     675//       /// This function deletes all edges and nodes of the graph.
     676//       /// It also frees the memory allocated to store them.
     677//       /// \todo It might belong to \ref ErasableGraph.
     678//       void clear() { }
     679//     };
     680
     681   
     682//     ///\brief Checks whether \c G meets the
     683//     ///\ref lemon::skeleton::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
     704
     705//     /// An empty erasable graph class.
     706 
     707//     /// This class is an extension of \ref ExtendableGraph. It also makes it
     708//     /// possible to erase edges or nodes.
     709//     class ErasableGraph : public ExtendableGraph
     710//     {
     711//     public:
     712//       /// Defalult constructor.
     713
     714//       /// Defalult constructor.
     715//       ///
     716//       ErasableGraph() { }
     717//       /// Deletes a node.
     718
     719//       /// Deletes node \c n node.
     720//       ///
     721//       void erase(Node n) { }
     722//       /// Deletes an edge.
     723
     724//       /// Deletes edge \c e edge.
     725//       ///
     726//       void erase(Edge e) { }
     727//     };
     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::skeleton::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
     765    /************* New GraphBase stuff **************/
     766
     767
     768    /// \bug The nodes and edges are not allowed to inherit from the
     769    /// same baseclass.
     770
     771    class BaseGraphItem {
    53772    public:
    54       /// Defalult constructor.
    55 
    56       /// Defalult constructor.
    57       ///
    58       StaticGraph() { }
    59       ///Copy consructor.
    60 
    61 //       ///\todo It is not clear, what we expect from a copy constructor.
    62 //       ///E.g. How to assign the nodes/edges to each other? What about maps?
    63 //       StaticGraph(const StaticGraph& g) { }
    64 
    65       /// The base type of node iterators,
    66       /// or in other words, the trivial node iterator.
    67 
    68       /// This is the base type of each node iterator,
    69       /// thus each kind of node iterator converts to this.
    70       /// More precisely each kind of node iterator should be inherited
    71       /// from the trivial node iterator.
    72       class Node {
    73       public:
    74         /// Default constructor
    75 
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
    78         Node() { }
    79         /// Copy constructor.
    80 
    81         /// Copy constructor.
    82         ///
    83         Node(const Node&) { }
    84 
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
    88         /// \sa Invalid for more details.
    89         Node(Invalid) { }
    90         /// Equality operator
    91 
    92         /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
    94         bool operator==(Node) const { return true; }
    95 
    96         /// Inequality operator
     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    /// A minimal GraphBase concept
     789
     790    /// This class describes a minimal concept which can be extended to a
     791    /// full-featured graph with \ref GraphFactory.
     792    class GraphBase {
     793    public:
     794
     795      GraphBase() {}
     796
     797
     798      /// \bug Nodes and Edges are comparable each other
     799     
     800      class Node : public BaseGraphItem {};
     801      class Edge : public BaseGraphItem {};
     802
     803      // Graph operation
     804      void firstNode(Node &n) const { }
     805      void firstEdge(Edge &e) const { }
     806
     807      void firstOutEdge(Edge &e, Node) const { }
     808      void firstInEdge(Edge &e, Node) const { }
     809
     810      void nextNode(Node &n) const { }
     811      void nextEdge(Edge &e) const { }
     812
     813
     814      // Question: isn't it reasonable if this methods have a Node
     815      // parameter? Like this:
     816      // Edge& nextOut(Edge &e, Node) const { return e; }
     817      void nextOutEdge(Edge &e) const { }
     818      void nextInEdge(Edge &e) const { }
     819
     820      Node head(Edge) const { return Node(); }
     821      Node tail(Edge) const { return Node(); }
     822     
     823
     824      // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
     825      // concept?
     826
     827
     828      // Maps.
     829      //
     830      // We need a special slimer concept which does not provide maps (it
     831      // wouldn't be strictly slimer, cause for map-factory id() & friends
     832      // a required...)
     833
     834      template<typename T>
     835      class NodeMap : public GraphMap<Node, T, GraphBase> {};
     836
     837      template<typename T>
     838      class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
     839    };
     840
     841
     842
     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;
    97851       
    98         /// \sa operator==(Node n)
    99         ///
    100         bool operator!=(Node) const { return true; }
    101 
    102         ///Comparison operator.
    103 
    104         ///This is a strict ordering between the nodes.
    105         ///
    106         ///This ordering can be different from the order in which NodeIt
    107         ///goes through the nodes.
    108         ///\todo Possibly we don't need it.
    109         bool operator<(Node) const { return true; }
    110       };
    111    
    112       /// This iterator goes through each node.
    113 
    114       /// This iterator goes through each node.
    115       /// Its usage is quite simple, for example you can count the number
    116       /// of nodes in graph \c g of type \c Graph like this:
    117       /// \code
    118       /// int count=0;
    119       /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
    120       /// \endcode
    121       class NodeIt : public Node {
    122       public:
    123         /// Default constructor
    124 
    125         /// @warning The default constructor sets the iterator
    126         /// to an undefined value.
    127         NodeIt() { }
    128         /// Copy constructor.
    129        
    130         /// Copy constructor.
    131         ///
    132         NodeIt(const NodeIt&) { }
    133         /// Invalid constructor \& conversion.
    134 
    135         /// Initialize the iterator to be invalid.
    136         /// \sa Invalid for more details.
    137         NodeIt(Invalid) { }
    138         /// Sets the iterator to the first node.
    139 
    140         /// Sets the iterator to the first node of \c g.
    141         ///
    142         NodeIt(const StaticGraph& g) { }
    143         /// Node -> NodeIt conversion.
    144 
    145         /// Sets the iterator to the node of \c g pointed by the trivial
    146         /// iterator n.
    147         /// This feature necessitates that each time we
    148         /// iterate the edge-set, the iteration order is the same.
    149         NodeIt(const StaticGraph& g, const Node& n) { }
    150         /// Next node.
    151 
    152         /// Assign the iterator to the next node.
    153         ///
    154         NodeIt& operator++() { return *this; }
    155       };
    156    
    157    
    158       /// The base type of the edge iterators.
    159 
    160       /// The base type of the edge iterators.
    161       ///
    162       class Edge {
    163       public:
    164         /// Default constructor
    165 
    166         /// @warning The default constructor sets the iterator
    167         /// to an undefined value.
    168         Edge() { }
    169         /// Copy constructor.
    170 
    171         /// Copy constructor.
    172         ///
    173         Edge(const Edge&) { }
    174         /// Initialize the iterator to be invalid.
    175 
    176         /// Initialize the iterator to be invalid.
    177         ///
    178         Edge(Invalid) { }
    179         /// Equality operator
    180 
    181         /// Two iterators are equal if and only if they point to the
    182         /// same object or both are invalid.
    183         bool operator==(Edge) const { return true; }
    184         /// Inequality operator
    185 
    186         /// \sa operator==(Node n)
    187         ///
    188         bool operator!=(Edge) const { return true; }
    189         ///Comparison operator.
    190 
    191         ///This is a strict ordering between the nodes.
    192         ///
    193         ///This ordering can be different from the order in which NodeIt
    194         ///goes through the nodes.
    195         ///\todo Possibly we don't need it.
    196         bool operator<(Edge) const { return true; }
    197       };
    198    
    199       /// This iterator goes trough the outgoing edges of a node.
    200 
    201       /// This iterator goes trough the \e outgoing edges of a certain node
    202       /// of a graph.
    203       /// Its usage is quite simple, for example you can count the number
    204       /// of outgoing edges of a node \c n
    205       /// in graph \c g of type \c Graph as follows.
    206       /// \code
    207       /// int count=0;
    208       /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    209       /// \endcode
    210    
    211       class OutEdgeIt : public Edge {
    212       public:
    213         /// Default constructor
    214 
    215         /// @warning The default constructor sets the iterator
    216         /// to an undefined value.
    217         OutEdgeIt() { }
    218         /// Copy constructor.
    219 
    220         /// Copy constructor.
    221         ///
    222         OutEdgeIt(const OutEdgeIt&) { }
    223         /// Initialize the iterator to be invalid.
    224 
    225         /// Initialize the iterator to be invalid.
    226         ///
    227         OutEdgeIt(Invalid) { }
    228         /// This constructor sets the iterator to first outgoing edge.
    229    
    230         /// This constructor set the iterator to the first outgoing edge of
    231         /// node
    232         ///@param n the node
    233         ///@param g the graph
    234         OutEdgeIt(const StaticGraph& g, const Node& n) { }
    235         /// Edge -> OutEdgeIt conversion
    236 
    237         /// Sets the iterator to the value of the trivial iterator \c e.
    238         /// This feature necessitates that each time we
    239         /// iterate the edge-set, the iteration order is the same.
    240         OutEdgeIt(const StaticGraph& g, const Edge& e) { }
    241         ///Next outgoing edge
    242        
    243         /// Assign the iterator to the next
    244         /// outgoing edge of the corresponding node.
    245         OutEdgeIt& operator++() { return *this; }
    246       };
    247 
    248       /// This iterator goes trough the incoming edges of a node.
    249 
    250       /// This iterator goes trough the \e incoming edges of a certain node
    251       /// of a graph.
    252       /// Its usage is quite simple, for example you can count the number
    253       /// of outgoing edges of a node \c n
    254       /// in graph \c g of type \c Graph as follows.
    255       /// \code
    256       /// int count=0;
    257       /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    258       /// \endcode
    259 
    260       class InEdgeIt : public Edge {
    261       public:
    262         /// Default constructor
    263 
    264         /// @warning The default constructor sets the iterator
    265         /// to an undefined value.
    266         InEdgeIt() { }
    267         /// Copy constructor.
    268 
    269         /// Copy constructor.
    270         ///
    271         InEdgeIt(const InEdgeIt&) { }
    272         /// Initialize the iterator to be invalid.
    273 
    274         /// Initialize the iterator to be invalid.
    275         ///
    276         InEdgeIt(Invalid) { }
    277         /// This constructor sets the iterator to first incoming edge.
    278    
    279         /// This constructor set the iterator to the first incoming edge of
    280         /// node
    281         ///@param n the node
    282         ///@param g the graph
    283         InEdgeIt(const StaticGraph& g, const Node& n) { }
    284         /// Edge -> InEdgeIt conversion
    285 
    286         /// Sets the iterator to the value of the trivial iterator \c e.
    287         /// This feature necessitates that each time we
    288         /// iterate the edge-set, the iteration order is the same.
    289         InEdgeIt(const StaticGraph& g, const Edge& n) { }
    290         /// Next incoming edge
    291 
    292         /// Assign the iterator to the next inedge of the corresponding node.
    293         ///
    294         InEdgeIt& operator++() { return *this; }
    295       };
    296       /// This iterator goes through each edge.
    297 
    298       /// This iterator goes through each edge of a graph.
    299       /// Its usage is quite simple, for example you can count the number
    300       /// of edges in a graph \c g of type \c Graph as follows:
    301       /// \code
    302       /// int count=0;
    303       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
    304       /// \endcode
    305       class EdgeIt : public Edge {
    306       public:
    307         /// Default constructor
    308 
    309         /// @warning The default constructor sets the iterator
    310         /// to an undefined value.
    311         EdgeIt() { }
    312         /// Copy constructor.
    313 
    314         /// Copy constructor.
    315         ///
    316         EdgeIt(const EdgeIt&) { }
    317         /// Initialize the iterator to be invalid.
    318 
    319         /// Initialize the iterator to be invalid.
    320         ///
    321         EdgeIt(Invalid) { }
    322         /// This constructor sets the iterator to first edge.
    323    
    324         /// This constructor set the iterator to the first edge of
    325         /// node
    326         ///@param g the graph
    327         EdgeIt(const StaticGraph& g) { }
    328         /// Edge -> EdgeIt conversion
    329 
    330         /// Sets the iterator to the value of the trivial iterator \c e.
    331         /// This feature necessitates that each time we
    332         /// iterate the edge-set, the iteration order is the same.
    333         EdgeIt(const StaticGraph&, const Edge&) { }
    334         ///Next edge
    335        
    336         /// Assign the iterator to the next
    337         /// edge of the corresponding node.
    338         EdgeIt& operator++() { return *this; }
    339       };
    340 
    341       /// First node of the graph.
    342 
    343       /// \retval i the first node.
    344       /// \return the first node.
    345       ///
    346       NodeIt& first(NodeIt& i) const { return i; }
    347 
    348       /// The first incoming edge.
    349 
    350       /// The first incoming edge.
    351       ///
    352       InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
    353       /// The first outgoing edge.
    354 
    355       /// The first outgoing edge.
    356       ///
    357       OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
    358       /// The first edge of the Graph.
    359 
    360       /// The first edge of the Graph.
    361       ///
    362       EdgeIt& first(EdgeIt& i) const { return i; }
    363 
    364       ///Gives back the head node of an edge.
    365 
    366       ///Gives back the head node of an edge.
    367       ///
    368       Node head(Edge) const { return INVALID; }
    369       ///Gives back the tail node of an edge.
    370 
    371       ///Gives back the tail node of an edge.
    372       ///
    373       Node tail(Edge) const { return INVALID; }
    374  
    375       ///Gives back the \e id of a node.
    376 
    377       ///\warning Not all graph structures provide this feature.
    378       ///
    379       ///\todo Should each graph provide \c id?
    380       int id(const Node&) const { return 0; }
    381       ///Gives back the \e id of an edge.
    382 
    383       ///\warning Not all graph structures provide this feature.
    384       ///
    385       ///\todo Should each graph provide \c id?
    386       int id(const Edge&) const { return 0; }
    387 
    388       ///\e
    389      
    390       ///\todo Should it be in the concept?
    391       ///
    392       int nodeNum() const { return 0; }
    393       ///\e
    394 
    395       ///\todo Should it be in the concept?
    396       ///
    397       int edgeNum() const { return 0; }
    398 
    399 
    400       ///Reference map of the nodes to type \c T.
    401 
    402       /// \ingroup skeletons
    403       ///Reference map of the nodes to type \c T.
    404       /// \sa Reference
    405       /// \warning Making maps that can handle bool type (NodeMap<bool>)
    406       /// needs some extra attention!
    407       template<class T> class NodeMap : public ReferenceMap< Node, T >
    408       {
    409       public:
    410 
    411         ///\e
    412         NodeMap(const StaticGraph&) { }
    413         ///\e
    414         NodeMap(const StaticGraph&, T) { }
    415 
    416         ///Copy constructor
    417         template<typename TT> NodeMap(const NodeMap<TT>&) { }
    418         ///Assignment operator
    419         template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
    420         { return *this; }
    421       };
    422 
    423       ///Reference map of the edges to type \c T.
    424 
    425       /// \ingroup skeletons
    426       ///Reference map of the edges to type \c T.
    427       /// \sa Reference
    428       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
    429       /// needs some extra attention!
    430       template<class T> class EdgeMap
    431         : public ReferenceMap<Edge,T>
    432       {
    433       public:
    434 
    435         ///\e
    436         EdgeMap(const StaticGraph&) { }
    437         ///\e
    438         EdgeMap(const StaticGraph&, T) { }
    439    
    440         ///Copy constructor
    441         template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
    442         ///Assignment operator
    443         template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
    444         { return *this; }
    445       };
    446     };
    447 
    448     struct DummyType {
    449       int value;
    450       DummyType() {}
    451       DummyType(int p) : value(p) {}
    452       DummyType& operator=(int p) { value = p; return *this;}
    453     };
    454    
    455     ///\brief Checks whether \c G meets the
    456     ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
    457     template<class Graph> void checkCompileStaticGraph(Graph &G)
    458     {
    459       typedef typename Graph::Node Node;
    460       typedef typename Graph::NodeIt NodeIt;
    461       typedef typename Graph::Edge Edge;
    462       typedef typename Graph::EdgeIt EdgeIt;
    463       typedef typename Graph::InEdgeIt InEdgeIt;
    464       typedef typename Graph::OutEdgeIt OutEdgeIt;
    465  
    466       {
    467         Node i; Node j(i); Node k(INVALID);
    468         i=j;
    469         bool b; b=true;
    470         b=(i==INVALID); b=(i!=INVALID);
    471         b=(i==j); b=(i!=j); b=(i<j);
    472       }
    473       {
    474         NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
    475         i=j;
    476         j=G.first(i);
    477         j=++i;
    478         bool b; b=true;
    479         b=(i==INVALID); b=(i!=INVALID);
    480         Node n(i);
    481         n=i;
    482         b=(i==j); b=(i!=j); b=(i<j);
    483         //Node ->NodeIt conversion
    484         NodeIt ni(G,n);
    485       }
    486       {
    487         Edge i; Edge j(i); Edge k(INVALID);
    488         i=j;
    489         bool b; b=true;
    490         b=(i==INVALID); b=(i!=INVALID);
    491         b=(i==j); b=(i!=j); b=(i<j);
    492       }
    493       {
    494         EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
    495         i=j;
    496         j=G.first(i);
    497         j=++i;
    498         bool b; b=true;
    499         b=(i==INVALID); b=(i!=INVALID);
    500         Edge e(i);
    501         e=i;
    502         b=(i==j); b=(i!=j); b=(i<j);
    503         //Edge ->EdgeIt conversion
    504         EdgeIt ei(G,e);
    505       }
    506       {
    507         Node n;
    508         InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
    509         i=j;
    510         j=G.first(i,n);
    511         j=++i;
    512         bool b; b=true;
    513         b=(i==INVALID); b=(i!=INVALID);
    514         Edge e(i);
    515         e=i;
    516         b=(i==j); b=(i!=j); b=(i<j);
    517         //Edge ->InEdgeIt conversion
    518         InEdgeIt ei(G,e);
    519       }
    520       {
    521         Node n;
    522         OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
    523         i=j;
    524         j=G.first(i,n);
    525         j=++i;
    526         bool b; b=true;
    527         b=(i==INVALID); b=(i!=INVALID);
    528         Edge e(i);
    529         e=i;
    530         b=(i==j); b=(i!=j); b=(i<j);
    531         //Edge ->OutEdgeIt conversion
    532         OutEdgeIt ei(G,e);
    533       }
    534       {
    535         Node n,m;
    536         n=m=INVALID;
    537         Edge e;
    538         e=INVALID;
    539         n=G.tail(e);
    540         n=G.head(e);
    541       }
    542       // id tests
    543       { Node n; int i=G.id(n); i=i; }
    544       { Edge e; int i=G.id(e); i=i; }
    545       //NodeMap tests
    546       {
    547         Node k;
    548         typename Graph::template NodeMap<int> m(G);
    549         //Const map
    550         typename Graph::template NodeMap<int> const &cm = m;
    551         //Inicialize with default value
    552         typename Graph::template NodeMap<int> mdef(G,12);
    553         //Copy
    554         typename Graph::template NodeMap<int> mm(cm);
    555         //Copy from another type
    556         typename Graph::template NodeMap<double> dm(cm);
    557         //Copy to more complex type
    558         typename Graph::template NodeMap<DummyType> em(cm);
    559         int v;
    560         v=m[k]; m[k]=v; m.set(k,v);
    561         v=cm[k];
    562    
    563         m=cm; 
    564         dm=cm; //Copy from another type 
    565         em=cm; //Copy to more complex type
    566         {
    567           //Check the typedef's
    568           typename Graph::template NodeMap<int>::ValueType val;
    569           val=1;
    570           typename Graph::template NodeMap<int>::KeyType key;
    571           key = typename Graph::NodeIt(G);
    572         }
    573       } 
    574       { //bool NodeMap
    575         Node k;
    576         typename Graph::template NodeMap<bool> m(G);
    577         typename Graph::template NodeMap<bool> const &cm = m;  //Const map
    578         //Inicialize with default value
    579         typename Graph::template NodeMap<bool> mdef(G,12);
    580         typename Graph::template NodeMap<bool> mm(cm);   //Copy
    581         typename Graph::template NodeMap<int> dm(cm); //Copy from another type
    582         bool v;
    583         v=m[k]; m[k]=v; m.set(k,v);
    584         v=cm[k];
    585    
    586         m=cm; 
    587         dm=cm; //Copy from another type
    588         m=dm; //Copy to another type
    589 
    590         {
    591           //Check the typedef's
    592           typename Graph::template NodeMap<bool>::ValueType val;
    593           val=true;
    594           typename Graph::template NodeMap<bool>::KeyType key;
    595           key= typename Graph::NodeIt(G);
     852        i1 = i3;
     853        if( i1 == i3 ) {
     854          if ( i2 != i3 && i3 < i2 )
     855            return;
    596856        }
    597857      }
    598       //EdgeMap tests
    599       {
    600         Edge k;
    601         typename Graph::template EdgeMap<int> m(G);
    602         typename Graph::template EdgeMap<int> const &cm = m;  //Const map
    603         //Inicialize with default value
    604         typename Graph::template EdgeMap<int> mdef(G,12);
    605         typename Graph::template EdgeMap<int> mm(cm);   //Copy
    606         typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
    607         int v;
    608         v=m[k]; m[k]=v; m.set(k,v);
    609         v=cm[k];
    610    
    611         m=cm; 
    612         dm=cm; //Copy from another type
    613         {
    614           //Check the typedef's
    615           typename Graph::template EdgeMap<int>::ValueType val;
    616           val=1;
    617           typename Graph::template EdgeMap<int>::KeyType key;
    618           key= typename Graph::EdgeIt(G);
    619         }
    620       } 
    621       { //bool EdgeMap
    622         Edge k;
    623         typename Graph::template EdgeMap<bool> m(G);
    624         typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
    625         //Inicialize with default value
    626         typename Graph::template EdgeMap<bool> mdef(G,12);
    627         typename Graph::template EdgeMap<bool> mm(cm);   //Copy
    628         typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
    629         bool v;
    630         v=m[k]; m[k]=v; m.set(k,v);
    631         v=cm[k];
    632    
    633         m=cm; 
    634         dm=cm; //Copy from another type
    635         m=dm; //Copy to another type
    636         {
    637           //Check the typedef's
    638           typename Graph::template EdgeMap<bool>::ValueType val;
    639           val=true;
    640           typename Graph::template EdgeMap<bool>::KeyType key;
    641           key= typename Graph::EdgeIt(G);
    642         }
     858    };
     859
     860   
     861   
     862    class StaticGraph
     863      :  virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
     864    public:
     865      typedef BaseGraphComponent::Node Node;
     866      typedef BaseGraphComponent::Edge Edge;
     867    };
     868
     869    template <typename Graph>
     870    struct StaticGraphConcept {
     871      void constraints() {
     872        function_requires<BaseGraphComponentConcept<Graph> >();
     873        function_requires<IterableGraphComponentConcept<Graph> >();
     874        function_requires<MappableGraphComponentConcept<Graph> >();
    643875      }
    644     }
    645    
    646     /// An empty non-static graph class.
    647    
    648     /// This class provides everything that \ref StaticGraph
    649     /// with additional functionality which enables to build a
    650     /// graph from scratch.
    651     class ExtendableGraph : public StaticGraph
    652     {
     876      Graph& graph;
     877    };
     878
     879    class ExtendableGraph
     880      :  virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
    653881    public:
    654       /// Defalult constructor.
    655 
    656       /// Defalult constructor.
    657       ///
    658       ExtendableGraph() { }
    659       ///Add a new node to the graph.
    660 
    661       /// \return the new node.
    662       ///
    663       Node addNode() { return INVALID; }
    664       ///Add a new edge to the graph.
    665 
    666       ///Add a new edge to the graph with tail node \c t
    667       ///and head node \c h.
    668       ///\return the new edge.
    669       Edge addEdge(Node h, Node t) { return INVALID; }
    670    
    671       /// Resets the graph.
    672 
    673       /// This function deletes all edges and nodes of the graph.
    674       /// It also frees the memory allocated to store them.
    675       /// \todo It might belong to \ref ErasableGraph.
    676       void clear() { }
     882      typedef BaseGraphComponent::Node Node;
     883      typedef BaseGraphComponent::Edge Edge;
    677884    };
    678885
    679    
    680     ///\brief Checks whether \c G meets the
    681     ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
    682     template<class Graph> void checkCompileExtendableGraph(Graph &G)
    683     {
    684       checkCompileStaticGraph(G);
    685 
    686       typedef typename Graph::Node Node;
    687       typedef typename Graph::NodeIt NodeIt;
    688       typedef typename Graph::Edge Edge;
    689       typedef typename Graph::EdgeIt EdgeIt;
    690       typedef typename Graph::InEdgeIt InEdgeIt;
    691       typedef typename Graph::OutEdgeIt OutEdgeIt;
    692  
    693       Node n,m;
    694       n=G.addNode();
    695       m=G.addNode();
    696       Edge e;
    697       e=G.addEdge(n,m);
    698  
    699       //  G.clear();
    700     }
    701 
    702 
    703     /// An empty erasable graph class.
    704  
    705     /// This class is an extension of \ref ExtendableGraph. It also makes it
    706     /// possible to erase edges or nodes.
    707     class ErasableGraph : public ExtendableGraph
    708     {
     886    template <typename Graph>
     887    struct ExtendableGraphConcept {
     888      void constraints() {
     889        function_requires<StaticGraphConcept<Graph> >();
     890        function_requires<ExtendableGraphComponentConcept<Graph> >();
     891        function_requires<ClearableGraphComponentConcept<Graph> >();
     892      }
     893      Graph& graph;
     894    };
     895
     896    class ErasableGraph
     897      :  virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
    709898    public:
    710       /// Defalult constructor.
    711 
    712       /// Defalult constructor.
    713       ///
    714       ErasableGraph() { }
    715       /// Deletes a node.
    716 
    717       /// Deletes node \c n node.
    718       ///
    719       void erase(Node n) { }
    720       /// Deletes an edge.
    721 
    722       /// Deletes edge \c e edge.
    723       ///
    724       void erase(Edge e) { }
     899      typedef BaseGraphComponent::Node Node;
     900      typedef BaseGraphComponent::Edge Edge;
    725901    };
    726    
    727     template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
    728     {
    729       typename Graph::Edge e;
    730       G.erase(e);
    731     }
    732 
    733     template<class Graph> void checkCompileGraphEraseNode(Graph &G)
    734     {
    735       typename Graph::Node n;
    736       G.erase(n);
    737     }
    738 
    739     ///\brief Checks whether \c G meets the
    740     ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
    741     template<class Graph> void checkCompileErasableGraph(Graph &G)
    742     {
    743       checkCompileExtendableGraph(G);
    744       checkCompileGraphEraseNode(G);
    745       checkCompileGraphEraseEdge(G);
    746     }
    747 
    748     ///Checks whether a graph has findEdge() member function.
    749    
    750     ///\todo findEdge() might be a global function.
    751     ///
    752     template<class Graph> void checkCompileGraphFindEdge(Graph &G)
    753     {
    754       typedef typename Graph::NodeIt Node;
    755       typedef typename Graph::NodeIt NodeIt;
    756 
    757       G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
    758       G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 
    759     }
    760  
     902
     903    template <typename Graph>
     904    struct ErasableGraphConcept {
     905      void constraints() {
     906        function_requires<ExtendableGraphConcept<Graph> >();
     907        function_requires<ErasableGraphComponentConcept<Graph> >();
     908      }
     909      Graph& graph;
     910    };
     911
    761912    // @}
    762913  } //namespace skeleton 
  • src/lemon/skeletons/maps.h

    r921 r946  
    1717#ifndef LEMON_MAPSKELETON_H
    1818#define LEMON_MAPSKELETON_H
     19
     20#include <lemon/concept_check.h>
    1921
    2022///\ingroup skeletons
     
    114116    };
    115117
     118
     119    template<typename Item, typename T, typename Graph>
     120    class GraphMap : public ReadWriteMap<Item, T> {
     121      // I really, really don't like the idea that every graph should have
     122      // reference maps! --klao
     123
     124    private:
     125      // We state explicitly that graph maps have no default constructor?
     126      GraphMap();
     127
     128    public:
     129      explicit GraphMap(Graph const&) {}
     130      // value for initializing
     131      GraphMap(Graph const&, T) {}
     132
     133      // this probably should be required:
     134      GraphMap(GraphMap const&) {}
     135      GraphMap& operator=(GraphMap const&) { return *this; }
     136
     137      // but this is a absolute no-op! We should provide a more generic
     138      // graph-map-copy operation.
     139      //
     140      // template<typename TT>
     141      // GraphMap(GraphMap<TT> const&);
     142      //
     143      // template<typename TT>
     144      // GraphMap& operator=(const GraphMap<TT>&);
     145    };
     146
     147
     148    /****************  Concept-checking classes  ****************/
     149
     150    template<typename ReadMap>
     151    struct ReadMapConcept {
     152      typedef typename ReadMap::KeyType KeyType;
     153      typedef typename ReadMap::ValueType ValueType;
     154
     155      void constraints() {
     156        // No constraints for constructor.
     157
     158        // What are the requirement for the ValueType?
     159        // CopyConstructible? Assignable? None of these?
     160        ValueType v = m[k];
     161        v = m[k];
     162
     163        // FIXME:
     164        ignore_unused_variable_warning(v);
     165      }
     166
     167      ReadMap m;
     168      KeyType k;
     169    };
     170
     171    template<typename WriteMap>
     172    struct WriteMapConcept {
     173      typedef typename WriteMap::KeyType KeyType;
     174      typedef typename WriteMap::ValueType ValueType;
     175
     176      void constraints() {
     177        // No constraints for constructor.
     178
     179        m.set(k, v);
     180      }
     181
     182      WriteMap m;
     183      KeyType k;
     184      ValueType v;
     185    };
     186
     187    template<typename ReadWriteMap>
     188    struct ReadWriteMapConcept {
     189      void constraints() {
     190        function_requires< ReadMapConcept<ReadWriteMap> >();
     191        function_requires< WriteMapConcept<ReadWriteMap> >();
     192      }
     193    };
     194
     195    template<typename ReferenceMap>
     196    struct ReferenceMapConcept {
     197      typedef typename ReferenceMap::KeyType KeyType;
     198      typedef typename ReferenceMap::ValueType ValueType;
     199      typedef typename ReferenceMap::ReferenceType ReferenceType;
     200
     201      // What for is this?
     202      typedef typename ReferenceMap::ConstReferenceType ConstReferenceType;
     203
     204      void constraints() {
     205        function_requires< ReadWriteMapConcept<ReferenceMap> >();
     206
     207        m[k] = v;
     208        // Or should we require real reference?
     209        // Like this:
     210        // ValueType &vv = m[k];
     211        // ignore_unused_variable_warning(vv);
     212      }
     213
     214      ReferenceMap m;
     215      KeyType k;
     216      ValueType v;
     217    };
     218
     219    /// \todo GraphMapConceptCheck
     220
     221    template<typename GraphMap, typename Graph>
     222    struct GraphMapConcept {
     223      void constraints() {
     224        function_requires< ReadWriteMapConcept<GraphMap> >();
     225        // Construction with a graph parameter
     226        GraphMap a(g);
     227        // Ctor with a graph and a default value parameter
     228        GraphMap a2(g,t);
     229        // Copy ctor. Do we need it?
     230        GraphMap b=c;
     231        // Copy operator. Do we need it?
     232        a=b;
     233
     234        ignore_unused_variable_warning(a2);
     235      }
     236      const GraphMap &c;
     237      const Graph &g;
     238      const typename GraphMap::ValueType &t;
     239    };
     240   
     241
    116242    // @}
    117243
Note: See TracChangeset for help on using the changeset viewer.