COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/digraph.h @ 627:2313edd0db0b

Last change on this file since 627:2313edd0db0b was 627:2313edd0db0b, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Standard graph maps are required to be reference maps (#190)

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