COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/skeletons/graph.h @ 921:818510fa3d99

Last change on this file since 921:818510fa3d99 was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

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