COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/path.h @ 160:b1bd0c2a7f57

Last change on this file since 160:b1bd0c2a7f57 was 157:2ccc1afc2c52, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Using \tparam commands + removing \author commands (ticket #29, #39)

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