1 /* -*- C++ -*- |
|
2 * src/lemon/concept/path.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 ///\ingroup concept |
|
18 ///\file |
|
19 ///\brief Classes for representing paths in graphs. |
|
20 /// |
|
21 ///\todo Iterators have obsolete style |
|
22 |
|
23 #ifndef LEMON_CONCEPT_PATH_H |
|
24 #define LEMON_CONCEPT_PATH_H |
|
25 |
|
26 #include <lemon/invalid.h> |
|
27 |
|
28 namespace lemon { |
|
29 namespace concept { |
|
30 /// \addtogroup concept |
|
31 /// @{ |
|
32 |
|
33 |
|
34 //! \brief A skeleton structure for representing directed paths in a graph. |
|
35 //! |
|
36 //! A skeleton structure for representing directed paths in a graph. |
|
37 //! \param GR The graph type in which the path is. |
|
38 //! |
|
39 //! In a sense, the path can be treated as a graph, for it has \c NodeIt |
|
40 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
|
41 //! and \c Edge of the original graph. |
|
42 template<typename GR> |
|
43 class Path { |
|
44 public: |
|
45 |
|
46 /// Type of the underlying graph. |
|
47 typedef /*typename*/ GR Graph; |
|
48 /// Edge type of the underlying graph. |
|
49 typedef typename Graph::Edge GraphEdge; |
|
50 /// Node type of the underlying graph. |
|
51 typedef typename Graph::Node GraphNode; |
|
52 class NodeIt; |
|
53 class EdgeIt; |
|
54 |
|
55 /// \param _G The graph in which the path is. |
|
56 /// |
|
57 Path(const Graph &) {} |
|
58 |
|
59 /// Length of the path. |
|
60 int length() const {return 0;} |
|
61 /// Returns whether the path is empty. |
|
62 bool empty() const { return true;} |
|
63 |
|
64 /// Resets the path to an empty path. |
|
65 void clear() {} |
|
66 |
|
67 /// \brief Starting point of the path. |
|
68 /// |
|
69 /// Starting point of the path. |
|
70 /// Returns INVALID if the path is empty. |
|
71 GraphNode/*It*/ target() const {return INVALID;} |
|
72 /// \brief End point of the path. |
|
73 /// |
|
74 /// End point of the path. |
|
75 /// Returns INVALID if the path is empty. |
|
76 GraphNode/*It*/ source() const {return INVALID;} |
|
77 |
|
78 /// \brief First NodeIt/EdgeIt. |
|
79 /// |
|
80 /// Initializes node or edge iterator to point to the first |
|
81 /// node or edge. |
|
82 template<typename It> |
|
83 It& first(It &i) const { return i=It(*this); } |
|
84 |
|
85 /// \brief The target of an edge. |
|
86 /// |
|
87 /// Returns node iterator pointing to the target node of the |
|
88 /// given edge iterator. |
|
89 NodeIt target(const EdgeIt&) const {return INVALID;} |
|
90 |
|
91 /// \brief The source of an edge. |
|
92 /// |
|
93 /// Returns node iterator pointing to the source node of the |
|
94 /// given edge iterator. |
|
95 NodeIt source(const EdgeIt&) const {return INVALID;} |
|
96 |
|
97 |
|
98 /* Iterator classes */ |
|
99 |
|
100 /** |
|
101 * \brief Iterator class to iterate on the edges of the paths |
|
102 * |
|
103 * This class is used to iterate on the edges of the paths |
|
104 * |
|
105 * Of course it converts to Graph::Edge |
|
106 * |
|
107 */ |
|
108 class EdgeIt { |
|
109 public: |
|
110 /// Default constructor |
|
111 EdgeIt() {} |
|
112 /// Invalid constructor |
|
113 EdgeIt(Invalid) {} |
|
114 /// Constructor with starting point |
|
115 EdgeIt(const Path &) {} |
|
116 |
|
117 operator GraphEdge () const {} |
|
118 |
|
119 /// Next edge |
|
120 EdgeIt& operator++() {return *this;} |
|
121 |
|
122 /// Comparison operator |
|
123 bool operator==(const EdgeIt&) const {return true;} |
|
124 /// Comparison operator |
|
125 bool operator!=(const EdgeIt&) const {return true;} |
|
126 // /// Comparison operator |
|
127 // /// \todo It is not clear what is the "natural" ordering. |
|
128 // bool operator<(const EdgeIt& e) const {} |
|
129 |
|
130 }; |
|
131 |
|
132 /** |
|
133 * \brief Iterator class to iterate on the nodes of the paths |
|
134 * |
|
135 * This class is used to iterate on the nodes of the paths |
|
136 * |
|
137 * Of course it converts to Graph::Node. |
|
138 * |
|
139 */ |
|
140 class NodeIt { |
|
141 public: |
|
142 /// Default constructor |
|
143 NodeIt() {} |
|
144 /// Invalid constructor |
|
145 NodeIt(Invalid) {} |
|
146 /// Constructor with starting point |
|
147 NodeIt(const Path &) {} |
|
148 |
|
149 ///Conversion to Graph::Node |
|
150 operator const GraphNode& () const {} |
|
151 /// Next node |
|
152 NodeIt& operator++() {return *this;} |
|
153 |
|
154 /// Comparison operator |
|
155 bool operator==(const NodeIt&) const {return true;} |
|
156 /// Comparison operator |
|
157 bool operator!=(const NodeIt&) const {return true;} |
|
158 // /// Comparison operator |
|
159 // /// \todo It is not clear what is the "natural" ordering. |
|
160 // bool operator<(const NodeIt& e) const {} |
|
161 |
|
162 }; |
|
163 |
|
164 friend class Builder; |
|
165 |
|
166 /** |
|
167 * \brief Class to build paths |
|
168 * |
|
169 * This class is used to fill a path with edges. |
|
170 * |
|
171 * You can push new edges to the front and to the back of the path in |
|
172 * arbitrary order then you should commit these changes to the graph. |
|
173 * |
|
174 * While the builder is active (after the first modifying |
|
175 * operation and until the call of \ref commit()) the |
|
176 * underlining Path is in a "transitional" state (operations on |
|
177 * it have undefined result). |
|
178 */ |
|
179 class Builder { |
|
180 public: |
|
181 |
|
182 Path &P; |
|
183 |
|
184 ///\param _P the path you want to fill in. |
|
185 /// |
|
186 |
|
187 Builder(Path &_p) : P(_p) {} |
|
188 |
|
189 /// Sets the starting node of the path. |
|
190 |
|
191 /// Sets the starting node of the path. Edge added to the path |
|
192 /// afterwards have to be incident to this node. |
|
193 /// You \em must start building an empty path with these functions. |
|
194 /// (And you \em must \em not use it later). |
|
195 /// \sa pushFront() |
|
196 /// \sa pushBack() |
|
197 void setStartNode(const GraphNode &) {} |
|
198 |
|
199 ///Push a new edge to the front of the path |
|
200 |
|
201 ///Push a new edge to the front of the path. |
|
202 ///If the path is empty, you \em must call \ref setStartNode() before |
|
203 ///the first use of \ref pushFront(). |
|
204 void pushFront(const GraphEdge&) {} |
|
205 |
|
206 ///Push a new edge to the back of the path |
|
207 |
|
208 ///Push a new edge to the back of the path. |
|
209 ///If the path is empty, you \em must call \ref setStartNode() before |
|
210 ///the first use of \ref pushBack(). |
|
211 void pushBack(const GraphEdge&) {} |
|
212 |
|
213 ///Commit the changes to the path. |
|
214 void commit() {} |
|
215 |
|
216 ///Reserve (front) storage for the builder in advance. |
|
217 |
|
218 ///If you know a reasonable upper bound on the number of the edges |
|
219 ///to add to the front of the path, |
|
220 ///using this function you may speed up the building. |
|
221 void reserveFront(size_t) {} |
|
222 ///Reserve (back) storage for the builder in advance. |
|
223 |
|
224 ///If you know a reasonable upper bound on the number of the edges |
|
225 ///to add to the back of the path, |
|
226 ///using this function you may speed up the building. |
|
227 void reserveBack(size_t) {} |
|
228 }; |
|
229 }; |
|
230 |
|
231 ///@} |
|
232 } |
|
233 |
|
234 } // namespace lemon |
|
235 |
|
236 #endif // LEMON_CONCEPT_PATH_H |
|