src/include/skeletons/graph.h
author marci
Tue, 04 May 2004 12:03:04 +0000
changeset 525 ddc405f1d48f
parent 503 769f31e9f7b0
permissions -rw-r--r--
misc
     1 // -*- c++ -*-
     2 #ifndef HUGO_SKELETON_GRAPH_H
     3 #define HUGO_SKELETON_GRAPH_H
     4 
     5 ///\file
     6 ///\brief Declaration of GraphSkeleton.
     7 
     8 #include <invalid.h>
     9 
    10 /// The namespace of HugoLib
    11 namespace hugo {
    12 
    13   // @defgroup empty_graph The GraphSkeleton 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 GraphSkeleton
    32   {
    33   public:
    34     /// Defalult constructor.
    35     GraphSkeleton() {}
    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     GraphSkeleton(const GraphSkeleton &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) const { return true; }
    62 
    63       /// \sa \ref operator==(Node n)
    64       ///
    65       bool operator!=(Node) const { return true; }
    66 
    67       bool operator<(Node) 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 GraphSkeleton &) {}
    91       /// @warning The default constructor sets the iterator
    92       /// to an undefined value.
    93       NodeIt(const NodeIt &n) : Node(n) {}
    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) const { return true; }
   108       bool operator!=(Edge) const { return true; }
   109       bool operator<(Edge) const { return true; }
   110     };
   111     
   112     /// This iterator goes trough the outgoing edges of a node.
   113 
   114     /// This iterator goes trough the \e outgoing edges of a certain node
   115     /// of a graph.
   116     /// Its usage is quite simple, for example you can count the number
   117     /// of outgoing edges of a node \c n
   118     /// in graph \c G of type \c Graph as follows.
   119     /// \code
   120     ///int count=0;
   121     ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
   122     /// \endcode
   123     
   124     class OutEdgeIt : public Edge {
   125     public:
   126       /// @warning The default constructor sets the iterator
   127       /// to an undefined value.
   128       OutEdgeIt() {}
   129       /// Initialize the iterator to be invalid
   130       OutEdgeIt(Invalid) {}
   131       /// This constructor sets the iterator to first outgoing edge.
   132     
   133       /// This constructor set the iterator to the first outgoing edge of
   134       /// node
   135       ///@param n the node
   136       ///@param G the graph
   137       OutEdgeIt(const GraphSkeleton &, Node) {}
   138     };
   139 
   140     /// This iterator goes trough the incoming edges of a node.
   141 
   142     /// This iterator goes trough the \e incoming edges of a certain node
   143     /// of a graph.
   144     /// Its usage is quite simple, for example you can count the number
   145     /// of outgoing edges of a node \c n
   146     /// in graph \c G of type \c Graph as follows.
   147     /// \code
   148     ///int count=0;
   149     ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
   150     /// \endcode
   151 
   152     class InEdgeIt : public Edge {
   153     public:
   154       /// @warning The default constructor sets the iterator
   155       /// to an undefined value.
   156       InEdgeIt() {}
   157       /// Initialize the iterator to be invalid
   158       InEdgeIt(Invalid) {}
   159       InEdgeIt(const GraphSkeleton &, Node) {}    
   160     };
   161     //  class SymEdgeIt : public Edge {};
   162 
   163     /// This iterator goes through each edge.
   164 
   165     /// This iterator goes through each edge of a graph.
   166     /// Its usage is quite simple, for example you can count the number
   167     /// of edges in a graph \c G of type \c Graph as follows:
   168     /// \code
   169     ///int count=0;
   170     ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
   171     /// \endcode
   172     class EdgeIt : public Edge {
   173     public:
   174       /// @warning The default constructor sets the iterator
   175       /// to an undefined value.
   176       EdgeIt() {}
   177       /// Initialize the iterator to be invalid
   178       EdgeIt(Invalid) {}
   179       EdgeIt(const GraphSkeleton &) {}
   180     };
   181 
   182     /// First node of the graph.
   183 
   184     /// \retval i the first node.
   185     /// \return the first node.
   186     ///
   187     NodeIt &first(NodeIt &i) const { return i;}
   188 
   189     /// The first incoming edge.
   190     InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
   191     /// The first outgoing edge.
   192     OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
   193     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
   194     /// The first edge of the Graph.
   195     EdgeIt &first(EdgeIt &i) const { return i;}
   196 
   197 //     Node getNext(Node) const {}
   198 //     InEdgeIt getNext(InEdgeIt) const {}
   199 //     OutEdgeIt getNext(OutEdgeIt) const {}
   200 //     //SymEdgeIt getNext(SymEdgeIt) const {}
   201 //     EdgeIt getNext(EdgeIt) const {}
   202 
   203     /// Go to the next node.
   204     NodeIt &next(NodeIt &i) const { return i;}
   205     /// Go to the next incoming edge.
   206     InEdgeIt &next(InEdgeIt &i) const { return i;}
   207     /// Go to the next outgoing edge.
   208     OutEdgeIt &next(OutEdgeIt &i) const { return i;}
   209     //SymEdgeIt &next(SymEdgeIt &) const {}
   210     /// Go to the next edge.
   211     EdgeIt &next(EdgeIt &i) const { return i;}
   212 
   213     ///Gives back the head node of an edge.
   214     Node head(Edge) const { return INVALID; }
   215     ///Gives back the tail node of an edge.
   216     Node tail(Edge) const { return INVALID; }
   217   
   218     //   Node aNode(InEdgeIt) const {}
   219     //   Node aNode(OutEdgeIt) const {}
   220     //   Node aNode(SymEdgeIt) const {}
   221 
   222     //   Node bNode(InEdgeIt) const {}
   223     //   Node bNode(OutEdgeIt) const {}
   224     //   Node bNode(SymEdgeIt) const {}
   225 
   226     /// Checks if a node iterator is valid
   227 
   228     ///\todo Maybe, it would be better if iterator converted to
   229     ///bool directly, as Jacint prefers.
   230     bool valid(const Node&) const { return true;}
   231     /// Checks if an edge iterator is valid
   232 
   233     ///\todo Maybe, it would be better if iterator converted to
   234     ///bool directly, as Jacint prefers.
   235     bool valid(const Edge&) const { return true;}
   236 
   237     ///Gives back the \e id of a node.
   238 
   239     ///\warning Not all graph structures provide this feature.
   240     ///
   241     int id(const Node&) const { return 0;}
   242     ///Gives back the \e id of an edge.
   243 
   244     ///\warning Not all graph structures provide this feature.
   245     ///
   246     int id(const Edge&) const { return 0;}
   247 
   248     //void setInvalid(Node &) const {};
   249     //void setInvalid(Edge &) const {};
   250   
   251     ///Add a new node to the graph.
   252 
   253     /// \return the new node.
   254     ///
   255     Node addNode() { return INVALID;}
   256     ///Add a new edge to the graph.
   257 
   258     ///Add a new edge to the graph with tail node \c tail
   259     ///and head node \c head.
   260     ///\return the new edge.
   261     Edge addEdge(Node, Node) { return INVALID;}
   262     
   263     /// Resets the graph.
   264 
   265     /// This function deletes all edges and nodes of the graph.
   266     /// It also frees the memory allocated to store them.
   267     void clear() {}
   268 
   269     int nodeNum() const { return 0;}
   270     int edgeNum() const { return 0;}
   271 
   272     ///Read/write/reference map of the nodes to type \c T.
   273 
   274     ///Read/write/reference map of the nodes to type \c T.
   275     /// \sa MemoryMapSkeleton
   276     /// \todo We may need copy constructor
   277     /// \todo We may need conversion from other nodetype
   278     /// \todo We may need operator=
   279     /// \warning Making maps that can handle bool type (NodeMap<bool>)
   280     /// needs extra attention!
   281 
   282     template<class T> class NodeMap
   283     {
   284     public:
   285       typedef T ValueType;
   286       typedef Node KeyType;
   287 
   288       NodeMap(const GraphSkeleton &) {}
   289       NodeMap(const GraphSkeleton &, T) {}
   290 
   291       template<typename TT> NodeMap(const NodeMap<TT> &) {}
   292 
   293       /// Sets the value of a node.
   294 
   295       /// Sets the value associated with node \c i to the value \c t.
   296       ///
   297       void set(Node, T) {}
   298       // Gets the value of a node.
   299       //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?
   300       T &operator[](Node) {return *(T*)0;}
   301       const T &operator[](Node) const {return *(T*)0;}
   302 
   303       /// Updates the map if the graph has been changed
   304 
   305       /// \todo Do we need this?
   306       ///
   307       void update() {}
   308       void update(T a) {}   //FIXME: Is it necessary
   309     };
   310 
   311     ///Read/write/reference map of the edges to type \c T.
   312 
   313     ///Read/write/reference map of the edges to type \c T.
   314     ///It behaves exactly in the same way as \ref NodeMap.
   315     /// \sa NodeMap
   316     /// \sa MemoryMapSkeleton
   317     /// \todo We may need copy constructor
   318     /// \todo We may need conversion from other edgetype
   319     /// \todo We may need operator=
   320     template<class T> class EdgeMap
   321     {
   322     public:
   323       typedef T ValueType;
   324       typedef Edge KeyType;
   325 
   326       EdgeMap(const GraphSkeleton &) {}
   327       EdgeMap(const GraphSkeleton &, T ) {}
   328     
   329       ///\todo It can copy between different types.
   330       ///
   331       template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
   332 
   333       void set(Edge, T) {}
   334       //T get(Edge) const {return *(T*)0;}
   335       T &operator[](Edge) {return *(T*)0;}
   336       const T &operator[](Edge) const {return *(T*)0;}
   337     
   338       void update() {}
   339       void update(T a) {}   //FIXME: Is it necessary
   340     };
   341   };
   342 
   343   /// An empty eraseable graph class.
   344   
   345   /// This class provides all the common features of an \e eraseable graph
   346   /// structure,
   347   /// however completely without implementations and real data structures
   348   /// behind the interface.
   349   /// All graph algorithms should compile with this class, but it will not
   350   /// run properly, of course.
   351   ///
   352   /// \todo This blabla could be replaced by a sepatate description about
   353   /// Skeletons.
   354   ///
   355   /// It can be used for checking the interface compatibility,
   356   /// or it can serve as a skeleton of a new graph structure.
   357   /// 
   358   /// Also, you will find here the full documentation of a certain graph
   359   /// feature, the documentation of a real graph imlementation
   360   /// like @ref ListGraph or
   361   /// @ref SmartGraph will just refer to this structure.
   362   class EraseableGraphSkeleton : public GraphSkeleton
   363   {
   364   public:
   365     /// Deletes a node.
   366     void erase(Node n) {}
   367     /// Deletes an edge.
   368     void erase(Edge e) {}
   369 
   370     /// Defalult constructor.
   371     EraseableGraphSkeleton() {}
   372     ///Copy consructor.
   373     EraseableGraphSkeleton(const GraphSkeleton &G) {}
   374   };
   375 
   376   
   377   // @}
   378 
   379 } //namespace hugo
   380 
   381 
   382 
   383 // class EmptyBipGraph : public Graph Skeleton
   384 // {
   385 //   class ANode {};
   386 //   class BNode {};
   387 
   388 //   ANode &next(ANode &) {}
   389 //   BNode &next(BNode &) {}
   390 
   391 //   ANode &getFirst(ANode &) const {}
   392 //   BNode &getFirst(BNode &) const {}
   393 
   394 //   enum NodeClass { A = 0, B = 1 };
   395 //   NodeClass getClass(Node n) {}
   396 
   397 // }
   398 
   399 #endif // HUGO_SKELETON_GRAPH_H