COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/digraph.h @ 1369:9fd86ec2cb81

Last change on this file since 1369:9fd86ec2cb81 was 1336:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 6 years ago

STL style iterators (#325)

For

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