36 /// \brief A skeleton structure for representing directed paths in |
36 /// \brief A skeleton structure for representing directed paths in |
37 /// a digraph. |
37 /// a digraph. |
38 /// |
38 /// |
39 /// A skeleton structure for representing directed paths in a |
39 /// A skeleton structure for representing directed paths in a |
40 /// digraph. |
40 /// digraph. |
|
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 /// |
41 /// \tparam GR The digraph type in which the path is. |
56 /// \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> |
57 template <typename GR> |
49 class Path { |
58 class Path { |
50 public: |
59 public: |
51 |
60 |
52 /// Type of the underlying digraph. |
61 /// Type of the underlying digraph. |
57 class ArcIt; |
66 class ArcIt; |
58 |
67 |
59 /// \brief Default constructor |
68 /// \brief Default constructor |
60 Path() {} |
69 Path() {} |
61 |
70 |
62 /// \brief Template constructor |
71 /// \brief Template copy constructor |
63 template <typename CPath> |
72 template <typename CPath> |
64 Path(const CPath& cpath) {} |
73 Path(const CPath& cpath) {} |
65 |
74 |
66 /// \brief Template assigment |
75 /// \brief Template assigment operator |
67 template <typename CPath> |
76 template <typename CPath> |
68 Path& operator=(const CPath& cpath) { |
77 Path& operator=(const CPath& cpath) { |
69 ignore_unused_variable_warning(cpath); |
78 ignore_unused_variable_warning(cpath); |
70 return *this; |
79 return *this; |
71 } |
80 } |
72 |
81 |
73 /// Length of the path ie. the number of arcs in the path. |
82 /// Length of the path, i.e. the number of arcs on the path. |
74 int length() const { return 0;} |
83 int length() const { return 0;} |
75 |
84 |
76 /// Returns whether the path is empty. |
85 /// Returns whether the path is empty. |
77 bool empty() const { return true;} |
86 bool empty() const { return true;} |
78 |
87 |
79 /// Resets the path to an empty path. |
88 /// Resets the path to an empty path. |
80 void clear() {} |
89 void clear() {} |
81 |
90 |
82 /// \brief LEMON style iterator for path arcs |
91 /// \brief LEMON style iterator for enumerating the arcs of a path. |
83 /// |
92 /// |
84 /// This class is used to iterate on the arcs of the paths. |
93 /// LEMON style iterator class for enumerating the arcs of a path. |
85 class ArcIt { |
94 class ArcIt { |
86 public: |
95 public: |
87 /// Default constructor |
96 /// Default constructor |
88 ArcIt() {} |
97 ArcIt() {} |
89 /// Invalid constructor |
98 /// Invalid constructor |
90 ArcIt(Invalid) {} |
99 ArcIt(Invalid) {} |
91 /// Constructor for first arc |
100 /// Sets the iterator to the first arc of the given path |
92 ArcIt(const Path &) {} |
101 ArcIt(const Path &) {} |
93 |
102 |
94 /// Conversion to Arc |
103 /// Conversion to \c Arc |
95 operator Arc() const { return INVALID; } |
104 operator Arc() const { return INVALID; } |
96 |
105 |
97 /// Next arc |
106 /// Next arc |
98 ArcIt& operator++() {return *this;} |
107 ArcIt& operator++() {return *this;} |
99 |
108 |
190 |
199 |
191 |
200 |
192 /// \brief A skeleton structure for path dumpers. |
201 /// \brief A skeleton structure for path dumpers. |
193 /// |
202 /// |
194 /// A skeleton structure for path dumpers. The path dumpers are |
203 /// A skeleton structure for path dumpers. The path dumpers are |
195 /// the generalization of the paths. The path dumpers can |
204 /// the generalization of the paths, they can enumerate the arcs |
196 /// enumerate the arcs of the path wheter in forward or in |
205 /// of the path either in forward or in backward order. |
197 /// backward order. In most time these classes are not used |
206 /// These classes are typically not used directly, they are rather |
198 /// directly rather it used to assign a dumped class to a real |
207 /// used to be assigned to a real path type. |
199 /// path type. |
|
200 /// |
208 /// |
201 /// The main purpose of this concept is that the shortest path |
209 /// The main purpose of this concept is that the shortest path |
202 /// algorithms can enumerate easily the arcs in reverse order. |
210 /// algorithms can enumerate the arcs easily in reverse order. |
203 /// If we would like to give back a real path from these |
211 /// In LEMON, such algorithms give back a (reverse) path dumper that |
204 /// algorithms then we should create a temporarly path object. In |
212 /// can be assigned to a real path. The dumpers can be implemented as |
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. |
213 /// an adaptor class to the predecessor map. |
208 /// |
214 /// |
209 /// \tparam GR The digraph type in which the path is. |
215 /// \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> |
216 template <typename GR> |
214 class PathDumper { |
217 class PathDumper { |
215 public: |
218 public: |
216 |
219 |
217 /// Type of the underlying digraph. |
220 /// Type of the underlying digraph. |
218 typedef GR Digraph; |
221 typedef GR Digraph; |
219 /// Arc type of the underlying digraph. |
222 /// Arc type of the underlying digraph. |
220 typedef typename Digraph::Arc Arc; |
223 typedef typename Digraph::Arc Arc; |
221 |
224 |
222 /// Length of the path ie. the number of arcs in the path. |
225 /// Length of the path, i.e. the number of arcs on the path. |
223 int length() const { return 0;} |
226 int length() const { return 0;} |
224 |
227 |
225 /// Returns whether the path is empty. |
228 /// Returns whether the path is empty. |
226 bool empty() const { return true;} |
229 bool empty() const { return true;} |
227 |
230 |
228 /// \brief Forward or reverse dumping |
231 /// \brief Forward or reverse dumping |
229 /// |
232 /// |
230 /// If the RevPathTag is defined and true then reverse dumping |
233 /// If this tag is defined to be \c True, then reverse dumping |
231 /// is provided in the path dumper. In this case instead of the |
234 /// is provided in the path dumper. In this case, \c RevArcIt |
232 /// ArcIt the RevArcIt iterator should be implemented in the |
235 /// iterator should be implemented instead of \c ArcIt iterator. |
233 /// dumper. |
|
234 typedef False RevPathTag; |
236 typedef False RevPathTag; |
235 |
237 |
236 /// \brief LEMON style iterator for path arcs |
238 /// \brief LEMON style iterator for enumerating the arcs of a path. |
237 /// |
239 /// |
238 /// This class is used to iterate on the arcs of the paths. |
240 /// LEMON style iterator class for enumerating the arcs of a path. |
239 class ArcIt { |
241 class ArcIt { |
240 public: |
242 public: |
241 /// Default constructor |
243 /// Default constructor |
242 ArcIt() {} |
244 ArcIt() {} |
243 /// Invalid constructor |
245 /// Invalid constructor |
244 ArcIt(Invalid) {} |
246 ArcIt(Invalid) {} |
245 /// Constructor for first arc |
247 /// Sets the iterator to the first arc of the given path |
246 ArcIt(const PathDumper&) {} |
248 ArcIt(const PathDumper&) {} |
247 |
249 |
248 /// Conversion to Arc |
250 /// Conversion to \c Arc |
249 operator Arc() const { return INVALID; } |
251 operator Arc() const { return INVALID; } |
250 |
252 |
251 /// Next arc |
253 /// Next arc |
252 ArcIt& operator++() {return *this;} |
254 ArcIt& operator++() {return *this;} |
253 |
255 |
258 /// Comparison operator |
260 /// Comparison operator |
259 bool operator<(const ArcIt&) const {return false;} |
261 bool operator<(const ArcIt&) const {return false;} |
260 |
262 |
261 }; |
263 }; |
262 |
264 |
263 /// \brief LEMON style iterator for path arcs |
265 /// \brief LEMON style iterator for enumerating the arcs of a path |
|
266 /// in reverse direction. |
264 /// |
267 /// |
265 /// This class is used to iterate on the arcs of the paths in |
268 /// LEMON style iterator class for enumerating the arcs of a path |
266 /// reverse direction. |
269 /// in reverse direction. |
267 class RevArcIt { |
270 class RevArcIt { |
268 public: |
271 public: |
269 /// Default constructor |
272 /// Default constructor |
270 RevArcIt() {} |
273 RevArcIt() {} |
271 /// Invalid constructor |
274 /// Invalid constructor |
272 RevArcIt(Invalid) {} |
275 RevArcIt(Invalid) {} |
273 /// Constructor for first arc |
276 /// Sets the iterator to the last arc of the given path |
274 RevArcIt(const PathDumper &) {} |
277 RevArcIt(const PathDumper &) {} |
275 |
278 |
276 /// Conversion to Arc |
279 /// Conversion to \c Arc |
277 operator Arc() const { return INVALID; } |
280 operator Arc() const { return INVALID; } |
278 |
281 |
279 /// Next arc |
282 /// Next arc |
280 RevArcIt& operator++() {return *this;} |
283 RevArcIt& operator++() {return *this;} |
281 |
284 |