COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/path.h @ 236:da953e387d31

Last change on this file since 236:da953e387d31 was 236:da953e387d31, checked in by Akos Ladanyi <ladanyi@…>, 16 years ago

Unify the spelling of LEMON (#103).

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