COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concepts/graph.h @ 2287:16954ac69517

Last change on this file since 2287:16954ac69517 was 2260:4274224f8a7d, checked in by Alpar Juttner, 17 years ago

concept -> concepts (namespace & directory)

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