COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/digraph.h

Last change on this file was 1432:da87dbdf3daf, checked in by Alpar Juttner <alpar@…>, 9 months ago

Resolve deprecation warnings of gcc 9 (#633)

File size: 19.3 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-2013
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#include <lemon/bits/stl_iterators.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 common interface of all directed
40    /// graphs (digraphs).
41    ///
42    /// Like all concept classes, it only provides an interface
43    /// without any sensible implementation. So any general algorithm for
44    /// directed graphs should compile with this class, but it will not
45    /// run properly, of course.
46    /// An actual digraph implementation like \ref ListDigraph or
47    /// \ref SmartDigraph may have additional functionality.
48    ///
49    /// \sa Graph
50    class Digraph {
51    private:
52      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
53      Digraph(const Digraph &) {}
54      /// \brief Assignment of a digraph to another one is \e not allowed.
55      /// Use DigraphCopy instead.
56      void operator=(const Digraph &) {}
57
58    public:
59      /// Default constructor.
60      Digraph() { }
61
62      /// The node type of the digraph
63
64      /// This class identifies a node of the digraph. It also serves
65      /// as a base class of the node iterators,
66      /// thus they convert to this type.
67      class Node {
68      public:
69        /// Default constructor
70
71        /// Default constructor.
72        /// \warning It sets the object to an undefined value.
73        Node() { }
74        /// Copy constructor.
75
76        /// Copy constructor.
77        ///
78        Node(const Node&) { }
79
80        /// Assignment operator
81
82        /// Assignment operator.
83        ///
84        const Node &operator=(const Node&) { return *this; }
85
86        /// %Invalid constructor \& conversion.
87
88        /// Initializes the object to be invalid.
89        /// \sa Invalid for more details.
90        Node(Invalid) { }
91        /// Equality operator
92
93        /// Equality operator.
94        ///
95        /// Two iterators are equal if and only if they point to the
96        /// same object or both are \c INVALID.
97        bool operator==(Node) const { return true; }
98
99        /// Inequality operator
100
101        /// Inequality operator.
102        bool operator!=(Node) const { return true; }
103
104        /// Artificial ordering operator.
105
106        /// Artificial ordering operator.
107        ///
108        /// \note This operator only has to define some strict ordering of
109        /// the nodes; this order has nothing to do with the iteration
110        /// ordering of the nodes.
111        bool operator<(Node) const { return false; }
112      };
113
114      /// Iterator class for the nodes.
115
116      /// This iterator goes through each node of the digraph.
117      /// Its usage is quite simple, for example, you can count the number
118      /// of nodes in a 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        /// Default constructor.
128        /// \warning It sets the iterator to an undefined value.
129        NodeIt() { }
130        /// Copy constructor.
131
132        /// Copy constructor.
133        ///
134        NodeIt(const NodeIt& n) : Node(n) { }
135        /// Assignment operator
136
137        /// Assignment operator.
138        ///
139        const NodeIt &operator=(const NodeIt&) { return *this; }
140
141        /// %Invalid constructor \& conversion.
142
143        /// Initializes the iterator to be invalid.
144        /// \sa Invalid for more details.
145        NodeIt(Invalid) { }
146        /// Sets the iterator to the first node.
147
148        /// Sets the iterator to the first node of the given digraph.
149        ///
150        explicit NodeIt(const Digraph&) { }
151        /// Sets the iterator to the given node.
152
153        /// Sets the iterator to the given node of the given digraph.
154        ///
155        NodeIt(const Digraph&, const Node&) { }
156        /// Next node.
157
158        /// Assign the iterator to the next node.
159        ///
160        NodeIt& operator++() { return *this; }
161      };
162
163      /// \brief Gets the collection of the nodes of the digraph.
164      ///
165      /// This function can be used for iterating on
166      /// the nodes of the digraph. It returns a wrapped NodeIt, which looks
167      /// like an STL container (by having begin() and end())
168      /// which you can use in range-based for loops, STL algorithms, etc.
169      /// For example you can write:
170      ///\code
171      /// ListDigraph g;
172      /// for(auto v: g.nodes())
173      ///   doSomething(v);
174      ///
175      /// //Using an STL algorithm:
176      /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
177      ///\endcode
178      LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
179        return LemonRangeWrapper1<NodeIt, Digraph>(*this);
180      }
181
182
183      /// The arc type of the digraph
184
185      /// This class identifies an arc of the digraph. It also serves
186      /// as a base class of the arc iterators,
187      /// thus they will convert to this type.
188      class Arc {
189      public:
190        /// Default constructor
191
192        /// Default constructor.
193        /// \warning It sets the object to an undefined value.
194        Arc() { }
195        /// Copy constructor.
196
197        /// Copy constructor.
198        ///
199        Arc(const Arc&) { }
200        /// Assignment operator
201
202        /// Assignment operator.
203        ///
204        const Arc &operator=(const Arc&) { return *this; }
205
206        /// %Invalid constructor \& conversion.
207
208        /// Initializes the object to be invalid.
209        /// \sa Invalid for more details.
210        Arc(Invalid) { }
211        /// Equality operator
212
213        /// Equality operator.
214        ///
215        /// Two iterators are equal if and only if they point to the
216        /// same object or both are \c INVALID.
217        bool operator==(Arc) const { return true; }
218        /// Inequality operator
219
220        /// Inequality operator.
221        bool operator!=(Arc) const { return true; }
222
223        /// Artificial ordering operator.
224
225        /// Artificial ordering operator.
226        ///
227        /// \note This operator only has to define some strict ordering of
228        /// the arcs; this order has nothing to do with the iteration
229        /// ordering of the arcs.
230        bool operator<(Arc) const { return false; }
231      };
232
233      /// Iterator class for the outgoing arcs of a node.
234
235      /// This iterator goes trough the \e outgoing arcs of a certain node
236      /// of a digraph.
237      /// Its usage is quite simple, for example, you can count the number
238      /// of outgoing arcs of a node \c n
239      /// in a digraph \c g of type \c %Digraph as follows.
240      ///\code
241      /// int count=0;
242      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
243      ///\endcode
244      class OutArcIt : public Arc {
245      public:
246        /// Default constructor
247
248        /// Default constructor.
249        /// \warning It sets the iterator to an undefined value.
250        OutArcIt() { }
251        /// Copy constructor.
252
253        /// Copy constructor.
254        ///
255        OutArcIt(const OutArcIt& e) : Arc(e) { }
256        /// Assignment operator
257
258        /// Assignment operator.
259        ///
260        const OutArcIt &operator=(const OutArcIt&) { return *this; }
261        /// %Invalid constructor \& conversion.
262
263        /// Initializes the iterator to be invalid.
264        /// \sa Invalid for more details.
265        OutArcIt(Invalid) { }
266        /// Sets the iterator to the first outgoing arc.
267
268        /// Sets the iterator to the first outgoing arc of the given node.
269        ///
270        OutArcIt(const Digraph&, const Node&) { }
271        /// Sets the iterator to the given arc.
272
273        /// Sets the iterator to the given arc of the given digraph.
274        ///
275        OutArcIt(const Digraph&, const Arc&) { }
276        /// Next outgoing arc
277
278        /// Assign the iterator to the next
279        /// outgoing arc of the corresponding node.
280        OutArcIt& operator++() { return *this; }
281      };
282
283      /// \brief Gets the collection of the outgoing arcs of a certain node
284      /// of the digraph.
285      ///
286      /// This function can be used for iterating on the
287      /// outgoing arcs of a certain node of the digraph. It returns a wrapped
288      /// OutArcIt, which looks like an STL container
289      /// (by having begin() and end()) which you can use in range-based
290      /// for loops, STL algorithms, etc.
291      /// For example if g is a Digraph and u is a node, you can write:
292      ///\code
293      /// for(auto a: g.outArcs(u))
294      ///   doSomething(a);
295      ///
296      /// //Using an STL algorithm:
297      /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
298      ///\endcode
299      LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
300        return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
301      }
302
303
304      /// Iterator class for the incoming arcs of a node.
305
306      /// This iterator goes trough the \e incoming arcs of a certain node
307      /// of a digraph.
308      /// Its usage is quite simple, for example, you can count the number
309      /// of incoming arcs of a node \c n
310      /// in a digraph \c g of type \c %Digraph as follows.
311      ///\code
312      /// int count=0;
313      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
314      ///\endcode
315      class InArcIt : public Arc {
316      public:
317        /// Default constructor
318
319        /// Default constructor.
320        /// \warning It sets the iterator to an undefined value.
321        InArcIt() { }
322        /// Copy constructor.
323
324        /// Copy constructor.
325        ///
326        InArcIt(const InArcIt& e) : Arc(e) { }
327        /// Assignment operator
328
329        /// Assignment operator.
330        ///
331        const InArcIt &operator=(const InArcIt&) { return *this; }
332
333        /// %Invalid constructor \& conversion.
334
335        /// Initializes the iterator to be invalid.
336        /// \sa Invalid for more details.
337        InArcIt(Invalid) { }
338        /// Sets the iterator to the first incoming arc.
339
340        /// Sets the iterator to the first incoming arc of the given node.
341        ///
342        InArcIt(const Digraph&, const Node&) { }
343        /// Sets the iterator to the given arc.
344
345        /// Sets the iterator to the given arc of the given digraph.
346        ///
347        InArcIt(const Digraph&, const Arc&) { }
348        /// Next incoming arc
349
350        /// Assign the iterator to the next
351        /// incoming arc of the corresponding node.
352        InArcIt& operator++() { return *this; }
353      };
354
355      /// \brief Gets the collection of the incoming arcs of a certain node
356      /// of the digraph.
357      ///
358      /// This function can be used for iterating on the
359      /// incoming arcs of a certain node of the digraph. It returns a wrapped
360      /// InArcIt, which looks like an STL container
361      /// (by having begin() and end()) which you can use in range-based
362      /// for loops, STL algorithms, etc.
363      /// For example if g is a Digraph and u is a node, you can write:
364      ///\code
365      /// for(auto a: g.inArcs(u))
366      ///   doSomething(a);
367      ///
368      /// //Using an STL algorithm:
369      /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
370      ///\endcode
371      LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
372        return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
373      }
374
375
376      /// Iterator class for the arcs.
377
378      /// This iterator goes through each arc of the digraph.
379      /// Its usage is quite simple, for example, you can count the number
380      /// of arcs in a digraph \c g of type \c %Digraph as follows:
381      ///\code
382      /// int count=0;
383      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
384      ///\endcode
385      class ArcIt : public Arc {
386      public:
387        /// Default constructor
388
389        /// Default constructor.
390        /// \warning It sets the iterator to an undefined value.
391        ArcIt() { }
392        /// Copy constructor.
393
394        /// Copy constructor.
395        ///
396        ArcIt(const ArcIt& e) : Arc(e) { }
397        /// Assignment operator
398
399        /// Assignment operator.
400        ///
401        const ArcIt &operator=(const ArcIt&) { return *this; }
402
403        /// %Invalid constructor \& conversion.
404
405        /// Initializes the iterator to be invalid.
406        /// \sa Invalid for more details.
407        ArcIt(Invalid) { }
408        /// Sets the iterator to the first arc.
409
410        /// Sets the iterator to the first arc of the given digraph.
411        ///
412        explicit ArcIt(const Digraph& g) {
413          ::lemon::ignore_unused_variable_warning(g);
414        }
415        /// Sets the iterator to the given arc.
416
417        /// Sets the iterator to the given arc of the given digraph.
418        ///
419        ArcIt(const Digraph&, const Arc&) { }
420        /// Next arc
421
422        /// Assign the iterator to the next arc.
423        ///
424        ArcIt& operator++() { return *this; }
425      };
426
427      /// \brief Gets the collection of the arcs of the digraph.
428      ///
429      /// This function can be used for iterating on the
430      /// arcs of the digraph. It returns a wrapped
431      /// ArcIt, which looks like an STL container
432      /// (by having begin() and end()) which you can use in range-based
433      /// for loops, STL algorithms, etc.
434      /// For example you can write:
435      ///\code
436      /// ListDigraph g;
437      /// for(auto a: g.arcs())
438      ///   doSomething(a);
439      ///
440      /// //Using an STL algorithm:
441      /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
442      ///\endcode
443      LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
444        return LemonRangeWrapper1<ArcIt, Digraph>(*this);
445      }
446
447
448      /// \brief The source node of the arc.
449      ///
450      /// Returns the source node of the given arc.
451      Node source(Arc) const { return INVALID; }
452
453      /// \brief The target node of the arc.
454      ///
455      /// Returns the target node of the given arc.
456      Node target(Arc) const { return INVALID; }
457
458      /// \brief The ID of the node.
459      ///
460      /// Returns the ID of the given node.
461      int id(Node) const { return -1; }
462
463      /// \brief The ID of the arc.
464      ///
465      /// Returns the ID of the given arc.
466      int id(Arc) const { return -1; }
467
468      /// \brief The node with the given ID.
469      ///
470      /// Returns the node with the given ID.
471      /// \pre The argument should be a valid node ID in the digraph.
472      Node nodeFromId(int) const { return INVALID; }
473
474      /// \brief The arc with the given ID.
475      ///
476      /// Returns the arc with the given ID.
477      /// \pre The argument should be a valid arc ID in the digraph.
478      Arc arcFromId(int) const { return INVALID; }
479
480      /// \brief An upper bound on the node IDs.
481      ///
482      /// Returns an upper bound on the node IDs.
483      int maxNodeId() const { return -1; }
484
485      /// \brief An upper bound on the arc IDs.
486      ///
487      /// Returns an upper bound on the arc IDs.
488      int maxArcId() const { return -1; }
489
490      void first(Node&) const {}
491      void next(Node&) const {}
492
493      void first(Arc&) const {}
494      void next(Arc&) const {}
495
496
497      void firstIn(Arc&, const Node&) const {}
498      void nextIn(Arc&) const {}
499
500      void firstOut(Arc&, const Node&) const {}
501      void nextOut(Arc&) const {}
502
503      // The second parameter is dummy.
504      Node fromId(int, Node) const { return INVALID; }
505      // The second parameter is dummy.
506      Arc fromId(int, Arc) const { return INVALID; }
507
508      // Dummy parameter.
509      int maxId(Node) const { return -1; }
510      // Dummy parameter.
511      int maxId(Arc) const { return -1; }
512
513      /// \brief The opposite node on the arc.
514      ///
515      /// Returns the opposite node on the given arc.
516      Node oppositeNode(Node, Arc) const { return INVALID; }
517
518      /// \brief The base node of the iterator.
519      ///
520      /// Returns the base node of the given outgoing arc iterator
521      /// (i.e. the source node of the corresponding arc).
522      Node baseNode(OutArcIt) const { return INVALID; }
523
524      /// \brief The running node of the iterator.
525      ///
526      /// Returns the running node of the given outgoing arc iterator
527      /// (i.e. the target node of the corresponding arc).
528      Node runningNode(OutArcIt) const { return INVALID; }
529
530      /// \brief The base node of the iterator.
531      ///
532      /// Returns the base node of the given incoming arc iterator
533      /// (i.e. the target node of the corresponding arc).
534      Node baseNode(InArcIt) const { return INVALID; }
535
536      /// \brief The running node of the iterator.
537      ///
538      /// Returns the running node of the given incoming arc iterator
539      /// (i.e. the source node of the corresponding arc).
540      Node runningNode(InArcIt) const { return INVALID; }
541
542      /// \brief Standard graph map type for the nodes.
543      ///
544      /// Standard graph map type for the nodes.
545      /// It conforms to the ReferenceMap concept.
546      template<class T>
547      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
548      public:
549
550        /// Constructor
551        explicit NodeMap(const Digraph&) { }
552        /// Constructor with given initial value
553        NodeMap(const Digraph&, T) { }
554
555      private:
556        ///Copy constructor
557        NodeMap(const NodeMap& nm) :
558          ReferenceMap<Node, T, T&, const T&>(nm) { }
559      public:
560        ///Assignment operator
561        NodeMap& operator=(const NodeMap&) {
562          return *this;
563        }
564        ///Template Assignment operator
565        template <typename CMap>
566        NodeMap& operator=(const CMap&) {
567          checkConcept<ReadMap<Node, T>, CMap>();
568          return *this;
569        }
570      };
571
572      /// \brief Standard graph map type for the arcs.
573      ///
574      /// Standard graph map type for the arcs.
575      /// It conforms to the ReferenceMap concept.
576      template<class T>
577      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
578      public:
579
580        /// Constructor
581        explicit ArcMap(const Digraph&) { }
582        /// Constructor with given initial value
583        ArcMap(const Digraph&, T) { }
584
585      private:
586        ///Copy constructor
587        ArcMap(const ArcMap& em) :
588          ReferenceMap<Arc, T, T&, const T&>(em) { }
589        ///Assignment operator
590        ArcMap& operator=(const ArcMap&) {
591          return *this;
592        }
593        ///Template Assignment operator
594        template <typename CMap>
595        ArcMap& operator=(const CMap&) {
596          checkConcept<ReadMap<Arc, T>, CMap>();
597          return *this;
598        }
599      };
600
601      template <typename _Digraph>
602      struct Constraints {
603        void constraints() {
604          checkConcept<BaseDigraphComponent, _Digraph>();
605          checkConcept<IterableDigraphComponent<>, _Digraph>();
606          checkConcept<IDableDigraphComponent<>, _Digraph>();
607          checkConcept<MappableDigraphComponent<>, _Digraph>();
608        }
609      };
610
611    };
612
613  } //namespace concepts
614} //namespace lemon
615
616
617
618#endif
Note: See TracBrowser for help on using the repository browser.