src/work/marci/graph_concept.h
author athos
Tue, 11 May 2004 16:38:17 +0000
changeset 611 83530dad618a
parent 333 e0a80761dfd9
child 651 a56e043aeab1
permissions -rw-r--r--
Some modifications and another testfile.
     1 // -*- c++ -*-
     2 #ifndef HUGO_GRAPH_H
     3 #define HUGO_GRAPH_H
     4 
     5 ///\file
     6 ///\brief Declaration of GraphSkeleturo.
     7 
     8 #include <invalid.h>
     9 
    10 /// The namespace of HugoLib
    11 namespace hugo {
    12 
    13   /// @defgroup empty_graph The GraphSkeleturo class
    14   /// @{
    15 
    16   /// An empty graph class.
    17   
    18   /// This class provides all the common features of a graph structure,
    19   /// however completely without implementations and real data structures
    20   /// behind the interface.
    21   /// All graph algorithms should compile with this class, but it will not
    22   /// run properly, of course.
    23   ///
    24   /// It can be used for checking the interface compatibility,
    25   /// or it can serve as a skeleton of a new graph structure.
    26   /// 
    27   /// Also, you will find here the full documentation of a certain graph
    28   /// feature, the documentation of a real graph imlementation
    29   /// like @ref ListGraph or
    30   /// @ref SmartGraph will just refer to this structure.
    31   class GraphSkeleturo
    32   {
    33   public:
    34     /// Defalult constructor.
    35     GraphSkeleturo() {}
    36     ///Copy consructor.
    37 
    38     ///\todo It is not clear, what we expect from a copy constructor.
    39     ///E.g. How to assign the nodes/edges to each other? What about maps?
    40     GraphSkeleturo(const GraphSkeleturo &G) {}
    41 
    42     /// The base type of the node iterators.
    43 
    44     /// This is the base type of each node iterators,
    45     /// thus each kind of node iterator will convert to this.
    46     class Node {
    47     public:
    48       /// @warning The default constructor sets the iterator
    49       /// to an undefined value.
    50       Node() {}   //FIXME
    51       /// Invalid constructor \& conversion.
    52 
    53       /// This constructor initializes the iterator to be invalid.
    54       /// \sa Invalid for more details.
    55 
    56       Node(Invalid) {}
    57       //Node(const Node &) {}
    58 
    59       /// Two iterators are equal if and only if they point to the
    60       /// same object or both are invalid.
    61       bool operator==(Node n) const { return true; }
    62 
    63       /// \sa \ref operator==(Node n)
    64       ///
    65       bool operator!=(Node n) const { return true; }
    66 
    67       bool operator<(Node n) const { return true; }
    68     };
    69     
    70     /// This iterator goes through each node.
    71 
    72     /// This iterator goes through each node.
    73     /// Its usage is quite simple, for example you can count the number
    74     /// of nodes in graph \c G of type \c Graph like this:
    75     /// \code
    76     ///int count=0;
    77     ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
    78     /// \endcode
    79     class NodeIt : public Node {
    80     public:
    81       /// @warning The default constructor sets the iterator
    82       /// to an undefined value.
    83       NodeIt() {} //FIXME
    84       /// Invalid constructor \& conversion.
    85 
    86       /// Initialize the iterator to be invalid
    87       /// \sa Invalid for more details.
    88       NodeIt(Invalid) {}
    89       /// Sets the iterator to the first node of \c G.
    90       NodeIt(const GraphSkeleturo &G) {}
    91       /// @warning The default constructor sets the iterator
    92       /// to an undefined value.
    93       NodeIt(const NodeIt &) {}
    94     };
    95     
    96     
    97     /// The base type of the edge iterators.
    98     class Edge {
    99     public:
   100       /// @warning The default constructor sets the iterator
   101       /// to an undefined value.
   102       Edge() {}   //FIXME
   103       /// Initialize the iterator to be invalid
   104       Edge(Invalid) {}
   105       /// Two iterators are equal if and only if they point to the
   106       /// same object or both are invalid.
   107       bool operator==(Edge n) const { return true; }
   108       bool operator!=(Edge n) const { return true; }
   109       bool operator<(Edge n) const { return true; }
   110     };
   111     
   112     //  class SymEdgeIt : public Edge {};
   113 
   114     /// This iterator goes through each edge.
   115 
   116     /// This iterator goes through each edge of a graph.
   117     /// Its usage is quite simple, for example you can count the number
   118     /// of edges in a graph \c G of type \c Graph as follows:
   119     /// \code
   120     ///int count=0;
   121     ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
   122     /// \endcode
   123     class EdgeIt : public Edge {
   124     public:
   125       /// @warning The default constructor sets the iterator
   126       /// to an undefined value.
   127       EdgeIt() {}
   128       /// Initialize the iterator to be invalid
   129       EdgeIt(Invalid) {}
   130       EdgeIt(const GraphSkeleturo &) {}
   131     };
   132 
   133     /// First node of the graph.
   134 
   135     /// \post \c i and the return value will be the first node.
   136     ///
   137     NodeIt &first(NodeIt &i) const { return i;}
   138 
   139     /// The first incoming edge.
   140     InEdgeIt &first(InEdgeIt &i, Node n) const { return i;}
   141     /// The first outgoing edge.
   142     OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;}
   143     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
   144     /// The first edge of the Graph.
   145     EdgeIt &first(EdgeIt &i) const { return i;}
   146 
   147 //     Node getNext(Node) const {}
   148 //     InEdgeIt getNext(InEdgeIt) const {}
   149 //     OutEdgeIt getNext(OutEdgeIt) const {}
   150 //     //SymEdgeIt getNext(SymEdgeIt) const {}
   151 //     EdgeIt getNext(EdgeIt) const {}
   152 
   153     /// Go to the next node.
   154     NodeIt &next(NodeIt &i) const { return i;}
   155     /// Go to the next incoming edge.
   156     InEdgeIt &next(InEdgeIt &i) const { return i;}
   157     /// Go to the next outgoing edge.
   158     OutEdgeIt &next(OutEdgeIt &i) const { return i;}
   159     //SymEdgeIt &next(SymEdgeIt &) const {}
   160     /// Go to the next edge.
   161     EdgeIt &next(EdgeIt &i) const { return i;}
   162 
   163     ///Gives back the head node of an edge.
   164     Node head(Edge) const { return INVALID; }
   165     ///Gives back the tail node of an edge.
   166     Node tail(Edge) const { return INVALID; }
   167   
   168     //   Node aNode(InEdgeIt) const {}
   169     //   Node aNode(OutEdgeIt) const {}
   170     //   Node aNode(SymEdgeIt) const {}
   171 
   172     //   Node bNode(InEdgeIt) const {}
   173     //   Node bNode(OutEdgeIt) const {}
   174     //   Node bNode(SymEdgeIt) const {}
   175 
   176     /// Checks if a node iterator is valid
   177 
   178     ///\todo Maybe, it would be better if iterator converted to
   179     ///bool directly, as Jacint prefers.
   180     bool valid(const Node&) const { return true;}
   181     /// Checks if an edge iterator is valid
   182 
   183     ///\todo Maybe, it would be better if iterator converted to
   184     ///bool directly, as Jacint prefers.
   185     bool valid(const Edge&) const { return true;}
   186 
   187     ///Gives back the \e id of a node.
   188 
   189     ///\warning Not all graph structures provide this feature.
   190     ///
   191     int id(const Node&) const { return 0;}
   192     ///Gives back the \e id of an edge.
   193 
   194     ///\warning Not all graph structures provide this feature.
   195     ///
   196     int id(const Edge&) const { return 0;}
   197 
   198     //void setInvalid(Node &) const {};
   199     //void setInvalid(Edge &) const {};
   200   
   201     ///Add a new node to the graph.
   202 
   203     /// \return the new node.
   204     ///
   205     Node addNode() { return INVALID;}
   206     ///Add a new edge to the graph.
   207 
   208     ///Add a new edge to the graph with tail node \c tail
   209     ///and head node \c head.
   210     ///\return the new edge.
   211     Edge addEdge(Node tail, Node head) { return INVALID;}
   212     
   213     /// Resets the graph.
   214 
   215     /// This function deletes all edges and nodes of the graph.
   216     /// It also frees the memory allocated to store them.
   217     void clear() {}
   218 
   219     ///Read/write/reference map of the nodes to type \c T.
   220 
   221     ///Read/write/reference map of the nodes to type \c T.
   222     /// \sa MemoryMapSkeleturo
   223     /// \todo We may need copy constructor
   224     /// \todo We may need conversion from other nodetype
   225     /// \todo We may need operator=
   226     /// \warning Making maps that can handle bool type (NodeMap<bool>)
   227     /// needs extra attention!
   228 
   229     template<class T> class NodeMap
   230     {
   231     public:
   232       typedef T ValueType;
   233       typedef Node KeyType;
   234 
   235       NodeMap(const GraphSkeleturo &G) {}
   236       NodeMap(const GraphSkeleturo &G, T t) {}
   237 
   238       template<typename TT> NodeMap(const NodeMap<TT> &m) {}
   239 
   240       /// Sets the value of a node.
   241 
   242       /// Sets the value associated with node \c i to the value \c t.
   243       ///
   244       void set(Node i, T t) {}
   245       /// Gets the value of a node.
   246       T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary
   247       T &operator[](Node i) {return *(T*)0;}
   248       const T &operator[](Node i) const {return *(T*)0;}
   249 
   250       /// Updates the map if the graph has been changed
   251 
   252       /// \todo Do we need this?
   253       ///
   254       void update() {}
   255       void update(T a) {}   //FIXME: Is it necessary
   256     };
   257 
   258     ///Read/write/reference map of the edges to type \c T.
   259 
   260     ///Read/write/reference map of the edges to type \c T.
   261     ///It behaves exactly in the same way as \ref NodeMap.
   262     /// \sa NodeMap
   263     /// \sa MemoryMapSkeleturo
   264     /// \todo We may need copy constructor
   265     /// \todo We may need conversion from other edgetype
   266     /// \todo We may need operator=
   267     template<class T> class EdgeMap
   268     {
   269     public:
   270       typedef T ValueType;
   271       typedef Edge KeyType;
   272 
   273       EdgeMap(const GraphSkeleturo &G) {}
   274       EdgeMap(const GraphSkeleturo &G, T t) {}
   275     
   276       void set(Edge i, T t) {}
   277       T get(Edge i) const {return *(T*)0;}
   278       T &operator[](Edge i) {return *(T*)0;}
   279     
   280       void update() {}
   281       void update(T a) {}   //FIXME: Is it necessary
   282     };
   283   };
   284 
   285   /// An empty eraseable graph class.
   286   
   287   /// This class provides all the common features of an \e eraseable graph
   288   /// structure,
   289   /// however completely without implementations and real data structures
   290   /// behind the interface.
   291   /// All graph algorithms should compile with this class, but it will not
   292   /// run properly, of course.
   293   ///
   294   /// \todo This blabla could be replaced by a sepatate description about
   295   /// Skeleturos.
   296   ///
   297   /// It can be used for checking the interface compatibility,
   298   /// or it can serve as a skeleton of a new graph structure.
   299   /// 
   300   /// Also, you will find here the full documentation of a certain graph
   301   /// feature, the documentation of a real graph imlementation
   302   /// like @ref ListGraph or
   303   /// @ref SmartGraph will just refer to this structure.
   304   class EraseableGraphSkeleturo : public GraphSkeleturo
   305   {
   306   public:
   307     /// Deletes a node.
   308     void erase(Node n) {}
   309     /// Deletes an edge.
   310     void erase(Edge e) {}
   311 
   312     /// Defalult constructor.
   313     GraphSkeleturo() {}
   314     ///Copy consructor.
   315     GraphSkeleturo(const GraphSkeleturo &G) {}
   316   };
   317 
   318   /// An empty out-edge-iterable graph class.
   319   
   320   /// An empty graph class which provides a function to 
   321   /// iterate on out-edges of any node.
   322   class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo
   323   {
   324   public:
   325 
   326     /// This iterator goes trough the outgoing edges of a node.
   327 
   328     /// This iterator goes trough the \e outgoing edges of a certain node
   329     /// of a graph.
   330     /// Its usage is quite simple, for example you can count the number
   331     /// of outgoing edges of a node \c n
   332     /// in graph \c G of type \c Graph as follows.
   333     /// \code
   334     ///int count=0;
   335     ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
   336     /// \endcode
   337     class OutEdgeIt : public Edge {
   338     public:
   339       /// @warning The default constructor sets the iterator
   340       /// to an undefined value.
   341       OutEdgeIt() {}
   342       /// Initialize the iterator to be invalid
   343       OutEdgeIt(Invalid) {}
   344       /// This constructor sets the iterator to first outgoing edge.
   345     
   346       /// This constructor set the iterator to the first outgoing edge of
   347       /// node
   348       ///@param n the node
   349       ///@param G the graph
   350       OutEdgeIt(const GraphSkeleturo & G, Node n) {}
   351     };
   352   };
   353 
   354   /// An empty in-edge-iterable graph class.
   355   
   356   /// An empty graph class which provides a function to 
   357   /// iterate on in-edges of any node.
   358   class InEdgeIterableGraphSkeleturo : public GraphSkeleturo
   359   {
   360   public:
   361 
   362     /// This iterator goes trough the incoming edges of a node.
   363 
   364     /// This iterator goes trough the \e incoming edges of a certain node
   365     /// of a graph.
   366     /// Its usage is quite simple, for example you can count the number
   367     /// of incoming edges of a node \c n
   368     /// in graph \c G of type \c Graph as follows.
   369     /// \code
   370     ///int count=0;
   371     ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
   372     /// \endcode
   373     class InEdgeIt : public Edge {
   374     public:
   375       /// @warning The default constructor sets the iterator
   376       /// to an undefined value.
   377       InEdgeIt() {}
   378       /// Initialize the iterator to be invalid
   379       InEdgeIt(Invalid) {}
   380       /// This constructor sets the iterator to first incomig edge.
   381     
   382       /// This constructor set the iterator to the first incomig edge of
   383       /// node
   384       ///@param n the node
   385       ///@param G the graph
   386       InEdgeIt(const GraphSkeleturo & G, Node n) {}
   387     };
   388   };
   389 
   390 
   391   /// An empty node-eraseable graph class.
   392   
   393   /// An empty graph class which provides a function to 
   394   /// delete any of its nodes.
   395   class NodeEraseableGraphSkeleturo : public GraphSkeleturo
   396   {
   397   public:
   398     /// Deletes a node.
   399     void erase(Node n) {}
   400   };
   401 
   402   /// An empty edge-eraseable graph class.
   403   
   404   /// An empty graph class which provides a function to delete any 
   405   /// of its edges.
   406   class EdgeEraseableGraphSkeleturo : public GraphSkeleturo
   407   {
   408   public:
   409     /// Deletes a node.
   410     void erase(Edge n) {}
   411   };
   412 
   413   /// An empty graph class which provides a function to get the number of its nodes.
   414   
   415   /// This graph class provides a function for getting the number of its 
   416   /// nodes. 
   417   /// Clearly, for physical graph structures it can be expected to have such a 
   418   /// function. For wrappers or graphs which are given in an implicit way, 
   419   /// the implementation can be circumstantial, that is why this composes a 
   420   /// separate concept.
   421   class NodeCountingGraphSkeleturo : public GraphSkeleturo
   422   {
   423   public:
   424     /// Returns the number of nodes.
   425     int nodeNum() const { return 0;}
   426   };
   427 
   428   /// An empty graph class which provides a function to get the number of its edges.
   429   
   430   /// This graph class provides a function for getting the number of its 
   431   /// edges. 
   432   /// Clearly, for physical graph structures it can be expected to have such a 
   433   /// function. For wrappers or graphs which are given in an implicit way, 
   434   /// the implementation can be circumstantial, that is why this composes a 
   435   /// separate concept.
   436   class EdgeCountingGraphSkeleturo : public GraphSkeleturo
   437   {
   438   public:
   439     /// Returns the number of edges.
   440     int edgeNum() const { return 0;}
   441   };
   442   
   443   /// @}
   444 
   445 } //namespace hugo
   446 
   447 
   448 
   449 // class EmptyBipGraph : public Graph Skeleturo
   450 // {
   451 //   class ANode {};
   452 //   class BNode {};
   453 
   454 //   ANode &next(ANode &) {}
   455 //   BNode &next(BNode &) {}
   456 
   457 //   ANode &getFirst(ANode &) const {}
   458 //   BNode &getFirst(BNode &) const {}
   459 
   460 //   enum NodeClass { A = 0, B = 1 };
   461 //   NodeClass getClass(Node n) {}
   462 
   463 // }
   464 
   465 #endif // HUGO_GRAPH_H