COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concepts/path.h @ 2357:5365600a7a5c

Last change on this file since 2357:5365600a7a5c was 2357:5365600a7a5c, checked in by Balazs Dezso, 16 years ago

Some bug fix
RevIt? => RevEdgeIt? renaming

File size: 8.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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 graphs.
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 graph.
40    ///
41    /// A skeleton structure for representing directed paths in a
42    /// graph. 
43    /// \param _Graph The graph type in which the path is.
44    ///
45    /// In a sense, the path can be treated as a list of edges. 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 _Graph>
51    class Path {
52    public:
53
54      /// Type of the underlying graph.
55      typedef _Graph Graph;
56      /// Edge type of the underlying graph.
57      typedef typename Graph::Edge Edge;
58
59      class EdgeIt;
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 edges 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 edges
82      ///
83      /// This class is used to iterate on the edges of the paths.
84      class EdgeIt {
85      public:
86        /// Default constructor
87        EdgeIt() {}
88        /// Invalid constructor
89        EdgeIt(Invalid) {}
90        /// Constructor for first edge
91        EdgeIt(const Path &) {}
92
93        /// Conversion to Edge
94        operator Edge() const { return INVALID; }
95
96        /// Next edge
97        EdgeIt& operator++() {return *this;}
98
99        /// Comparison operator
100        bool operator==(const EdgeIt&) const {return true;}
101        /// Comparison operator
102        bool operator!=(const EdgeIt&) const {return true;}
103        /// Comparison operator
104        bool operator<(const EdgeIt&) const {return false;}
105
106      };
107
108      template <typename _Path>
109      struct Constraints {
110        void constraints() {
111          Path<Graph> 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::EdgeIt id, ii(INVALID), i(p);
120
121          ++i;
122          typename Graph::Edge 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 _Graph, 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::EdgeIt id, ii(INVALID), i(p);
148
149          ++i;
150          typename _Graph::Edge ed = i;
151
152          e = (i == ii);
153          e = (i != ii);
154          e = (i < ii);
155
156          ignore_unused_variable_warning(l);
157          ignore_unused_variable_warning(e);
158          ignore_unused_variable_warning(id);
159          ignore_unused_variable_warning(ii);
160          ignore_unused_variable_warning(ed);
161        }
162        _Path& p;
163      };
164
165      template <typename _Graph, typename _Path>
166      struct PathDumperConstraints<
167        _Graph, _Path,
168        typename enable_if<typename _Path::RevPathTag, void>::type
169      > {
170        void constraints() {
171          int l = p.length();
172          int e = p.empty();
173
174          typename _Path::RevEdgeIt id, ii(INVALID), i(p);
175
176          ++i;
177          typename _Graph::Edge ed = i;
178
179          e = (i == ii);
180          e = (i != ii);
181          e = (i < ii);
182
183          ignore_unused_variable_warning(l);
184          ignore_unused_variable_warning(e);
185          ignore_unused_variable_warning(id);
186          ignore_unused_variable_warning(ii);
187          ignore_unused_variable_warning(ed);
188        }
189        _Path& p;
190      };
191   
192    }
193
194
195    /// \brief A skeleton structure for path dumpers.
196    ///
197    /// A skeleton structure for path dumpers. The path dumpers are
198    /// the generalization of the paths. The path dumpers can
199    /// enumerate the edges of the path wheter in forward or in
200    /// backward order.  In most time these classes are not used
201    /// directly rather it used to assign a dumped class to a real
202    /// path type.
203    ///
204    /// The main purpose of this concept is that the shortest path
205    /// algorithms can enumerate easily the edges in reverse order.
206    /// If we would like to give back a real path from these
207    /// algorithms then we should create a temporarly path object. In
208    /// Lemon such algorithms gives back a path dumper what can
209    /// assigned to a real path and the dumpers can be implemented as
210    /// an adaptor class to the predecessor map.
211
212    /// \param _Graph  The graph type in which the path is.
213    ///
214    /// The paths can be constructed from any path type by a
215    /// template constructor or a template assignment operator.
216    ///
217    template <typename _Graph>
218    class PathDumper {
219    public:
220
221      /// Type of the underlying graph.
222      typedef _Graph Graph;
223      /// Edge type of the underlying graph.
224      typedef typename Graph::Edge Edge;
225
226      /// Length of the path ie. the number of edges in the path.
227      int length() const { return 0;}
228
229      /// Returns whether the path is empty.
230      bool empty() const { return true;}
231
232      /// \brief Forward or reverse dumping
233      ///
234      /// If the RevPathTag is defined and true then reverse dumping
235      /// is provided in the path dumper. In this case instead of the
236      /// EdgeIt the RevEdgeIt iterator should be implemented in the
237      /// dumper.
238      typedef False RevPathTag;
239
240      /// \brief Lemon style iterator for path edges
241      ///
242      /// This class is used to iterate on the edges of the paths.
243      class EdgeIt {
244      public:
245        /// Default constructor
246        EdgeIt() {}
247        /// Invalid constructor
248        EdgeIt(Invalid) {}
249        /// Constructor for first edge
250        EdgeIt(const PathDumper&) {}
251
252        /// Conversion to Edge
253        operator Edge() const { return INVALID; }
254
255        /// Next edge
256        EdgeIt& operator++() {return *this;}
257
258        /// Comparison operator
259        bool operator==(const EdgeIt&) const {return true;}
260        /// Comparison operator
261        bool operator!=(const EdgeIt&) const {return true;}
262        /// Comparison operator
263        bool operator<(const EdgeIt&) const {return false;}
264
265      };
266
267      /// \brief Lemon style iterator for path edges
268      ///
269      /// This class is used to iterate on the edges of the paths in
270      /// reverse direction.
271      class RevEdgeIt {
272      public:
273        /// Default constructor
274        RevEdgeIt() {}
275        /// Invalid constructor
276        RevEdgeIt(Invalid) {}
277        /// Constructor for first edge
278        RevEdgeIt(const PathDumper &) {}
279
280        /// Conversion to Edge
281        operator Edge() const { return INVALID; }
282
283        /// Next edge
284        RevEdgeIt& operator++() {return *this;}
285
286        /// Comparison operator
287        bool operator==(const RevEdgeIt&) const {return true;}
288        /// Comparison operator
289        bool operator!=(const RevEdgeIt&) const {return true;}
290        /// Comparison operator
291        bool operator<(const RevEdgeIt&) const {return false;}
292
293      };
294
295      template <typename _Path>
296      struct Constraints {
297        void constraints() {
298          function_requires<_path_bits::
299            PathDumperConstraints<Graph, _Path> >();
300        }
301      };
302
303    };
304
305
306    ///@}
307  }
308
309} // namespace lemon
310
311#endif // LEMON_CONCEPT_PATH_H
Note: See TracBrowser for help on using the repository browser.