COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/concepts/digraph.h @ 88:18444049848b

Last change on this file since 88:18444049848b was 57:c1acf0018c0a, checked in by Balazs Dezso <deba@…>, 16 years ago

Port ListDigraph? and ListGraph? from svn -r 3433
Details:

  • port Digraph and Graph concepts
  • port ListDigraph? and ListGraph?
  • port Basic graph constructing tools
  • port Digraph and Graph tests
File size: 14.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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_DIGRAPH_H
20#define LEMON_CONCEPT_DIGRAPH_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 digraphs.
41    ///
42    /// Note that actual digraph implementation like @ref ListDigraph or
43    /// @ref SmartDigraph may have several additional functionality.
44    ///
45    /// \sa concept
46    class Digraph {
47    private:
48      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
49     
50      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
51      ///
52      Digraph(const Digraph &) {};
53      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
54      ///\e not allowed. Use DigraphCopy() instead.
55     
56      ///Assignment of \ref Digraph "Digraph"s to another ones are
57      ///\e not allowed.  Use DigraphCopy() instead.
58
59      void operator=(const Digraph &) {}
60    public:
61      ///\e
62
63      /// Defalult constructor.
64
65      /// Defalult constructor.
66      ///
67      Digraph() { }
68      /// Class for identifying a node of the digraph
69
70      /// This class identifies a node of the digraph. 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 digraph 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 digraph \c g of type \c Digraph like this:
120      ///\code
121      /// int count=0;
122      /// for (Digraph::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 Digraph&) { }
146        /// Node -> NodeIt conversion.
147
148        /// Sets the iterator to the node of \c the digraph pointed by
149        /// the trivial iterator.
150        /// This feature necessitates that each time we
151        /// iterate the arc-set, the iteration order is the same.
152        NodeIt(const Digraph&, 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 arc of the digraph
162
163      /// This class identifies an arc of the digraph. It also serves
164      /// as a base class of the arc iterators,
165      /// thus they will convert to this type.
166      class Arc {
167      public:
168        /// Default constructor
169
170        /// @warning The default constructor sets the iterator
171        /// to an undefined value.
172        Arc() { }
173        /// Copy constructor.
174
175        /// Copy constructor.
176        ///
177        Arc(const Arc&) { }
178        /// Initialize the iterator to be invalid.
179
180        /// Initialize the iterator to be invalid.
181        ///
182        Arc(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==(Arc) const { return true; }
188        /// Inequality operator
189
190        /// \sa operator==(Arc n)
191        ///
192        bool operator!=(Arc) const { return true; }
193
194        /// Artificial ordering operator.
195       
196        /// To allow the use of digraph 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<(Arc) const { return false; }
203      };
204   
205      /// This iterator goes trough the outgoing arcs of a node.
206
207      /// This iterator goes trough the \e outgoing arcs of a certain node
208      /// of a digraph.
209      /// Its usage is quite simple, for example you can count the number
210      /// of outgoing arcs of a node \c n
211      /// in digraph \c g of type \c Digraph as follows.
212      ///\code
213      /// int count=0;
214      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
215      ///\endcode
216   
217      class OutArcIt : public Arc {
218      public:
219        /// Default constructor
220
221        /// @warning The default constructor sets the iterator
222        /// to an undefined value.
223        OutArcIt() { }
224        /// Copy constructor.
225
226        /// Copy constructor.
227        ///
228        OutArcIt(const OutArcIt& e) : Arc(e) { }
229        /// Initialize the iterator to be invalid.
230
231        /// Initialize the iterator to be invalid.
232        ///
233        OutArcIt(Invalid) { }
234        /// This constructor sets the iterator to the first outgoing arc.
235   
236        /// This constructor sets the iterator to the first outgoing arc of
237        /// the node.
238        OutArcIt(const Digraph&, const Node&) { }
239        /// Arc -> OutArcIt conversion
240
241        /// Sets the iterator to the value of the trivial iterator.
242        /// This feature necessitates that each time we
243        /// iterate the arc-set, the iteration order is the same.
244        OutArcIt(const Digraph&, const Arc&) { }
245        ///Next outgoing arc
246       
247        /// Assign the iterator to the next
248        /// outgoing arc of the corresponding node.
249        OutArcIt& operator++() { return *this; }
250      };
251
252      /// This iterator goes trough the incoming arcs of a node.
253
254      /// This iterator goes trough the \e incoming arcs of a certain node
255      /// of a digraph.
256      /// Its usage is quite simple, for example you can count the number
257      /// of outgoing arcs of a node \c n
258      /// in digraph \c g of type \c Digraph as follows.
259      ///\code
260      /// int count=0;
261      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
262      ///\endcode
263
264      class InArcIt : public Arc {
265      public:
266        /// Default constructor
267
268        /// @warning The default constructor sets the iterator
269        /// to an undefined value.
270        InArcIt() { }
271        /// Copy constructor.
272
273        /// Copy constructor.
274        ///
275        InArcIt(const InArcIt& e) : Arc(e) { }
276        /// Initialize the iterator to be invalid.
277
278        /// Initialize the iterator to be invalid.
279        ///
280        InArcIt(Invalid) { }
281        /// This constructor sets the iterator to first incoming arc.
282   
283        /// This constructor set the iterator to the first incoming arc of
284        /// the node.
285        InArcIt(const Digraph&, const Node&) { }
286        /// Arc -> InArcIt 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 arc-set, the iteration order is the same.
291        InArcIt(const Digraph&, const Arc&) { }
292        /// Next incoming arc
293
294        /// Assign the iterator to the next inarc of the corresponding node.
295        ///
296        InArcIt& operator++() { return *this; }
297      };
298      /// This iterator goes through each arc.
299
300      /// This iterator goes through each arc of a digraph.
301      /// Its usage is quite simple, for example you can count the number
302      /// of arcs in a digraph \c g of type \c Digraph as follows:
303      ///\code
304      /// int count=0;
305      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
306      ///\endcode
307      class ArcIt : public Arc {
308      public:
309        /// Default constructor
310
311        /// @warning The default constructor sets the iterator
312        /// to an undefined value.
313        ArcIt() { }
314        /// Copy constructor.
315
316        /// Copy constructor.
317        ///
318        ArcIt(const ArcIt& e) : Arc(e) { }
319        /// Initialize the iterator to be invalid.
320
321        /// Initialize the iterator to be invalid.
322        ///
323        ArcIt(Invalid) { }
324        /// This constructor sets the iterator to the first arc.
325   
326        /// This constructor sets the iterator to the first arc of \c g.
327        ///@param g the digraph
328        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
329        /// Arc -> ArcIt 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 arc-set, the iteration order is the same.
334        ArcIt(const Digraph&, const Arc&) { }
335        ///Next arc
336       
337        /// Assign the iterator to the next arc.
338        ArcIt& operator++() { return *this; }
339      };
340      ///Gives back the target node of an arc.
341
342      ///Gives back the target node of an arc.
343      ///
344      Node target(Arc) const { return INVALID; }
345      ///Gives back the source node of an arc.
346
347      ///Gives back the source node of an arc.
348      ///
349      Node source(Arc) const { return INVALID; }
350
351      void first(Node&) const {}
352      void next(Node&) const {}
353
354      void first(Arc&) const {}
355      void next(Arc&) const {}
356
357
358      void firstIn(Arc&, const Node&) const {}
359      void nextIn(Arc&) const {}
360
361      void firstOut(Arc&, const Node&) const {}
362      void nextOut(Arc&) 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 arc.
368      Node baseNode(const InArcIt&) 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 arc.
374      Node runningNode(const InArcIt&) 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 arc.
380      Node baseNode(const OutArcIt&) 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 arc.
386      Node runningNode(const OutArcIt&) const { return INVALID; }
387
388      /// \brief The opposite node on the given arc.
389      ///
390      /// Gives back the opposite node on the given arc.
391      Node oppositeNode(const Node&, const Arc&) 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 Digraph&) { }
403        ///\e
404        NodeMap(const Digraph&, 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 arcs to type \c T.
417      ///
418      /// Reference map of the arcs to type \c T.
419      /// \sa Reference
420      template<class T>
421      class ArcMap : public ReadWriteMap<Arc,T> {
422      public:
423
424        ///\e
425        ArcMap(const Digraph&) { }
426        ///\e
427        ArcMap(const Digraph&, T) { }
428        ///Copy constructor
429        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
430        ///Assignment operator
431        template <typename CMap>
432        ArcMap& operator=(const CMap&) {
433          checkConcept<ReadMap<Arc, T>, CMap>();
434          return *this;
435        }
436      };
437
438      template <typename RDigraph>
439      struct Constraints {
440        void constraints() {
441          checkConcept<IterableDigraphComponent<>, Digraph>();
442          checkConcept<MappableDigraphComponent<>, Digraph>();
443        }
444      };
445
446    };
447   
448  } //namespace concepts 
449} //namespace lemon
450
451
452
453#endif // LEMON_CONCEPT_DIGRAPH_H
Note: See TracBrowser for help on using the repository browser.