COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concepts/graph.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

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