COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/graph.h @ 2116:b6a68c15a6a3

Last change on this file since 2116:b6a68c15a6a3 was 2111:ea1fa1bc3f6d, checked in by Balazs Dezso, 18 years ago

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

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