COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/path.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: 11.0 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///\ingroup concept
20///\file
21///\brief The concept of paths
22///
23
24#ifndef LEMON_CONCEPTS_PATH_H
25#define LEMON_CONCEPTS_PATH_H
26
27#include <lemon/core.h>
28#include <lemon/concept_check.h>
29#include <lemon/bits/stl_iterators.h>
30
31namespace lemon {
32  namespace concepts {
33
34    /// \addtogroup concept
35    /// @{
36
37    /// \brief A skeleton structure for representing directed paths in
38    /// a digraph.
39    ///
40    /// A skeleton structure for representing directed paths in a
41    /// digraph.
42    /// In a sense, a path can be treated as a list of arcs.
43    /// LEMON path types just store this list. As a consequence, they cannot
44    /// enumerate the nodes on the path directly and a zero length path
45    /// cannot store its source node.
46    ///
47    /// The arcs of a path should be stored in the order of their directions,
48    /// i.e. the target node of each arc should be the same as the source
49    /// node of the next arc. This consistency could be checked using
50    /// \ref checkPath().
51    /// The source and target nodes of a (consistent) path can be obtained
52    /// using \ref pathSource() and \ref pathTarget().
53    ///
54    /// A path can be constructed from another path of any type using the
55    /// copy constructor or the assignment operator.
56    ///
57    /// \tparam GR The digraph type in which the path is.
58    template <typename GR>
59    class Path {
60    public:
61
62      /// Type of the underlying digraph.
63      typedef GR Digraph;
64      /// Arc type of the underlying digraph.
65      typedef typename Digraph::Arc Arc;
66
67      class ArcIt;
68
69      /// \brief Default constructor
70      Path() {}
71
72      /// \brief Template copy constructor
73      template <typename CPath>
74      Path(const CPath& cpath) {}
75
76      /// \brief Template assigment operator
77      template <typename CPath>
78      Path& operator=(const CPath& cpath) {
79        ::lemon::ignore_unused_variable_warning(cpath);
80        return *this;
81      }
82
83      /// Length of the path, i.e. the number of arcs on the path.
84      int length() const { return 0;}
85
86      /// Returns whether the path is empty.
87      bool empty() const { return true;}
88
89      /// Resets the path to an empty path.
90      void clear() {}
91
92      /// \brief LEMON style iterator for enumerating the arcs of a path.
93      ///
94      /// LEMON style iterator class for enumerating the arcs of a path.
95      class ArcIt {
96      public:
97        /// Default constructor
98        ArcIt() {}
99        /// Invalid constructor
100        ArcIt(Invalid) {}
101        /// Sets the iterator to the first arc of the given path
102        ArcIt(const Path &) {}
103
104        /// Conversion to \c Arc
105        operator Arc() const { return INVALID; }
106
107        /// Next arc
108        ArcIt& operator++() {return *this;}
109
110        /// Comparison operator
111        bool operator==(const ArcIt&) const {return true;}
112        /// Comparison operator
113        bool operator!=(const ArcIt&) const {return true;}
114        /// Comparison operator
115        bool operator<(const ArcIt&) const {return false;}
116
117      };
118
119      /// \brief Gets the collection of the arcs of the path.
120      ///
121      /// This function can be used for iterating on the
122      /// arcs of the path. It returns a wrapped
123      /// ArcIt, which looks like an STL container
124      /// (by having begin() and end()) which you can use in range-based
125      /// for loops, STL algorithms, etc.
126      /// For example you can write:
127      ///\code
128      /// for(auto a: p.arcs())
129      ///   doSomething(a);
130      ///\endcode
131      LemonRangeWrapper1<ArcIt, Path> arcs() const {
132        return LemonRangeWrapper1<ArcIt, Path>(*this);
133      }
134
135
136      template <typename _Path>
137      struct Constraints {
138        void constraints() {
139          Path<Digraph> pc;
140          _Path p, pp(pc);
141          int l = p.length();
142          int e = p.empty();
143          p.clear();
144
145          p = pc;
146
147          typename _Path::ArcIt id, ii(INVALID), i(p);
148
149          ++i;
150          typename Digraph::Arc ed = i;
151
152          e = (i == ii);
153          e = (i != ii);
154          e = (i < ii);
155
156          ::lemon::ignore_unused_variable_warning(l);
157          ::lemon::ignore_unused_variable_warning(pp);
158          ::lemon::ignore_unused_variable_warning(e);
159          ::lemon::ignore_unused_variable_warning(id);
160          ::lemon::ignore_unused_variable_warning(ii);
161          ::lemon::ignore_unused_variable_warning(ed);
162        }
163      };
164
165    };
166
167    namespace _path_bits {
168
169      template <typename _Digraph, typename _Path, typename RevPathTag = void>
170      struct PathDumperConstraints {
171        void constraints() {
172          int l = p.length();
173          int e = p.empty();
174
175          typename _Path::ArcIt id, i(p);
176
177          ++i;
178          typename _Digraph::Arc ed = i;
179
180          e = (i == INVALID);
181          e = (i != INVALID);
182
183          ::lemon::ignore_unused_variable_warning(l);
184          ::lemon::ignore_unused_variable_warning(e);
185          ::lemon::ignore_unused_variable_warning(id);
186          ::lemon::ignore_unused_variable_warning(ed);
187        }
188        _Path& p;
189        PathDumperConstraints() {}
190      };
191
192      template <typename _Digraph, typename _Path>
193      struct PathDumperConstraints<
194        _Digraph, _Path,
195        typename enable_if<typename _Path::RevPathTag, void>::type
196      > {
197        void constraints() {
198          int l = p.length();
199          int e = p.empty();
200
201          typename _Path::RevArcIt id, i(p);
202
203          ++i;
204          typename _Digraph::Arc ed = i;
205
206          e = (i == INVALID);
207          e = (i != INVALID);
208
209          ::lemon::ignore_unused_variable_warning(l);
210          ::lemon::ignore_unused_variable_warning(e);
211          ::lemon::ignore_unused_variable_warning(id);
212          ::lemon::ignore_unused_variable_warning(ed);
213        }
214        _Path& p;
215        PathDumperConstraints() {}
216      };
217
218    }
219
220
221    /// \brief A skeleton structure for path dumpers.
222    ///
223    /// A skeleton structure for path dumpers. The path dumpers are
224    /// the generalization of the paths, they can enumerate the arcs
225    /// of the path either in forward or in backward order.
226    /// These classes are typically not used directly, they are rather
227    /// used to be assigned to a real path type.
228    ///
229    /// The main purpose of this concept is that the shortest path
230    /// algorithms can enumerate the arcs easily in reverse order.
231    /// In LEMON, such algorithms give back a (reverse) path dumper that
232    /// can be assigned to a real path. The dumpers can be implemented as
233    /// an adaptor class to the predecessor map.
234    ///
235    /// \tparam GR The digraph type in which the path is.
236    template <typename GR>
237    class PathDumper {
238    public:
239
240      /// Type of the underlying digraph.
241      typedef GR Digraph;
242      /// Arc type of the underlying digraph.
243      typedef typename Digraph::Arc Arc;
244
245      /// Length of the path, i.e. the number of arcs on the path.
246      int length() const { return 0;}
247
248      /// Returns whether the path is empty.
249      bool empty() const { return true;}
250
251      /// \brief Forward or reverse dumping
252      ///
253      /// If this tag is defined to be \c True, then reverse dumping
254      /// is provided in the path dumper. In this case, \c RevArcIt
255      /// iterator should be implemented instead of \c ArcIt iterator.
256      typedef False RevPathTag;
257
258      /// \brief LEMON style iterator for enumerating the arcs of a path.
259      ///
260      /// LEMON style iterator class for enumerating the arcs of a path.
261      class ArcIt {
262      public:
263        /// Default constructor
264        ArcIt() {}
265        /// Invalid constructor
266        ArcIt(Invalid) {}
267        /// Sets the iterator to the first arc of the given path
268        ArcIt(const PathDumper&) {}
269
270        /// Conversion to \c Arc
271        operator Arc() const { return INVALID; }
272
273        /// Next arc
274        ArcIt& operator++() {return *this;}
275
276        /// Comparison operator
277        bool operator==(const ArcIt&) const {return true;}
278        /// Comparison operator
279        bool operator!=(const ArcIt&) const {return true;}
280        /// Comparison operator
281        bool operator<(const ArcIt&) const {return false;}
282
283      };
284
285      /// \brief Gets the collection of the arcs of the path.
286      ///
287      /// This function can be used for iterating on the
288      /// arcs of the path. It returns a wrapped
289      /// ArcIt, which looks like an STL container
290      /// (by having begin() and end()) which you can use in range-based
291      /// for loops, STL algorithms, etc.
292      /// For example you can write:
293      ///\code
294      /// for(auto a: p.arcs())
295      ///   doSomething(a);
296      ///\endcode
297      LemonRangeWrapper1<ArcIt, PathDumper> arcs() const {
298        return LemonRangeWrapper1<ArcIt, PathDumper>(*this);
299      }
300
301
302      /// \brief LEMON style iterator for enumerating the arcs of a path
303      /// in reverse direction.
304      ///
305      /// LEMON style iterator class for enumerating the arcs of a path
306      /// in reverse direction.
307      class RevArcIt {
308      public:
309        /// Default constructor
310        RevArcIt() {}
311        /// Invalid constructor
312        RevArcIt(Invalid) {}
313        /// Sets the iterator to the last arc of the given path
314        RevArcIt(const PathDumper &) {}
315
316        /// Conversion to \c Arc
317        operator Arc() const { return INVALID; }
318
319        /// Next arc
320        RevArcIt& operator++() {return *this;}
321
322        /// Comparison operator
323        bool operator==(const RevArcIt&) const {return true;}
324        /// Comparison operator
325        bool operator!=(const RevArcIt&) const {return true;}
326        /// Comparison operator
327        bool operator<(const RevArcIt&) const {return false;}
328
329      };
330
331      /// \brief Gets the collection of the arcs of the path
332      /// in reverse direction.
333      ///
334      /// This function can be used for iterating on the
335      /// arcs of the path in reverse direction. It returns a wrapped
336      /// RevArcIt, which looks like an STL container
337      /// (by having begin() and end()) which you can use in range-based
338      /// for loops, STL algorithms, etc.
339      /// For example you can write:
340      ///\code
341      /// for(auto a: p.revArcs())
342      ///   doSomething(a);
343      ///\endcode
344      LemonRangeWrapper1<RevArcIt, PathDumper> revArcs() const {
345        return LemonRangeWrapper1<RevArcIt, PathDumper>(*this);
346      }
347
348
349      template <typename _Path>
350      struct Constraints {
351        void constraints() {
352          function_requires<_path_bits::
353            PathDumperConstraints<Digraph, _Path> >();
354        }
355      };
356
357    };
358
359
360    ///@}
361  }
362
363} // namespace lemon
364
365#endif
Note: See TracBrowser for help on using the repository browser.