COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/concepts/path.h

Last change on this file was 1198:2236d00ca778, checked in by Alpar Juttner <alpar@…>, 17 months ago

Merge #615

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