COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/concepts/path.h @ 278:931190050520

Last change on this file since 278:931190050520 was 278:931190050520, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

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