COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/path.h @ 280:e7f8647ce760

Last change on this file since 280:e7f8647ce760 was 280:e7f8647ce760, checked in by Alpar Juttner <alpar@…>, 16 years ago

Remove todo-s and convert them to trac tickets

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