COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/graph.h @ 881:a9f19f38970b

Last change on this file since 881:a9f19f38970b was 881:a9f19f38970b, checked in by Alpar Juttner, 20 years ago

Right (but still too short) documentation of the namespaces.

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