COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/graph.h @ 733:240003bddaff

Last change on this file since 733:240003bddaff was 732:33cbc0635e92, checked in by Alpar Juttner, 20 years ago

Skeletons have been simplified.
"Optional features" have been deleted.
Map skeletons have been renamed.

File size: 11.5 KB
Line 
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 <hugo/invalid.h>
9#include <hugo/skeletons/maps.h>
10
11/// The namespace of HugoLib
12namespace hugo {
13  namespace skeleton {
14   
15    // @defgroup empty_graph The GraphSkeleton class
16    // @{
17
18    /// An empty static graph class.
19 
20    /// This class provides all the common features of a graph structure,
21    /// however completely without implementations and real data structures
22    /// behind the interface.
23    /// All graph algorithms should compile with this class, but it will not
24    /// run properly, of course.
25    ///
26    /// It can be used for checking the interface compatibility,
27    /// or it can serve as a skeleton of a new graph structure.
28    ///
29    /// Also, you will find here the full documentation of a certain graph
30    /// feature, the documentation of a real graph imlementation
31    /// like @ref ListGraph or
32    /// @ref SmartGraph will just refer to this structure.
33    class StaticGraphSkeleton
34    {
35    public:
36      /// Defalult constructor.
37      StaticGraphSkeleton() {}
38      ///Copy consructor.
39
40      ///\todo It is not clear, what we expect from a copy constructor.
41      ///E.g. How to assign the nodes/edges to each other? What about maps?
42      StaticGraphSkeleton(const StaticGraphSkeleton &G) {}
43
44      /// The base type of the node iterators.
45
46      /// This is the base type of each node iterators,
47      /// thus each kind of node iterator will convert to this.
48      class Node {
49      public:
50        /// @warning The default constructor sets the iterator
51        /// to an undefined value.
52        Node() {}   //FIXME
53        /// Invalid constructor \& conversion.
54
55        /// This constructor initializes the iterator to be invalid.
56        /// \sa Invalid for more details.
57
58        Node(Invalid) {}
59        //Node(const Node &) {}
60
61        /// Two iterators are equal if and only if they point to the
62        /// same object or both are invalid.
63        bool operator==(Node) const { return true; }
64
65        /// \sa \ref operator==(Node n)
66        ///
67        bool operator!=(Node) const { return true; }
68
69        bool operator<(Node) const { return true; }
70      };
71   
72      /// This iterator goes through each node.
73
74      /// This iterator goes through each node.
75      /// Its usage is quite simple, for example you can count the number
76      /// of nodes in graph \c G of type \c Graph like this:
77      /// \code
78      ///int count=0;
79      ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
80      /// \endcode
81      class NodeIt : public Node {
82      public:
83        /// @warning The default constructor sets the iterator
84        /// to an undefined value.
85        NodeIt() {} //FIXME
86        /// Invalid constructor \& conversion.
87
88        /// Initialize the iterator to be invalid
89        /// \sa Invalid for more details.
90        NodeIt(Invalid) {}
91        /// Sets the iterator to the first node of \c G.
92        NodeIt(const StaticGraphSkeleton &) {}
93        /// @warning The default constructor sets the iterator
94        /// to an undefined value.
95        NodeIt(const NodeIt &n) : Node(n) {}
96      };
97   
98   
99      /// The base type of the edge iterators.
100      class Edge {
101      public:
102        /// @warning The default constructor sets the iterator
103        /// to an undefined value.
104        Edge() {}   //FIXME
105        /// Initialize the iterator to be invalid
106        Edge(Invalid) {}
107        /// Two iterators are equal if and only if they point to the
108        /// same object or both are invalid.
109        bool operator==(Edge) const { return true; }
110        bool operator!=(Edge) const { return true; }
111        bool operator<(Edge) const { return true; }
112      };
113   
114      /// This iterator goes trough the outgoing edges of a node.
115
116      /// This iterator goes trough the \e outgoing edges of a certain node
117      /// of a graph.
118      /// Its usage is quite simple, for example you can count the number
119      /// of outgoing edges of a node \c n
120      /// in graph \c G of type \c Graph as follows.
121      /// \code
122      ///int count=0;
123      ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
124      /// \endcode
125   
126      class OutEdgeIt : public Edge {
127      public:
128        /// @warning The default constructor sets the iterator
129        /// to an undefined value.
130        OutEdgeIt() {}
131        /// Initialize the iterator to be invalid
132        OutEdgeIt(Invalid) {}
133        /// This constructor sets the iterator to first outgoing edge.
134   
135        /// This constructor set the iterator to the first outgoing edge of
136        /// node
137        ///@param n the node
138        ///@param G the graph
139        OutEdgeIt(const StaticGraphSkeleton &, Node) {}
140      };
141
142      /// This iterator goes trough the incoming edges of a node.
143
144      /// This iterator goes trough the \e incoming edges of a certain node
145      /// of a graph.
146      /// Its usage is quite simple, for example you can count the number
147      /// of outgoing edges of a node \c n
148      /// in graph \c G of type \c Graph as follows.
149      /// \code
150      ///int count=0;
151      ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
152      /// \endcode
153
154      class InEdgeIt : public Edge {
155      public:
156        /// @warning The default constructor sets the iterator
157        /// to an undefined value.
158        InEdgeIt() {}
159        /// Initialize the iterator to be invalid
160        InEdgeIt(Invalid) {}
161        InEdgeIt(const StaticGraphSkeleton &, Node) {}   
162      };
163      //  class SymEdgeIt : public Edge {};
164
165      /// This iterator goes through each edge.
166
167      /// This iterator goes through each edge of a graph.
168      /// Its usage is quite simple, for example you can count the number
169      /// of edges in a graph \c G of type \c Graph as follows:
170      /// \code
171      ///int count=0;
172      ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
173      /// \endcode
174      class EdgeIt : public Edge {
175      public:
176        /// @warning The default constructor sets the iterator
177        /// to an undefined value.
178        EdgeIt() {}
179        /// Initialize the iterator to be invalid
180        EdgeIt(Invalid) {}
181        EdgeIt(const StaticGraphSkeleton &) {}
182      };
183
184      /// First node of the graph.
185
186      /// \retval i the first node.
187      /// \return the first node.
188      ///
189      NodeIt &first(NodeIt &i) const { return i;}
190
191      /// The first incoming edge.
192      InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
193      /// The first outgoing edge.
194      OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
195      //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
196      /// The first edge of the Graph.
197      EdgeIt &first(EdgeIt &i) const { return i;}
198
199      //     Node getNext(Node) const {}
200      //     InEdgeIt getNext(InEdgeIt) const {}
201      //     OutEdgeIt getNext(OutEdgeIt) const {}
202      //     //SymEdgeIt getNext(SymEdgeIt) const {}
203      //     EdgeIt getNext(EdgeIt) const {}
204
205      /// Go to the next node.
206      NodeIt &next(NodeIt &i) const { return i;}
207      /// Go to the next incoming edge.
208      InEdgeIt &next(InEdgeIt &i) const { return i;}
209      /// Go to the next outgoing edge.
210      OutEdgeIt &next(OutEdgeIt &i) const { return i;}
211      //SymEdgeIt &next(SymEdgeIt &) const {}
212      /// Go to the next edge.
213      EdgeIt &next(EdgeIt &i) const { return i;}
214
215      ///Gives back the head node of an edge.
216      Node head(Edge) const { return INVALID; }
217      ///Gives back the tail node of an edge.
218      Node tail(Edge) const { return INVALID; }
219 
220      //   Node aNode(InEdgeIt) const {}
221      //   Node aNode(OutEdgeIt) const {}
222      //   Node aNode(SymEdgeIt) const {}
223
224      //   Node bNode(InEdgeIt) const {}
225      //   Node bNode(OutEdgeIt) const {}
226      //   Node bNode(SymEdgeIt) const {}
227
228      /// Checks if a node iterator is valid
229
230      ///\todo Maybe, it would be better if iterator converted to
231      ///bool directly, as Jacint prefers.
232      bool valid(const Node&) const { return true;}
233      /// Checks if an edge iterator is valid
234
235      ///\todo Maybe, it would be better if iterator converted to
236      ///bool directly, as Jacint prefers.
237      bool valid(const Edge&) const { return true;}
238
239      ///Gives back the \e id of a node.
240
241      ///\warning Not all graph structures provide this feature.
242      ///
243      int id(const Node&) const { return 0;}
244      ///Gives back the \e id of an edge.
245
246      ///\warning Not all graph structures provide this feature.
247      ///
248      int id(const Edge&) const { return 0;}
249
250      /// Resets the graph.
251
252      /// This function deletes all edges and nodes of the graph.
253      /// It also frees the memory allocated to store them.
254      void clear() {}
255
256      int nodeNum() const { return 0;}
257      int edgeNum() const { return 0;}
258
259
260
261      ///Reference map of the nodes to type \c T.
262
263      ///Reference map of the nodes to type \c T.
264      /// \sa ReferenceSkeleton
265      /// \warning Making maps that can handle bool type (NodeMap<bool>)
266      /// needs extra attention!
267
268      template<class T> class NodeMap
269        : public ReferenceMap< Node, T >
270      {
271      public:
272
273        class ReferenceMap<Node,T>;
274
275        NodeMap(const StaticGraphSkeleton &) {}
276        NodeMap(const StaticGraphSkeleton &, T) {}
277
278        ///Copy constructor
279        template<typename TT> NodeMap(const NodeMap<TT> &) {}
280        ///Assignment operator
281        template<typename TT> NodeMap &operator=(const NodeMap<TT> &)
282        {return *this;}
283      };
284
285      ///Reference map of the edges to type \c T.
286
287      ///Reference map of the edges to type \c T.
288      /// \sa ReferenceSkeleton
289      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
290      /// needs extra attention!
291      template<class T> class EdgeMap
292        : public ReferenceMap<Edge,T>
293      {
294      public:
295        typedef T ValueType;
296        typedef Edge KeyType;
297
298        EdgeMap(const StaticGraphSkeleton &) {}
299        EdgeMap(const StaticGraphSkeleton &, T ) {}
300   
301        ///Copy constructor
302        template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
303        ///Assignment operator
304        template<typename TT> EdgeMap &operator=(const EdgeMap<TT> &)
305        {return *this;}
306      };
307    };
308
309
310 
311    /// An empty graph class.
312
313    /// This class provides everything that \c StaticGraphSkeleton
314    /// with additional functionality which enables to build a
315    /// graph from scratch.
316    class GraphSkeleton : public StaticGraphSkeleton
317    {
318    public:
319      /// Defalult constructor.
320      GraphSkeleton() {}
321      ///Copy consructor.
322
323      ///\todo It is not clear, what we expect from a copy constructor.
324      ///E.g. How to assign the nodes/edges to each other? What about maps?
325      GraphSkeleton(const GraphSkeleton &G) {}
326
327      ///Add a new node to the graph.
328
329      /// \return the new node.
330      ///
331      Node addNode() { return INVALID;}
332      ///Add a new edge to the graph.
333
334      ///Add a new edge to the graph with tail node \c tail
335      ///and head node \c head.
336      ///\return the new edge.
337      Edge addEdge(Node, Node) { return INVALID;}
338   
339      /// Resets the graph.
340
341      /// This function deletes all edges and nodes of the graph.
342      /// It also frees the memory allocated to store them.
343      /// \todo It might belong to \c EraseableGraphSkeleton.
344      void clear() {}
345    };
346
347    /// An empty eraseable graph class.
348 
349    /// This class is an extension of \c GraphSkeleton. It also makes it
350    /// possible to erase edges or nodes.
351    class EraseableGraphSkeleton : public GraphSkeleton
352    {
353    public:
354      /// Deletes a node.
355      void erase(Node n) {}
356      /// Deletes an edge.
357      void erase(Edge e) {}
358
359      /// Defalult constructor.
360      EraseableGraphSkeleton() {}
361      ///Copy consructor.
362      EraseableGraphSkeleton(const GraphSkeleton &G) {}
363    };
364
365    // @}
366  } //namespace skeleton
367 
368} //namespace hugo
369
370
371
372// class EmptyBipGraph : public Graph Skeleton
373// {
374//   class ANode {};
375//   class BNode {};
376
377//   ANode &next(ANode &) {}
378//   BNode &next(BNode &) {}
379
380//   ANode &getFirst(ANode &) const {}
381//   BNode &getFirst(BNode &) const {}
382
383//   enum NodeClass { A = 0, B = 1 };
384//   NodeClass getClass(Node n) {}
385
386// }
387
388#endif // HUGO_SKELETON_GRAPH_H
Note: See TracBrowser for help on using the repository browser.