COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/concepts/digraph.h @ 157:2ccc1afc2c52

Last change on this file since 157:2ccc1afc2c52 was 125:19e82bda606a, checked in by Balazs Dezso <deba@…>, 16 years ago

Fix bug #83 in graph concept, extender and smart graph

File size: 15.1 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_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      /// \brief Returns the ID of the node.
352      int id(Node) const { return -1; }
353
354      /// \brief Returns the ID of the arc.
355      int id(Arc) const { return -1; }
356
357      /// \brief Returns the node with the given ID.
358      ///
359      /// \pre The argument should be a valid node ID in the graph.
360      Node nodeFromId(int) const { return INVALID; }
361
362      /// \brief Returns the arc with the given ID.
363      ///
364      /// \pre The argument should be a valid arc ID in the graph.
365      Arc arcFromId(int) const { return INVALID; }
366
367      /// \brief Returns an upper bound on the node IDs.
368      int maxNodeId() const { return -1; }
369
370      /// \brief Returns an upper bound on the arc IDs.
371      int maxArcId() const { return -1; }
372
373      void first(Node&) const {}
374      void next(Node&) const {}
375
376      void first(Arc&) const {}
377      void next(Arc&) const {}
378
379
380      void firstIn(Arc&, const Node&) const {}
381      void nextIn(Arc&) const {}
382
383      void firstOut(Arc&, const Node&) const {}
384      void nextOut(Arc&) const {}
385
386      // The second parameter is dummy.
387      Node fromId(int, Node) const { return INVALID; }
388      // The second parameter is dummy.
389      Arc fromId(int, Arc) const { return INVALID; }
390
391      // Dummy parameter.
392      int maxId(Node) const { return -1; }
393      // Dummy parameter.
394      int maxId(Arc) const { return -1; }
395
396      /// \brief The base node of the iterator.
397      ///
398      /// Gives back the base node of the iterator.
399      /// It is always the target of the pointed arc.
400      Node baseNode(const InArcIt&) const { return INVALID; }
401
402      /// \brief The running node of the iterator.
403      ///
404      /// Gives back the running node of the iterator.
405      /// It is always the source of the pointed arc.
406      Node runningNode(const InArcIt&) const { return INVALID; }
407
408      /// \brief The base node of the iterator.
409      ///
410      /// Gives back the base node of the iterator.
411      /// It is always the source of the pointed arc.
412      Node baseNode(const OutArcIt&) const { return INVALID; }
413
414      /// \brief The running node of the iterator.
415      ///
416      /// Gives back the running node of the iterator.
417      /// It is always the target of the pointed arc.
418      Node runningNode(const OutArcIt&) const { return INVALID; }
419
420      /// \brief The opposite node on the given arc.
421      ///
422      /// Gives back the opposite node on the given arc.
423      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
424
425      /// \brief Read write map of the nodes to type \c T.
426      ///
427      /// ReadWrite map of the nodes to type \c T.
428      /// \sa Reference
429      template<class T>
430      class NodeMap : public ReadWriteMap< Node, T > {
431      public:
432
433        ///\e
434        NodeMap(const Digraph&) { }
435        ///\e
436        NodeMap(const Digraph&, T) { }
437
438        ///Copy constructor
439        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, 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 Read write map of the arcs to type \c T.
449      ///
450      /// Reference map of the arcs to type \c T.
451      /// \sa Reference
452      template<class T>
453      class ArcMap : public ReadWriteMap<Arc,T> {
454      public:
455
456        ///\e
457        ArcMap(const Digraph&) { }
458        ///\e
459        ArcMap(const Digraph&, T) { }
460        ///Copy constructor
461        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
462        ///Assignment operator
463        template <typename CMap>
464        ArcMap& operator=(const CMap&) {
465          checkConcept<ReadMap<Arc, T>, CMap>();
466          return *this;
467        }
468      };
469
470      template <typename _Digraph>
471      struct Constraints {
472        void constraints() {
473          checkConcept<IterableDigraphComponent<>, _Digraph>();
474          checkConcept<IDableDigraphComponent<>, _Digraph>();
475          checkConcept<MappableDigraphComponent<>, _Digraph>();
476        }
477      };
478
479    };
480   
481  } //namespace concepts 
482} //namespace lemon
483
484
485
486#endif // LEMON_CONCEPT_DIGRAPH_H
Note: See TracBrowser for help on using the repository browser.