1 // -*- c++ -*- // |
1 // -*- c++ -*- // |
2 |
2 |
3 ///ingroup datas |
3 ///\ingroup datas |
4 ///\file |
4 ///\file |
5 ///\brief Class for representing paths in graphs. |
5 ///\brief Classes for representing paths in graphs. |
6 |
6 |
7 #ifndef HUGO_PATH_H |
7 #ifndef HUGO_PATH_H |
8 #define HUGO_PATH_H |
8 #define HUGO_PATH_H |
9 |
9 |
10 #include <deque> |
10 #include <deque> |
11 #include <vector> |
11 #include <vector> |
12 #include <algorithm> |
12 #include <algorithm> |
13 |
13 |
14 #include <invalid.h> |
14 #include <invalid.h> |
|
15 #include <error.h> |
|
16 #include <debug.h> |
15 |
17 |
16 namespace hugo { |
18 namespace hugo { |
17 |
19 |
18 /// \addtogroup datas |
20 /// \addtogroup datas |
19 /// @{ |
21 /// @{ |
20 |
22 |
21 ///A container for directed paths |
23 |
22 |
24 //! \brief A structure for representing directed path in a graph. |
23 ///\param Graph The graph type in which the path is. |
25 //! |
24 /// |
26 //! \param Graph The graph type in which the path is. |
25 ///In a sense, the path can be treated as a graph, for is has \c NodeIt |
27 //! \param DM DebugMode, defaults to DefaultDebugMode. |
26 ///and \c EdgeIt with the same usage. These types converts to the \c Node |
28 //! |
27 ///and \c Edge of the original graph. |
29 //! In a sense, the path can be treated as a graph, for is has \c NodeIt |
28 ///\todo How to clear a path? |
30 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
29 ///\todo Clarify the consistency checks to do. |
31 //! and \c Edge of the original graph. |
30 template<typename Graph> |
32 //! |
|
33 //! \todo Thoroughfully check all the range and consistency tests. |
|
34 template<typename Graph, typename DM = DefaultDebugMode> |
31 class DirPath { |
35 class DirPath { |
32 public: |
36 public: |
33 typedef typename Graph::Edge GraphEdge; |
37 typedef typename Graph::Edge GraphEdge; |
34 typedef typename Graph::Node GraphNode; |
38 typedef typename Graph::Node GraphNode; |
35 class NodeIt; |
39 class NodeIt; |
40 typedef std::vector<GraphEdge> Container; |
44 typedef std::vector<GraphEdge> Container; |
41 Container edges; |
45 Container edges; |
42 |
46 |
43 public: |
47 public: |
44 |
48 |
45 /// Constructor |
|
46 |
|
47 /// \param _G The graph in which the path is. |
49 /// \param _G The graph in which the path is. |
48 /// |
50 /// |
49 DirPath(const Graph &_G) : gr(&_G) {} |
51 DirPath(const Graph &_G) : gr(&_G) {} |
50 |
52 |
|
53 /// \brief Subpath constructor. |
|
54 /// |
51 /// Subpath defined by two nodes. |
55 /// Subpath defined by two nodes. |
52 /// \warning It is an error if the two edges are not in order! |
56 /// \warning It is an error if the two edges are not in order! |
|
57 /// \todo Implement! |
53 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); |
58 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); |
|
59 /// \brief Subpath constructor. |
|
60 /// |
54 /// Subpath defined by two edges. Contains edges in [a,b) |
61 /// Subpath defined by two edges. Contains edges in [a,b) |
55 /// \warning It is an error if the two edges are not in order! |
62 /// \warning It is an error if the two edges are not in order! |
|
63 /// \todo Implement! |
56 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); |
64 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); |
57 |
65 |
|
66 /// Length of the path. |
58 size_t length() const { return edges.size(); } |
67 size_t length() const { return edges.size(); } |
|
68 /// Returns whether the path is empty. |
59 bool empty() const { return edges.empty(); } |
69 bool empty() const { return edges.empty(); } |
|
70 |
|
71 /// Resets the path to an empty path. |
|
72 void clear() { edges.clear(); } |
|
73 |
|
74 /// \brief Starting point of the path. |
|
75 /// |
|
76 /// Starting point of the path. |
|
77 /// Returns INVALID if the path is empty. |
60 GraphNode from() const { |
78 GraphNode from() const { |
61 return empty() ? INVALID : gr->tail(edges[0]); |
79 return empty() ? INVALID : gr->tail(edges[0]); |
62 } |
80 } |
|
81 /// \brief End point of the path. |
|
82 /// |
|
83 /// End point of the path. |
|
84 /// Returns INVALID if the path is empty. |
63 GraphNode to() const { |
85 GraphNode to() const { |
64 return empty() ? INVALID : gr->head(edges[length()-1]); |
86 return empty() ? INVALID : gr->head(edges[length()-1]); |
65 } |
87 } |
66 |
88 |
|
89 /// \brief Initializes node or edge iterator to point to the first |
|
90 /// node or edge. |
|
91 /// |
|
92 /// \sa nth |
67 template<typename It> |
93 template<typename It> |
68 It& first(It &i) const { return i=It(*this); } |
94 It& first(It &i) const { return i=It(*this); } |
69 |
95 |
|
96 /// \brief Initializes node or edge iterator to point to the node or edge |
|
97 /// of a given index. |
70 template<typename It> |
98 template<typename It> |
71 It& nth(It &i, int n) const { return i=It(*this, n); } |
99 It& nth(It &i, int n) const { |
72 |
100 // FIXME: this test should be different for NodeIt and EdgeIt: |
|
101 if( DM::range_check && (n<0 || n>int(length())) ) |
|
102 fault("DirPath::nth: index out of range"); |
|
103 return i=It(*this, n); |
|
104 } |
|
105 |
|
106 /// Checks validity of a node or edge iterator. |
73 template<typename It> |
107 template<typename It> |
74 bool valid(const It &i) const { return i.valid(); } |
108 bool valid(const It &i) const { return i.valid(); } |
75 |
109 |
|
110 /// Steps the given node or edge iterator. |
76 template<typename It> |
111 template<typename It> |
77 It& next(It &e) const { return ++e; } |
112 It& next(It &e) const { |
78 |
113 if( DM::range_check && !e.valid() ) |
79 /// \todo ! |
114 fault("DirPath::next() on invalid iterator"); |
80 NodeIt head(const EdgeIt& e) const; |
115 return ++e; |
81 NodeIt tail(const EdgeIt& e) const; |
116 } |
|
117 |
|
118 /// \brief Returns node iterator pointing to the head node of the |
|
119 /// given edge iterator. |
|
120 NodeIt head(const EdgeIt& e) const { |
|
121 return NodeIt(*this, e.idx+1); |
|
122 } |
|
123 |
|
124 /// \brief Returns node iterator pointing to the tail node of the |
|
125 /// given edge iterator. |
|
126 NodeIt tail(const EdgeIt& e) const { |
|
127 return NodeIt(*this, e.idx); |
|
128 } |
82 |
129 |
83 |
130 |
84 /*** Iterator classes ***/ |
131 /*** Iterator classes ***/ |
85 class EdgeIt { |
132 class EdgeIt { |
86 friend class DirPath; |
133 friend class DirPath; |
141 void validate() { if( size_t(idx) > p->length() ) idx=-1; } |
188 void validate() { if( size_t(idx) > p->length() ) idx=-1; } |
142 }; |
189 }; |
143 |
190 |
144 friend class Builder; |
191 friend class Builder; |
145 |
192 |
146 ///Class to build paths |
193 /** |
147 |
194 * \brief Class to build paths |
148 ///\ingroup datas |
195 * |
149 ///This class is used to build new paths. |
196 * \ingroup datas |
150 ///You can push new edges to the front and to the back of the path in |
197 * This class is used to fill a path with edges. |
151 ///arbitrary order the you can commit these changes to the graph. |
198 * |
152 ///\todo We must clarify when the path will be in "transitional" state. |
199 * You can push new edges to the front and to the back of the path in |
|
200 * arbitrary order the you can commit these changes to the graph. |
|
201 * |
|
202 * Fundamentally, for most "Paths" (classes fulfilling the |
|
203 * PathConcept) while the builder is active (after the first modifying |
|
204 * operation and until the commit()) the original Path is in a |
|
205 * "transitional" state (operations ot it have undefined result). But |
|
206 * in the case of DirPath the original path is unchanged until the |
|
207 * commit. However we don't recomend that you use this feature. |
|
208 */ |
153 class Builder { |
209 class Builder { |
154 DirPath &P; |
210 DirPath &P; |
155 Container d; |
211 Container front, back; |
156 |
212 |
157 public: |
213 public: |
158 ///Constructor |
214 ///\param _P the path you want to fill in. |
159 |
|
160 ///\param _P the path you want to build. |
|
161 /// |
215 /// |
162 Builder(DirPath &_P) : P(_P) {} |
216 Builder(DirPath &_P) : P(_P) {} |
163 |
217 |
164 ///Set the first node of the path. |
218 ///Sets the first node of the path. |
165 |
219 |
166 ///Set the first node of the path. |
220 ///Sets the first node of the path. If the path is empty, this |
167 ///If the path is empty, this must be call before any call of |
221 ///function or setTo() have to be called before any call to \ref |
168 ///\ref pushFront() or \ref pushBack() |
222 ///pushFront() or \ref pushBack() |
169 void setFirst(const GraphNode &) { } |
223 void setFrom(const GraphNode &) {} |
|
224 |
|
225 ///Sets the last node of the path. |
|
226 |
|
227 ///Sets the last node of the path. If the path is empty, this |
|
228 ///function or setFrom() have to be called before any call of \ref |
|
229 ///pushFront() or \ref pushBack() |
|
230 void setTo(const GraphNode &) {} |
170 |
231 |
171 ///Push a new edge to the front of the path |
232 ///Push a new edge to the front of the path |
172 |
233 |
173 ///Push a new edge to the front of the path. |
234 ///Push a new edge to the front of the path. |
174 ///\sa setFirst() |
235 ///\sa setTo |
175 bool pushFront(const GraphEdge& e) { |
236 void pushFront(const GraphEdge& e) { |
176 if( empty() || P.gr->head(e)==from() ) { |
237 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) { |
177 d.push_back(e); |
238 fault("DirPath::Builder::pushFront: nonincident edge"); |
178 return true; |
|
179 } |
239 } |
180 return false; |
240 front.push_back(e); |
181 } |
241 } |
|
242 |
182 ///Push a new edge to the back of the path |
243 ///Push a new edge to the back of the path |
183 |
244 |
184 ///Push a new edge to the back of the path. |
245 ///Push a new edge to the back of the path. |
185 ///\sa setFirst() |
246 ///\sa setFrom |
186 bool pushBack(const GraphEdge& e) { |
247 void pushBack(const GraphEdge& e) { |
187 if( empty() || P.gr->tail(e)==to() ) { |
248 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) { |
188 P.edges.push_back(e); |
249 fault("DirPath::Builder::pushBack: nonincident edge"); |
189 return true; |
|
190 } |
250 } |
191 return false; |
251 back.push_back(e); |
192 } |
252 } |
193 |
253 |
194 ///Commit the changes to the path. |
254 ///Commit the changes to the path. |
195 void commit() { |
255 void commit() { |
196 if( !d.empty() ) { |
256 if( !(front.empty() && back.empty()) ) { |
197 P.edges.insert(P.edges.begin(), d.rbegin(), d.rend()); |
257 Container tmp; |
198 d.clear(); |
258 tmp.reserve(front.size()+back.size()+P.length()); |
|
259 tmp.insert(tmp.end(), front.rbegin(), front.rend()); |
|
260 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); |
|
261 tmp.insert(tmp.end(), back.begin(), back.end()); |
|
262 P.edges.swap(tmp); |
|
263 front.clear(); |
|
264 back.clear(); |
199 } |
265 } |
200 } |
266 } |
201 |
267 |
202 ///Desctuctor |
268 // ///Desctuctor |
203 |
269 |
204 ///The desctuctor. |
270 // ///The desctuctor. |
205 ///It commit also commit the changes. |
271 // ///It commit also commit the changes. |
206 ///\todo Is this what we want? |
272 // ///\todo Is this what we want? |
207 ~Builder() { commit(); } |
273 // Nope. Let's use commit() explicitly. |
|
274 // ~Builder() { commit(); } |
208 |
275 |
209 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? |
276 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? |
210 // Hogy kenyelmes egy ilyet hasznalni? |
277 // Hogy kenyelmes egy ilyet hasznalni? |
211 void reserve(size_t r) { |
278 void reserve(size_t r) { |
212 d.reserve(r); |
279 front.reserve(r); |
213 P.edges.reserve(P.length()+r); |
280 back.reserve(r); |
214 } |
281 } |
215 |
282 |
216 private: |
283 private: |
217 bool empty() { return d.empty() && P.empty(); } |
284 bool empty() { |
|
285 return front.empty() && back.empty() && P.empty(); |
|
286 } |
218 |
287 |
219 GraphNode from() const { |
288 GraphNode from() const { |
220 if( ! d.empty() ) |
289 if( ! front.empty() ) |
221 return P.gr->tail(d[d.size()-1]); |
290 return P.gr->tail(front[front.size()-1]); |
222 else if( ! P.empty() ) |
291 else if( ! P.empty() ) |
223 return P.gr->tail(P.edges[0]); |
292 return P.gr->tail(P.edges[0]); |
|
293 else if( ! back.empty() ) |
|
294 return P.gr->tail(back[0]); |
224 else |
295 else |
225 return INVALID; |
296 return INVALID; |
226 } |
297 } |
227 GraphNode to() const { |
298 GraphNode to() const { |
228 if( ! P.empty() ) |
299 if( ! back.empty() ) |
|
300 return P.gr->head(back[back.size()-1]); |
|
301 else if( ! P.empty() ) |
229 return P.gr->head(P.edges[P.length()-1]); |
302 return P.gr->head(P.edges[P.length()-1]); |
230 else if( ! d.empty() ) |
303 else if( ! front.empty() ) |
231 return P.gr->head(d[0]); |
304 return P.gr->head(front[0]); |
232 else |
305 else |
233 return INVALID; |
306 return INVALID; |
234 } |
307 } |
235 |
308 |
236 }; |
309 }; |