COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/graph.h @ 2126:2c8adbee9fa6

Last change on this file since 2126:2c8adbee9fa6 was 2126:2c8adbee9fa6, checked in by Balazs Dezso, 18 years ago

Renameing file: graph_component.h => graph_components.h

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