COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_concept.h @ 1153:4b0468de3a31

Last change on this file since 1153:4b0468de3a31 was 987:87f7c54892df, checked in by Alpar Juttner, 16 years ago

Naming changes:

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