COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/graph.h @ 880:9d0bfd35b97c

Last change on this file since 880:9d0bfd35b97c was 880:9d0bfd35b97c, checked in by Alpar Juttner, 16 years ago
  • Name changing: XYZGraphSkeleton -> XYZGraph
  • Fix some bad \ref's in the doc.
File size: 13.3 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_SKELETON_GRAPH_H
3#define HUGO_SKELETON_GRAPH_H
4
5///\ingroup skeletons
6///\file
7///\brief Declaration of Graph.
8
9#include <hugo/invalid.h>
10#include <hugo/skeletons/maps.h>
11
12/// The namespace of HugoLib
13namespace hugo {
14  namespace skeleton {
15   
16    /// \addtogroup skeletons
17    /// @{
18
19    /// An empty static graph class.
20 
21    /// This class provides all the common features of a graph structure,
22    /// however completely without implementations and real data structures
23    /// behind the interface.
24    /// All graph algorithms should compile with this class, but it will not
25    /// run properly, of course.
26    ///
27    /// It can be used for checking the interface compatibility,
28    /// or it can serve as a skeleton of a new graph structure.
29    ///
30    /// Also, you will find here the full documentation of a certain graph
31    /// feature, the documentation of a real graph imlementation
32    /// like @ref ListGraph or
33    /// @ref SmartGraph will just refer to this structure.
34    class StaticGraph
35    {
36    public:
37      /// Defalult constructor.
38
39      /// Defalult constructor.
40      ///
41      StaticGraph() { }
42      ///Copy consructor.
43
44//       ///\todo It is not clear, what we expect from a copy constructor.
45//       ///E.g. How to assign the nodes/edges to each other? What about maps?
46//       StaticGraph(const StaticGraph& g) { }
47
48      /// The base type of node iterators,
49      /// or in other words, the trivial node iterator.
50
51      /// This is the base type of each node iterator,
52      /// thus each kind of node iterator converts to this.
53      /// More precisely each kind of node iterator should be inherited
54      /// from the trivial node iterator.
55      class Node {
56      public:
57        /// Default constructor
58
59        /// @warning The default constructor sets the iterator
60        /// to an undefined value.
61        Node() { }
62        /// Copy constructor.
63
64        /// Copy constructor.
65        ///
66        Node(const Node&) { }
67
68        /// Invalid constructor \& conversion.
69
70        /// This constructor initializes the iterator to be invalid.
71        /// \sa Invalid for more details.
72        Node(Invalid) { }
73        /// Equality operator
74
75        /// Two iterators are equal if and only if they point to the
76        /// same object or both are invalid.
77        bool operator==(Node) const { return true; }
78
79        /// Inequality operator
80       
81        /// \sa \ref operator==(Node n)
82        ///
83        bool operator!=(Node) const { return true; }
84
85        ///Comparison operator.
86
87        ///This is a strict ordering between the nodes.
88        ///
89        ///This ordering can be different from the order in which NodeIt
90        ///goes through the nodes.
91        ///\todo Possibly we don't need it.
92        bool operator<(Node) const { return true; }
93      };
94   
95      /// This iterator goes through each node.
96
97      /// This iterator goes through each node.
98      /// Its usage is quite simple, for example you can count the number
99      /// of nodes in graph \c g of type \c Graph like this:
100      /// \code
101      /// int count=0;
102      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
103      /// \endcode
104      class NodeIt : public Node {
105      public:
106        /// Default constructor
107
108        /// @warning The default constructor sets the iterator
109        /// to an undefined value.
110        NodeIt() { }
111        /// Copy constructor.
112       
113        /// Copy constructor.
114        ///
115        NodeIt(const NodeIt&) { }
116        /// Invalid constructor \& conversion.
117
118        /// Initialize the iterator to be invalid.
119        /// \sa Invalid for more details.
120        NodeIt(Invalid) { }
121        /// Sets the iterator to the first node.
122
123        /// Sets the iterator to the first node of \c g.
124        ///
125        NodeIt(const StaticGraph& g) { }
126        /// Node -> NodeIt conversion.
127
128        /// Sets the iterator to the node of \c g pointed by the trivial
129        /// iterator n.
130        /// This feature necessitates that each time we
131        /// iterate the edge-set, the iteration order is the same.
132        NodeIt(const StaticGraph& g, const Node& n) { }
133        /// Next node.
134
135        /// Assign the iterator to the next node.
136        ///
137        NodeIt& operator++() { return *this; }
138      };
139   
140   
141      /// The base type of the edge iterators.
142
143      /// The base type of the edge iterators.
144      ///
145      class Edge {
146      public:
147        /// Default constructor
148
149        /// @warning The default constructor sets the iterator
150        /// to an undefined value.
151        Edge() { }
152        /// Copy constructor.
153
154        /// Copy constructor.
155        ///
156        Edge(const Edge&) { }
157        /// Initialize the iterator to be invalid.
158
159        /// Initialize the iterator to be invalid.
160        ///
161        Edge(Invalid) { }
162        /// Equality operator
163
164        /// Two iterators are equal if and only if they point to the
165        /// same object or both are invalid.
166        bool operator==(Edge) const { return true; }
167        /// Inequality operator
168
169        /// \sa \ref operator==(Node n)
170        ///
171        bool operator!=(Edge) const { return true; }
172        ///Comparison operator.
173
174        ///This is a strict ordering between the nodes.
175        ///
176        ///This ordering can be different from the order in which NodeIt
177        ///goes through the nodes.
178        ///\todo Possibly we don't need it.
179        bool operator<(Edge) const { return true; }
180      };
181   
182      /// This iterator goes trough the outgoing edges of a node.
183
184      /// This iterator goes trough the \e outgoing edges of a certain node
185      /// of a graph.
186      /// Its usage is quite simple, for example you can count the number
187      /// of outgoing edges of a node \c n
188      /// in graph \c g of type \c Graph as follows.
189      /// \code
190      /// int count=0;
191      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
192      /// \endcode
193   
194      class OutEdgeIt : public Edge {
195      public:
196        /// Default constructor
197
198        /// @warning The default constructor sets the iterator
199        /// to an undefined value.
200        OutEdgeIt() { }
201        /// Copy constructor.
202
203        /// Copy constructor.
204        ///
205        OutEdgeIt(const OutEdgeIt&) { }
206        /// Initialize the iterator to be invalid.
207
208        /// Initialize the iterator to be invalid.
209        ///
210        OutEdgeIt(Invalid) { }
211        /// This constructor sets the iterator to first outgoing edge.
212   
213        /// This constructor set the iterator to the first outgoing edge of
214        /// node
215        ///@param n the node
216        ///@param g the graph
217        OutEdgeIt(const StaticGraph& g, const Node& n) { }
218        /// Edge -> OutEdgeIt conversion
219
220        /// Sets the iterator to the value of the trivial iterator \c e.
221        /// This feature necessitates that each time we
222        /// iterate the edge-set, the iteration order is the same.
223        OutEdgeIt(const StaticGraph& g, const Edge& e) { }
224        ///Next outgoing edge
225       
226        /// Assign the iterator to the next
227        /// outgoing edge of the corresponding node.
228        OutEdgeIt& operator++() { return *this; }
229      };
230
231      /// This iterator goes trough the incoming edges of a node.
232
233      /// This iterator goes trough the \e incoming edges of a certain node
234      /// of a graph.
235      /// Its usage is quite simple, for example you can count the number
236      /// of outgoing edges of a node \c n
237      /// in graph \c g of type \c Graph as follows.
238      /// \code
239      /// int count=0;
240      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
241      /// \endcode
242
243      class InEdgeIt : public Edge {
244      public:
245        /// Default constructor
246
247        /// @warning The default constructor sets the iterator
248        /// to an undefined value.
249        InEdgeIt() { }
250        /// Copy constructor.
251
252        /// Copy constructor.
253        ///
254        InEdgeIt(const InEdgeIt&) { }
255        /// Initialize the iterator to be invalid.
256
257        /// Initialize the iterator to be invalid.
258        ///
259        InEdgeIt(Invalid) { }
260        /// This constructor sets the iterator to first incoming edge.
261   
262        /// This constructor set the iterator to the first incoming edge of
263        /// node
264        ///@param n the node
265        ///@param g the graph
266        InEdgeIt(const StaticGraph& g, const Node& n) { }
267        /// Edge -> InEdgeIt conversion
268
269        /// Sets the iterator to the value of the trivial iterator \c e.
270        /// This feature necessitates that each time we
271        /// iterate the edge-set, the iteration order is the same.
272        InEdgeIt(const StaticGraph& g, const Edge& n) { }
273        /// Next incoming edge
274
275        /// Assign the iterator to the next inedge of the corresponding node.
276        ///
277        InEdgeIt& operator++() { return *this; }
278      };
279      /// This iterator goes through each edge.
280
281      /// This iterator goes through each edge of a graph.
282      /// Its usage is quite simple, for example you can count the number
283      /// of edges in a graph \c g of type \c Graph as follows:
284      /// \code
285      /// int count=0;
286      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
287      /// \endcode
288      class EdgeIt : public Edge {
289      public:
290        /// Default constructor
291
292        /// @warning The default constructor sets the iterator
293        /// to an undefined value.
294        EdgeIt() { }
295        /// Copy constructor.
296
297        /// Copy constructor.
298        ///
299        EdgeIt(const EdgeIt&) { }
300        /// Initialize the iterator to be invalid.
301
302        /// Initialize the iterator to be invalid.
303        ///
304        EdgeIt(Invalid) { }
305        /// This constructor sets the iterator to first edge.
306   
307        /// This constructor set the iterator to the first edge of
308        /// node
309        ///@param g the graph
310        EdgeIt(const StaticGraph& g) { }
311        /// Edge -> EdgeIt conversion
312
313        /// Sets the iterator to the value of the trivial iterator \c e.
314        /// This feature necessitates that each time we
315        /// iterate the edge-set, the iteration order is the same.
316        EdgeIt(const StaticGraph&, const Edge&) { }
317        ///Next edge
318       
319        /// Assign the iterator to the next
320        /// edge of the corresponding node.
321        EdgeIt& operator++() { return *this; }
322      };
323
324      /// First node of the graph.
325
326      /// \retval i the first node.
327      /// \return the first node.
328      ///
329      NodeIt& first(NodeIt& i) const { return i; }
330
331      /// The first incoming edge.
332
333      /// The first incoming edge.
334      ///
335      InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
336      /// The first outgoing edge.
337
338      /// The first outgoing edge.
339      ///
340      OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
341      /// The first edge of the Graph.
342
343      /// The first edge of the Graph.
344      ///
345      EdgeIt& first(EdgeIt& i) const { return i; }
346
347      ///Gives back the head node of an edge.
348
349      ///Gives back the head node of an edge.
350      ///
351      Node head(Edge) const { return INVALID; }
352      ///Gives back the tail node of an edge.
353
354      ///Gives back the tail node of an edge.
355      ///
356      Node tail(Edge) const { return INVALID; }
357 
358      ///Gives back the \e id of a node.
359
360      ///\warning Not all graph structures provide this feature.
361      ///
362      ///\todo Should each graph provide \c id?
363      int id(const Node&) const { return 0; }
364      ///Gives back the \e id of an edge.
365
366      ///\warning Not all graph structures provide this feature.
367      ///
368      ///\todo Should each graph provide \c id?
369      int id(const Edge&) const { return 0; }
370
371      /// .
372     
373      ///\todo Should it be in the concept?
374      ///
375      int nodeNum() const { return 0; }
376      /// .
377
378      ///\todo Should it be in the concept?
379      ///
380      int edgeNum() const { return 0; }
381
382
383      ///Reference map of the nodes to type \c T.
384
385      /// \ingroup skeletons
386      ///Reference map of the nodes to type \c T.
387      /// \sa Reference
388      /// \warning Making maps that can handle bool type (NodeMap<bool>)
389      /// needs some extra attention!
390      template<class T> class NodeMap : public ReferenceMap< Node, T >
391      {
392      public:
393
394        /// .
395        NodeMap(const StaticGraph&) { }
396        /// .
397        NodeMap(const StaticGraph&, T) { }
398
399        ///Copy constructor
400        template<typename TT> NodeMap(const NodeMap<TT>&) { }
401        ///Assignment operator
402        template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
403        { return *this; }
404      };
405
406      ///Reference map of the edges to type \c T.
407
408      /// \ingroup skeletons
409      ///Reference map of the edges to type \c T.
410      /// \sa Reference
411      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
412      /// needs some extra attention!
413      template<class T> class EdgeMap
414        : public ReferenceMap<Edge,T>
415      {
416      public:
417
418        /// .
419        EdgeMap(const StaticGraph&) { }
420        /// .
421        EdgeMap(const StaticGraph&, T) { }
422   
423        ///Copy constructor
424        template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
425        ///Assignment operator
426        template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
427        { return *this; }
428      };
429    };
430
431
432 
433    /// An empty non-static graph class.
434
435    /// This class provides everything that \ref StaticGraph
436    /// with additional functionality which enables to build a
437    /// graph from scratch.
438    class ExtendableGraph : public StaticGraph
439    {
440    public:
441      /// Defalult constructor.
442
443      /// Defalult constructor.
444      ///
445      ExtendableGraph() { }
446      ///Add a new node to the graph.
447
448      /// \return the new node.
449      ///
450      Node addNode() { return INVALID; }
451      ///Add a new edge to the graph.
452
453      ///Add a new edge to the graph with tail node \c t
454      ///and head node \c h.
455      ///\return the new edge.
456      Edge addEdge(Node h, Node t) { return INVALID; }
457   
458      /// Resets the graph.
459
460      /// This function deletes all edges and nodes of the graph.
461      /// It also frees the memory allocated to store them.
462      /// \todo It might belong to \ref ErasableGraph.
463      void clear() { }
464    };
465
466    /// An empty erasable graph class.
467 
468    /// This class is an extension of \ref ExtendableGraph. It also makes it
469    /// possible to erase edges or nodes.
470    class ErasableGraph : public ExtendableGraph
471    {
472    public:
473      /// Defalult constructor.
474
475      /// Defalult constructor.
476      ///
477      ErasableGraph() { }
478      /// Deletes a node.
479
480      /// Deletes node \c n node.
481      ///
482      void erase(Node n) { }
483      /// Deletes an edge.
484
485      /// Deletes edge \c e edge.
486      ///
487      void erase(Edge e) { }
488    };
489
490    // @}
491  } //namespace skeleton 
492} //namespace hugo
493
494
495
496#endif // HUGO_SKELETON_GRAPH_H
Note: See TracBrowser for help on using the repository browser.