COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/graph.h @ 2120:a907fb95f1e0

Last change on this file since 2120:a907fb95f1e0 was 2120:a907fb95f1e0, checked in by Alpar Juttner, 15 years ago

As we agreed, Node/Edge::operator<() is required by the concept

File size: 14.1 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    /// The directed graph concept
63
64    /// This class describes the \ref concept "concept" of the
65    /// immutable directed graphs.
66    ///
67    /// Note that actual graph implementation like @ref ListGraph or
68    /// @ref SmartGraph may have several additional functionality.
69    ///
70    /// \sa concept
71    class Graph {
72    public:
73      ///\e
74
75      /// Defalult constructor.
76
77      /// Defalult constructor.
78      ///
79      Graph() { }
80
81      /// The base type of node iterators,
82      /// or in other words, the trivial node iterator.
83
84      /// This is the base type of each node iterator,
85      /// thus each kind of node iterator converts to this.
86      /// More precisely each kind of node iterator should be inherited
87      /// from the trivial node iterator.
88      class Node {
89      public:
90        /// Default constructor
91
92        /// @warning The default constructor sets the iterator
93        /// to an undefined value.
94        Node() { }
95        /// Copy constructor.
96
97        /// Copy constructor.
98        ///
99        Node(const Node&) { }
100
101        /// Invalid constructor \& conversion.
102
103        /// This constructor initializes the iterator to be invalid.
104        /// \sa Invalid for more details.
105        Node(Invalid) { }
106        /// Equality operator
107
108        /// Two iterators are equal if and only if they point to the
109        /// same object or both are invalid.
110        bool operator==(Node) const { return true; }
111
112        /// Inequality operator
113       
114        /// \sa operator==(Node n)
115        ///
116        bool operator!=(Node) const { return true; }
117
118        /// Artificial ordering operator.
119       
120        /// To allow the use of graph descriptors as key type in std::map or
121        /// similar associative container we require this.
122        ///
123        /// \note This operator only have to define some strict ordering of
124        /// the items; this order has nothing to do with the iteration
125        /// ordering of the items.
126        bool operator<(Node) const { return false; }
127
128      };
129   
130      /// This iterator goes through each node.
131
132      /// This iterator goes through each node.
133      /// Its usage is quite simple, for example you can count the number
134      /// of nodes in graph \c g of type \c Graph like this:
135      ///\code
136      /// int count=0;
137      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
138      ///\endcode
139      class NodeIt : public Node {
140      public:
141        /// Default constructor
142
143        /// @warning The default constructor sets the iterator
144        /// to an undefined value.
145        NodeIt() { }
146        /// Copy constructor.
147       
148        /// Copy constructor.
149        ///
150        NodeIt(const NodeIt& n) : Node(n) { }
151        /// Invalid constructor \& conversion.
152
153        /// Initialize the iterator to be invalid.
154        /// \sa Invalid for more details.
155        NodeIt(Invalid) { }
156        /// Sets the iterator to the first node.
157
158        /// Sets the iterator to the first node of \c g.
159        ///
160        NodeIt(const Graph&) { }
161        /// Node -> NodeIt conversion.
162
163        /// Sets the iterator to the node of \c the graph pointed by
164        /// the trivial iterator.
165        /// This feature necessitates that each time we
166        /// iterate the edge-set, the iteration order is the same.
167        NodeIt(const Graph&, const Node&) { }
168        /// Next node.
169
170        /// Assign the iterator to the next node.
171        ///
172        NodeIt& operator++() { return *this; }
173      };
174   
175   
176      /// The base type of the edge iterators.
177
178      /// The base type of the edge iterators.
179      ///
180      class Edge {
181      public:
182        /// Default constructor
183
184        /// @warning The default constructor sets the iterator
185        /// to an undefined value.
186        Edge() { }
187        /// Copy constructor.
188
189        /// Copy constructor.
190        ///
191        Edge(const Edge&) { }
192        /// Initialize the iterator to be invalid.
193
194        /// Initialize the iterator to be invalid.
195        ///
196        Edge(Invalid) { }
197        /// Equality operator
198
199        /// Two iterators are equal if and only if they point to the
200        /// same object or both are invalid.
201        bool operator==(Edge) const { return true; }
202        /// Inequality operator
203
204        /// \sa operator==(Edge n)
205        ///
206        bool operator!=(Edge) const { return true; }
207
208        /// Artificial ordering operator.
209       
210        /// To allow the use of graph descriptors as key type in std::map or
211        /// similar associative container we require this.
212        ///
213        /// \note This operator only have to define some strict ordering of
214        /// the items; this order has nothing to do with the iteration
215        /// ordering of the items.
216        bool operator<(Edge) const { return false; }
217      };
218   
219      /// This iterator goes trough the outgoing edges of a node.
220
221      /// This iterator goes trough the \e outgoing edges of a certain node
222      /// of a graph.
223      /// Its usage is quite simple, for example you can count the number
224      /// of outgoing edges of a node \c n
225      /// in graph \c g of type \c Graph as follows.
226      ///\code
227      /// int count=0;
228      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
229      ///\endcode
230   
231      class OutEdgeIt : public Edge {
232      public:
233        /// Default constructor
234
235        /// @warning The default constructor sets the iterator
236        /// to an undefined value.
237        OutEdgeIt() { }
238        /// Copy constructor.
239
240        /// Copy constructor.
241        ///
242        OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
243        /// Initialize the iterator to be invalid.
244
245        /// Initialize the iterator to be invalid.
246        ///
247        OutEdgeIt(Invalid) { }
248        /// This constructor sets the iterator to the first outgoing edge.
249   
250        /// This constructor sets the iterator to the first outgoing edge of
251        /// the node.
252        OutEdgeIt(const Graph&, const Node&) { }
253        /// Edge -> OutEdgeIt conversion
254
255        /// Sets the iterator to the value of the trivial iterator.
256        /// This feature necessitates that each time we
257        /// iterate the edge-set, the iteration order is the same.
258        OutEdgeIt(const Graph&, const Edge&) { }
259        ///Next outgoing edge
260       
261        /// Assign the iterator to the next
262        /// outgoing edge of the corresponding node.
263        OutEdgeIt& operator++() { return *this; }
264      };
265
266      /// This iterator goes trough the incoming edges of a node.
267
268      /// This iterator goes trough the \e incoming edges of a certain node
269      /// of a graph.
270      /// Its usage is quite simple, for example you can count the number
271      /// of outgoing edges of a node \c n
272      /// in graph \c g of type \c Graph as follows.
273      ///\code
274      /// int count=0;
275      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
276      ///\endcode
277
278      class InEdgeIt : public Edge {
279      public:
280        /// Default constructor
281
282        /// @warning The default constructor sets the iterator
283        /// to an undefined value.
284        InEdgeIt() { }
285        /// Copy constructor.
286
287        /// Copy constructor.
288        ///
289        InEdgeIt(const InEdgeIt& e) : Edge(e) { }
290        /// Initialize the iterator to be invalid.
291
292        /// Initialize the iterator to be invalid.
293        ///
294        InEdgeIt(Invalid) { }
295        /// This constructor sets the iterator to first incoming edge.
296   
297        /// This constructor set the iterator to the first incoming edge of
298        /// the node.
299        InEdgeIt(const Graph&, const Node&) { }
300        /// Edge -> InEdgeIt conversion
301
302        /// Sets the iterator to the value of the trivial iterator \c e.
303        /// This feature necessitates that each time we
304        /// iterate the edge-set, the iteration order is the same.
305        InEdgeIt(const Graph&, const Edge&) { }
306        /// Next incoming edge
307
308        /// Assign the iterator to the next inedge of the corresponding node.
309        ///
310        InEdgeIt& operator++() { return *this; }
311      };
312      /// This iterator goes through each edge.
313
314      /// This iterator goes through each edge of a graph.
315      /// Its usage is quite simple, for example you can count the number
316      /// of edges in a graph \c g of type \c Graph as follows:
317      ///\code
318      /// int count=0;
319      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
320      ///\endcode
321      class EdgeIt : public Edge {
322      public:
323        /// Default constructor
324
325        /// @warning The default constructor sets the iterator
326        /// to an undefined value.
327        EdgeIt() { }
328        /// Copy constructor.
329
330        /// Copy constructor.
331        ///
332        EdgeIt(const EdgeIt& e) : Edge(e) { }
333        /// Initialize the iterator to be invalid.
334
335        /// Initialize the iterator to be invalid.
336        ///
337        EdgeIt(Invalid) { }
338        /// This constructor sets the iterator to the first edge.
339   
340        /// This constructor sets the iterator to the first edge of \c g.
341        ///@param g the graph
342        EdgeIt(const Graph& g) { ignore_unused_variable_warning(g); }
343        /// Edge -> EdgeIt conversion
344
345        /// Sets the iterator to the value of the trivial iterator \c e.
346        /// This feature necessitates that each time we
347        /// iterate the edge-set, the iteration order is the same.
348        EdgeIt(const Graph&, const Edge&) { }
349        ///Next edge
350       
351        /// Assign the iterator to the next edge.
352        EdgeIt& operator++() { return *this; }
353      };
354      ///Gives back the target node of an edge.
355
356      ///Gives back the target node of an edge.
357      ///
358      Node target(Edge) const { return INVALID; }
359      ///Gives back the source node of an edge.
360
361      ///Gives back the source node of an edge.
362      ///
363      Node source(Edge) const { return INVALID; }
364
365      void first(Node&) const {}
366      void next(Node&) const {}
367
368      void first(Edge&) const {}
369      void next(Edge&) const {}
370
371
372      void firstIn(Edge&, const Node&) const {}
373      void nextIn(Edge&) const {}
374
375      void firstOut(Edge&, const Node&) const {}
376      void nextOut(Edge&) const {}
377
378      /// \brief The base node of the iterator.
379      ///
380      /// Gives back the base node of the iterator.
381      /// It is always the target of the pointed edge.
382      Node baseNode(const InEdgeIt&) const { return INVALID; }
383
384      /// \brief The running node of the iterator.
385      ///
386      /// Gives back the running node of the iterator.
387      /// It is always the source of the pointed edge.
388      Node runningNode(const InEdgeIt&) const { return INVALID; }
389
390      /// \brief The base node of the iterator.
391      ///
392      /// Gives back the base node of the iterator.
393      /// It is always the source of the pointed edge.
394      Node baseNode(const OutEdgeIt&) const { return INVALID; }
395
396      /// \brief The running node of the iterator.
397      ///
398      /// Gives back the running node of the iterator.
399      /// It is always the target of the pointed edge.
400      Node runningNode(const OutEdgeIt&) const { return INVALID; }
401
402      /// \brief The opposite node on the given edge.
403      ///
404      /// Gives back the opposite node on the given edge.
405      Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
406
407      /// \brief Read write map of the nodes to type \c T.
408      ///
409      /// ReadWrite map of the nodes to type \c T.
410      /// \sa Reference
411      /// \warning Making maps that can handle bool type (NodeMap<bool>)
412      /// needs some extra attention!
413      /// \todo Wrong documentation
414      template<class T>
415      class NodeMap : public ReadWriteMap< Node, T >
416      {
417      public:
418
419        ///\e
420        NodeMap(const Graph&) { }
421        ///\e
422        NodeMap(const Graph&, T) { }
423
424        ///Copy constructor
425        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
426        ///Assignment operator
427        NodeMap& operator=(const NodeMap&) { return *this; }
428        // \todo fix this concept
429      };
430
431      /// \brief Read write map of the edges to type \c T.
432      ///
433      /// Reference map of the edges to type \c T.
434      /// \sa Reference
435      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
436      /// needs some extra attention!
437      /// \todo Wrong documentation
438      template<class T>
439      class EdgeMap : public ReadWriteMap<Edge,T>
440      {
441      public:
442
443        ///\e
444        EdgeMap(const Graph&) { }
445        ///\e
446        EdgeMap(const Graph&, T) { }
447        ///Copy constructor
448        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
449        ///Assignment operator
450        EdgeMap& operator=(const EdgeMap&) { return *this; }
451        // \todo fix this concept   
452      };
453
454      template <typename RGraph>
455      struct Constraints : public _Graph::Constraints<RGraph> {};
456
457    };
458   
459    // @}
460  } //namespace concept 
461} //namespace lemon
462
463
464
465#endif // LEMON_CONCEPT_GRAPH_H
Note: See TracBrowser for help on using the repository browser.