COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/path.h @ 644:2ca0cdb5f366

Last change on this file since 644:2ca0cdb5f366 was 606:c5fd2d996909, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Various doc improvements (#248)

  • Rename all the ugly template parameters (too long and/or starting with an underscore).
  • Rename function parameters starting with an underscore.
  • Extend the doc for many classes.
  • Use LaTeX-style O(...) expressions only for the complicated ones.
  • A lot of small unification changes.
  • Small fixes.
  • Some other improvements.
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-2009
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_CONCEPTS_PATH_H
25#define LEMON_CONCEPTS_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 GR 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 GR>
49    class Path {
50    public:
51
52      /// Type of the underlying digraph.
53      typedef GR 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        ignore_unused_variable_warning(cpath);
70        return *this;
71      }
72
73      /// Length of the path ie. the number of arcs in the path.
74      int length() const { return 0;}
75
76      /// Returns whether the path is empty.
77      bool empty() const { return true;}
78
79      /// Resets the path to an empty path.
80      void clear() {}
81
82      /// \brief LEMON style iterator for path arcs
83      ///
84      /// This class is used to iterate on the arcs of the paths.
85      class ArcIt {
86      public:
87        /// Default constructor
88        ArcIt() {}
89        /// Invalid constructor
90        ArcIt(Invalid) {}
91        /// Constructor for first arc
92        ArcIt(const Path &) {}
93
94        /// Conversion to Arc
95        operator Arc() const { return INVALID; }
96
97        /// Next arc
98        ArcIt& operator++() {return *this;}
99
100        /// Comparison operator
101        bool operator==(const ArcIt&) const {return true;}
102        /// Comparison operator
103        bool operator!=(const ArcIt&) const {return true;}
104        /// Comparison operator
105        bool operator<(const ArcIt&) const {return false;}
106
107      };
108
109      template <typename _Path>
110      struct Constraints {
111        void constraints() {
112          Path<Digraph> pc;
113          _Path p, pp(pc);
114          int l = p.length();
115          int e = p.empty();
116          p.clear();
117
118          p = pc;
119
120          typename _Path::ArcIt id, ii(INVALID), i(p);
121
122          ++i;
123          typename Digraph::Arc ed = i;
124
125          e = (i == ii);
126          e = (i != ii);
127          e = (i < ii);
128
129          ignore_unused_variable_warning(l);
130          ignore_unused_variable_warning(pp);
131          ignore_unused_variable_warning(e);
132          ignore_unused_variable_warning(id);
133          ignore_unused_variable_warning(ii);
134          ignore_unused_variable_warning(ed);
135        }
136      };
137
138    };
139
140    namespace _path_bits {
141
142      template <typename _Digraph, typename _Path, typename RevPathTag = void>
143      struct PathDumperConstraints {
144        void constraints() {
145          int l = p.length();
146          int e = p.empty();
147
148          typename _Path::ArcIt id, i(p);
149
150          ++i;
151          typename _Digraph::Arc ed = i;
152
153          e = (i == INVALID);
154          e = (i != INVALID);
155
156          ignore_unused_variable_warning(l);
157          ignore_unused_variable_warning(e);
158          ignore_unused_variable_warning(id);
159          ignore_unused_variable_warning(ed);
160        }
161        _Path& p;
162      };
163
164      template <typename _Digraph, typename _Path>
165      struct PathDumperConstraints<
166        _Digraph, _Path,
167        typename enable_if<typename _Path::RevPathTag, void>::type
168      > {
169        void constraints() {
170          int l = p.length();
171          int e = p.empty();
172
173          typename _Path::RevArcIt id, i(p);
174
175          ++i;
176          typename _Digraph::Arc ed = i;
177
178          e = (i == INVALID);
179          e = (i != INVALID);
180
181          ignore_unused_variable_warning(l);
182          ignore_unused_variable_warning(e);
183          ignore_unused_variable_warning(id);
184          ignore_unused_variable_warning(ed);
185        }
186        _Path& p;
187      };
188
189    }
190
191
192    /// \brief A skeleton structure for path dumpers.
193    ///
194    /// A skeleton structure for path dumpers. The path dumpers are
195    /// the generalization of the paths. The path dumpers can
196    /// enumerate the arcs of the path wheter in forward or in
197    /// backward order.  In most time these classes are not used
198    /// directly rather it used to assign a dumped class to a real
199    /// path type.
200    ///
201    /// The main purpose of this concept is that the shortest path
202    /// algorithms can enumerate easily the arcs in reverse order.
203    /// If we would like to give back a real path from these
204    /// algorithms then we should create a temporarly path object. In
205    /// LEMON such algorithms gives back a path dumper what can
206    /// assigned to a real path and the dumpers can be implemented as
207    /// an adaptor class to the predecessor map.
208    ///
209    /// \tparam GR The digraph type in which the path is.
210    ///
211    /// The paths can be constructed from any path type by a
212    /// template constructor or a template assignment operator.
213    template <typename GR>
214    class PathDumper {
215    public:
216
217      /// Type of the underlying digraph.
218      typedef GR 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
Note: See TracBrowser for help on using the repository browser.