COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/skeletons/graph.h @ 948:bc86b64f958e

Last change on this file since 948:bc86b64f958e was 946:c94ef40a22ce, checked in by Mihaly Barasz, 16 years ago

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

File size: 26.2 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/skeletons/graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_SKELETON_GRAPH_H
18#define LEMON_SKELETON_GRAPH_H
19
20///\ingroup skeletons
21///\file
22///\brief Declaration of Graph.
23
24#include <lemon/invalid.h>
25#include <lemon/skeletons/maps.h>
26#include <lemon/concept_check.h>
27#include <lemon/skeletons/graph_component.h>
28
29namespace lemon {
30  namespace skeleton {
31   
32    /// \addtogroup skeletons
33    /// @{
34
35//     /// An empty static graph class.
36 
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 {
772    public:
773      BaseGraphItem() {}
774      BaseGraphItem(Invalid) {}
775
776      // We explicitely list these:
777      BaseGraphItem(BaseGraphItem const&) {}
778      BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
779
780      bool operator==(BaseGraphItem) const { return false; }
781      bool operator!=(BaseGraphItem) const { return false; }
782
783      // Technical requirement. Do we really need this?
784      bool operator<(BaseGraphItem) const { return false; }
785    };
786
787
788    /// 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;
851       
852        i1 = i3;
853        if( i1 == i3 ) {
854          if ( i2 != i3 && i3 < i2 )
855            return;
856        }
857      }
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> >();
875      }
876      Graph& graph;
877    };
878
879    class ExtendableGraph
880      :  virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
881    public:
882      typedef BaseGraphComponent::Node Node;
883      typedef BaseGraphComponent::Edge Edge;
884    };
885
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 {
898    public:
899      typedef BaseGraphComponent::Node Node;
900      typedef BaseGraphComponent::Edge Edge;
901    };
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
912    // @}
913  } //namespace skeleton 
914} //namespace lemon
915
916
917
918#endif // LEMON_SKELETON_GRAPH_H
Note: See TracBrowser for help on using the repository browser.