COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/graph.h @ 794:d9ec436d11fe

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

New doxygen module "skeletons" for the skeletons.

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