[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 | |
---|
| 31 | namespace 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 |
---|