COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/path.h

Last change on this file was 1416:f179aa1045a4, checked in by Peter Kovacs <kpeter@…>, 10 months ago

Suppress unused typdef warnings (#615)

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