COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/concepts/path.h @ 1092:dceba191c00d

Last change on this file since 1092:dceba191c00d was 1092:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

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